% Find all the solutions for the "cubetto" problem
% see http://stacktrace.it/articoli/2008/02/il-cubetto/
%
% (c) 2008 by Daniele Varrazzo <daniele dot varrazzo at gmail dot com>
%
% This program is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
% 
% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
% 
% You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

%
% Disclaimer: this is my first Erlang program...
%

-module(cubetto).
-export([main/0]).

main() ->
    Pieces = parse_cubetto("cubetto-pezzi.txt"),
    Game = cubetto_game(),
    Sol = [ [ {0,[{pos,0},{rotate,y,0},ident]} | Sol] ||
        Sol <- find_solutions(Game,
            {Pieces, get_face(Pieces, 0), [1,2,3,4,5]})],
    lists:foreach(fun(S) -> print_sol(Pieces, S) end, Sol),
    io:format("Solutions: ~w~n", [length(Sol)]).


%
% Shape file parsing
%

parse_cubetto(FileName) ->
    {ok, File} = file:open(FileName, read),

    Row = io:get_line(File, ""),
    parse_cubetto(File, Row, [], 0),

    Faces = receive_faces(lists:seq(0,5), []),
    dict:from_list([ {Idx, sets:from_list(Face)} || {Idx, Face} <- Faces]).

parse_cubetto(_File, eof, Acc, Num) ->
    spawn(fun parse_face/0) ! {self(), {Num, Acc}};

parse_cubetto(File, "\n", []=Acc, Num) ->   % ignore consecutive eols
    Row = io:get_line(File, ""),
    parse_cubetto(File, Row, Acc, Num);

parse_cubetto(File, "\n", Acc, Num) ->
    spawn(fun parse_face/0) ! {self(), {Num, Acc}},
    Row = io:get_line(File, ""),
    parse_cubetto(File, Row, [], Num+1);

parse_cubetto(File, Row, Acc, Num) ->
    NewRow = io:get_line(File, ""),
    parse_cubetto(File, NewRow, [Row|Acc], Num).

parse_face() ->
    receive
        {Pid, {Num, Face}} ->
            Pid ! {Num, parse_face_3d(lists:reverse(Face))}
    end.

receive_faces([], Acc) ->
    Acc;

receive_faces(Faces, Acc) ->
    receive
        {Num, Face} ->
            receive_faces(Faces -- [Num], [{Num, Face}|Acc])
    end.


side_ord() -> [ -5, -3, -1, 1, 3, 5].

plane_to_space(X, Y) -> {X, 5, Y}.

parse_face_3d({Row, Y}) when Y == -5; Y == 5 ->
    row_to_points(Row, side_ord(), Y);

parse_face_3d({[C1,_,_,_,_,C2,$\n], Y}) ->
    row_to_points([C1,C2], [-5,5], Y);

parse_face_3d(Face) ->
    lists:flatmap(fun parse_face_3d/1, lists:zip(Face, side_ord())).

row_to_points(Row, Xs, Z) ->
    [ plane_to_space(X, Z) || {X, C} <- lists:zip(Xs,
        [ C || C <- Row, ((C =:= $.) or (C =:= $#)) ]), C =:= $# ].


%
% Game solution
%

-record(game, {
    generate_moves,
    change_state,
    is_final_state}).

% Find all the solutions of a recursive game
find_solutions(#game{}=Game, InitialState) ->
    Solution = [],
    Solutions = [],
    find_solutions(Game, InitialState, Solution, Solutions).

find_solutions(#game{}=Game, State, Sol, Sols) ->
    Moves = (Game#game.generate_moves)(State),
    find_solutions(Game, State, Moves, Sol, Sols).

find_solutions(#game{}, _State, [], _Sol, Sols) ->
    Sols;

find_solutions(#game{}=Game, State, [Move|Moves], Sol, Sols) ->
    case (Game#game.change_state)(State, Move) of
        invalid ->
            find_solutions(Game, State, Moves, Sol, Sols);
        NewState ->
            NewSols = case (Game#game.is_final_state)(NewState) of
                true ->
                    [lists:reverse([Move|Sol]) | Sols];
                false ->
                    find_solutions(Game, NewState, [Move|Sol], Sols)
            end,
            find_solutions(Game, State, Moves, Sol, NewSols)
    end.

cubetto_game() ->
    #game{
        generate_moves = fun generate_moves/1,
        change_state = fun change_state/2,
        is_final_state = fun is_final_state/1
    }.

generate_moves({_Pieces, _World, Left}) ->
    [ {Piece, Xform }
        ||  Piece <- Left,
            Xform <- generate_xforms(6 - length(Left)) ].

generate_xforms() ->
    [ [{rotate, y, Ang}, Xform]
        ||  Ang <- [0, 90, 180, 270],
            Xform <- [ ident, {flip, x} ]  ].

generate_xforms(Num) ->
    [ [{pos, Num} | Xforms] || Xforms <- generate_xforms() ].


get_face(Pieces, Idx) -> dict:fetch(Idx, Pieces).

change_state({Pieces, World, Left}, {Piece, Xforms}) ->
    MovedPiece = dot(
        mmult([ xform(Xform) || Xform <- Xforms ]),
        get_face(Pieces, Piece)),
    case sets:size(sets:intersection(World, MovedPiece)) of
        0 -> {Pieces, sets:union(World,  MovedPiece), Left -- [Piece]};
        _ -> invalid
    end.

is_final_state({_Pieces, _World, []})       -> true;
is_final_state({_Pieces, _World, _Left})    -> false.


%
% Geometrical transformations
%

dot({X1, X2, X3}, {Y1, Y2, Y3}) when is_integer(X1), is_integer(Y1) ->
    X1 * Y1 + X2 * Y2 + X3 * Y3;
dot({{E1X, E1Y, E1Z}, {E2X, E2Y, E2Z}, {E3X, E3Y, E3Z}}, {_,_,_}=V) ->
    {   dot({E1X, E2X, E3X}, V),
        dot({E1Y, E2Y, E3Y}, V),
        dot({E1Z, E2Z, E3Z}, V)};
dot(Base, Points) ->
    sets:from_list([ dot(Base, Point) || Point <- sets:to_list(Points) ]).

mmult([M1,M2|Tail]) ->
    mmult([mmult(M1,M2)|Tail]);
mmult([M]) ->
    M.
mmult(M,{{_,_,_}=V1,{_,_,_}=V2,{_,_,_}=V3}) ->
    {dot(M, V1), dot(M, V2), dot(M, V3)}.

xform(ident) -> {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

xform({flip, x}) -> {{-1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

xform({rotate, _Axis, 0}) -> xform(ident);
xform({rotate, x, 90}) -> {{1, 0, 0}, {0, 0, 1}, {0, -1, 0}};
xform({rotate, y, 90}) -> {{0, 0, -1}, {0, 1, 0}, {1, 0, 0}};
xform({rotate, z, 90}) -> {{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}};

xform({rotate, Axis, 180}) ->
    mmult(xform({rotate, Axis, 90}), xform({rotate, Axis, 90}));

xform({rotate, Axis, 270}) ->
    mmult(xform({rotate, Axis, 180}), xform({rotate, Axis, 90}));

xform({pos, 0}) -> xform(ident);
xform({pos, 1}) -> xform({rotate, z, 270});
xform({pos, 2}) -> xform({rotate, z, 180});
xform({pos, 3}) -> xform({rotate, z, 90});
xform({pos, 4}) -> xform({rotate, x, 90});
xform({pos, 5}) -> xform({rotate, x, 270}).


%
% Solutions output.
%

print_sol(Pieces, Moves) ->
    [P0,P1,P2,P3,P4,P5] = [ piece_to_ascii(Pieces, Move) || Move <- Moves ],
    print_faces([P5]),
    print_faces([P0,P1,P2,P3]),
    print_faces([P4]),
    io:format("~n").

print_faces([[Row|Tail]]) ->
    io:format("~s~n", [Row]),
    print_faces([Tail]);

print_faces([[]]) ->
    io:format("~n");

print_faces([P1,P2|Tail]) ->
    P = [ R1 ++ " " ++ R2 || {R1, R2} <- lists:zip(P1, P2) ],
    print_faces([P|Tail]).


point_to_char(Face, Point) ->
    case sets:is_element(Point, Face) of
        false -> $\ ;
        true  -> $#
    end.

piece_to_ascii(Pieces, {Idx, [{pos,_}, Rotation, Flip]}) ->
    Face = dot(mmult([xform(Rotation), xform(Flip)]),
        sets:union(get_face(Pieces, Idx), fill_hole(Flip))),
    lists:reverse([ [
        point_to_char(Face, plane_to_space(X, Y))
            || X <- side_ord() ]
            || Y <- lists:reverse(side_ord()) ]).

fill_hole(ident) ->
    sets:from_list([ plane_to_space(X, Y) ||
        X <- [-3, -1, 1, 3], Y <- [-3, -1, 1, 3],
        ((abs(X) =:= 3) or (abs(Y) =:= 3)) ]);

fill_hole({flip,x}) ->
    sets:from_list([ plane_to_space(X, Y) ||
        X <- [-3, -1, 1, 3], Y <- [-3, -1, 1, 3] ]).