# Ambiguous Locations on a Grid

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.
• The testcases for Case 5 don't seem quite right. I get (0,2),(2,1), (1,3), (1,3), and nothing. – TFeld Jan 29 '19 at 19:33
• @TFeld Thanks. Fixed. – Beefster Jan 29 '19 at 21:17
• @Arnauld Seems reasonable to me. I'll add that to the already non-exhaustive list. – Beefster Jan 30 '19 at 18:25

# 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[]


# Python 2, 234202200 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!

# 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.

# J, 61 bytes

Takes in the grid with infinity _ for empty tiles, 1 for walls. Returns the grid with either 0 or 1, with the latter indicating a possible position.

e."1 2]]0 1|:i.@4|."{_2+((,-)|.=i.2)([:<./(1+|.!.1)^:(<_))"$]  Try it online! Can probably further be golfed by trying other arrangements of the different axes. • ((,-)|.=i.2) 4 directions in clockwise order: 0 1, 1 0, 0 _1, _1 0 • (…)^:(<_)"$ for each direction and the grid
• ^:(<_) until the output does not change, return all intermediate steps:
• 1+|.!.1 shift the grid, pushing new 1 in at the borders, incrementing each cell.
• [:<./ take the minimum of each cell over all steps.
• _2+ Minus 2. We now have the 4 grids, representing each direction, with the cell representing the distance.
• i.@4|."{ get all possible rotations of the 4 grids.
• 0 1|: transpose so that each cell has 4 lists: the possible arrangements of the sensors.
• e."1 2]] set cells to 1 if the given sensor input is in the 4 lists, otherwise to 0.