Hacker News new | past | comments | ask | show | jobs | submit login
Advent of Code Solutions (jupyter.org)
309 points by abecedarius on Dec 25, 2016 | hide | past | web | favorite | 49 comments

I knew he was working on these from seeing the leaderboard, and was reeeeally hoping he'd share the solutions, so I'm super happy to see this. What about you, Darius? Did you participate this year? I remember you from CS212 and would be interested in seeing your solutions as well!

No, I haven't started this year, though maybe I still will -- it's always interesting to see the Norvig treatment after having a go yourself.

There are 3 assembly code exercise: day 12, 23, and 25. The solutions in the post just interprets the code as is, which all run quite a while. I tend to write my code on a much slower computer and I being quite impatient, so I was forced to abort the program and forced myself to actually read the assembly code (input). It is actually quite interesting:

Day 12 calculates the fibonacci sequence, day 23 involves a big multiplication, and day 25 outputs the a number in binary format. If we run all additions and multiplications with "inc" and "dec", of course it is going to take forever (on my computer at least). So for me, I was forced to read the code and recognize the multiplication and algorithm and put in a couple "shortcut". If my computer is any faster, I might miss the fun.

Interesting that he used a non-ascii character (Ø) as a variable name. Also ctrl+f in Chrome seems to think this character is the same as o.

I wouldn't be surprised if that behaviour was intentional.

It is intentional. It allows a search for "pokemon" to match "Pokémon".

It's done with case-insensitive matching based on the rules of character collation [1], but I'm struggling to find a good article on the topic.


I feel like most of his Day 0 functions should be in Python's standard library (groupby, first, firstrue (e.g.: detect), counttrue (e.g. count with block in ruby), trace, etc.)

Gotta be careful of that groupby. Using defaultdict has the pitfall that it continues to insert new keys when looking up missing keys after you're done grouping. Sometimes it's better to use a regular dict and setdefault during the grouping, ensuring that, after the grouping, missing lookups will properly raise KeyError.

In fact, AFAIK, Norvig made that specific mistake previously.

Some of those are actually in itertools package.

In general, Python doesn't seem to include a function in its standard libraries if you can write it as an obvious combination of 2 or 3 existing functions or sequence comprehensions. Which is a good thing, you don't want to cognitively overload the users with too many similar building blocks.

>Which is a good thing, you don't want to cognitively overload the users with too many similar building blocks.

On the other hand if you've spent some time in a different high level language doing stuff like this in python feels too pedestrian.

Not sure what your point is - it may feel pedestrian, but consider the alternative.

Let's say, to "save users time" you decide to include all the meaningful combinations of some basic functions into your standard library. Then selecting from all those functions is about as time consuming than combining the two basic functions, unless you have memorized all of them by heart.

And then, what can also happen, if you haven't got them all memorized, you actually look up for a certain combination, only to find that particular one is for whatever reason missing from the library and you still have to compose it with the other functions you have.

The point is, there is a trade-off between time saved by having functions in standard library and time spent looking those functions up. So you don't want to have functions that are obvious combinations of 2-3 function, unless it's something very very common (e.g. a map function as a combination of monadic bind and return).

>there is a trade-off between time saved by having functions in standard library and time spent looking those functions up.

Meh, difficulty of writing such code is irrelevant in comparison to how these higher level functions read and compose, consider :

    next(x for x in seq if x > y, None)

    first(seq, lambda x: x > y, None)
    seq.first(lambda x: x > y, None)
the intent is very clear in the second example, it just has useless implementation details in the first.

I haven't done python in a while but every time I go back to it I find such edge cases where the code ends up being obfuscated or you write one-off functions that you need in random places and should be in std. Contrast with Clojure for eg. with it's rich collection manipulation standard library - data manipulation is high level and expressive

Too many small functions means name collisions. Names like "product" are precious real estate.

Most of them are only the slightest sprinkle of sytactic sugar over one-liners commonly used for puzzle problem solving but not real-world programming in Python.

It's funny seeing how Norvig implements some of these functions. I've seen a few of these used as Google interview questions and Norvig's solutions would not pass the hiring bar ...

That's just slander unless you tell us why.

Of course. It would be idiotic to expect 'code of advent' solutions to pass as production code, especially if you take into account the time pressure for submitting these solutions.

I get what you are saying. However, the comparison is to whiteboard interview questions. If these don't pass your bar... Think long and hard about what this implies about who you would not hire.


I love in Day 2 how he represents the keypad in string form, padded with . characters to simplify the edge detection logic.

Also love how he aliases `str.split` to `Keypad` so you can see the intention of his semantics that much more easily. And the assertion of keypad[2][2], as a quick reference point for himself. The whole thing is just so eminently understandable.

It's great to have a benchmark from which other work can be compared. Norvig's submissions are one example for the Python community. Hopefully, other submissions are raised for the other languages.

I don't understand why solutions to pretty trivial problems are upvoted so many times. Solutions to the very hardest project Euler problems would be far more interesting.

The very hardest PE problems are almost completely mathematical and require very straightforward code.

There's a few amazing computational ones interspersed, like the Numbermind one, but in general I didn't find that the further along I went the harder I worked out my elegant programming skills. It was mostly doing math on paper and pressing it into code.

I agree. In my experience, Project Euler is more computer science for mathematicians than math for computer scientists.

I know Norvig uses both Lisp and Python, but it seems like he is all Python these days. Nothing wrong with that, but a little depressing for Lisp.

It's not a shame for a language to lose against Python. Python has by far the best focus on usability of the standard libraries of all the languages I have ever seen (which includes major ones). As they say, "practicality beats purity".

Let me compare for example Lisp lists with Python lists. Lisp lists are in a way more low-level, lacking useful things as slices. Sure you can always write a function to do a slice, but the point is many useful functions are missing from the standard libraries. I tried to learn Common Lisp and Clojure (I like the language more than Python) but I was never more productive in it than in Python for this reason.

This year, I have actually done some AoC in Haskell, and it's a similar deal as with Lisp. There are plenty libraries, but they just don't work as well together. An example: I needed a queue. So I used Data.Seq, but, there is no pop() function. No big deal, for sure, but annoying. Another example: I wanted to put list or set into a hash table, but unfortunately, these are not defined as instances of Data.Hashable.

It's actually debatable whether list should be Hashable by default. Sure it would be practical, but someone could complain about the hashing implementation. And that's why Python is going to beat Haskell on these problems, where you simply don't want to worry about thousands of those little things.

I was actually thinking about building myself a "pythonic" Haskell prelude which would have similar design to Python standard libraries and the same attention to consistency.

I would expect Clojure's standard library to be just as useful as Python. I did last years contest in Clojure and it was quite straightforward and fairly little code.

Clojure is much much more usable than CL.

The way I understood the Clojure's standard library is that for many things (such as string manipulation) you have to fall back on Java libraries. And Java standard string libraries are AFAIK terrible compared to Python (again, no shame here).

That's certainly not true at all. Clojure has a rich string library where you can do all sorts of manipulation. Clojure's strings are also native data sequences so you can use the entire Clojure standard library's tools for manipulating data right on strings naturally.

I wrote full-time Clojure for two years, and did all of last year's Advent of Code in Clojure. In my entire life, I have never once written a line of Java and I have no idea the details of its standard library. That's how well-encapsulated Clojure is.

> Sure you can always write a function to do a slice

Common Lisp provides the function SUBSEQ for primitive slices.

  CL-USER 66 > (subseq '((a 1 x0) (b 2 x1) (c 3 x2)) 1 2)
  ((B 2 X1))
For some more slice functionality you could use the CL-SLICE lib.

It's also not too difficult to write. I wrote a multi-dimensional slice like Take in Mathematica:

  CL-USER 58 > (take '((a 1 x0) (b 2 x1) (c 3 x2))
                     '(1 3)
                     '(1 3))
  ((2 X1) (3 X2))

  CL-USER 59 > (take '((a 1 x0) (b 2 x1) (c 3 x2))
  ((B 2 X1) (C 3 X2))

  CL-USER 61 > (take '((a 1 x0) (b 2 x1) (c 3 x2))
                     '(1 2))
  ((1) (2) (3))

  CL-USER 62 > (take '((a 1 x0) (b 2 x1) (c 3 x2))
                     '(1 2)
  ((B 2 X1))

  CL-USER 65 > (take '((a 1 x0) (b 2 x1) (c 3 x2))
  ((2 X1) (3 X2))
with steps:

  CL-USER 71 > (take '((a 1 x0 y0) (b 2 x1 y1) (c 3 x2 y2))
                     '(1 4 2))
  ((1 Y0) (2 Y1) (3 Y2))

As I said, I am sure I can do it or find it in some library. But the integration of the APIs that Python has is missing. For example, I doubt your subseq works on strings (or bytestrings). But as I said, Python is IMHO the state of the art when it comes to PL usability (people have spent a lot of time thinking about use cases, sometimes at the expense of elegance or versatility), so no shame here.

> For example, I doubt your subseq works on strings (or bytestrings)

Your view of Common Lisp seems to be created more by assumptions and not so by actual real limitations.


    CL-USER 10 > (subseq "xxfoobarxx" 2 8)
Any vector:

    CL-USER 11 > (subseq #(10 30 20 100 50 30 20 20) 2 8)
    #(20 100 50 30 20 20)

    CL-USER 12 > (subseq #*10101010010101001010101 2 8)

> I doubt your subseq works on strings (or bytestrings)

Actually, it does.

Thanks for the reply. I'm actually in the same boat as you. I'd like to use CL and Clojure as they are definitely faster than Python (I don't think Jython or PyPy are actual solutions if you want all your code to run 10x faster). I've read several Lisp books and you never seem to get to the power of what you get in 3 chapters of Python or Perl. Granted, Lisp has super powers, but not sure if worth it. Damien Conway got interviewed by a Linux magazine awhile back (years) and goes over some of this. I keep waiting for someone to release a Lisp that takes off, but they all have big problems that make getting started a huge pain. Clojure needs you to understand Java, Emacs, Leinegein...etc.

> So I used Data.Seq, but, there is no pop() function

Perhaps "viewl :: Seq a -> ViewL" a could be used as pop.

> I wanted to put list or set into a hash table, but unfortunately, these are not defined as instances of Data.Hashable.

Are you using the "hashable" package? There does seem to be an instance for lists (when the elements of the list are themselves hashable):

> Hashable a => Hashable [a]

I am not even sure from the documentation what the ViewL abstraction is supposed to be good for.

OK, I stand corrected on Hashable, apparently what I said is not true for neither lists or sets.

This class of problems falls into a weird space for me. They are 'toy problems' but not I don't feel like I'd have fun doing them.

I had a lot of fun playing Shenzhen I/O and TIS-100, so if you want to do some programming challenges, I'd recommend trying those.

Yeah, I made it about 5 days in this year and then quit because I wasn't having fun.

Too many of the problems had the structure:

* here's Part A * submit solution for Part A * OK, now here's Part B * Part B is just different enough that you have to do a not-fun refactoring of your Part A code (that wouldn't be necessary if you'd just been asked to also design for Part B up front)

It was too much like working with an awful PM who can't decide what they want, and it mostly just made me angry.

I didn't get that far either, as I got too busy, but that's the part I liked the most about it: did I write my code well enough for part A that I didn't need to do a lot of work for part B? What could I have done differently to make the code resilient to requirements changes?

One way to look at it is that the part-2 problems are un-fun retreads of the part-1 problem.

The other (better, I think!) way of looking at it is that the part-2 problems are incentive for you to think carefully about your part-1 solution, so that it generalizes.

Norvig's keypad is a perfect example. Norvig's solution of a sentinel character generalizes, as would a solution based on a simple graph structure. But I plowed into it with a flat array of integers and the modulo operator, and had to rewrite for part-2; my solution was, in the context of the contest, inferior to Norvig's.

I made a graph and it adapted nicely to part 2. An advantage of the graph is that it would have handled the keypad becoming 3 dimensional or some other change that stopped it working as a simple grid. A big disadvantage is I made several errors while building the graph in both parts which took a while to track down.

I had a lot of fun with them because of how straightforward they were. I didn't spend any time with pencil and paper like I do with most programming challenges, but instead immediately started writing code in a new language (in this case, Ruby).

It was a breath of fresh air from the other problems where I have to do fancy things like "dynamic programming" and "math."

I solved the first couple from a previous year's in pure x86 as a means of making them more interesting. A few hundred lines of terrible, terrible x86.

I was amused when it performed even worse than expected - thanks to the lack of console buffering when I eschewed linking in the C stdlib (I forget if I instead invoked WriteConsole or what...)

I would like to see this done in C

I'd been following along in C, and I was very surprised to see how similar some solutions were, e.g. as mentioned above[1], drawing a map of the keypad with special characters for edge detection.

I've never finished an Advent of Code though, and I don't think I'd get further in another language than C, I just spend most of my Christmas/December time with family instead of coding; maybe if there was a February of Code I'd participate more actively.

I actually think C is an _ideal_ language for challenges like these: parse a simple input file, do one or two things and write out a number. In fact (with a small number of very big exceptions) my code is usually quite short and concise, even compared to solutions my friends write in higher level languages. I originally picked C, not because I thought I'd be finish blazing fast in it, but because I wanted to learn to use it better (also for work and fun), so with that said, what little code I've written is publicly displayed on GitHub[2] for (as Hungarians say) spitting at. It has some comments and sometimes longish explanations about "design decisions" in the commit messages. I really did end up learning a lot and I am much more fluent in C now than before (no more Google/StackOverflowing every single statement, hooray!), but perhaps the most surprising thing was:

You don't need a Makefile to build `thing` from `thing.c` if you don't need to pass any fancy arguments or anything, you can just write `make thing` without a Makefile and if there's a `thing.c` there it'll run gcc on it and produce your binary!

I'd like to finish these challenges someday. Let's see.

1: https://news.ycombinator.com/item?id=13259460

2: https://github.com/sinisterstuf/adventofcode

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact