YAPC::Europe 2011 “Modern Perl”

Twitter #ye2011 RSS Log in

Making data dance

By Carl Mäsak (‎masak‎)
Date: Monday, 15 August 2011 12:50
Duration: 20 minutes
Target audience: Any
Language:
Tags: algorithms languages problems solutions 蝶

Donald Knuth's "Dancing Links" algorithm deserves wider recognition. It can solve the N-queens problem. It can help us tile pentominoes. It makes solving a Sudoku problem trivial.

There's only one little issue: these problems are all solved in another domain which we can call the "big huge matrix of ones and zeroes domain". Constructing such a matrix manually is about as fun as boning fish.

Solution: I wrote a set of parsers that can understand a given problem type, so that we can always deal with cute ASCII representations of the problems, and never the matrix itself. We become unfettered from the technical specifics of the algorithm, while still reaping all the benefits from it.

The same idea has been implemented in Perl 5/Moose (for prototyping), C (for speed), and Perl 6 (for beauty), and I will say a thing or two about what's nice about implementing a small project like this in each of those languages.

Attended by:

Other conferences

London Perl & Raku Workshop 2024 25 October 2024 — German Perl/Raku Workshop 2025 14 April 2025 — and more.

Feel free to contact us: mail@yapceurope.lv.
YAPC::Europe 2011 in Riga organizing committee.