Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic Programming solution in Clear category for Express Delivery by sawako.oono
from typing import List
import copy
def checkio(field_map: List[str]) -> str:
"""
Go with Dynamic Programming.
For each cell define a list:
[[min time w/load,last move for min time],[min time w/o load,last move for min time]]
Generally,
min time w/load = min(min time w/load of adjascent cells)+2 **exclude (0,0)**
min time w/o load = min(min time w/o load of adjascent cells)+1
When the cell is "B",
min time w/load = min(min(min time w/load of adjascent cells)+2 , min(min time w/o load of adjascent cells)+2)
min time w/o load = min(min(mintime w/o load of adjascent cells)+1 , min(min time w/load of adjascent cells)+3)
"""
w_y,w_x=len(field_map),len(field_map[0])
REFER = {
"L": (0, 1),
"R": (0, -1),
"U": (1, 0),
"D": (-1, 0)
}
graph=[]
for y in range(w_y):
row=[]
for x in range(w_x):
if x==0 and y==0:
row.append([[0,""],[None,None]])
else:
row.append([[None,None],[None,None]])
graph.append(row)
graph_copy=[]
while graph!=graph_copy:
graph_copy=copy.deepcopy(graph)
for y in range(w_y):
for x in range(w_x):
if field_map[y][x]=="W" :
pass
else:
load=[]
no_load=[]
for key,(Y,X) in REFER.items():
if 0<=Y+y<=w_y-1 and 0<=X+x<=w_x-1:
if not (y==0 and x==0):
if graph[Y+y][X+x][0]!=[None,None]:
load.append([graph[Y+y][X+x][0][0]+2,key])
if graph[Y+y][X+x][1]!=[None,None]:
no_load.append([graph[Y+y][X+x][1][0]+1,key])
if 0<=Y+y<=w_y-1 and 0<=X+x<=w_x-1 and field_map[y][x]=="B":
if not (y==0 and x==0):
if graph[Y+y][X+x][0]!=[None,None]:
no_load.append([graph[Y+y][X+x][0][0]+3,key+"B"])
if graph[Y+y][X+x][1]!=[None,None]:
load.append([graph[Y+y][X+x][1][0]+2,key+"B"])
if load==[]:
pass
else:
min_load=sorted(load,key=lambda x:x[0])[0]
graph[y][x][0]=min_load
if no_load==[]:
pass
else:
min_no_load=sorted(no_load,key=lambda x:x[0])[0]
graph[y][x][1]=min_no_load
y,x=w_y-1,w_x-1
load=0
ans=""
while True:
key=graph[y][x][load][1]
ans+=graph[y][x][load][1][::-1]
if y==0 and x==0 and load==0:
break
y_c=y
x_c=x
if key[-1]=="B":
load=1-load
key=key[:-1]
y_c+=REFER[key][0]
x_c+=REFER[key][1]
y=y_c
x=x_c
return ans[::-1]
if __name__ == '__main__':
print("Example:")
print(checkio(["S...", "....", "B.WB", "..WE"]))
#This part is using only for self-checking and not necessary for auto-testing
ACTIONS = {
"L": (0, -1),
"R": (0, 1),
"U": (-1, 0),
"D": (1, 0),
"B": (0, 0)
}
def check_solution(func, max_time, field):
max_row, max_col = len(field), len(field[0])
s_row, s_col = 0, 0
total_time = 0
hold_box = True
route = func(field[:])
for step in route:
if step not in ACTIONS:
print("Unknown action {0}".format(step))
return False
if step == "B":
if hold_box:
if field[s_row][s_col] == "B":
hold_box = False
total_time += 1
continue
else:
print("Stephan broke the cargo")
return False
else:
if field[s_row][s_col] == "B":
hold_box = True
total_time += 1
continue
n_row, n_col = s_row + ACTIONS[step][0], s_col + ACTIONS[step][1],
total_time += 2 if hold_box else 1
if 0 > n_row or n_row >= max_row or 0 > n_col or n_row >= max_col:
print("We've lost Stephan.")
return False
if field[n_row][n_col] == "W":
print("Stephan fell in water.")
return False
s_row, s_col = n_row, n_col
if field[s_row][s_col] == "E" and hold_box:
if total_time <= max_time:
return True
else:
print("You can deliver the cargo faster.")
return False
print("The cargo is not delivered")
return False
assert check_solution(checkio, 12, ["S...", "....", "B.WB", "..WE"]), "1st Example"
assert check_solution(checkio, 11, ["S...", "....", "B..B", "..WE"]), "2nd example"
print("Coding complete? Click 'Check' to earn cool rewards!")
July 5, 2021