Always 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"
I 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
Interesting he thought it was tedious - I thought this one was actually the closest to being like a real world software engineering task! No mathematical tricks or lateral thinking, just a gnarly problem that requires planning and breaking down into more manageable pieces. I actually really enjoyed it for that.
> 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.
How 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.
Norvig teaches a really cool, and challenging, class on Udacity called the "Design of Computer Programs"[0] in Python where you can learn his thought process on how to write reliable and beautiful software to solve interesting problems.
I'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).
I am a plumber too, and a good one, but I notice (if you forgo the time pressure: my fast solutions are always plumbing) that the language I use matters in my thinking and that is probably how I learnt them. When I have the time, I think solutions up (mostly in my head or on 'paper'(scratch buffer)) in lisp/scheme, haskell/idris or apl/k. The result, when I consider it elegant, is usually very nice after translating to another language.
For Scheme I think my thinking came from working through SICP many years ago while the other languages in the list force you basically to first think about a solution before you start typing.
I am not saying, obviously, people cannot think up these things straight in rust, python, c# etc, however, for me personally, it works much better if I first work it out in one of the others; it is way too tempting to grab for my plumbing wrench otherwise.
If 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.
I wouldn't worry about it. Jobs that require this are few and far between - so the necessity isn't there. HN have a wideon for this leetcode stuff. In reality, unless it's your hobby, you don't need to be able.
This 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.
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 !).
This 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.
Probably 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.
I 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.
This 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!
Day 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
It'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
def 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.
{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.
Norvig'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.
Even 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?
>what looks like exclusively, in Python rather than other interesting languages?
probably because he cares more about the problems and less about the language and python is a pleasant general purpose language (and ubiquitous in AI research)
I never understood why many software developers are so focused on languages rather than on problems, the language at the end of the day doesn't really matter, unless the problem is in a very peculiar domain.
Norvig is a teacher. His first choice was Lisp for a long time. He chooses Python because it is a good enough alternative for his teaching. You can find his motivation here: http://www.norvig.com/python-lisp.html
He is writing such programs, essays etc since long time on his website norvig.com, I don't think he only like python and definitely not the marketing at all.
My favorite essay is http://norvig.com/21-days.html after reading this essay you might change your opinion about he finding only python interesting.
I 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)
Why do we speak in english instead of other interesting languages? Between java, python, and haskell (which are the linguae francae of the papers which I tend to read, the first and last having replaced C and lisp during my lifetime) I think python is a defendable choice for minimising boilerplate while maximising potential readership.
As someone who has studied maths Proj Euler is infinitely more interesting especially in the harder questions. For me, most of time spent in advent of code is basically about parsing a blob of text. Project Euler inspires much more interesting ideas. Mostly it is number theory and algebra.
[+] [-] solaxun|5 years ago|reply
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"
[+] [-] tincholio|5 years ago|reply
[+] [-] robsws|5 years ago|reply
[+] [-] prezjordan|5 years ago|reply
> 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.
[+] [-] daveFNbuck|5 years ago|reply
[+] [-] Storm-Bringer|5 years ago|reply
Asking because for example most solutions to Day 1 I've seen are O(n^2)
[+] [-] O_H_E|5 years ago|reply
Yeah, I too smiled at his comment last week.
[+] [-] systemvoltage|5 years ago|reply
[+] [-] donkey-hotei|5 years ago|reply
[0] https://www.udacity.com/course/design-of-computer-programs--...
[+] [-] Jtsummers|5 years ago|reply
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
[+] [-] tluyben2|5 years ago|reply
For Scheme I think my thinking came from working through SICP many years ago while the other languages in the list force you basically to first think about a solution before you start typing.
I am not saying, obviously, people cannot think up these things straight in rust, python, c# etc, however, for me personally, it works much better if I first work it out in one of the others; it is way too tempting to grab for my plumbing wrench otherwise.
[+] [-] ZoomZoomZoom|5 years ago|reply
After that, it's just practice interspersed with data structure and algorithm research.
[+] [-] notretarded|5 years ago|reply
[+] [-] natalyarostova|5 years ago|reply
[+] [-] dwrodri|5 years ago|reply
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|5 years ago|reply
[+] [-] ykevinator|5 years ago|reply
[deleted]
[+] [-] edelans|5 years ago|reply
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 !).
[+] [-] thundergolfer|5 years ago|reply
In this case I think they work really well, and aren't stuck in places where they're not needed.
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] sundarurfriend|5 years ago|reply
[+] [-] monksdream|5 years ago|reply
[0]: https://github.com/norvig/pytudes/blob/master/requirements.t...
[+] [-] maccard|5 years ago|reply
[+] [-] raverbashing|5 years ago|reply
[+] [-] ZoomZoomZoom|5 years ago|reply
[+] [-] dmurray|5 years ago|reply
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|5 years ago|reply
[+] [-] unknown|5 years ago|reply
[deleted]
[+] [-] djaychela|5 years ago|reply
[+] [-] emmelaich|5 years ago|reply
Love it. There's so many bits of Python I've written where I should have had something like this.
[+] [-] yt-sdb|5 years ago|reply
> cat = ''.join
[+] [-] avl999|5 years ago|reply
[+] [-] yeswecatan|5 years ago|reply
[+] [-] sgk284|5 years ago|reply
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:
But that has a lot of duplication, so it'd probably be best to just use an imperative approach here and do something like:[+] [-] wodenokoto|5 years ago|reply
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.
[+] [-] daveFNbuck|5 years ago|reply
[+] [-] akho|5 years ago|reply
[+] [-] johndoe42377|5 years ago|reply
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.
[+] [-] bmitc|5 years ago|reply
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?
[+] [-] Barrin92|5 years ago|reply
probably because he cares more about the problems and less about the language and python is a pleasant general purpose language (and ubiquitous in AI research)
I never understood why many software developers are so focused on languages rather than on problems, the language at the end of the day doesn't really matter, unless the problem is in a very peculiar domain.
[+] [-] qart|5 years ago|reply
[+] [-] jp42|5 years ago|reply
My favorite essay is http://norvig.com/21-days.html after reading this essay you might change your opinion about he finding only python interesting.
[+] [-] nl|5 years ago|reply
Also: https://norvig.com/python-lisp.html
[+] [-] myle|5 years ago|reply
We don't have to all enjoy the same things.
In this particular case also, if you read his code, I would be surprised if you don't learn something.
[+] [-] zeroDivisible|5 years ago|reply
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)
[+] [-] 082349872349872|5 years ago|reply
[+] [-] foxes|5 years ago|reply
[+] [-] djur|5 years ago|reply