8 ms·

Advent of Code Solutions

309 points by abecedarius 10y ago

solaxun 10y ago
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!
- abecedarius 10y ago
  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.
dorianm 10y ago
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.)
- tedmiston 10y ago
  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.
- xapata 10y ago
  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.
- js8 10y ago
  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.
  - rubber_duck 10y ago
    >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.
    - js8 10y ago
      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).
      - rubber_duck 10y ago
        >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) vs. 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
- choppaface 10y ago
  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 ...
  - Kiro 10y ago
    Why?
  - kwhitefoot 10y ago
    That's just slander unless you tell us why.
  - kutkloon7 10y ago
    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.
    - taeric 10y ago
      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.
  - deleted 10y ago
    [deleted]
throwaway7645 10y ago
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.
- js8 10y ago
  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.
  - lispm 10y ago
    > 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)) -2) ((B 2 X1) (C 3 X2)) CL-USER 61 > (take '((a 1 x0) (b 2 x1) (c 3 x2)) :all '(1 2)) ((1) (2) (3)) CL-USER 62 > (take '((a 1 x0) (b 2 x1) (c 3 x2)) '(1 2) :all) ((B 2 X1)) CL-USER 65 > (take '((a 1 x0) (b 2 x1) (c 3 x2)) -2 -2) ((2 X1) (3 X2)) with steps: CL-USER 71 > (take '((a 1 x0 y0) (b 2 x1 y1) (c 3 x2 y2)) :all '(1 4 2)) ((1 Y0) (2 Y1) (3 Y2))
Buge 10y ago
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.
- niwri 10y ago
  I wouldn't be surprised if that behaviour was intentional.
  - johnfn 10y ago
    It is intentional. It allows a search for "pokemon" to match "Pokémon".
  - x3n0ph3n3 10y ago
    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. 1.https://en.wikipedia.org/wiki/Collation https://en.wikipedia.org/wiki/Collation
    - Pyppe 10y ago
      Transliteration. See e.g. https://en.m.wikipedia.org/wiki/Transliteration https://en.m.wikipedia.org/wiki/Transliteration
jblow 10y ago
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.
- MaulingMonkey 10y ago
  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...)
- joelgrus 10y ago
  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.
  - steveklabnik 10y ago
    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?
  - tptacek 10y ago
    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.
Dowwie 10y ago
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.
kutkloon7 10y ago
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.
- RodericDay 10y ago
  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.
  - chillee 10y ago
    I agree. In my experience, Project Euler is more computer science for mathematicians than math for computer scientists.
Tycho 10y ago
I love in Day 2 how he represents the keypad in string form, padded with . characters to simplify the edge detection logic.
- kornish 10y ago
  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.
plg 10y ago
I would like to see this done in C
- sinisterstuf 10y ago
  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 https://news.ycombinator.com/item?id=13259460 2: https://github.com/sinisterstuf/adventofcode https://github.com/sinisterstuf/adventofcode
hzhou321 10y ago
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.

309 points by abecedarius 10y ago

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!

abecedarius 10y ago
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.

dorianm 10y ago

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.)

tedmiston 10y ago
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.
xapata 10y ago
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.
js8 10y ago
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.
- rubber_duck 10y ago
  >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.
  - js8 10y ago
    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).
    - rubber_duck 10y ago
      >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) vs. 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
choppaface 10y ago
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 ...
- Kiro 10y ago
  Why?
- kwhitefoot 10y ago
  That's just slander unless you tell us why.
- kutkloon7 10y ago
  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.
  - taeric 10y ago
    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.
- deleted 10y ago
  [deleted]

throwaway7645 10y ago

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.

js8 10y ago
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.
- lispm 10y ago
  > 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)) -2) ((B 2 X1) (C 3 X2)) CL-USER 61 > (take '((a 1 x0) (b 2 x1) (c 3 x2)) :all '(1 2)) ((1) (2) (3)) CL-USER 62 > (take '((a 1 x0) (b 2 x1) (c 3 x2)) '(1 2) :all) ((B 2 X1)) CL-USER 65 > (take '((a 1 x0) (b 2 x1) (c 3 x2)) -2 -2) ((2 X1) (3 X2)) with steps: CL-USER 71 > (take '((a 1 x0 y0) (b 2 x1 y1) (c 3 x2 y2)) :all '(1 4 2)) ((1 Y0) (2 Y1) (3 Y2))

Buge 10y ago

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.

niwri 10y ago
I wouldn't be surprised if that behaviour was intentional.
- johnfn 10y ago
  It is intentional. It allows a search for "pokemon" to match "Pokémon".
- x3n0ph3n3 10y ago
  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. 1.https://en.wikipedia.org/wiki/Collation https://en.wikipedia.org/wiki/Collation
  - Pyppe 10y ago
    Transliteration. See e.g. https://en.m.wikipedia.org/wiki/Transliteration https://en.m.wikipedia.org/wiki/Transliteration

jblow 10y ago

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.

MaulingMonkey 10y ago
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...)
joelgrus 10y ago
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.
- steveklabnik 10y ago
  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?
- tptacek 10y ago
  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.

Dowwie 10y ago

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.

kutkloon7 10y ago

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.

RodericDay 10y ago
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.
- chillee 10y ago
  I agree. In my experience, Project Euler is more computer science for mathematicians than math for computer scientists.

Tycho 10y ago

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

kornish 10y ago
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.

plg 10y ago

I would like to see this done in C

sinisterstuf 10y ago
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 https://news.ycombinator.com/item?id=13259460 2: https://github.com/sinisterstuf/adventofcode https://github.com/sinisterstuf/adventofcode

hzhou321 10y ago

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.