Language vs algorithm part 1: Tower of Hanoi

As I see people talking about languages and some wondering differences and alike. I am going with a first try at picking one typical example (uses in basic classes) and showing it in several languages. Hopefully this creates curiosity about trying different things. And understand languages are just tools.

Disclaimer: I cannot avoid typos and maybe bugs in doing this. So let’s see how it goes.

The first example is a typical recursion problem: The Tower of Hanoi.
This is a classic mathematical puzzle that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
  3. No disk may be placed on top of a smaller disk.

Python

def hanoi(n, src, aux, dst):
    if n == 1:
        print(f"Move disk 1 from {src} to {dst}")
        return
    hanoi(n-1, src, dst, aux)
    print(f"Move disk {n} from {src} to {dst}")
    hanoi(n-1, aux, src, dst)
    
hanoi(3, 'A', 'B', 'C')

Java

public static void hanoi(int n, char src, char aux, char dst) {
    if (n == 1) {
        System.out.printf("Move disk 1 from %c to %c\n", src, dst);
        return;
    }
    hanoi(n-1, src, dst, aux);
    System.out.printf("Move disk %d from %c to %c\n", n, src, dst);
    hanoi(n-1, aux, src, dst);
}

hanoi(3, 'A', 'B', 'C');

C++

void hanoi(int n, char src, char aux, char dst) {
    if (n == 1) {
        cout << "Move disk 1 from " << src << " to " << dst << endl;
        return;
    }
    hanoi(n-1, src, dst, aux);
    cout << "Move disk " << n << " from " << src << " to " << dst << endl;
    hanoi(n-1, aux, src, dst);
}

hanoi(3, 'A', 'B', 'C');

JavaScript

function hanoi(n, src, aux, dst) {
    if (n == 1) {
        console.log(`Move disk 1 from ${src} to ${dst}`);
        return;
    }
    hanoi(n-1, src, dst, aux);
    console.log(`Move disk ${n} from ${src} to ${dst}`);
    hanoi(n-1, aux, src, dst);
}
hanoi(3, 'A', 'B', 'C')

JavaScript non-recursive

function hanoi(n, src, dst, aux) {
    let stack = [];
    stack.push([n, src, dst, aux]);
    while (stack.length > 0) {
        let [n, src, dst, aux] = stack.pop();
        if (n === 1) {
            console.log(`Move disk 1 from ${src} to ${dst}`);
        } else {
            stack.push([n-1, aux, dst, src]);
            stack.push([1, src, dst, aux]);
            stack.push([n-1, src, aux, dst]);
        }
    }
}
hanoi(3, 'A', 'B', 'C');

PHP

function hanoi($n, $src, $aux, $dst) {
    if ($n == 1) {
        echo "Move disk 1 from $src to $dst\n";
        return;
    }
    hanoi($n-1, $src, $dst, $aux);
    echo "Move disk $n from $src to $dst\n";
    hanoi($n-1, $aux, $src, $dst);
}

hanoi(3, 'A', 'B', 'C');

GO

package main

import "fmt"

func hanoi(n int, source string, destination string, spare string) {
    if n > 0 {
        hanoi(n-1, source, spare, destination)
        fmt.Printf("Move disk %d from %s to %s\n", n, source, destination)
        hanoi(n-1, spare, destination, source)
    }
}

func main() {
    hanoi(3, "A", "C", "B")
}

ADA

procedure Tower_Of_Hanoi (Discs : Integer; From, To, Using : Character) is
begin
   if Discs = 1 then
      Put_Line("Move disc from " & Character'Value(From) & " to " & Character'Value(To));
   else
      Tower_Of_Hanoi(Discs - 1, From, Using, To);
      Put_Line("Move disc from " & Character'Value(From) & " to " & Character'Value(To));
      Tower_Of_Hanoi(Discs - 1, Using, To, From);
   end if;
end Tower_Of_Hanoi;

COBOL

       IDENTIFICATION DIVISION.
       PROGRAM-ID. HANOI.
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
           SELECT SYSIN ASSIGN TO KEYBOARD.
           SELECT SYSOUT ASSIGN TO PRINTER.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  DISCS PIC 9(2).
       01  FROM-POLE PIC X.
       01  TO-POLE PIC X.
       01  USE-POLE PIC X.
       PROCEDURE DIVISION.
       BEGIN.
           DISPLAY "ENTER THE NUMBER OF DISCS".
           ACCEPT DISCS.
           DISPLAY "ENTER THE FROM POLE (A, B OR C)".
           ACCEPT FROM-POLE.
           DISPLAY "ENTER THE TO POLE (A, B OR C)".
           ACCEPT TO-POLE.
           DISPLAY "ENTER THE USE POLE (A, B OR C)".
           ACCEPT USE-POLE.
           PERFORM TOWERS OF HANOI
                   USING DISCS, FROM-POLE, TO-POLE, USE-POLE.
           STOP RUN.
       TOWERS OF HANOI.
           IF DISCS > 0 THEN
               PERFORM TOWERS OF HANOI
                   USING DISCS - 1, FROM-POLE, USE-POLE, TO-POLE
               END-PERFORM
               DISPLAY "MOVE DISC FROM ", FROM-POLE,
                   " TO ", TO-POLE
               PERFORM TOWERS OF HANOI
                   USING DISCS - 1, USE-POLE, TO-POLE, FROM-POLE
           END-IF.

And one old and modern that are my favourites:

FORTH

: hanoi ( n a b c -- )
  dup 1 = if
    dup 1 swap move
  else
    dup 1 - over swap swap hanoi
    swap move
    dup 1 - rot rot hanoi
  then
;
 
: move ( a b -- ) ." Move disk " dup . ." from " 1 . ." to " 2 . cr ;

Brainfk (sorry guys)

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

This is not the best example to show variety, it should show how similar some (modern) languages actually are :slight_smile:

UPDATE: this is now a wiki and all next parts will be also. Feel free to add versions in other languages!

8 Likes

What is name of the fourth language?

That is PHP (as written). It became very popular in the early days of facebook as legend says facebook initial idea was hacked fast together with it.

2 Likes

ah tyes tower of hanoi

Could JS and C be added?

I guess C will look like C++ … i truly dislike JS so i hope if somebody would chip in for it :slight_smile:
Maybe part 2 i pick an example (showing more differences) and let who want chip in making an example in a different language

1 Like

13 posts were split to a new topic: Making posts wiki and TL3 flair

Added JS :slight_smile: It’s the same as the Python and PHP ones but with JS syntax (PHP is basically a JS fork so converting the two should always be pretty easy).

1 Like

I moved it cause I think it was going from most similar languages to least alike :slightly_smiling_face:

Is there a nim example? I couldn’t find one online, and the nim playground is down so I cannot test around.

2 Likes

I can add nim, but there is somebody here who is more expert in nim than me and maybe he can take the tas up.

2 Likes

One reason why many examples appear similar is that they use recursion and conditional statements to solve Tower of Hanoi. Recursion involves a function calling itself, which looks similar across different languages (in many programming languages). Similarly, conditional statements, such as the “if” statement, have a similar syntax in many programming languages.

Here is JavaScript version that uses non recursive way to solve Tower of Hanoi:

function hanoi(n, src, dst, aux) {
  let stack = [];
  stack.push([n, src, dst, aux]); // initiating starting tower setup
  while (stack.length > 0) {
    let [n, src, dst, aux] = stack.pop(); // destructures array variables to gain easier access
    if (n === 1) console.log(`Move disk 1 from ${src} to ${dst}`); // identify moves that need to be reported console
    else {  
      stack.push([n - 1, aux, dst, src]); // manipulate data step by step to find correct moves
      stack.push([1, src, dst, aux]);
      stack.push([n - 1, src, aux, dst]);
    }
  }
}

hanoi(3, 'A', 'B', 'C');

This start to look different already.

EDIT: I slightly updated that code and added some explanations.

1 Like

Indeed, would be nice to see some more dynamic programming examples :slight_smile: