advent-of-code-2018/6-2.py at master · sebbele/advent-of-code-2018 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#!/usr/bin/env python

from pprint import pprint

input = []
with open('6_input.txt') as f:
    for line in f:
        input.append(line.replace('\n', ''))

#input = [   '1, 1',
#            '1, 6',
#            '8, 3',
#            '3, 4',
#            '5, 5',
#            '8, 9' ]

def inputToDict(input):
    input_dict = {}
    for i in range(len(input)):
        y = input[i].replace(',', '').split()[1]
        x = input[i].replace(',', '').split()[0]
        input_dict[i] = [int(y),int(x)]
    return input_dict


def generateGrid(input):
    grid = []
    y_values = []
    x_values = []
    for coords in input.values():
        y_values.append(int(coords[0]))
        x_values.append(int(coords[1]))
    max_y = int(max(y_values)) + 2
    max_x = int(max(x_values)) + 2
    for y in range(max_y):
        grid.append(['.'] * max_x)
    return grid

def initialPopulate(grid, input_dict):
    for key in input_dict:
        y = int(input_dict[key][0])
        x = int(input_dict[key][1])
        grid[y][x] = key
    return grid

def propagateGrid(grid, input_dict):
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            coords = [y, x]
            if grid[y][x] != '.':
                continue
            else:
                grid[y][x] = getManhattan(grid, coords, input_dict)
                continue
    return grid

def getManhattan(grid, coords, candidates):
    total_hops = 0
    for candidate in candidates:
        manhattan_distance = abs(candidates[candidate][1] - coords[1]) + abs(candidates[candidate][0] - coords[0])
        total_hops += manhattan_distance
    return total_hops

#def calcArea(grid, input_dict):
#    # remove candidates with infinite area
#    # top
#    infinite_ids = [x for x in grid[0] if x != '.']
#    # bottom
#    infinite_ids = infinite_ids + [x for x in grid[-1] if x != '.']
#    #left
#    infinite_ids = infinite_ids + [grid[i][0] for i in range(len(grid)) if grid[i][0] != '.']
#    # right
#    infinite_ids = infinite_ids + [grid[i][-1] for i in range(len(grid)) if grid[i][-1] != '.']
#    count = []
#    for key in input_dict:
#        count.append(0)
#        if key in infinite_ids:
#            continue
#        else:
#            for y in grid:
#                count[key] = count[key] + y.count(key)
#    res = [ count.index(max(count)), max(count) ]
#    return res

def findSafeSpace(grid, input_dict, threshold):
    res = 0
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            coords = [y, x]
            tot = getManhattan(grid, coords, input_dict)
            if tot < threshold:
                grid[coords[0]][coords[1]] = '#'
                res += 1
    return grid, res

if __name__ == '__main__':
    input_dict = inputToDict(input)
    grid = generateGrid(input_dict)
    grid = initialPopulate(grid, input_dict)
    grid, res = findSafeSpace(grid, input_dict, 10000)
    print(res)