Pythonあれこれ（Vol.91掲載）

著者：飯尾 淳

本連載では「Pythonを昔から使っているものの、それほど使いこなしてはいない」という筆者が、いろいろな日常業務をPythonで処理することで、立派な「蛇使い」に育つことを目指します。その過程を温かく見守ってください。皆さんと共に勉強していきましょう。第21回では、「ハノイの塔」の解法「GDHP（Gniibe Distributed Hanoi Protocol）」の手順をアニメーションで表示するPythonアプリを作成します。

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

図2　GDHPの手順をアニメーションで表示するJavaScriptコード

const COLORS = [ 'crimson', 'forestgreen', 'yellow', 'royalblue',
                 'saddlebrown', 'hotpink', 'darkorange', 'darkmagenta' ];
const NUM_OF_DISKS = COLORS.length;
const BASE_LENGTH = 200;
const C_WIDTH  = 3.732 * BASE_LENGTH;
const C_HEIGHT = 3.500 * BASE_LENGTH;
const DISK_R = 0.9 * BASE_LENGTH;
const POLE_R = 15;
const POSITIONS = { 'Source'      : [0.268, 0.714],
                    'Auxiliary'   : [0.500, 0.286],
                    'Destination' : [0.732, 0.714] };
const FLASHING_COUNTER = 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)*(NUM_OF_DISKS-level)/NUM_OF_DISKS + POLE_R;
  }
}
class MovingDisk extends Disk {
  constructor(level,from,to) {
    super(level); 
    [sx,sy] = [from.pos.x,from.pos.y];
    [dx,dy] = [to.pos.x,  to.pos.y];
    this.pos = new Position(sx,sy);
    this.mvec = new Vector((dx-sx)/STEPS,(dy-sy)/STEPS);
    this.move_ctr = 0;
    this.from = from;
    this.to = to;
  }
  step_forward() {
    this.pos.move(this.mvec);
    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 {
  constructor(name, disks, direction=null) {
    this.name = name;
    this.disks = [];
    for (var i = 0; i < disks; i++) {
      this.disks.push(new Disk(i));
    }
    this.direction = direction;
    this.moving = false;
    this.flash_ctr = 0;
  }
  get toplevel() {
    var l = this.disks.length;
    // '-1' means there is no disk.
    return (l > 0) ? this.disks[l-1].level : -1;
  }
}
var src = new Tower('Source', NUM_OF_DISKS);
var aux = new Tower('Auxiliary',   0, src);
var dst = new Tower('Destination', 0, src);
// In the case of NUM_OF_DISKS is odd, 
// the src must face the src.
// Otherwise, the src faces the aux.
src.direction = (COLORS.length % 2 == 1) ? dst : aux;
// the reference to moving disk is stored to this variable.
var moving_disk = null;

function setup() {
  createCanvas(C_WIDTH, C_HEIGHT);
  frameRate(30);
  [src,aux,dst].forEach(function(t) {
    [rx,ry] = POSITIONS[t.name];
    t.pos = new Position(rx * C_WIDTH, ry * C_HEIGHT);
  })
}
function base_drawing() {
  background('beige');
  [src,aux,dst].forEach(function(t) {
    // draw disks
    t.disks.forEach(function(d) {
      stroke('black');
      fill(d.color);
      ellipse(t.pos.x,t.pos.y,2*d.r);
    })
    // draw a pole
    stroke('brown');
    fill(t.moving & (t.flash_ctr < FLASHING_COUNTER/2) ? 'gold' : 'white');
    ellipse(t.pos.x,t.pos.y,2*POLE_R);
    // draw a direction
    stroke('navy');
    [sx, sy] = [t.pos.x, t.pos.y];
    [dx, dy] = [t.direction.pos.x, t.direction.pos.y];
    r = POLE_R / Math.sqrt((dx-sx)*(dx-sx)+(dy-sy)*(dy-sy));
    [dx, dy] = [(dx-sx)*r+sx, (dy-sy)*r+sy];
    line(sx,sy,dx,dy);
  })
}
function flash_poles() {
  [src,aux,dst].forEach(function(t) {
    t.moving = (t.direction.direction === t);
    t.flash_ctr += 1;
    t.flash_ctr %= FLASHING_COUNTER;
  })
}
function pop_disk(src,aux,dst) {
  var towers = [src,aux,dst].filter(t => t.moving);
  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();
  stroke('black');
  fill(d.color);
  ellipse(d.pos.x,d.pos.y,2*d.r);
  return d.finish_p();
}
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.moving = false;
  })
}
function draw() {
  // base drawing
  base_drawing();
  // find two exchange-towers out of three
  flash_poles();
  // start moving
  if (moving_disk == null) {
    moving_disk = pop_disk(src,aux,dst);
  } else {
    if (draw_moving_disk()) {
      turn();
      moving_disk = null;
    }
  }
}

図3　Pygameを用いて描画ウィンドウを表示するPythonコード

import pygame

pygame.init()
screen = pygame.display.set_mode((640,480))
pygame.display.set_caption('Pygame Window')

while True:
  for event in pygame.event.get():
    if event.type == pygame.TEXTINPUT and event.text == 'q':
      pygame.quit()
      exit()

  screen.fill('lavender')

  pygame.display.flip()
  pygame.time.delay(30)

図5　GDHPの手順をアニメーションで表示するPythonコード

import pygame
import math

COLORS = [ 'crimson', 'forestgreen', 'yellow', 'royalblue',
           'saddlebrown', 'hotpink', 'darkorange', 'darkmagenta' ]
NUM_OF_DISKS = len(COLORS)
BASE_LENGTH = 200
C_WIDTH  = 3.732 * BASE_LENGTH
C_HEIGHT = 3.500 * BASE_LENGTH
DISK_R = 0.9 * BASE_LENGTH
POLE_R = 15
POSITIONS = { 'Source'      : [0.268, 0.714],
              'Auxiliary'   : [0.500, 0.286],
              'Destination' : [0.732, 0.714] }
FLASHING_COUNTER = 20
STEPS = 30

class Vector:
  def __init__(self, x, y):
    self.x = x
    self.y = y
class Position(Vector):
  def __init__(self, x, y):
    super().__init__(x, y)
  def move(self, vec):
    self.x += vec.x
    self.y += vec.y
class Disk:
  def __init__(self, level):
    self.level = level
    self.color = COLORS[level]
    self.r = (DISK_R-POLE_R)*(NUM_OF_DISKS-level)/NUM_OF_DISKS + POLE_R
class MovingDisk(Disk):
  def __init__(self, level, frm, to):
    super().__init__(level) 
    [sx, sy] = [frm.pos.x, frm.pos.y]
    [dx, dy] = [to.pos.x,  to.pos.y]
    self.pos = Position(sx,sy)
    self.mvec = Vector((dx-sx)/STEPS,(dy-sy)/STEPS)
    self.move_ctr = 0
    self.frm = frm
    self.to = to
  def step_forward(self):
    self.pos.move(self.mvec)
    self.move_ctr += 1
  def finish_p(self):
    ret_flag = (self.move_ctr == STEPS)
    if ret_flag:
      self.to.disks.append(Disk(self.level))
    return ret_flag
class Tower:
  def __init__(self, name, disks, direction=None):
    self.name = name
    self.disks = []
    for i in range(disks):
      self.disks.append(Disk(i))
    self.direction = direction
    self.moving = False
    self.flash_ctr = 0
  def toplevel(self):
    l = len(self.disks)
    # '-1' means there is no disk.
    return self.disks[l-1].level if l > 0 else -1
def setup():
  pygame.init()
  screen = pygame.display.set_mode((C_WIDTH, C_HEIGHT))
  pygame.display.set_caption('GDHP')
  for t in [src,aux,dst]:
    [rx, ry] = POSITIONS[t.name]
    t.pos = Position(rx * C_WIDTH, ry * C_HEIGHT)
  return screen
def base_drawing():
  screen.fill('beige')
  for t in [src,aux,dst]:
    # draw disks
    for d in t.disks:
      pygame.draw.circle(screen, d.color, (t.pos.x,t.pos.y), d.r)
      pygame.draw.circle(screen, 'black', (t.pos.x,t.pos.y), d.r, 1)
    # draw a pole
    fillcolor = 'gold' \
      if t.moving and t.flash_ctr < FLASHING_COUNTER/2 else 'white' 
    pygame.draw.circle(screen, fillcolor, (t.pos.x,t.pos.y), POLE_R)
    pygame.draw.circle(screen, 'brown', (t.pos.x,t.pos.y), POLE_R, 1)
    # draw a direction
    [sx, sy] = [t.pos.x, t.pos.y]
    [dx, dy] = [t.direction.pos.x, t.direction.pos.y]
    r = POLE_R / math.sqrt((dx-sx)*(dx-sx)+(dy-sy)*(dy-sy))
    [dx, dy] = [(dx-sx)*r+sx, (dy-sy)*r+sy]
    pygame.draw.line(screen, (0,0,128), (sx,sy), (dx,dy), 3)
def flash_poles():
  for t in [src,aux,dst]:
    t.moving = (t.direction.direction == t)
    t.flash_ctr += 1
    t.flash_ctr %= FLASHING_COUNTER
def pop_disk(src,aux,dst):
  towers = list(filter(lambda x: x.moving, [src,aux,dst]))
  idx = 0 if towers[0].toplevel() > towers[1].toplevel() else 1
  [frm, to] = [towers[idx], towers[1-idx]]
  return MovingDisk(frm.disks.pop().level,frm,to) \
           if len(frm.disks) > 0 else None
def draw_moving_disk():
  d = moving_disk
  d.step_forward()
  pygame.draw.circle(screen, d.color, (d.pos.x,d.pos.y), d.r)
  pygame.draw.circle(screen, 'black', (d.pos.x,d.pos.y), d.r, 1)
  return d.finish_p()
def turn():
  for t in [moving_disk.frm,moving_disk.to]:
    t.direction = list(filter(
      lambda x: (x != t) and (x != t.direction), [src,aux,dst]))[0]
    t.moving = False
def draw():
  # base drawing
  base_drawing()
  # find two exchange-towers out of three
  flash_poles()
  # start moving
  finish_p = False
  mdisk = moving_disk
  if mdisk == None:
    mdisk = pop_disk(src,aux,dst)
    if mdisk == None:
      finish_p = True
  else:
    if draw_moving_disk():
      turn()
      mdisk = None
  return mdisk, finish_p
# main routine
if __name__ == '__main__':
  src = Tower('Source', NUM_OF_DISKS)
  aux = Tower('Auxiliary',   0, src)
  dst = Tower('Destination', 0, src)
  # In the case of NUM_OF_DISKS is odd, 
  # the src must face the src.
  # Otherwise, the src faces the aux.
  src.direction = dst if len(COLORS) % 2 == 1 else aux
  # the reference to moving disk is stored to this variable.
  moving_disk = None
  screen = setup()
  while True:
    for event in pygame.event.get():
      if event.type == pygame.TEXTINPUT and event.text == 'q':
        pygame.quit()
        exit()
    moving_disk, finish_p = draw()
    if finish_p:
      pygame.quit()
      exit()
    pygame.display.flip()
    pygame.time.delay(30)