package Snake;

use strict;
use Data::Dumper;
use Clone qw(clone);

my $counter = 0;

sub output2 {
	my %hash = @{ clone(\@_) };

	system "cls";
	print $Snake::counter."\n";

	#output top
	print "            #===+===+===#\n";
	for(my $y = -4; $y <= 4; $y++) {
		print "            |";
		for(my $x = -4; $x <= 4; $x++) {
			my $z = 4;
			print $hash{$x}{$y}{$z};
			if($x == 4) {
				print "|";
			} elsif(($x-1) % 3 == 0) {
				print ":";
			}
		}
		print "\n";
		if($y == 4) {
			print "#===+===+===#===+===+===#===+===+===#\n";
		} elsif(($y-1) % 3 == 0) {
			print "            #---+---+---#\n";
		}
	}

	for(my $z = 4; $z >= -4; $z--) {
		print "|";

		# output left
		for(my $y = -4; $y <= 4; $y++) {
			my $x = -4;
			print $hash{$x}{$y}{$z};
			if($y == 4) {
				print "|";
			} elsif(($y-1) % 3 == 0) {
				print ":" if(($y-1) % 3 == 0);
			}
		}

		# output front
		for(my $x = -4; $x <= 4; $x++) {
			my $y = 4;
			print $hash{$x}{$y}{$z};
			if($x == 4) {
				print "|";
			} elsif(($x-1) % 3 == 0) {
				print ":";
			}
		}

		# output right
		for(my $y = 4; $y >= -4; $y--) {
			my $x = 4;
			print $hash{$x}{$y}{$z};
			if($y == -4) {
				print "|";
			} elsif(($y+1) % 3 == 0) {
				print ":";
			}
		}
		print "\n";
		if($z == -4) {
			print "#===+===+===#===+===+===#===+===+===#\n";
		} elsif(($z+1) % 3 == 0) {
			print "#---+---+---#---+---+---#---+---+---#\n";
		}
	}

	# output bottom
	for(my $y = 4; $y >= -4; $y--) {
		print "            |";
		for(my $x = -4; $x <= 4; $x++) {
			my $z = -4;
			print $hash{$x}{$y}{$z};
			if($x == 4) {
				print "|";
			} elsif(($x-1) % 3 == 0) {
				print ":";
			}
		}
		print "\n";
		if($y == -4) {
			print "            #===+===+===#\n";
		} elsif(($y+1) % 3 == 0) {
			print "            #---+---+---#\n";
		}
	}

	# output back (upside-down)
	for(my $z = -4; $z <= 4; $z++) {
		print "            |";
		for(my $x = -4; $x <= 4; $x++) {
			my $y = -4;
			print $hash{$x}{$y}{$z};
			if($x == 4) {
				print "|";
			} elsif(($x-1) % 3 == 0) {
				print ":";
			}
		}
		print "\n";
		if($z == 4) {
			print "            #===+===+===#\n";
		} elsif(($z-1) % 3 == 0) {
			print "            #---+---+---#\n";
		}
	}
}

sub rotateX {
	my $in = shift;
	my ($x, $y, $z) = @{$in};
	return [$x, -$z, $y];
}

sub rotateY {
	my $in = shift;
	my ($x, $y, $z) = @{$in};
	return [-$z, $y, $x];
}

sub rotateZ {
	my $in = shift;
	my ($x, $y, $z) = @{$in};
	return [-$y, $x, $z];
}

sub rotateReal {
	my $method = shift;
	return rotateX(@_) if $method eq "X";
	return rotateY(@_) if $method eq "Y";
	return rotateZ(@_);
}

sub rotate {
	my $in     = shift;
	my $method = shift;
	my $out    = {};

	# move central point
	${$out}{"location"} = rotateReal $method, ${$in}{"location"};

	# move all points
	foreach my $x (-1, 0, 1) {
		foreach my $y (-1, 0, 1) {
			foreach my $z (-1, 0, 1) {
				my @that = @{ rotateReal($method, [$x, $y, $z]) };
				${$out}{"configuration"}{ $that[0] }{ $that[1] }{ $that[2] } = ${$in}{"configuration"}{$x}{$y}{$z};
			}
		}
	}
	return $out;
}

sub commit {
	my $shaded = shift;
	my $cubie  = shift;
	foreach my $x (-1, 0, 1) {
		foreach my $y (-1, 0, 1) {
			foreach my $z (-1, 0, 1) {
				# TODO: check that the space is not occupied
				${$shaded}{$x + ${$cubie}{"location"}[0]}{$y + ${$cubie}{"location"}[1]}{$z + ${$cubie}{"location"}[2]} = ${$cubie}{"configuration"}{$x}{$y}{$z};
			}
		}
	}
	return $shaded;
}

# blank out all the blocks where this cubie previously resided
sub uncommit {
	my $shaded = shift;
	my $cubie = shift;
	foreach my $x (-1, 0, 1) {
		foreach my $y (-1, 0, 1) {
			foreach my $z (-1, 0, 1) {
				${$shaded}{$x + ${$cubie}{"location"}[0]}{$y + ${$cubie}{"location"}[1]}{$z + ${$cubie}{"location"}[2]} = " ";
			}
		}
	}
	return $shaded;
}

# compare two rotations to see if they are equivalent
# return 1 if they are the same, 0 if not
sub thesame {
	my $one = shift;
	my $two = shift;

	# if they aren't in the same physical location then they cannot be the same
	return 0 if !(
		${$one}{"location"}[0] == ${$two}{"location"}[0]
		&& ${$one}{"location"}[1] == ${$two}{"location"}[1]
		&& ${$one}{"location"}[2] == ${$two}{"location"}[2]
	);

	# if they are in the same physical location then we have to compare pixel for pixel
	foreach my $x (-1, 0, 1) {
		foreach my $y (-1, 0, 1) {
			foreach my $z (-1, 0, 1) {
				return 0 if ${$one}{"configuration"}{$x}{$y}{$z} ne ${$two}{"configuration"}{$x}{$y}{$z};
			}
		}
	}
	return 1;
}

# checks if the first rotation appears in the list of other rotations
sub isin {
	my $this   = shift;
	my $others = shift;
	foreach my $that (@{$others}) {
		return 1 if thesame($this, $that);
	}
	return 0;
}

# list all the cubic components.
# These are the canonical locations of these components, but by applying
# rotations, all others can be generated.
# we just provide the central point
my %types = (
	"C" => [0, 0, 0],
	"F" => [0, 0, 3],
	"E" => [3, 0, 3],
	"V" => [3, 3, 3],
);

# start with canonical locations only
my %cubies = (
	# 1 centre
	"C" => {
		"midd" => [],
	},

	# 6 faces
	# all blocks are on the top side of the cube
	"F" => {
		"flat" => [[-1,0,1],[0,0,1],[1,0,1]],
		"ben1" => [[0,1,1],[0,0,1],[1,0,1]],
		"ben2" => [[0,1,1],[0,0,1],[1,0,1]],
		"ben3" => [[0,1,1],[0,0,1],[1,0,1]],
		"ben4" => [[0,1,1],[0,0,1],[1,0,1]],
		"ben5" => [[0,1,1],[0,0,1],[1,0,1]],
	},

	# 12 edges
	"E" => {
		"barr" => [[0,1,1],[0,0,1],[0,-1,1],[1,1,0],[1,0,0],[1,0,-1]],
		"fred" => [[1,0,-1],[1,0,0],[1,-1,0],[0,1,1],[0,0,1],[-1,0,1]],
		"geof" => [[1,0,-1],[1,0,0],[1,-1,0],[-1,0,1],[0,0,1],[0,-1,1]],
		"wilm" => [[0,1,1],[0,0,1],[1,0,1],[1,0,0],[1,0,-1]],
		"albe" => [[0,1,1],[0,0,1],[1,0,1],[1,0,0],[1,0,-1]],
		"stev" => [[0,1,1],[0,0,1],[1,0,1],[1,0,0],[1,0,-1]],
		"alas" => [[0,1,1],[0,0,1],[1,0,1],[1,0,0],[1,0,-1]],
		"wilf" => [[1,1,0],[1,0,0],[1,0,1],[0,0,1],[0,-1,1]],
		"mike" => [[1,1,0],[1,0,0],[1,0,1],[0,0,1],[0,-1,1]],
		"sall" => [[1,0,-1],[1,0,0],[1,0,1],[0,0,1],[0,-1,1]],
		"arik" => [[1,0,-1],[1,0,0],[1,0,1],[0,0,1],[-1,0,1]],
		"tony" => [[0,1,1],[0,0,1],[0,-1,1]],
	},

	# 8 vertices
	"V" => {
		"hort" => [[-1,0,1],[0,0,1],[0,-1,1],[0,1,-1],[0,1,0],[1,1,0],[1,0,0],[1,-1,0]],
		"chul" => [[-1,1,0],[0,1,0],[0,1,-1],[1,0,-1],[1,0,0],[1,-1,0]],
		"eddi" => [[0,1,-1],[0,1,0],[1,1,0],[1,0,0],[1,-1,0]],
		"susi" => [[-1,1,0],[0,1,0],[1,1,0],[1,0,0],[1,0,-1]],
		"debo" => [[-1,0,1],[0,0,1],[0,-1,1]],
		"mark" => [[-1,0,1],[0,0,1],[0,-1,1]],
		"haze" => [[0,0,1],[0,-1,1]],
		"yvet" => [[0,0,1],[0,-1,1]],
	},
);

my %all = ();

# generate all possible rotated positions of all cubies
foreach my $type (sort keys %cubies) {
	foreach my $name (sort keys %{$cubies{$type}}) {

		$all{$name} = {
			"rotations" => [],
			"used"      => "no"
		};

		# generate an initial possibility
		my %rotation = ();

		# @{$types{$type}} contains the (x, y, z) where this type of block is moored
		$rotation{"location"} = \@{$types{$type}};

		# grey in the whole volume
		for(my $x = -1; $x <= 1; $x++) {
			for(my $y = -1; $y <= 1; $y++) {
				for(my $z = -1; $z <= 1; $z++) {
					$rotation{"configuration"}{$x}{$y}{$z} = ".";
				}
			}
		}

		# blacken the selected areas
		foreach my $point (@{$cubies{$type}{$name}}) {
			$rotation{"configuration"}{ ${$point}[0] }{ ${$point}[1] }{ ${$point}[2] } = "#";
		}

		push @{$all{$name}{"rotations"}}, \%rotation;

		# now apply some rotations
		# Apply all rotations to all existing configurations to get more
		# each rotation always generates something different from all the others
		my @in = ();

		my $moreFound = 1;
		while ($moreFound) {
			$moreFound = 0;
			foreach my $axis ("X", "Y", "Z") {
				@in = @{ clone(\@{$all{$name}{"rotations"}}) };
				foreach my $rotation (@in) {
					my $out = rotate($rotation, $axis);
					if(!isin($out, \@{$all{$name}{"rotations"}})) {
						push @{$all{$name}{"rotations"}}, $out;
						$moreFound = 1;
					}
				}
			}
		}

	}

}

my $shaded = {};
for(my $x = -4; $x <=  4; $x++) {
	for(my $y = -4; $y <=  4; $y++) {
		for(my $z = -4; $z <=  4; $z++) {
			${$shaded}{$x}{$y}{$z} = " ";
		}
	}
}

my $curLocation = [ -3, -3, -3 ];
my $all = \%all;

# now start trying to commit stuff

sub tryThis;

sub tryThis {
	my $shaded = shift;
	my $curLocation = shift;
	my $all = shift;

	foreach my $name (sort keys %{ $all }) {

		# no use trying to place a cubie which has already been placed
		next unless ${$all}{$name}{"used"} eq "no";

		ROTATION: for(0..@{ ${$all}{$name}{"rotations"} }-1) {
			my($x, $y, $z) = @{ ${$all}{$name}{"rotations"}[$_]{"location"} };
			if(
				$x == ${$curLocation}[0]
				&& $y == ${$curLocation}[1]
				&& $z == ${$curLocation}[2]
			) {
				$shaded = commit($shaded, ${$all}{$name}{"rotations"}[$_]);
				${$all}{$name}{"used"} = ${$all}{$name}{"rotations"}[$_]{"location"};

				# check for consistency
				for(my $a = -4; $a <= 4; $a++) {
					for(my $b = -4; $b <= 4; $b++) {
						foreach my $c (-2, 1) {
							if(
								(
									${$shaded}{$a}{$b}{$c} ne " "
									&& ${$shaded}{$a}{$b}{$c+1} ne " "
									&& ${$shaded}{$a}{$b}{$c} ne ${$shaded}{$a}{$b}{$c+1}
								)
								|| (
									${$shaded}{$a}{$c}{$b} ne " "
									&& ${$shaded}{$a}{$c+1}{$b} ne " "
									&& ${$shaded}{$a}{$c}{$b} ne ${$shaded}{$a}{$c+1}{$b}
								)
								|| (
									${$shaded}{$c}{$a}{$b} ne " "
									&& ${$shaded}{$c+1}{$a}{$b} ne " "
									&& ${$shaded}{$c}{$a}{$b} ne ${$shaded}{$c+1}{$a}{$b}
								)
							) {
								$shaded = uncommit($shaded, ${$all}{$name}{"rotations"}[$_]);
								${$all}{$name}{"used"} = "no";

								$Snake::counter++;
								output2(%{$shaded}) unless $Snake::counter % 1000;
								next ROTATION;
							}
						}
					}
				}

				${$curLocation}[0] += 3;
				if(${$curLocation}[0] == 6) {
					${$curLocation}[0] = -3;
					${$curLocation}[1] += 3;
					if(${$curLocation}[1] == 6) {
						${$curLocation}[1] = -3;
						${$curLocation}[2] += 3;
						if(${$curLocation}[2] == 6) {
							output2(%{$shaded});
							exit;
						}
					}
				}

				tryThis $shaded, $curLocation, $all;

				# if we return here, then obviously the current situation is unsolvable
				# so, undo a step and go back

				$shaded = uncommit($shaded, ${$all}{$name}{"rotations"}[$_]);
				${$all}{$name}{"used"} = "no";

				${$curLocation}[0] -= 3;
				if(${$curLocation}[0] == -6) {
					${$curLocation}[0] = 3;
					${$curLocation}[1] -= 3;
					if(${$curLocation}[1] == -6) {
						${$curLocation}[1] = 3;
						${$curLocation}[2] -= 3;
						if(${$curLocation}[2] == -6) {
							exit;
						}
					}
				}

			}
		}
	}
}

tryThis $shaded, $curLocation, $all;