Re: the TOWERS OF HANOI

[bplus]

Hi TempodiBasic,

Looking at your code:

Code: QB64: [Select]

1. SUB MakeMoves (NumMoves&)

Are you moving disks a tower section at a time? I haven't figured out how to watch your code move by move. (It's so different from what I am working.) Append: never mind I figured it out.

Also from the you tube link I posted above, I made a non-recursive Towers of Hanoi solver that runs slightly slower than the recursive one from Samples. Actually I made two, by optimizing the first nonRecursive, nonRecursive1 looks quite different!

Code: QB64: [Select]

1. _TITLE "Towers of Hanoi 4 non recurs" 'B+ started 2019-03-03
2.  
3. 'OK the samples game had a better ways 1. tracks the top disk in each tower and had a disk move routine
4. 'it also called the first tower 0 in the tower array
5.  
6. '2019-03-02 Towers of Hanoi 2 modified with move count and no updates in Auto Mode until finished.
7. '2019-03-02  Towers of Hanoi 3 add working non-recursive method that is slower than recursive.
8.  
9. '2019-03-03 Towers of Hanoi 4 non recurs, Attempt to improve nonRecursive speed in nonRecursive1.
10. ' Yes it works and is faster than
11. 'the other non-recursive BUT still not as fast as AUTO which isn't as fast as Tempodi's recursive.
12.  
13. CONST xmax = 800
14. CONST ymax = 600
15. SCREEN _NEWIMAGE(xmax, ymax, 32)
16. _SCREENMOVE 300, 20
17. DIM SHARED nDisks AS INTEGER, hDisk AS INTEGER, wMult AS INTEGER
18.  
19. nDisks = 10 '<<<<<<<<<<<<   modify as needed max tested 25 worked
20.  
21. 'top tracks the amount of disks in each tower, dpal assigns a color to each disk, tower stores the 3 sets of disk values
22. DIM SHARED nT(2) '<<<  so much smarter than my first attempt that used 2 functions on tower array
23. DIM SHARED dpal(1 TO nDisks) AS _UNSIGNED LONG
24. DIM SHARED tower(0 TO 2, 1 TO nDisks) AS INTEGER
25. DIM SHARED nMoves AS _INTEGER64
26.  
27. 'init
28. hDisk = 520 / nDisks 'for drawing disk heights
29. wMult = 240 / nDisks 'multiplier for disk widths
30. FOR i = 1 TO nDisks
31.     dpal(i) = _RGB32(RND * 255, RND * 255, RND * 255)
32. NEXT
33. FOR i = 1 TO nDisks
34.     tower(0, i) = nDisks + 1 - i
35. NEXT
36. nT(0) = nDisks
37. updateScreen
38. INPUT "Enter p to Play Game or Enter, n to solve non recursively, s to solve recursively: "; choice$
39. IF choice$ = "p" THEN
40.     playGame
41. ELSEIF choice$ = "n" THEN
42.     nonRecursive1
43. ELSE
44.     AUTO
45. END IF
46.  
47. SUB playGame
48.     WHILE _KEYDOWN(27) = 0
49.         'message click or press for fromt
50.         fromT = 0: toT = 0
51.         rowMessage 1, "Click or press tower # of disk to move... "
52.         rowMessage 2, " "
53.         fromT = getTower%
54.         rowMessage 1, "Moving disk from tower" + STR$(fromT + 1)
55.         IF nT(fromT) THEN
56.             rowMessage 2, "Click or press tower # to move disk to..."
57.             toT = getTower
58.             rowMessage 2, "Moving disk to tower" + STR$(toT + 1)
59.             IF toT <> fromT THEN
60.                 IF nT(toT) = 0 THEN
61.                     moveDisk fromT, toT
62.                     updateScreen
63.                 ELSEIF tower(fromT, nT(fromT)) < tower(toT, nT(toT)) THEN
64.                     moveDisk fromT, toT
65.                     updateScreen
66.                 ELSE
67.                     rowMessage 3, "Can't place a larger disk on top a smaller one."
68.                 END IF
69.             ELSE
70.                 rowMessage 3, "You attempted to move a disk to the same tower."
71.             END IF
72.         ELSE
73.             rowMessage 3, "There is no disk to move in tower" + STR$(fromT + 1)
74.         END IF
75.         fromT = 0: toT = 0
76.         _LIMIT 30
77.     WEND
78. END SUB
79.  
80. SUB getClick (mx, my, q)
81.     WHILE _MOUSEINPUT: WEND '<<<<<<<<<<  clear previous mouse activity   ITS NOT CLEARING!!!!!!!!!!!!!!
82.     _KEYCLEAR 'clear previous key presses
83.     mx = -1: my = -1: q = 0
84.     DO WHILE mx = -1 AND my = -1
85.         q = _KEYHIT
86.         IF q = 27 OR (q > 31 AND q < 126) THEN _KEYCLEAR: EXIT SUB
87.         i = _MOUSEINPUT: mb = _MOUSEBUTTON(1)
88.         DO WHILE mb 'wait for release
89.             q = _KEYHIT
90.             IF q = 27 OR (q > 31 AND q < 126) THEN EXIT SUB
91.             i = _MOUSEINPUT: mb = _MOUSEBUTTON(1): mx = _MOUSEX: my = _MOUSEY
92.             _LIMIT 1000
93.         LOOP
94.         _LIMIT 1000
95.     LOOP
96. END SUB
97.  
98. SUB updateScreen
99.     CLS
100.     LINE (0, 580)-STEP(xmax, 0)
101.     FOR t = 0 TO 2
102.         FOR i = 1 TO nDisks
103.             IF tower(t, i) THEN
104.                 xhalf = ((tower(t, i)) * wMult) / 2
105.                 LINE ((t + 1) * 250 - xhalf - 125, 580 - hDisk * i)-STEP(2 * xhalf, hDisk), dpal(tower(t, i)), BF
106.             END IF
107.         NEXT
108.     NEXT
109.     _PRINTSTRING (0, ymax - 18), SPACE$(11) + "Tower #1" + SPACE$(24) + "Tower #2" + SPACE$(23) + "Tower #3"
110.     _PRINTSTRING (300, 60), STR$(nMoves) + " Moves"
111.     'INPUT "OK press enter.."; wate$
112.     _DISPLAY
113. END SUB
114.  
115. FUNCTION getTower% ()
116.     getClick mx, my, q
117.     IF ABS(150 - mx) < 125 THEN t = 0
118.     IF ABS(400 - mx) < 125 THEN t = 1
119.     IF ABS(650 - mx) < 125 THEN t = 2
120.     IF q THEN
121.         IF INSTR("123", CHR$(q)) > 0 THEN t = INSTR("123", CHR$(q)) - 1
122.         IF CHR$(q) = "q" OR q = 27 THEN END
123.     END IF
124.     getTower% = t
125. END FUNCTION
126.  
127. 'clear row with spaces then print message$ on it
128. SUB rowMessage (lineNumber, message$)
129.     LOCATE lineNumber, 1: PRINT SPACE$(xmax \ 8)
130.     LOCATE lineNumber, 1: PRINT message$
131.     _DISPLAY
132. END SUB
133.  
134. 'from sample (my attempt was way more complicated)
135. SUB moveDisk (fromT, toT)
136.     tower(toT, nT(toT) + 1) = tower(fromT, nT(fromT))
137.     nT(toT) = nT(toT) + 1
138.     tower(fromT, nT(fromT)) = 0
139.     nT(fromT) = nT(fromT) - 1
140.     nMoves = nMoves + 1
141.     IF nDisks < 10 THEN updateScreen
142. END SUB
143.  
144. 'from sample
145. SUB AUTO
146.     t# = TIMER(.001)
147.     MOVEPILE nDisks, 0, 2
148.     updateScreen
149.     _PRINTSTRING (20, 20), "Done in" + STR$(TIMER(.001) - t#) + " secs."
150.     _DISPLAY
151.     SLEEP
152. END SUB
153.  
154. 'from sample
155. SUB MOVEPILE (N, START, FINISH)
156.     IF N > 1 THEN CALL MOVEPILE(N - 1, START, 3 - START - FINISH)
157.     moveDisk START, FINISH
158.     IF N > 1 THEN CALL MOVEPILE(N - 1, 3 - START - FINISH, FINISH)
159. END SUB
160.  
161. SUB nonRecursive 'this works but is way slower than recursive method
162.     DIM numMoves AS _INTEGER64, move AS _INTEGER64
163.     DIM d1 AS INTEGER, td0 AS INTEGER, td1 AS INTEGER, td2 AS INTEGER, fromT AS INTEGER, toT AS INTEGER
164.     t# = TIMER(.001)
165.     numMoves = 2 ^ nDisks - 1
166.     d1 = 0
167.  
168.     move = 1
169.     WHILE move <= numMoves
170.         td0 = td(0): td1 = td(1): td2 = td(2)
171.         'PRINT td0, td1, td2
172.         '_KEYCLEAR
173.         'INPUT "OK press enter.. "; wate$
174.         '_DISPLAY
175.  
176.         IF move MOD 2 = 1 THEN
177.             fromT = d1
178.             toT = (d1 + 1) MOD 3
179.             d1 = toT
180.         ELSE
181.             IF td0 = 1 THEN
182.                 IF td1 = 0 THEN
183.                     fromT = 2: toT = 1
184.                 ELSEIF td2 = 0 THEN
185.                     fromT = 1: toT = 2
186.                 ELSEIF td1 < td2 THEN
187.                     fromT = 1: toT = 2
188.                 ELSE
189.                     fromT = 2: toT = 1
190.                 END IF
191.             ELSEIF td1 = 1 THEN
192.                 IF td0 = 0 THEN
193.                     fromT = 2: toT = 0
194.                 ELSEIF td2 = 0 THEN
195.                     fromT = 0: toT = 2
196.                 ELSEIF td0 > td2 THEN
197.                     fromT = 2: toT = 0
198.                 ELSE
199.                     fromT = 0: toT = 2
200.                 END IF
201.             ELSEIF td2 = 1 THEN
202.                 IF td0 = 0 THEN
203.                     fromT = 1: toT = 0
204.                 ELSEIF td1 = 0 THEN
205.                     fromT = 0: toT = 1
206.                 ELSEIF td0 < td1 THEN
207.                     fromT = 0: toT = 1
208.                 ELSE
209.                     fromT = 1: toT = 0
210.                 END IF
211.             END IF
212.         END IF
213.         moveDisk fromT, toT
214.         move = move + 1
215.     WEND
216.  
217.     updateScreen
218.     _PRINTSTRING (20, 20), "Done in" + STR$(TIMER(.001) - t#) + " secs."
219.     _DISPLAY
220.     SLEEP
221.  
222. END SUB
223.  
224. SUB nonRecursive1 'this works but is way slower than recursive method
225.     DIM numMoves AS _INTEGER64, move AS _INTEGER64
226.     DIM d1 AS INTEGER, d2 AS INTEGER, d3 AS INTEGER, dv2 AS INTEGER, dv3 AS INTEGER, fromT AS INTEGER, toT AS INTEGER
227.     t# = TIMER(.001)
228.     numMoves = 2 ^ nDisks - 1
229.     d1 = 0
230.  
231.     move = 1
232.     WHILE move <= numMoves
233.         'td0 = td(0): td1 = td(1): td2 = td(2) 'these can be eliminated with function td()
234.         'PRINT td0, td1, td2
235.         '_KEYCLEAR
236.         'INPUT "OK press enter.. "; wate$
237.         '_DISPLAY
238.  
239.         IF move MOD 2 = 1 THEN 'move disk #1 up 1 and then get the other to tower names and use those to get disk values in tower
240.             fromT = d1
241.             toT = (d1 + 1) MOD 3
242.             d1 = toT
243.         ELSE
244.             d2 = (d1 + 1) MOD 3: d3 = (d2 + 1) MOD 3 'the two towers disk #1 is not
245.             IF nT(d2) = 0 THEN dv2 = 0 ELSE dv2 = tower(d2, nT(d2)) 'the value of the top disk of each tower
246.             IF nT(d3) = 0 THEN dv3 = 0 ELSE dv3 = tower(d3, nT(d3)) 'add dv2, dv3 for next move
247.  
248.             IF dv2 = 0 THEN
249.                 fromT = d3: toT = d2
250.             ELSEIF dv3 = 0 THEN
251.                 fromT = d2: toT = d3
252.             ELSEIF dv2 < dv3 THEN
253.                 fromT = d2: toT = d3
254.             ELSE
255.                 fromT = d3: toT = d2
256.             END IF
257.         END IF
258.         moveDisk fromT, toT
259.         move = move + 1
260.     WEND
261.  
262.     updateScreen
263.     _PRINTSTRING (20, 20), "Done in" + STR$(TIMER(.001) - t#) + " secs."
264.     _DISPLAY
265.     SLEEP
266.  
267. END SUB
268.  
269. FUNCTION td (t)
270.     FOR i = nDisks TO 1 STEP -1
271.         IF tower(t, i) THEN td = tower(t, i): EXIT FUNCTION
272.     NEXT
273. END FUNCTION
274.  

[TempodiBasic]

Hi Bplus
please gives to Ceasar that is of Cesar

the hanoi tower that I have posted in original code and then translated to QB64 is a sample code of TurboBasic 1.0 packaging.
My is the only translation, the algorithm is not mine!

[Qwerkey]

@Tempo, you are Italian and spell Caesar incorrectly (I think that he was most probably Roman)!

Tempo, bplus and Ron, some years ago I did think about writing a Towers of Hanoi program.  It looks like you have the logic completely solved, although the mere mention of 'recursion' has me flummoxed.  The program would look rather nicer with 3D disks on a 3D pyramid.  When I've learnt some OpenGL from Ashish, I may start a project with this in mind.  Don't hold your breaths, though!

[TempodiBasic]

Qwerkey
:-) lol you're right it is mispelled but I think that it is probably more mistyped!
the real name is nor Ceasar nor Cesare but Gaius Iulius Caesar https://en.wikipedia.org/wiki/Julius_Caesar
who turned the Roman Republic to the Roman Empire.

I'm waiting for the 3D Hanoi Tower... with or without OpengGl....