Ticket #2271 (closed enhancement: fixed)

Opened 5 years ago

Last modified 5 years ago

[with patch; massively positive review] Include Antti Ajanki's DLX library

Reported by: boothby Owned by: mhansen
Priority: major Milestone: sage-2.10.3
Component: combinatorics Keywords:
Cc: Work issues:
Report Upstream: Reviewers:
Authors: Merged in:
Dependencies: Stopgaps:

Description (last modified by boothby) (diff)

The Dancing Links algorithm (DLX) is sweet. It solves the Exact Cover problem with the quickness.

Arguments for including Ajanki's code:

  • It's the only Python implementation of DLX I've seen.
  • I emailed the author, who happily added the "or later" bit after the GPL2
  • With my Sage Matrix -> DLXMatrix code (plus docstrings to everything I added), the file dlx.py is only 8kB!
  • It will resolve tickets #1311 and #1313

Attachments

2271_adds_DLX.hg Download (3.0 KB) - added by boothby 5 years ago.
2271_adds_DLX.patch Download (9.3 KB) - added by boothby 5 years ago.
2271_doctests.patch Download (17.4 KB) - added by boothby 5 years ago.

Change History

comment:1 Changed 5 years ago by boothby

  • Type changed from defect to enhancement

Changed 5 years ago by boothby

comment:2 Changed 5 years ago by was

  • Summary changed from Include Antti Ajanki's DLX library to [with patch; needs review] Include Antti Ajanki's DLX library

+1 to include this in Sage.

I haven't formally refereed it.

You should just attach a single plain text patch instead of an hg bundle.

comment:3 Changed 5 years ago by mabshoff

  • Milestone set to sage-2.10.3

comment:4 Changed 5 years ago by boothby

Oops, I forgot to add the functions to all.py, so the tests fail. New patch up in a few.

Changed 5 years ago by boothby

comment:5 Changed 5 years ago by rlm

  • Summary changed from [with patch; needs review] Include Antti Ajanki's DLX library to [with patch; positive review pending documentation] Include Antti Ajanki's DLX library

This patch (although awesome) doesn't quite obey the new doctest-for-every-function rule, since the following functions do not have doctests:

  1. walknodes
  2. constructmatrix
  3. covercolumn
  4. uncovercolumn
  5. dosearch
  6. solve

comment:6 Changed 5 years ago by boothby

  • Description modified (diff)

Changed 5 years ago by boothby

comment:7 follow-up: ↓ 9 Changed 5 years ago by boothby

2271_doctests.patch implements world peace, washes your dishes, and makes coffee before your alarm goes off in the morning. It's truly amazing. Also, it contains doctests for everything in sight, reworks the DLXMatrix class to be a real python generator class, and implements an iterative formulation of DLX.

In the creation of these doctests, I have discovered a wondrous resolution of P vs. NP, but the proof was too long to justify appending to the patch.

comment:8 Changed 5 years ago by rlm

  • Summary changed from [with patch; positive review pending documentation] Include Antti Ajanki's DLX library to [with patch; massively positive review] Include Antti Ajanki's DLX library

As well as a round of applause.

comment:9 in reply to: ↑ 7 Changed 5 years ago by mabshoff

Replying to boothby:

2271_doctests.patch implements world peace, washes your dishes, and makes coffee before your alarm goes off in the morning. It's truly amazing. Also, it contains doctests for everything in sight, reworks the DLXMatrix class to be a real python generator class, and implements an iterative formulation of DLX.

In the creation of these doctests, I have discovered a wondrous resolution of P vs. NP, but the proof was too long to justify appending to the patch.

I guess you should have written it in the margins :)

Cheers,

Michael

comment:10 Changed 5 years ago by mabshoff

  • Status changed from new to closed
  • Resolution set to fixed

Merged 2271_adds_DLX.patch and 2271_doctests.patch in Sage 2.10.3.alpha0 - w00t

Note: See TracTickets for help on using tickets.