オフィス内の席替えで「現在の座席番号、移動先の座席番号、名前」のデータから待ったりパラレルに動いたりする段取りを計算

moving-order.pl

#!/usr/bin/env perl
use strict;
use warnings;

my %map;    # 座席表
my @lines;  # 順に移動する列を保持する

{
    # データ読み込み
    while (<DATA>) {
        chomp;
        my ($now, $to, $name) = split;
        my $person = +{
            name => $name,
            now  => $now,   # いまいる席番号
            to   => $to,    # 行きたい席番号
        };
        $map{$now} = $person;
    }

    # 移動の連鎖を作る
    for my $person (values %map) {
        # 座席表にいる人を片っ端から処理 こまかいことは make_chain() の中で
        make_chain($person);
    }

    # 結果表示
    for my $first (@lines) {
        my $person = $first;
        if ($person->{need_temp}) {
            # ループになってる列。はじめの人はどこかに退避する必要がある
            print '(循環) ';
        }
        print '[', $person->{to}, ']';
        while ($person) {
            print ' ← ', $person->{name}, '[', $person->{now}, ']';
            $person = $person->{next};
        }
        print "\n";
    }
}

sub make_chain
{
    my ($person, $start) = @_;
    return if $person->{resolved}++;  # もう処理した人

    my $blocker = $map{$person->{to}};  # 移動先にいる人
    if (!$blocker) {
        # 移動先が空いてるなら連鎖の最初の人になれる
        push @lines, $person;
        return;
    }
    if ($start && $blocker->{name} eq $start->{name}) {
        # 移動先の人が一巡してしまった。ループなので仕方なく連鎖の最初の人にする
        $person->{need_temp} = 1;  # ただし要退避
        push @lines, $person;
        return;
    }

    # 自分は移動先にいる人の次に動くね
    $blocker->{next} = $person;

    # 移動先にいる人について繰り返す
    make_chain($blocker, $start || $person);
}

__DATA__
99  109 中村玄道
101 111 尾形俊太郎
103 113 山崎烝
105 107 青柳牧太夫
84  114 安藤勇次郎
86  94  川島勝司
88  96  島田魁
90  97  藤堂平助
83  93  武田観柳斎
85  91  原田左之助
87  103 斎藤一
89  105 新見錦
68  69  芦屋昇
70  95  沖田総司
72  88  近藤芳助
74  90  阿部十郎
67  99  荒木田左馬之助
69  84  松原忠司
71  101 河合耆三郎
73  86  平間重助
52  71  志村武蔵
54  73  野口健司
51  52  芹沢鴨
53  54  永倉新八
55  56  御倉伊勢武
57  58  大石鍬次郎
36  28  中西昇
38  26  奥沢栄助
40  39  林信太郎
42  22  矢田賢之助
37  23  久米部正親
39  27  佐伯又三郎
41  25  谷三十郎
24  51  岸島芳太郎
26  53  松永主計
28  55  土方歳三
23  42  中村小三郎
25  38  伊東甲子太郎
27  36  神崎一二三
110 92  伊藤鉄五郎
107 78  葛山武八郎
109 89  橋本皆助
111 72  沼尻小文吾
113 87  安富才助
92  41  富山弥兵衛
94  74  前野五郎
98  40  近藤勇
91  64  大野右仲
93  21  尾関弥四郎
95  24  山南敬助
97  46  服部武雄
76  60  藤太郎
78  62  相馬主計
80  66  鈴木三樹三郎
82  83  池田小三郎
75  59  茨木司
77  61  大谷勇雄
79  63  篠原泰之進
81  65  近藤隼雄
60  37  村上清
64  48  加納鷲雄
66  50  川村隼人
59  44  平山五郎
61  76  安藤早太郎
63  80  近藤周平
65  82  小原幸造
44  75  酒井兵庫
46  77  吉村貫一郎
48  79  楠小十郎
50  81  井上源三郎
56  110 尾関政一郎
58  108 新井忠雄