Our next puzzle involves a number of two sided connections that have a number on each side. We're asked to build a chain of these in which each side of each link corresponds to the same number on the other side of the link. The chain's score is composed of the sum of the numbers and must begin with a zero.
I'm thinking we should do this one with recursion as building a chain can be thought of as building several smaller chains after adding some pieces. The general strategy I'll try to employ is this:
It also seems wise to store the actual chains as the second part of the problem might require us to know another property of the chains
import numpy as np
links = open('/Users/Sven/py_files/aoc_2017/day24_input.txt').readlines()
links = [x.replace('\n', '').split('/') for x in links]
for i in range(len(links)):
links[i] = [int(x) for x in links[i]]
links[:5]
So I thought a bit about which data structure to use for this problem and I thnk that the lists are just fine. Sets are not going to work because of the double sided connections and I don't really see any advantage of tuples as the connections are uordered.
I'm pretty sure we're going to want to write a function that can find all the links that contain a certain number:
# I'm not sure if I prefer this function to just find them or also return
# the corresponding other value... I guess I'll return
# a list of the indices and the other values. Start with this helper
def switch_link(num, link):
return(link[(link.index(num) + 1) % 2])
# I'm surprised I hadn't seen this enumerate function before but it seems very nice
# it returns a pair of lists with indices and the values of the argument. Here
# we use it to find the links that match the conditions of num being within the sublist
def find_links(links, num):
# locations and values
indices = [i for i, val in enumerate(links) if num in val]
sublists = [val for i, val in enumerate(links) if num in val]
switches = [switch_link(num, sublist) for sublist in sublists]
return(indices, switches)
find_links(links, 31)
So this is telling us that at indices 0, 41, 46, and 55 there is a 31 in those links and the corresponding value at those positions are 32, 46, 7, and 11.
Let's try to get into the details of the function we need to write now.
def find_subchains(links, open_end):
# First we find all of the possible connections
indices, open_ends = find_links(links, open_end)
# If there are none, we return None
if len(indices) == 0:
return(None)
# set up the return value:
return_list = []
# Now loop through them all, call find_subchains
for ind, end in zip(indices, open_ends):
# Identify the linke we're adding to the chain:
used_link = links[ind]
# make a copy of the links without the specific one
links_reduced = links.copy()
del links_reduced[ind]
subchains = find_subchains(links_reduced, end)
# if we found terminal points:
#print('Chain used:', used_link, '\n\nSubchains:', subchains)
if subchains is None:
return_list.append([used_link])
# otherwise we found some longer subchain, append the used link to it
else:
for i in range(len(subchains)):
subchains[i].append(used_link)
return_list.append(subchains[i])
return(return_list)
test = [[0,1], [1, 2], [2, 3], [3, 4], [3, 6], [2, 7], [8, 9]]
find_subchains(test[1:], 1)
This seems to be working nicely. Now we'll do it with the whole set:
start_inds, start_vals = find_links(links, 0)
all_chains = []
for ind, val in zip(start_inds, start_vals):
smaller_links = links.copy()
del smaller_links[ind]
chains = find_subchains(smaller_links, val)
for i in range(len(chains)):
chains[i].append(links[ind])
all_chains += chains
all_chains[:2]
Now we need to flatten these out and sum them. I think this might best be accomplished by using np.array
s and the axes sum.
sums = [np.sum(np.array(x)) for x in all_chains]
max(sums)
As predicted, having the literal bridges will come in handy. Here we need to figure out what the strength of the longest bridge is in the set. The strongest one might not be the longest so we'll first check their lengths:
max_len = max([len(x) for x in all_chains])
# strengths of all the longest bridge:
long_n_strong = [np.sum(np.array(x)) for x in all_chains if len(x) == max_len]
max(long_n_strong)