falling dominoes, debugging

1
votes

Here is the program I'm trying to write:

The user gives the properties of some domino pieces, some of which are vertical, and some are horizontal, and they are in n rows and m columns. Suppose we are looking at them from above: a horizontal domino can fall either to the right or to the left, and can only make other horizontal dominoes to fall. and a vertical domino can fall to the up or down and can only cause other vertical dominoes to fall.

first the user will give us the number of rows and columns as 'n m', and in the following n lines of input, the user will give lines each made of m characters, like for example m=5: ||-|- The '|' represents a horizontal and the '-' represents a vertical domino.

Now the program is supposed to determine the minimum number of dominoes which we have to push to make them all to fall.

this is the example presented in the question:

input:

3 3
|||
||-
||-

output:

4

We push the first dominoes in each row and the 2nd one in the third column (from left to right)

So here is my code:

dim = input()
n, m = [int(i) for i in dim.split(' ')]
min_d = 0
vertical = []
for q in range(0, m):
    vertical.append(n)

for j in range(0, n):
    line = list(input())
    # horizontal:
    if line[0] == '|':
        min_d += 1
    for l in range(1, m):
        if line[l] == '|':
            if line[l-1] == '-':
                min_d += 1
    # vertical:
    if j == 0:
        for k in range(0, m):
            if line[k] == '-':
                min_d += 1
                vertical[k] = 0
    if j > 0:
        for p in range(0, m):
            if line[p] == '-':
                if vertical[p] != j-1:
                    min_d += 1
                vertical[p] = j

print(min_d)

and it works fine for the above example and some other examples I made up and calculated manually. But when I submit this on the site, I get "WRONG ANSWER!" for all the tests! What is wrong with this?

2
pythonpython-3.xalgorithmdebugging
What is giving you WRONG ANSWER! ? - Hearner
for q in range(0, m): vertical.append(n) this will just give you [3,3,3] - Mitch
Since you need to worry about the vertical dominoes as well parsing the input one line at a time will not work since we care whats on the other line. Make the 2d array before starting to check for how many dominoes need to be pushed - Mitch
I did this to use less memory, and the [3, 3, 3] doesn't make a problem. I just wanted to fill the list with numbers >= m. - Matina
@Mitchel0022 I think you are wrong. The vertical array flags the identity of the cell of the respective column in the preceding line of the input matrix. The approach is feasible since one only needs to track a change of symbols when sweeping along a column or a line. vertical entries hold the index of the previous line and are updated whenever a h-aligned domino is encountered. If it doesn't, the vertical entry 'lags behind' henceforth, triggering another increment at the next '-'. vertical is initialised with the number of lines, a value that can never be a legal identity marker. - collapsar

2 Answers

1
votes

So it sounds like this is more of a problem to do with finding out what the question is saying rather than the code, which given the assumption that each domino can only know the ones directly next to them and facing the same direction is not particularly difficult. Is it possible that the question is actually more complex, and knocking over a domino between two similar facing domino could allow a path for the dominoes to hit each other?

For instance:

3 3
|-|

Could have output

2

Because, knocking the middle domino over first allows to knock the left domino into the right one.

0
votes

If you transform your initial "matrix" in a string you can then count the number of occurence of -| to find how many vertical push you need to do.

And then you can do the same on the columns by using the occurences of |-.

Something like:

import re

matrix = (
    "|||-"
    "||--"
    "||--"
)
# Size of matrix
x = 3
y = 4
min_push = 0

# By line
regline = re.compile("-\|")
for i in range(0, x*y, y):
    current_line = matrix[i:i+y]
    if current_line[0] == "|":
        min_push += 1
    min_push += len(re.findall(regline, current_line))

# Turn the "matrix" string by 90° so columns become lines
matrix_tmp = [ "" for i in range(y) ]
for i in range(x*y):
    matrix_tmp[i%y] += matrix[i]

matrix = "".join(matrix_tmp)

# By column
regline = re.compile("\|-")
for i in range(0, x*y, x):
    current_col = matrix[i:i+x]
    if current_col[0] == "-":
        min_push += 1
    min_push += len(re.findall(regline, current_col))

print(min_push)