Sean McLemon | Advent of Code

2018-12-06 - Chronal Coordinates

(original .ipynb)

testInput = (
    (1, 1),
    (1, 6),
    (8, 3),
    (3, 4),
    (5, 5),
    (8, 9)
)

realInput = (
	(46, 246),
	(349, 99),
	(245, 65),
	(241, 253),
	(127, 128),
	(295, 69),
	(205, 74),
	(167, 72),
	(103, 186),
	(101, 242),
	(256, 75),
	(122, 359),
	(132, 318),
	(163, 219),
	(87, 309),
	(283, 324),
	(164, 342),
	(255, 174),
	(187, 305),
	(145, 195),
	(69, 266),
	(137, 239),
	(241, 232),
	(97, 319),
	(264, 347),
	(256, 214),
	(217, 47),
	(109, 118),
	(244, 120),
	(132, 310),
	(247, 309),
	(185, 138),
	(215, 323),
	(184, 51),
	(268, 188),
	(54, 226),
	(262, 347),
	(206, 260),
	(213, 175),
	(302, 277),
	(188, 275),
	(352, 143),
	(217, 49),
	(296, 237),
	(349, 339),
	(179, 309),
	(227, 329),
	(226, 346),
	(306, 238),
	(48, 163)
)

# Part 1

# for the testInput the largest area is 17

def manhattan_distance(p, q):
    px = p[0]
    py = p[1]
    
    qx = q[0]
    qy = q[1]
    
    return abs(px - qx) + abs(py - qy)

def initialiseProblem(pointLookup, problemInput):
    # assign each point an ID and store in "points"
    for point_id, p in enumerate(problemInput):
        pointLookup[point_id] = p
    
    max_coord = 0
    
    for point in problemInput:
        x = point[0]
        y = point[1]
        
        if x > max_coord: 
            max_coord = x
        if y > max_coord:
            max_coord = y
        
    grid = []
    for i in range(max_coord + 1):
        grid.append([-1] * max_coord)
        
    return grid

points = {}
g = initialiseProblem(points, realInput)

# calculate distances on grid
for y, col in enumerate(g):
    for x, row in enumerate(col):
        closest_id = -1
        closest_distance = None
        
        for point_id in points:
            current_distance = manhattan_distance(points[point_id], (x, y))
            if closest_distance is None or current_distance < closest_distance:
                closest_distance = current_distance
                closest_id = [ point_id ]
            elif current_distance == closest_distance:
                closest_id.append(current_distance)
                
        g[y][x] = closest_id

        
# filter out those equally far away
for y, col in enumerate(g):
    for x, row in enumerate(col):
        if len(g[y][x]) > 1:
            g[y][x] = None
        else:
            g[y][x] = g[y][x][0] # lol

# filter out those with infinite length - those at the edges
infinite_length_list = []
for y, col in enumerate(g):
    for x, row in enumerate(col):
        if x == 0 or y == 0 or x == len(col)-1 or y == len(col)-1:
            infinite_length_list.append(g[y][x])
            g[y][x] = None
            
infinite_length_set = set(infinite_length_list)


# now loop through the points again, count their sizes
sizes = {}
for y, col in enumerate(g):
    for x, row in enumerate(col):
        point_id = g[y][x]
        
        if point_id in infinite_length_set:
            continue
    
        if point_id in sizes:
            sizes[point_id] += 1
        else:
            sizes[point_id] = 1

sorted([ sizes[point_id] for point_id in sizes ], key= lambda n: -n )[0]

3449

# Part 2

# for test input the size of region is 16
points = {}
g = initialiseProblem(points, realInput)

# calculate distances on grid
total_points = 0
for y, col in enumerate(g):
    for x, row in enumerate(col):
        total_distance = 0
        
        for point_id in points:
            total_distance += manhattan_distance(points[point_id], (x, y))
                
        if total_distance < 10000:
            total_points += 1

print(total_points)

44868