So we're given a kind of splitting pattern problem. The rules of the problem are this:
This one seems like it's really going to test my understanding of np.array. Let's start by just getting the input into the computer and trying to transform all the instructions into np.arrays
import numpy as np
import math
original = np.array([[0, 1, 0], [0, 0, 1], [1, 1, 1]])
enhancements = open('/Users/Sven/py_files/aoc_2017/day21_input.txt').readlines()
enhancements = [x.replace('.', '0').replace('#', '1').replace('\n', '') for x in enhancements]
enhancements[:5]
enh_in = [x.split(' => ')[0] for x in enhancements]
enh_out = [x.split(' => ')[1] for x in enhancements]
print(enh_in[:5])
print(enh_out[:5])
K so we need to maybe make a funcion just to format these to arrays:
def split_string(string):
return([int(x) for x in string])
def code_to_array(code):
# split the rows
rows = code.split('/')
rows = [split_string(x) for x in rows]
#y for x in non_flat for y in x
return(rows)
code_to_array(enh_in[0])
Now apply to the whole list of inputs and outputs
enh_in = np.array([np.array(code_to_array(x)) for x in enh_in])
enh_out = np.array([np.array(code_to_array(x)) for x in enh_out])
for i in range(5):
print(enh_in[i], end = '\n\n')
So if I can remember my abstract algebra correctly this is the dihedral group D8. It has 8 possible orientations which are formed by the original position, 1-3 rotations in the same direction, the two reflections as well as one rotation and either reflection. I think we'll want to compute all these transformations for each of the enhancements.
# First type of flip
def flip1(mat):
flipped = [np.flip(x).tolist() for x in mat]
return(np.array(flipped))
print(enh_in[13], end = '\n\n')
print(flip1(enh_in[13]))
# second kind of flip. Not quite sure how I intuitioned this but
# I think a transpose flip1 transpose is the same as a vertical flip
def flip2(mat):
flipped = np.transpose(flip1(np.transpose(mat)))
return(flipped)
print(enh_in[13])
print(flip2(enh_in[13]))
# Now for a rotation, I think we'll just worry about the 2x2 and 3x3 cases..
# I'm pretty sure I can program the general one but... ya know... laziness
rota3 = [2, 5, 8, 1, 4, 7, 0, 3, 6]
rota2 = [1, 3, 0, 2]
def flatten(mat):
return([y for x in mat for y in x])
def rotate(mat):
# kinda think this will be easier if we just flatten
# and cheater my way through this
l = len(mat)
flattened = flatten(mat)
if l == 3:
flattened = [flattened[i] for i in rota3]
else:
flattened = [flattened[i] for i in rota2]
mat = np.array(flattened)
mat.shape = (l, l)
return(mat)
print(enh_in[13], rotate(enh_in[13]), sep = '\n\n')
print()
Great! Now we need to apply the 7 transformations to each matrix and take the unique values
def get_transformations(mat):
transformations = [
mat,
rotate(mat),
rotate(rotate(mat)),
rotate(rotate(rotate(mat))),
flip1(mat),
flip2(mat),
flip1(rotate(mat)),
flip2(rotate(mat))
]
transformations = np.unique(np.array(transformations), axis = 0)
return(transformations)
print(enh_in[14])
print('\nTransformations:\n')
ww = get_transformations(enh_in[14])
for t in ww:
print(t, end = '\n\n')
Lovely, now we have to apply this to every input and make the association with the output arrays. I've learned that lists are 'not hashable' and thus cannot be the keys to dictionaries. Instead I think we'll use a tuple version of the matrix as the keys.
def make_associations(old, new):
old = get_transformations(old)
new = [new for i in range(len(old))]
old = [tuple(flatten(mat)) for mat in old]
return dict(zip(old, new))
make_associations(enh_in[1], enh_out[1])
Now we make a big dict (heh) of all the associations.
mapping = list(map(make_associations, enh_in, enh_out))
enh_dict = dict()
for i in range(len(mapping)):
enh_dict.update(mapping[i])
# here to shortcut the dictionary access:
def enhance_array(arr):
return(enh_dict[tuple(flatten(arr))])
test = enhance_array(original)
test2 = enhance_array(original)
print(test, test2, sep = '\n\n')
Alright that's mighty grand. I think the hardest part of this will probably be figuring out how to put the arrays back together after we find their enhancements.
#import random
#ww = np.random.choice([0, 1], 36)
#ww = np.array(ww)
#ww.shape = (6, 6)
#ww
def split_array(arr):
# which stage are we at?
if len(arr) % 2 == 0:
divisor = 2
else:
divisor = 3
# this is how many 'blocks' each side will have
quotient = int(len(arr) / divisor)
# Now make the subarrays
subarrays = []
for i in range(quotient):
for j in range(quotient):
#print(arr[divisor*i:divisor*(i+1), divisor*j:divisor*(j+1)])
subarrays.append(arr[divisor*i:divisor*(i+1), divisor*j:divisor*(j+1)])
return(subarrays)
# Note that I returned a list of arrays, not a np.array
print(test)
print(split_array(test))
for x in split_array(test):
print(x)
Maybe this won't be so hard? Now this to recombine:
def recombine_array(arr):
# heres the small pieces that make up the whole
subarr_len = len(arr[0])
# Here's the number of such pieces
n_blocks = len(arr)
n_blocks_rt = int(math.sqrt(n_blocks))
# this is what we'll spit out
recombined = []
# let the looping begin.. first go across blocks of size subarr_len
for first_ind in range(n_blocks_rt):
# To get the alternating pattern right we'll use two smaller loops
for second_ind in range(subarr_len):
new_row = []
for third_ind in range(n_blocks_rt):
sublock = arr[first_ind*n_blocks_rt + third_ind][second_ind]
new_row += sublock.tolist()
recombined.append(new_row)
return(np.array(recombined))
print(test)
print(recombine_array(split_array(test)))
np.equal(test, recombine_array(split_array(test))).all()
Now it looks like it's loop time. Time for 5 iterations:
five_its = np.copy(original)
for i in range(5):
five_its = split_array(five_its)
five_its = [enhance_array(x) for x in five_its]
five_its = recombine_array(five_its)
np.sum(five_its)
Okay, this turned out to be one of the hardest ones for me. I think it has taught me the most about np.arrays though. I had a lot of issues with accidentally making arrays of arrays and having the dimensions not line up. Some of the loops I wrote seem very easy to me now but I struggled WAY too much with the recombining array function.
We are now simply asked about after 18 iterations... I wonder if either my method will break or other people solved this in a sneakier way than literally mimicking the process.
eighteen_its = np.copy(original)
for i in range(18):
eighteen_its = split_array(eighteen_its)
eighteen_its = [enhance_array(x) for x in eighteen_its]
eighteen_its = recombine_array(eighteen_its)
np.sum(eighteen_its)