Hacker News new | past | comments | ask | show | jobs | submit login
Norvig's Python programs to practice or demonstrate skills (github.com/norvig)
937 points by federicoponzi on Nov 27, 2017 | hide | past | favorite | 84 comments

Norvig is a beast. For those that don't know, he is high up in Google Research (AI director I believe) and also wrote the #1 AI textbook. He has the #1 AI course on coursera or edx too (can't remember which one). He's a big lisp advocate (look at his review of SICP on amazon), but also has the programs for his books in Java, and Python.

Regarding lisp, he made a post about language choice here: https://news.ycombinator.com/item?id=1803815

I think Lisp still has an edge for larger projects and for applications where the speed of the compiled code is important. But Python has the edge (with a large number of students) when the main goal is communication, not programming per se. In terms of programming-in-the-large, at Google and elsewhere, I think that language choice is not as important as all the other choices: if you have the right overall architecture, the right team of programmers, the right development process that allows for rapid development with continuous improvement, then many languages will work for you; if you don't have those things you're in trouble regardless of your language choice.

I agree for the first part. Common Lisp and Python are my favorite programming languages. I think the second is great for teaching programming and general use (where performance isn't a concern), while Common Lisp, in my view, is a "must-know" for any advanced programmer. Lisp is secret alien technology.

Although to be honest, there's Clojure, which isn't as easy to learn as Python nor as flexible/powerful as CL, but sits in confortable middle ground.

I think that's an excellent view of the tradeoffs between the two.

I'd like to ask him about a more ml-y python. Same syntax, same tinyness, but less mutable OO at its core.

Try http://coconut-lang.org

Not pure, not perfect, but still great!

It's like someone has looked at Python and thought "Python is too easy to read. Let's add LOTS more syntax to it".

Wow, this plus a persistent data structures library could be almost as much fun as clojure!

very nice, thanks

Everybody knows about AIMA (Artificial Intelligence, Modern Apporach) but Norvigs PAIP (Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp) is also a gem.

It's elegant learn programming, history of AI, and simple old school Common Lisp in the same package.

AI methods include GPS, Eliza style chatbots, symbolic math, constraint satisfaction, logic programming, natural language programming.

>Norvigs PAIP (Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp) is also a gem.

It's a wonderful book and it even includes some advanced advice on how to speedup Common Lisp code, which I have not found elsewhere!

I was curious, so I looked up the SICP review you mentioned: https://www.amazon.com/review/R403HR4VL71K8

Also liked this one (referring to sicp too):https://www.amazon.com/gp/review/R2C7L5KHUVHOR2?ref_=glimp_1...

His website contains a lot of gems:


I think the course to which you refer is on Udacity, with Thrun; I found it easier to read the book.

Thanks for correcting my mistake! It's def better than most I signed up for!

Last I read (a while ago), he was Director of Research at Google (not just AI). This was after being Director of Search (Quality), IIRC.

I get it that Peter Norvig is a very smart programmer. But can someone explain to me - like a farmer to his cow - how do these resources differ from typical programming challenges found on the web ?

How will these make me a better programmer ? Is each designed to teach a different programming concept or technique ? Are they useful in fields lower than machine learning or AI ?

What's the benefit of a program that detects palindromes ?

Peter Norvig has this unique style where he explains his design process in detail, including exploring the problem on example cases, writing multiple solutions, the thinking involved in moving from one solution to the next one, including profiling and finding bottlenecks etc., you see how he goes about problem solving and he is a master problem solver. In fact his writing provides a good opportunity to reflect on what designing programs even means: investigating and choosing trade-offs, choosing an adequate representation (data structure) for a problem etc. This illustrates on a small scale how a lot of the most serious software engineering happens, the engineering where you actually have a definite, hard problem to solve, rather than just making the program pretty by criteria on which there is no agreement etc.

He does this not only in those notebooks but for example also in his "Paradigms Of Artificial Intelligence Programming" book. I have not seen this done to any serious extent in any algorithm textbook or tutorials.

I code Python professionally (and passionately), and would consider myself quite experienced. His code in ' When Cheryl Met Eve: A Birthday Story' is the most beautifully constructed stuff in the world. That sort of stuff isn't about coding ability, it's about a reasoning process that some people have developed to such an extent that it's innately beautiful no matter how it's expressed. I'm sure his javascript solution would be nearly as beautiful.

> I'm sure his javascript solution would be nearly as beautiful.

I really like his Python code, but I think his Lisp code from PAIP is extremely underrated. In fact, it makes me sad he switched to Python for some AI tasks (same as Goodman & Tenenbaum in http://probmods.org) given that Lisp offers a unique feature for AI: homoiconicity.

This is something that I think will make a comeback with Bayesian program learning. For a glimpse of the future, see above link.

And how many great books and papers from before the early 80s are stacking dust in libraries and college archives ?

there are lots of lisp/fp books that aren't as known as PAIP. based on the few I took on ebay (henderson's recursion book and the likes) we might have a lot of surprises.

> His code in ' When Cheryl Met Eve: A Birthday Story' is the most beautifully constructed stuff in the world.

Where is this published? I couldn't look it up.

The content of the challenges aren't the focus. The main take-away is to see how Norvig does it after you've had a whack at it yourself. You can learn a lot by seeing how he reads the problem, dissects it into different functions, documents and tests them, and keeps an eye out for performance and computational complexity.

His code is highly readable and elegant, and I wish every single person I'll share a codebase with will have studied him before.

Ha, brilliant programmers can sometimes be hard to appreciate. They make problems look easy. But the simplicity comes from the complete understanding of the problem.

I think it's a trait of brilliant minds. They simplify things. I don't remember the exact quote, but it was something like this:

  * a fool doesn't understand
  * a normal person can be taught
  * a in intelligent person can teach
  * a genius can simplify

This reminds me of the quote attributed to Albert Einstein

“If you can't explain it to a six year old, you don't understand it yourself.”

I really thing what Einstein is getting at here is the ability to simplify things to the level that a six year old can understand it. Of course, you probably can't simplify the mathematics to the level of a six-year old, but you can simplify the concepts so that they are understandable by a six year old.

I've found this to be true in my own life. I think I understand something, but then I try to teach it to someone else and then I learn that I don't really understand it. So I have to go back and study and think about it so more until I understand it better. If I really understand thoroughly, inside and out, then I find that I am able to simplify things such that I can explain them to my young children.

This is why rubber duck debugging works. You start explaining to a rubber duckie what problem you have, how you're trying to solve it and what happens. Posting a question on a hostile forum or snarky IRC channel also works. When I think how to formulate my question best, to cause no misunderstanding, I often stumble upon the solution.

It is also why teaching people programming makes you a better programmer. Even if you're answering newbie questions, it often makes you re-evaluate your knowledge or realize you don't understand something as clearly as you thought. Even newbies have different needs and interests, so they ask different questions than you would.

And a slight twist on it, if you find the problem too hard, you're looking at it wrong.

We all had moments when we realized how stupid the solution was. Most of the things that eludes us trigger a chase for complexity when it's mostly trying simple stuff that aren't in our neural habits.

teaching involves didactic reduction, in other words: simplification; from the easy to the difficult, from the special case to the generalization.

You should check out Norvig's design of computer programs course on Udacity (https://www.udacity.com/course/design-of-computer-programs--...) where he uses these kinds of puzzle programs to teach programming design concepts. It is a hard but really rewarding course.

>I get it that Peter Norvig is a very smart programmer. But can someone explain to me - like a farmer to his cow - how do these resources differ from typical programming challenges found on the web ?

By virtue of being better written and more thought out.

Also, they are not "programming challenges". They are solutions to programming challenges.

His Design of Computer programs course on Udacity is amazing.


I second this. It's interesting and informative to watch him break down programs and to see his code. Plus, you get treated to selections from his Hawaiian shirt collection.

The problem with this course is that it is quite boring if you're not interested in given subjects - e.g. Poker lectures make me sleepy.

Tried to go through the course a few years ago. In my case it was the regex bit. Trying to write the code is a massive chore with with very little payoff for going through it, and needing to go through the instructions several times in a row. Gave up on the course there.

Some people gave up on that section (week 5 of 10) and went on with the rest of the course. That seems to work out OK.

(I felt a little bad about these reactions because I'd helped with that code. In its defense, I've also been told by a couple of people that they gained a lot by working through it.)

At one point I a friend was mentioning the regex golf https://xkcd.com/1313/ comic and how some insane person on the internet solved it. I mentioned my pains with the regex bit of the Design of Computer Programs course, and how Norvig had some Chtulhu like ability to write regexes that befuddle mortal minds. Lo and behold, it had been Norvig all along solving that. Python notebook available in the pytudes above.

Great course, learned a ton from it, but yeah lesson 3 where you had to build / follow him building a regex interpreter was definitely a beatdown for me. Everything else was pretty manageable, but still challenging.

He's not really trying to teach you poker or even how to write a poker program but rather how to solve problems by programming.

GP just means poker as an example it vehicle bores him. I agree - same with deck of card exercises.

Solve problems in particular domains - i.e. you have to understand the domain, learn rules - and it is very boring if the domain is not interesting for you.

Literate programming / ipython notebooks make me very uncomfortable.

Primarily the problem is that it's a living body of mutable state -- like an Excel spreadsheet, except it doesn't auto-update -- if I poke at some bit of it, and then re-evaluate a cell, some state will change, probably. And then maybe other cells' outputs will be invalid. Hmm, maybe I should re-evaluate the whole notebook? Oh, but some of the cells contain shell commands, for example to download a dictionary file from norvig.com. Do I want to do that? Maybe I should just undo the change I made. The ipynb is in git of course. But instead of a nice diff showing lines of code, the python code is held inside some JSON document.

Ipython notebook is beautiful technology, the front-end is really-well done. But accumulating all that mutable state goes against all my instincts as a programmer. I prefer editing .py files in my text editor, with Make when necessary. And then creating output from input with a single, transient, execution.

Yes this is a problem when the notebooks grow, but where do you draw the line, the work flow Jupyter uses is perfect for exploratory coding, but it gets complicated quickly

Yes, to be honest I do much more programming than exploratory data analysis currently. FWIW, here's how I use it when I want to use Jupyter:

- Write all my python code in .py files as usual.

- The Jupyter notebook contains calls to functions generating graphical/HTML/etc output, nothing else.

- Either use one of the various `reload*` functionalities to update the state of the persistent python process, or use `ipython console --existing` to create a conventional ipython shell sharing the same kernel as Jupyter and evaluate code in there.

Is there a mode to rerun everything on every update? That's how my https://github.com/darius/halp works, and it's fine for working out code with cheap test cases. You wouldn't want to do that for data analyses that take even a second, but I've found myself using it a lot to develop code.

You can run these notebooks for free in the cloud (on MyBinder.org provided by the Jupyter team). Just head there: https://mybinder.org/v2/gh/norvig/pytudes/master You may need to `pip install numpy`. Watch out images are ephemeral.

What the fuck is this magic, and how did I not know about this? I've been looking so long for something like this... Does it exist for scala? Java? This is amazing!!!

There's a nice Jupyter kernel for Clojure: https://github.com/didiercrunch/lein-jupyter.

If there is a Java/Scala kernel for Jupyter, then Yes. Even if not, we managed to get RStudio to work on that so there is hope for <your preferred environment>. I would reach out to github.com/jupyterhub/binderhub (you can say I redirected you there, same username on GH) the R support was prototyped a few weeks ago at a free workshop we ran. We'll be really happy to get Java/Scala people to contribute and invite them if we can do another workshop.

They are also run directly on github, but you can't edit them. Still useful if you just want to read, though.

Technically No, they are just rendered on GitHub (using nbconvert internally, so more like nbviewer.org). What you see on GH is the result of last run by Peter (which may be forged, or out of date). But thanks for pointing it out.

Oh, I thought that they were run because they had the output, which I didn't think would be commited to the repository. Good to know.

You can also run them on Azure Notebooks which is basically a free hosted jupyter notebook service for anyone to use:


basically 1) click the link 2) click clone 3) sign in (any gmail, msft id), then go to the notebooks directly and run them. You can also click Terminal for shell prompt.

The sign-in is required since you can edit the notebooks, store/modify data etc.

It is unclear how you would `pip install numpy` on mybinder.org

`!pip install numpy` in a notebook, or "new" > "terminal" and you have a shell...

Norvig's notebooks are my favorite resource for code reading. He has so much of them, written is such a nice, clean, clever but yet understandable and readable way, it's always a pleasure and amazing learning experience to go through them.

For example, going through his notebook for code advent (the first linked) [1].

[1] https://nbviewer.jupyter.org/url/norvig.com/ipython/Advent%2...

I really like his (How to Write a (Lisp) Interpreter (in Python)) : http://norvig.com/lispy.html

You learn to build a lisp interpreter in about 100 lines of python (you miss a few features like macros, but it's still quite complete). Very nice to learn how language interpretation works

He shows a more complete version in another essay http://norvig.com/lispy2.html

'Etudes for Programmers' itself remains an interesting read and entertaining problem set. And not a single one is about implementing a Red-Black tree from memory.

In fact, you won't find any mention of red-black trees anywhere in the book, because the term wasn't invented until a few months after it was published :P

This book looks interesting, but it's ridiculously overpriced for a book from 1978.

Yes, I'm not sure why it's never been reprinted or why used copies appreciate like they're made of pure bitcoin. There is a copy kicking around on libgen.

Is the adventofcode.com fun/educational/worthwhile? I see it starts again Dec 1. I like doing things like this but end up regretting it as it sucks too much time solving unnecessary problems.

Well I would consider any puzzle type problems technically "unnecessary" but I thought the adventofcode puzzles in 2016 were fun, well designed and tapped into some good CS algorithm and theory stuff.

I imagine the best way to make it educational would be to skip the problems you know how to solve and then try to solve the others without a whole lot of "cheating".

Obviously looking at resources to learn approaches to solving the problem isn't cheating, but there is some value in spending time just trying to figure out an approach before doing that.

> Is the adventofcode.com fun/educational/worthwhile?

For me, the answer to all three questions is - yes.

It depends on your previous knowledge, so some problems might seem too easy and/or some other problems might be too hard.

If you are an experienced programmer, maybe use AoC to learn/practice some language you didn't use before?

Here is code for "Artificial Intelligence: A Modern Approach" https://github.com/aimacode

Norvig wrote some of the Python version https://github.com/aimacode/aima-python

The majority of the python stuff is contributed by others

source: was a contributor

His regex golf seems kind of strange; he never mentions suffix trees. It seems like a fairly straightforward process to go through and mark the shortest distinguishing infix for each string in a generalized suffix tree.

What would be a similar resource but for Ruby?

http://rubyquiz.com/ is pretty good.

The algorithms I browsed make sense, but his coding style is peculiar, and somewhat un-pythonic.

For instance: https://github.com/norvig/pytudes/blob/master/py/SET.py

Why the CAPS name? Why are we defining `test` if we’re just running it on the next line - or rather, why are running the test in that same file as it’s definition, and then running an example 100k times?

Any professional python developer will know this, but when an adventuring friend calls me to help him debug something, with code modeled on what he’s seen in examples like these, I’ll likely just throw my hands up.

On the flip side, this isn’t bad for showing how something works, and the cognitive overload for a beginner to “get to the meat” if he’d used `argparse` or `click` might be a bit high.

`set` is a built-in. He probably didn't want to smash it.

Defining a function and immediately calling it prevents pollution of module scope. Without it, `photo` would be exported.

The tests are in the same file because it makes the example self-contained, I assume.

The experiments are run 100,000 times because they have a random component and this exercises the system.

Please re-read my comment. I understand what he did, but my points stand.

The name `SET` conveys little. Running the exercise in the same file is OK as it’s not in a module, but again - the work demonstrates algorithms well enough, but I can’t see this coding style as “smart” or “clean”. It’s not.

Top of the file:

""" Game of Set (Peter Norvig 2010-2015) """

It's the name of the problem being solved.

Yeah, `game.py` would've been great!

>Any professional python developer will know this, but when an adventuring friend calls me to help him debug something, with code modeled on what he’s seen in examples like these, I’ll likely just throw my hands up.

A professional python developer would also know the difference between code written for exposition purposes, code written to validate an idea, and code written for production use. They are not identical, and should not be. The concerns and aims of each code are different and they optimize for different things, and that is reflected in the coding style.

>but when an adventuring friend calls me to help him debug something, with code modeled on what he’s seen in examples like these, I’ll likely just throw my hands up.

I doub't changing the capitalization of a variable renders you unable to help. Seems like something that you could trivially filter out, and use it as an opportunity to educate.

That kind of software construction discipline is unnecessary for projects of this size.

Kind of OT, but... according to his CV Norvig was the Chief Designer for Harlequin?!


Am I the only one getting 500 for this link?

It's not just this page. GitHub is apparently having issues right now.


I had checked that page when I posted my comment. Somehow the issue got fixed before that note got posted. Thanks!

Working now

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