LoginSignup
5
0

More than 1 year has passed since last update.

PostgreSQLAdvent Calendar 2021Day 19
@kingtomo1122

Towers of Hanoi on PostgreSQL

Last updated at Posted at 2021-12-19

この記事はPostgreSQL Advent Calendar 2021の19日目の記事です。

はじめに

冬になるとハノイの塔をやりたくなりますよね。
しかし、財政難で既製品の購入はできないため、PostgreSQLでなんとかしようと思います。ありがたきOSS！

ハノイの塔とは

WikiPediaより：

ハノイの塔（ハノイのとう、Tower of Hanoi）は、パズルの一種。 バラモンの塔または ルーカスタワー(Lucas' Tower)[注 1]とも呼ばれる。

パズルのルールは、「3本の塔があり、ある1本の塔にあるN枚の円盤を上に大きな円盤を載せないようにしながら別の塔に移動させる」というもの。

頭の体操です！

PostgreSQLで実現

どうしようかな～と考えて、以下の仕様で作り始めました。
とりまDB名は「hanoi」で。

テーブル構成

テーブル名 役割 備考
tbl_src スタート塔 初期状態で、円盤はここに積む
tbl_dst ゴール塔 ここにもってくればOK！
tbl_wrk 作業用塔 一時置き場
tbl_height 件数管理 各塔が現在何段あるかを管理。あとで使う

ユーザ構成

全部消して入れ直しなどのズルができないように、スーパーユーザとは別に一般ピーポーを作成し、上記テーブルの操作はできないようにしておきます。
操作はSQL関数定義してそれを実行する形とします。

PS D:\work\2021\AdventCalendar\script> createuser -P player
PS D:\work\2021\AdventCalendar\script> psql -U player -W -c "SELECT * FROM tbl_src;" hanoi
パスワード:
ERROR:  permission denied for table tbl_src

SQL関数

「SQL関数」と書きましたが、結果返す必要もないなと思い、PROCEDUREにしてみました。
プロシージャ名は「move」。引数で移動元テーブル名、移動先テーブル名を指定することとし、プロシージャ内でズルしてないかの判断をします。

構築！

初期構築スクリプト

DB：hanoiを作って、次のSQLファイルを流し込みます。

create_hanoi.sql
CREATE TABLE IF NOT EXISTS tbl_src(i INT NOT NULL);
CREATE TABLE IF NOT EXISTS tbl_wrk(i INT NOT NULL);
CREATE TABLE IF NOT EXISTS tbl_dst(i INT NOT NULL);

CREATE TABLE IF NOT EXISTS tbl_height(tbl_src INT, tbl_wrk INT, tbl_dst INT);

INSERT INTO tbl_src VALUES (1),(2),(3);
INSERT INTO tbl_height VALUES (3, 0, 0);

TABLE tbl_src ORDER BY i; TABLE tbl_wrk ORDER BY i; TABLE tbl_dst ORDER BY i;

動かして↓のようになればOK！
3つのテーブル内容表示しており、上からtbl_src、tbl_wrk、tbl_dstの結果です。

D:\work\2021\AdventCalendar\script>createdb hanoi
D:\work\2021\AdventCalendar\script>psql -f create_hanoi.sql hanoi
CREATE TABLE
CREATE TABLE
CREATE TABLE
CREATE TABLE
INSERT 0 3
INSERT 0 1
 i
---
 1
 2
 3
(3 行)


 i
---
(0 行)


 i
---
(0 行)

移動プロシージャ

以下のプロシージャを定義します。

CREATE OR REPLACE PROCEDURE move(from_tbl TEXT, to_tbl TEXT) AS $$
DECLARE
  all_tbl TEXT[];
  tbl TEXT;
  res RECORD;
BEGIN
  -- move one object
  EXECUTE '
  WITH a AS (DELETE FROM ' || from_tbl || ' WHERE i = (SELECT min(i) FROM ' || from_tbl || ') RETURNING i), 
       b AS (SELECT min(i) FROM ' || to_tbl || ')
  INSERT INTO ' || to_tbl || ' SELECT CASE WHEN b IS NULL OR a.i < b.min THEN a.i END FROM a, b
  '
  USING from_tbl, to_tbl;
  EXECUTE 'UPDATE tbl_height SET ' || from_tbl || ' = ' || from_tbl || '-1, ' || to_tbl || ' = ' || to_tbl || '+1';

  -- show current status
  all_tbl = ARRAY['tbl_src','tbl_wrk','tbl_dst'];
  RAISE INFO '===============';
  FOREACH tbl IN ARRAY all_tbl LOOP
    RAISE INFO '%', tbl;
    FOR res IN EXECUTE 'TABLE ' || tbl || ' ORDER BY i;' LOOP
      RAISE INFO '%', res;
    END LOOP;
    RAISE INFO '-----';
  END LOOP;
  RAISE INFO '===============';
END;
$$ LANGUAGE PLPGSQL
SECURITY DEFINER;

いろいろやってるけど、ポイントは以下2点。

  1. WITH句の1つ目でfrom_tblから一番上の円盤(最小値のもの)を削除してその結果(RETURNING)をaに入れ、2つ目でto_tblの一番上の円盤を取得してbに入れる。a, bを使ってto_tblに円盤を挿入する。
  2. 一般ピーポーでも関数実行でテーブル操作できるように「SECURITY DEFINER」でPROCEDURE定義する。

いい感じ？

無事にPostgreSQL上で論理ハノイの塔を構築できました。

PS D:\work\2021\AdventCalendar\script> psql -U player -W hanoi
パスワード:
psql (14.0)
"help"でヘルプを表示します。

hanoi=> CALL move('tbl_src', 'tbl_dst');
INFO:  ===============
INFO:  tbl_src
INFO:  (2)
INFO:  (3)
INFO:  -----
INFO:  tbl_wrk
INFO:  -----
INFO:  tbl_dst
INFO:  (1)
INFO:  -----
INFO:  ===============
CALL
hanoi=> CALL move('tbl_src', 'tbl_wrk');
INFO:  ===============
INFO:  tbl_src
INFO:  (3)
INFO:  -----
INFO:  tbl_wrk
INFO:  (2)
INFO:  -----
INFO:  tbl_dst
INFO:  (1)
INFO:  -----
INFO:  ===============
CALL

　
　
　
「・・・も、物足りないorz」

昭和生まれに論理ハノイの塔は物足りなさ抜群でチョベリバな感じです。。。
ということで、物理ハノイの塔をGetします。とはいえ、冒頭で申しました通り財政難のため、自作しました。粘土で。

IMG_1987.JPG

折角なので、論理ハノイの塔と物理ハノイの塔を連携します！

論理ハノイの塔と物理ハノイの塔の連携

手間は省きたい

折角moveプロシージャも作ったので、書き直したくないでござる。
そんなときは、、、

「ロジカルデコーディング～」

これで、論理ハノイの塔への操作で物理ハノイの塔を操作することをやっていきます。

ロジカルデコーディングとは

ロジカルデコーディングは「SQLによって実行された更新結果を外部のコンシューマにストリーミングする基盤」です。
https://www.postgresql.jp/document/13/html/logicaldecoding.html

ロジカルデコーディングでは、WALの内容をアプリケーションが扱いやすい形式に変換（デコード）できます。論理レプリケーションでも利用されていますが、クライアントアプリケーション「pg_recvlogical」を使うとさくっとWALの内容を見ることができます。デフォルトのプラグインはcontribに含まれてる「test_decoding」です。ソースコードからインストールするときは、こいつも一緒にインストールしましょう（Windowsパッケージには最初から含まれてた）。

なお、利用するにはwal_levelを"logical"に設定する必要があります（デフォルトは"replica"）。

postgresql.conf
#------------------------------------------------------------------------------
# WRITE-AHEAD LOG
#------------------------------------------------------------------------------

# - Settings -

#wal_level = replica            # minimal, replica, or logical
wal_level = logical         # minimal, replica, or logical
                    # (change requires restart)

moveプロシージャ呼び出すと、pg_recvlogicalで次のようなWALの内容を確認できます。

PS D:\work\2021\AdventCalendar\script> pg_recvlogical.exe --create-slot --if-not-exists --start --slot=hanoi --dbname=hanoi -f -
pg_recvlogical: エラー: ファイル"-"のstatに失敗しました: Invalid argument
BEGIN 1620
table public.tbl_src: DELETE: (no-tuple-data)
table public.tbl_dst: INSERT: i[integer]:1
table public.tbl_height: UPDATE: tbl_src[integer]:2 tbl_wrk[integer]:0 tbl_dst[integer]:1
COMMIT 1620

なんかエラーでるけどバグかしら。 マニュアルには標準出力に出すときは-fで"-"を指定してねってかいてあるけど、Windows(PowerShell?)だとダメでした。まぁ、処理が止まるわけではないので今回はスルー。

この結果をパースしてあげれば何とかなりそう。

どうやって動かすか？

論理ハノイの塔の操作内容はpg_recvlogicalで取得するとして、その操作内容をどのように物理ハノイの塔に適用するか？
悩んだ結果、買いました。ロボットアーム。

IMG_1946.JPG

マニュアルに従ってアセンブリング！！

IMG_1947.JPG

男の子ってこういうのが好きなんでしょ？

このロボットアームはArduinoが搭載されており、Arduino内のメモリにinoファイルを登録しておくことで、pythonから制御可能です。
今回は次のようなhanoi.ino、hanoi_recvlogical.pyを用意して制御しました。

hanoi.ino
#include <Servo.h>

int servopin1 = 9;    //Define servo interface digital interface 9
int servopin2 = 6;    //Define servo interface digital interface 6
int servopin3 = 5;    //Define servo interface digital interface 5
int servopin4 = 3;    //Define servo interface digital interface 3
int servopin5 = 11;   //Define servo interface digital interface 11

int moveServoData;
Servo servo1;
Servo servo2;
Servo servo3;
Servo servo4;
Servo servo5;
int angle  = 90;        //Angle of rotation of the servo
int angle2 = 90;        //Angle of rotation of the servo
int angle3 = 90;        //Angle of rotation of the servo
int angle4 = 90;        //Angle of rotation of the servo

void setup() {
  // put your setup code here, to run once:
  pinMode(servopin1,OUTPUT);//Set the servo interface as the output interface
  pinMode(servopin2,OUTPUT);//Set the servo interface as the output interface
  pinMode(servopin3,OUTPUT);//Set the servo interface as the output interface
  pinMode(servopin4,OUTPUT);//Set the servo interface as the output interface
  pinMode(servopin5,OUTPUT);//Set the servo interface as the output interface
  Serial.begin(9600);
}

void loop()
{
  servo1.attach(servopin1);
  servo2.attach(servopin2);
  servo3.attach(servopin3);
  servo4.attach(servopin4);
  servo5.attach(servopin5);

  if(Serial.available()>0){
    angle = Serial.read();
    angle2 = Serial.read();
    angle3 = Serial.read();
    angle4 = Serial.read();

    pickup();
    delay(1000);
    puton();
  }
  delay(20);
}

void pickup(){
  // 広げる
  servo5.write(0); 
  delay(1000);
  // 回転
  servo1.write(angle);
  delay(1000);
  // 倒れる
  for(int i = 90; i >= angle2; i=i-3){
    servo2.write(i);
    delay(50);
  }
  servo2.write(angle2);
  //servo2.write(angle2);
  delay(500);
  // 深く倒れる（いじらない）
  servo3.write(90);
  delay(500);
  // 傾げる（いじらない）
  servo4.write(90);
  delay(500);
  // 閉じる
  for(int i = 0; i <= 90; i=i+3){
    servo5.write(i);
    delay(50);
  }
  //servo5.write(90); 
  delay(1000);
  // 持ち上げる
  for(int i = angle2; i <= 90; i=i+3){
    servo2.write(i);
    delay(50);
  }
  //servo2.write(90);
  delay(500);
}

void puton(){
  // 回転
  servo1.write(angle3);
  delay(1000);
  // 倒れる
  for(int i = 90; i >= angle4; i=i-3){
    servo2.write(i);
    delay(50);
  }
  servo2.write(angle4);
  //servo2.write(0);
  delay(500);
  // 深く倒れる（いじらない）
  servo3.write(90);
  delay(500);
  // 傾げる（いじらない）
  servo4.write(90);
  delay(500);
  // 開く
  for(int i = 90; i >= 0; i=i-3){
    servo5.write(i);
    delay(50);
  }
  //servo5.write(0); 
  delay(1000);
  // 元に戻る
  for(int i = angle4; i <= 90; i=i+3){
    servo2.write(i);
    delay(50);
  }
  //servo2.write(90);
  delay(500);
}

loop関数の中で、Serial通信からの入力値を待っててくれるので、python(pySerial)で値を送ってあげればアームを動かせます。
なお、サーボモータ5個着いてますが、制御が面倒なので使うのは3つのみとしました。3つでも「回転する」「倒れる」「アームを開閉する」ことで円盤を移動できます。

python側

とりま、pyserialをpipでインストール。

D:\work\2021\AdventCalendar\script> pip install pyserial

で、右(0度)をtbl_src、真ん中(90度)をtbl_wrk、左(180度)をtbl_dstとし、高さが何段目かを0度(一番下)、6度(真ん中)、9度(一番上)と定義して次のコードを作成します。
ちなみに、「何段目か」を取得するためにtbl_heightをわざわざ更新して、pg_recvlogicalで値を取得できるようにしています。

hanoi_recvlogical.py
import serial, time
import subprocess

ser = serial.Serial("COM4", 9600)
time.sleep(1.5)

proc = subprocess.Popen('pg_recvlogical.exe --create-slot --if-not-exists --start --slot=hanoi --dbname=hanoi -f -', shell=True, stdout=subprocess.PIPE)

tower_pos = {
    "tbl_src" : 0,
    "tbl_wrk" : 90,
    "tbl_dst" : 180
}
tower_height = {
    1 : 0, # bottom
    2 : 6, # middle
    3 : 9  # top
}

while True:
    for line in proc.stdout:
        print(line.decode('utf-8'), end='')
        line = line.decode('utf-8')
        if line.find('BEGIN') != -1:
            args =  [90, 90, 90, 90]
            flg = [False, False, False, False]
        elif line.find('DELETE') != -1:
            work = line[:(line.find(':'))]
            work = work[(work.find('.'))+1:]
            args[0] = work
            flg[0]  = True
        elif line.find('INSERT') != -1:
            work = line[:(line.find(':'))]
            work = work[(work.find('.'))+1:]
            args[2] = work
            flg[2]  = True
        elif line.find('UPDATE') != -1:
            for idx in [0, 2]:
                work = line[(line.find(args[idx]))+1:]
                work = work[(work.find(':'))+1:]
                work = work[:(work.find(' '))]
                args[idx+1] = int(work)
                flg[idx+1]  = True
            args[1] = args[1] + 1
            # move arm...
            if flg == [True, True, True, True]:
                a  = tower_pos[args[0]]
                a2 = tower_height[args[1]]
                a3 = tower_pos[args[2]]
                a4 = tower_height[args[3]]

                send_data = a.to_bytes(1, 'big')
                ser.write(send_data)
                send_data = a2.to_bytes(1, 'big')
                ser.write(send_data)
                send_data = a3.to_bytes(1, 'big')
                ser.write(send_data)
                send_data = a4.to_bytes(1, 'big')
                ser.write(send_data)
            flg = [False, False, False, False]
        elif line.find('COMMIT') != -1:
            flg = [False, False, False, False]
        else:
            # do nothing...
            print("do nothing...")

システム構成

登場人物多くて複雑に見えますが、図示するとこんな感じです。シンプル。

image_for_tower_of_hanoi.png

moveプロシージャと連携できた！

上記がそろうことで、「CALL move」すると「アームを動かす」ということが実現できました。

ここまできたら・・・

ハノイの塔自動解決

ハノイの塔って、再帰プログラムで解決できるんだって。
ググってみると、色々とアルゴリズムでてくる。折角だから、ここまでやってみましょう。

「再帰プログラム」といえば、PostgreSQLでも「With Recursive」使えるし！かつる！！

さらに、こんなの発見！
https://wiki.postgresql.org/wiki/Towers_of_Hanoi

偉大なる先人の教え。ありがたや。かつる！！

ちょっとカスタマイズ

Wikiの関数をまるっとコピー。それを呼び出せば以下のような挙動をとります。
こちらの関数では1テーブルに3つの論理ハノイの塔を再現していました。
a列がtbl_src、b列がtbl_dst、c列がtbl_wrkですね。

hanoi=# SELECT * FROM hanoi(3);
 move |    a    |    b    |   c
------+---------+---------+-------
    1 | {3,2,1} | {}      | {}
    2 | {3,2}   | {1}     | {}
    3 | {3}     | {1}     | {2}
    4 | {3}     | {}      | {2,1}
    5 | {}      | {3}     | {2,1}
    6 | {1}     | {3}     | {2}
    7 | {1}     | {3,2}   | {}
    8 | {}      | {3,2,1} | {}
(8 行)

このままでは使えないので、ラッパー関数を用意してあげました(特に理由なくDO文で)。

DO $$
DECLARE
    r record;
BEGIN
    FOR r IN SELECT
        CASE WHEN next_a = 1 THEN
            'tbl_src'
        WHEN next_b = 1 THEN
            'tbl_dst'
        ELSE
            'tbl_wrk'
        END from_tbl,
        CASE WHEN next_a = -1 THEN
            'tbl_src'
        WHEN next_b = -1 THEN
            'tbl_dst'
        ELSE
            'tbl_wrk'
        END to_tbl
    FROM 
        (SELECT
            coalesce(a, 0) - coalesce(lead(a) over (), 0) next_a,
            coalesce(b, 0) - coalesce(lead(b) over (), 0) next_b,
            coalesce(c, 0) - coalesce(lead(c) over (), 0) next_c
        FROM (SELECT array_length(a,1) a, array_length(b,1) b, array_length(c,1) c FROM hanoi(3)) f
        ) g WHERE next_a = 1 OR next_b = 1 OR next_c = 1
    LOOP
        EXECUTE 'CALL move(''' || r.from_tbl || ''',''' || r.to_tbl || ''')';
    END LOOP;
END $$;

「SELECT * FROM hanoi(3)」の結果をLOOPしつつ、window関数使って各行での増減を比較したり、CASE句を駆使して必要なテーブル名を取得したりして、「CALL move」を実行してます。

ちょっとお色直し

折角なので、物理ハノイの塔もお化粧しました。クリスマスツリーバージョン！

IMG_1990.JPG

実食！！！

アームの動きが遅いので界王拳(4倍)した動画がこちらです。

　
TAKE10でなんとか成功した・・・
それまでは、アームが急にぐるんぐるん回ったりご乱心で塔をなぎ倒す暴挙＼(^o^)／
殿中でござるぞ！
　
　

現場からは以上です。

まとめ

毎年よい記事を書こうと「起承転結」を意識して書き始めるのですが、今年も「起承転々承」な投げっぱなしジャーマンな記事になりました。
まぁ、久しぶりにWindows版のPostgreSQLに触って、Linux版との違いを体験できたのでヨシとしよう(Windows版だとpsqlのオプションの順番に厳しいとか)。

これからも楽しくPostgreSQLライフを送りたいと思います！

5
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
0