Arduino and Tower of Hanoi

BEHOLD!!! My arduino can solve the Tower of Hanoi! This is pretty much my first ever programming attempt so of course most of it is copy-pasta from here. Code after the jump.

I don’t actually know if this solves the problem; just assuming Er’s code does the right stuff in RAM. I’m really only interested in making ANY code run and playing with memory.

As for benchmarks, it takes 15,910 miliseconds to solve for 25 disks.

/*
  Tower of Hanoi 
 Demonstrates using the AVR to solve a computational problem. Kinda slow...
*/

#define _disks 25;    // How many disks to use in the puzzle

void setup()
{
  // Make this 115200 baud to test how long printing takes.
  Serial.begin(9600);
}

void loop()
{
  int i, dir, *D, *s, n, j, howlong;

  n = _disks;
  // Making sure there is enough RAM
  if((D = (int *)malloc((n+2) * sizeof(int))) == NULL) hang();
  if((s = (int *)malloc((n+2) * sizeof(int))) == NULL) hang();
  j = n+1;

  Serial.print("Solving Hanoi for ");
  Serial.print(n, DEC);
  Serial.println(" disks.");

  // Use this value later to compute time
  howlong = millis();

/*
  Serial.print("D starts at ");
  Serial.println(long(D), DEC);
  Serial.print("s starts at ");
  Serial.println(long(s), DEC);
  // I love it when commands line up.
*/

  for (i=0; i<=j; i++) {
    D[i] = 1;
    s[i] = i+1;
    //Serial.println(long(&D[i]), DEC);
  }

  dir = n&1;
  for(;;) {
    i = s[0];
    if(i>n) break;
    j=D[i];
    D[i]=(i&1)==dir ? ~j>>(j&1)&3 : ++j>>(j>>2<<1);
    s[0] = 1;
    s[i-1] = s[i];
    s[i] = i+1;
  }

  /*
  // Commented out the free() statements to test the hang() function
  // causes the array to be allocated out of bounds (eventually).  
  free(D);
  free(s);  
  */

  // I want to find out how long it took
  Serial.print(int((millis() - howlong)), DEC);
  Serial.println(" millis to compute.");
  Serial.println("Done!");
  delay(1000);

}

void hang()
{
  long *memscroller = 0;
  int i; // Used for formatting

  Serial.println("malloc() failed, dropping pants and dumping...");
  delay(1000);

  // This just loops through memory addresses and prints the values stored therein.
  while(true)
  {
    Serial.print(byte(*memscroller++), HEX); // Print byte value

    // Do some really bad formatting
    if(i++%8 == 0) Serial.print("\t"); // Tab after 8 bytes  
    if(i++%32 == 0)
    {
      Serial.print("\n"); //Newline after 32 bytes
      i=0; //Reset variable
    }

    delay(100);
  }
}

And there you have it. One of my first forays into C and micro-controllers! Hello world!

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s