Author Topic: Tower of Hanoi puzzle (Read 8058 times)

Arnold · « **on:** March 22, 2016, 04:56:09 AM »

Hello,

This is the Tower of Hanoi problem in Oxygenbasic. The recursive algorithm I found at Rosetta code:
https://rosettacode.org/wiki/Towers_of_Hanoi
The Basic solution using a Subroutine can be run almost unchanged with Oxygenbasic. (the print statement must be adapted).
The iterative binary algorithm I found here:
http://hanoitower.mkolar.org/shortestTHalgo.html

When I started to read about ToH in Wikipedia I noticed that this problem and the possible variations is indeed not a trivial task. ToH is even used in psychological research on problem solving or is also used as a test by neuropsychologists trying to evaluate frontal lobe deficits. And much more. This is really astonishing.

The two algorithms I found are brilliant. I am jealous that I probably will never have such enlightenments. The binary solution is a little bit faster but using faster computers than mine I think this will not play a big role.

Nevertheless I wonder how this little piece of code would look in assembler and if there would be a gain in speed:

sub bmove(int n)
for x=1 to (1 << n)-1
count+=1
xm1=x-1
i=x & xm1 : fp=(i+i\3)&3
i=(x | xm1)+1 : tp=(i+i\3)&3

i=x : j=1
do
if (i & 1) then exit do
i=i >> 1 : j++
end do
next
end sub

Roland

Code: OxygenBasic

#include "$/inc/console.inc"
 
SetConsoleTitle "Towers of Hanoi problem"
 
! function GetTickCount lib "KERNEL32.DLL" () as dword
 
function time() as double 
  return GetTickCount()/1000
end function
 
int count, seeMoves
double t1,t2
 
sub rmove (int n, fromPeg, toPeg, viaPeg)
   if n>0 then
     rmove n-1, fromPeg, viaPeg, toPeg
     count+=1
     if seeMoves then
       printl count ": Move disc " n " from " chr(fromPeg+64) " to " chr(toPeg+64)
     end if
     rmove n-1, viaPeg, toPeg, fromPeg
   end if
end sub
 
sub bmove(int n)
   for x=1 to (1 << n)-1
     count+=1
     xm1=x-1
'     fp=mod(x & xm1,3) : tp=mod((x | xm1)+1,3) 'slower
     i=x & xm1     : fp=(i+i\3)&3
     i=(x | xm1)+1 : tp=(i+i\3)&3
 
     i=x : j=1
     do
       if (i & 1) then exit do
       i=i >> 1 : j++ 
     end do
 
     if seeMoves then
       printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
     end if
   next
end sub
 
 
start:
 
cls
seeMoves=0
print "Number of discs? " : num = val(input)
print "See the moves? (y/n) "
ans=waitkey : if lcase(chr(ans))="y" or lcase(chr(ans))="j" then seeMoves=1
printl "Minimum moves required: " pow(2,num)-1 & cr
 
printl "Calculating recursive, wait ..."
count=0
t1=time() : rmove num,1,2,3 : t2=time()
printl "Calculated " count " moves in " str(t2-t1,3) " seconds" & cr
 
printl "Calculating binary, wait ..."
count=0
t1=time() : bmove num : t2=time()
printl "Calculated " count " moves in " str(t2-t1,3) " seconds" & cr
 
printl "Another Try? (y/n)"
ans = getkey
if lcase(chr(ans))="y" or lcase(chr(ans))="j" then goto start
 
 

.

JRS · « **Reply #1 on:** March 23, 2016, 10:30:36 PM »

Roland,

Is this doing bit shifting?

Code: OxygenBasic

i=i >> 1 
 

Arnold · « **Reply #2 on:** March 24, 2016, 12:39:56 AM »

Hi John,

yes I think << and >> do the same job as the C operators. (binary left/right shift by the number of bits). I assume it is the same as integer divide / multiply with 2 ^ NumberOfBits. I also found <<< and >>> but I am not quite sure about the purpose of these operators.

Roland

Code: OxygenBasic

#include "$/inc/console.inc"
 
int i=100000000, j=i
int nb=4  'number of bits to shift
 
i = i >> nb : printl i
j = j \ (pow(2,nb)) : printl j
 
'reverse
 
i = i << nb : printl i
j = j * (pow(2,nb)) : printl j
 
waitkey
 

JRS · « **Reply #3 on:** March 24, 2016, 01:03:12 AM »

Charles created these Script BASIC extension module functions to deal with shift and rotate of bits.

@Charles - I'm unable to find the docs for these functions. Can you refresh my memory?

Code: C

besFUNCTION(gfx_Shift)
  DIM AS int bp, co, v, x, y, d, p, ar;
  besARGUMENTS("ii[i]")
    AT v, AT p, AT ar
  besARGEND
  IF (ar EQ NULL) THEN_DO ar = 0;
  x = 0xffffffff & v;
  IF (p >= 0) THEN
    y = x << p; // bit shift left
  ELSE
    y = x >> (-p); // bit shift right
  END_IF
//
// SUPPORT FOR ARITHMETIC RIGHT SHIFTS
//
  IF ((ar) AND (p < 0) AND (x & 0x80000000)) THEN
    d = 31 + p;
    IF (d < 0) THEN_DO d = 0; // LIMIT
    bp = 0x80000000;
    DEF_FOR (co = 31 TO co >= d STEP DECR co)
    BEGIN_FOR
      y = y | bp;
      bp = bp >> 1;
    NEXT
  END_IF
  besRETURN_LONG(y);
besEND
 
besFUNCTION(gfx_Rotate)
  DIM AS int co, v, x, y, d, p;
  besARGUMENTS("ii")
    AT v, AT p
  besARGEND
  x = 0xffffffff & v;
  d = p & 0x1f;
  DEF_FOR (co = 1 TO co <= d STEP INCR co)
  BEGIN_FOR
    y = x << 1;
    IF (x & 0x80000000) THEN_DO y |= 1;
    x = y;
  NEXT
    besRETURN_LONG(x & 0xffffffff);
besEND
 

Charles Pegge · « **Reply #4 on:** March 24, 2016, 02:03:26 PM »

OxygenBasic incorporates bit rotation operators. It uses assembly code instructions ROL and ROR.

In the case of 32 bit integers:

<<< shift left with bit 31 moving to bit 0

>>> shift right with bit 0 moving to bit 31

In C without recourse to Assember, such operators have to be emulated.

Shift Arithmetic Right (SAR) is the same as Shift Right (SHR) except that if bit 31, the sign bit, is set then it remains set after each bit shift, instead of being cleared. The effect is to retain sign. Thus, -4 becomes -2 etc.

JRS · « **Reply #5 on:** March 25, 2016, 12:56:37 AM »

I can't understand how this code would do a shift right with the Script BASIC gfx_shift function.

Code: OxygenBasic

i=i >> 1
 

If I translate this to

Code: Script BASIC

i = SHIFT(i, 1)
 

It's going to do a shift left as the second argument is greater than zero.

Charles Pegge · « **Reply #6 on:** March 25, 2016, 01:08:02 AM »

Hi John,

use negative values to shift right, for this function:

shift(i,-1)

Arnold · « **Reply #7 on:** March 25, 2016, 01:38:17 AM »

I do not know about Scriptbasic, but I think instead using shift operaters integer multiplication or division can be used. I assume for quads this is necessary anyway. So in OxygenBasic I could use for:

i=i>>1
i=i\2
and the loop would be:
for x=1 to (1 << n)-1
for x=1 to x*pow(2,n)-1

But I wanted to keep some of the original code. (and shifting is a little bit faster)

Roland

Mike Lobanovsky · « **Reply #8 on:** March 25, 2016, 03:20:49 AM »

Quote from: Arnold on March 25, 2016, 01:38:17 AM

(and shifting is a little bit faster)

Hi,

Actually, right shifts are a hellofalot faster on a modern Pentium than the respective integer division by a power-of-two (POT):

SHR/SAR instructions take only 1 CPU cycle to execute if the dividend is already in a register, or only 3 cycles if it is in memory;
SHR/SAR can be paired with other instructions in the Pentium UV pipes (if only the memory dividend and/or divisor aren't using an immediate value for displacement addressing), which effectively halves the execution time to 0.5 and 1.5 CPU cycles, respectively;
DIV/IDIV take 41/46 CPU cycles to execute on a Pentium and they need a few extra cycles to load at least the dividend into a register (memory and immediate dividends aren't permitted);
DIV/IDIV instructions aren't pairable at all.

Left shifts are also much faster than unsigned/signed multiplication by a POT: SHL/SAL are as fast and pairable as SHR/SAR while MUL/IMUL take at least 10 CPU cycles to execute and aren't pairable in the UV pipes.

Please correct me Charles if I am wrong, but in my opinion, since Oxygen resolves its BASIC code to assembly, the above considerations hold true for O2 as well.

Charles Pegge · « **Reply #9 on:** March 25, 2016, 11:56:19 AM »

Hi Mike, Glad to see you back

Yes O2 resolves shifts directly to assembler.

I recall my last DIV timing was about 35 clocks. Division fundamentally requires successive approximation. But muls have improved considerably on recent Pentiums, down to 1 or 2 clocks - in one massive hardware mul-gasm, I imagine.

JRS · « **Reply #10 on:** March 25, 2016, 05:55:18 PM »

Quote from: Charles

Hi Mike, Glad to see you back.

+1

JRS · « **Reply #11 on:** March 25, 2016, 10:34:39 PM »

Roland,

Here is the Script BASIC version. The Script BASIC POW() is base 10 only.

Code: Script BASIC

IMPORT gfx.inc
 
PRINT "Towers of Hanoi problem\n"
 
count = 0
seeMoves = 0
t1 = .0
t2 = .0
 
SUB rmove (n, fromPeg, toPeg, viaPeg)
   IF n > 0 THEN
     rmove n - 1, fromPeg, viaPeg, toPeg
     count += 1
     IF seeMoves THEN
       PRINT count, ": Move disc ", n, " from ", CHR(fromPeg + 64), " to ", CHR(toPeg + 64),"\n"
     END IF
     rmove n - 1, viaPeg, toPeg, fromPeg
   END IF
END SUB
 
SUB bmove(n)
   FOR x = 1 TO n - 1
     count += 1
     xm1 = x -1
     ' fp = x AND xm1 % 3 
     ' tp = (x OR xm1) + 1 % 3
     i = x AND xm1
     fp = (i + i \ 3) AND 3
     i = (x OR xm1) + 1
     tp = (i + i \ 3) AND 3
     i = x
     j = 1
     WHILE NOT i AND 1
'      IF i AND 1 THEN GOTO Exit_Do
       i = gfx::Shift(i, -1)
       j += 1
     WEND
'    Exit_Do:
     IF seeMoves THEN
       PRINT count, ": Move disc ", j, " from ", CHR(fp + 65), " to ", CHR(tp + 65), "\n"
     END IF
   NEXT
END SUB
 
 
start:
 
' cls
seeMoves = 0
PRINT "Number of discs? "
LINE INPUT user_input
num = VAL(CHOMP(user_input))
PRINT "See the moves? (y/n) "
LINE INPUT waitkey
ans = CHOMP(waitkey)
IF LCASE(ans) = "y" OR LCASE(ans) = "j" THEN seeMoves = 1
' PRINT "Minimum moves required: ", POW(num) - 1, "\n"
 
PRINT "Calculating recursive, wait ...\n"
count = 0
t1 = gfx::TIME()
rmove(num, 1, 2, 3)
t2 = gfx::time()
PRINT "Calculated ", count, " moves in ", FORMAT("%.4f",(t2-t1)/1000), " seconds\n"
 
PRINT "Calculating binary, wait ...\n"
count = 0
t1 = gfx::time()
bmove(num)
t2 = gfx::time()
PRINT "Calculated ", count, " moves in ", FORMAT("%.4f",(t2-t1)/1000), " seconds\n"
 
PRINT "Another Try? (y/n) "
LINE INPUT getkey
ans = CHOMP(gettkey)
IF LCASE(ans) = "y" OR LCASE(ans) = "j" THEN GOTO start
 

jrs@laptop:~/sb/sb22/test$ scriba hanoi.sb Towers of Hanoi problem Number of discs? 4 See the moves? (y/n) y Calculating recursive, wait ... 1: Move disc 1 from A to C 2: Move disc 2 from A to B 3: Move disc 1 from C to B 4: Move disc 3 from A to C 5: Move disc 1 from B to A 6: Move disc 2 from B to C 7: Move disc 1 from A to C 8: Move disc 4 from A to B 9: Move disc 1 from C to B 10: Move disc 2 from C to A 11: Move disc 1 from B to A 12: Move disc 3 from C to B 13: Move disc 1 from A to C 14: Move disc 2 from A to B 15: Move disc 1 from C to B Calculated 15 moves in 0.0000 seconds Calculating binary, wait ... 1: Move disc 1 from A to C 2: Move disc 2 from A to B 3: Move disc 1 from C to B Calculated 3 moves in 0.0000 seconds Another Try? (y/n)

Mike Lobanovsky · « **Reply #12 on:** March 26, 2016, 02:39:47 AM »

Hi everyone,

I'm also glad to see you around!

@Charles:

Intel is very reluctant to publish exact data on their modern superscalar CPUs (the ones that allow "out-of-order" parallel execution of instructions in the U and V execution pipes) so I won't be able to quote their quadcore iN CPUs, but their Core2 processors are still very slow in muldiv operations' latency which is also heavily bitness-dependent:

0. DIV : 40 cycles in 32 bits, 116 cycles in 64 bits, non-pairable
1. MUL : 5 cycles in 32 bits, 8 cycles in 64 bits, non-pairable
2. IMUL : 3 cycles in 32 bits, 5 cycles in 64 bits, non-pairable
3. left/right shift : 1 cycle in any bitness, freely pairable (i.e. 0.5 cycles if paired)

This means that the left shift is still 3 times faster than the fastest IMUL (non-paired 32 bits, worst case) and 16 times faster than the slowest MUL (paired 64 bits, best case).

DIV indeed remains the toughest bottleneck, and especially so, under 64 bits.

Arnold · « **Reply #13 on:** March 28, 2016, 12:39:33 AM »

Hi Charles,

this was my laborious task yesterday. I tried to transfer the statements for the ToH bmove function into assembler (amove). You will recognise the code.

Would there be a strategy to make this code still a little bit more efficient? As is at the moment there is not much gain of speed, but this is clear of course.

The reason for my question is if it makes sense to try assembly code for some small critical pieces in a function or sub or if this would be "much do about nothing". I personally think a good algorithm would save a lot of time anyway.

Roland

Code: OxygenBasic

$ filename "Hanoi.exe"
'#include "$/inc/RTL32.inc"
 
#include "$/inc/console.inc"
 
! function GetTickCount lib "KERNEL32.DLL" () as dword
 
function time() as double
  return GetTickCount()/1000
end function
 
int num, seeMoves
string ans
double t1,t2
 
#view
sub bmove(int n)
  int count=0
  for ix=1 to (1 << n)-1
     count+=1
     xm1=ix-1
 
     i=ix & xm1
     fp=(i+i\3)&3
     i=(ix | xm1)+1
     tp=(i+i\3)&3
 
 
     i=ix
     j=1
     do
       if (i & 1) then exit do
       i=i >> 1
       j++
     end do
     if seeMoves
       printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
     end if
  next
  printl "Calculated " count " moves"
end sub
#endv
 
 
sub amove(int n) '0x8
  int count,ix,to_limit,xm1,i,tmp1,fp,tmp2,tp,j     
 
'_7     '  for ix=1 to (1 << n)-1
  mov eax,1
  mov ix,eax
  mov eax,1
  mov cl,n
  shl eax,cl
''  mov [ebp-0x20],eax
''  mov eax,[ebp-0x20]
  sub eax,1
  mov to_limit,eax
(
._for
  mov eax,to_limit
  cmp ix,eaX
  mov eax,-1
  jle fwd _c
  inc eax
._c
  or eax,eax
  jz fwd _exit_for
 
 
'_8     '     count+=1
  add dword count,1
'_9     '     xm1=ix-1
  mov eax, ix
  sub eax,1
  mov xm1,eax
'_11'     i=ix & xm1
  mov eax,ix
  and eax,xm1
  mov i,eax
'_12    '     fp=(i+i\3)&3
  mov eax,i
  cwd
  mov ecx,3
  idiv ecx
  mov tmp1,eax
  mov eax,i
  add eax,tmp1
''  mov [ebp-0x30],eax
''  mov eax,[ebp-0x30]
  and eax,3
  mov fp,eax
'_13'     i=(ix | xm1)+1
  mov eax,ix
  or eax,xm1
''  mov [ebp-0x44],eax
''  mov eax,[ebp-0x44]
  add eax,1
  mov i,eax
'_14    '     tp=(i+i\3)&3
  mov eax,i
  cwd
  mov ecx,3
  idiv ecx
  mov tmp2,eax
  mov eax,i
  add eax,tmp2
''  mov [ebp-0x4C],eax
''  mov eax,[ebp-0x4C]
  and eax,3
  mov tp,eax
'_16    '     i=ix
  mov eax, ix
  mov i,eax
'_17    '     j=1
  mov eax,1
  mov j,eax
 
'_18    '     do
(
._do
        '       if (i & 1) then exit do
(
  mov eax,i
  and eax,1
._cnd
  or eax,eax
  jz fwd _exit_cnd
  jmp fwd _exit_do
._exit_cnd
._exit_if
)
 
'_20    '       i=i >> 1
  mov eax,i
  shr eax,1
  mov i,eax
'_21    '       j++
  inc [ebp-0x5C]
  inc j
'_22    '     end do
  jmp long _do
._exit_do
)
 
  if seeMoves then
     printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
  end if
 
'_24    '  next
  inc ix
  jmp long _for
._exit_for
 
  printl "Calculated " count " moves"
)
 
end sub
 
 
 
start:
 
cls
seeMoves=0
print "Number of discs? " : num = val(input)
print "See the moves? (y/n) "
ans=waitkey : if lcase(chr(ans))="y" then seeMoves=1
printl "Minimum moves required: " pow(2,num)-1 & cr
 
printl "Calculating binary, wait ..."
t1=time() : bmove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
 
printl "Calculating binary with ASM, wait ..."
t1=time() : amove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
 
printl "Another Try? (y/n)"
ans = getkey
if lcase(chr(ans))="y" then goto start
 

Output:

Number of discs? 28
See the moves? (y/n)
Minimum moves required: 268435455

Calculating binary, wait ...
Calculated 268435455 moves in 22.557 seconds

Calculating binary with ASM, wait ...
Calculated 268435455 moves in 20.639 seconds

Another Try? (y/n)

Mike Lobanovsky · « **Reply #14 on:** March 28, 2016, 05:27:15 AM »

Hi Roland,

The asm code you suggest is rather slow because it is built around memory variable access and integer division. You can speed it up almost 3 times by:

saving more temp vars in the CPU registers; and
using a much faster approximation of integer divide by 3.

There are a lot of tricks described on the net to speed up hand-written assembly for slower processor instructions like integer division and multiplication and FPU maths.

Please try the following code:

Code: OxygenBasic

    $ filename "Hanoi.exe"
    '#include "$/inc/RTL32.inc"
     
    #include "$/inc/console.inc"
     
    ! function GetTickCount lib "KERNEL32.DLL" () as dword
     
    function time() as double
      return GetTickCount()/1000
    end function
     
    int num, seeMoves
    string ans
    double t1,t2
     
    #view
    sub bmove(int n)
      int count=0
      for ix=1 to (1 << n)-1
         count+=1
         xm1=ix-1
     
         i=ix & xm1
         fp=(i+i\3)&3
         i=(ix | xm1)+1
         tp=(i+i\3)&3
     
     
         i=ix
         j=1
         do
           if (i & 1) then exit do
           i=i >> 1
           j++
         end do
         if seeMoves
           printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
         end if
      next
      printl "Calculated " count " moves"
    end sub
    #endv
     
     
    sub amove(int n) '0x8
      int count,ix,to_limit,xm1,i,tmp1,fp,tmp2,tp,j     
     
    '_7     '  for ix=1 to (1 << n)-1
      mov eax,1
      mov ix,eax
      mov eax,1
      mov cl,n
      shl eax,cl
    ''  mov [ebp-0x20],eax
    ''  mov eax,[ebp-0x20]
      sub eax,1
      mov to_limit,eax
    (
    ._for
      mov eax,to_limit
      cmp ix,eaX
      mov eax,-1
      jle fwd _c
      inc eax
    ._c
      or eax,eax
      jz fwd _exit_for
     
     
    '_8     '     count+=1
      add dword count,1
    '_9     '     xm1=ix-1
      mov eax, ix
      sub eax,1
      mov xm1,eax
    '_11'     i=ix & xm1
      mov eax,ix
      and eax,xm1
      mov i,eax
    '_12    '     fp=(i+i\3)&3
      mov eax,i
      cwd
      mov ecx,3
      idiv ecx
      mov tmp1,eax
      mov eax,i
      add eax,tmp1
    ''  mov [ebp-0x30],eax
    ''  mov eax,[ebp-0x30]
      and eax,3
      mov fp,eax
    '_13'     i=(ix | xm1)+1
      mov eax,ix
      or eax,xm1
    ''  mov [ebp-0x44],eax
    ''  mov eax,[ebp-0x44]
      add eax,1
      mov i,eax
    '_14    '     tp=(i+i\3)&3
      mov eax,i
      cwd
      mov ecx,3
      idiv ecx
      mov tmp2,eax
      mov eax,i
      add eax,tmp2
    ''  mov [ebp-0x4C],eax
    ''  mov eax,[ebp-0x4C]
      and eax,3
      mov tp,eax
    '_16    '     i=ix
      mov eax, ix
      mov i,eax
    '_17    '     j=1
      mov eax,1
      mov j,eax
     
    '_18    '     do
    (
    ._do
            '       if (i & 1) then exit do
    (
      mov eax,i
      and eax,1
    ._cnd
      or eax,eax
      jz fwd _exit_cnd
      jmp fwd _exit_do
    ._exit_cnd
    ._exit_if
    )
     
    '_20    '       i=i >> 1
      mov eax,i
      shr eax,1
      mov i,eax
    '_21    '       j++
      inc [ebp-0x5C]
      inc j
    '_22    '     end do
      jmp long _do
    ._exit_do
    )
     
      if seeMoves then
         printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
      end if
     
    '_24    '  next
      inc ix
      jmp long _for
    ._exit_for
     
      printl "Calculated " count " moves"
    )
     
    end sub
 
sub amove2(int n)
  int count,i,j,fp,tp
  
  pushad
  
  '_7 for ix=1 to (1 << n)-1
  mov esi, 1 ' ix
  mov edi, esi
  mov cl, n
  shl edi, cl
  dec edi ' to_limit
  
(
  ._for
  cmp esi, edi
  jle fwd _c
  jmp fwd _exit_for
 
  '_8 count+=1
  ._c
  add dword [count], 1
  
  '_9 xm1=ix-1
  mov ebx, esi
  dec ebx ' xm1
  
  '_11 i=ix & xm1
  mov eax, esi ' ix
  and eax, ebx ' xm1
  mov i, eax
  
  '_12 fp=(i+i\3)&3
  mov ecx, 0xAAAAAAAB ' 1/3
  mul ecx ' multiply with inverse
  shr edx, 1 ' shift by 33
  add edx, i
  and edx, 3
  mov fp, edx
  
  '_13 i=(ix | xm1)+1
  mov eax, esi ' ix
  or eax, ebx ' xm1
  inc eax
  mov i, eax
  
  '_14 tp=(i+i\3)&3
  mov ecx, 0xAAAAAAAB ' 1/3
  mul ecx ' multiply with inverse
  shr edx, 1 ' shift by 33
  add edx, i
  and edx, 3
  mov tp, edx
  
  '_16 i=ix
  mov ecx, esi
  
  '_17 j=1
  mov edx, 1
  
  '_18 do
(
  ._do
(
  ' if (i & 1) then exit do
  mov eax, ecx ' i
  and eax, 1
  ._cnd
  or eax, eax
  jz fwd _exit_cnd
  jmp fwd _exit_do
  ._exit_cnd
  ._exit_if
)
  
  '_20 i=i >> 1
  shr ecx, 1
  
  '_21 j++
  '    inc [ebp-0x5C]
  inc edx ' j
  
  '_22 end do
  jmp long _do
  ._exit_do
)
  
  '_24 next
  inc esi ' ix
  jmp long _for
  ._exit_for
 
  popad
)
  
  printl "Calculated " count " moves"
end sub
     
    start:
     
    cls
    seeMoves=0
    print "Number of discs? " : num = val(input)
    print "See the moves? (y/n) "
    ans=waitkey : if lcase(chr(ans))="y" then seeMoves=1
    printl "Minimum moves required: " pow(2,num)-1 & cr
     
    printl "Calculating binary, wait ..."
    t1=time() : bmove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
     
    printl "Calculating binary with Roland's ASM, wait ..."
    t1=time() : amove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
     
    printl "Calculating binary with Mike's ASM, wait ..."
    t1=time() : amove2 num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
 
    printl "Another Try? (y/n)"
    ans = getkey
    if lcase(chr(ans))="y" then goto start

.

Oxygen Basic

News:

Author Topic: Tower of Hanoi puzzle (Read 8058 times)

Arnold

Tower of Hanoi puzzle

JRS

Re: Tower of Hanoi puzzle

Arnold

Re: Tower of Hanoi puzzle

JRS

Re: Tower of Hanoi puzzle

Charles Pegge

Re: Tower of Hanoi puzzle

JRS

Re: Tower of Hanoi puzzle

Charles Pegge

Re: Tower of Hanoi puzzle

Arnold

Re: Tower of Hanoi puzzle

Mike Lobanovsky

Re: Tower of Hanoi puzzle

Charles Pegge

Re: Tower of Hanoi puzzle

JRS

Re: Tower of Hanoi puzzle

JRS

Re: Tower of Hanoi puzzle

Mike Lobanovsky

Re: Tower of Hanoi puzzle

Arnold

Re: Tower of Hanoi puzzle

Mike Lobanovsky

Re: Tower of Hanoi puzzle