7 ms·

Peter Norvig's Sudoku solver: Clojure & Python side by side

143 points by redacted 16y ago

nickik 16y ago
This is very, very cool. I wanted to look at that for a long time. This gives me a good reason.
d0m 16y ago
As much as I like lisp the beauty, strength and philosophy of Lisp, it seems like I can't make the switch in my real production project. Why? Because of the readability: (Taken from the article) (let [width (inc (apply max (map (comp count values) squares))) line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))] So, I see that and I'm like, wtf, where do I start. let width .. inc apply max of map comp coun, wtf. Let's start from the end. map all squares with comp count values, take the max of those, increment it, put that in width. ok then, line join repeat 3 join.. wtf. let's try it from the end; minus three times the width repeat.. ok, repeat 3width '-', then, join this, repeat it 3 times, then join again with +, and put that in line. I always struggle like that when reading lisp, people always give example like: (map square '(1 2 3 4)) where you can read it all in one pass.. but real code is usually more complicated. So, if I had to rewrite that more clearly, I'd probably just separate it in more functions so I don't have to have more than, say 4 nested (). And, yeah, the problem is not that much the "read from the end", but more about the actual work of each line of lisp being a puzzle to guess where to start reading it. Some are better to read up front, others are better to start from the last. Sometime you skip the first part, and read the last part, then come back at the beginning. That is what trouble me. I want to be able to read code as fast as possible - skim over it while understanding it. Now, you might argue that you can write nested stuff in every languages. True enough BUT it seems like the philosophy in python is more about making things clearer and using more function if it makes everything simpler/easier to maintain and understand.. while in practically all lisps code I read, it feels like it is a write-only code without thought about you will read it after. Is it because all the "Here's why lisp is better" are written by new-lisper who are too much excited as they can now use closures and nest everything rather than using simple, yet useful, normal functions? When I read lisps forum, it's always about how that or that doesn't support tail recursive function or why macro rocks everything, but never talking about readability and good practices about not nesting everything up. Yeah, they say to use real editor, to never look at the (), to align thing smartly.. I don't know for you, but I feel like my brain works in a kind of stack. I can put some stuff in my short memory, but I can't put more than say 5-6 stuff at once. And when I see this: (let [width (inc (apply max (map (comp count values) squares))) It just seem too much to read it quickly; I need to stop and think. Yeah, some laugh at me saying "Yeah, you need to think*! You are not used to that! Well, no, when I'm reading a book, I like to think about the concept or the story, not trying to figure out how to read that complicated sentence. When I read python code, I think about pattern, modularity, what's the goal of the actual file. When I'm reading lisp, I can't go quickly into it because of those 10 levels nested function. /end of rant.
- deleted 16y ago
  [deleted]
  - evanrmurphy 16y ago
    Hmm... I just tried it, and backslashes don't seem to work as a way to escape Hacker News markup. Were you kidding? Update: Ah, it looks like you can get literal asterisks if you use your whitespace carefully: * asterisk * another one emphasis
    - deleted 16y ago
      [deleted]
    - m_myers 16y ago
      Nope, not kidding, just ignorant. I'll delete my comment.
- swannodette 16y ago
  (inc (->> squares (map (comp count values)) (reduce max))) Similar to the Python | operator that came up yesterday.
- nickik 16y ago
  len(values[s]) for s in squares) (map (comp count values) squares) How is that better! If you know the standard function this is super easy (in both languages). Note clojure is just one pure function call nothing fancy. (inc (apply max 1+max The expressivness is tiny bit better in python because the max function looks at the type of the input. apply is a commen pattern that is easy to anderstand. The python way is a little bit easier to read but the clojure way makes the library simpler. line = '+'.join(['-'*(width*3)]*3) line (join \+ (repeat 3 (join (repeat (* 3 width) \-)))) The thing that makes python shorter here is that they alow math on non number. I don't think that a good idea in general but that up to the language designers taste. The diffrence between the code is basiclly that in clojure you have to use repeat two times instead of * and one more join. So only real diffrences are on the first line clojure uses apply and on the second repeat instead of join. I think is just a matter of training. Much harder then the language reading is to know what the standard functions really do.
macmac 16y ago
To those questioning Clojure's performance I will just leave this: http://meshy.org/2009/12/13/widefinder-2-with-clojure.html http://meshy.org/2009/12/13/widefinder-2-with-clojure.html here.
andrewcooke 16y ago
Why is Clojure so slow (more exactly, why is it as slow as Python)? Naively I would have expected it to be much faster than Python - it's not.
- dpritchett 16y ago
  My guess is because the Python example was written by Peter Norvig.
  - sunkencity 16y ago
    Clojure is not a very fast language.
    - swannodette 16y ago
      http://shootout.alioth.debian.org/u32/which-language-is-best.php http://shootout.alioth.debian.org/u32/which-language-is-best... Not true according to these microbenchmarks and certainly not in my own experience.
      - sunkencity 16y ago
        YMMV. I find that stuff I write in Ruby is faster than that I write in clojure. I suppose it depends on the problem space, if your problems are greatly speeded up by mutability and C bindings then clojure is not a perfect fit.
        igouy 16y ago
        Do you see why people might have thought your comment was misleading, with the "fast stuff in C" not in Ruby? :-) http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=clojure&lang2=yarv http://shootout.alioth.debian.org/u32/benchmark.php?test=all...
        fogus 16y ago
        I find that stuff I write in Ruby is faster than that I write in clojure. Have you considered the possibility that the problem is not with Clojure?
sunkencity 16y ago
Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language. Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.
- nickik 16y ago
  > Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language. Clojure always sad its designed for CONCURENCY and he said that Clojure has great primitives for parallism. Most people just dont know the diffrence. > Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. That wasn't a designgoal of clojure to provid parallism just out of box. It maybe is a designgoal now because everybody wants it to be. > But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times. pmap does work great for some things but just thinking you can throw in some 'p'-s want wrok. Rich or anybody else never claimed that this will be possible he infact always said that it wan't but people in the internet just dont listen that well.
  - Luyt 16y ago
    Clojure always said its designed for concurrency and he said that Clojure has great primitives for parallelism. Most people just dont know the difference. Well, here's the difference (according to Wikipedia): Parallelism - a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). There are several different forms of parallel computing: bit-level, instruction level, data, and task parallelism. Parallelism has been employed for many years, mainly in high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling. Concurrency - a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the Parallel Random Access Machine model and the Actor model.
SeanDav 16y ago
Don't want to start a religious war, but to me the Python code just looks more clean. I am amazed that Python ran anywhere close to Closure in terms of speed, let alone faster!
- nickik 16y ago
  Its a straight code port. I think it would if norvig would of used CL or Clojure you could say the same thing to a python port. I do agree that the python code looks a little cleaner but both look fine.
  - alecco 16y ago
    I really like Python, but CPython is an ugly monster. Edit: did the down-voters ever cared to read the code or even write a Python module in C?
    - nickik 16y ago
      Isn't pypy pretty fast and feature comple? Im not up to date.
      - kingkilr 16y ago
        Yes, our current release implements Python 2.5 completely, and our trunk implements 2.7. As for speed, I'll let: http://speed.pypy.org/ http://speed.pypy.org/ speak for itself.
        igouy 16y ago
        Is there a memory use comparison?
    - Confusion 16y ago
      I think that, like me, the downvoters don't understand what CPython has to do with anything.
shawndumas 16y ago
to see the code side-by-side http://tin.nu/sudoku.html http://tin.nu/sudoku.html
scott_s 16y ago
The design of the Clojure code can be clearly seen from the Python code. But I'm not sure if that's idiomatic Clojure. I'd like to see what the Clojure version would look like if a Clojure programmer solved the problem without looking at the Python code first. That would give me more insight into the differences between the languages.
- puredanger 16y ago
  Yeah, I started a port of this code into Clojure about a year ago with no attempt to keep the design and it diverged a bit. I never finished it though as my plane landed. :)
- swannodette 16y ago
  Follow Norvig's lead from Paradigms of Artificial Inteligence - write fast embedded paradigms. So write a performant Constraint Solver DSL couple it with a performant Prolog DSL. Solve all kinds of problems declaratively instead of just Sudoku. I've been working on that https://github.com/swannodette/logos https://github.com/swannodette/logos ;)
dfan 16y ago
I feel like his reduce-true could be implemented with take-while and reductions, but my Clojure isn't strong enough to produce it. (last (take-while identity (reductions f ns)))) is close, but we need to take one more element than take-while does.
rdtsc 16y ago
Same thing for Erlang implementation: https://github.com/apauley/sudoku-in-erlang https://github.com/apauley/sudoku-in-erlang Initially Python was faster, however after some discussion and some performance optimisations Erlang got faster: http://erlang.org/pipermail/erlang-questions/2011-March/057176.html http://erlang.org/pipermail/erlang-questions/2011-March/0571... Of course, it is worth keeping in mind that they didn't also go and try to optimize the Python version. So perhaps after doing that Python would win again.
kqueue 16y ago
The spikes you are mentioning might be due to the OS lowering your process priority. If you are on a FreeBSD machine, try running rtprio(1) to avoid the OS changing the process priority upon extensive CPU usage.
- klochner 16y ago
  The spikes are from hard problem instances - he's not running on the same data set each time. From Norvig's post: But the main message is that the mean and median stay about the same even as we sample more, but the maximum keeps going up--dramatically. The standard deviation edges up too, but mostly because of the very few very long times that are way out beyond the 99th percentile. This is a heavy-tailed distribution, not a normal one.
- mjb 16y ago
  They are more likely due to properties of the puzzles themselves than operating system behaviour, especially on a modern operating system on a multi-core machine. Plus, in the original Norvig article (http://norvig.com/sudoku.html http://norvig.com/sudoku.html) he talks about several puzzles which take 10s and 100s of seconds to complete, which is extremely unlikely to be due to scheduler behaviour. With languages like Python and Clojure several background processes (like GC pauses) could also contribute to some drops in throughput. Of course, it would be easy to tell these cases apart by counting operations (backtracks, etc) rather than time.
beagle3 16y ago
It is not really comparable, yet, I will post Arthur Whitney's Sudoku solver (in the K language) , in its entirety here: p,:3/:_(p:9\:!81)%3 s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x} ( can be found with a test case in http://nsl.com/k/sudoku/aw3.k http://nsl.com/k/sudoku/aw3.k ) The Norvig code is smarter - it always tries to fill the square with the least options. The Whitney code is dumb - it just recursively tries everything that's not blocked by peers in order. Both backtrack on failure. The codes are equally general - both work off a data driven peer list (peers, p). The K code runs much faster for most boards, but there are boards in which the Norvig heuristic makes a x100 difference. Personally, I prefer the K version, although I'm aware I am in the minority.
- wewyor 16y ago
  You are probably only in the minority because K, J, APL and what have you look like perl turned up to 11 for those of us who are unfamiliar with the syntax. Though if you consider that these are all vector programming languages, they are really made for this kind of thing.
- deathflute 16y ago
  Arthur's languages are awesome, no doubt about it. But the fact remains that they are proprietary and prohibitively so. As much as you romanticize k/q, I bet you can't even afford to run it on your home computer, let alone do any real work on it.
  - beagle3 16y ago
    J, which is close enough, was always free-to-use and recently open sourced https://github.com/openj/core https://github.com/openj/core K4/Q 32-bit is free for noncommercial use http://kx.com/trialsoftware.php http://kx.com/trialsoftware.php and has been from the day it became generally available. (And before that, k2/k3/ksql were similarly available) A free / open source K3 interpreter is being developed in https://github.com/kevinlawler/kona https://github.com/kevinlawler/kona , and while incomplete it is already quite capable. Oh, and Kx are (or at least were) quite reasonable with commercial use licenses for businesses that can't yet afford them. > Arthur's languages are awesome, no doubt about it. That is the only true thing you wrote.

143 points by redacted 16y ago

This is very, very cool. I wanted to look at that for a long time. This gives me a good reason.

d0m 16y ago

As much as I like lisp the beauty, strength and philosophy of Lisp, it seems like I can't make the switch in my real production project. Why? Because of the readability: (Taken from the article) (let [width (inc (apply max (map (comp count values) squares))) line (join \+ (repeat 3 (join (repeat (* 3 width) \-))))] So, I see that and I'm like, wtf, where do I start. let width .. inc apply max of map comp coun, wtf. Let's start from the end. map all squares with comp count values, take the max of those, increment it, put that in width. ok then, line join repeat 3 join.. wtf. let's try it from the end; minus three times the width repeat.. ok, repeat 3width '-', then, join this, repeat it 3 times, then join again with +, and put that in line. I always struggle like that when reading lisp, people always give example like: (map square '(1 2 3 4)) where you can read it all in one pass.. but real code is usually more complicated. So, if I had to rewrite that more clearly, I'd probably just separate it in more functions so I don't have to have more than, say 4 nested (). And, yeah, the problem is not that much the "read from the end", but more about the actual work of each line of lisp being a puzzle to guess where to start reading it. Some are better to read up front, others are better to start from the last. Sometime you skip the first part, and read the last part, then come back at the beginning. That is what trouble me. I want to be able to read code as fast as possible - skim over it while understanding it. Now, you might argue that you can write nested stuff in every languages. True enough BUT it seems like the philosophy in python is more about making things clearer and using more function if it makes everything simpler/easier to maintain and understand.. while in practically all lisps code I read, it feels like it is a write-only code without thought about you will read it after. Is it because all the "Here's why lisp is better" are written by new-lisper who are too much excited as they can now use closures and nest everything rather than using simple, yet useful, normal functions? When I read lisps forum, it's always about how that or that doesn't support tail recursive function or why macro rocks everything, but never talking about readability and good practices about not nesting everything up. Yeah, they say to use real editor, to never look at the (), to align thing smartly.. I don't know for you, but I feel like my brain works in a kind of stack. I can put some stuff in my short memory, but I can't put more than say 5-6 stuff at once. And when I see this: (let [width (inc (apply max (map (comp count values) squares))) It just seem too much to read it quickly; I need to stop and think. Yeah, some laugh at me saying "Yeah, you need to think*! You are not used to that! Well, no, when I'm reading a book, I like to think about the concept or the story, not trying to figure out how to read that complicated sentence. When I read python code, I think about pattern, modularity, what's the goal of the actual file. When I'm reading lisp, I can't go quickly into it because of those 10 levels nested function. /end of rant.

deleted 16y ago
[deleted]
- evanrmurphy 16y ago
  Hmm... I just tried it, and backslashes don't seem to work as a way to escape Hacker News markup. Were you kidding? Update: Ah, it looks like you can get literal asterisks if you use your whitespace carefully: * asterisk * another one emphasis
  - deleted 16y ago
    [deleted]
  - m_myers 16y ago
    Nope, not kidding, just ignorant. I'll delete my comment.
swannodette 16y ago
(inc (->> squares (map (comp count values)) (reduce max))) Similar to the Python | operator that came up yesterday.
nickik 16y ago
len(values[s]) for s in squares) (map (comp count values) squares) How is that better! If you know the standard function this is super easy (in both languages). Note clojure is just one pure function call nothing fancy. (inc (apply max 1+max The expressivness is tiny bit better in python because the max function looks at the type of the input. apply is a commen pattern that is easy to anderstand. The python way is a little bit easier to read but the clojure way makes the library simpler. line = '+'.join(['-'*(width*3)]*3) line (join \+ (repeat 3 (join (repeat (* 3 width) \-)))) The thing that makes python shorter here is that they alow math on non number. I don't think that a good idea in general but that up to the language designers taste. The diffrence between the code is basiclly that in clojure you have to use repeat two times instead of * and one more join. So only real diffrences are on the first line clojure uses apply and on the second repeat instead of join. I think is just a matter of training. Much harder then the language reading is to know what the standard functions really do.

macmac 16y ago

To those questioning Clojure's performance I will just leave this: http://meshy.org/2009/12/13/widefinder-2-with-clojure.html http://meshy.org/2009/12/13/widefinder-2-with-clojure.html here.

andrewcooke 16y ago

Why is Clojure so slow (more exactly, why is it as slow as Python)? Naively I would have expected it to be much faster than Python - it's not.

dpritchett 16y ago
My guess is because the Python example was written by Peter Norvig.
- sunkencity 16y ago
  Clojure is not a very fast language.
  - swannodette 16y ago
    http://shootout.alioth.debian.org/u32/which-language-is-best.php http://shootout.alioth.debian.org/u32/which-language-is-best... Not true according to these microbenchmarks and certainly not in my own experience.
    - sunkencity 16y ago
      YMMV. I find that stuff I write in Ruby is faster than that I write in clojure. I suppose it depends on the problem space, if your problems are greatly speeded up by mutability and C bindings then clojure is not a perfect fit.
      - igouy 16y ago
        Do you see why people might have thought your comment was misleading, with the "fast stuff in C" not in Ruby? :-) http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=clojure&lang2=yarv http://shootout.alioth.debian.org/u32/benchmark.php?test=all...
      - fogus 16y ago
        I find that stuff I write in Ruby is faster than that I write in clojure. Have you considered the possibility that the problem is not with Clojure?

sunkencity 16y ago

Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language. Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times.

nickik 16y ago
> Interesting that the clojure stuff is slower than python. From what I gather most clojure stuff never actually gain any of the possible multi-core performance boost that is one of promises of the language. Clojure always sad its designed for CONCURENCY and he said that Clojure has great primitives for parallism. Most people just dont know the diffrence. > Not that I don't like clojure, but part of the hype is that it's supposed to do a lot of the scaling inherently just by the design of the language. That wasn't a designgoal of clojure to provid parallism just out of box. It maybe is a designgoal now because everybody wants it to be. > But in reality it's never that simple. Switching from map to pmap doesn't do much, actually a whole different way of writing the code is necessary. I'd like to see a version of this that tries to maximise multi core performance, and see what a 12-core mac pro can do with the execution times. pmap does work great for some things but just thinking you can throw in some 'p'-s want wrok. Rich or anybody else never claimed that this will be possible he infact always said that it wan't but people in the internet just dont listen that well.
- Luyt 16y ago
  Clojure always said its designed for concurrency and he said that Clojure has great primitives for parallelism. Most people just dont know the difference. Well, here's the difference (according to Wikipedia): Parallelism - a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel"). There are several different forms of parallel computing: bit-level, instruction level, data, and task parallelism. Parallelism has been employed for many years, mainly in high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling. Concurrency - a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the Parallel Random Access Machine model and the Actor model.

SeanDav 16y ago

Don't want to start a religious war, but to me the Python code just looks more clean. I am amazed that Python ran anywhere close to Closure in terms of speed, let alone faster!

nickik 16y ago
Its a straight code port. I think it would if norvig would of used CL or Clojure you could say the same thing to a python port. I do agree that the python code looks a little cleaner but both look fine.
- alecco 16y ago
  I really like Python, but CPython is an ugly monster. Edit: did the down-voters ever cared to read the code or even write a Python module in C?
  - nickik 16y ago
    Isn't pypy pretty fast and feature comple? Im not up to date.
    - kingkilr 16y ago
      Yes, our current release implements Python 2.5 completely, and our trunk implements 2.7. As for speed, I'll let: http://speed.pypy.org/ http://speed.pypy.org/ speak for itself.
      - igouy 16y ago
        Is there a memory use comparison?
  - Confusion 16y ago
    I think that, like me, the downvoters don't understand what CPython has to do with anything.

shawndumas 16y ago

to see the code side-by-side http://tin.nu/sudoku.html http://tin.nu/sudoku.html

scott_s 16y ago

The design of the Clojure code can be clearly seen from the Python code. But I'm not sure if that's idiomatic Clojure. I'd like to see what the Clojure version would look like if a Clojure programmer solved the problem without looking at the Python code first. That would give me more insight into the differences between the languages.

puredanger 16y ago
Yeah, I started a port of this code into Clojure about a year ago with no attempt to keep the design and it diverged a bit. I never finished it though as my plane landed. :)
swannodette 16y ago
Follow Norvig's lead from Paradigms of Artificial Inteligence - write fast embedded paradigms. So write a performant Constraint Solver DSL couple it with a performant Prolog DSL. Solve all kinds of problems declaratively instead of just Sudoku. I've been working on that https://github.com/swannodette/logos https://github.com/swannodette/logos ;)

dfan 16y ago

I feel like his reduce-true could be implemented with take-while and reductions, but my Clojure isn't strong enough to produce it. (last (take-while identity (reductions f ns)))) is close, but we need to take one more element than take-while does.

rdtsc 16y ago

Same thing for Erlang implementation: https://github.com/apauley/sudoku-in-erlang https://github.com/apauley/sudoku-in-erlang Initially Python was faster, however after some discussion and some performance optimisations Erlang got faster: http://erlang.org/pipermail/erlang-questions/2011-March/057176.html http://erlang.org/pipermail/erlang-questions/2011-March/0571... Of course, it is worth keeping in mind that they didn't also go and try to optimize the Python version. So perhaps after doing that Python would win again.

kqueue 16y ago

The spikes you are mentioning might be due to the OS lowering your process priority. If you are on a FreeBSD machine, try running rtprio(1) to avoid the OS changing the process priority upon extensive CPU usage.

klochner 16y ago
The spikes are from hard problem instances - he's not running on the same data set each time. From Norvig's post: But the main message is that the mean and median stay about the same even as we sample more, but the maximum keeps going up--dramatically. The standard deviation edges up too, but mostly because of the very few very long times that are way out beyond the 99th percentile. This is a heavy-tailed distribution, not a normal one.
mjb 16y ago
They are more likely due to properties of the puzzles themselves than operating system behaviour, especially on a modern operating system on a multi-core machine. Plus, in the original Norvig article (http://norvig.com/sudoku.html http://norvig.com/sudoku.html) he talks about several puzzles which take 10s and 100s of seconds to complete, which is extremely unlikely to be due to scheduler behaviour. With languages like Python and Clojure several background processes (like GC pauses) could also contribute to some drops in throughput. Of course, it would be easy to tell these cases apart by counting operations (backtracks, etc) rather than time.

beagle3 16y ago

It is not really comparable, yet, I will post Arthur Whitney's Sudoku solver (in the K language) , in its entirety here: p,:3/:_(p:9\:!81)%3 s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x} ( can be found with a test case in http://nsl.com/k/sudoku/aw3.k http://nsl.com/k/sudoku/aw3.k ) The Norvig code is smarter - it always tries to fill the square with the least options. The Whitney code is dumb - it just recursively tries everything that's not blocked by peers in order. Both backtrack on failure. The codes are equally general - both work off a data driven peer list (peers, p). The K code runs much faster for most boards, but there are boards in which the Norvig heuristic makes a x100 difference. Personally, I prefer the K version, although I'm aware I am in the minority.

wewyor 16y ago
You are probably only in the minority because K, J, APL and what have you look like perl turned up to 11 for those of us who are unfamiliar with the syntax. Though if you consider that these are all vector programming languages, they are really made for this kind of thing.
deathflute 16y ago
Arthur's languages are awesome, no doubt about it. But the fact remains that they are proprietary and prohibitively so. As much as you romanticize k/q, I bet you can't even afford to run it on your home computer, let alone do any real work on it.
- beagle3 16y ago
  J, which is close enough, was always free-to-use and recently open sourced https://github.com/openj/core https://github.com/openj/core K4/Q 32-bit is free for noncommercial use http://kx.com/trialsoftware.php http://kx.com/trialsoftware.php and has been from the day it became generally available. (And before that, k2/k3/ksql were similarly available) A free / open source K3 interpreter is being developed in https://github.com/kevinlawler/kona https://github.com/kevinlawler/kona , and while incomplete it is already quite capable. Oh, and Kx are (or at least were) quite reasonable with commercial use licenses for businesses that can't yet afford them. > Arthur's languages are awesome, no doubt about it. That is the only true thing you wrote.