[jimbokun]

Here is your 10x programmer:

https://norvig.com/sudoku.html

"In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about one page of code for the main idea and two pages for embellishments) using two ideas: constraint propagation and search."

If you gave this task to an "average" developer, how long would it take for them to implement? How many lines of code would it be? Would the implementation be correct? How long would their code take to execute?

    % python sudo.py
    All tests pass.
    Solved 50 of 50 easy puzzles (avg 0.01 secs (86 Hz), max 0.03 secs).
    Solved 95 of 95 hard puzzles (avg 0.04 secs (24 Hz), max 0.18 secs).
    Solved 11 of 11 hardest puzzles (avg 0.01 secs (71 Hz), max 0.02 secs).
    Solved 99 of 99 random puzzles (avg 0.01 secs (85 Hz), max 0.02 secs).

Does the average developer know what "constraint propagation" and "search" mean in the above sense, or remember enough about them from their CS class to recognize them as the right tools and how to implement them?

Also, can the average developer implement a spell checker from scratch on a single transcontinental flight?

https://norvig.com/spell-correct.html

So Norvig is always the paradigmatic example of the 10x developer, for me. Having a broad range of CS techniques at your disposal and knowing how and when to deploy them, is almost a super power.

[mjw1007]

I'm sure Norvig is very good, but I think the sudoku webpage is presenting a finished program in an idealised way, not recording the process he used to write it, false starts and all.

(It seems likely to me that there were some false starts, because eliminate() returns either `values` or False, when both of its callers would be just as happy if it returned True or False.)

[Tcepsa]

Not saying there weren't false starts, but your example of eliminate() is actually a fairly common idiom[0] where, when a function is testing things for "truthiness" or "falsiness", it will return the truthy or falsey value rather than actual True or False. It lets code be more brief because you can do e.g. a check for null and perform assignment of either the value or a default in a single statement, so for example something like this:

  if( maybeNullValue ) {
    myValue = maybeNullValue;
  } else {
    myValue = defaultValue;
  }

can instead be expressed as this:

  myValue = maybeNullValue || defaultValue;

I'm personally a little bit torn about it. On the one hand, now that I'm familiar with it I love how much more concise code can be. On the other, it can have a fairly negative impact on code maintainability: if someone comes along who isn't familiar with that idiom, they might have a bad time trying to figure out what's going on (or worse, they might take offense that all these predicates aren't returning True or False values and rewrite the whole mess--or you could end up with a mix of the two, where some functions follow the idiomatic convention and others return actual boolean values which is arguably the worst)

Also I'm not trying to say that there's not some YAGNI going on here--just that I suspect he did it that way somewhat reflexively, and that in that particular case we probably cannot infer he had originally intended to do something else with those results and then changed his mind later.

[0] at least in the Lisp world, which Norvig has extensive experience with[1]

[1] https://github.com/norvig/paip-lisp

[jimbokun]

He didn't give an implementation time for the sudoku solver, but he did say he completed the spell checker in a single transcontinental flight.

[WalterBright]

I don't remember how long it took me to do the spell checker challenge:

https://github.com/dlang/dmd/blob/master/src/dmd/root/spelle...

but I'm sure it was much longer than it took Peter. This checker is used by the D compiler to look for a misspelled identifier when a symbol lookup fails. The identifiers in scope form the dictionary.

It works surprisingly well. I added it to the Digital Mars C++ compiler as well.

https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...

[lonelappde]

> returns either `values` or False, when both of its callers would be just as happy if it returned True or False.)

That's pythonic.

You don't convert from a data type to Boolean.

[willvarfar]

I know I'm late to the party, but why isn't everyone mentioning Ron Jeffries infamous TDD Sudoku as a comparison?

A lot of the links are dead these days, I'm afraid, but back in 2007 this was the kind of thing that everyone on HN knew about!

http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-s...

[hyperpape]

I'm sure Norvig is exceptional in many ways, quite possibly 10x, but the tricky thing about examples is that some things that look hard from the outside aren't. They're just about familiarity.

I saw that you mentioned a spell-checker, and thought "I'd use levenshtein distance. That wouldn't be hard to implement on a flight. I wonder what he did that's better." Turns out, he used levenshtein distance, and tuned the results with frequency estimates. I don't know if I'd have thought of that, but it's also not a mysterious technique--I'm confident a lot of people who work more in related areas than I do would think of it.

[perl4ever]

“Four thousand dollars!” gasped the CEO. “All you did was walk over and push a little button on the side of that machine. Can you give us a breakdown?” The consultant jotted on a piece of paper and handed it to the CEO.

“Pushing button: $1 Knowing which button to push: $3999″

[jimbokun]

"...but the tricky thing about examples is that some things that look hard from the outside aren't. They're just about familiarity."

And that's how you become a 10x developer.

[hnick]

While I agree with your general point, the business world typically doesn't have much use for solo 'toy problems' and cares more about working in large teams and all that it entails.

I got into programming because I love the toy problems, but it means that once I have something 90% solved in my head it becomes a huge struggle to continue. Sometimes in my working life I'd have to whip something up to fix an issue or provide a POC which gets thrown away or given to a team (I don't care either way) and those were the best projects.

[zzzeek]

Norvig's work in those questions are more like the 100x developer category.

[charleslmunger]

If you want an answer to that question: https://news.ycombinator.com/item?id=3033446

[cwmoore]

Norvig is so another level maybe because of being so literate. I came across a Kakuro (Soduku * crossword) puzzle in a newsprint puzzle booklet, and failing to solve it with a pencil, attempted it in JavaScript.

I am now >10x at solving Kakuro puzzles with access to a command line and the repo (~100ms/10x10).

[fjfaase]

Solving a sudoku is just an exact cover problem, for which there already exist solvers. Just write a simple transformation program and you are done. https://www.iwriteiam.nl/D1009.html#9

[corporateslave5]

I’ve gotten solving a sudoku puzzle as an interview question, to be implemented in full in 45 mins.

[Recursing]

Same (not as an interview, as coding challenge), using simple backtracking and a high level language it's really easy. My solution wasn't anywhere near as good as Norvig's, though. (And today I would just use z3)

[lonelappde]

Solving suduko is a college homework assignment. Norvig's solution is simple and quick, but he spent decades dedicating his entire professional life to studying all manner of AI, so it's not clear his overall problem solving speed is.hifh including the time spent on past study. In the meantime he wasn't learning to be good at kernel hacking or UI development.