Ambiguous Locations on a Grid

Question

You have a little robot with four distance sensors. It knows the layout of a room, but it has no sense of orientation other than being able to lock onto the grid orientation. You want to be able to find out where the robot is based on the readings, but it can be ambiguous because of the limited sensors.

Challenge Explanation

You will be given a room layout and four clockwise distance readings giving the number of cells between you and a wall. There can be walls in the middle of the room and the edges of the grid are also walls. The robot cannot be placed on top of a wall.

Your objective is to list all of the locations within the room that the robot could be in that would give the given readings. Keep in mind that the robot has no sense of orientation (other than being locked to 90 degree angles on the grid- i.e. the robot will never be oriented diagonally or some other skew angle), so a reading of [1, 2, 3, 4], for example, is the same as reading [3, 4, 1, 2].

Examples

For these examples, cell coordinates will be given as 0-indexed (x, y) pairs from the top-left cell. Readings will be given in clockwise order in a square bracketed list. Layouts will use pound signs for walls and other characters (usually dots) to represent empty cells.

Case 1

. . . .
. . . .
. . # .
. . . .

• [1, 0, 2, 3] ==> (1, 0), (3, 1)
• [0, 0, 3, 3] ==> (0, 0), (3, 0), (0, 3), (3, 3)
• [2, 1, 1, 0] ==> (0, 2), (2, 1)
• [1, 1, 2, 2] ==> (1, 1)

Case 2

# a . # a .
a # . . # a
. . # . . #
# . . # . .
a # . . # a
. a # . a #

• [0, 0, 1, 1] ==> every position on the grid that is a dot
• [1, 0, 0, 0] ==> all of the a's on the grid

Case 3

.

• [0, 0, 0, 0] ==> (0, 0)

Case 4

. # #
. . .

• [1, 2, 0, 0] ==> (0, 1)
• [0, 1, 2, 0] ==> (0, 1)
• [0, 0, 1, 0] ==> (0, 0)
• [1, 0, 1, 0] ==> (1, 1)
• [0, 1, 0, 1] ==> (1, 1)

Case 5

. # . .
. . . .
. . # .
. . . .

• [2, 1, 1, 0] ==> (0, 2), (2, 1)
• [0, 2, 2, 1] ==> (1, 1)
• [1, 0, 2, 2] ==> (1, 1)
• [0, 3, 0, 0] ==> (0, 0)
• [1, 0, 1, 1] ==> (1, 2)

Other Rules

• Input may be in any convenient format. Input is a grid of walls and spaces and a list of four distances in clockwise order.
• Output may either be a list of all cells that satisfy the reading or a modified version of the grid showing which cells satisfy the reading. The exact format of the output doesn't matter as long as it is reasonable and consistent. Valid output formats include, but are not limited to:
  • Printing a line for each cell coordinate as an ordered pair
  • Printing the grid with ., #, and ! for space, walls, and possible locations, respectively.
  • Returning a list of ordered pairs
  • Returning a list of indexes
  • Returning a list of lists using different values for spaces, walls, and possible locations
  • Return/print a matrix of 0s and 1s, using 1s to represent cells where the reading would occur. (It is not necessary to include walls)
  • Once again, this list is not exhaustive, so other representations are valid as long as they are consistent and show every possible valid location in a grid or list. If you are unsure, leave a comment and I will be happy to clarify.
• You may assume that a reading corresponds to at least one location on the grid.
• You may assume that the input grid is at least 1x1 in size and has at least one empty space.
• You may assume that the input grid is no larger than 256 cells in each dimension.
• You may assume that the input grid is always a perfect rectangle and not jagged.
• There is no penalty or bonus if your program happens to give sane outputs for invalid inputs.
• This is code golf, so shortest code wins.

Answer 1

JavaScript (ES6),  130 128 126  125 bytes

Takes input as \$(m)(l)\$ where \$m\$ is a binary matrix describing the room layout (\$0\$ = wall, \$1\$ = empty) and \$l\$ is the list of distances.

Returns another binary matrix where each valid position is marked with \$1\$.

m=>l=>m.map((r,y)=>r.map((v,x)=>v&!!([...'3210321'].map(d=>(g=X=>(m[Y+=~-d%2]||0)[X+=(d-2)%2]?1+g(X):0)(x,Y=y))+g).match(l)))

Try it online! (with post-processed output for readability)

Commented

m => l =>                         // m[] = layout matrix; l[] = list of distances
  m.map((r, y) =>                 // for each row r[] at position y in m[]:
    r.map((v, x) =>               //   for each cell v at position x in r[];
      v &&                        //     yield 0 if v = 0
      !!(                         //     otherwise, test whether we can find l[] within a
        [...'3210321']            //     list containing twice the results of the sensors
        .map(d =>                 //       for each direction d:
          (g = X => (             //         g = recursive function taking X
              m[Y += ~-d % 2]     //         add dy[d] to Y
              || 0                //         use a dummy object if we're out of the board
            )[X += (d - 2) % 2] ? //         add dx[d] to X; if (m[Y] || 0)[X] is equal to 1:
              1 +                 //           add 1 to the final result
              g(X)                //           and do a recursive call
            :                     //         else:
              0                   //           yield 0 and stop recursion
          )(x, Y = y)             //         initial call to g with X = x and Y = y
        )                         //       end of map() over directions
        + g                       //       coerce the result to a comma-separated string,
                                  //       followed by harmless garbage
      ).match(l)                  //     test whether l[] can be found in this string
                                  //     (l[] is implicitly coerced to a string as well)
    )                             //   end of map() over r[]
  )                               // end of map() over m[]

Answer 2

Python 2, 234 202 200 191 bytes

lambda m,a:[(i,j)for j,l in e(m)for i,c in e(l)if('#'<c)*[(''.join(L)[::-1]+'#').find('#')for L in l[:i],zip(*m)[i][:j],l[:i:-1],zip(*m)[i][:j:-1]]in[a[q:]+a[:q]for q in 0,1,2,3]]
e=enumerate

Try it online!

Answer 3

Charcoal, 42 bytes

ＰθＦθ¿⁼¶ι⸿¿№Ｅ⁴Ｅ⁴⊖⌕⁺⪫ＫＤ⊕⌈η✳§⟦→↓←↑⟧⁺κμω#¦#η!ι

Try it online! Link is to verbose version of code. Charcoal seems to add some padding to the output for some reason; I'm assuming it's a bug in Charcoal. Explanation:

Ｐθ

Print the map without moving the cursor.

Ｆθ

Loop over each character in the map.

¿⁼¶ι⸿

If it's a newline then move the cursor to the start of the next line.

⊖⌕⁺⪫ＫＤ⊕⌈η✳§⟦→↓←↑⟧⁺κμω#¦#

Find the distance to the wall in direction k+m.

¿№Ｅ⁴Ｅ⁴...η!ι

Loop over all four starting directions k, peek in all four clockwise directions m, and if the result includes the second input then print a ! otherwise print the current character.