#!/usr/bin/perl

use Data::Dumper;
use strict;
our (%params,@params,$params);
require "../cgi-lib.pl";
ReadParse(*params);

print "Content-Type: text/html\n\n";

my($maxx) = 10;
my($maxy) = 10;
if($params{maxx} =~ /^\s*(\d+)\s*$/ && $1 >= 3 && $1 <= 100) {
    $maxx = $1;
}
if($params{maxy} =~ /^\s*(\d+)\s*$/ && $1 >= 3 && $1 <= 100) {
    $maxy = $1;
}
my $type = $params{type} || 'primes';

my @path_data = choose_data($type,1);
my @fill_data = choose_data($type,0);

my(@grid,$tries,$path_length);
if($params{mazeid}) {
    my($g);
    ($maxx,$maxy,$g) = get_mazeid($params{mazeid});
    @grid = @{$g};
    $tries = 1;
} else {
    for(my $i=0;$i<100;$i++) {
	my($ret) = get_maze($maxx,$maxy);
	if($ret->{status}) {
	    @grid = @{$ret->{grid}};
	    $tries = $i+1;
	    $path_length = $ret->{path_length};
	    $i = 1000;
	}
    }
}

sub get_mazeid {
    my($id) = @_;
    my(@grid);
    if($id eq "1188329393") {

    } else {
	@grid = (
	                     # Left
	    [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
	    [ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 ],
	    [ 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0 ],
	    [ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0 ],
	    [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ],
	    [ 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 ],
	    [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ], # Top
	    [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
	    [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
	    [ 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 ],
	    [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ],
	    [ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0 ],
	    [ 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0 ],
	    [ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 ],
	    [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
	                    # Right
	    );
	return ( 15, 15, \@grid );
    }
}

sub get_maze {
    my($maxx,$maxy) = @_;
    my(@grid,$done,%pos);
    while(!$done) {
	my($x,$y) = get_rand_start($maxx,$maxy);
	if(($x == 0 || $x == $maxx-1) && ($y == 0 || $y == $maxy-1)) {
	    $done = 0;
	} else {
	    $done = 1;
	    $pos{x} = $x;
	    $pos{y} = $y;
	}
    }
    
    $grid[$pos{x}][$pos{y}] = 1;
    my(%start) = ( x => $pos{x},
		   y => $pos{y});
    $done = 0;
    my($path_length) = 1;
    my $repeats = 0;
    while(!$done) {
	$repeats++;
	if($repeats > 20) {
	    $done = 1;
	}
	my($p) = get_rand_next(\%pos);
	if($p->{x} < 0 || $p->{y} < 0 ||
	   $p->{x} >= $maxx || $p->{y} >= $maxy ||
	   $grid[$p->{x}][$p->{y}]) {
	    # Not a valid move (backtracking or off the board)
	    next;
	}
	# If we're off the board, we win!
	if($p->{x} == 0 || $p->{y} == 0 ||
	   $p->{x} == $maxx-1 || $p->{y} == $maxy-1) {
	    #if($path_length > $maxx && $path_length > $maxy) {
	    if($path_length > ($maxx*$maxy*0.2)) {
		if(abs($start{x} - $p->{x}) + abs($start{y}-$p->{y}) <= 1) {
		    # We just looped around really fast, boo
		} else {
		    $grid[$p->{x}][$p->{y}] = 1;
		    $done = 1;
		}
	    } else {
		# We just sidestepped the starting move, too short
	    }
	} else {
	    # Count neighbors, should only have 1
	    my($ncount) = 0;
	    $ncount += $grid[$p->{x}-1][$p->{y}];
	    $ncount += $grid[$p->{x}+1][$p->{y}];
	    $ncount += $grid[$p->{x}][$p->{y}-1];
	    $ncount += $grid[$p->{x}][$p->{y}+1];
	    if($ncount == 1) {
		# Hooray, next square!
		$grid[$p->{x}][$p->{y}] = 1;
		$pos{x} = $p->{x};
		$pos{y} = $p->{y};
		$path_length++;
		$repeats = 0;
	    }
	}
    }
    if($repeats > 20) {
	return { status => 0 },
    } else {
	return { status => 1, grid => \@grid, path_length => $path_length };
    }
}

my($x,$y);

print "<style>\n.path_box_hidden { width: 20px; height: 20px; text-align: center; }</style>\n";
print "<style>\n.path_box_visible { width: 20px; height: 20px; text-align: center; background-color: #50C080; }</style>\n";
print "<style>\n.fill_box { width: 20px; height: 20px; text-align: center; }</style>\n";

print "<form>";
print "Width: <input size=\"3\" name=\"maxx\" value=\"$maxx\">\n";
print "Height: <input size=\"3\" name=\"maxy\" value=\"$maxy\">\n";
print "<select name=\"type\">\n";
my @options = (
    { val => 'prime', name => 'Primes' },
    { val => 'fib', name => 'Fibonacci' },
    { val => '2', name => 'x 2', },
    { val => '3', name => 'x 3', },
    { val => '4', name => 'x 4', },
    { val => '5', name => 'x 5', },
    { val => '6', name => 'x 6', },
    { val => '7', name => 'x 7', },
    { val => '8', name => 'x 8', },
    { val => '9', name => 'x 9', },
    { val => '10', name => 'x 10', },
    );
foreach my $o (@options) {
    print "<option value=\"$o->{val}\"".($type eq $o->{val} ? " selected" : "").">$o->{name}</option>\n";
}
print "</select>\n";
print "<input type=\"submit\" value=\"Generate\">\n";
print '<input type="button" value="View/Hide" onclick="toggle()">';
print "</form>\n";

my(@ids);
for($x=0;$x<$maxx;$x++) {
    for($y=0;$y<$maxy;$y++) {
	if($grid[$x][$y]) {
	    push @ids,"cell".$x."_".$y;
	}
    }
}
print qq`<script>
var is_hidden = true;
function toggle() {
    var ids,new_class,i;
    ids = new Array(`;
print join(",",(map { "'$_'" } @ids));
print qq`);
    if(is_hidden) {
        is_hidden = false;
        new_class = "path_box_visible";
    } else {
        is_hidden = true;
        new_class = "path_box_hidden";
    }
    for(i=0;i<ids.length;i++) {
        var cell = document.getElementById(ids[i]);
        cell.className = new_class;
    }
}
</script>`;

if(!$tries) {
    print "I got stuck, try again! :(<br>\n";
}

print "<table border=1>\n";
for($y=0;$y<$maxy;$y++) {
    print "<tr>\n";
    for($x=0;$x<$maxx;$x++) {
	if($grid[$x][$y]) {
	    print '<td id="cell'.$x.'_'.$y.'" class="path_box_hidden">'.pick_one(\@path_data).'</td>';
	} else {
	    print '<td class="fill_box">'.pick_one(\@fill_data).'</td>';
	}
    }
    print "</tr>\n";
}
print "</table>\n";
print "Length: $path_length\n";

sub choose_data {
    my($type,$path) = @_;
    if($type =~ /^(\d+)$/ && $1 >=2) {
	my($mult) = $1;
	my(@path) = ();
	my(@fill) = ();
	for(my $i=1;$i<100;$i++) {
	    if($i % $mult) {
		push @fill,$i;
	    } else {
		push @path,$i;
	    }
	}
	if($path) { return @path; }
	else { return @fill; }
    } elsif($type eq "fib") {
	if($path) { return (1,2,3,5,8,13,21,34,55,89); }
	else { return (4,6,7,9,10,11,12,14,15,16,17,18,19,20,22,23,24,25,26,27,28,29,30,31,32,33,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,90,91,92,93,94,95,96,97,98,99); }
    } else {
	if($path) { return (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97); }
	else { return (1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,35,36,38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64,65,66,68,69,70,72,74,75,76,77,78,80,81,82,84,85,86,87,88,90,91,92,93,94,95,96,98,99); }
    }
}

sub pick_one {
    my($list) = @_;
    my($idx) = int(rand(@{$list}));
    return $list->[$idx];
}

sub get_rand_next {
    my($pos) = @_;
    my($r) = int(rand(4));
    if($r == 0) {
	return { x => $pos->{x}-1, y => $pos->{y}};
    } elsif($r == 1) {
	return { x => $pos->{x}+1, y => $pos->{y}};
    } elsif($r == 2) {
	return { x => $pos->{x}, y => $pos->{y}-1};
    } else {
	return { x => $pos->{x}, y => $pos->{y}+1};
    }
}

sub get_rand_start {
    my($maxx,$maxy) = @_;
    my($r) = int(rand(4));
    if($r == 0) {
	return(get_rand_x(),0);
    } elsif($r == 1) {
	return(get_rand_x(),$maxy-1);
    } elsif($r == 2) {
	return(0,get_rand_y());
    } else {
	return($maxx-1,get_rand_y());
    }
}

sub get_rand_x {
    return int(rand($maxx));
}

sub get_rand_y {
    return int(rand($maxy));
}