#!/usr/bin/perl -w
use strict;

our $board_size = 12;
our @left   = ("10","01","01","01");
our @right  = ("01","01","01","10");
our @top    = ("1","1","1");
our @bottom = ("0","0","0");

our $winctr = 0;

our @pieces = (
    ["10","0","10","1"], # A
    ["01","0","01","1"], # B
    ["01","1","01","0"], # C
    ["10","0","10","0"], # D
    ["10","1","10","1"], # E
    ["01","0","10","0"], # F
    ["10","1","10","0"], # G
    ["01","0","10","1"], # H
    ["10","1","01","1"], # I
    ["01","1","10","1"], # J
    ["10","1","01","0"], # K
    ["10","0","01","0"]  # L
);

sub my_pattern {
    my @board = @_;
    #my @flips = (1,1,1,1,1,1,1,1,1,1,1,1); # Everyone faces front (one)
    #my @flips = (1,2,1,1,2,1,1,2,1,1,2,1); # Middle row facing the back (one)
    my @flips = (2,2,2,2,2,2,2,2,2,2,2,2);  # Everyone faces back (one)
    #my @flips = (2,1,2,1,2,1,2,1,2,1,2,1); # 
    #my @flips = (2,1,1,1,2,1,1,2,1,1,1,2); # 
    #my @flips = (2,1,2,2,1,2,2,1,2,2,1,2); # Aisles are facing to the back 
    my $i;
    
    for ($i = 0;$i < $board_size;$i++) {
        if ($board[$i][1] != $flips[$i]) {
            return(0);
        }
    }
    
    return(1);
}
sub letter {
    my $i = $_[0];
    my $alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
    return(substr($alphabet,$i,1));
}

sub print_solution {
    my @b = @_;
    my $i;
    my $fctr = 0;
    my $fmt = "| %s%s | %s%s | %s%s |\n";
    
    for ($i = 0;$i < 12;$i++) {
        if ($b[$i][1] == 2) {
            $fctr++;
        }
    }
    
    # if (($fctr == 0) || ($fctr == $board_size) || my_pattern(@b)) { # Use this 'if' for ALL interlocking solutions
    # if ($fctr == 0) {                                               # Use this for the 'classic' solution of everyone facing front.
    if (($fctr == 0) || my_pattern(@b)) {                           # Use this 'if' for the real solution, and the custom pattern specified
        print STDERR "SOLUTION!\n";
        printf STDERR $fmt,letter($b[9][0]),($b[9][1] == 2 ? "f" : " "),letter($b[10][0]),($b[10][1] == 2 ? "f" : " "),letter($b[11][0]),($b[11][1] == 2 ? "f" : " ");
        printf STDERR $fmt,letter($b[6][0]),($b[6][1] == 2 ? "f" : " "),letter($b[7][0]),($b[7][1] == 2 ? "f" : " "),letter($b[8][0]),($b[8][1] == 2 ? "f" : " ");
        printf STDERR $fmt,letter($b[3][0]),($b[3][1] == 2 ? "f" : " "),letter($b[4][0]),($b[4][1] == 2 ? "f" : " "),letter($b[5][0]),($b[5][1] == 2 ? "f" : " ");
        printf STDERR $fmt,letter($b[0][0]),($b[0][1] == 2 ? "f" : " "),letter($b[1][0]),($b[1][1] == 2 ? "f" : " "),letter($b[2][0]),($b[2][1] == 2 ? "f" : " ");
        print STDERR "\n";
    }
    
    
    # Un-comment out the following lines if you want a list of all solutions to the board
    # It prints the solution number, how many of the rafters are 'flipped' (spun 180 degrees) in the solution,
    # and the 12 pieces in this order:
    #
    # 10  11  12
    #  7   8   9
    #  4   5   6
    #  1   2   3
    #
    #  Each 'flipped' piece is indicated with the suffix 'f'
    
    # print "$winctr,";
    
    #print "$fctr";
    #for ($i = 0;$i < 12;$i++) {
    #    print "," . letter($b[$i][0]) . ($b[$i][1] == 2 ? "f" : "");
    # }
    #print "\n";
    
    $winctr++;
}

sub complements {
    my $x = $_[0];
    my $y = $_[1];
    my $i;
    
    if (length($x) != length($y)) {
        print "Comparing [$x] and [$y]?  This should never happen!\n\n";
        exit;
    }
    
    for ($i = 0;$i < length($x);$i++) {
        if (substr($x,$i,1) eq substr($y,$i,1)) {
            return(0);
        }
    }
    
    return(1);
}

sub side_compare {
    my $x = $_[0];
    my $y = $_[1];
    my $i;
    
    if (length($x) != length($y)) {
        print "Comparing [$x] and [$y]?  This should never happen!\n\n";
        exit;
    }
    
    for ($i = 0;$i < length($x);$i++) {
        if (substr($x,$i,1) ne substr($y,$i,1)) {
            return(0);
        }
    }
    
    return(1);
}

sub get_edges {
    my @args = @_;
    my $loc;
    my @board;
    my @edges = ("00","00","00","00");
    my $piece;
    
    # Depending on location, 2, 3, or 4 edges are tested.  In order: Left, Bottom, Right, Top
    
    $loc   = shift(@args);
    @board = @args;
    
    #  Does $piece 'fit' in location $loc?
    if ($loc == 0) {
        # Left
        $edges[0] = $left[0];
        
        # Bottom
        $edges[1] = $bottom[0];
        
        # Right
        # Not used
        
        # Top
        # Not used
    }
    elsif ($loc == 1) {
        # Left
        $piece = $board[0][0]; # Piece to the left
        $edges[0] = ($board[0][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $edges[1] = $bottom[1];
        
        # Right
        # Not used
        
        # Top
        # Not used
    }
    elsif ($loc == 2) {
        # Left
        $piece = $board[1][0]; # Piece to the left
        $edges[0] = ($board[1][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $edges[1] = $bottom[2];
        
        # Right
        $edges[2] = $right[0];
        
        # Top
        # Not used
    }
    elsif ($loc == 3) {
        # Left
        $edges[0] = $left[1];
        
        # Bottom
        $piece = $board[0][0]; # Piece below
        $edges[1] = ($board[0][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        # Not used
        
        # Top
        # Not used
    }
    elsif ($loc == 4) {
        # Left
        $piece = $board[3][0]; # Piece to the left
        $edges[0] = ($board[3][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $piece = $board[1][0]; # Piece below
        $edges[1] = ($board[1][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        # Not used
        
        # Top
        # Not used
    }
    elsif ($loc == 5) {
        # Left
        $piece = $board[4][0]; # Piece to the left
        $edges[0] = ($board[4][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $piece = $board[2][0]; # Piece below
        $edges[1] = ($board[2][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        $edges[2] = $right[1];
        
        # Top
        # Not used
    }
    elsif ($loc == 6) {
        # Left
        $edges[0] = $left[2];
        
        # Bottom
        $piece = $board[3][0]; # Piece below
        $edges[1] = ($board[3][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        # Not used
        
        # Top
        # Not used
    }
    elsif ($loc == 7) {
        # Left
        $piece = $board[6][0]; # Piece to the left
        $edges[0] = ($board[6][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $piece = $board[4][0]; # Piece below
        $edges[1] = ($board[4][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        # Not used
        
        # Top
        # Not used
    }
    elsif ($loc == 8) {
        # Left
        $piece = $board[7][0]; # Piece to the left
        $edges[0] = ($board[7][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $piece = $board[5][0]; # Piece below
        $edges[1] = ($board[5][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        $edges[2] = $right[2];
        
        # Top
        # Not used
    }
    elsif ($loc == 9) {
        # Left
        $edges[0] = $left[3];
        
        # Bottom
        $piece = $board[6][0]; # Piece below
        $edges[1] = ($board[6][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        # Not used
        
        # Top
        $edges[3] = $top[0];
    }
    elsif ($loc == 10) {
        # Left
        $piece = $board[9][0]; # Piece to the left
        $edges[0] = ($board[9][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $piece = $board[7][0]; # Piece below
        $edges[1] = ($board[7][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        # Not used
        
        # Top
        $edges[3] = $top[1];
    }
    elsif ($loc == 11) {
        # Left
        $piece = $board[10][0]; # Piece to the left
        $edges[0] = ($board[10][1] == 2 ? $pieces[$piece][2] : $pieces[$piece][0]);
        
        # Bottom
        $piece = $board[8][0]; # Piece below
        $edges[1] = ($board[8][1] == 2 ? $pieces[$piece][3] : $pieces[$piece][1]);
        
        # Right
        $edges[2] = $right[3];
        
        # Top
        $edges[3] = $top[2];
    }
    
    return(@edges);
}

sub fits {
    my @args = @_;
    my $loc;
    my $piece;
    my @board;
    my @r_sides; # Regular sides
    my @f_sides; # Flipped sides
    my ($i, $j);
    my @edges;
    my $flip;
    
    $loc   = shift(@args);
    $piece = shift(@args);
    $flip  = shift(@args);
    @board = @args;
    
    for ($i = 0;$i < 4;$i++) {
        $r_sides[$i] = $pieces[$piece][$i];
    }
    
    for ($i = 0;$i < 4;$i++) {
        $j = ($i + 2) % 4;
        $f_sides[$j] = $pieces[$piece][$i];
    }
    
    
    @edges = get_edges($loc,@board); # Array of edges to check.   In order: Left, Bottom, Right, Top
    
    #  Does $piece 'fit' in location $loc?
    if ($loc == 0) {
        # check left and bottom
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 1) {
        # check left and bottom
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 2) {        
        # check left and bottom and right
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]) && side_compare($edges[2],$r_sides[0]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]) && side_compare($edges[2],$f_sides[0]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 3) {
        # check left and bottom
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 4) {        
        # check left and bottom
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 5) {
        # check left and bottom and right
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]) && side_compare($edges[2],$right[1]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]) && side_compare($edges[2],$right[1]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 6) {
        # check left and bottom
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 7) {
        # check left and bottom
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 8) {
        # check left and bottom and right
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]) && side_compare($edges[2],$right[2]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]) && side_compare($edges[2],$right[2]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 9) {
        # check left and bottom and top
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]) && complements($edges[3],$r_sides[1]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]) && complements($edges[3],$f_sides[1]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 10) {
        # check left and bottom and top
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]) && complements($edges[3],$r_sides[1]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]) && complements($edges[3],$f_sides[1]))) {
            return(2);
        }
        
        return(0);
    }
    elsif ($loc == 11) {
        # check all sides
        if (($flip == 0) && (side_compare($edges[0],$r_sides[2]) && complements($edges[1],$r_sides[3]) && complements($edges[3],$r_sides[1]) && side_compare($edges[2],$r_sides[0]))) {
            return(1);
        }
        
        if (($flip == 1) && (side_compare($edges[0],$f_sides[2]) && complements($edges[1],$f_sides[3]) && complements($edges[3],$f_sides[1]) && side_compare($edges[2],$f_sides[0]))) {
            return(2);
        }
        
        return(0);
    }
    else {
        print "This should not happen!!\n\n";
        exit;
    }
}

sub solve {
    my @args = @_;
    my $j;
    my @board;
    my @in_use;
    my $i;
    my $piece;
    my $check_if_fits;
    my $k;
    
    $j = shift(@args);  # Position on board
    @board = @args;
    
    # If j = 12, we've fit all the pieces!
    if ($j == 12) {
        print_solution(@board);
        return;
    }
    
    # Account for all pieces already in use
    for ($i = 0;$i < $board_size;$i++) {
        $in_use[$i] = 0;
    }
    
    for ($i = 0;$i < $j;$i++) {
        $piece = $board[$i][0];
        if ($piece < 0) {
            next;
        }
        $in_use[$piece] = 1;
    }
    
    # Now iterate through the unused pieces to look for a fit
    for ($i = 0;$i < $board_size;$i++) {
        if ($in_use[$i] == 0) {
            for ($k = 0;$k < 2;$k++) {
                $check_if_fits = fits($j,$i,$k,@board); # 1 = Regular orientation, 2 = Flipped orientation
                if ($check_if_fits > 0) {
                    $board[$j][0] = $i;
                    $board[$j][1] = $check_if_fits;
                    
                    solve($j + 1,@board);
                }
            }
        }
    }
}

my @board;
my $i;

for ($i = 0;$i < $board_size;$i++) {
    $board[$i] = [-1,0]; # Each element records a puzzle piece, and an orientation
}

solve(0,@board);

# print STDERR "\nThere were $winctr boards that fit when pieces could be flipped.\n\n";