30
\$\begingroup\$

In the ASCII art world, there is water, hash walls and letter mechanisms.

You are in a room made up of hash walls (# signs):

#######
#     #
#     #
#     #
# ### #
#     #
#######

You install an S water source (S sign) and an E water tank (E sign) which can receive water from any direction, but you only have one S source and one E tank.

#######
#  S  #
#     #
#     #
# ### #
#  E  #
#######

So you have to select wisely where to place the source. That's where you pull off your skills.

The task

You get an input consisting of a string representing a room with the source and the tank:

#######
#  S  #
#     #
#     #
# ### #
#  E  #
#######

You have to find out if the water ultimately reaches the tank. The water flows down, if possible, else to the left and right, if possible. The water doesn't accumulate because it doesn't go up.

So, for the above input, the result is:

#######
#  *  #
#  *  #
#*****#
#*###*#
#**O**#
#######

The water happily reaches the tank, so you must output a truthy value.

But if the water doesn't reach the tank:

#######
#S    #
#     #
#  E  #
# ### #
#     #
#######

#######
#*    #
#*    #
#* X  #
#*### #
#*****#
#######

Then you must output a falsy value.

Write a program to decide whether the water ultimately reaches the tank. Your code should be as short as possible.

Assumptions

  • Assume that the input is always valid (the entire room is an enclosed rectangular region with the S and E).

  • Assume there is only one room provided as input.

Test Cases

Your program should return a truthy value for the following test cases:

#######
#  S  #
#     #
#     #
# ### #
#  E  #
#######

#######
#  S  #
#     #
#  E  #
#     #
#     #
#######

#######
#     #
#     #
# SE  #
# ### #
#     #
#######

###############################################
#                      S                      #
#                                             #
#                                             #
#                                             #
#               ###############               #
#                                             #
#  ##################     ##################  #
#                                             #
#                                             #
#                    #####                    #
#                      E                      #
###############################################

#######
#  S  #
#     #
#     #
# ### #
#   # #
### ###
## E ##
#     #
#######

But a falsy value for the following test cases:

#######
#S    #
#     #
#  E  #
# ### #
#     #
#######

#######
#     #
# SE  #
#     #
#     #
#     #
#######

#######
#     #
#  E  #
#     #
#  S  #
#     #
#######

####################################
#                                  #
#                                  #
#                                  #
#S             #                  E#
####################################

The second to last room in the True category and the last room in the False category were shamelessly stolen borrowed from Koth: Jump and Run by Manu (who deleted the sandbox post).

The last room in the True category is from Martin Buttner's answer in Retina.

\$\endgroup\$
  • \$\begingroup\$ Note: I deleted my KOTH sandbox post, your challenge looks much better :) \$\endgroup\$ – CommonGuy Feb 29 '16 at 10:33
  • \$\begingroup\$ Does'nt the water accumulated until it fill any room? Thus the water always reach the tank if and only if they are in the same room. \$\endgroup\$ – Bob Feb 29 '16 at 10:50
  • 1
    \$\begingroup\$ Pro tip for formatting test cases in true/false challenges (or classification challenges with few classes): group the test cases by output and separate the groups so you can avoid the from /to/really bits (which makes it easier for participants to process all test cases at once). \$\endgroup\$ – Martin Ender Feb 29 '16 at 12:36
  • 1
    \$\begingroup\$ So basically Minecraft liquid flow logic. Although in Minecraft I think the 3rd in your true test cases would return false since the water would only go towards the left side. \$\endgroup\$ – Patrick Roberts Feb 29 '16 at 19:22
  • 1
    \$\begingroup\$ Reminds me of falling-sand water physics. \$\endgroup\$ – immibis Feb 29 '16 at 20:06
15
\$\begingroup\$

Snails, 20 bytes

\S{d(=\#n)?^#},!(t\E

Prints 0 for the falsey value and 1 for the truthy value.

Try it online!

  • \S matches S at the start
  • d sets direction to down
  • {...}, matches the stuff in braces 0 or more times
  • =\# is an assertion which succeeds if there is a # char ahead of the snail, but does not move it
  • n turns 90 degrees in either direction
  • (...)? matches the pattern in parentheses 0 or 1 times
  • \ ​ matches a space and moves the snail onto it
  • !(... is a negative assertion
  • t teleports to any unmatched square in the grid
  • \E matches E
\$\endgroup\$
  • \$\begingroup\$ I don't want to compile this language by myself. Is there an online interpreter for this? \$\endgroup\$ – user48538 Feb 29 '16 at 11:25
  • \$\begingroup\$ @zyabin101 No, there is no online interpreter. \$\endgroup\$ – feersum Feb 29 '16 at 11:27
  • \$\begingroup\$ Okay, time to call Dennis. :P Where is my projector? \$\endgroup\$ – user48538 Feb 29 '16 at 11:45
  • 5
    \$\begingroup\$ i.imgur.com/dvWrAwP.png I made it myself. \$\endgroup\$ – user48538 Feb 29 '16 at 11:58
  • \$\begingroup\$ Well, I've tried, but it's printing 0 for all test cases but one for me. What am I doing wrong? \$\endgroup\$ – Dennis Feb 29 '16 at 13:48
6
\$\begingroup\$

Retina, 87 bytes

Byte count assumes ISO 8859-1 encoding.

+mT`E `S`(?<=^(?(1)!)(?<-1>.)*S.*¶(.)*)[E ]|.?S(?=(.)*¶.*#(?<-2>.)*(?(2)!)$)[E ]?
M`E
0

Try it online!

As much as 2D string processing is possible in Retina (or .NET regex in general), it's not exactly concise...

Explanation

+mT`E `S`(?<=^(?(1)!)(?<-1>.)*S.*¶(.)*)[E ]|.?S(?=(.)*¶.*#(?<-2>.)*(?(2)!)$)[E ]?

This is a flood-fill which marks all the cells that are reached by water with S. It does so by matching the characters that can be reached and then transliterating them to S with T-mode. This flood-fill goes through both spaces and E. The + at the beginning repeats this until the output stops changing.

As for the actual regex is contains two separate cases:

(?<=^(?(1)!)(?<-1>.)*S.*¶(.)*)[E ]

This matches a space or E which is exactly one cell below an S. The vertical matching is done by counting the prefix on the current line using balancing groups so we can ensure that the horizontal position is the same. This one takes care of falling water.

.?S(?=(.)*¶.*#(?<-2>.)*(?(2)!)$)[E ]?

This is very similar: it matches an S and if available the character before and after it, provided that the character directly beneath the S is a #. This takes care of water spreading along the ground.

When we're done it's very easy to determine if the water reached E. If it did, then E has been removed from the string in the flood-fill, and if not the E is still there. So let's count the number of Es:

M`E

But now that's 0 (which I'd consider falsy) for truthy test cases and 1 (which I'd consider truthy) for falsy test cases. We can invert this very easily by counting the number of 0s in this result:

0

Done.

\$\endgroup\$
  • \$\begingroup\$ Adding your input as a test case. \$\endgroup\$ – user48538 Feb 29 '16 at 18:38
11
\$\begingroup\$

Slip, 20 + 2 = 22 bytes

S>( ^4|^4(?|`#)^T)*E

So Slip's still as broken as ever, but for once this was a challenge it could actually do. It was never really designed to be that golfy though, so it'll never beat Snails at anything :P

Needs the r flag (no repeating cells) to terminate.

Try it online. Output is the path taken for truthy, empty for falsy.

S                 Match S
>                 Rotate pointer downward
(                 Either...
 <space>^4          Match a space and point downwards
 |                  or
 ^4                 Point downwards
 (?|`#)             Match # below then reset pointer
 ^T                 Either turn left or right
)*                ... 0+ times
E                 Match E
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.