Sean McLemon | Advent of Code

2017-12-06 - Memory Reallocation

(original .ipynb)

# part 1
test_puzzle_input = "0 2 7 0"
real_input = "4	1	15	12	0	9	9	5	5	8	7	3	14	5	12	3"

def serialize_banks(banks):
    return ",".join([str(b) for b in banks])

def reallocate_banks(banks):
    
    largest_idx = -1
    largest_bank = -1
    
    # find largest bank
    for i, bank in enumerate(banks):
        if bank > largest_bank:
            largest_idx = i
            largest_bank = bank

    # remove everything from that bank
    banks[largest_idx] = 0    
    
    # reallocate
    allocation_remaining = largest_bank
    i = largest_idx + 1
    while True:
        if i == len(banks):
            i = 0
        
        if allocation_remaining == 0:
            return

        banks[i] += 1
        allocation_remaining -= 1
        
        i += 1
        

def solve(initial_banks_str, split=" "):
    banks = [int(s) for s in initial_banks_str.split(split) if len(s) > 0]
    
    initial_config_serialized = serialize_banks(banks)
    # print(initial_config_serialized)
    previous_bank_configurations = set([initial_config_serialized])
    
    cycles = 0
    while True:
        reallocate_banks(banks)
        cycles += 1
        serialized_banks = serialize_banks(banks)
        
        # print(serialized_banks)
        
        if serialized_banks in previous_bank_configurations:
            
            return cycles
        
        previous_bank_configurations.add(serialized_banks)
    
#solve(test_puzzle_input)
solve(real_input, "\t")

6681

test_puzzle_input = "0 2 7 0"
real_input = "4	1	15	12	0	9	9	5	5	8	7	3	14	5	12	3"

def find_loop_length(initial_banks_str, split=" "):
    banks = [int(s) for s in initial_banks_str.split(split) if len(s) > 0]
    
    initial_config_serialized = serialize_banks(banks)
    #print(initial_config_serialized)
    previous_bank_configurations = set([initial_config_serialized])
    
    cycles = 0
    counter = -1
    while True:
        reallocate_banks(banks)
        cycles += 1
        if (counter >= 0):
            counter += 1
            
        serialized_banks = serialize_banks(banks)
        
        #print(serialized_banks)
        
        if serialized_banks in previous_bank_configurations:
            if (counter < 0):
                counter = 0
                previous_bank_configurations = set([serialized_banks])
            else: 
                return counter
        
        previous_bank_configurations.add(serialized_banks)
    
#find_loop_length(test_puzzle_input)
find_loop_length(real_input, "\t")

2392