google devfest 2010 patchwork

gistfile1.txt

#!/usr/bin/perl

use strict;
use warnings;
use utf8;
binmode STDIN => ":utf8";
binmode STDOUT => ":utf8";

no warnings "recursion";

my @bitmap = ();

use Storable;
use YAML;

use Data::Dumper;

my $width = 600;

if ( 0 and -e 'data.bin') {
 my $bitmap = retrieve('data.bin');
 @bitmap = @$bitmap;
} else {
	my $y = 0;
	while ( <> ) {
		chomp;
		my(@line) = split //;

		@line = splice(@line, 0, $width);
		$bitmap[$y]  = \@line;
		$y++;

		( $y > $width - 1 ) and last;
	}
	store \@bitmap, 'data.bin';
}
&show;

my @orignal = @bitmap;
my $orignal = \@orignal;

my $cells = {};

my @lands = ();
	for (my $y = 0; $y < $width ; $y++) {
		for (my $x = 0; $x < $width ; $x++) {
			my $c = $bitmap[$y][$x];
			if ( $c =~ /^[AB]$/ ) {

				push @lands, {
					x => $x,
					y => $y,
				};
				my $id = @lands;
				my $total = fill($c, $x, $y, $id);
				$cells->{$id} = $total;
			}
		}
	}

	my $cells_total = 0;

	my $max = 0;
	my $key = 0;
	foreach my $k (keys %$cells) {
		my $v = $cells->{$k};

		$cells_total += $v;
		if ( $max < $v ) {
			$max = $v;
			$key = $k;
		}
	}

#validate
#@bitmap = @orignal;
#my $p = $lands[$key - 1];
#
#my $c = $bitmap[$p->{y}][$p->{x}];
#
#my $n = fill( $c, $p->{x}, $p->{y}, -1);

	print "cells_total: $cells_total\n";

	
	my $ids_to_fill = {};
	foreach my $k (keys %$cells) {
		my $v = $cells->{$k};
		if ( $max == $v ) {
			$ids_to_fill->{$k} = 1;
		}
	}

	&show;

	sub show  {
	return;
		for (my $y = 0; $y < $width ; $y++) {
			for (my $x = 0; $x < $width ; $x++) {
				my $c = $bitmap[$y][$x];
				printf "%3s", $c;
			}
			print "\n";
		}
		
	}


print YAML::Dump $cells;
print "cell_id: $key\n";
print "max: $max\n";
print YAML::Dump $ids_to_fill;


open F, '>result.txt';
my $total_found = 0;
	for (my $y = 0; $y < $width ; $y++) {
		my $filled_cells_in_line = 0;
		for (my $x = 0; $x < $width ; $x++) {
			my $c = $bitmap[$y][$x];
			if ( $ids_to_fill->{$c} ) {
				$bitmap[$y][$x] = 'X';
				$filled_cells_in_line++;
			}
		}
		$total_found += $filled_cells_in_line;
		print F "$filled_cells_in_line\n";
	}
	print F "\n";
	print "$total_found\n";
	
	&show;

sub fill {
	my $letter = shift;
	my $x = shift;
	my $y = shift;
	my $id = shift;

	my $c = $bitmap[$y][$x];

	($c eq $letter) or die "$y $x not $letter";

	#print "$letter $x $y($c) = $id\n";
	
	my $total = 1;
	# fill self
	$bitmap[$y][$x] = $id;

	my $_x;
	my $_y;

	my @neighbors = (
		{x => $x -1, y => $y  }, #left
		{x => $x -0, y => $y - 1 }, #up
		{x => $x +1, y => $y - 0 }, #right
		{x => $x +0, y => $y + 1 }  #down
	);

	foreach my $diff (@neighbors) {
		$_x = $diff->{x};
		$_y = $diff->{y};
		if ( $_x >= 0 and $_y >= 0 and defined($bitmap[$_y]) and defined($bitmap[$_y][$_x]) ) {
			if ( $bitmap[$_y][$_x] eq $letter ) {
				$total += fill($letter, $_x, $_y, $id);
			}
		}
		
	}
	
	return $total;
}

sub validate {
	for (my $y = 0; $y < $width ; $y++) {
		for (my $x = 0; $x < $width ; $x++) {
			my $my_id = $bitmap[$y][$x];
			my $my_letter = $orignal[$y][$x];

			my $_x;
			my $_y;
			
			# left
			$_x = $x - 1;
			$_y = $y;
			if ( $_x >= 0 and $_y >= 0 and defined($bitmap[$_y]) and defined($bitmap[$_y][$_x]) ) {
				if ( $my_letter eq $orignal[$_y][$_x] ) {
					$my_id == $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				} else {
					$my_id != $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				}
			}
			# up
			$_x = $x;
			$_y = $y - 1;
			if ( $_x >= 0 and $_y >= 0 and defined($bitmap[$_y]) and defined($bitmap[$_y][$_x]) ) {
				if ( $my_letter eq $orignal[$_y][$_x] ) {
					$my_id == $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				} else {
					$my_id != $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				}
			}

			# right
			$_x = $x + 1;
			$_y = $y;
			if ( $_x >= 0 and $_y >= 0 and defined($bitmap[$_y]) and defined($bitmap[$_y][$_x]) ) {
				if ( $my_letter eq $orignal[$_y][$_x] ) {
					$my_id == $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				} else {
					$my_id != $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				}
			}
			# down
			$_x = $x;
			$_y = $y + 1;
			if ( $_x >= 0 and $_y >= 0 and defined($bitmap[$_y]) and defined($bitmap[$_y][$_x]) ) {
				if ( $my_letter eq $orignal[$_y][$_x] ) {
					$my_id == $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				} else {
					$my_id != $bitmap[$_y][$_x] or die "$x,$y ne $_x,$y";
				}
			}



		}
	}
}

gistfile2.txt