# A rolling drop gathers all pearls?

Quell is a single-player grid-based puzzle game. Pearls are scattered across a 2D map and the aim is to collect them all by rolling a drop of water over them. For this challenge we will only consider basic maps containing the drop, pearls, walls, and empty spaces. (The full game includes a variety of additional objects/interactions such as spikes, movable blocks, and teleport rings.) We will also assume that the map is bounded and connected, that is, it is surrounded by walls and a continuous path exists between any two squares.

The drop, initially stationary, may be rolled up, down, left, or right. A distinctive feature of Quell is that once you start the drop rolling, it rolls as far as possible in that direction, stopping only when it hits a wall. Any pearls along the path are collected automatically. Your inability to stop the drop or change its direction until it hits a wall has two consequences:

• There may be empty spaces on the map that the drop can never pass through or pearls that can never be collected (the latter never happens in the real game).
• The order in which pearls are collected matters on some maps because certain moves cut the drop off from areas that were previously accessible.

For example, consider the following map, where O = drop, @ = pearl, # = wall, . = empty space:

#######
#@.#.@#
#..#..#
#O....#
#..####
#@.#
####


We see that the move sequence RULDLUD (among others) collects all three pearls:

#######      #######      #######      #######      #######      #######      #######      #######
#@.#.@#      #@.#.@#      #@.#.O#      #@.#O.#      #@.#..#      #@.#..#      #O.#..#      #..#..#
#..#..#  R   #..#..#  U   #..#..#  L   #..#..#  D   #..#..#  L   #..#..#  U   #..#..#  D   #..#..#
#O....#  =>  #....O#  =>  #.....#  =>  #.....#  =>  #...O.#  =>  #O....#  =>  #.....#  =>  #.....#
#..####      #..####      #..####      #..####      #..####      #..####      #..####      #..####
#@.#         #@.#         #@.#         #@.#         #@.#         #@.#         #@.#         #O.#
####         ####         ####         ####         ####         ####         ####         ####


However, if the first move is U or D the drop will become trapped in the 'alley' on the left side and then unable to collect the pearl in the top-right corner.

Your goal in this challenge is to decide whether all pearls in a given map can be collected. Your program/function may take the map in any sensible format (e.g. multiline string, list of lines, matrix), which extends to replacing O@#. with distinct characters/digits of your choice. To indicate whether the map is solvable or not, output/return either

• any truthy/falsy value (swapping allowed) according to your language's convention, or
• one of two distinct, fixed values of your choice.

For reference, a polynomial-time algorithm for solving this problem is presented here. You are not required to implement this algorithm (though of course you may).

### Test cases

#### Solvable

 #########
##....@..#
#[email protected]...@#
##....@#.#
#########
(possible solution: RULDR)

######
##@...##
#@.....#
##.....#
###...#
#@O.#
#####
(possible solution: LULDRUL)

#######
#@.#.@#
#..#..#
#O....#
#..####
#@.#
####
(possible solution: RULDLUD)

###############
#..#..........#
#[email protected].@....#
#......@......#
#.@#########@.#
#...@.@.@.@...#
#..........#..#
###############
(possible solution: RLURDRULRDLULDR)

#############
#O........#@#
#.#.........#
#.@....@#...#
#...#@......#
#...@#......#
#........#..#
#..#........#
#..........##
##@........@#
#############
(possible solution: DRULDRULRUDLUDRLUR)


#### Unsolvable

######
#O...##
#.....#
#..@..#
#@...@#
#######

#####
#.@.#
####...####
#@...O...@#
####...####
#.@.#
#####

#######
#@.#.@#
#..#..#
#O....#
#..#..#
#@.#.@#
#######

###############
#..#..........#
#[email protected].@....#
#....#.@......#
#.@#########@.#
#...@.@.@.@...#
#..........#..#
###############

#############
#O........#@#
#.#.........#
#.@.#..@#...#
#...#@......#
#...@#......#
#........#..#
#..#........#
#..........##
##@........@#
#############



# Python 2, 247237229 217 bytes

Thanks to Dingus for removing 12 bytes of code residue.

A simple breadth first search, definitely not in polynomial time.

q=[input()]
s={0}
r=1
for b in q:
r&='4'in b;s|={b}
for v,w in(0,1),(0,-1),(1,0),(-1,0):
n=eval(b);f=b.find;y,x=divmod(f('3')-1,f(']')+2);x/=3
while~-n[y][x]:n[y][x]=2;x+=v;y+=w
n[y-w][x-v]=3;q+={n}-s
print r


Prints 0 if the map is solvable and 1 otherwise. Takes input as a list of list of integer with the following mapping:

OUTSIDE = 0
WALL = 1
INSIDE = 2
DROPLET = 3
PEARL = 4


# Charcoal, 76 bytes

⊞υυＷＳ⊞υ⁺⊟υ⪪ι¹ＦυＦ⟦Ｌθ¹±¹±Ｌθ⟧«≔Ｅιλη≔⌕ηOζＷ‹#§η⁺ζκ«§≔ηζ.≧⁺κζ§≔ηζO»¿¬№υη⊞υη»⊙υ¬№ι@


Try it online! Link is to verbose version of code. Takes input as a rectangular newline-terminated list of strings and outputs a Charcoal boolean, i.e. - if all the pearls can be collected, nothing if not. Explanation:

⊞υυＷＳ⊞υ⁺⊟υ⪪ι¹


Read in the list and convert it into a character array for convenience. Start a breadth first search from the initial position.

ＦυＦ⟦Ｌθ¹±¹±Ｌθ⟧«


Loop over all positions and directions.

≔Ｅιλη


Clone the current position.

≔⌕ηOζ


Get the index of the drop.

Ｗ‹#§η⁺ζκ«


While it's not hitting a wall...

§≔ηζ.≧⁺κζ§≔ηζO»


... move the drop one square in the current direction.

¿¬№υη⊞υη


If this results in a new position then save it to the search list.

»⊙υ¬№ι@


Output whether any positions have no pearls left.

• @Dingus My bad, a typo slipped in at the last second. Should be fixed now.
– Neil
Commented Nov 10, 2021 at 0:00