Blog der Heimetli Software AG

Towers of Hanoi in Typescript

21. Juni 2023 von Peter Tellenbach

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.

Diese Aufgabe hatte ich schon mit JavaScript gelöst aber diese Version finde ich besser weil die globalen Funktionen und Variablen in eine Klasse verpackt sind. Dank den Aufräumarbeiten war es recht einfach eine weitere Scheibe in die Türme zu setzen.

Der Code für die Animation

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

class Post
{
   constructor( public px: number, public level: number )
   {
   }

   draw( ctx: CanvasRenderingContext2D )
   {
      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( public px: number, public py: number, private r: number, private color: string )
   {
   }

   draw( ctx: CanvasRenderingContext2D )
   {
      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() ;
   }
}

class Hanoi
{
    private ctx!:   CanvasRenderingContext2D ;
    private posts!: Array<Post> ;
    private discs!: Array<Disc> ;
        
    drawScene()
    {
        this.ctx.clearRect( 0, 0, this.ctx.canvas.width, this.ctx.canvas.height ) ;
                           
        this.ctx.fillStyle = "#404040" ;
                           
        this.ctx.fillRect( 5, this.ctx.canvas.height-25, this.ctx.canvas.width-10, 20 ) ;
                           
        this.posts.forEach( p => p.draw(this.ctx) ) ;
    }

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

    draw()
    {
        this.drawScene() ;
        this.drawDiscs() ;
    }

    async drawAndSleep()
    {
        this.draw() ;
        await sleep( 25 ) ;
    }

    async move( disc: Disc, post: Post )
    {
       while( disc.py > 40 )
       {
            await this.drawAndSleep() ;
            disc.py -= 5 ;
       }
    
       const dx = post.px > disc.px ? 5 : -5 ;
    
       while( disc.px != post.px )
       {
            await this.drawAndSleep() ;
            disc.px += dx ;
       }
    
       while( disc.py < post.level )
       {
            await this.drawAndSleep() ;
            disc.py += 5 ;
       }
    }

    async hanoi( index: number, from: Post, to: Post, temp: Post )
    {
       if( index < this.discs.length )
       {
          await this.hanoi( index + 1, from, temp, to ) ;
          await this.move( this.discs[index], to ) ;
          from.level += 20 ;
          to.level   -= 20 ;
          await this.hanoi( index + 1, temp, to, from ) ;
       }
    }
    
    async animate()
    {
        let context = (<HTMLCanvasElement>document.querySelector( "#canvas" )).getContext( "2d" ) ;

        if( context != null )
        {
            const DISCS  = ["#E41A1C","#377EB8","#4DAF4A","#984EA3","#FF7F00","#7F88DD"] ;
            const BASE   = context.canvas.height-35 ;
            const HEIGHT = 20 ;

            this.ctx   = context ;

            this.posts = [new Post(85,BASE-DISCS.length*HEIGHT),
                          new Post(250,BASE),
                          new Post(425,BASE)] ;

            this.discs = DISCS.map( (c,i) => new Disc(85,BASE-i*HEIGHT,65-i*10,c) ) ;

            await this.hanoi( 0, this.posts[0], this.posts[2], this.posts[1] ) ;
            this.draw() ;
        }
    }
}

window.addEventListener("DOMContentLoaded", async () => await new Hanoi().animate() ) ;