Execution Time: Part1 = 0.02 seconds. Part2 = ~2.1 seconds. total = ~2.1 seconds
Aiming for simplicity over speed. This is pretty fast for not employing simple tricks like trees and all that.
New version that is using a dictionary to keep track of the next empty slot that fits the current index.
Execution Time: Part1 = 0.02 seconds. Part2 = ~0.08 seconds. total = ~0.08 seconds 80 ms
Edit: final revision. I just realized that the calculating for "last_consecutive_full_partition" was not necessary and very slow. if I know all the next available slots, and can end early once my current index dips below all next available slots then the last_consecutive_full_partition will never be reached.
This drops the time now to less than ~0.1 seconds
Probably Final Edit:
I found someone's O(n) code for OCaml. I tried to convert it to be faith fully in pure python. seems to work really really fast. 30-50 ms time for most inputs. seems to scale linearly too
def int_of_char(x):
return ord(x) - ord('0')
# Represent content as tuples:
# ('Empty', size) or ('File', id, size)
def parse(line):
arr = []
for i in range(len(line)):
c = int_of_char(line[i])
if i % 2 == 0:
arr.append(('File', i // 2, c))
else:
arr.append(('Empty', c))
return arr
def int_sum(low, high):
return (high - low + 1) * (high + low) // 2
def size(elem):
t = elem[0]
if t == 'Empty':
return elem[1]
else:
return elem[2]
def part1(array):
total = 0
left = 0
pos = 0
right = len(array) - 1
while left < right:
if array[left][0] == 'File':
# File
_, fid, fsize = array[left]
total += fid * int_sum(pos, pos + fsize - 1)
pos += fsize
left += 1
else:
# Empty
_, esize = array[left]
if array[right][0] == 'Empty':
right -= 1
else:
# Right is File
_, fid, fsize = array[right]
if esize >= fsize:
array[left] = ('Empty', esize - fsize)
total += fid * int_sum(pos, pos + fsize - 1)
pos += fsize
right -= 1
else:
array[right] = ('File', fid, fsize - esize)
total += fid * int_sum(pos, pos + esize - 1)
pos += esize
left += 1
# If one element remains (left == right)
if left == right and left < len(array):
if array[left][0] == 'File':
_, fid, fsize = array[left]
total += fid * int_sum(pos, pos + fsize - 1)
return total
def positions(arr):
total = 0
res = []
for e in arr:
res.append(total)
total += size(e)
return res
def array_fold_right_i(f, arr, acc):
pos = len(arr) - 1
for elt in reversed(arr):
acc = f(elt, pos, acc)
pos -= 1
return acc
def part2(array):
def find_empty(size_needed, max_pos, pos):
while pos <= max_pos:
if array[pos][0] == 'File':
raise Exception("Unexpected: only empty at odd positions")
# Empty
_, esize = array[pos]
if esize >= size_needed:
array[pos] = ('Empty', esize - size_needed)
return pos
pos += 2
return None
emptys = [1 if i < 10 else None for i in range(10)]
pos_arr = positions(array)
def fold_fun(elt, i, total):
if elt[0] == 'Empty':
return total
# File
_, fid, fsize = elt
init_pos = emptys[fsize]
if init_pos is None:
new_pos = pos_arr[i]
else:
opt = find_empty(fsize, i, init_pos)
if opt is None:
new_pos = pos_arr[i]
else:
new_pos = pos_arr[opt]
pos_arr[opt] += fsize
emptys[fsize] = opt
return total + fid * int_sum(new_pos, new_pos + fsize - 1)
return array_fold_right_i(fold_fun, array, 0)
def main():
with open('largest_test', 'r') as f:
line = f.read().replace('\r', '').replace('\n', '')
arr = parse(line)
arr_copy = arr[:]
p1 = part1(arr_copy)
print("Part 1 :", p1)
p2 = part2(arr)
print("Part 2 :", p2)
if __name__ == "__main__":
main()