Opened 13 years ago
Closed 13 years ago
#7770 closed enhancement (fixed)
Implement Tower of Hanoi graph
| Reported by: | Rob Beezer | Owned by: | Robert Miller |
|---|---|---|---|
| Priority: | minor | Milestone: | sage-4.3.1 |
| Component: | graph theory | Keywords: | tower of hanoi graph |
| Cc: | Merged in: | sage-4.3.1.alpha0 | |
| Authors: | Rob Beezer | Reviewers: | David Joyner |
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | Stopgaps: |
Status badges
Description
The Tower of Hanoi puzzle can be described by a graph whose vertices are possible states of the disks on the pegs, with edges represdenting legitimate moves of a single disk.
Attachments (1)
Change History (7)
comment:1 Changed 13 years ago by
| Authors: | → Rob Beezer |
|---|---|
| Status: | new → needs_review |
Changed 13 years ago by
| Attachment: | trac_7770_hanoi_tower_graph.patch added |
|---|
comment:2 follow-up: 3 Changed 13 years ago by
| Status: | needs_review → needs_work |
|---|
This looks like an interesting patch but
sage -t "devel/sage/sage/graphs/graph_generators.py"
seems to fail (sage 4.3, imac, 10.6.2).
comment:3 Changed 13 years ago by
| Status: | needs_work → needs_review |
|---|
Replying to wdj:
This looks like an interesting patch but
sage -t "devel/sage/sage/graphs/graph_generators.py"seems to fail (sage 4.3, imac, 10.6.2).
Arrgghh ...
Ignore this. I'll keep refereeing it.
comment:4 Changed 13 years ago by
| Status: | needs_review → positive_review |
|---|
Positive review.
Installs fine on 64bit ubuntu and imac 10.6.2 running sage 4.3. Passes sage -testall on the ubuntu machine and has (I think only) unrelated failures on the imac. Also I check the html output for the reference manual and it looks good.
Thanks for this patch Rob! I have used it already in some lecture notes I'm working on for next semester.
comment:5 Changed 13 years ago by
| Reviewers: | → David Joyner |
|---|
Hi David,
Thanks for the quick review, and I'm especially glad to hear it is being used *immediately*. ;-)
I'm going to send you some extra info on the graph off-list. (I don't have permission to post it yet).
Rob
comment:6 Changed 13 years ago by
| Merged in: | → sage-4.3.1.alpha0 |
|---|---|
| Resolution: | → fixed |
| Status: | positive_review → closed |
Some rough timing information on a 3 GHZ Core 2 Duo:
4 pegs, 10 disks, no labels, no layout info
2^20 = 1,048,576vertices3,142,656 edges
240 seconds
Distance between vertex 0 and
(4^10)-1, iethe minimum number of moves to solve the puzzle:
742 ms
I could probably provide timing on sage.math for a release tour (along with a nice graphic).