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

#1

Post by howrude » Wed, Dec 27, 2023, 2:21 AM UTC

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

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

#2

Post by dang » Wed, Dec 27, 2023, 2:22 AM UTC

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

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

#3

Post by caprock » Wed, Dec 27, 2023, 2:27 AM UTC

Here's the more direct link to the Stanford page:

https://online.stanford.edu/donald-e-knuth-lectures

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

#4

Post by jsenn » Wed, Dec 27, 2023, 3:16 AM UTC

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, including the “swap and pop” for deleting from the middle of the array.

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

#5

Post by dragontamer » Wed, Dec 27, 2023, 4:38 AM UTC

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.

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

#6

Post by mindesc » Wed, Dec 27, 2023, 8:17 AM UTC

Dancing links has been so far my favourite algorithm to learn

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

#7

Post by revskill » Wed, Dec 27, 2023, 8:54 AM UTC

Still wait for vol 5.

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

#8

Post by radicality » Wed, Dec 27, 2023, 9:37 AM UTC

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.htm...

https://github.com/rafalio/dancing-links-java/tree/master