Matrix A, consisting of N rows and N columns of non-negative integers, is given. Rows are numbered from 0 to N−1 (from top to bottom). Columns are numbered from 0 to N−1 (from left to right). We would like to find a path that starts at the upper-left corner (0, 0) and, moving only right and down, finishes at the bottom-right corner (N−1, N−1). Then, all the numbers on this path will be multiplied together.
Find a path such that the product of all the numbers on the path contain the minimal number of trailing zeros. We assume that 0 has 1 trailing zero.
Write a function:
def solution(A)
that, given matrix A, returns the minimal number of trailing zeros.
Examples:
1. Given matrix A below:
the function should return 1. The optimal path is: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3) → (3,3). The product of numbers 2, 10, 1, 4, 2, 1, 1 is 160, which has one trailing zero. There is no path that yields a product with no trailing zeros.
2. Given matrix A below:
the function should return 2. One of the optimal paths is: (0,0) → (1,0) → (1,1) → (1,2) → (2,2) → (3,2) → (3,3). The product of numbers 10, 1, 1, 1, 10, 1, 1 is 100, which has two trailing zeros. There is no path that yields a product with fewer than two trailing zeros.
3. Given matrix A below:
the function should return 1. One of the optimal paths is: (0,0) → (0,1) → (1,1) → (1,2) → (2,2). The product of numbers 10, 10, 0, 10, 10 is 0, which has one trailing zero. There is no path that yields a product with no trailing zeros.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..500];
- each element of matrix A is an integer within the range [0..1,000,000,000].
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}".format(self.level, self.value)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
0 T 0.00014591217041015625
0 T 0.0002601146697998047
0 T 0.00018525123596191406
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}".format(self.level, self.value)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
0 T 0.00012826919555664062
0 T 0.00012135505676269531
0 T 8.916854858398438e-05
function result: 0
0 T 0.0002803802490234375
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}".format(self.level, self.value)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
0 T 0.00015687942504882812
0 T 0.00020122528076171875
0 T 0.0001125335693359375
function result: 0
0 T 0.0021910667419433594
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
0 T 0.00019860267639160156
0 T 0.00019168853759765625
0 T 0.00010752677917480469
function result: 0
0 T 0.0022745132446289062
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
0 T 0.0001556873321533203
0 T 0.0001976490020751953
0 T 0.00010991096496582031
function result: 0
0 T 0.002205371856689453
function result: 1
0 T 0.0001544952392578125
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return 0x1f"{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return 0x1f1f1f1f ^ self.level ^ self.value ^ self.x ^ self.y
#"{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return 0x1f1f1f1f ^ self.level ^ self.value ^ self.x ^ self.y
#"{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
0 T 0.00017786026000976562
Invalid result type, int expected, <class 'float'> found.stdout:
0 T 5.5789947509765625e-05
0 T 0.00015163421630859375
function result: 0
0 T 0.0008313655853271484
Invalid result type, int expected, <class 'float'> found.stdout:
0 T 0.00010609626770019531
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x,)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
0 T 0.00015473365783691406
0 T 0.00019621849060058594
0 T 0.00010752677917480469
function result: 0
0 T 0.0021932125091552734
function result: 1
0 T 0.00011396408081054688
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
c = 0
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
0 T 0.00019216537475585938
0 T 0.00019502639770507812
0 T 0.00010728836059570312
function result: 0
0 T 0.002272367477416992
function result: 1
0 T 0.00011444091796875
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
print(c)
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
Traceback (most recent call last): File "exec.py", line 132, in <module> main() File "exec.py", line 94, in main result = solution( A ) File "/tmp/solution.py", line 69, in solution n = solve(A) File "/tmp/solution.py", line 63, in solve print(c) NameError: name 'c' is not defined
Traceback (most recent call last): File "exec.py", line 132, in <module> main() File "exec.py", line 94, in main result = solution( A ) File "/tmp/solution.py", line 69, in solution n = solve(A) File "/tmp/solution.py", line 63, in solve print(c) NameError: name 'c' is not defined
Traceback (most recent call last): File "exec.py", line 132, in <module> main() File "exec.py", line 94, in main result = solution( A ) File "/tmp/solution.py", line 69, in solution n = solve(A) File "/tmp/solution.py", line 63, in solve print(c) NameError: name 'c' is not defined
Traceback (most recent call last): File "exec.py", line 132, in <module> main() File "exec.py", line 94, in main result = solution( A ) File "/tmp/solution.py", line 69, in solution n = solve(A) File "/tmp/solution.py", line 63, in solve print(c) NameError: name 'c' is not defined
Traceback (most recent call last): File "exec.py", line 132, in <module> main() File "exec.py", line 94, in main result = solution( A ) File "/tmp/solution.py", line 69, in solution n = solve(A) File "/tmp/solution.py", line 63, in solve print(c) NameError: name 'c' is not defined
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
return m
def solution(A):
import time
t = time.time()
n = solve(A)
print("T", time.time()-t)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
return m
def solution(A):
n = solve(A)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
return m
def solution(A):
n = solve(A)
return n
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
return m
def solution(A):
n = solve(A)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
return m
def solution(A):
n = solve(A)
return n
[[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3], [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]
[[2, 10, 10], [10, 1, 1], [1, 1, 1]]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
from collections import defaultdict, deque
def nzeros(n):
s1 = str(n)
s2 = s1.rstrip('0')
return len(s1) - len(s2)
class Node(object):
def __init__(self, x, y, level, value):
self.x = x
self.y = y
self.level = level
self.value = value
self.zeros = nzeros(value)
@property
def hsh(self):
return "{}:{}:{}{}".format(self.level, self.value, self.x, self.y)
def solve(A):
q = deque()
n = Node(0, 0, 0, A[0][0])
q.appendleft(n)
N = len(A) -1
m = math.inf
zpl = defaultdict(lambda: math.inf)
hashes = set([n.hsh])
while len(q) != 0:
n = q.pop()
x = n.x
y = n.y
lvl = n.level +1
if y == N and x == N:
if n.zeros < m:
m = n.zeros
continue
# can we go right?
if x < N:
right_value = A[y][x+1] * n.value
right_node = Node(x+1, y, lvl, right_value)
if right_node.hsh not in hashes and zpl[lvl] >= right_node.zeros:
q.appendleft(right_node)
hashes.add(right_node.hsh)
zpl[lvl] = right_node.zeros
# can we go down
if y < N:
down_value = A[y+1][x] * n.value
down_node = Node(x, y+1, lvl, down_value)
if down_node.hsh not in hashes and zpl[lvl] >= down_node.zeros:
hashes.add(down_node.hsh)
q.appendleft(down_node)
zpl[lvl] = down_node.zeros
return m
def solution(A):
n = solve(A)
return n
The following issues have been detected: timeout errors.
all elements in A are neither dividable by 2 or 5; length of A is close to 500
running time: >6.00 sec., time limit: 0.26 sec.
all elements in A are dividable by either power of 2 or 5; length of A is close to 500
running time: >6.00 sec., time limit: 0.29 sec.
tests with corner cases values, maximal A size
running time: >10.00 sec., time limit: 4.94 sec.
tests with defined result; length of A is close to 500
running time: 0.44 sec., time limit: 0.27 sec.
alternating diagonals consist of 2 or 5
running time: 5.89 sec., time limit: 3.52 sec.