Blog der Heimetli Software AG

Towers of Hanoi

von

Das ist eine sehr beliebte Aufgabe für Informatik-Studenten die sich in die Rekursion einarbeiten. Man findet die Türme aber auch in der Kinderabteilung von Spielzeugläden.

Aufgabe: die Scheiben vom Stab links auf den Stab rechts zu bewegen, mit der Einschränkung dass nie eine grössere Scheibe auf einer kleineren liegen darf.

Der Code für die Animation

class Post
{
   constructor( px, level )
   {
      this.px    = px ;
      this.level = level ;
   }

   draw( ctx )
   {
      const y = ctx.canvas.height - 25 ;

      ctx.beginPath() ;
      ctx.moveTo( this.px - 5,  y ) ;
      ctx.lineTo( this.px - 5,  y - 120 ) ;
      ctx.arc( this.px, y - 120, 5, Math.PI, 0 ) ;
      ctx.lineTo( this.px + 5, y ) ;
      ctx.closePath() ;

      ctx.fill() ;
   }
}

class Disc
{
   constructor( px, py, r, color )
   {
      this.px    = px ;
      this.py    = py ;
      this.r     = r ;
      this.color = color ;
   }

   draw( ctx )
   {
      ctx.fillStyle = this.color ;

      ctx.beginPath() ;
      ctx.moveTo( this.px - this.r + 10,  this.py + 10 ) ;
      ctx.lineTo( this.px + this.r - 10,  this.py + 10 ) ;
      ctx.arc( this.px + this.r - 10, this.py, 10, 3 * Math.PI / 2, Math.PI / 2 ) ;
      ctx.lineTo( this.px + this.r - 10, this.py - 10 ) ;
      ctx.lineTo( this.px - this.r + 10, this.py - 10 ) ;
      ctx.arc( this.px - this.r + 10, this.py, 10, Math.PI / 2, 3 * Math.PI / 2 ) ;
      ctx.closePath() ;

      ctx.fill() ;
   }
}

const sleep = ms => new Promise( r => setTimeout(r,ms) ) ;

const ctx   = document.querySelector( "#canvas" ).getContext( "2d" ) ;
const posts = [new Post(85,ctx.canvas.height-135),
	       new Post(250,ctx.canvas.height-35),
	       new Post(425,ctx.canvas.height-35)] ;
const discs = [new Disc(85,ctx.canvas.height-35,65,"#E41A1C"),
	       new Disc(85,ctx.canvas.height-55,55,"#377EB8"),
	       new Disc(85,ctx.canvas.height-75,45,"#4DAF4A"),
	       new Disc(85,ctx.canvas.height-95,35,"#984EA3"),
	       new Disc(85,ctx.canvas.height-115,25,"#FF7F00")] ;

function drawScene( ctx )
{
   ctx.clearRect( 0, 0, ctx.canvas.width, ctx.canvas.height ) ;

   ctx.fillStyle = "#404040" ;

   ctx.fillRect( 5, ctx.canvas.height-25, ctx.canvas.width-10, 20 ) ;

   posts.forEach( p => {
      p.draw( ctx ) ;
    } ) ;
}

function drawDiscs( ctx )
{
   discs.forEach( d => {
      d.draw( ctx ) ;
   } ) ;
}

async function move( disc, post )
{
   while( disc.py > 40 )
   {
      drawScene( ctx ) ;
      drawDiscs( ctx ) ;
      await sleep( 25 ) ;
      disc.py -= 5 ;
   }

   const dx = post.px > disc.px ? 5 : -5 ;

   while( disc.px != post.px )
   {
      drawScene( ctx ) ;
      drawDiscs( ctx ) ;
      await sleep( 25 ) ;
      disc.px += dx ;
   }

   while( disc.py < post.level )
   {
      drawScene( ctx ) ;
      drawDiscs( ctx ) ;
      await sleep( 25 ) ;
      disc.py += 5 ;
   }
}

async function hanoi( index, from, to, temp )
{
   if( index < discs.length )
   {
      await hanoi( index + 1, from, temp, to ) ;
      await move( discs[index], to ) ;
      from.level += 20 ;
      to.level   -= 20 ;
      await hanoi( index + 1, temp, to, from ) ;
   }
}

async function animate()
{
   await hanoi( 0, posts[0], posts[2], posts[1] ) ;
   drawScene( ctx ) ;
   drawDiscs( ctx ) ;
}

animate() ;

Eine verbesserte Version in Typescript gibt es mittlerweile auch.