Advent Of Code 2023

"""Solution code for "Advent of Code 2023 Day 11".

- Problem link: https://adventofcode.com/2023/day/11
"""


def solve_part1(lines):
    count_by_y, count_by_x = {}, {}
    answer = 0

    y = 0
    for line in lines:
        galaxy_count = line.count('#')
        if galaxy_count == 0:
            y += 2
        else:
            y += 1
            count_by_y[y] = galaxy_count
            for y_prev, galaxy_count_prev in count_by_y.items():
                answer += (y - y_prev) * galaxy_count * galaxy_count_prev

    x = 0
    for col in zip(*lines):
        galaxy_count = col.count('#')
        if galaxy_count == 0:
            x += 2
        else:
            x += 1
            count_by_x[x] = galaxy_count
            for x_prev, galaxy_count_prev in count_by_x.items():
                answer += (x - x_prev) * galaxy_count * galaxy_count_prev

    print(answer)


def solve_part2(lines):
    count_by_y, count_by_x = {}, {}
    answer = 0

    y = 0
    for line in lines:
        galaxy_count = line.count('#')
        if galaxy_count == 0:
            y += 1000000
        else:
            y += 1
            count_by_y[y] = galaxy_count
            for y_prev, galaxy_count_prev in count_by_y.items():
                answer += (y - y_prev) * galaxy_count * galaxy_count_prev

    x = 0
    for col in zip(*lines):
        galaxy_count = col.count('#')
        if galaxy_count == 0:
            x += 1000000
        else:
            x += 1
            count_by_x[x] = galaxy_count
            for x_prev, galaxy_count_prev in count_by_x.items():
                answer += (x - x_prev) * galaxy_count * galaxy_count_prev

    print(answer)


def main():
    with open('./AdventOfCode/2023/day11.txt', encoding='utf-8') as file:
        lines = file.read().split('\n')
    print('[PART 1]')
    solve_part1(lines)
    print('[PART 2]')
    solve_part2(lines)


if __name__ == '__main__':
    main()

  @functools.cache
  def count_rec(spring_count, group_no, pos):
      if pos >= len(row):
          if spring_count == 0 and group_no == group_count:
              return 1
          elif (
              spring_count == group_sizes[-1] and group_no == group_count - 1
          ):
              return 1
          else:
              return 0

      ret = 0
      if row[pos] == '?' or row[pos] == '#':
          if group_no < group_count and spring_count < group_sizes[group_no]:
              ret += count_rec(spring_count + 1, group_no, pos + 1)
      if row[pos] == '?' or row[pos] == '.':
          if spring_count == 0:
              ret += count_rec(0, group_no, pos + 1)
          elif spring_count == group_sizes[group_no]:
              ret += count_rec(0, group_no + 1, pos + 1)
      return ret

  group_count = len(group_sizes)
  return count_rec(0, 0, 0)

def solve_part1(lines):

  answer = 0
  for line in lines:
      row, group_sizes = line.split()
      group_sizes = [int(x) for x in group_sizes.split(',')]
      answer += count(row, group_sizes)
  return answer

def solve_part2(lines):

  answer = 0
  for line in lines:
      row, group_sizes = line.split()
      row = '?'.join([row] * 5)
      group_sizes = ','.join([group_sizes] * 5)
      group_sizes = [int(x) for x in group_sizes.split(',')]
      answer += count(row, group_sizes)
  return answer

def main():

  with open('./AdventOfCode/2023/day12.txt', encoding='utf-8') as file:
      lines = file.read().split('\n')
  print('[PART 1]')
  print('=>', solve_part1(lines))
  print('[PART 2]')
  print('=>', solve_part2(lines))

if name == 'main':

  main()

</dkpr>

"""Solution code for "Advent of Code 2023 Day 13".

- Problem link: https://adventofcode.com/2023/day/13
"""

import collections
import itertools


def calc1(grid):
    ret = 0
    row_to_id = collections.defaultdict(itertools.count().__next__)
    row_id = [row_to_id[row] for row in grid]

    col_to_id = collections.defaultdict(itertools.count().__next__)
    col_id = [col_to_id[col] for col in zip(*grid)]

    for r in range(1, len(row_id)):
        if all(
            row_id[u] == row_id[d]
            for u, d in zip(range(r - 1, -1, -1), range(r, len(row_id)))
        ):
            ret += r * 100

    for c in range(1, len(col_id)):
        if all(
            col_id[u] == col_id[d]
            for u, d in zip(range(c - 1, -1, -1), range(c, len(col_id)))
        ):
            ret += c
    return ret


def solve_part1(lines):
    answer = 0
    grid = []
    for l in lines:
        if l == '':
            answer += calc1(grid)
            grid.clear()
        else:
            grid.append(l)

    answer += calc1(grid)
    return answer


def calc2(grid):
    grid = [row.replace('#', '0').replace('.', '1') for row in grid]
    row_id = [int(row, 2) for row in grid]
    col_id = [int(''.join(col), 2) for col in zip(*grid)]
    ret = 0
    for r in range(1, len(row_id)):
        if (
            sum(
                (row_id[u] ^ row_id[d]).bit_count()
                for u, d in zip(range(r - 1, -1, -1), range(r, len(row_id)))
            )
            == 1
        ):
            ret += r * 100

    for c in range(1, len(col_id)):
        if (
            sum(
                (col_id[l] ^ col_id[r]).bit_count()
                for l, r in zip(range(c - 1, -1, -1), range(c, len(col_id)))
            )
            == 1
        ):
            ret += c
    return ret


def solve_part2(lines):
    answer = 0
    grid = []
    for l in lines:
        if l == '':
            answer += calc2(grid)
            grid.clear()
        else:
            grid.append(l)

    answer += calc2(grid)
    return answer


def main():
    with open('./AdventOfCode/2023/day13.txt', encoding='utf-8') as file:
        lines = file.read().split('\n')
    print('[PART 1]')
    print('=>', solve_part1(lines))
    print('[PART 2]')
    print('=>', solve_part2(lines))


if __name__ == '__main__':
    main()

"""Solution code for "Advent of Code 2023 Day 14".

- Problem link: https://adventofcode.com/2023/day/14
"""


def solve_part1(lines):
    answer = 0
    for col in zip(*lines):
        rock_count = 0
        for r, v in enumerate(reversed(col), start=1):
            if v == 'O':
                rock_count += 1
            elif v == '#':
                for x in range(1, rock_count + 1):
                    answer += r - x
                rock_count = 0
        for x in range(rock_count):
            answer += len(lines) - x
    return answer


def move(grid, pos_beg, pos_end, step):
    rock_count = 0
    for pos in range(pos_beg, pos_end, step):
        v = grid[pos]
        if v == 'O':
            rock_count += 1
            grid[pos] = '.'
        elif v == '#':
            for i in range(1, rock_count + 1):
                grid[pos - i * step] = 'O'
            rock_count = 0
    for i in range(1, rock_count + 1):
        grid[pos_end - i * step] = 'O'


def solve_part2(lines):
    r, c = len(lines), len(lines[0])
    grid = list(''.join(lines))
    for _ in range(110):
        prev_grid = grid[:]
        for i in range(c):
            move(grid, c * (r - 1) + i, i - c, -c)
        for i in range(r):
            move(grid, (i + 1) * c - 1, i * c - 1, -1)
        for i in range(c):
            move(grid, i, r * c + i, c)
        for i in range(r):
            move(grid, c * i, c * (i + 1), 1)
        if grid == prev_grid:
            break
    answer = 0
    for pos, v in enumerate(grid):
        if v == 'O':
            answer += r - (pos // c)

    return answer


def main():
    with open('./AdventOfCode/2023/day14.txt', encoding='utf-8') as file:
        lines = file.read().split('\n')
    print('[PART 1]')
    print('=>', solve_part1(lines))
    print('[PART 2]')
    print('=>', solve_part2(lines))


if __name__ == '__main__':
    main()

"""Solution code for "Advent of Code 2023 Day 15".

- Problem link: https://adventofcode.com/2023/day/15
"""


def hash_(s):
    h = 0
    for c in s:
        h = (h + ord(c)) * 17 % 256
    return h


def solve_part1(lines):
    answer = 0
    seqs = lines[0].split(',')
    for s in seqs:
        answer += hash_(s)
    return answer


def solve_part2(lines):
    answer = 0
    seqs = lines[0].split(',')
    box = [[] for _ in range(256)]
    val_by_lens = {}
    for s in seqs:
        if '=' in s:
            lens, val = s.split('=')
            box_no = hash_(lens)
            if lens not in box[box_no]:
                box[box_no].append(lens)
            val_by_lens[lens] = val
        elif s[-1] == '-':
            lens = s[:-1]
            box_no = hash_(lens)
            try:
                box[box_no].remove(lens)
            except ValueError:
                pass

    for i in range(256):
        for j, lens in enumerate(box[i], start=1):
            answer += (i + 1) * j * int(val_by_lens[lens])
    return answer


def main():
    with open('./AdventOfCode/2023/day15.txt', encoding='utf-8') as file:
        lines = file.read().split('\n')
    print('[PART 1]')
    print('=>', solve_part1(lines))
    print('[PART 2]')
    print('=>', solve_part2(lines))


if __name__ == '__main__':
    main()

"""Solution code for "Advent of Code 2023 Day 19".

- Problem link: https://adventofcode.com/2023/day/19
"""


def solve_part1(lines):
    answer = 0
    line_iter = iter(lines)
    rules_by_name = {}
    while True:
        line = next(line_iter)
        if line.rstrip() == '':
            break
        x, y = line[:-1].split('{')
        rules_by_name[x] = y
    for line in line_iter:
        vals = line[1:-1].split(',')
        x, m, a, s = [int(x.split('=')[1]) for x in vals]
        rule_name = 'in'
        while True:
            if rule_name == 'A':
                answer += x + m + a + s
                break
            elif rule_name == 'R':
                break
            rules = rules_by_name[rule_name]
            for rule in rules.split(','):
                if ':' not in rule:
                    rule_name = rule
                    break
                cond, target = rule.split(':')
                if eval(cond):
                    rule_name = target
                    break

    return answer


def solve_rec(rule_name, ranges, rules_by_name):
    if rule_name == 'R':
        return 0
    elif rule_name == 'A':
        ret = 1
        for k in 'xmas':
            ret *= max(0, ranges[k][1] - ranges[k][0])
        return ret

    ret = 0
    rules = rules_by_name[rule_name]
    for rule in rules.split(','):
        branch_ranges = {k: [b, e] for k, (b, e) in ranges.items()}
        if ':' not in rule:
            ret += solve_rec(rule, branch_ranges, rules_by_name)
            break
        cond, target = rule.split(':')
        var, comp, val = cond[0], cond[1], int(cond[2:])
        if comp == '<':
            ranges[var][0] = max(val, ranges[var][0])
            branch_ranges[var][1] = min(val, branch_ranges[var][1])
            ret += solve_rec(target, branch_ranges, rules_by_name)
        else:
            ranges[var][1] = min(val + 1, ranges[var][1])
            branch_ranges[var][0] = max(val + 1, branch_ranges[var][0])
            ret += solve_rec(target, branch_ranges, rules_by_name)

    return ret


def solve_part2(lines):
    answer = 0
    line_iter = iter(lines)
    rules_by_name = {}
    while True:
        line = next(line_iter)
        if line.rstrip() == '':
            break
        x, y = line[:-1].split('{')
        rules_by_name[x] = y

    answer = solve_rec(
        'in',
        {'x': [1, 4001], 'm': [1, 4001], 'a': [1, 4001], 's': [1, 4001]},
        rules_by_name,
    )
    return answer


def main():
    with open('./AdventOfCode/2023/day19.txt', encoding='utf-8') as file:
        lines = file.read().split('\n')
    print('[PART 1]')
    print('=>', solve_part1(lines))
    print('[PART 2]')
    print('=>', solve_part2(lines))


if __name__ == '__main__':
    main()