diff options
Diffstat (limited to 'solutions/py/d17.py')
| -rw-r--r-- | solutions/py/d17.py | 235 |
1 files changed, 235 insertions, 0 deletions
diff --git a/solutions/py/d17.py b/solutions/py/d17.py new file mode 100644 index 0000000..1807431 --- /dev/null +++ b/solutions/py/d17.py @@ -0,0 +1,235 @@ +import intcode +from collections import deque +import heapq as heap +import time + +def draw(view, intersections={}, robot=None, direction=None): + min_x=max_x=min_y=max_y = 0 + for p in view: + min_x = min(p[0], min_x) + max_x = max(p[0], max_x) + min_y = min(p[1], min_y) + max_y = max(p[1], max_y) + s = "" + for y in range(min_y, max_y+1): + s += "\n" + for x in range(min_x, max_x+1): + point = (x, y) + if robot is not None and point == robot: + if direction == 0: + s += ">" + elif direction == 1: + s += "v" + elif direction == 2: + s += "<" + elif direction == 3: + s += "^" + else: + s += "D" + elif point in intersections: + s += "O" + elif point in view: + s += view[point] * 1 + else: + s += " " * 1 + return s + +def neighbours(p): + return [(p[0]+1, p[1]), (p[0]-1, p[1]), \ + (p[0], p[1]+1), (p[0], p[1]-1)] + +c = intcode.Computer([int(x) for x in open("../input/17", "r").readlines()[0].split(",")]) + +view = {} +scaffolds = [] +buffer = "" +x=y = 0 +while not c.SIG_HALT: + c.step() + if c.SIG_INPUT: + print("input??") + break + if c.SIG_OUTPUT: + if c.output == 10: + y += 1 + x = 0 + elif c.output == 35: + view[(x,y)] = "#" + scaffolds.append((x,y)) + x += 1 + elif c.output == 46: + view[(x,y)] = "." + x += 1 + else: + view[(x,y)] = "#" + scaffolds.append((x,y)) + robot = (x,y) + if c.output == 60: # < + direction = 2 + elif c.output == 62: # > + direction = 0 + elif c.output == 94: # ^ + direction = 3 + elif c.output == 86 or c.output == 118: # V or v + direction = 1 + else: + print("????????????????") + break + x += 1 + buffer = "" + c.output = None + c.SIG_OUTPUT = False +print(draw(view)) + +intersections = set() +al_sum = 0 +for s in scaffolds: + ns = 0 + for n in neighbours(s): + if n in scaffolds: + ns += 1 + if ns == 4: + intersections.add(s) + al_sum += s[0] * s[1] +print(intersections) +print(draw(view, intersections=intersections, robot=robot, direction=direction)) +print(al_sum) + +x,y = robot +visited = set() +left = set() +for s in scaffolds: + left.add(s) + +def get_infront(robot, direction): + dx=dy = 0 + if direction == 0: + dx = 1 + elif direction == 1: + dy = 1 + elif direction == 2: + dx = -1 + else: + dy = -1 + return (robot[0]+dx, robot[1]+dy) + +def get_behind(robot, direction): + dx=dy = 0 + if direction == 0: + dx = -1 + elif direction == 1: + dy = -1 + elif direction == 2: + dx = 1 + else: + dy = 1 + return (robot[0]+dx, robot[1]+dy) + +def get_turn(robot, direction, point): + dx = point[0] - robot[0] + dy = point[1] - robot[1] + if dx == 1: + turn_direction = 0 + elif dy == 1: + turn_direction = 1 + elif dx == -1: + turn_direction = 2 + else: + turn_direction = 3 + if direction == turn_direction: + return None + if (direction + 1) % 4 == turn_direction: + return "R" + elif (direction - 1) % 4 == turn_direction: + return "L" + else: + return False + +def get_direction(direction, turn): + if turn == "L": + return (direction - 1) % 4 + elif turn == "R": + return (direction + 1) % 4 + else: + return False + +def get_turnable_points(scaffolds, robot, direction): + valid = set() + for n in neighbours(robot): + if n in scaffolds and n != get_behind(robot, direction): + valid.add(n) + return list(valid) + +''' +For each path, take steps until a wall is reached. For each intersection on the +way, queue new searches with turns (but don't start them, FIFO). When a wall is +reached, check if each point has been visited. If all points have been visited, +done. Else, + +Structure of a deque-element: +Each search-element consists of a single tuple. The tuple contains + - The robot's position + - The robot's direction (after turning) + - The instruction-set up to that point + - The current WIP instruction + - All points that have been visited (as a set) + +Structure of the instruction-set: +The instruction-set consists of a list of tuples. The tuples contain + - A turn-instruction + - The number of steps to take (after turning) +For example: +[(R,8), (R,8), (R,4), (R,4), (R,8)] +''' + +current = None +direction = 2 +paths = deque() +paths.append((robot, direction, [], ["L", 0], set())) +while True: + #print("considering", len(paths), "paths") + if current is None: + #print("popping") + current = paths.popleft() + #print("now", current) + robot = current[0] + direction = current[1] + instruction_set = current[2] + wip_instruction = current[3] + visited = current[4] + if len(visited) == len(scaffolds): + print("len(visited) == len(scaffolds)") + instruction_set.append(wip_instruction) + print(instruction_set) + break + + if get_infront(robot, direction) not in scaffolds: + #print("wall") + # wall in front. save + instruction_set.append(wip_instruction) + avail_points = get_turnable_points(scaffolds, robot, direction) + if len(avail_points) != 1: + print("len(avail_direction != 2") + print(instruction_set) + break + wip_instruction = [get_turn(robot, direction, avail_points[0]), 0] + direction = get_direction(direction, get_turn(robot, direction, avail_points[0])) + paths.append((robot, direction, instruction_set, wip_instruction, visited)) + #print("appended. now", paths) + current = None + else: # wall not in front + ''' + if robot in intersections: + # queue intersections + new_instruction_set = instruction_set.copy() + new_instruction_set.append(wip_instruction) + paths.append((robot, get_direction(direction, "L"), \ + new_instruction_set, ["L", 0], visited)) + paths.append((robot, get_direction(direction, "R"), \ + new_instruction_set, ["R", 0], visited)) + ''' + # take step + robot = get_infront(robot, direction) + #print("stepped", robot) + visited.add(robot) + wip_instruction[1] += 1 |