Dumb robot

[harey]

Each square of an n x n grid of squares is either filled with cement blocks or left empty, such that there is at least one path from the top left corner to the bottom right corner of the grid. Outside the grid everything is filled with cement. A robot is currently located at the top left corner and wants to get to the bottom right corner, but it only knows the value of n and doesn't know the layout of the grid. It also has no method of observing its surroundings, and it is your job to give it instructions to ensure it ends up at its destination. Your instructions should be a finite list of directions (Up, Down, Left, Right) - the robot will try to move in the indicated directions in order, and, if there is a cement wall in the way at some step, it will simply fail to move in the corresponding direction and continue on with the next instruction in the list. Since the robot has no way of sensing whether it has reached its destination, it might reach the destination somewhere in the middle of your list of instructions and then later leave. The goal is to give a list of instructions, depending only on n, such that after following your instructions the robot is guaranteed to end its journey in the bottom right corner of the grid.

The bad news: I do not know the solution and I cannot ask for hints.

[CaptainEd]

Harey, I’m with you: there’s a crazy number of possible mazes just in n=3. I think I’ve got them covered:

DRDRDRDR

URUR

DRDRDRDR

[CaptainEd]

I gather that when it sees Left, it goes as far left as possible until it hits cement.

Edited March 11, 2018 by CaptainEd

[CaptainEd]

I must be wrong, imagine a capital H in a 3x3 grid. How do I get to the crossbar? Any Down or Up would take me to the bottom or top of the left vertical bar, with no way to stop in the middle. So, now I guess that each instruction moves the robots either 0 or 1 spaces. 

[harey]

13 hours ago, CaptainEd said:

I gather that when it sees Left, it goes as far left as possible until it hits cement.

An interesting variant. The problem states "there is a path", but it does not state "there is a path for the robot".

I think it is easier we stay with moving just to the next square.

Edited March 12, 2018 by harey

[Molly Mae]

 

I'm assuming there are no false paths, which would likely make this challenge impossible for n>4

Case: n=1
Solution: We did it!

Case: n=2
Solution: 3 moves (RDR or DRD), We did it!

Case: n=3
Solution: RRDDRRDDRD (alternately: DDRRDDRRDR), We did it!

At n>3, we get to the tricky part where we have to start incorporating ups and lefts, so the instruction set will definitely look different.  We have to ask ourselves how long this list of instructions is going to be for n>3.  That's a question I'm equipped to answer.

We can phrase it this way:  For n=5, the instruction set will be ______ long.

Answer:  

 

Hella

Edited March 12, 2018 by Molly Mae

[harey]

3 hours ago, Molly Mae said:

  Hide contents

Case: n=3

Solution: RRDDRRDDRD (alternately: DDRRDDRRDR), We did it!

 

  Hide contents

It can happen: RRddrrddrd (in lowercase instructions the robot cannot execute)

 

Edited March 12, 2018 by harey

[Molly Mae]

14 minutes ago, harey said:

 

Yeah, I was assuming no false paths.  Allowing for false paths makes this difficult problem yet more difficult.

[CaptainEd]

Harey, can we assume as Molly Mae did, that there is no maze, but only a simple path? I assumed otherwise, that it can be a maze, so I imagined a figure H, with only two cells with cement (top center and bottom center).

[harey]

1 hour ago, CaptainEd said:

Harey, can we assume as Molly Mae did, that there is no maze, but only a simple path? I assumed otherwise, that it can be a maze, so I imagined a figure H, with only two cells with cement (top center and bottom center).

I do not really understand what you mean by "simple path", but I think the answer is no. The figure H is OK, but you can very well have:

* * *    * * c   * * *
c * c   c * *   * c *
* * *    * * *   * c * ...

Your list must work for all these cases, as well as for all grids where there is/are one/three/four cement blocks. i.e. the solution Molly Mae proposed would not work for the first maze (so it does not matter anymore that it works for the 2nd and 3rd).

Even calculating the number of possibilities for 2 blocks gives me headaches. 7 * 6 / 2? Wrong, the robot must be free to leave the corner and the lower right corner must remain accessible.

To get insane...

[harey]

Congratulations, works. I checked it:

Spoiler

1 2 3
4 5 6
7 8 9

Some observations:
- Empty grid:  DRDR
               4589
- We can stop when he arrives to 5, DRDR always leads to 9.
- Same way, we can stop if he arrives to 6 or 8.
- if 5 is empty, we do not care about 2
- if 5 is empty and 4 blocked: dRD
                               125
So it works if 5 is empty.

If 5 is cemented, there remain two paths:
a) 1 2 3 6 9
b) 1 4 7 8 9

Let's try b (4 7 8 free, 5 blocked): DrDRD
                                     44789

If the robot can pass this way, we do not care which of {2,3,6} are free or cemented.
If the robot cannot pass this way, {2,3,6} must be free.

5 and 8 blocked: DrDrdrdrUrURdRDrD
                 44777777441223669

5 and 7 blocked: DrdrdrdrURuRDrD (we do not care about the state of 8)
                 444444441223669

5 and 4 blocked: dRdRDrD  (we do not care about the state of 7 and 8)
                 1223669

BTW, if I did not make an error, the last three instructions are not necessary.

 

I suspect a kind of recursivity, but it probably will not show up for small n. For n=2 and n=3, the robot stays where it should,  which does not seem evident for larger n.

 

Edited March 13, 2018 by harey

[CaptainEd]

Thanks for pruning unnecessary instructions.

As Molly Mae said, the maze possibilities make this even more difficult. Here are a couple of n=4 mazes:

* * c *    * * * *    * * * *

c * * *    c * c *   c * c *

c * c *    * * c *   * * c c

* * c *    * c * *   c  * * *

 

 

[Shashank]

For a 2x2 maze, the sequence will be Left- Right- Left

Let's assume our maze is 

a   b

c  d

The robot is standing at a, facing downward at c. As per the question, there will a path from a to d, so there could be cement on "b" or "c" or no cement at all. Also, there is cement outside the grid so the robot cannot move out of the grid.

Case1- Let's assume that the cement is in "b" and apply the commands- 

Left- The robot will turn towards "b" and hit the wall

Right- It will move towards "c" 

Left- It will move towards "d"- its destination

 

Case 2- Let's assume that cement is in "c" and apply the commands

Left- It will move towards "b"

Right- It will move towards "d"

Left- It will hit the cement outside the grid and will stay at the same place "d"

 

Case 3- Let's assume that there are no cement blocks

The movement will be same as in case 2

 

I hope this is acceptable as a solution

[plasmid]

Was this a problem posed to a bunch of programmers? A solution for any 4x4 maze (although IDK whether or not this is an optimal one) is

Spoiler

RRRDDDRRRDDURRRDDUURRRDDLDDRRRDRRRLUURRRDDLLDDRRRDRRRLLLDDRRRDRRRLDDRRURRDULLDDRDRRRURRDDRUURRDDRULLLDDRRDRRRLULLDDRDRRRURRDRDRLDDR

(Feel free to check it by hand for all possible 4x4 mazes if you like.)

But when I tried running the algorithm to solve any 5x5 maze, it's been running for a while and still hasn't found a solution. I can't guarantee that this approach will find one. I'll paste the perl code below.

Spoiler

#!/usr/bin/perl
use strict;
use warnings;

if (@ARGV < 1) {
  print "syntax: $0 MazeSize [Verbose]\n";
  print "MazeSize is the size of the maze\n";
  print "Verbose (optional) can be any value; ";
  print "this acts as a flag if you want\n";
  print "to see everything while calculations are done\n";
  die;
} 

# Read the size of the n x n maze and whether or not
# to be verbose from the command line
my $size = $ARGV[0];
my $verbose = 0;
if (@ARGV > 1) {
  $verbose = $ARGV[1];
}

# The array $maze[$x][$y] will have each square of the maze plus
# a perimeter of concrete blocks, so the ranges for x and y will
# be from 0 to $size+1, where the values from 1 to $size are the
# "actual" maze.
my @maze;

# Start off with an empty list of instructions
my @moves = ();

# The main loop
# This will create each possible configuration of mazes for the
# given size.
# Then for each configuration, it will use a greedy algorithm (?)
# to number each square in the maze with the number of steps to the
# exit. And it will make sure that there is a path from the start
# to the exit for this particular maze configuration.
# Then it will make a robot at (0, 0) walk according to the current
# string of instructions (if there is any) and find out where it
# ends up.
# Then it will make the robot follow the numbers from the spot
# where it's standing to the exit and append that to the instructions.
# 
# After it does that for every configuration of mazes, it will
# go through all of that all over again, and keep repeating until it
# goes through every confinguration of mazes without ever having to
# append any more instructions to the current instruction set.
# The $finished variable will be 1 if no more instructions needed
# to be appended and 0 if any needed to be appended.

my $finished = 0;

until ($finished) {
  $finished = 1;
  # Make each possible configuration of mazes. Basically, you
  # take a binary number with n^2 digits and convert all the
  # 1s into cement blocks (-1) while leaving all the 0s empty (0).
  # The loop increments by 2 each step so the least significant
  # digit in the binary string is never 1, and only goes up to
  # 2^((size^2)-1) so the most significant digit is never 1 --
  # otherwise the start or end position would be blocked.
  MAZELOOP: for (my $seed=0; $seed < 2**(($size**2)-1); $seed+=2) {
    my $sprintf_arg = "%0" . $size**2 . "b";
    my $binaryseed = sprintf($sprintf_arg, $seed);
    if ($verbose) {print "\nBinary seed: $binaryseed\n";}
    for (my $x=1; $x<=$size; $x++) {
      for (my $y=1; $y<=$size; $y++) {
        $maze[$x][$y] = -1 * substr($binaryseed, -1, 1, "");
      }
    }
    # Set the perimeter (cells with coordinate 0 or $size+1) to -1
    for (my $x=0; $x<=$size+1; $x++) {
      $maze[$x][0] = -1;
      $maze[$x][$size+1] = -1;
      $maze[0][$x] = -1;
      $maze[$size+1][$x] = -1;
    }
    
    # Give the goal (the cell at $maze[$size-1][$size-1]) a
    # value of 1. Then use a greedy algorithm to give every
    # other square in the maze a number indicating how many
    # steps it would take to reach the exit (plus 1).
    # Continue until no new cells can be given a number.
    $maze[$size][$size] = 1;
    my $nextstep = 1;
    my $nomore = 0;
    until ($nomore) {
      $nextstep++;
      $nomore = 1;
      for (my $x=1; $x<=$size; $x++) {
        for (my $y=1; $y<=$size; $y++) {
          if ($maze[$x][$y] == 0) {
            if ( ($maze[$x-1][$y] > 0) ||
                 ($maze[$x+1][$y] > 0) ||
                 ($maze[$x][$y-1] > 0) ||
                 ($maze[$x][$y+1] > 0) ) {
              $maze[$x][$y] = -2;
            }
          }
        }
      }
      for (my $x=1; $x<=$size; $x++) {
        for (my $y=1; $y<=$size; $y++) {
          if ($maze[$x][$y] == -2) {
            $maze[$x][$y] = $nextstep;
            $nomore = 0;
          }
        }
      }
    }
    if ($verbose) {
      print "This maze is\n";
      for (my $y=0; $y<=$size+1; $y++) {
        for (my $x=0; $x<=$size+1; $x++) {
          printf ("% i  ", $maze[$x][$y]);
        }
        print "\n";
      }
    }
    
    # Make sure that there is a path from the start to the
    # finish, which will be true if and only if $maze[1][1]
    # is greater than zero. Otherwise, go to the next step
    # in MAZELOOP
    next MAZELOOP if ($maze[1][1] == 0);
    if ($verbose) {print "This maze has a path to the exit\n";}
    
    # Make the robot follow the current set of instructions
    my $x=1; my $y=1;
    for (my $move=0; $move<@moves; $move++) {
      if (($moves[$move] == 0) && ($maze[$x+1][$y]>0)) {$x++;}
      if (($moves[$move] == 1) && ($maze[$x][$y+1]>0)) {$y++;}
      if (($moves[$move] == 2) && ($maze[$x-1][$y]>0)) {$x--;}
      if (($moves[$move] == 3) && ($maze[$x][$y-1]>0)) {$y--;}
    }
    
    # If the robot is not already at the goal
    while ($maze[$x][$y] > 1) {
      # Make $finished be zero
      $finished = 0;
      # And make the robot look for steps to reach a lower
      # number square
      if ($maze[$x+1][$y] == $maze[$x][$y]-1) {push(@moves, 0); $x++;}
      elsif ($maze[$x][$y+1] == $maze[$x][$y]-1) {push(@moves, 1); $y++;}
      elsif ($maze[$x-1][$y] == $maze[$x][$y]-1) {push(@moves, 2); $x--;}
      elsif ($maze[$x][$y-1] == $maze[$x][$y]-1) {push(@moves, 3); $y--;}
      unless ($verbose) {
        print "Current instructions:\n";
        for (my $move=0; $move<@moves; $move++) {
          if ($moves[$move]==0) {print "R";}
          elsif ($moves[$move]==1) {print "D";}
          elsif ($moves[$move]==2) {print "L";}
          elsif ($moves[$move]==3) {print "U";}
        }
        print "\n\n";
      }
    }
    if ($verbose) {
      print "Current instructions:\n";
      for (my $move=0; $move<@moves; $move++) {
        if ($moves[$move]==0) {print "R";}
        elsif ($moves[$move]==1) {print "D";}
        elsif ($moves[$move]==2) {print "L";}
        elsif ($moves[$move]==3) {print "U";}
      }
      print "\n";
    }
  }
}

print "\nFinal instructions:\n";
for (my $move=0; $move<@moves; $move++) {
  if ($moves[$move]==0) {print "R";}
  elsif ($moves[$move]==1) {print "D";}
  elsif ($moves[$move]==2) {print "L";}
  elsif ($moves[$move]==3) {print "U";}
}
print "\n";

 

 

[plasmid]

It reached a final set of instructions for a 5 x 5 maze, which I'm sure you're all dying to see...

Spoiler

RRRRDDDDRRRRDDDURRRRDDDUURRRRDDDUUURRRRDDDLDDRRRRDDRRRRDURRRRDLDDRRRRUUURRRRDDDLUURRRRDDDURRRDDUUURRRRDDDDLUUURRRRDDDULUURRRRDDDLLDDRRRRDDRRRRDURRRRDLDDRRRRUURRRDDULUURRURRDDDDULLDDRDRRRDRLDLDDRRRRLUURRDRRDUULLDDDRDRRRRDDURRDDLLUURRRRDDDRRURRDDDDLLUUURRRRDDDDRRDDLULUURRURRDDDDURRDDDDUUURRURRDDDDRRURRDDUURRDDLDDDRRURRDDRRUURRDDDULLUURRRRDDDLDLDDRRURRDDRRURRDDUURRDDRRUURRDDLLUUURRURRDDDDULLUURRURRDDDDRRUUURRDDDDLDDRRDDRRRRDURRRRDLLLDDRRRRDDRRRRDURRRRDLDDRRRRLLDDRDRRDULLDDRDRRRUULLDDDRDRRRRDDURRDDRRURRDDUURRRRDDURRDLLLLDDRRRRDDRRRRDURRRRDLLDLDDRRRDRLDDRRRRLLLDDRRRRDLDDRRRRLUURRDRRDURRDDLULLDDRDRDRRRDRRURRDUURRDDULLLDDRRDRRDRRRRLDDRRRRLLDDRRRRURRRDDLUUURRRDDRDLDDRDULUURRRDDRDLDDRDULLLLDDRRRDRDRRRRURRRRDLDDRRRRLULLDDLDDRRRRURRRRDLLULLDDRDRRRDRLDDRRRRURRRRDRRLULLLDDRDRDRRRLDDRRRRDRRURRDRDLLUUURRRDDRDLULUURRRDDRDLDDRDRLLDDRRDRUURRDRRDLUURRDRRDLLLDDRDRRDRRURRDRRLDDRRUURRDDRRLDLLDDRDRRULLDDRDRRULULLDDRDRDRRRDRRURRDRRDURRDUURRRDRDLUURRDRDLDDRRDURRDUULLLDDRDRDRRRLDDRRRRDRRURRDRDUURURRDDDRLUURURRDDDRLDDRULULLDDLDDRRRRLLDDRRRRURRDRDRUULLLLDDRRDRDRRRRDRLDDRRRRLLDDRRRRURRDRLULLDDRDRRLLUULLDDDRDRRRRDRRLLDDRRURRDDRRUURRDDRRLDDRLUURRRDDRLDDRLUUURRRDDDRLDDRLUURURRDDDRLDDRDRLULULLDDRDRDRRRLDDRRRRURRDRRDRUURRRDDRDRLDDRURURRDDRLUURRRDDRLDDRDRLUULLLDDRDRDRRRLDDRRRRDRRURRRDDRUURRRDDRDRLDDRURURRDDRLUURRRDDRLDDRUUUURRRDDDDRLDDDRULUURRRDDDDRLUURRRDDDDRLUUUURRRDDDDRLDDDRUULUURRRDDDDRUUURRDDDRLDDDRLDDRRDRDUURURRRDDDLLUURRRRDDDURRRDDDRRLUUURRDRRDDLLUUURRRRDDDULUURRRRDDDLULUURRRRDDDULLUURRRRDDDRRRRDURRRRDLDDRRDDLUURRRRDDRRDRRURRRDLLDDRRDRRDRRRRLLLDDRRDRRDRRLDDRDRRRULLDDRDRDRRRLDDRRRRURRDDRRDUURRDDRRDUUURRDDRRDLLLLDDRRDRRDLUURRDRRDUUURRDDRRDLLLLDDDDRRRRUURRDDDRRLDLLDDRDRRLULLDDRDRDRRRLDDRRRRURRDLLUUURRRDRDDLULUURRRDRDDRRDRDDLDDRRDULLLDDRRDRRDURRRDDRRLLDDRDRRRULLLLDDRDRRRDURRRRDRRRULLDLLDDRDRRRURRRDRLDDRRUURRDDDRRUUURRDDDRRLDLDDRRULULLDDRDRDRRRLDDRRRRUUUURRDDDDRRLLLDDRDRRLLULLDDRDRDRRRLDDRRRRURRDRRDRDUURRRDDRDUUURRRDDRDLUURRDRDLLUUUURRRDDDRDLDDRDURURRDRDLLUURRRDRDLDDRDULLLDDRRDRDURRRDLLDDRRDRDLULLLDDRRDRRDURRRRDLDDRRUURRDDDRRUUURRDDDRRUULLLDDRDRDRRRLDDRRRRURRDRDLULLDDRDRRDURRDRUUUURRDDDRRDRRLDLDDRRDLUURURURRDDLDDRRULULLLDDRRDRDRURRRDRLDDRRRDRULLULLDDRDRRDRURRRDRULLLLDDRRDRDRRLDDRRRLLDDRDRRRURRDRRLUURRRDDDRLDDRLUUURRRDDDRULUURRRDDDRLDDRLUURURRDDDDRLDDRLULULLDDRDRDRRRLDDRRRRURRDRRDRUURRRDDRDRLDDRURURRDDRLUURRRDDRLDDRDRLUULLLDDRDRDRRRLDDRRRRURRRDDRUURRRDDRUUURRRDDDRLDDDRURURRDDRURRDDDRLUURRRDDRLUUURRRDDDRLDDDRULUURRRDDDRURRDDDRLDDDRULLLDDRRDDRDDRLLDDRRDDRURURRDDRUUUURRRDDDDRLUUUURRRDDDDRLDDDDRULUUURRRDDDDRUULUURRRDDDDRLLUUURRRRDDDULUURRRRDDDUURRRRDDDRRRDDLDDRRRDDLLUUUURRRRDDDDLUULUURRRRDDDDUUURRRRDDDDULLUURRRRDDDUUUURRRRDDDDURRRDDDRRRRDDDRRRUURRRRDDDLUURRRRDDDUUURRRRDDDULUURRRRDDDLDDRRDDRRRRDURRRRDDLUURRDRRDLLDDRRDRRDRRRRLLLDDRRDRRDRRRRLDDRDRRRULLDDRDRDRRRLDDRRRRDRRURRDDRRDUURRDDRRDUUURRDDRRDLLLLDDRRDRRDRRRRLUURRDRRDUUURRDDRRDLLLLDDDDRRRRUURRDDDRRLDLLDDRDRRLULLDDRDRDRRRLDDRRRRDRRURRDRULLLDDRRDRRDRRRRURRRDLDDRRRRLULLLDDRRDRRDRRRRURRRRDULLLLDDRRDRRDRRRRURRRRDLDDRRRRULULLDDRDRDRRRLDDRRRRDRRLLDDRRDRRRRLLULLDDRDRDRRRLDDRRRRURRDRRURRDLUURRDRDLDDRDUURRDRDLULLLDDRDRDRRRLDDRRRRDRRUUUURRDDDDRRDLDDRDURRRDRDRRDLLDDRRDRDRRDLULLDDRDRRDRDLLLDDRRRDURRDRRLLLLDDRRRDRDRRRDLLDDRRRDURRRDULLLDDRRDRRDRRURRRDUULLLDDRDRDRRRLDDRRRRDRRURRDRDULULLLDDRRDRDRRRRURRRDRULLLLDDRRRDRULLULLDDRDRRDRURRRDRLUURRDRDRLLDDRRLULULLDDDDRRRRURRDRRLLDDRRDRRUURRRDDRLDDRUUURRRDDDDRLUURRRDDDRLDDRUUUURRRDDDDRLUUURRRDDDDRLDDRULUURRRDDDRLDDRLUUUURRRDDDDRLDDRDDRULLDDRDRDRLLLDDRRDDRLUULLLDDRDRDRRRLDDRRRRDRRURRRDDRUURRRDDRURRDDDRLDDDRLUURRRDDRURRDDDRULLLLDDRDRRDRURRRRDLUUURRDRRDDDLLUURRRRDDRRLDDRDDURRDDURRDDDRUURRRDDDRLDDRUUURRRDDDRLUURRRDDDRLDDRULUURRRDDDRLDDRLLDDRRRDDRLDDRLLLDDRRDDRLLLLDDRRRDDRURURRDDRDDR

This will work (unless my program is buggy), but I would be surprised if this is anywhere near optimal. And I'm not going to attempt a 10 x 10.

[plasmid]

I changed the way the algorithm works, so that it more systematically checks all possible paths for all possible mazes and is guaranteed to eventually find the shortest possible set of instructions that will solve every maze of size n x n. The bad news is that it takes a long time to run. Even after doing what I could to make this run reasonably efficiently, it still could only process a 3 x 3 maze and will take a while to process even a 4 x 4 maze, albeit on a crummy laptop.

If this was a question posed to programmers, and the person asking the question knew full well that the numbers would get huge fast (checking all possible instructions for a 17 step solution would mean checking 4¹⁷ = 17 billion potential solutions against almost 4000 mazes for the 4 x 4 case) and was making the point that you'll need to come up with something other than exhaustive brute force (sort of like the algorithm I had earlier but probably a smarter version), then it would make sense.

At any rate, this is a solution for any 3 x 3 maze with the shortest possible number of moves.

Spoiler

RDRRDLLDDRR

 

[wolfgang]

we can give him

Spoiler

right-down-right-down.....and so on

so that the number of orders= n+1

 

[CaptainEd]

Plasmid, that’s an impressively simple solution to all the n=3 mazes! Of course, the 5x5 solution is impressive, too!

Harey, this is a very interesting puzzle.