Weakest calculator/pocket computer that can do Tower of Hanoi?
|
08-11-2018, 05:26 PM
Post: #1
|
|||
|
|||
Weakest calculator/pocket computer that can do Tower of Hanoi?
What's the weakest (least RAM, sparsest programming capabilities) handheld that can do Tower of Hanoi solutions? I know it's been done on the 42S, but that has a spacious 8 KB RAM. I've pulled it off on my Casio fx-7000g, which gives you a little over 400 bytes for your program, and 26 variables/registers. It'll handle up to 8 discs (which takes quite a long time to run). Has anybody managed to do it on a 32S?
|
|||
08-11-2018, 06:42 PM
Post: #2
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-11-2018 05:26 PM)Dave Britten Wrote: What's the weakest (least RAM, sparsest programming capabilities) handheld that can do Tower of Hanoi solutions? I know it's been done on the 42S, but that has a spacious 8 KB RAM. I've pulled it off on my Casio fx-7000g, which gives you a little over 400 bytes for your program, and 26 variables/registers. It'll handle up to 8 discs (which takes quite a long time to run). Has anybody managed to do it on a 32S? If you implement the iterative solution, you can do it on almost anything. I did it on the 19C, but that was ages ago, and that program is lost in the mists of time and I don't remember any of the implementation details. I'll take a shot at doing it on the HP-25 tonight... |
|||
08-11-2018, 06:52 PM
Post: #3
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
Now that would be impressive to see it running on a 25. I'm assuming you'd have to simply display the moves in "from.to" format or similar.
I used the iterative method for the 1st-gen Casio program, and it just barely fits in memory (and uses nearly all the variables, even with packing the stacks into a single variable each). But it also shows the discs graphically. There's no doubt plenty of opportunities to shrink and optimize it. |
|||
08-11-2018, 08:35 PM
Post: #4
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
Doing it on the 25 does seem a bit ambitious. When I started writing the code, it turned out quite a bit longer than I thought. Devil in the details... It does fit in the 19C/29C, though:
Code: 01▸LBL 0 |
|||
08-12-2018, 01:46 AM
(This post was last modified: 08-12-2018 02:14 AM by Thomas Okken.)
Post: #5
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
A bit smarter algorithm, taking advantage of the fact that if you're not displaying the towers anyway, and only showing the sequence of moves, you don't have to keep track of where the discs are:
Code: 01▸LBL 0 Better, but still too long for the HP-25. Not having MOD really hurts. |
|||
08-12-2018, 01:52 AM
Post: #6
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 01:46 AM)Thomas Okken Wrote: A bit smarter algorithm, taking advantage of the fact that if you're not displaying the towers anyway, and only showing the sequence of moves, you don't have to keep track of where the discs are: I kind of suspected it might be possible to squeeze an optimization like that out of the problem. Hadn't experimented with the idea myself, though. (08-12-2018 01:46 AM)Thomas Okken Wrote: Not having MOD really hurts. Yeah, that was definitely getting in my way doing the Casio version, particularly the section that chooses the next pair of pegs to operate on. I think doing stunts with Int and Frac would outweigh the savings of a few otherwise viable optimizations. |
|||
08-12-2018, 07:16 AM
(This post was last modified: 08-12-2018 01:19 PM by Thomas Klemm.)
Post: #7
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
This program for the HP-11C implements A001511:
Code: 01▸LBL A Quote:a(n) = number of disk to be moved at n-th step of optimal solution to Towers of Hanoi problem It uses the following method to calculate \(a(n)\): Quote:a(n) is the number of digits that must be counted from right to left to reach the first 1 in the binary representation of n. Example with 3 disks Hint: Move odd disks to the right and even disks to the left. 1 [A] → 1 ; move disk 1 to the right 2 [A] → 2 ; move disk 2 to the left 3 [A] → 1 ; move disk 1 to the right 4 [A] → 3 ; move disk 3 to the right 5 [A] → 1 ; (…) 6 [A] → 2 7 [A] → 1 (08-11-2018 08:35 PM)Thomas Okken Wrote: Doing it on the 25 does seem a bit ambitious. It should be possible to convert this program for the HP-25. Cheers Thomas Edit: Fixed typo in line 08 of the program. |
|||
08-12-2018, 07:46 AM
Post: #8
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 07:16 AM)Thomas Klemm Wrote: This program for the HP-11C implements A001511: That program always returns 1, for any input. Even if it did do what you say it should do, it would still be only a partial solution, because all it would tell you is which disc should be moved at any given step. The reason why my (second) program is so much longer is because it works out from from which to which position the disc is moved. |
|||
08-12-2018, 08:10 AM
Post: #9
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-11-2018 05:26 PM)Dave Britten Wrote: What's the weakest (least RAM, sparsest programming capabilities) handheld that can do Tower of Hanoi solutions? On the HP-35 you could do the following to calculate \(a(n)\) from A001511: 1. Fill the stack with \(\frac{1}{2}\): .5 ENTER ENTER ENTER 2. Enter the number \(n\): CLx \(n\) 3. Count how often you have to hit the [×] key until the number ends with .5. [×] [×] … 4. Continue at step 2 with the next number. Kind regards Thomas |
|||
08-12-2018, 09:35 AM
(This post was last modified: 08-12-2018 09:48 AM by Thomas Klemm.)
Post: #10
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 07:46 AM)Thomas Okken Wrote: That program always returns 1, for any input. That's weird. Are you sure that you've entered these lines? Code: 13 1 Quote:Even if it did do what you say it should do, it would still be only a partial solution, because all it would tell you is which disc should be moved at any given step. The reason why my (second) program is so much longer is because it works out from from which to which position the disc is moved. It depends on how a solution is specified. You could give the sequence A001511 to someone and without understanding the rules it would be possible to play the game. You'd have to know how to move odd and even disk numbers differently but you could colour the disks accordingly which would give them a nice touch. If you desperately need to know the positions they could be calculated from \(n\) and \(a(n)\): Here's a Python program: Code: def hanoi(n): And this is the generated output: Code: (disk, from, to) Is that what you want? Not sure if we can squeeze that into the 49 lines of a HP-25 though. (08-12-2018 01:46 AM)Thomas Okken Wrote: Not having MOD really hurts. Agreed. Cheers Thomas |
|||
08-12-2018, 01:16 PM
(This post was last modified: 08-12-2018 01:20 PM by Thomas Klemm.)
Post: #11
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi? | |||
08-12-2018, 01:19 PM
(This post was last modified: 08-12-2018 01:34 PM by Thomas Okken.)
Post: #12
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 09:35 AM)Thomas Klemm Wrote:(08-12-2018 07:46 AM)Thomas Okken Wrote: That program always returns 1, for any input. I am. Are you sure you have even tested this program? Those two lines are never reached. Here's what happens: Code: 01▸LBL A X:n UPDATE: Ah, we posted at the same time -- never mind. However, (08-12-2018 09:35 AM)Thomas Klemm Wrote: If you desperately need to know the positions they could be calculated from n and a(n) I wouldn't call myself particularly desperate, but merely specifying which disc is moved at each step, without saying from where to where, looks like only half a solution to me. If you had read my second program more carefully, you would have noticed that it performs the same calculation that yours does, and then it works out the exact move. All your program accomplishes is to amputate two thirds of the logic. What's left certainly fits in an HP-25, but I wouldn't call that sequence a solution to the Towers of Hanoi puzzle, but merely an interesting property of such a solution. |
|||
08-12-2018, 01:32 PM
Post: #13
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 01:19 PM)Thomas Okken Wrote: Are you sure you have even tested this program? Unfortunately I can't run the Nonpareil emulator at the moment. So no, the program as it was typed wasn't tested. However it was tested on the real hardware. But from there I can't transfer programs to a computer. Based on the behaviour you described I imagined what could have gone wrong. Missing a key happens to me all the time so I thought I give it a try. Kind regards Thomas |
|||
08-12-2018, 05:08 PM
Post: #14
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 07:16 AM)Thomas Klemm Wrote: It should be possible to convert this program for the HP-25. Here's what I came up with: Code: 01 ENTER I've used this online HP-25 emulator to test it. I hope I didn't make typos again. Cheers Thomas PS: I wasn't aware that the ENTER in the first line is needed. Otherwise 1 will just be appended to the number in the display. Does anybody know with which model this behaviour changed? |
|||
08-12-2018, 06:07 PM
Post: #15
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 05:08 PM)Thomas Klemm Wrote: PS: I wasn't aware that the ENTER in the first line is needed. As far as I'm aware, that behavior is a bug in the HP-25 (and 25C), not found in other HP models. See http://www.hpmuseum.org/forum/thread-9566.html |
|||
08-13-2018, 12:45 AM
Post: #16
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
I found [attachment=6204]a most useful reference.
example: Chapter 2; the Classical Tower of Hanoi, pgs 94-05 Quote:As in the case of the CR it is clear that in an optimal solution disc 1 has to BEST! SlideRule |
|||
08-13-2018, 01:38 AM
Post: #17
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-12-2018 05:08 PM)Thomas Klemm Wrote: PS: I wasn't aware that the ENTER in the first line is needed. Specify that the program is run after ENTER has been pressed. To expand this to a complete solution the oddness of the input is required, so a STO as the first step avoids the issue. I wonder if the sign of the output could indicate the direction of the move rather than calculating the final position? Anyway, here is a 49 step programme for the HP 25 that gives the solution to an n level Tower of Hanoi problem: Code: 01 STO 4 To run:
The program will display a sequence of two digits numbers that represent the poles moved between, pick the legal move in each case. For a three high tower these are: Code: Display Meaning Pauli |
|||
08-13-2018, 03:40 AM
Post: #18
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-13-2018 01:38 AM)Paul Dale Wrote: Anyway, here is a 49 step programme for the HP 25 that gives the solution to an n level Tower of Hanoi problem: Lame. Why don't you just admit you don't know how to do this on the HP-25? Just like Thomas K., who also seems to think he's coded a solution even though he didn't, and like me, who coded a solution that is complete but is too long to fit. |
|||
08-13-2018, 07:03 AM
Post: #19
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-13-2018 03:40 AM)Thomas Okken Wrote: Lame. Why don't you just admit you don't know how to do this on the HP-25? Just like Thomas K., who also seems to think he's coded a solution even though he didn't, and like me, who coded a solution that is complete but is too long to fit. I'm happy to admit that I've not come up with a complete solution for the HP-25 but this is a solution for somebody manually moving discs around. Okay, the single PSE is too fast and R/S would be needed instead but that's trivial. Regardless, I'm not yet ready to admit that a complete solution is totally impossible (I'm close but not quite yet). Pauli |
|||
08-13-2018, 11:47 AM
(This post was last modified: 09-10-2018 04:08 PM by Thomas Klemm.)
Post: #20
|
|||
|
|||
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(08-13-2018 07:03 AM)Paul Dale Wrote: Regardless, I'm not yet ready to admit that a complete solution is totally impossible (I'm close but not quite yet). Here's a program for the HP-25: Code: 01 STO 0 ; k=n For a move \(n\) it returns: Z: to Y: from X: disk Example: 12 R/S Z: 1 Y: 2 X: 3 Thus move disk 3 from peg 2 to peg 1. It's the translation of the following Python program: Code: def hanoi(n): This is the list for all moves for 5 disks: Code: >>> for n in range(1, 2**5): There are 12 lines left that could be used for a loop or a fancy display or what not. Cheers Thomas Addendum: I've used from Binary solution of Tower of Hanoi: Quote:Another formulation is from peg (m - (m & -m)) % 3 to peg (m + (m & -m)) % 3 And then from A006519: Quote:Highest power of 2 dividing n. But I went the other way round: first I've generated the from and to sequences and looked them up in OEIS. Only when I figured out the formulas I found them in Wikipedia. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 6 Guest(s)