8 ms·
Peter Norvig's “pytudes” for Advent of Code 2020
- sundarurfriend 6y agoHTML view of the noteboook, in case Github is failing to load it for anyone else: http://archive.today/Xzyse http://archive.today/Xzyse (originally from https://htmtopdf.herokuapp.com/ipynbviewer/ https://htmtopdf.herokuapp.com/ipynbviewer/ , just didn't want to HN hug them).
- dwrodri 6y agoThis is very well-written code. I don't think anyone would bring into question Norvig's technical skills, but I wouldn't think someone like him would spend much time at his job writing code, or have much free time to program as a hobby. As someone who aspires to a position similar to Norvig's (directing research at an organization that is frequently applied in real life), I think it's really cool to see him having time to do stuff like this.
- markdown 6y agoIf you haven't, you should check out the free course he gave at Udacity.
- rurp 6y agoThat was one of the first courses I took that course as I was learning to program. Of course most of it was way over my head at the time, but even to a beginner it was clear that he really, really knows what he is doing.
- dwrodri 6y agoThanks for the recommendation! It looks quite good. Assuming you're referencing this: https://www.udacity.com/course/design-of-computer-programs--cs212 https://www.udacity.com/course/design-of-computer-programs--... I have been meaning to brush up on my interview skills, and I've found the lack of structure in LeetCode's Monthly problem sets to be quite frustrating. Every time I'd get stuck on a certain problem, I'd dive deep into the techniques behind the solution just to discard that knowledge the next day, as the selection of problems was seemingly random.
- ykevinator 6y agoYou've presented an excellent question, what could account for his having so much free time?
- solaxun 6y agoAlways look forward to these so I can compare my solutions afterwards. Sometimes it's almost frustrating to see how clean and concise the mess I made could have been, but I do learn a lot. It's like he gets as close to golfing as possible, without the obfuscation. Too bad he punted on 20... one of the few difficult problems this year. Usually the hard problems are where you really see the contrast between his solutions and the rest of us plebs. Do I sense a hit of frustration in his comment? ;) "too tedious for too little reward...." "sea monster as characters inelegant"
- O_H_E 6y ago> Do I sense a hit of frustration in his comment? ;) Yeah, I too smiled at his comment last week.
- daveFNbuck 6y agoThat one was tedious though. It's easy to see what the solution is, but it just takes a lot of time to write it up.
- dubya 6y agoI punted on part 2 of #20 as well, but came back to it the next day with a reasonable idea. Some of the tedious parts are easier to do by hand, like picking the corner of the map to start with on #20, or solving the uniqueness on #21. I'm still looking forward to reviewing how Norvig did most of the problems.
- tincholio 6y agoI had a similar feeling with that one, found the corners by counting edges on part one, and really got de-motivated for part two and actually solving the puzzle and looking for the patterns
- prezjordan 6y agoFull quote > Family holiday preparations kept me from doing Part 2 on the night it was released, and unfortunately I didn't feel like coming back to it later: it seemed too tedious for too little reward. I thought it was inelegant that a solid block of # pixels would be considered a sea monster with waves. Phew - I'm not alone.
- systemvoltage 6y agoHow do you algorithmically code like this? In my software engineering career, I am a plumber at best. Would fail hard at anyone who would ask me to code anything more than fizz buzz under time pressure. That said, I've built some incredible production worthy and robust systems that move mountains as a plumber. I am damn good at that.
- ZoomZoomZoom 6y agoIf you're ok with throwing time pressure out of the equation, then I think the main thing is just an aspiration to find a beautiful solution to a problem, where "beautiful" is being concise, efficient, short (and, rarely, original) in some proportion that suits your fancy. After that, it's just practice interspersed with data structure and algorithm research.
- Jtsummers 6y agoI'd recommend taking a look at his book Paradigms of AI Programming [0]. It really shows his thought process in developing solutions to problems. The only other way is practice, and in particular practice with languages that offer functional features. Notice his use of lambdas, assignment of existing functions/constructors to more accurate names (Passport instead of dict, day 4), and higher order functions (quantify). Those are things that really help in algorithmic code by increasing accuracy of the names of things to the application (almost creating a domain specific language). [0] https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
- jamestimmins 6y agoWhat kind of experience do you need for this book? For most ML you need linear algebra and whatnot, but this doesn't appear necessary here. If you've worked through something like SICP, do you think that would be sufficient?
- Jtsummers 6y agoThis is more classical AI, if you have a foundation in algorithms and data structures you can follow along. More experience, it'll be easier. If you've worked through SICP and that's your primary study of programming, then you can approach PAIP, but may need to take your time and look up related material to help you out.
- ZoomZoomZoom 6y agoIt's heartwarming to see he skipped d20p2.
- Jtsummers 6y agoFor me it followed (other than the pattern matching of the sea monster) directly from my backtracking solution to part 1 (versus his solution). One of the cases where doing the first thing that came to mind ("Well, gotta see where all the tiles go to see which are the corners") was the right thing, poor reading comprehension for the win! I specifically missed this line in the problem description which led to his (and many other people's) solutions: > but the outermost edges won't line up with any other tiles.
- thundergolfer 6y agoThis is another vote of confidence for type annotations. There still seems to be a debate between highly experienced Pythonistas whether typing is good or not. In this case I think they work really well, and aren't stuck in places where they're not needed.
- deleted 6y ago[deleted]
- emmelaich 6y ago> cat = ''.join() Love it. There's so many bits of Python I've written where I should have had something like this.
- yt-sdb 6y agoI was confused by this. It is: > cat = ''.join
- emmelaich 6y agoThanks, my bad!
- 082349872349872 6y agoIf a mathematician is someone who knows that 0 = 0 + 0 then would a pythonista be someone who knows that ''==''+'' ?
- bmitc 6y agoEven as a software engineer who studied mathematics, I just can't get excited about the type of problems found in Advent of Code and other such things, like Project Euler. Those problems amount to little puzzles and tricks and algorithms that have little to no context. What I find interesting about computing and programming is the representation and exploration of ideas. Also, I can't help but wonder. Why does the Director of Google Research and a computer scientist use his personal time to code, what looks like exclusively, in Python rather than other interesting languages? Is it a bit of marketing for Google and/or his book, or does he just like Python?
- zeroDivisible 6y agoI find it fascinating (in a very good way) that he does find time to code. Python is not a bad language, in all fairness, any programming language which picks your interest enough to spend time working with it is a good choice. The added benefit of Python is the ease of using something like Jupyter notebooks, which make it trivial to iterate. (disclaimer: I coded more in Ruby than in Python, but I still enjoy both)
- bmitc 6y ago> The added benefit of Python is the ease of using something like Jupyter notebooks, which make it trivial to iterate. Although, other languages do have better REPLs, allowing easier iteration than Python's REPL. Some languages, have both a better REPL and notebook-style programming, such as F#. But I was really more curious rather than saying which language would be "better".
- djur 6y agoIs Python uninteresting?
- bmitc 6y agoI personally don’t think it is because in the face of many modern languages, it doesn’t do any one thing the best and doesn’t present an interesting paradigm. Is there something it does interesting that I can’t find in languages like F#, Racket, or Elixir? But my question was trying to understand if Python has some hidden mojo that Norvig really likes or if he uses it like this publicly because he’s a top leader at a company that also uses it heavily. People listen to people like that in positions like his, and if he did all his solutions in Julia, F#, or whatever, that’d probably route a good amount of attention to those other languages that Google and his book doesn’t really use or hire for.
- johndoe42377 6y agoNorvig's code is gold, even back from the times of PAIP (which is still definitely a must read). His "poker" course (on YouTube) is also golden standard. Why? The background in math, basic data structures and logic, so one know the range and boundaries of what is possible. Plus careful attention to details, like it is in any art.
- yeswecatan 6y agoCan someone please explain how `for y in nums & {2020 - x} ` in his day 1 solution?
- daveFNbuck 6y ago{2020 - x} is a single item set. nums & {2020 - x} does set intersection with nums, which restricts nums to either the item that sums with x to 2020 or nothing if there is no such item in nums.
- wodenokoto 6y agodef day1_1(nums): "Find 2 distinct numbers that sum to 2020, and return their product." return first(x * y for x in nums for y in nums & {2020 - x} if x != y) `nums` is a set of integers `nums & {2020 - x}` Finds all the numbers that are in the set of `nums` and the set of `{2020 - x}` - this basically extracts a number, `y`, for which `x+y = 2020`. So for each x in nums, he extracts a number from nums that, added to x, equals 2020. If there is such a number y, he checks if it is the same as x, and only if it is different, does he yield in his generator, as the product of y and x. It's succint, but not exactly readable, imho.
- sgk284 6y agoIt's a bit overly clever. I am a huge fan of Peter Norvig (and he was once my skip-level boss), but I'd call this code out in a code review for being obtuse. Notice that the input, `nums`, is a set. So he's taking the intersection of two sets. One set always has one item, so the result will be a collection with either 0 or 1 items. It could have also been written as: first(x * (2020 - x) for x in nums if (2020 - x) in nums and x != (2020 - x)) But that has a lot of duplication, so it'd probably be best to just use an imperative approach here and do something like: def day1_1(nums): "Find 2 distinct numbers that sum to 2020, and return their product." for x in nums: y = 2020 - x if x == y: continue if y in nums: return x * y
- philshem 6y agowhen I saw the first() function, I thought it was some default python that was new to me. But he defines it above in his commonly used functions: def first(iterable, default=None) -> object: "Return first item in iterable, or default." return next(iter(iterable), default)
- akho 6y agoThe 'timing' section is disappointing. All very clean though.
- edelans 6y agoIf you like this, you will love https://github.com/mebeim/aoc/tree/master/2020 https://github.com/mebeim/aoc/tree/master/2020 The guy created very clean python solutions, and very insigthful walkthrough (although a bit wordy some times). It was my go to repo after validating my solutions on AoC (he managed to publish daily during the whole challenge !).
- monksdream 6y agoProbably the most indicative part of Norvig's code beauty is the requirements file [0]. With python developers being infamous for importing obscure/questionable libraries for even a simple task, I love how Norvig solved all these with just native libraries and the staples numpy/plt. [0]: https://github.com/norvig/pytudes/blob/master/requirements.txt https://github.com/norvig/pytudes/blob/master/requirements.t...
- raverbashing 6y agoI just find Norvig's style of "functional Python" lovely in its own way (with noted disregard of Pep8 and other "best practices")
- dmurray 6y agoI thought I spotted a bug on the very first day, part 2. def day1_2(nums): "Find 3 distinct numbers that sum to 2020, and return their product." return first(x * y * z for x, y in combinations(nums, 2) for z in nums & {2020 - x - y} if x != z != y) The last line (if x != z != y) returns true when x and y are equal and z is different. But x and y are already constrained to be different since nums is a set and itertools combinations picks distinct elements from the iterable. If the test had been x != y != z it would have been a bug.
- norvig 6y agoGood point, dmurray. It was a subtle point here, and probably I should have commented on it.
- deleted 6y ago[deleted]
- djaychela 6y agoThis was precisely the kind of thing I was looking for. I've done AOC for a few years, and did OK this year (got 2 stars on all but 3 days, and one star on all but 2), but being able to compare my ramshackle, simplistic code to something like this is the project for a month - break down one a day.... I'll do this in february, so thanks for posting that, OP!
- avl999 6y agoDay 5 part 1 solution is interesting. I had implemented it the obvious way doing a binary search. I didn't realize you could represent that string as binary and get the equivalent integer. That's really cool however I am not sure I get the idea behind why that actually works