Skip to content

Instantly share code, notes, and snippets.

@akkartik
Last active December 17, 2019 18:39
Show Gist options
  • Save akkartik/722a6e09f0999dbdc546d473b5c927bc to your computer and use it in GitHub Desktop.
Save akkartik/722a6e09f0999dbdc546d473b5c927bc to your computer and use it in GitHub Desktop.
import sys
def parse(inst):
dir, mag = inst[0], int(inst[1:])
if dir == 'U': return (0, -mag)
if dir == 'D': return (0, mag)
if dir == 'L': return (-mag, 0)
if dir == 'R': return (mag, 0)
raise 'bad inst {}'.format(inst)
def add(a, b):
return (a[0]+b[0], a[1]+b[1])
def sign(x):
if x == 0: return 0
if x > 0: return 1
return -1
def dir(x, y):
return (sign(x), sign(y))
def mag(x, y):
if x == 0: return abs(y)
if y == 0: return abs(x)
raise "non-manhattan line"
def mul(v, n):
return tuple(x*n for x in v)
# little non-idiomatic: excludes 'init', but not final point
def draw(init, vector):
n = mag(*vector)
inc = dir(*vector)
return [add(init, mul(inc, i)) for i in range(1, n+1)]
def add_all(init, vectors):
result = init
for vector in vectors:
result = add(result, vector)
return result
def draw_all(init, vectors):
return [p for i in range(0, len(vectors))
for p in draw(add_all(init, vectors[0:i]),
vectors[i])]
def manhattan_distance(x):
return abs(x[0]) + abs(x[1])
line1 = list(map(parse, sys.stdin.readline().split(',')))
line2 = list(map(parse, sys.stdin.readline().split(',')))
line1_points = set(draw_all([0, 0], line1))
line2_points = set(draw_all([0, 0], line2))
print(min(line1_points.intersection(line2_points), key=manhattan_distance))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment