initial = 'wenycdww'
initial_list = [initial + '-' + str(x) for x in range(128)]
initial_list[:5]
Next convert each of these strings to a list of ascii positions and add the standard suffix:
def to_ascii_list(x):
return([ord(let) for let in x])
ascii_list = [to_ascii_list(x) + [17, 31, 73, 47, 23] for x in initial_list]
ascii_list[:5]
We'll use these same helper functions:
def mod(x):
return(x % 256)
def sub_indices(marks, start, length):
if start + length <= len(marks):
return(list(range(start, (start + length))))
# If we go beyond the length of marks, get the leftovers:
else:
return(list(range(start, len(marks))) + list(range(mod(start+length))))
Now make a function that is like the code we used for day 10
def tie_knots(x):
# Define record keepers
marks = list(range(256))
skip = 0
pos = 0
# loop over the start tying the knots:
for inst in x*64:
indices = sub_indices(marks, pos, inst)
sublist = [marks[i] for i in indices]
sublist.reverse()
for i in range(len(sublist)):
marks[indices[i]] = sublist[i]
pos = mod(pos + inst + skip)
skip += 1
return(marks)
And a function to create the dense hash:
def dense_hash(x):
chunks = [str(m) for m in x]
chunks = [chunks[(16*i):(16*(i+1))] for i in range(int(256/16))]
chunks = [' ^ '.join(x) for x in chunks]
dense_hash = [eval(x) for x in chunks]
return(dense_hash)
Functions to turn into hex and then to binary
ww = dense_hash(tie_knots(ascii_list[0]))
def hex2(x):
x = hex(x).split('x')[1]
if len(x) == 1:
x = '0' + x
return(x)
def hex2bin(x):
x = ''.join([hex2(h) for h in x])
x = bin(int(x, 16))[2:]
x = str(x)
while len(x) < 128:
x = '0' + x
return(x)
Finally a function to count up the digit sum
def digit_sum(x):
i = 0
for let in str(x):
if let == '1':
i += 1
return(i)
Now use all the functions. I don't really like to nest these too much as I find it hard to read.
result = [tie_knots(x) for x in ascii_list]
result = [dense_hash(x) for x in result]
result = [hex2bin(x) for x in result]
sum([digit_sum(x) for x in result])
Well I only have a very foggy idea of what I'm doing but I guess it's right. I guess that's more a testament to my ability to read and follow directions than any understanding of computer science.
Now we're asked about a continuous regions on this as if it were a grid. A region is defined as portions of the graph that are 1s and are connected vertically or horizontally. We're asked how many such regions exist. I think this might be accomplished in a similar way to some of the other ones with the nodes on a graph. We can search through all the adjacent cells for more 1s, advance to those locations, record their positions ect.
for i in range(8):
print(result[i][:8])
Convert to int:
result_int = [[int(x) for x in l] for l in result]
Hmmm I'm having some ideas about how to make this run quicker but I guess that probably doesn't matter too much...
We can just check the condition of a least one 1 in the matrix as a condition to execute the function again.
First a function to check which neighbors are ones:
def check_neighbors(mat, row, col):
neighbors = set([])
neigh_row = [row - 1, row, row, row + 1]
neigh_col = [col, col -1, col + 1, col]
for i in range(4):
if 0 <= neigh_row[i] <= 127 and 0 <= neigh_col[i] <= 127:
if mat[neigh_row[i]][neigh_col[i]] == 1:
neighbors.add((neigh_row[i], neigh_col[i]))
return neighbors
check_neighbors(result_int, 0, 0)
Now a function that recursively searches. I think we'll have the cell being a one as a precondition to calling the function.
# Function arguments:
# mat: the blanket of 1s and 0s
# row/col: the row and column to be tested
# region: the set of tuples of cells
def find_region(mat, row, col, region):
# add to the pile
region.add((row, col))
# Check if any neighboring 1s
neighbors = check_neighbors(mat, row, col)
# if so, start looping through them:
for neighb in neighbors:
if not neighb in region:
region = find_region(mat, neighb[0], neighb[1], region)
return(region)
find_region(result_int, 0, 0, set([(0, 0)]))
Alright, we'll use a check function to see if we need to keep identifying regions
def remaining_region(x):
for row in range(len(x)):
for col in range(len(x[row])):
if x[row][col] == 1:
return row, col
else:
return(-1, -1)
Kinda interesting here that I learned more about the scoping. If you copy a list, this doesn't copy the contents of the list
import copy
mat = copy.deepcopy(result_int)
i = 0
while remaining_region(mat)[1] >= 0:
i -= 1
row, col = remaining_region(mat)
region = find_region(mat, row, col, set([(row, col)]))
for reg in region:
mat[reg[0]][reg[1]] = i
for i in range(8):
print(result_int[i][:8])
print()
for i in range(8):
print(mat[i][:8])
The solution should be the minimum of the whole thing
minimum = [val for sublist in mat for val in sublist]
min(minimum)