Day 24

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:

  1. Find all the connections that have a zero in them and call the function on them
  2. The function will parse the list of remaining connections and find all candidate connections.
  3. It will call itself on those connections and remove that connection from the pool.
  4. When there are no possible connections, it will return

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

In [1]:
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]
Out[1]:
[[32, 31], [2, 2], [0, 43], [45, 15], [33, 24]]

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:

In [2]:
# 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)
Out[2]:
([0, 41, 46, 55], [32, 46, 7, 11])

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.

  • Input should be the reduced list of links and the open side of the connection (helped by find_links)
  • We will make a list of possible connections via the find_links function
  • For each possible connection, we will need to call the function again
  • When these functions return, we need to join on the connection sent as an argument
  • Output should be the list of subchains that can follow from that point. This will be a list of lists of lists (pairs at lowest level)
In [3]:
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)
In [4]:
test = [[0,1], [1, 2], [2, 3], [3, 4], [3, 6], [2, 7], [8, 9]]
find_subchains(test[1:], 1)
Out[4]:
[[[3, 4], [2, 3], [1, 2]], [[3, 6], [2, 3], [1, 2]], [[2, 7], [1, 2]]]

This seems to be working nicely. Now we'll do it with the whole set:

In [5]:
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
In [6]:
all_chains[:2]
Out[6]:
[[[45, 15], [45, 43], [0, 43]],
 [[40, 7],
  [7, 4],
  [4, 4],
  [19, 4],
  [19, 0],
  [5, 0],
  [5, 5],
  [5, 45],
  [45, 43],
  [0, 43]]]

Now we need to flatten these out and sum them. I think this might best be accomplished by using np.arrays and the axes sum.

In [7]:
sums = [np.sum(np.array(x)) for x in all_chains]
max(sums)
Out[7]:
1511

Part 2

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:

In [8]:
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)
Out[8]:
1471