<jupyter_start><jupyter_text>Day 15<jupyter_code>puzzle_input = [2,0,1,7,4,14,18]<jupyter_output><empty_output><jupyter_text>Part A<jupyter_code>def idx_of_last_occurance(puzzle, last_idx):
    
    last = puzzle[last_idx]
    
    idx  = last_idx - 1
    while puzzle[idx] != last:
        if idx == 0:
            return last_idx
        idx -= 1
        
    return idx


puzzle_length = 2020

puzzle = puzzle_input + [0]*(puzzle_length - len(puzzle_input))

last_idx = len(puzzle_input)-1
while last_idx < puzzle_length-1:
    puzzle[last_idx+1] = last_idx - idx_of_last_occurance(puzzle, last_idx)
    last_idx += 1
    
answer15A = puzzle[-1]
print('answer 15A:', answer15A, len(puzzle))<jupyter_output>answer 15A: 496 2020<jupyter_text>Part BSame as A, but now for a much longer higher number N. This depends quadratically on N. THerefore, we will use a lookup table: number -> index of last occurance for the first 100 numbers<jupyter_code>class LookupTable:
    
    def __init__(self, size):
        
        self.lookup = [-1]*size
        self.size = size
        
    def get_last_occ_idx(self, n):
        if n < self.size:
            return self.lookup[n]
        else:
            return -1
        
    def set_last_occ_idx(self, n, idx):
        if n < self.size:
            self.lookup[n] = idx
            

def idx_of_last_occurance(puzzle, last_idx, lookup):
    
    last = puzzle[last_idx]
    
    if lookup.get_last_occ_idx(last):
        return idx
    
    idx  = last_idx - 1
    while puzzle[idx] != last:
        if idx == 0:
            return last_idx
        idx -= 1
        
    return idx
puzzle_length = 30000000
#puzzle_length = 2020
#lookup_size = 100
#lookup = LookupTable(lookup_size)
value_to_last_index = [0]*puzzle_length
for idx, p in enumerate(puzzle_input[:-1]):
    value_to_last_index[p] = idx
value_to_last_index = [-1]*puzzle_length
for idx, p in enumerate(puzzle_input[:-1]):
    value_to_last_index[p] = idx

last_idx = len(puzzle_input)-1
last_val = puzzle_input[-1]
prev_val = -1
while last_idx < puzzle_length-1:
    
    #print(last_idx, last_val, prev_val)
    
    prev_val = last_val
    last_occ_idx = value_to_last_index[last_val]
    if last_occ_idx == -1:
        last_val = 0
    else:
        last_val = last_idx - last_occ_idx

    value_to_last_index[prev_val] = last_idx
 
    last_idx += 1
    if last_idx%1000000==0:
        print('last_idx:', last_idx/1000000, end='\n')
    
answer15B = last_val
print('\nanswer 15B:', answer15B)<jupyter_output>last_idx: 1.0
last_idx: 2.0
last_idx: 3.0
last_idx: 4.0
last_idx: 5.0
last_idx: 6.0
last_idx: 7.0
last_idx: 8.0
last_idx: 9.0
last_idx: 10.0
last_idx: 11.0
last_idx: 12.0
last_idx: 13.0
last_idx: 14.0
last_idx: 15.0
last_idx: 16.0
last_idx: 17.0
last_idx: 18.0
last_idx: 19.0
last_idx: 20.0
last_idx: 21.0
last_idx: 22.0
last_idx: 23.0
last_idx: 24.0
last_idx: 25.0
last_idx: 26.0
last_idx: 27.0
last_idx: 28.0
last_idx: 29.0

answer 15B: 883<jupyter_text>Analysis of occurance of numbers in the puzzle list<jupyter_code>from collections import Counter
d = dict(Counter(puzzle[:last_idx]))
sorted_idx = np.argsort(-1*np.array(list(d.values())))
sorted_counts = np.array(list(d.values()))[sorted_idx]
sorted_values = np.array(list(d.keys()))[sorted_idx]
sorted_counts[:20]
sorted_values[:20]
import matplotlib as mpl
import matplotlib.pyplot as plt

plt.plot(sorted_counts[:100])
plt.plot(sorted_values[:100], sorted_counts[:100])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11293103448275862, 'fraction_numerical': 0.05488505747126437, 'mean_word_length': 3.3458177278402, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '237832', 'license': 'MIT', 'n_tokens_mistral': 1504, 'n_tokens_neox': 1351, 'n_words': 293, 'path': 'day15.ipynb', 'repo_name': 'Paijmans/advent_of_code', 'size': '3480'}