# wpf kolos 3 20.01.2020 jmolinski

chodnik.py

# wpf kolos 3 20.01.2020 jmolinski

BENCHMARK = False


def add_if_valid(n, m, t, q, d, x, y, c, v):
    if x < 0 or y < 0 or y >= m or x >= n:
        return

    if t[x][y] == False:
        return

    if c > d[x][y] + 1:
        return

    q.append((x, y, c, v))

    if c < d[x][y]:
        d[x][y] = c


def przeszukaj(t, n, m):
    q = []
    d = [list(n * m for i in range(m)) for j in range(n)]

    add_if_valid(n, m, t, q, d, 0, 1, 1, (0, 1))
    add_if_valid(n, m, t, q, d, 1, 0, 1, (1, 0))

    if BENCHMARK:
        counter = 0

    while q:
        if BENCHMARK:
            counter += 1

        x, y, c, v = q.pop(0)

        def cost(nv):
            return 0 if nv == v else 1

        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nv = (dx, dy)
            add_if_valid(n, m, t, q, d, x + dx, y + dy, c + cost(nv), nv)

    if BENCHMARK:
        print(counter, n * m, int(100 * counter / (n * m)) / 100)

    if d[n - 1][m - 1] == n * m:
        return -1
    return d[n - 1][m - 1]


def chodnik(t):
    n, m = len(t), len(t[0])

    if t[0][0] == False or t[n - 1][m - 1] == False:
        return -1

    if n == m and n == 1:
        return 1

    return przeszukaj(t, n, m)


def process_data(d):
    # converts 0/1 strings to NEGATED false/true matrix
    # so 0 -> true, 1 -> false
    return [
        [not bool(int(x)) for x in r]
        for r in [row.strip() for row in d.split("\n")]
        if r
    ]


data_1 = """
    0001000
    0001010
    0000010
"""

assert chodnik(process_data(data_1)) == 5

data_2 = """
    00010010000
    10010010000
    00011000000
    00001010000
    01000010000
    01000000010
    01000000010
"""

assert chodnik(process_data(data_2)) == 6

data_3 = """
    0010010000
    1010010000
    0011000000
    0001010000
    0100010000
    0100000010
    0100000010
"""

data_4 = """
    0010010000
    1010010000
    0011000000
    0001010000
    0100010000
    0100000010
    0100000010
"""
assert chodnik(process_data(data_3)) == 8

data_4 = """
    100
    000
    000
"""

data_5 = """
    000
    000
    001
"""

data_6 = """
    000
    111
    000
"""

data_7 = """
    010
    010
    010
"""

data_8 = """
    000
    111
    000
"""

data_9 = """
    010
    100
    000
"""

assert chodnik(process_data(data_4)) == -1
assert chodnik(process_data(data_5)) == -1
assert chodnik(process_data(data_6)) == -1
assert chodnik(process_data(data_7)) == -1
assert chodnik(process_data(data_8)) == -1
assert chodnik(process_data(data_9)) == -1


data_10 = """
    0000
    0110
    0001
    0010
"""

assert chodnik(process_data(data_10)) == -1

data_11 = "0"
data_12 = "0000"
data_13 = """
    0
    0
    0
"""
data_14 = "1"
data_15 = "111"
data_16 = """
    0
    1
    0
"""

assert chodnik(process_data(data_11)) == 1
assert chodnik(process_data(data_12)) == 1
assert chodnik(process_data(data_13)) == 1
assert chodnik(process_data(data_14)) == -1
assert chodnik(process_data(data_15)) == -1
assert chodnik(process_data(data_16)) == -1

data_17 = """
    00
    10
"""

data_18 = """
    000
    010
    000
"""

data_19 = """
    0000
    0110
    0110
    0000
"""

data_20 = """
    0000
    0110
    0111
    0000
"""

data_21 = """
    0000
    0110
    0110
    1000
"""

assert chodnik(process_data(data_17)) == 2
assert chodnik(process_data(data_18)) == 2
assert chodnik(process_data(data_19)) == 2
assert chodnik(process_data(data_20)) == 2
assert chodnik(process_data(data_21)) == 2

data_22 = """
    0100010001000100010001001
    0001000100010001000100010
"""

data_23 = """
    0100010001000100010001000
    0001000100010001000100010
"""

data_24 = """
    0100010001000100010001000
    0001000100010001000100010
    0000000000010000000000010
    0000000000010000000000010
"""

assert chodnik(process_data(data_22)) == -1
assert chodnik(process_data(data_23)) == 25
assert chodnik(process_data(data_24)) == 9

print("All tests passed")