Она не займёт много времени, примерно час.
It won’t take long, about an hour.
Тестовое задание. На бесконечной координатной сетке находится муравей. Муравей может перемещатся на 1 клетку вверх (x,y+1), вниз (x,y-1), влево (x-1,y), вправо (x+1,y), по одной клетке за шаг. Клетки, в которых сумма цифр в координате X плюс сумма цифр в координате Y больше чем 25 недоступны муравью. Например, клетка с координатами (59, 79) недоступна, т.к. 5+9+7+9=30, что больше 25. Сколько cклеток может посетить муравей если его начальная позиция (1000,1000), (включая начальную клетку). Прислать ответ и решение в виде числа клеток и исходного текста программы на языке Python решающей задачу.
Test. On an infinite coordinate grid there is ant. The ant can move 1 cell up (x,y+1), down (x,y-1), left (x-1,y), right (x+1,y), one cell at a time step. Cells in which the sum of the digits in the X coordinate plus the sum of the digits in Y coordinates greater than 25 are inaccessible to the ant. For example, a cell with coordinates (59, 79) is not available, because 5+9+7+9=30, which more than 25. How many cells can an ant visit if its initial position (1000,1000), (including the starting cell). Send a reply and solution in the form of the number of cells and the source text of the program in the language Python solving the problem.
| ^ | |||
| < | m | > | |
| v | |||
(59, 79)
sum(split(x) + split(y)) <= 25
999 + 1000 = 28
No information about ability to repeat steps, that is why we assume that an ant is able to pass it’s path repetedly.
c = 0
for x in range(1000,1100):
for y in range(1000,1100):
s = sum([int(x) for x in str(x)]) + sum([int(y) for y in str(y)])
print([int(x) for x in str(x)], [int(y) for y in str(y)], s)
if s <=25:
c+=1
print(c)[1, 0, 0, 0] [1, 0, 0, 0] 2 [1, 0, 0, 0] [1, 0, 0, 1] 3 [1, 0, 0, 0] [1, 0, 0, 2] 4 [1, 0, 0, 0] [1, 0, 0, 3] 5 [1, 0, 0, 0] [1, 0, 0, 4] 6 ... [1, 0, 9, 9] [1, 0, 8, 8] 36 [1, 0, 9, 9] [1, 0, 8, 9] 37 [1, 0, 9, 9] [1, 0, 9, 0] 29 [1, 0, 9, 9] [1, 0, 9, 1] 30 [1, 0, 9, 9] [1, 0, 9, 2] 31 [1, 0, 9, 9] [1, 0, 9, 3] 32 [1, 0, 9, 9] [1, 0, 9, 4] 33 [1, 0, 9, 9] [1, 0, 9, 5] 34 [1, 0, 9, 9] [1, 0, 9, 6] 35 [1, 0, 9, 9] [1, 0, 9, 7] 36 [1, 0, 9, 9] [1, 0, 9, 8] 37 [1, 0, 9, 9] [1, 0, 9, 9] 38 8240
https://github.com/pranav1246/Ant-Food-Reachability/blob/main/Problem.pdf
def find_path_bfs(s, e, grid):
queue = [(s, [])] # start point, empty path
while len(queue) > 0:
node, path = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
return path
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if not is_visited(item, v):
queue.append((item, path[:]))
return None # no path foundhttps://www.geeksforgeeks.org/shortest-path-in-grid-with-obstacles/
- 0 - it is free to go
- 2 - 2, that means it is free and if you step into this cell, you can pass through any adjacent cell of it that contains obstacles
- 1 - obstacle
- n = 3, m = 4 - start point
from collections import deque
def possiblePath(n, m, grid):
# Check if the source or destination cell is blocked
if grid[0][0] == 1 or grid[n - 1][m - 1] == 1:
# Return -1 to indicate no path
return -1
# Create a queue to store the cells to explore
q = deque()
# Add the source cell to the queue and mark its distance as 0
q.append((0, 0))
# Define two arrays to represent the four directions of movement
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# Create a 2D list to store the distance of each cell from the source
dis = [[-1 for _ in range(m)] for _ in range(n)]
# Set the distance of the source cell as 0
dis[0][0] = 0
# Loop until the queue is empty or the destination is reached
while q:
# Get the front cell from the queue and remove it
p = q.popleft()
# Loop through the four directions of movement
for i in range(4):
# Calculate the coordinates of the neighboring cell
x = p[0] + dx[i]
y = p[1] + dy[i]
# Check if the neighboring cell is inside the grid and not visited before
if 0 <= x < n and 0 <= y < m and dis[x][y] == -1:
# Check if the neighboring cell is free or special
if grid[x][y] == 0 or grid[x][y] == 2:
# Set the distance of the neighboring cell as one more than the current cell
dis[x][y] = dis[p[0]][p[1]] + 1
# Add the neighboring cell to the queue for further exploration
q.append((x, y))
# Check if the neighboring cell is special
if grid[x][y] == 2:
# Loop through the four directions of movement again
for j in range(4):
# Calculate the coordinates of the adjacent cell
xx = x + dx[j]
yy = y + dy[j]
# Check if the adjacent cell is inside the grid
if 0 <= xx < n and 0 <= yy < m:
# Check if the adjacent cell is blocked
if grid[xx][yy] == 1:
# Change the adjacent cell to free
grid[xx][yy] = 0
# Return the distance of the destination cell from the source
return dis[n - 1][m - 1]
# Driver code
n = 3
m = 4
grid = [
[0, 1, 2, 1],
[2, 1, 0, 0],
[0, 2, 1, 0]
]
result = possiblePath(n, m, grid)
# Function Call
print(result)5
test reachability:
- create grid with allowed and blocked elements
- check reachability
import time
import numpy as np
grid = np.zeros((1000, 1000))+1
c = 0
start_time = time.time()
for i, x in enumerate(range(1000,2000)):
for j, y in enumerate(range(1000,2000)):
s = sum([int(x) for x in str(x)]) + sum([int(y) for y in str(y)])
if s <=5:
grid[i,j]=0
for i, x in enumerate(range(1000,2000)):
for j, y in enumerate(range(1000,2000)):
if grid[i,j]==0:
if possiblePath(i+1, j+1, grid) >= 0:
c+=1
print("--- %s seconds ---" % (time.time() - start_time))
print(c)--- 5.115052938461304 seconds --- 10
import time
import numpy as np
grid = np.zeros((1000, 1000))+1
c = 0
# grid = []
maxi = 15
start_time = time.time()
for i, x in enumerate(range(1000,2000)):
for j, y in enumerate(range(1000,2000)):
s = sum([int(x) for x in str(x)]) + sum([int(y) for y in str(y)])
if s <= maxi:
grid[i,j]=0
# grid
# print(grid)
for i, x in enumerate(range(1000,2000)):
for j, y in enumerate(range(1000,2000)):
# print(i,j,possiblePath(i+1, j+1, grid))
if grid[i,j]==0:
# print(i+1, j+1, possiblePath(i+1, j+1, grid))
if possiblePath(i+1, j+1, grid) >= 0:
c+=1
# s = sum([int(x) for x in str(x)]) + sum([int(y) for y in str(y)])
# print([int(x) for x in str(x)], [int(y) for y in str(y)], s)
# if s <=25:
# c+=1
print("--- %s seconds ---" % (time.time() - start_time))
print(c)--- 110.37837839126587 seconds --- 1260
import time
import numpy as np
grid = np.zeros((1000, 1000))+1
c = 0
maxi = 20
start_time = time.time()
for i, x in enumerate(range(1000,2000)):
for j, y in enumerate(range(1000,2000)):
s = sum([int(x) for x in str(x)]) + sum([int(y) for y in str(y)])
if s <= maxi:
grid[i,j]=0
# grid
for i, x in enumerate(range(1000,2000)):
for j, y in enumerate(range(1000,2000)):
if grid[i,j]==0:
# print(i+1, j+1, possiblePath(i+1, j+1, grid))
if possiblePath(i+1, j+1, grid) >= 0:
c+=1
print("--- %s seconds ---" % (time.time() - start_time))
print(c)--- 2847.934205055237 seconds --- 12175
from pandas import read_csv
from matplotlib import pyplot
import matplotlib.pyplot as plt
from sklearn.preprocessing import PolynomialFeatures
import numpy as np
from sklearn.linear_model import Ridge
poly = PolynomialFeatures(degree=4, include_bias=False)
ridge = Ridge(alpha=0.006)
x = [5,15,20]
y = [5/60,110/60, 2847/60] # time
x_appr = np.linspace(5.0, 25.0, num=10)
x_poly = poly.fit_transform(np.array(x).reshape(-1,1))
ridge.fit(x_poly, y)
pyplot.scatter(x, y)
y = ridge.predict(x_poly)
x_poly = poly.fit_transform(np.array(x_appr).reshape(-1,1))
y = ridge.predict(x_poly)
pyplot.plot(x_appr, y)
pyplot.scatter([25], y[-1])
pyplot.ylabel("time in minutes")
pyplot.title("interpolation of time for 25 max: "+ str(round(y[-1], 2)))
plt.savefig('./autoimgs/time_appr.png')
plt.close()
from pandas import read_csv
from matplotlib import pyplot
import matplotlib.pyplot as plt
from sklearn.preprocessing import PolynomialFeatures
import numpy as np
from sklearn.linear_model import Ridge
poly = PolynomialFeatures(degree=4, include_bias=False)
ridge = Ridge(alpha=0.006)
x = [5,15,20]
y = [10,1260, 12175] # result
x_appr = np.linspace(5.0, 25.0, num=10)
x_poly = poly.fit_transform(np.array(x).reshape(-1,1))
ridge.fit(x_poly, y)
pyplot.scatter(x, y)
y = ridge.predict(x_poly)
x_poly = poly.fit_transform(np.array(x_appr).reshape(-1,1))
y = ridge.predict(x_poly)
pyplot.plot(x_appr, y)
pyplot.scatter([25], y[-1])
pyplot.ylabel("time in minutes")
pyplot.title("interpolation of result for 25 max: "+ str(round(y[-1], 2)))
plt.savefig('./autoimgs/result_appr.png')
plt.close()
We solved task for mas sum of numbers of 20, the answer is 12175. It tooks 47 minutes to calcuate, while the task was for 1 hour as was said.
We took BFS (Breadth-First Search) for check of reachability for cell by ant.
We used pandas, numpy, sklearn and matplotlib.
1 CPU with 2000 MHZ was used.
Interpolation of computing time is 180 minutes or 3 hours, for 25 max sum.
Interpolation of result count of grid cell is 42166, for 25 max sum.
Final answer is 42166.
Мы решили задачу для суммы чисел 20, ответ 12175. Это на расчет ушло 47 минут, при этом задача была на 1 час как и было сказал.
Мы использовали BFS (Breadth-First Search) для проверки достижимости ячейки муравьем.
Мы использовали pandas, numpy, sklearn и matplotlib.
Был использован 1 процессор с частотой 2000 МГц.
Для максимальной суммы 25 это займет примерно 180 минут или 3 часа.
Для 25 максимум результат количество ячеек сетки составляет примерно 42166.
Окончательный ответ: 42166.