バーティカルバーの極意（Vol.61掲載）

著者：飯尾淳

　前回から、「GDHP」（Gniibe Distributed HanoiProtocol）というプロトコルでハノイの塔パズルを解き、それを可視化して確認しようという試みに挑戦しています。プログラムはJavaScript で記述し、「p5.js」というグラフィックスライブラリを利用します。
　前回は、初期状態の塔を積み上げるところまで完成させました。今回はアニメーションで実際に動作させ、GDHPでパズルが解けることを確認しましょう。

シェルスクリプトマガジン Vol.61は以下のリンク先でご購入できます。

図1　向かい合う2本の塔を点滅させるコード

（略）
const POSITIONS = { 'Source'      : [0.268, 0.714],
                    'Auxiliary'   : [0.500, 0.286],
                    'Destination' : [0.732, 0.714] };
const FLASH_CTR = 20;

class Position {
（略）
}

class Tower {
  constructor(name, disks, direction=null) {
（略）
    this.pos = new Position(rx*C_WIDTH, ry*C_HEIGHT);

    this.exchanging = false;
    this.flash_ctr = 0;
  }

  draw() {
（略）
    // 支柱を描く
    stroke('brown');
    fill(this.exchanging & (this.flash_ctr < FLASH_CTR/2) 
      ? 'gold' : 'white');
    ellipse(pos.x, pos.y, 2*POLE_R);

（略）
    line(sx, sy, dx, dy);
  }

  flash_pole() {
    this.exchanging = (this.direction.direction === this);
    this.flash_ctr++;
    this.flash_ctr %= FLASH_CTR;
  }
}
）
function draw() {
  background('beige');
  [src, aux, dst].forEach(function(t) { 
    t.draw(); 
    t.flash_pole();
  })
}

（略）

const POSITIONS = { 'Source' : [0.268, 0.714],

'Auxiliary' : [0.500, 0.286],

'Destination' : [0.732, 0.714] };

const FLASH_CTR = 20;

class Position {

（略）

}

class Tower {

constructor(name, disks, direction=null) {

（略）

this.pos = new Position(rx*C_WIDTH, ry*C_HEIGHT);

this.exchanging = false;

this.flash_ctr = 0;

}

draw() {

（略）

// 支柱を描く

stroke('brown');

fill(this.exchanging & (this.flash_ctr < FLASH_CTR/2)

? 'gold' : 'white');

ellipse(pos.x, pos.y, 2*POLE_R);

（略）

line(sx, sy, dx, dy);

}

flash_pole() {

this.exchanging = (this.direction.direction === this);

this.flash_ctr++;

this.flash_ctr %= FLASH_CTR;

}

）

function draw() {

background('beige');

[src, aux, dst].forEach(function(t) {

t.draw();

t.flash_pole();

})

}

図3　draw()関数を修正する

var moving_disk = null;
（略）
function draw() {
  background('beige');
  [src, aux, dst].forEach(function(t) {
    t.draw();
    t.flash_pole();
  })

  if (moving_disk == null) {
    moving_disk = pop_disk();
  } else {
    var finished_p = draw_moving_disk();
    if (finished_p) {
      turn();
      moving_disk = null;
    }
  }
}

var moving_disk = null;

（略）

function draw() {

background('beige');

[src, aux, dst].forEach(function(t) {

t.draw();

t.flash_pole();

})

if (moving_disk == null) {

moving_disk = pop_disk();

} else {

var finished_p = draw_moving_disk();

if (finished_p) {

turn();

moving_disk = null;

}

図4　円盤を移動させる修正

（略）
const FLASH_CTR = 20;
const STEPS = 30;

class Vector {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class Position extends Vector {
  constructor(x, y) { super(x, y); }

  move(vec) {
    this.x += vec.x;
    this.y += vec.y;
  }
}  

class Disk {
  constructor(level) {
  this.level = level;
  this.color = COLORS[level];
  this.r = (DISK_R-POLE_R)*(N_DISKS-level)
              / N_DISKS + POLE_R;
}

  draw(pos) {
    stroke('black');
    fill(this.color);
    ellipse(pos.x, pos.y, 2*this.r);
  }
}

class MovingDisk extends Disk {
  constructor(level, from, to) {
    super(level); 
    this.pos = new Position(from.pos.x, from.pos.y);
    this.vec = new Vector((to.pos.x-from.pos.x)/STEPS, 
                          (to.pos.y-from.pos.y)/STEPS);
    this.move_ctr = 0;
    this.from = from;
    this.to = to;
  }

  step_forward() {
    this.pos.move(this.vec);
    this.move_ctr++;
  }

  finish_p() {
    var ret_flag = false;
    if (ret_flag = (this.move_ctr == STEPS)) {
      this.to.disks.push(new Disk(this.level));
    }
    return ret_flag;
  }
}

class Tower {
（略）
  flash_pole() {
    this.exchanging = (this.direction.direction === this);
    this.flash_ctr++;
    this.flash_ctr %= FLASH_CTR;
  }

  get toplevel() {
    var l = this.disks.length;
    // '-1'は円盤が一つもないことを示す
    return (l > 0) ? this.disks[l-1].level : -1;
  }
}

var src = new Tower('Source', N_DISKS);
（略）
src.direction = (N_DISKS % 2 == 1) ? dst : aux;

// 移動中の円盤
var moving_disk = null;

function pop_disk() {
  var towers = [src, aux, dst].filter(t => t.exchanging);
  var idx, from, to;
  idx = (towers[0].toplevel > towers[1].toplevel) ? 0 : 1;
  [from, to] = [towers[idx], towers[1-idx]];
  return new MovingDisk(from.disks.pop().level, from, to);
}

function draw_moving_disk() {
  var d = moving_disk;
  d.step_forward();
  d.draw(d.pos);
  return d.finish_p();
}

function turn() {
  // まだ何もしない
}

function setup() {
  createCanvas(C_WIDTH, C_HEIGHT);
  frameRate(30);
}

function draw() {
  background('beige');
  [src, aux, dst].forEach(function(t) { 
    t.draw(); 
    t.flash_pole();
  })

  if (moving_disk == null) {
    moving_disk = pop_disk();
  } else {
    var finished_p = draw_moving_disk();
    if (finished_p) {
      turn();
      moving_disk = null;
    }
  }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

（略）

const FLASH_CTR = 20;

const STEPS = 30;

class Vector {

constructor(x, y) {

this.x = x;

this.y = y;

}

class Position extends Vector {

constructor(x, y) { super(x, y); }

move(vec) {

this.x += vec.x;

this.y += vec.y;

}

class Disk {

constructor(level) {

this.level = level;

this.color = COLORS[level];

this.r = (DISK_R-POLE_R)*(N_DISKS-level)

/ N_DISKS + POLE_R;

}

draw(pos) {

stroke('black');

fill(this.color);

ellipse(pos.x, pos.y, 2*this.r);

}

class MovingDisk extends Disk {

constructor(level, from, to) {

super(level);

this.pos = new Position(from.pos.x, from.pos.y);

this.vec = new Vector((to.pos.x-from.pos.x)/STEPS,

(to.pos.y-from.pos.y)/STEPS);

this.move_ctr = 0;

this.from = from;

this.to = to;

}

step_forward() {

this.pos.move(this.vec);

this.move_ctr++;

}

finish_p() {

var ret_flag = false;

if (ret_flag = (this.move_ctr == STEPS)) {

this.to.disks.push(new Disk(this.level));

}

return ret_flag;

}

class Tower {

（略）

flash_pole() {

this.exchanging = (this.direction.direction === this);

this.flash_ctr++;

this.flash_ctr %= FLASH_CTR;

}

get toplevel() {

var l = this.disks.length;

// '-1'は円盤が一つもないことを示す

return (l > 0) ? this.disks[l-1].level : -1;

}

var src = new Tower('Source', N_DISKS);

（略）

src.direction = (N_DISKS % 2 == 1) ? dst : aux;

// 移動中の円盤

var moving_disk = null;

function pop_disk() {

var towers = [src, aux, dst].filter(t => t.exchanging);

var idx, from, to;

idx = (towers[0].toplevel > towers[1].toplevel) ? 0 : 1;

[from, to] = [towers[idx], towers[1-idx]];

return new MovingDisk(from.disks.pop().level, from, to);

}

function draw_moving_disk() {

var d = moving_disk;

d.step_forward();

d.draw(d.pos);

return d.finish_p();

}

function turn() {

// まだ何もしない

}

function setup() {

createCanvas(C_WIDTH, C_HEIGHT);

frameRate(30);

}

function draw() {

background('beige');

[src, aux, dst].forEach(function(t) {

t.draw();

t.flash_pole();

})

if (moving_disk == null) {

moving_disk = pop_disk();

} else {

var finished_p = draw_moving_disk();

if (finished_p) {

turn();

moving_disk = null;

}

図6　trun()関数

function turn() {
  [moving_disk.from, moving_disk.to].forEach(function(t) {
    t.direction = ([src, aux, dst]
      .filter(x => (x !== t) && (x !== t.direction)))[0];
    t.exchanging = false;
  })
}

function turn() {

[moving_disk.from, moving_disk.to].forEach(function(t) {

t.direction = ([src, aux, dst]

.filter(x => (x !== t) && (x !== t.direction)))[0];

t.exchanging = false;

})

}

図7　終了条件を追加

（略）
function pop_disk() {
  var towers = [src, aux, dst].filter(t => t.exchanging);
  var idx, from, to;
  if (towers[0].toplevel == towers[1].toplevel) { 
    noLoop(); 
    return null; 
  };
  idx = (towers[0].toplevel > towers[1].toplevel) ? 0 : 1;
  [from, to] = [towers[idx], towers[1-idx]];
  return new MovingDisk(from.disks.pop().level, from, to);
}
（略）

（略）

function pop_disk() {

var towers = [src, aux, dst].filter(t => t.exchanging);

var idx, from, to;

if (towers[0].toplevel == towers[1].toplevel) {

noLoop();

return null;

};

idx = (towers[0].toplevel > towers[1].toplevel) ? 0 : 1;

[from, to] = [towers[idx], towers[1-idx]];

return new MovingDisk(from.disks.pop().level, from, to);

}

（略）