Commits

Shlomi Fish committed 85eaebe Merge

Committed

Comments (0)

Files changed (21)

 nurikabe-solver/Games-Nurikabe-Solver/Build
+nurikabe-solver/Games-Nurikabe-Solver/META.json
+nurikabe-solver/Games-Nurikabe-Solver/META.yml
 nurikabe-solver/Games-Nurikabe-Solver/MYMETA.json
 nurikabe-solver/Games-Nurikabe-Solver/MYMETA.yml
 nurikabe-solver/Games-Nurikabe-Solver/_build
 nurikabe-solver/Games-Nurikabe-Solver/blib
+
+syntax: regexp
+
+^nurikabe-solver/Games-Nurikabe-Solver/Games-Nurikabe-Solver-\d+\.\d+(?:/|\.tar\.gz$)

docs/Nurikabe_Strategies.txt

+# vim:ft=txt
+
+#. Proximity analysis - some cells can be eliminated because they are not
+reachable (also consider that white cells of certain islands interfere
+with the extent of different islands).
+
+#. A straight row or column of black cells can be tested for black cells in
+its middle which will place two white cells and so one can conclude that
+they are white.
+
+#. If you have something like:
+
+   |[B][G][B]
+   |[G][G][B]
+   -----------------
+
+Then it is evident that the upper [G] (Gray/Unknown) has to be white, or else
+the lower [G]s will also all be black.
+
+#. Cells between two islands (either diagonally or in a one-cell vertical
+or horiozntal spacing) must be black, or else the two islands will be joined.
+
+#. Filling-style strategy: if past a certain geometery (that is within the
+limits of its number), an island can only expand into one cell, then that
+cell will be white.
+
+#. If an Island reaches certain points which consume all of its
+number, then its white edge points can be marked with black in the opposite
+direction to its extent.
+
+#. One cannot have a loop or a path of white cells (including diagonal ones)
+from one edge of the board to the other, which contains black cells inside,
+because this will prevent the black cells from being contiguous.
+    - Alternative phrasing: a polymino of black cells that can only expand into
+    a single grey cell will expand there.
+
+#. Sometimes extending an $N -1 island to a white cell in proximity to one of
+its cells will cause the remaining cells to form a 4*4 black region. As
+a result, this white cell must be black.
+
+#. Often when there's a situation like:
+
+[W][G][G]
+[B][B][B]
+
+We can see that the island should expand into the leftmost gray/unknown cell
+or else it will need to take a costly detour which will consume the rest of its
+number.
+
+#. Islands that can expand in several different manners must mark all the
+common black cells inflected by these ways in this way. For example:
+
++------
+|[2][G]
+|[G][G]
+
+The lower-right [G] cell must be black because it will be black whether the
+2 expands to the right or to the bottom.
+
+In addition, if we have:
+
+    x1 x2 x3 x4
+y1     [B][B][B]
+y2  [B][4][W][B]
+y3  [B][G][W][B]
+y4     [G][G][B]
+
+The the 4-cell region can only expand into (x2,y3) or (x3,y4) so
+[G](x2,y4) must be black.
+
+#. If marking a cell as white will make it reachable only by one island,
+and as a result they will form a parly-diagonal loop of white cells, which
+will segment the black master region, then the cell must be black.
+
+#. If we have something like:
+   x1  x2 x3
+y1 [2W][G][B]
+y2 [ G][G][B]
+
+The if [G](x1,y2) is white, then (x2,y1) and (x2,y2) will be black which
+will form a 2*2 region of black cells which is impossible.

nurikabe-solver/Games-Nurikabe-Solver/Build.PL

     license             => 'mit',
     dist_author         => 'Shlomi Fish <shlomif@cpan.org>',
     dist_version_from   => 'lib/Games/Nurikabe/Solver.pm',
+    configure_requires =>
+    {
+        'Module::Build' => '0.36',
+    },
     build_requires => {
         'Test::Differences' => 0,
         'Test::More' => 0,
         'Class::XSAccessor' => 0,
     },
     add_to_cleanup      => [ 'Games-Nurikabe-Solver-*' ],
-    create_makefile_pl => 'traditional',
 );
 
 $builder->create_build_script();

nurikabe-solver/Games-Nurikabe-Solver/Changes

 Revision history for Games-Nurikabe-Solver
 
-0.01    TODO - Fill in.
-
+0.01    2013-05-22
+    - First release.

nurikabe-solver/Games-Nurikabe-Solver/MANIFEST

 lib/Games/Nurikabe/Solver/Island.pm
 lib/Games/Nurikabe/Solver/Move.pm
 lib/Games/Nurikabe/Solver.pm
-Makefile.PL
 MANIFEST
 META.yml
 README
 t/board-input.t
 t/boilerplate.t
 t/calc-vicinity.t
+t/cpan-changes.t
 t/island-surround.t
 t/lib/Games/Nurikabe/Solver/Test/BoardInput.pm
 t/load-from-string.t
 t/pod.t
 t/solve1.t
 t/solve-refactor.t
+t/style-trailing-space.t
+META.json

nurikabe-solver/Games-Nurikabe-Solver/inc/Test/Run/Builder.pm

         Test::Run::CmdLine::Iface->new(
             {
                 'test_files' => [glob("t/*.t")],
-            }   
+            }
             # 'backend_params' => $self->_get_backend_params(),
         );
 
 sub ACTION_tags
 {
     my $self = shift;
-    return 
+    return
         $self->do_system(
             "ctags",
             qw(-f tags --recurse --totals

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver.pm

 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Base.pm

 sub mk_accessors
 {
     my $package = shift;
-    return $package->mk_acc_ref([@_]); 
+    return $package->mk_acc_ref([@_]);
 }
 
 =head2 __PACKAGE__->mk_acc_ref([qw(method1 method2 method3)])
 package $package;
 
 Class::XSAccessor->import(
-    accessors => \$mapping,            
+    accessors => \$mapping,
 );
 EOF
 
 
     return $self->_new_coords(
         {
-            y => $coords->y + $offset->[0], 
+            y => $coords->y + $offset->[0],
             x => $coords->x + $offset->[1],
         }
     );
 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Board.pm

 
 =head2 $class->load_from_string($string)
 
-Loads from the string. A string is something like 
+Loads from the string. A string is something like
 
     Width=5 Height=5
     [] [] [] [1] []
 {
     my $class = shift;
     my $string = shift;
-    
+
     if ($string !~ m{\AWidth=(\d+)\s*Height=(\d+)\n}gms)
     {
         die "Cannot read string";
                 my $num_cells = $cell_contents;
                 my $index = scalar(@islands);
 
-                push @islands, 
+                push @islands,
                     Games::Nurikabe::Solver::Island->new(
                         {
                             idx => $index,
 =head2 \@coords = $self->border_exclude_coords()
 
 Returns the coordinates of the cells directly outside the board's borders so
-they can be excluded. 
+they can be excluded.
 
 =cut
 
             {
                 $self->_mark_as_black($coords);
             }
-            
+
             $self->_add_move(
                 {
                     reason => "surround_island_when_full",
     my $offset = $shape->{'offset'};
     my $blacks_offsets = $shape->{'blacks'};
 
-    # Other [X,Y] 
+    # Other [X,Y]
     my $other_coords = $self->add_offset($c, $offset);
-    
+
     if (! $self->_is_in_bounds($other_coords))
     {
         return;
     }
 
     my $other_cell = $self->get_cell($other_coords);
-    
+
     if ($other_cell->not_same_island($cell))
     {
         # Bingo.
 {
     my $self = shift;
 
-    # Mark non-traversable cells - these are cells that are too close 
+    # Mark non-traversable cells - these are cells that are too close
     # to a white island cell.
     foreach my $island (@{$self->_islands()})
     {
 {
     my $self = shift;
 
-    # Mark non-traversable cells - these are cells that are too close 
+    # Mark non-traversable cells - these are cells that are too close
     # to a white island cell.
     foreach my $island (@{$self->_islands()})
     {
             {
                 # Perform a BrFS scan on the cell to find all adjacent black
                 # cells and the unknown cells that are adjacent to them.
-                
+
                 my @queue = ($cell_coords);
 
                 my %adjacent_unknowns;
                 # may well as be white.
                 if (
                     ($cells_count < $self->_found_totals->{$NK_BLACK})
-                        && 
+                        &&
                     (@k == 1)
                 )
                 {
 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Cell.pm

     my $self = shift;
     my $other = shift;
 
-    return 
+    return
     (
-           $self->belongs_to_island() 
+           $self->belongs_to_island()
         && ($self->island() != $other->island())
     );
 }
     my ($self, $island) = @_;
 
     if (($self->status() eq $NK_BLACK)
-        || (defined($self->island()) 
+        || (defined($self->island())
             && $self->island() != $island->idx()
         )
     )
 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Constants.pm

 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Coords.pm

 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Island.pm

 
                 if (!exists($exclude_coords{$s}))
                 {
-                    push @ret, $to_check; 
+                    push @ret, $to_check;
                     # Make sure we don't repeat ourselves
                     $exclude_coords{$s} = 1;
                 }
 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Move.pm

     {
         die "Color should be black or white.";
     }
-    
+
     return $self->_verdicted_cells()->{$color};
 }
 
 
 Copyright 2008 Shlomi Fish, all rights reserved.
 
-This program is released under the following license: MIT/X11 Licence. 
+This program is released under the following license: MIT/X11 Licence.
 
 =cut
 

nurikabe-solver/Games-Nurikabe-Solver/t/calc-vicinity.t

 [] [6] [] [] []
 EOF
 
-    my $board = 
+    my $board =
         Games::Nurikabe::Solver::Board->load_from_string(
             $string_representation
         );

nurikabe-solver/Games-Nurikabe-Solver/t/cpan-changes.t

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More;
+
+eval 'use Test::CPAN::Changes';
+plan skip_all => 'Test::CPAN::Changes required for this test' if $@;
+
+changes_ok();
+

nurikabe-solver/Games-Nurikabe-Solver/t/island-surround.t

     (
         map
         {
-        [ 
-            map { 
+        [
+            map {
             Games::Nurikabe::Solver::Cell->new(
                 { status => $NK_UNKNOWN }
                 )
                 idx => 0,
                 order => scalar(@$white_cells),
                 known_cells =>
-                [ 
-                    map 
+                [
+                    map
                     {
                         $board->_new_coords( {y => $_->[0], x => $_->[1],} )
                     }

nurikabe-solver/Games-Nurikabe-Solver/t/load-from-string.t

 [] [6] [] [] []
 EOF
 
-    my $board = 
+    my $board =
         Games::Nurikabe::Solver::Board->load_from_string(
             $string_representation
         );
     # TEST
     eq_or_diff (
         _island_cells_dump($board->get_island(0)),
-        [[0,3]], 
+        [[0,3]],
         "known_cells of island 0",
     );
-    
+
     # TEST
     is ($board->get_island(2)->idx(), 2, "idx() of island 2 is 2");
 
     # TEST
     eq_or_diff (
         _island_cells_dump($board->get_island(2)),
-        [[3,3]], 
+        [[3,3]],
         "known_cells of island 2",
     );
 

nurikabe-solver/Games-Nurikabe-Solver/t/solve-refactor.t

 []  []
 EOF
 
-    my $board = 
+    my $board =
         Games::Nurikabe::Solver::Board->load_from_string(
             $string_representation
         );
     {
         my $moves = $board->_solve_using(
             {
-                name => "surround_island", 
+                name => "surround_island",
                 params => {},
             }
         );

nurikabe-solver/Games-Nurikabe-Solver/t/solve1.t

 []  []
 EOF
 
-    my $board = 
+    my $board =
         Games::Nurikabe::Solver::Board->load_from_string(
             $string_representation
         );
     is ($board->_num_found_cells($NK_BLACK), 0, "Found 0 Black Cells");
 
     # TEST
-    is ($board->_num_found_cells($NK_UNKNOWN), 3, 
+    is ($board->_num_found_cells($NK_UNKNOWN), 3,
         "Currently have 3 unknown cells"
     );
 
         is ($board->_num_found_cells($NK_BLACK), 2, "Found 2 Black Cells");
 
         # TEST
-        is ($board->_num_found_cells($NK_UNKNOWN), 1, 
+        is ($board->_num_found_cells($NK_UNKNOWN), 1,
             "Currently have 1 unknown cells"
         );
     }
     my $string_representation = <<"EOF";
 Width=3 Height=3
 [] []  []
-[] [1] [] 
+[] [1] []
 [] []  []
 EOF
 
         );
 
         my $m;
-        
+
         $m = shift(@$moves);
         # TEST
         is ($m->reason(), "surrounded_by_blacks", "reason for 0 is surrounded_by_blacks");
         # TEST
         eq_or_diff(
             verdict_cells($m, $NK_BLACK),
-            [[0,2]], 
+            [[0,2]],
             "Verdicted cells for 1 is OK.",
         );
 
         # TEST
         eq_or_diff(
             verdict_cells($m, $NK_BLACK),
-            [[2,0]], 
+            [[2,0]],
             "Verdicted cells for 2 is OK.",
         );
 
         # TEST
         eq_or_diff(
             verdict_cells($m, $NK_BLACK),
-            [[2,2]], 
+            [[2,2]],
             "Verdicted cells for 3 is OK.",
         );
 
 sub in_black
 {
     my ($self, $coords) = @_;
-    
+
     return (any { $_->y == $coords->[0] && $_->x == $coords->[1] }
            @{$self->move->get_verdict_cells($NK_BLACK)})
        ;
 sub in_white
 {
     my ($self, $coords) = @_;
-    
+
     return (any { $_->y == $coords->[0] && $_->x == $coords->[1] }
            @{$self->move->get_verdict_cells($NK_WHITE)})
        ;
     }
     else
     {
-        return 'Coordinates [ ' . 
+        return 'Coordinates [ ' .
             join(" , ", map { '['.join(',',@$_) . ']' } @not_found)
             . ' ] were not marked as white in this move.'
             ;

nurikabe-solver/Games-Nurikabe-Solver/t/style-trailing-space.t

+#!/usr/bin/perl
+
+use strict;
+use warnings;
+
+use Test::More;
+
+eval "use Test::TrailingSpace";
+if ($@)
+{
+    plan skip_all => "Test::TrailingSpace required for trailing space test.";
+}
+else
+{
+    plan tests => 1;
+}
+
+my $finder = Test::TrailingSpace->new(
+    {
+        root => '.',
+        filename_regex => qr/(?:(?:\.(?:t|pm|pl|PL|yml|json|arc|vim))|README|Changes|LICENSE|MANIFEST)\z/,
+    },
+);
+
+# TEST
+$finder->no_trailing_space(
+    "No trailing space was found."
+);
+