from math import floor
from heapq import heappush, heappop
xs = [
"R1009", "U993", "L383", "D725", "R163", "D312", "R339", "U650", "R558",
"U384", "R329", "D61", "L172", "D555", "R160", "D972", "L550", "D801",
"L965", "U818", "L123", "D530", "R176", "D353", "L25", "U694", "L339",
"U600", "L681", "D37", "R149", "D742", "R762", "U869", "R826", "U300",
"L949", "U978", "L303", "U361", "R136", "D343", "L909", "U551", "R745",
"U913", "L566", "D292", "R820", "U886", "R205", "D431", "L93", "D71",
"R577", "U872", "L705", "U510", "L698", "U963", "R607", "U527", "L669",
"D543", "R690", "U954", "L929", "D218", "R490", "U500", "L589", "D332",
"R949", "D538", "R696", "U659", "L188", "U468", "L939", "U833", "L445",
"D430", "R78", "D303", "R130", "D649", "R849", "D712", "L511", "U745",
"R51", "U973", "R799", "U829", "R605", "D771", "L837", "U204", "L414",
"D427", "R538", "U116", "R540", "D168", "R493", "U900", "L679", "U431",
"L521", "D500", "L428", "U332", "L954", "U717", "L853", "D339", "L88",
"U807", "L607", "D496", "L163", "U468", "L25", "U267", "L759", "D898",
"L591", "U445", "L469", "U531", "R596", "D486", "L728", "D677", "R350",
"D429", "R39", "U568", "R92", "D875", "L835", "D841", "R877", "U178",
"L221", "U88", "R592", "U692", "R455", "U693", "L419", "U90", "R609",
"U672", "L293", "U168", "R175", "D456", "R319", "D570", "R504", "D165",
"L232", "D624", "L604", "D68", "R807", "D59", "R320", "D281", "L371",
"U956", "L788", "D897", "L231", "D829", "R287", "D798", "L443", "U194",
"R513", "D925", "L232", "U225", "L919", "U563", "R448", "D889", "R661",
"U852", "L950", "D558", "L269", "U186", "L625", "U673", "L995", "U732",
"R435", "U849", "L413", "D690", "L158", "D234", "R361", "D458", "L271",
"U90", "L781", "U754", "R256", "U162", "L842", "U927", "L144", "D62",
"R928", "D238", "R473", "U97", "L745", "U303", "L487", "D349", "L520",
"D31", "L825", "U385", "L133", "D948", "L39", "U62", "R801", "D664",
"L333", "U134", "R692", "U385", "L658", "U202", "L279", "D374", "R489",
"D686", "L182", "U222", "R733", "U177", "R94", "D603", "L376", "U901",
"R216", "D851", "L155", "D214", "L460", "U758", "R121", "D746", "L180",
"U175", "L943", "U146", "L166", "D251", "L238", "U168", "L642", "D341",
"R281", "U182", "R539", "D416", "R553", "D67", "L748", "U272", "R257",
"D869", "L340", "U180", "R791", "U138", "L755", "D976", "R731", "U713",
"R602", "D284", "L258", "U176", "R509", "U46", "R935", "U576", "R96",
"U89", "L913", "U703", "R833"
]
ys = [
"L1006", "D998", "R94", "D841", "R911", "D381", "R532", "U836", "L299",
"U237", "R781", "D597", "L399", "D800", "L775", "D405", "L485", "U636",
"R589", "D942", "L878", "D779", "L751", "U711", "L973", "U410", "L151",
"U15", "L685", "U417", "L106", "D648", "L105", "D461", "R448", "D743",
"L589", "D430", "R883", "U37", "R155", "U350", "L421", "U23", "R337",
"U816", "R384", "D671", "R615", "D410", "L910", "U914", "L579", "U385",
"R916", "U13", "R268", "D519", "R289", "U410", "L389", "D885", "L894",
"U734", "L474", "U707", "L72", "U155", "L237", "U760", "L127", "U806",
"L15", "U381", "L557", "D727", "L569", "U320", "L985", "D452", "L8",
"D884", "R356", "U732", "L672", "D458", "L485", "U402", "L238", "D30",
"R644", "U125", "R753", "U183", "L773", "U487", "R849", "U210", "L164",
"D808", "L595", "D668", "L340", "U785", "R313", "D72", "L76", "D263",
"R689", "U604", "R471", "U688", "R462", "D915", "R106", "D335", "R869",
"U499", "R190", "D916", "R468", "D882", "R56", "D858", "L143", "D741",
"L386", "U856", "R50", "U853", "R151", "D114", "L773", "U854", "L290",
"D344", "L23", "U796", "L531", "D932", "R314", "U960", "R643", "D303",
"L661", "D493", "L82", "D491", "L722", "U848", "L686", "U4", "L985",
"D509", "L135", "D452", "R500", "U105", "L326", "D101", "R222", "D944",
"L645", "D362", "L628", "U305", "L965", "U356", "L358", "D137", "R787",
"U728", "R967", "U404", "R18", "D928", "L695", "D965", "R281", "D597",
"L791", "U731", "R746", "U163", "L780", "U41", "L255", "U81", "L530",
"D964", "R921", "D297", "R475", "U663", "L226", "U623", "L984", "U943",
"L143", "U201", "R926", "U572", "R343", "U839", "R764", "U751", "R128",
"U939", "R987", "D108", "R474", "U599", "R412", "D248", "R125", "U797",
"L91", "D761", "L840", "U290", "L281", "U779", "R650", "D797", "R185",
"D320", "L25", "U378", "L696", "U332", "R75", "D620", "L213", "D667",
"R558", "U267", "L846", "U306", "R939", "D220", "R311", "U827", "R345",
"U534", "R56", "D679", "R48", "D845", "R898", "U8", "R862", "D960", "R753",
"U319", "L886", "D795", "R805", "D265", "R876", "U729", "R894", "D368",
"R858", "U744", "R506", "D327", "L903", "U919", "L721", "U507", "L463",
"U753", "R775", "D719", "R315", "U128", "R17", "D376", "R999", "D386",
"L259", "U181", "L162", "U605", "L265", "D430", "R35", "D968", "R207",
"U466", "R796", "D667", "R93", "U749", "L315", "D410", "R312", "U929",
"L923", "U260", "R638"
]
def to_coords(xs):
row, col = 0, 0
coords = []
for x in xs:
d, amt = x[0], int(x[1:])
if d == 'U':
for i in range(1, amt + 1):
coords.append((row + i, col))
row += amt
elif d == 'D':
for i in range(1, amt + 1):
coords.append((row - i, col))
row -= amt
elif d == 'L':
for i in range(1, amt + 1):
coords.append((row, col - i))
col -= amt
elif d == 'R':
for i in range(1, amt + 1):
coords.append((row, col + i))
col += i
return coords
def contains(row, col, d):
if row not in d:
return False
return col in d[row]
def intersections(xs, ys):
d = {}
ints = set()
for row, col in to_coords(xs):
if row in d:
d[row].add(col)
else:
d[row] = {col}
for row, col in to_coords(ys):
if contains(row, col, d):
ints.add((row, col))
return ints
def trace_to(coord, xs):
count = 0
for coord_x in to_coords(xs):
count += 1
if coord_x == coord:
return count
raise Exception("Intersection doesn't exist")
answer = []
for coord in intersections(xs, ys):
x = trace_to(coord, xs)
y = trace_to(coord, ys)
heappush(answer, x + y)
print(heappop(answer))
