Anonymous avatar Anonymous committed dc8f7b9

Extracted a method and added code to try to trace the solution.

Comments (0)

Files changed (1)

modules/Shlomif-Sokoban-Solver/lib/Shlomif/Sokoban/Solver/Board.pm

     _data
     _dests
     _init_state
+    _queue
 /;
 
 my $dest_place_bits = 0x1;
             _dests => [],
             _init_state => \$init_state,
             _collect => +{},
+            _queue => [],
         );
 
 
     return 1;
 }
 
+sub _try_to_move_box
+{
+    my ($self, $state_ref, $x, $y) = @_;
+
+    for my $offset ([-1,0],[1,0],[0,-1],[0,1])
+    {
+        my @push_to = ($x+$offset->[0], $y+$offset->[1]);
+        my @push_from = ($x-$offset->[0], $y-$offset->[1]);
+        
+        if (   (! $self->is_wall(@push_to))
+            && (! $self->is_box($state_ref, @push_to))
+            && $self->is_reachable($state_ref, @push_from)
+           )
+        {
+            # We can push.
+            my $new_state_ref =
+                $self->_derive($state_ref, [$x, $y], \@push_to)
+                ;
+
+            # Print it - this is temporary for debugging.
+            # (Now commented out.)
+            # $self->_output($new_state_ref);
+
+            # Else - register it and proceed.
+            
+            my ($rot_idx, $rot_state) =
+                $self->_get_min_rot_perm($new_state_ref);
+            if (exists($self->_collect()->{$$rot_state}))
+            {
+                # Do nothing
+            }
+            else
+            {
+                $self->_collect()->{$$rot_state} =
+                {
+                    r => (($rot_idx+$self->_collect()->{$$state_ref}->{r})%4),
+                    p => $state_ref
+                };
+                if ($self->_is_final($rot_state))
+                {
+                    return $rot_state;
+                }
+                push @{$self->_queue()}, $rot_state;
+            }
+            
+        }
+    }
+
+    return;
+}
+
+sub _trace_solution
+{
+    my ($self, $final_state) = @_;
+
+    my @solution;
+
+    {
+        my $state = $final_state;
+
+        while (defined($state))
+        {
+            push @solution, $state;
+            $state = $self->_collect->{$$state}->{p};
+        }
+    }
+
+    foreach my $state (reverse(@solution))
+    {
+        my $r = $self->_collect->{$$state}->{r};
+
+        # Normalize the state from its rotated position.
+        my $rot_state = $state;
+        while ($r%4 != 0)
+        {
+            $rot_state = $self->_rotate($rot_state);
+            $r++;
+        }
+
+        $self->_output($rot_state);
+    }
+}
 
 =head2 $board->solve()
 
 
     $self->_collect()->{$$rot_state} = { r => $rot_idx, p => undef() };
 
-    my @queue = ($rot_state);
+    push @{$self->_queue()}, $rot_state;
 
     my $w = $self->width()-1;
     my $h = $self->height()-1;
 
-    while (my $state_ref = pop(@queue))
+    while (my $state_ref = pop(@{$self->_queue()}))
     {
         for my $y (0 .. $h)
         {
             {
                 if ($self->is_box($state_ref, $x, $y))
                 {
-                    for my $offset ([-1,0],[1,0],[0,-1],[0,1])
+                    my $final = $self->_try_to_move_box($state_ref, $x, $y);
+
+                    if (defined($final))
                     {
-                        my @push_to = ($x+$offset->[0], $y+$offset->[1]);
-                        my @push_from = ($x-$offset->[0], $y-$offset->[1]);
-                        
-                        if (   (! $self->is_wall(@push_to))
-                            && (! $self->is_box($state_ref, @push_to))
-                            && $self->is_reachable($state_ref, @push_from)
-                           )
-                        {
-                            # We can push.
-                            my $new_state_ref =
-                                $self->_derive($state_ref, [$x, $y], \@push_to)
-                                ;
+                        $self->_trace_solution($final);
 
-                            # Print it - this is temporary for debugging.
-                            $self->_output($new_state_ref);
-
-                            if ($self->_is_final($new_state_ref))
-                            {
-                                print "Finished\n";
-                                return 0;
-                            }
-                            # Else - register it and proceed.
-                            
-                            ($rot_idx, $rot_state) = 
-                                $self->_get_min_rot_perm($new_state_ref);
-                            if (exists($self->_collect()->{$$rot_state}))
-                            {
-                                # Do nothing
-                            }
-                            else
-                            {
-                                $self->_collect()->{$$rot_state} =
-                                    {  r => $rot_idx, p => $state_ref }
-                                    ;
-                                push @queue, $rot_state;
-                            }
-                        }
+                        return $final;
                     }
                 }
             }
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.