9
\$\begingroup\$

Description

Carlos always loved playing video games, especially the well-known computer game "Pipes". Today he finally decided to write his own version of the legendary game from scratch.

In this game the player has to place the pipes on a rectangular field to make water pour from each source to a respective sink. He has already come up with the entire program, but one question still bugs him: how can he best check that the arrangement of pipes is correct?

It's your job to help him figure out exactly that.

Carlos has 7 types of pipes in his game, with numbers corresponding to each type:

  • vertical pipe 1
  • horizontal pipe 2
  • corner pipes 3-6
  • two pipes crossed in the same cell 7 (note that these pipes are not connected)

Here they are, pipes 1 to 7, respectively:

enter image description here

Water pours from each source in each direction that has a pipe connected to it (thus it can even pour in all four directions). The puzzle is solved correctly only if all water poured from each source eventually reaches a corresponding sink.

Help Carlos check whether the arrangement of pipes is correct. If it is correct, return the number of cells with pipes that will be full of water at the end of the game. If not, return -X, where X is the number of cells with water before the first leakage point is reached, or if the first drop of water reaches an incorrect destination (whichever comes first). Assume that water moves from one cell to another at the same speed.

Inputs

state is represented as an Array of strings of equal length representing some state of the game. The pipes are represented by the numbers '1' to '7', the sources are given as lowercase English letters, and the corresponding sinks are marked by uppercase letters. Empty cells are marked with '0'.

It is guaranteed that each letter from the English alphabet either is not present in state, or appears there twice (in uppercase and lowercase).


Example

For

 state = ["a224C22300000", 
          "0001643722B00", 
          "0b27275100000", 
          "00c7256500000", 
          "0006A45000000"]

the output should be pipesGame(state) = 19.

Here is how the game will end:

enter image description here


Tests

The description is a rather simple one, when pipes are leaking then things become interesting. So here are a few Testcases if you want to have a go with this.

import pipes
import unittest

class TestPipes(unittest.TestCase):
    def test1(self):
        STATE_1 = ["a224C22300000", 
                   "0001643722B00", 
                   "0b27275100000", 
                   "00c7256500000", 
                   "0006A45000000"]
        self.assertEqual(pipes.pipesGame(STATE_1), 19)

    def test2(self):
        STATE_2 =  ["0002270003777z24", 
                    "3a40052001000101", 
                    "1064000001000101", 
                    "1006774001032501", 
                    "1000001001010001", 
                    "1010001001064035", 
                    "6227206A0622Z250"]
        self.assertEqual(pipes.pipesGame(STATE_2), -48)

    def test3(self):
        STATE_3 = ["a727272777A"]
        self.assertEqual(pipes.pipesGame(STATE_3), 9)

    def test4(self):
        STATE_4 = ["3222222400000000", 
                   "1000032A40000000", 
                   "1000010110000000", 
                   "72q227277Q000000", 
                   "1000010110000000", 
                   "1000062a50000000", 
                   "6222222500000000"]
        self.assertEqual(pipes.pipesGame(STATE_4), -12)

    def test5(self):
        STATE_5 = ["00p2400003777z24", 
                  "1a406P0001000101", 
                  "1064000001000101", 
                  "1006774001032501", 
                  "1000001001010001", 
                  "1000001001064035", 
                  "6227276A0622Z250"]
        self.assertEqual(pipes.pipesGame(STATE_5), 43)

    def test6(self):
        STATE_6 = ["a000", "000A"]
        self.assertEqual(pipes.pipesGame(STATE_6), 0)

    def test7(self):
        STATE_7 = ["a", "7", "1", "7", "7", "1", "1", "A"]
        self.assertEqual(pipes.pipesGame(STATE_7), 6)

    def test8(self):
        STATE_8 = ["A0000b0000", 
                   "0000000000", 
                   "0000000000", 
                   "0000a00000", 
                   "0000000000", 
                   "0c00000000", 
                   "01000000B0", 
                   "0C00000000"]
        self.assertEqual(pipes.pipesGame(STATE_8), 1)

    def test9(self):
        STATE_9 = ["0020400040", 
                  "1203300300", 
                  "7340000000", 
                  "2040100000", 
                  "7000500700", 
                  "0000200000", 
                  "0002303000", 
                  "0000000600"]

        self.assertEqual(pipes.pipesGame(STATE_9), 0)

    def test10(self):
        STATE_10 = ["3277222400000000", 
                   "1000032A40000000", 
                   "1000010110000000", 
                   "1Q2227277q000000", 
                   "1000010110000000", 
                   "1000062a50000000", 
                   "6222222500000000"]
        self.assertEqual(pipes.pipesGame(STATE_10), 40)

if __name__ == '__main__':
    unittest.main()

Code

# Define GLOBALS
DIRECTION = {
             'l': (0, -1),
             'r': (0, 1),
             'u': (-1, 0),
             'd': (1, 0)
            }

FLOW = {
        'l': {'2': 'l', '3': 'd', '6': 'u', '7': 'l'},
        'r': {'2': 'r', '4': 'd', '5': 'u', '7': 'r'},
        'd': {'1': 'd', '5': 'l', '6': 'r', '7': 'd'},
        'u': {'1': 'u', '3': 'r', '4': 'l', '7': 'u'}
       }

_IN_RANGE = lambda x, y, state: 0<=x<len(state) and 0<=y<len(state[0])

def find_starting_points(state):
    """Finds the starting nodes of the state"""
    pipes = list(filter(lambda x: 'a'<=x<='z',''.join(state)))
    starts = {}

    for i in range(len(state)):
        for j in range(len(state[0])):
            if 'a'<=state[i][j]<='z':
                starts[state[i][j]] = [i,j]

    return starts, pipes

def follow_flow(flow, current_path, state, end, final_path):
    """Recursive function that follows the flow of the pipe"""
    x, y = [x+y for x,y in zip(current_path[-1], DIRECTION[flow])]

    if _IN_RANGE(x, y, state) and state[x][y] == end:
        final_path.append(current_path + [''])
    elif _IN_RANGE(x, y, state) and state[x][y] in FLOW[flow]:
        return follow_flow(FLOW[flow][state[x][y]], current_path + [[x, y]], state, end, final_path)
    else:
        final_path.append(current_path + ['leak'])

    return final_path

def sum_water(total_path):
    """"Sums the water flowed if leakage found return sum * -1"""
    final_cells = set()
    first_leak = list(map(lambda x: len(x), filter(lambda x: 'leak' in x, total_path)))
    first_leak = 0 if len(first_leak) == 0 else min(first_leak) - 1

    for path in total_path:
        path = path[:-1]
        path = list(map(lambda x: str(x[0]) + ' ' + str(x[1]), path))
        idx = min(first_leak, len(path)) if first_leak else len(path)
        final_cells |= set(path[:idx])

    return len(final_cells) * (-1 if first_leak > 0 else 1)

def pipesGame(state):
    """"Main CodeFights function"""
    starts, pipes = find_starting_points(state)
    total_path = []

    for pipe in pipes:
        end = pipe.upper()
        for di in DIRECTION:
            x, y = [x+y for x,y in zip(starts[pipe], DIRECTION[di])]
            if _IN_RANGE(x, y, state) and state[x][y] in FLOW[di]:
                total_path += follow_flow(FLOW[di][state[x][y]], [[x, y]], state, end, [])

    return sum_water(total_path)

Sorry for the long read, but this was actually quite a difficult challenge. That is why I wanted it to share it with this community.

Any review is welcome.

\$\endgroup\$
  • \$\begingroup\$ Just wondering why do you make starts? Is it intended for you to use the last state[i][j] every time? \$\endgroup\$ – Peilonrayz Nov 17 '17 at 19:53
  • \$\begingroup\$ @Peilonrayz What do you mean use the last state[i][j]? The starts are the the starting points of the water. \$\endgroup\$ – Ludisposed Nov 17 '17 at 20:03
  • \$\begingroup\$ Ohhh, that makes much more sense, :O I thought there were like duplicates, :) \$\endgroup\$ – Peilonrayz Nov 17 '17 at 20:04
  • \$\begingroup\$ @Peilonrayz Updated question, guess I forgot to add that.. my bad. :) Should be more clear now. \$\endgroup\$ – Ludisposed Nov 17 '17 at 20:11
7
+100
\$\begingroup\$

Just a quick comment:

In Python 3.x, range is a special object that is lazily evaluated. You can check this e.g. by typing range(100000000000000000000000000) in an interpreter, which executes instantly. In Python 2.x, this raises an OverflowError right away.

This special object has custom defined __contains__ dunder methods, which do exactly the same thing as your _IN_RANGE lambda (actually even more, since they can also deal with the optional argument step).

So, long story short, just use in for range objects in Python 3.x.

\$\endgroup\$
6
\$\begingroup\$

In sum_water_refractor you should use len instead of lambda x: len(x). There is no point in using a lambda if you don't change anything (number or value of parameters).

\$\endgroup\$
  • \$\begingroup\$ Added clarification. \$\endgroup\$ – Solomon Ucko Oct 30 '17 at 12:07

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.