5 ms·

Donald Knuth’s 2023 Christmas Lecture: Making the Cells Dance

264 points by howrude 3y ago

dang 3y ago
Related: Donald Knuth's Annual Christmas Lecture 2023 - https://news.ycombinator.com/item?id=38548712 https://news.ycombinator.com/item?id=38548712 - Dec 2023 (5 comments) 30 years of Donald Knuth's 'Christmas Lectures' are online – including 2023's - https://news.ycombinator.com/item?id=38775882 https://news.ycombinator.com/item?id=38775882 - Dec 2023 (10 comments)
caprock 3y ago
Here's the more direct link to the Stanford page: https://online.stanford.edu/donald-e-knuth-lectures https://online.stanford.edu/donald-e-knuth-lectures
jsenn 3y ago
Though not for the same purpose, some of the tricks described remind me of the “compact slot map” described here: https://gamedev.stackexchange.com/a/33905 https://gamedev.stackexchange.com/a/33905, including the “swap and pop” for deleting from the middle of the array.
dragontamer 3y ago
Dancing Links is very marvelous form of optimization. Thanks to a intent to optimize this problem relating to combinatorial-exploration, Knuth's "Dancing Links" operates upon a hyper-focused system where "malloc" and "free" of these linked lists are incredibly optimized. In fact, "malloc" is like 2 or 3 assembly instructions (akin to bump-allocation), while "free" is IIRC a no-op. This is because every linked-node can only point to the immediate cell to the right, or a cell later down the line. (So a malloc is basically &curNode+1). ------------- Its incredible that Knuth continues to work on this problem. I do think that these combinatorial problems he's gotten "stuck" on, here on Volume4, really constitute the most elegant of the entirety of the Comp. Sci field. I would like to see more chapters of Volume4 to come out though! ---------- I'll have to look at this "dancing cells" lecture of his, any improvements in this concept will definitely intrigue me.
mindesc 3y ago
Dancing links has been so far my favourite algorithm to learn
revskill 3y ago
Still wait for vol 5.
- wolfi1 3y ago
  and vol 6 and vol 7, but vol 4 has still to be completed
radicality 3y ago
It’s been many years, but I remember really enjoying implementing dancing links for sudoku solving when I was practicing for job interviews. I wrote about it on my blog, there is some very old (probably crappy) Java code for it too. https://rafal.io/posts/solving-sudoku-with-dancing-links.html https://rafal.io/posts/solving-sudoku-with-dancing-links.htm... https://github.com/rafalio/dancing-links-java/tree/master https://github.com/rafalio/dancing-links-java/tree/master
velo_aprx 3y ago
Why is he wearing, what to me looks like, traditional Sami clothing?
- criddell 3y ago
  Probably because he likes it.
- jhncls 3y ago
  Donald Knuth seems to be quite fond of Scandinavia. He did a sabbatical in Norway, where he also wrote a children's book: "Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness." Knuth's ancestors moved during the 19th century from Germany to the US. His father's family lived close to the Danish border [1]. [0]: https://www.youtube.com/watch?v=jB0aeePskBg&list=PLVV0r6CmEsFzeNLngr1JqyQki3wdoGrCn&index=41 https://www.youtube.com/watch?v=jB0aeePskBg&list=PLVV0r6CmEs... [1]: https://www.youtube.com/watch?v=VnoFvUnL6xU&list=PLVV0r6CmEsFzeNLngr1JqyQki3wdoGrCn&index=4&pp=iAQB https://www.youtube.com/watch?v=VnoFvUnL6xU&list=PLVV0r6CmEs...
- throw-7462637 3y ago
  This is a genuine question based on my desire to get a better understanding of our current progressive culture. I am not passing judgement and I hope you can answer honestly. Did you ask this question with the term 'cultural appropriation' in mind? Does this sweater make you uncomfortable and if so why?
  - velo_aprx 3y ago
    My question was also genuine. I was curious. Its not a common thing to wear.
    - deleted 3y ago
      [deleted]
- wingspar 3y ago
  I took it as a Christmas sweater…
JacobiX 3y ago
This is a very nice observation that I've found in the dancing links paper : My trusty old SPARCstation 2 computer, vintage 1992, is able to perform approxi- mately 0.39 mega-updates per second when working on large problems and maintaining the S fields. The 120 MHz Pentium I computer that Stanford computer science faculty were given in 1996 did 1.21 mega-updates per second, and my new 500 MHz Pentium III does 5.94. Thus the running time decreases as technology advances; but it remains essentially proportional to the number of updates, which is the number of times the links do their dance. Therefore I prefer to measure the performance of algorithm DLX by counting the number of updates, not by counting the number of elapsed seconds.
cb321 3y ago
The Briggs & Torczon paper focuses on set representation rather than key-value style access, but of course one can get associative access with just a 2nd dense array of satellite data or, equivalently, wider-than integers in the one dense array (depending upon memory layout desires). Then you basically have a direct access index (like only 256 possible things, so use an 8-bit byte-sized index array of 256 entries) paired with a dense table. This always struck me as very similar to early ideas in database indexing a la Ted Codd & crew (as perhaps more recently popularized in recent Python3.6 hash table impls). So, while Aho & Briggs & Torczon all deserve ongoing credit for popularization, I wonder if anyone out in HN-land knows of a reference to a database paper from the 60s or 70s introducing this? (For more complete attribution.)
tylerneylon 3y ago
This lecture covers Knuth's latest (and simplest-so-far) algorithm to solve the XCC problem; I'll describe XCC below. The XCC problem is designed to solve problems that are NP-hard. So algorithms that solve XCC are not known to be polynomial-time. But they're interesting because they can solve a whole swath of problems that are difficult (not known to have a poly-time algorithm) and interesting. This is in the same world as SAT-solvers, in case you already know about those. This particular Knuth lecture shows how you can simplify his original "dancing links" algorithm to a "dancing cells" version that no longer uses as complex a linked list structure internally, but rather uses flat arrays, although it does retain some link-like structure. The dancing cells alg isn't always better than dancing links, but for most of Knuth's test cases, this new version is faster. Ok, what is XCC? It's the "exact covering with colors" problem. (Knuth mentioned that XCC doesn't yet have a wikipedia page, and maybe it should!) It's an extension of the "exact cover" problem -- you're given a set of items that should be covered, and a set of options (sets of items) that may cover some items. Each item must be covered exactly once (no more, no less). Now I'll add the "with colors" part: You can divide items into primary (these need to be covered exactly once) and secondary: these items may be either uncovered, or have possibly-many covering options, but the "color" of the coverings must be the same. Here's a problem to help gain some intuition for XCC: Imagine trying to build an mxn word grid with valid English words. Each option can be either a word in a row or a word in a column. In this case your primary items could be something like "each row needs a word and each column needs a word." Then your secondary items would be the individual cells and each letter is a "color;" thus the use of consistent colors is a way to ensure that you can't assign different letters to the same cell. Another description of XCC: https://docs.rs/xcc/latest/xcc/ https://docs.rs/xcc/latest/xcc/ Word squares: https://en.wikipedia.org/wiki/Word_square https://en.wikipedia.org/wiki/Word_square
- cb321 3y ago
  It's not called "XCC" (or perhaps just "XC") as he mentioned in his talk, but there is this: https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Exact_cover which has a link to a Knuth algo (EDIT: and a section on what they call "generalized exact cover").
  - 3y ago
sydbarrett74 3y ago
Donald Knuth is an absolute treasure, and a true Renaissance Man. I adore this guy.

264 points by howrude 3y ago

dang 3y ago

Related: Donald Knuth's Annual Christmas Lecture 2023 - https://news.ycombinator.com/item?id=38548712 https://news.ycombinator.com/item?id=38548712 - Dec 2023 (5 comments) 30 years of Donald Knuth's 'Christmas Lectures' are online – including 2023's - https://news.ycombinator.com/item?id=38775882 https://news.ycombinator.com/item?id=38775882 - Dec 2023 (10 comments)

caprock 3y ago

Here's the more direct link to the Stanford page: https://online.stanford.edu/donald-e-knuth-lectures https://online.stanford.edu/donald-e-knuth-lectures

jsenn 3y ago

Though not for the same purpose, some of the tricks described remind me of the “compact slot map” described here: https://gamedev.stackexchange.com/a/33905 https://gamedev.stackexchange.com/a/33905, including the “swap and pop” for deleting from the middle of the array.

dragontamer 3y ago

Dancing Links is very marvelous form of optimization. Thanks to a intent to optimize this problem relating to combinatorial-exploration, Knuth's "Dancing Links" operates upon a hyper-focused system where "malloc" and "free" of these linked lists are incredibly optimized. In fact, "malloc" is like 2 or 3 assembly instructions (akin to bump-allocation), while "free" is IIRC a no-op. This is because every linked-node can only point to the immediate cell to the right, or a cell later down the line. (So a malloc is basically &curNode+1). ------------- Its incredible that Knuth continues to work on this problem. I do think that these combinatorial problems he's gotten "stuck" on, here on Volume4, really constitute the most elegant of the entirety of the Comp. Sci field. I would like to see more chapters of Volume4 to come out though! ---------- I'll have to look at this "dancing cells" lecture of his, any improvements in this concept will definitely intrigue me.

mindesc 3y ago

Dancing links has been so far my favourite algorithm to learn

revskill 3y ago

Still wait for vol 5.

wolfi1 3y ago
and vol 6 and vol 7, but vol 4 has still to be completed

radicality 3y ago

It’s been many years, but I remember really enjoying implementing dancing links for sudoku solving when I was practicing for job interviews. I wrote about it on my blog, there is some very old (probably crappy) Java code for it too. https://rafal.io/posts/solving-sudoku-with-dancing-links.html https://rafal.io/posts/solving-sudoku-with-dancing-links.htm... https://github.com/rafalio/dancing-links-java/tree/master https://github.com/rafalio/dancing-links-java/tree/master

velo_aprx 3y ago

Why is he wearing, what to me looks like, traditional Sami clothing?

criddell 3y ago
Probably because he likes it.
jhncls 3y ago
Donald Knuth seems to be quite fond of Scandinavia. He did a sabbatical in Norway, where he also wrote a children's book: "Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness." Knuth's ancestors moved during the 19th century from Germany to the US. His father's family lived close to the Danish border [1]. [0]: https://www.youtube.com/watch?v=jB0aeePskBg&list=PLVV0r6CmEsFzeNLngr1JqyQki3wdoGrCn&index=41 https://www.youtube.com/watch?v=jB0aeePskBg&list=PLVV0r6CmEs... [1]: https://www.youtube.com/watch?v=VnoFvUnL6xU&list=PLVV0r6CmEsFzeNLngr1JqyQki3wdoGrCn&index=4&pp=iAQB https://www.youtube.com/watch?v=VnoFvUnL6xU&list=PLVV0r6CmEs...
throw-7462637 3y ago
This is a genuine question based on my desire to get a better understanding of our current progressive culture. I am not passing judgement and I hope you can answer honestly. Did you ask this question with the term 'cultural appropriation' in mind? Does this sweater make you uncomfortable and if so why?
- velo_aprx 3y ago
  My question was also genuine. I was curious. Its not a common thing to wear.
  - deleted 3y ago
    [deleted]
wingspar 3y ago
I took it as a Christmas sweater…

JacobiX 3y ago

This is a very nice observation that I've found in the dancing links paper : My trusty old SPARCstation 2 computer, vintage 1992, is able to perform approxi- mately 0.39 mega-updates per second when working on large problems and maintaining the S fields. The 120 MHz Pentium I computer that Stanford computer science faculty were given in 1996 did 1.21 mega-updates per second, and my new 500 MHz Pentium III does 5.94. Thus the running time decreases as technology advances; but it remains essentially proportional to the number of updates, which is the number of times the links do their dance. Therefore I prefer to measure the performance of algorithm DLX by counting the number of updates, not by counting the number of elapsed seconds.

cb321 3y ago

The Briggs & Torczon paper focuses on set representation rather than key-value style access, but of course one can get associative access with just a 2nd dense array of satellite data or, equivalently, wider-than integers in the one dense array (depending upon memory layout desires). Then you basically have a direct access index (like only 256 possible things, so use an 8-bit byte-sized index array of 256 entries) paired with a dense table. This always struck me as very similar to early ideas in database indexing a la Ted Codd & crew (as perhaps more recently popularized in recent Python3.6 hash table impls). So, while Aho & Briggs & Torczon all deserve ongoing credit for popularization, I wonder if anyone out in HN-land knows of a reference to a database paper from the 60s or 70s introducing this? (For more complete attribution.)

tylerneylon 3y ago

This lecture covers Knuth's latest (and simplest-so-far) algorithm to solve the XCC problem; I'll describe XCC below. The XCC problem is designed to solve problems that are NP-hard. So algorithms that solve XCC are not known to be polynomial-time. But they're interesting because they can solve a whole swath of problems that are difficult (not known to have a poly-time algorithm) and interesting. This is in the same world as SAT-solvers, in case you already know about those. This particular Knuth lecture shows how you can simplify his original "dancing links" algorithm to a "dancing cells" version that no longer uses as complex a linked list structure internally, but rather uses flat arrays, although it does retain some link-like structure. The dancing cells alg isn't always better than dancing links, but for most of Knuth's test cases, this new version is faster. Ok, what is XCC? It's the "exact covering with colors" problem. (Knuth mentioned that XCC doesn't yet have a wikipedia page, and maybe it should!) It's an extension of the "exact cover" problem -- you're given a set of items that should be covered, and a set of options (sets of items) that may cover some items. Each item must be covered exactly once (no more, no less). Now I'll add the "with colors" part: You can divide items into primary (these need to be covered exactly once) and secondary: these items may be either uncovered, or have possibly-many covering options, but the "color" of the coverings must be the same. Here's a problem to help gain some intuition for XCC: Imagine trying to build an mxn word grid with valid English words. Each option can be either a word in a row or a word in a column. In this case your primary items could be something like "each row needs a word and each column needs a word." Then your secondary items would be the individual cells and each letter is a "color;" thus the use of consistent colors is a way to ensure that you can't assign different letters to the same cell. Another description of XCC: https://docs.rs/xcc/latest/xcc/ https://docs.rs/xcc/latest/xcc/ Word squares: https://en.wikipedia.org/wiki/Word_square https://en.wikipedia.org/wiki/Word_square

cb321 3y ago
It's not called "XCC" (or perhaps just "XC") as he mentioned in his talk, but there is this: https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Exact_cover which has a link to a Knuth algo (EDIT: and a section on what they call "generalized exact cover").
- 3y ago

sydbarrett74 3y ago

Donald Knuth is an absolute treasure, and a true Renaissance Man. I adore this guy.