Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Note: I deleted my KOTH sandbox post, your challenge looks much better :) – Manu Feb 29 at 10:33
1  
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). – Martin Ender Feb 29 at 12:36
1  
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. – Patrick Roberts Feb 29 at 19:22
1  
Reminds me of falling-sand water physics. – immibis Feb 29 at 20:06
4  
You should wait longer before accepting an answer. :P – VTCAKAVSMoACE Feb 29 at 20:14
up vote 14 down vote accepted

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
share|improve this answer
    
I don't want to compile this language by myself. Is there an online interpreter for this? – zyabin101 Feb 29 at 11:25
    
@zyabin101 No, there is no online interpreter. – feersum Feb 29 at 11:27
    
Okay, time to call Dennis. :P Where is my projector? – zyabin101 Feb 29 at 11:45
5  
i.imgur.com/dvWrAwP.png I made it myself. – zyabin101 Feb 29 at 11:58
    
Well, I've tried, but it's printing 0 for all test cases but one for me. What am I doing wrong? – Dennis Feb 29 at 13:48

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
share|improve this answer

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.

share|improve this answer
    
Adding your input as a test case. – zyabin101 Feb 29 at 18:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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