RiverCrossing.cpp

// g++ -std=c++11 RiverCrossing.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

enum Turn { L = 0, R = 1, };
enum Kind { S = 0, T = 1, };

typedef array<int,2> Tuple;      // {{ num_soldiers, num_titans }}
typedef array<Tuple,2> Tuples;   // {{ left_side_status, right_side_status }}
typedef pair<int, Tuples> State; // { which_turn, states }
typedef vector<State> Steps;

ostream& operator << (ostream& stream, const Tuple& tuple) {
    static const char *const repl = "ST";
    for (int i = S; i <= T; ++i) for (int j = tuple[i]; 0 < j; --j) stream << repl[i];
    return stream;
}

ostream& operator << (ostream& stream, const Tuples& tuples) {
    return stream << tuples[L] << '/' << tuples[R];
}

class Solver
{
    vector<Steps> _solutions;
public:
    const vector<Steps>& solutions() const
    {
        return _solutions;
    }
    Solver(const Tuples& initial)
    {
        queue<Steps> q;
        q.push(Steps{{L, initial}});
        while (!q.empty())
        {
            Steps steps(q.front());
            q.pop();
            State& state = steps.back();
            Tuples& ts = state.second;
            int i = state.first;
            if (ts[L][S] == 0 && ts[L][T] == 0) {
                _solutions.push_back(steps); // found a solution
                continue;
            }
            if ((0 < ts[L][S] && ts[L][S] < ts[L][T]) ||
                (0 < ts[R][S] && ts[R][S] < ts[R][T]))
            {
                continue; // soldier(s) died
            }
            for (const Tuple pat: vector<Tuple>{{{2,0}},{{1,0}},{{1,1}},{{0,1}},{{0,2}}}) {
                if (pat[S] <= ts[i][S] && pat[T] <= ts[i][T])
                {
                    int j = i ^ R;
                    Tuples us;
                    if (i) {
                        us = {{
                                {{ts[j][S] + pat[S], ts[j][T] + pat[T]}},
                                {{ts[i][S] - pat[S], ts[i][T] - pat[T]}}
                        }};
                    }
                    else {
                        us = {{
                                {{ts[i][S] - pat[S], ts[i][T] - pat[T]}},
                                {{ts[j][S] + pat[S], ts[j][T] + pat[T]}}
                        }};
                    }
                    State state{j, us};
                    if (steps.end() == find(steps.begin(), steps.end(), state)) {
                        Steps new_steps(steps);
                        new_steps.push_back(state);
                        q.push(new_steps);
                    }
                }
            }
        }
    }
};

int main()
{
    Solver solver({{{{3,3}},{{0,0}}}});
    int i = 0;
    for (Steps steps: solver.solutions()) {
        cout << "解答" << ++i << endl;
        for (State step: steps) {
            cout << step.second << endl;
        }
    }
}

softs_and_hards.py

'''
その昔、剛国と柔国という2つの国が隣り合っていた。
剛国の国民はとても気性が荒い事で有名だった。
特に柔国の人間と一緒に居ると必ず喧嘩になってしまった。
あるとき剛国の僧3人と柔国の僧3人の計6人が天竺を目指して旅を始めた。
いずれも名のある仏教徒である、剛国民と柔国民が一緒でも仲良くやっていた。
しかし剛国僧の人数の方が多くなるといつまた喧嘩になるかわからない。
柔国僧が多いかまたは同じ人数なら喧嘩の心配は無い。
とある川にたどり着いた。
渡りたいのだが、例によって小さな2人乗りの舟が一艘あるだけである。
柔国僧は全員舟を漕ぐ事が出来たが、剛国僧の方は舟を漕げるのが1人だけしかいなかった。
あとの2人の剛国僧は残念ながら誰かの漕ぐ舟に乗せてもらうしかない。
全員が喧嘩せずに向こう岸に渡る為にはどんな手順が必要か?
'''

from collections import deque

def checkio():
    xs = (0, ((3,2,1), (0,0,0)))
    q = deque([(xs, [xs])])
    solsutions = set()
    while q:
        xs, steps = q.popleft()
        i, sides = xs
        j = i^1
        if sides == ((0,0,0), (3,2,1)):
            solsutions.add(tuple(sides for i, sides in steps))
            continue
        if 0 < sides[i][0] < sum(sides[i][1:]) or 0 < sides[j][0] < sum(sides[j][1:]):
            continue
        for d in ((2,0,0), (1,0,0), (1,1,0), (1,0,1), (0,1,1), (0,0,1)):
            if d[0] <= sides[i][0] and d[1] <= sides[i][1] and d[2] <= sides[i][2]:
                xs = (j, ((sides[i][0]-d[0], sides[i][1]-d[1], sides[i][2]-d[2]), (sides[j][0]+d[0], sides[j][1]+d[1], sides[j][2]+d[2])))
                if i:
                    xs = (j, (xs[1][1], xs[1][0]))
                if xs not in steps:
                    q.append((xs, steps+[(xs)]))
    return solsutions

print(checkio())

tiger_and_sheep_and_vegetable.py

'''
虎と羊を連れた人が野菜を運んでいた。
ある所で川を渡る必要が生じた。
舟が一艘あったがとても小さい。
その人が乗るとあとは虎か羊か野菜の内のいずれか一つしか乗せられない。
しかし人が居ない所で虎と羊を一緒にすると虎は羊を食べてしまう。
同様に人が居ないと羊は野菜を食べてしまう。
全部が無事に向こう岸に渡るにはどのような手順が必要か?
'''

from collections import deque

def checkio():
    xs = (0, (set(['T','S','V']), set()))
    q = deque([(xs, [(xs)])])
    solsutions = []
    while q:
        xs, steps = q.popleft();
        i, sides = xs
        j = i^1
        if not sides[0]:
            solsutions.append([(list(step[0]), list(step[1])) for j, step in steps])
            continue
        if ('T' in sides[j] and 'S' in sides[j]) or ('S' in sides[j] and 'V' in sides[j]):
            continue
        for x in sides[i]:
            xs = (j, (sides[i].difference([x]), sides[j].union([x])))
            if i:
                xs = (j, (xs[1][1],xs[1][0]))
            if xs not in steps:
                q.append((xs, steps+[xs]))
        xs = (j,sides)
        if xs not in steps:
            q.append((xs, steps+[xs]))
    return solsutions

print(checkio())