Day 14: Restroom Redoubt

from collections import Counter

with open('input/14.txt', 'r') as f:
    lines = f.read().splitlines()

robots = []
for line in lines:
    position, velocity = line.split()
    position = position.split('=')[1].split(',')
    velocity = velocity.split('=')[1].split(',')
    px, py = int(position[0]), int(position[1])
    vx, vy = int(velocity[0]), int(velocity[1])
    robots.append((px, py, vx, vy))

width = 101
height = 103

def get_position_after_time(robot, t):
    px, py, vx, vy = robot
    return ((px + vx * t) % width, (py + vy * t) % height)

def get_quadrant(position):
    px, py = position
    if px == width // 2 or py == height // 2:
        return None
    return (px < width // 2, py < height // 2)

quadrants = Counter()
for robot in robots:
    new_position = get_position_after_time(robot, 100)
    quadrant = get_quadrant(new_position)
    if quadrant is not None:
        quadrants[quadrant] += 1

safety_factor = 1
for v in quadrants.values():
    safety_factor *= v

print("Part 1:", safety_factor)

def count_horizontal_adjacencies(positions):
    adjacencies = 0
    pos_set = set(positions)
    for y in range(height):
        for x in range(width - 1):
            if (x, y) in pos_set and (x + 1, y) in pos_set:
                adjacencies += 1
    return adjacencies

for t in range(10000):
    positions = [get_position_after_time(robot, t) for robot in robots]
    adjacencies = count_horizontal_adjacencies(positions)
    if adjacencies > 200:
        print("Part 2:", t)
        break

pub fn part1(input: &PuzzleInput) -> String {
    let mut robot_grid = Grid2D::new(101, 103, 0usize);

    for robot in input.robots.iter() {
        let pos = robot.position + robot.velocity * 100;
        let final_pos = Coordinate::new(
            pos.x.rem_euclid(robot_grid.width),
            pos.y.rem_euclid(robot_grid.height),
        );
        robot_grid[final_pos] += 1;
    }

    let counts = count_robots(&robot_grid);
    let safety_factor = counts[0] * counts[1] * counts[2] * counts[3];
    safety_factor.to_string()
}

pub fn count_robots(grid: &Grid2D<usize>) -> [usize; 4] {
    let x_center = grid.width / 2;
    let y_center = grid.height / 2;
    let mut counts = [0; 4];

    for x in 0..x_center {
        for y in 0..y_center {
            counts[0] += grid[(x, y).into()];
        }

        for y in (y_center + 1)..grid.height {
            counts[1] += grid[(x, y).into()];
        }
    }

    for x in (x_center + 1)..grid.width {
        for y in 0..y_center {
            counts[2] += grid[(x, y).into()];
        }

        for y in (y_center + 1)..grid.height {
            counts[3] += grid[(x, y).into()];
        }
    }

    counts
}

Just eyeball it.

pub fn part2(input: &PuzzleInput) -> String {
    for i in 0..=6446 {
        let mut robot_grid = Grid2D::new(101, 103, '.');

        for robot in input.robots.iter() {
            let pos = robot.position + robot.velocity * i;
            let final_pos = Coordinate::new(
                pos.x.rem_euclid(robot_grid.width),
                pos.y.rem_euclid(robot_grid.height),
            );
            robot_grid[final_pos] = '#';
        }

        let picture = format!("{}\ni: {}", robot_grid, i);

        if picture.contains("###############################") {
            println!("{}", picture);

            // Wait for user to press enter
            let mut buf = String::new();
            std::io::stdin().read_line(&mut buf).unwrap();
        }
    }

    "".to_string()
}

/* Advent of Code 2024
 * Day 14: Restroom Redoubt
 */

#import "Basic";
#import "File";
#import "String";

Vector2_Int :: struct {
    x, y: int;
}

Robot :: struct {
    position, velocity: Vector2_Int;
}

main :: () {
    input, success := read_entire_file("inputs/day_14.txt");
    assert(success);

    lines := split(input, "\n");
    pop(*lines);
    defer array_free(lines);

    robots: [..] Robot;
    defer array_free(robots);

    for lines {
        vectors := split(it, " ");
        defer array_free(vectors);

        position := split(slice(vectors[0], 2, vectors[0].count - 2), ",");
        velocity := split(slice(vectors[1], 2, vectors[1].count - 2), ",");
        defer array_free(position);
        defer array_free(velocity);

        array_add(*robots, .{
            .{string_to_int(position[0]), string_to_int(position[1])},
            .{string_to_int(velocity[0]), string_to_int(velocity[1])}
        });
    }

    // The example input uses a different size for the space the robots are in,
    // so it's best to define constants for that so it can be easily changed.
    width :: 101;
    height :: 103;
    middle_x :: width / 2;
    middle_y :: height / 2;

    // We need the untouched robots array again for part 2, so we have to copy
    // it here.
    robots_part_1: [..] Robot;
    array_copy(*robots_part_1, robots);
    defer array_free(robots_part_1);

    robot_counts: [4] int;
    for *robots_part_1 {
        it.position.x += it.velocity.x * 100;
        it.position.y += it.velocity.y * 100;

        while it.position.x < 0       it.position.x += width;
        while it.position.x >= width  it.position.x -= width;
        while it.position.y < 0       it.position.y += height;
        while it.position.y >= height it.position.y -= height;

        if it.position.x != middle_x && it.position.y != middle_y {
            robot_counts[
                cast(int) (it.position.y > middle_y) * 2
                + cast(int) (it.position.x > middle_x)
            ] += 1;
        }
    }

    print(
        "Part 1: %\n",
        robot_counts[0] * robot_counts[1] * robot_counts[2] * robot_counts[3]
    );

    // The best way to find the Christmas tree picture seems to be looking for
    // the first second where no robots are on the same tile.
    seconds := 1;
    while true {
        occupied_tiles: [height][width] bool;
        duplicate_found := false;

        for *robots {
            it.position.x += it.velocity.x;
            it.position.y += it.velocity.y;

            if it.position.x < 0       it.position.x += width;
            if it.position.x >= width  it.position.x -= width;
            if it.position.y < 0       it.position.y += height;
            if it.position.y >= height it.position.y -= height;

            if occupied_tiles[it.position.y][it.position.x] {
                duplicate_found = true;
            } else {
                occupied_tiles[it.position.y][it.position.x] = true;
            }
        }

        if duplicate_found {
            seconds += 1;
        } else {
            print("Part 2: %\n", seconds);
            break;
        }
    }
}

#! /usr/bin/env racket
#lang racket

(require "common.rkt")

(module+ test
  (require rackunit))

(struct robot (x y Δx Δy))

(define (parse-robots in-port)
  (for/list ([line (in-lines in-port)])
    (let* ([split (string-split line " ")]
           [position (string-split (substring (first split) 2) ",")]
           [x (string->number (first position))]
           [y (string->number (second position))]
           [velocity (string-split (substring (second split) 2) ",")]
           [Δx (string->number (first velocity))]
           [Δy (string->number (second velocity))])
      (robot x y Δx Δy))))

(define (top-left? q)
  (equal? 'tl q))
(define (top-right? q)
  (equal? 'tr q))
(define (bottom-left? q)
  (equal? 'bl q))
(define (bottom-right? q)
  (equal? 'br q))

(define (step robots width height [k 1])
  (for/list ([r (in-list robots)])
    (let* ([new-x (modulo (+ (robot-x r) (* k (robot-Δx r))) width)]
           [new-y (modulo (+ (robot-y r) (* k (robot-Δy r))) height)])
      (struct-copy robot r [x new-x] [y new-y]))))

(define (safety-factor robots width height)
  (let* ([mid-x (quotient width 2)]
         [mid-y (quotient height 2)]
         [quadrants (for/fold ([quadrants '()])
                              ([r (in-list robots)])
                      (let* ([x (robot-x r)]
                             [y (robot-y r)])
                        (cond
                          ;; top left
                          [(and (< x mid-x)
                                (< y mid-y))
                           (cons 'tl quadrants)]
                          ;; top right
                          [(and (> x mid-x)
                                (< y mid-y))
                           (cons 'tr quadrants)]
                          ;; bottom left
                          [(and (< x mid-x)
                                (> y mid-y))
                           (cons 'bl quadrants)]
                          ;; bottom right
                          [(and (> x mid-x)
                                (> y mid-y))
                           (cons 'br quadrants)]
                          [else (cons 'middle quadrants)])))]
         [tl-count (length (filter top-left? quadrants))]
         [tr-count (length (filter top-right? quadrants))]
         [bl-count (length (filter bottom-right? quadrants))]
         [br-count (length (filter bottom-left? quadrants))])
    (* tl-count tr-count bl-count br-count)))

;; Returns the number of unique positions the robots are in
(define (unique-positions robots)
  (set-count (for/set ([r (in-list robots)])
               (list (robot-x r) (robot-y r)))))

(define (day14/run-part01 robots width height)
  (safety-factor (step robots
                       width
                       height
                       100)
                 width
                 height))

;; I stole the idea of "no robots on the same space" from here
;; https://tildes.net/~comp.advent_of_code/1kos/day_14_restroom_redoubt#comment-ecv5
(define (day14/run-part02 robots width height)
  (let helper ((robots robots) (steps 0))
    (let ([posn-count (unique-positions robots)])
      (cond
        [(= posn-count (length robots)) steps]
        [else (helper (step robots width height) (add1 steps))]))))

(module+ test
  (check-equal? (day14/run-part01 (parse-robots (open-input-file "examples/day14.in")) 11 7) 12 "Test part 1"))

;; Run against my input and print the results
(module+ main
  (let* ([in-port (open-input-file "inputs/day14.in")]
         [robots (parse-robots in-port)]
         [part1 (day14/run-part01 robots 101 103)]
         [part2 (day14/run-part02 robots 101 103)])
    (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)))

import os
import re
import math
from collections import defaultdict
from copy import deepcopy
file = 'test.txt' if os.environ.get('DEBUG') == 'y' else 'input.txt'


if file == 'test.txt':
    rows, cols = 7, 11
else: 
    rows, cols = 103, 101

def grid(bots):
    g = [[0 for _ in range(cols)] for _ in range(rows)]
    for bot in bots:
        bx, by, _, _ = bot
        g[by][bx] += 1
    return g

bots = []
with open(file, 'r') as f:
    for line in f:
        px, py, vx, vy = map(int, re.findall('-?\d+', line))
        bots.append([px, py, vx, vy])


def print_grid(g):
    for y in range(rows):
        for x in range(cols):
            v = g[y][x]
            out = v if v else '.'
            print(out, end='')
        print()


def step(bots, g):
    for bot in bots:
        bx, by, vx, vy = bot
        nx, ny = bx + vx, by + vy 
        if nx < 0: nx += cols 
        elif nx >= cols: nx -= cols
        if ny < 0: ny += rows
        elif ny >= rows: ny -= rows
        bot[0], bot[1] = nx, ny
        g[by][bx] -= 1
        g[ny][nx] += 1

nbrs = [
    (-1, -1),
    (-1, 0),
    (-1, 1),
    (0, -1),
    (0, 0),
    (0, 1),
    (1, -1),
    (1, 0),
    (1, 1),
]

def _in(x, y):
    return 0 <= x < cols and 0 <= y < rows

def prob(x, y, g):
    val = 0
    for dx, dy in nbrs:
        nx, ny = x + dx, y + dy
        if _in(nx, ny) and g[ny][nx]:
            val += 1
    return 1 - val / 9, val / 9
            
def entropy(bots, g):
    total = 0
    for x, y, _, _ in bots:
        p0, p1 = prob(x, y, g)     
        if p0 != 0.0 and p1 != 0.0:
            total -= p0 * math.log(p0)
            total -= p1 * math.log(p1)
    return total



min_entropy = float('inf')
min_grid = None
min_frame = 0
g = grid(bots)
for i in range(10000):
    step(bots,g)
    e = entropy(bots, g)
    if e <= min_entropy:
        min_frame = i + 1
        min_entropy = e

print(min_frame)