back home

Day - 24

Part 1 - Code

      
import functools
import random
def get_partitions_rec(data, target, curr, acc, index):
  if target == 0:
    acc.append(curr)
  elif target > 0 and index < len(data):
    consider = data[index]
    if target - consider >= 0 and len(curr) < len(data) - 2:
      next_curr = [c for c in curr]
      next_curr.append(consider)
      get_partitions_rec(data, target-consider, next_curr, acc, index+1) 
    get_partitions_rec(data, target, curr, acc, index+1)
  else:
    pass

def get_partitions(data, target):
  possible_partitions = []
  get_partitions_rec(data, target, [], possible_partitions, 0)
  possible_partitions.sort(key=lambda x: len(x))
  return possible_partitions

def solve_for_bucket_size(data, bucket_size):
  data = [i for i in data]
  data_size = len(data)
  total_sum = sum(data)


  buckets = bucket_size

  bin_size = total_sum//buckets
  data = sorted(data, reverse=True)  

  # we can assume the following from the data:
  #   - the sum of the total weight tw of packages is divisible by three
  #   - there exists a partition of data such that each partition has a sum of tw/3
  #   - the max size of a partition is t-2 where t is the total number of values
  # thus, this problem can be solved by finding the smallest partition that has the sum tw/3
  # if there are multiple partitions of the same size, 
  # the answer is the one which has the smallest product

  partitions = get_partitions(data, bin_size)
  smallest_size = len(partitions[0])
  filtered = filter(lambda x: len(x) == smallest_size, partitions)
  mapped = sorted(map(lambda x: functools.reduce(lambda a,b: a*b, x), filtered))

  print(mapped[0])

def solve_part_1(data):
  solve_for_bucket_size(data, 3)

def solve_part_2(data):
  solve_for_bucket_size(data, 4)

def main():
  data = []
  with open("../../data/day24/data.txt", 'r') as file:
    data = [int(lines.strip()) for lines in file.readlines()]
  
  solve_part_1(data)
  solve_part_2(data)


if __name__ == "__main__":
  main()