lily's recent activity

Comment on Day 19: Linen Layout in ~comp.advent_of_code

lily

8 hours, 38 minutes ago

Link

Still in the cooldown period, I see. Didn't mind the easier puzzle, though. The only "trick" to this was using memoization so it could finish in a reasonable time. Solution (Jai) /* Advent of Code...

Still in the cooldown period, I see. Didn't mind the easier puzzle, though. The only "trick" to this was using memoization so it could finish in a reasonable time.

Solution (Jai)

/* Advent of Code 2024
 * Day 19: Linen Layout
 */

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

get_solution :: (
    design: string,
    towels: [] string,
    known_solutions: *Table(string, int)
) -> int {
    known_solution, success := table_find(known_solutions, design);
    if success {
        return known_solution;
    }

    solution := 0;
    for towels {
        if design == it {
            solution += 1;
        } else if begins_with(design, it) {
            solution += get_solution(
                slice(design, it.count, design.count - it.count),
                towels,
                known_solutions
            );
        }
    }

    table_add(known_solutions, design, solution);
    return solution;
}

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

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

    towels := split(lines[0], ", ");
    defer array_free(towels);

    designs := array_view(lines, 2, lines.count - 3);

    // I didn't want this to be global, so I'm passing a pointer to it into the
    // get_solutions() procedure.
    known_solutions: Table(string, int);
    deinit(*known_solutions);

    possible_designs := 0;
    total_solutions := 0;

    for designs {
        solutions := get_solution(it, towels, *known_solutions);

        if solutions > 0 {
            possible_designs += 1;
        }

        total_solutions += solutions;
    }

    print("Part 1: %\nPart 2: %\n", possible_designs, total_solutions);
}

2 votes

Comment on Day 18: RAM Run in ~comp.advent_of_code

lily

1 day, 7 hours ago

Link

This was a nice breather after yesterday - I definitely should've solved it quicker than I did, but I got caught up on a couple annoying bugs. Just another simple pathfinding problem, though this...

This was a nice breather after yesterday - I definitely should've solved it quicker than I did, but I got caught up on a couple annoying bugs. Just another simple pathfinding problem, though this one was even easier since it wasn't weighted (so I didn't have to bother with Djikstra). My solution for part 2 is incredibly lazy and pretty slow, but I don't really feel up to optimizing it further right now.

Solution (Jai)

/* Advent of Code 2024
 * Day 18: RAM Run
 */

#import "Basic";
#import "File";
#import "Flat_Pool";
#import "Hash";
#import "Hash_Table";
#import "String";

// These need to be configurable to make using the sample input easy.
GRID_SIZE :: 71;
PART_1_BYTES :: 1024;

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

Node :: struct {
    parent: *Node;
    position: Vector2_Int;
}

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    #procedure_of_call(operator ==(Vector2_Int.{}, Vector2_Int.{}))
);

operator == :: (a: Vector2_Int, b: Vector2_Int) -> bool {
    return a.x == b.x && a.y == b.y;
}

solve_grid :: (grid: [GRID_SIZE][GRID_SIZE] bool) -> int {
    queue: [..] *Node;
    array_add(*queue, New(Node));
    defer array_free(queue);

    seen: Vector2_Int_Set;
    table_add(*seen, .{0, 0}, #run {});
    defer deinit(*seen);

    while queue.count {
        current := queue[0];
        array_ordered_remove_by_index(*queue, 0);

        if current.position == .{GRID_SIZE - 1, GRID_SIZE - 1} {
            path_length := 0;
            while current != null {
                path_length += 1;
                current = current.parent;
            }

            return path_length - 1;
        }

        for Vector2_Int.[
            .{current.position.x - 1, current.position.y},
            .{current.position.x + 1, current.position.y},
            .{current.position.x, current.position.y - 1},
            .{current.position.x, current.position.y + 1}
        ] {
            if
                it.x >= 0 && it.x < GRID_SIZE && it.y >= 0 && it.y < GRID_SIZE
                && !grid[it.y][it.x]
                && !table_contains(*seen, it)
            {
                new_node := New(Node);
                new_node.parent = current;
                new_node.position = it;

                array_add(*queue, new_node);
                table_add(*seen, it, #run {});
            }
        }
    }

    return -1;
}

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

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

    grid: [GRID_SIZE][GRID_SIZE] bool;
    dropped_bytes := 0;

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

        grid[string_to_int(position[1])][string_to_int(position[0])] = true;

        dropped_bytes += 1;
        if (dropped_bytes == PART_1_BYTES) {
            break;
        }
    }

    // Using a pool saves us time doing memory allocations in the solving
    // procedure. It's not a huge performance gain, but it's just about
    // noticeable.
    pool: Flat_Pool;
    defer reset(*pool);

    context.allocator.proc = flat_pool_allocator_proc;
    context.allocator.data = *pool;

    print("Part 1: %\n", solve_grid(grid));

    for dropped_bytes..lines.count - 2 {
        position := split(lines[it], ",");
        defer array_free(position);

        grid[string_to_int(position[1])][string_to_int(position[0])] = true;

        if solve_grid(grid) == -1 {
            print("Part 2: %\n", lines[it]);
            break;
        } else {
            // We'll run out of memory if we don't do this. With a smaller input
            // this might not be required, but for the size we're given the
            // program will crash if we don't do it.
            reset(*pool);
        }
    }
}

1 vote

Comment on Day 17: Chronospatial Computer in ~comp.advent_of_code

lily

1 day, 8 hours ago (edited 1 day, 7 hours ago)

Link

I managed to finish this with only about five minutes left before midnight - phew! I'm posting the solution now since I had to immediately move on to tonight's actual puzzle. It took me quite a...

I managed to finish this with only about five minutes left before midnight - phew! I'm posting the solution now since I had to immediately move on to tonight's actual puzzle.

It took me quite a while to finally realize I should be looking at what the program actually did, and once I saw what it was doing it didn't take too long to figure out a solution (just bruteforce three bits at a time). I ended up having to use BFS for the bruteforcing, since otherwise it seemed it kept getting stuck on false leads.

Solution (Jai)

/* Advent of Code 2024
 * Day 17: Chronospatial Computer
 */

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

Registers :: struct {
    a, b, c: int;
}

State :: struct {
    register_a, iteration: int;
}

resolve_combo_operand :: (operand: u8, registers: Registers) -> int {
    if operand == {
        case 4; return registers.a;
        case 5; return registers.b;
        case 6; return registers.c;
        case;   return operand;
    }
}

run_program :: (initial_registers: Registers, program: [] u8) -> [..] int {
    registers := initial_registers;
    instruction_pointer := 0;
    output: [..] int;

    while instruction_pointer < program.count {
        opcode := program[instruction_pointer];
        operand := program[instruction_pointer + 1];
        instruction_pointer += 2;

        // I don't personally find the instruction names any more readable than
        // the plain opcodes, so I didn't bother using an enum.
        if opcode == {
            case 0;
                registers.a = (
                    registers.a
                    / 1 << resolve_combo_operand(operand, registers)
                );

            case 1;
                registers.b = registers.b ^ operand;

            case 2;
                registers.b = resolve_combo_operand(operand, registers) % 8;

            case 3;
                if registers.a != 0 {
                    instruction_pointer = operand;
                }

            case 4;
                registers.b = registers.b ^ registers.c;

            case 5;
                array_add(
                    *output,
                    resolve_combo_operand(operand, registers) % 8
                );

            case 6;
                registers.b = (
                    registers.a
                    / 1 << resolve_combo_operand(operand, registers)
                );

            case 7;
                registers.c = (
                    registers.a
                    / 1 << resolve_combo_operand(operand, registers)
                );
        }
    }

    return output;
}

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

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

    program_strings := split(slice(lines[4], 9, lines[4].count - 9), ",");
    defer array_free(program_strings);

    program: [..] u8;
    defer array_free(program);

    for program_strings {
        array_add(*program, xx string_to_int(it));
    }

    output := run_program(.{
        a = string_to_int(slice(lines[0], 12, lines[0].count - 12)),
        b = string_to_int(slice(lines[1], 12, lines[1].count - 12)),
        c = string_to_int(slice(lines[2], 12, lines[2].count - 12))
    }, program);
    defer array_free(output);

    builder: String_Builder;
    defer reset(*builder);

    for output {
        print_to_builder(*builder, "%", it);
        if it_index < output.count - 1 {
            append(*builder, ",");
        }
    }

    print("Part 1: %\n", builder_to_string(*builder));

    // Every three bits given to the program add another number to the output.
    // Because of this, we can bruteforce three bits at a time. We're using BFS
    // here instead of just bruteforcing the groups of bits in sequence because
    // occasionally we may run into a false lead.
    queue: [..] State;
    array_add(*queue, .{0, 0});
    defer array_free(queue);

    while queue.count {
        current := queue[0];
        array_ordered_remove_by_index(*queue, 0);

        target := program[program.count - current.iteration - 1];
        for 0..7 {
            new_register_a := current.register_a << 3 | it;
            registers := Registers.{new_register_a, 0, 0};

            output := run_program(registers, program);
            defer array_free(output);

            if output[0] == target {
                if current.iteration == program.count - 1 {
                    print("Part 2: %\n", new_register_a);
                    return;
                } else {
                    array_add(*queue, .{registers.a, current.iteration + 1});
                }
            }
        }
    }
}

1 vote

Comment on Day 16: Reindeer Maze in ~comp.advent_of_code

lily

3 days, 7 hours ago

Link

I was waiting for the annual pathfinding puzzle! I thought ahead and wrote a quick binary heap implementation before Advent of Code started this year, since the Jai compiler doesn't come with one...

I was waiting for the annual pathfinding puzzle! I thought ahead and wrote a quick binary heap implementation before Advent of Code started this year, since the Jai compiler doesn't come with one and I knew I'd need one at some point. Today's puzzle was pretty straightforward as far as pathfinding puzzles go - the only tricky part was making the seen table work properly with part 2.

Solution (Jai)

/* Advent of Code 2024
 * Day 16: Reindeer Maze
 */

#import "Basic";
#import "Binary_Heap";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

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

Node :: struct {
    parent: *Node;
    cost: int;
    position: Vector2_Int;
}

// This is used for the table of seen states. The direction isn't stored in Node
// because it is inferred from the parent's position, but we have to store it
// here.
Reindeer_State :: struct {
    position, direction: Vector2_Int;
}

operator == :: (a: Vector2_Int, b: Vector2_Int) -> bool {
    return a.x == b.x && a.y == b.y;
}

array_free_2d :: (array: [..][..] $T) {
    for array {
        array_free(it);
    }

    array_free(array);
}

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

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

    map: [..][..] bool;
    defer array_free_2d(map);

    start, end: Vector2_Int;
    for line, y: lines {
        if line == "" {
            continue;
        }

        row: [..] bool;
        for char, x: line {
            array_add(*row, char == #char "#");

            if char == #char "S" {
                start = .{x, y};
            } else if char == #char "E" {
                end = .{x, y};
            }
        }

        array_add(*map, row);
    }

    width := map[0].count;
    height := map.count;

    heap: Heap(*Node, (left: *Node, right: *Node) -> bool {
        return left.cost <= right.cost;
    });

    seen: Table(
        Reindeer_State,
        int,
        (state: Reindeer_State) -> u32 {
            return inline sdbm_hash(xx *state, size_of(Reindeer_State));
        },
        (a: Reindeer_State, b: Reindeer_State) -> bool {
            return a.position == b.position && a.direction == b.direction;
        }
    );

    defer heap_free(heap);
    defer deinit(*seen);

    start_node := New(Node);
    start_node.position = start;
    heap_add(*heap, start_node);
    table_set(*seen, .{start_node.position, .{1, 0}}, 0);

    minimum_cost := -1;

    best_paths: [..][..] Vector2_Int;
    defer array_free_2d(best_paths);

    while !heap_is_empty(heap) {
        current := heap_pop(*heap);

        if current.position == end {
            if minimum_cost == -1 {
                minimum_cost = current.cost;
                print("Part 1: %\n", minimum_cost);
            }

            if current.cost == minimum_cost {
                path: [..] Vector2_Int;
                while current != null {
                    array_insert_at(*path, current.position, 0);
                    current = current.parent;
                }

                array_add(*best_paths, path);
                continue;
            } else {
                // We're using Djikstra's algorithm, so we know there will be no
                // more best paths after this.
                break;
            }
        }

        for Vector2_Int.[.{-1, 0}, .{1, 0}, .{0, -1}, .{0, 1}] {
            last_direction: Vector2_Int;
            if current.parent == null {
                last_direction = .{1, 0};
            } else {
                last_direction = .{
                    current.position.x - current.parent.position.x,
                    current.position.y - current.parent.position.y
                };
            }

            backwards: bool;
            if      last_direction == .{-1, 0} backwards = (it == .{1, 0});
            else if last_direction == .{1, 0}  backwards = (it == .{-1, 0});
            else if last_direction == .{0, -1} backwards = (it == .{0, 1});
            else if last_direction == .{0, 1}  backwards = (it == .{0, -1});

            new_cost := (
                current.cost + ifx last_direction == it then 1 else 1001
            );

            new_position := Vector2_Int.{
                current.position.x + it.x,
                current.position.y + it.y
            };

            new_state := Reindeer_State.{new_position, last_direction};
            seen_cost, success := table_find(*seen, new_state);

            // No need for bounds checking; the map is completely surrounded by
            // walls.
            if
                !map[new_position.y][new_position.x]
                && !backwards
                && (!success || seen_cost >= new_cost)
            {
                new := New(Node);
                memcpy(new, current, size_of(Node));

                new.parent = current;
                new.cost = new_cost;
                new.position = new_position;

                heap_add(*heap, new);
                table_set(*seen, new_state, new_cost);
            }
        }
    }

    places_to_sit: Table(
        Vector2_Int,
        void,
        (vector: Vector2_Int) -> u32 {
            return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
        },
        #procedure_of_call(operator ==(Vector2_Int.{}, Vector2_Int.{}))
    );

    defer deinit(*places_to_sit);

    for best_paths {
        for it {
            if !table_contains(*places_to_sit, it) {
                table_add(*places_to_sit, it, #run {});
            }
        }
    }

    print("Part 2: %\n", places_to_sit.count);
}

Binary heap

// order_test is used to determine the order of the values in the queue. It
// should return whether the first passed value should be given higher priority
// than the second passed value.
Heap :: struct (
    Value_Type: Type,
    order_test: (Value_Type, Value_Type) -> bool
) {
    values: [..] Value_Type;
}

heap_add :: (heap: *Heap, value: heap.Value_Type) {
    array_add(*heap.values, value);

    current_index := heap.values.count - 1;
    while current_index > 0 {
        parent_index := (current_index - 1) / 2;

        current_value := heap.values[current_index];
        parent_value := heap.values[parent_index];

        if heap.order_test(parent_value, current_value) {
            break;
        }

        heap.values[current_index] = parent_value;
        heap.values[parent_index] = current_value;
        current_index = parent_index;
    }
}

heap_pop :: (heap: *Heap) -> heap.Value_Type {
    assert(!heap_is_empty(heap), "cannot pop from an empty heap");

    root_value := heap.values[0];
    heap.values[0] = pop(*heap.values);

    current_index := 0;
    while true {
        left_index := current_index * 2 + 1;
        right_index := left_index + 1;

        has_left := left_index < heap.values.count;
        has_right := right_index < heap.values.count;

        if !has_left && !has_right {
            break;
        }

        child_index: int;
        if !has_left {
            child_index = right_index;
        } else if !has_right {
            child_index = left_index;
        } else if heap.order_test(
            heap.values[left_index],
            heap.values[right_index]
        ) {
            child_index = left_index;
        } else {
            child_index = right_index;
        }

        current_value := heap.values[current_index];
        child_value := heap.values[child_index];

        if heap.order_test(current_value, child_value) {
            break;
        }

        heap.values[current_index] = child_value;
        heap.values[child_index] = current_value;
        current_index = child_index;
    }

    return root_value;
}

// These last two procedures don't require the heap be passed as a pointer,
// since they do not modify it.
heap_is_empty :: inline (heap: Heap) -> bool {
    return heap.values.count == 0;
}

heap_free :: inline (heap: Heap) {
    for heap.values {
        free(it);
    }

    array_free(heap.values);
}

#scope_file

#import "Basic";

1 vote

Comment on Day 15: Warehouse Woes in ~comp.advent_of_code

lily

4 days, 6 hours ago

Link

I agree with everyone else here. This was a bit tricky to implement, but I understood what I was supposed to be doing almost instantly. I did get tripped up on edge cases a bit for part 2, though,...

I agree with everyone else here. This was a bit tricky to implement, but I understood what I was supposed to be doing almost instantly. I did get tripped up on edge cases a bit for part 2, though, and I think my final solution is one of the worst I've written this year so far - it's overly long and hard to parse. Luckily, it seems to be more than performant enough.

Solution (Jai)

/* Advent of Code 2024
 * Day 15: Warehouse Woes
 */

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

Tile :: enum {
    EMPTY;
    WALL;
    BOX;
    BOX_LEFT;
    BOX_RIGHT;
}

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

array_free_2d :: (array: [..][..] $T) {
    for array {
        array_free(it);
    }

    array_free(array);
}

is_box :: inline (tile: Tile) -> bool {
    return tile == .BOX || tile == .BOX_LEFT || tile == .BOX_RIGHT;
}

// Moves a box in a given direction. Does not perform any validity checks; that
// is all handled by push_box(). The inputs to this procedure are assumed to be
// valid.
move_box :: inline (
    map: [..][..] Tile,
    position: Vector2_Int,
    direction: Vector2_Int
) {
    tile := map[position.y][position.x];
    map[position.y][position.x] = .EMPTY;
    map[position.y + direction.y][position.x + direction.x] = tile;
}

// Attempts to push a box in a given direction, along with all boxes in its way.
// Returns whether the push was successful.
//
// If should_push is false, the procedure will return whether the push is
// possible, but will not actually move the boxes. This is necessary for part 2,
// where we have to check whether multiple pushes are possible before pushing
// some boxes (and thus don't want a possible push to still physically happen if
// the other push isn't possible).
push_box :: (
    map: [..][..] Tile,
    position: Vector2_Int,
    direction: Vector2_Int,
    should_push := true
) -> bool {
    tile := map[position.y][position.x];
    if direction.x == 0 && (tile == .BOX_LEFT || tile == .BOX_RIGHT) {
        other_side := ifx tile == .BOX_LEFT then 1 else -1;
        next_tile_1 := map[position.y + direction.y][position.x];
        next_tile_2 := map[position.y + direction.y][position.x + other_side];

        aligned_with_next_box := (
            tile == .BOX_LEFT && next_tile_1 == .BOX_LEFT
            || tile == .BOX_RIGHT && next_tile_2 == .BOX_LEFT
        );

        if
            aligned_with_next_box && push_box(map, .{
                position.x + ifx tile == .BOX_RIGHT then -1 else 0,
                position.y + direction.y
            }, direction, false)
            || (
                next_tile_1 == .EMPTY || is_box(next_tile_1) && push_box(map, .{
                    position.x,
                    position.y + direction.y
                }, direction, false)
            ) && (
                next_tile_2 == .EMPTY || is_box(next_tile_2) && push_box(map, .{
                    position.x + other_side,
                    position.y + direction.y
                }, direction, false)
            )
        {
            if should_push {
                // I'm not a huge fan of calling push_box() a second time here,
                // but without writing a separate can_push_box() procedure for
                // above (which would heavily complicate things), I don't think
                // there's a way around it. Either way, there are no performance
                // issues in the current version of the program, so it luckily
                // doesn't seem like much of a problem.
                if aligned_with_next_box {
                    push_box(map, .{
                        position.x + ifx tile == .BOX_RIGHT then -1 else 0,
                        position.y + direction.y
                    }, direction);
                } else {
                    if next_tile_1 != .EMPTY {
                        push_box(map, .{
                            position.x,
                            position.y + direction.y
                        }, direction);
                    }

                    if next_tile_2 != .EMPTY {
                        push_box(map, .{
                            position.x + other_side,
                            position.y + direction.y
                        }, direction);
                    }
                }

                move_box(map, position, direction);
                move_box(map, .{position.x + other_side, position.y}, direction);
            }

            return true;
        }
    } else {
        next_tile := map[position.y + direction.y][position.x + direction.x];
        if next_tile == .EMPTY || is_box(next_tile) && push_box(map, .{
            position.x + direction.x,
            position.y + direction.y
        }, direction, should_push) {
            if should_push {
                move_box(map, position, direction);
            }

            return true;
        }
    }

    return false;
}

// Performs a series of instructions on a robot in a warehouse, then calculates
// the sum of the GPS coordinates of the boxes in the warehouse after the robot
// has finished moving.
//
// We don't have to bother with bounds checking, because the warehouse is
// surrounded on all sides with walls.
get_gps_sum :: (
    map: [][..] Tile,
    robot: Vector2_Int,
    instructions: [] Vector2_Int
) -> int {
    // The map and robot parameters are immutable (since we don't want to modify
    // them outside this function), so since we need to be able to modify them
    // in this function, we thus need to make copies of them.
    mutable_map: [..][..] Tile;
    defer array_free_2d(mutable_map);

    for map {
        row: [..] Tile;
        array_copy(*row, it);
        array_add(*mutable_map, row);
    }

    mutable_robot := Vector2_Int.{robot.x, robot.y};

    for instructions {
        new_position := Vector2_Int.{
            mutable_robot.x + it.x,
            mutable_robot.y + it.y
        };

        new_tile := mutable_map[new_position.y][new_position.x];
        if new_tile == .EMPTY || is_box(new_tile) && push_box(
            mutable_map,
            new_position,
            it
        ) {
            mutable_robot = new_position;
        }
    }

    gps_sum := 0;
    for row, y: mutable_map {
        for tile, x: row {
            if tile == .BOX || tile == .BOX_LEFT {
                gps_sum += x + y * 100;
            }
        }
    }

    return gps_sum;
}

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

    groups := split(input, "\n\n");
    defer array_free(groups);

    map_lines := split(groups[0], "\n");
    defer array_free(map_lines);

    map: [..][..] Tile;
    defer array_free_2d(map);

    robot: Vector2_Int;
    for line, y: map_lines {
        row: [..] Tile;
        for char, x: line {
            if char == {
                case #char "@"; robot = .{x, y}; #through;
                case #char "."; array_add(*row, .EMPTY);
                case #char "#"; array_add(*row, .WALL);
                case #char "O"; array_add(*row, .BOX);
            }
        }

        array_add(*map, row);
    }

    instructions: [..] Vector2_Int;
    defer array_free(instructions);

    for groups[1] {
        if it == {
            case #char "<"; array_add(*instructions, .{-1, 0});
            case #char ">"; array_add(*instructions, .{1, 0});
            case #char "^"; array_add(*instructions, .{0, -1});
            case #char "v"; array_add(*instructions, .{0, 1});
        }
    }

    print("Part 1: %\n", get_gps_sum(map, robot, instructions));

    wide_map: [..][..] Tile;
    defer array_free_2d(wide_map);

    for map {
        row: [..] Tile;
        for it {
            if it == .BOX {
                array_add(*row, .BOX_LEFT);
                array_add(*row, .BOX_RIGHT);
            } else {
                array_add(*row, it);
                array_add(*row, it);
            }
        }

        array_add(*wide_map, row);
    }

    robot.x *= 2;
    print("Part 2: %\n", get_gps_sum(wide_map, robot, instructions));
}

My original solution for part 1 did not use recursion, and, in my opinion, was much nicer than what I ended up with. I'll include it here; it's a replacement for the get_gps_sum() procedure.

Part 1-only solution

// Attempts to push a box in a given direction, along with all boxes in its way.
// Returns whether the push was successful.
get_gps_sum :: (
    map: [][..] Tile,
    width: int,
    height: int,
    robot: Vector2_Int,
    instructions: [] Vector2_Int
) -> int {
    // The map and robot parameters are not pointers (since we don't want to
    // modify them outside this function), so they are immutable. Since we need
    // to be able to modify them in this function, we thus need to make copies
    // of them.
    mutable_map: [..][..] Tile;
    defer array_free_2d(mutable_map);

    for map {
        row: [..] Tile;
        array_copy(*row, it);
        array_add(*mutable_map, row);
    }

    mutable_robot := Vector2_Int.{robot.x, robot.y};

    for instructions {
        new_robot := Vector2_Int.{
            mutable_robot.x + it.x,
            mutable_robot.y + it.y
        };

        new_tile := mutable_map[new_robot.y][new_robot.x];
        if new_tile == .EMPTY {
            mutable_robot = new_robot;
        } else if
            new_tile == .BOX || new_tile == .BOX_LEFT || new_tile == .BOX_RIGHT
        {
            position := Vector2_Int.{new_robot.x + it.x, new_robot.y + it.y};
            while mutable_map[position.y][position.x] == .BOX {
                position.x += it.x;
                position.y += it.y;
            }

            if mutable_map[position.y][position.x] == .EMPTY {
                while true {
                    position.x -= it.x;
                    position.y -= it.y;

                    if
                        position.x == mutable_robot.x
                        && position.y == mutable_robot.y
                    {
                        break;
                    }

                    mutable_map[position.y][position.x] = .EMPTY;
                    mutable_map[position.y + it.y][position.x + it.x] = .BOX;
                }

                mutable_robot = new_robot;
            }
        }
    }

    gps_sum := 0;
    for row, y: mutable_map {
        for tile, x: row {
            if tile == .BOX || tile == .BOX_LEFT {
                gps_sum += x + y * 100;
            }
        }
    }

    return gps_sum;
}

2 votes

Comment on Day 14: Restroom Redoubt in ~comp.advent_of_code
lily
4 days, 19 hours ago
Link Parent
Yeah, the speed at which it worked and how it did so with no issues was surprising, and suggests to me that the designer may have thought of that solution - though, what I did and checking for the...

Yeah, the speed at which it worked and how it did so with no issues was surprising, and suggests to me that the designer may have thought of that solution - though, what I did and checking for the minimum safety scores are somewhat similar solutions, so it's possible that my method works because the former was planned for. I can't say I'm very satisfied with myself for figuring it out, though, since it was just a hunch that I didn't really expect to work (as you said, it seems unlikely that it would do so without the input being specifically prepared for it). I think there's a good puzzle somewhere in here, but it just needed some extra clarification in my opinion.

Comment on Day 14: Restroom Redoubt in ~comp.advent_of_code

lily

5 days, 8 hours ago

Link

I initially was ready to give up upon seeing part 2, because I thought I'd have to sit there and comb through an output log for ages to find the Christmas tree (which, in my opinion, would be a...

I initially was ready to give up upon seeing part 2, because I thought I'd have to sit there and comb through an output log for ages to find the Christmas tree (which, in my opinion, would be a terrible puzzle). I eventually realized there's no way that would be the intended solution, so tried a few conditions before settling on "no robots on the same space". I'm still not really happy with this puzzle, though, since "in the shape of a Christmas tree" is incredibly vague, and my solution was just a guess - there could easily be a Christmas tree shape with multiple robots on the same tile, it just seemed like the puzzle wouldn't have been designed that way to me. I don't know. Probably my least favorite day so far, because it doesn't feel there's a "foolproof" solution. This puzzle seems to have been designed more to be cute than to be interesting to solve.

Solution (Jai)

/* 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;
        }
    }
}

2 votes

Comment on Day 13: Claw Contraption in ~comp.advent_of_code

lily

5 days, 20 hours ago

Link

I'm not the strongest with math, but I got there in the end. The actual programming part for this wasn't especially difficult, though I got tripped up with floating-point precision for a little...

I'm not the strongest with math, but I got there in the end. The actual programming part for this wasn't especially difficult, though I got tripped up with floating-point precision for a little bit.

Solution (Jai)

/* Advent of Code 2024
 * Day 13: Claw Contraption
 */

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

Machine :: struct {
    // No reason to define Vector2_Int when we're only using it here. An
    // anonymous struct works just fine.
    button_a, button_b, prize: struct {
        x, y: int;
    };
}

get_token_cost :: (machines: [] Machine, limit_button_presses: bool) -> int {
    tokens := 0;
    for machines {
        // Saves some typing.
        button_a := it.button_a;
        button_b := it.button_b;
        prize := it.prize;

        determinant := button_a.x * button_b.y - button_b.x * button_a.y;

        a_presses := (
            button_b.y * prize.x - button_b.x * prize.y
        ) / determinant;

        b_presses := (
            button_a.x * prize.y - button_a.y * prize.x
        ) / determinant;

        if
            button_a.x * a_presses + button_b.x * b_presses == prize.x
            && button_a.y * a_presses + button_b.y * b_presses == prize.y
            && a_presses > 0 && b_presses > 0
            && (!limit_button_presses || a_presses <= 100 && b_presses <= 100)
        {
            tokens += a_presses * 3 + b_presses;
        }
    }

    return tokens;
}

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

    groups := split(input, "\n\n");
    defer array_free(groups);

    machines: [..] Machine;
    defer array_free(machines);

    for groups {
        // Conveniently, this approach means we don't have to worry about the
        // trailing newline at all; it's ignored automatically.
        lines := split(it, "\n");
        defer array_free(lines);

        button_a := split(slice(lines[0], 12, lines[0].count - 12), ", Y+");
        button_b := split(slice(lines[1], 12, lines[1].count - 12), ", Y+");
        prize := split(slice(lines[2], 9, lines[2].count - 9), ", Y=");
        defer array_free(button_a);
        defer array_free(button_b);
        defer array_free(prize);

        array_add(*machines, Machine.{
            .{string_to_int(button_a[0]), string_to_int(button_a[1])},
            .{string_to_int(button_b[0]), string_to_int(button_b[1])},
            .{string_to_int(prize[0]), string_to_int(prize[1])},
        });
    }

    print("Part 1: %\n", get_token_cost(machines, true));

    for *machines {
        it.prize.x += 10000000000000;
        it.prize.y += 10000000000000;
    }

    print("Part 2: %\n", get_token_cost(machines, false));
}

1 vote

Comment on Day 12: Garden Groups in ~comp.advent_of_code

lily

6 days, 19 hours ago

Link

Really interesting part 2 on this one! I solved the puzzle last night, but my solution was extremely slow; I took the time today to speed it up a little, and while it's still not especially fast,...

Really interesting part 2 on this one! I solved the puzzle last night, but my solution was extremely slow; I took the time today to speed it up a little, and while it's still not especially fast, it is a lot better. I think the way I'm solving part 2 is pretty naïve and ugly, but it was all I could think of.

Solution (Jai)

/* Advent of Code 2024
 * Day 12: Garden Groups
 */

#import "Basic";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

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

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    (a: Vector2_Int, b: Vector2_Int) -> bool {
        return a.x == b.x && a.y == b.y;
    }
);

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

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

    width := map[0].count;
    height := map.count;

    // Using an array like this appears to be faster than a table/set when we
    // don't need to count the elements.
    seen_positions := NewArray(width * height, bool);
    defer array_free(seen_positions);

    price_part_1 := 0;
    price_part_2 := 0;

    for x: 0..width - 1 {
        for y: 0..height - 1 {
            if seen_positions[y * width + x] {
                continue;
            }

            plant_type := map[y][x];
            position := Vector2_Int.{x, y};

            // Here, we need to count the elements (to find the area of the
            // plot) and iterate through them (to transfer all the plants in the
            // plot into seen_positions), so we're forced to use a set.
            plot: Vector2_Int_Set;
            table_add(*plot, position, #run {});
            defer deinit(*plot);

            // Because we're using arrays for fences_x and fences_y, we have to
            // store the perimeter separately.
            perimeter := 0;

            // These arrays store all the individual fences (like what is used
            // for part 1). fences_x stores vertical fences, and fences_y stores
            // horizontal ones - the arrays are named based on the direction the
            // fence is moved into from.
            //
            // The reason for using arrays is the same as with seen_positions,
            // though these need to be slightly bigger to fit all the fences.
            fences_x := NewArray((width + 1) * height, int);
            fences_y := NewArray(width * (height + 1), int);
            defer array_free(fences_x);
            defer array_free(fences_y);

            stack: [..] Vector2_Int;
            array_add(*stack, position);
            defer array_free(stack);

            while stack.count {
                current := pop(*stack);
                for *Vector2_Int.[
                    .{current.x - 1, current.y},
                    .{current.x + 1, current.y},
                    .{current.x, current.y - 1},
                    .{current.x, current.y + 1}
                ] {
                    if
                        it.x < 0 || it.x >= width || it.y < 0 || it.y >= height
                        || map[it.y][it.x] != plant_type
                    {
                        perimeter += 1;

                        // The first two indices are vertical sides, and the
                        // second two are horizontal.
                        if it_index < 2 {
                            if it_index == 0 {
                                it.x += 1;
                                fences_x[it.y * (width + 1) + it.x] = -1;
                            } else {
                                fences_x[it.y * (width + 1) + it.x] = 1;
                            }
                        } else {
                            if it_index == 2 {
                                it.y += 1;
                                fences_y[it.y * width + it.x] = -1;
                            } else {
                                fences_y[it.y * width + it.x] = 1;
                            }
                        }

                        continue;
                    }

                    if !table_contains(*plot, it) {
                        table_add(*plot, it, #run {});
                        array_add(*stack, it);
                    }
                }
            }

            price_part_1 += plot.count * perimeter;

            // I dislike having all this repeated code between vertical and
            // horizontal fences, but I'm not sure if there's a clean way to
            // make things less redundant. I'm just going to leave it.
            sides_x := 0;
            for fence_x: 0..width {
                in_side := false;
                side_bias: int;

                for fence_y: 0..height - 1 {
                    bias := fences_x[fence_y * (width + 1) + fence_x];
                    if bias != 0 {
                        if !in_side || bias != side_bias {
                            in_side = true;
                            side_bias = bias;
                            sides_x += 1;
                        }
                    } else if in_side {
                        in_side = false;
                    }
                }
            }

            sides_y := 0;
            for fence_y: 0..height {
                in_side := false;
                side_bias: int;

                for fence_x: 0..width - 1 {
                    bias := fences_y[fence_y * width + fence_x];
                    if bias != 0 {
                        if !in_side || bias != side_bias {
                            in_side = true;
                            side_bias = bias;
                            sides_y += 1;
                        }
                    } else if in_side {
                        in_side = false;
                    }
                }
            }

            price_part_2 += plot.count * (sides_x + sides_y);

            for plot {
                seen_positions[it_index.y * width + it_index.x] = true;
            }
        }
    }

    print("Part 1: %\nPart 2: %\n", price_part_1, price_part_2);
}

Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code

lily

December 12

Link

Wasn't able to figure out the right approach last night, but coming back to the puzzle today it luckily didn't take too long. This is probably still far from optimal, but it seems fast enough....

Wasn't able to figure out the right approach last night, but coming back to the puzzle today it luckily didn't take too long. This is probably still far from optimal, but it seems fast enough.

Solution (Jai)

/* Advent of Code 2024
 * Day 11: Plutonian Pebbles
 */

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

add_stones :: (stones: *Table(int, int), stone: int, amount: int) {
    old_amount, success := table_find(stones, stone);
    if success {
        table_set(stones, stone, old_amount + amount);
    } else {
        table_add(stones, stone, amount);
    }
}

get_stone_count :: (stones: *Table(int, int)) -> int {
    stone_count := 0;
    for stones {
        stone_count += it;
    }

    return stone_count;
}

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

    stones: Table(int, int);
    defer deinit(*stones);

    for split(input, " ") {
        table_add(*stones, string_to_int(it), 1);
    }

    for 1..75 {
        // We have to track the new stones separately to avoid processing
        // the same stones multiple times in the same blink.
        new_stones: Table(int, int);
        defer deinit(*new_stones);

        for stones {
            if it_index == 0 {
                add_stones(*new_stones, 1, it);
            } else {
                stone := it_index;
                digit_count := 1;

                while stone >= 10 {
                    stone /= 10;
                    digit_count += 1;
                }

                if digit_count % 2 == 0 {
                    divisor := 1;
                    for 1..digit_count / 2 {
                        divisor *= 10;
                    }

                    add_stones(*new_stones, it_index / divisor, it);
                    add_stones(*new_stones, it_index % divisor, it);
                } else {
                    add_stones(*new_stones, it_index * 2024, it);
                }
            }

            table_set(*stones, it_index, 0);
        }

        for new_stones {
            add_stones(*stones, it_index, it);
        }

        // We have to wait to remove stones until everything for this blink has
        // been processed.
        for stones {
            if it == 0 {
                remove it;
            }
        }

        if it == 25 {
            print("Part 1: %\n", get_stone_count(*stones));
        }
    }

    print("Part 2: %\n", get_stone_count(*stones));
}

1 vote

Comment on Day 10: Hoof It in ~comp.advent_of_code

lily

December 10

Link

I happened to solve part 1 on this in such a way that made part 2 extremely easy - in fact, at first when trying to solve part 1 I was accidentally getting the answer for part 2 instead! I had to...

I happened to solve part 1 on this in such a way that made part 2 extremely easy - in fact, at first when trying to solve part 1 I was accidentally getting the answer for part 2 instead! I had to add extra code to make part 1 work, so for part 2 all I had to do was what I was already doing before.

Solution (Jai)

/* Advent of Code 2024
 * Day 10: Hoof It
 */

#import "Basic";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

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

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    (a: Vector2_Int, b: Vector2_Int) -> bool {
        return a.x == b.x && a.y == b.y;
    }
);

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

    map: [..][..] int;
    defer {
        for map {
            array_free(it);
        }

        array_free(map);
    }

    trailheads: [..] Vector2_Int;
    defer array_free(trailheads);

    for line, y: split(input, "\n") {
        if line == "" {
            continue;
        }

        row: [..] int;
        for char, x: line {
            array_add(*row, char - #char "0");

            if char == #char "0" {
                array_add(*trailheads, .{x, y});
            }
        }

        array_add(*map, row);
    }

    width := map[0].count;
    height := map.count;

    score_sum := 0;
    rating_sum := 0;

    for trailheads {
        trails: [..][..] Vector2_Int;
        defer array_free(trails);

        trail: [..] Vector2_Int;
        array_add(*trail, it);
        array_add(*trails, trail);

        reachable_peaks: Vector2_Int_Set;
        defer deinit(*reachable_peaks);

        while trails.count {
            trail := pop(*trails);
            defer array_free(trail);

            tile := trail[trail.count - 1];
            current_height := map[tile.y][tile.x];

            for Vector2_Int.[
                .{tile.x - 1, tile.y},
                .{tile.x + 1, tile.y},
                .{tile.x, tile.y - 1},
                .{tile.x, tile.y + 1}
            ] {
                if
                    it.x >= 0 && it.x < width && it.y >= 0 && it.y < height
                    && map[it.y][it.x] == current_height + 1
                {
                    if map[it.y][it.x] == 9 {
                        if !table_contains(*reachable_peaks, it) {
                            table_add(*reachable_peaks, it, #run {});
                        }

                        rating_sum += 1;
                    } else {
                        new_trail: [..] Vector2_Int;
                        array_copy(*new_trail, trail);
                        array_add(*new_trail, it);
                        array_add(*trails, new_trail);
                    }
                }
            }
        }

        score_sum += reachable_peaks.count;
    }

    print("Part 1: %\nPart 2: %\n", score_sum, rating_sum);
}

2 votes

Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code

lily

December 9

Link

Really enjoyed this one! Performance wasn't great at first on part 1, but I was able to mostly solve that problem by figuring out a better method of detecting gaps between files. I think my code...

Really enjoyed this one! Performance wasn't great at first on part 1, but I was able to mostly solve that problem by figuring out a better method of detecting gaps between files. I think my code here is a little messy, but I'm not really in the mood to refactor...

Solution (Jai)

/* Advent of Code 2024
 * Day 09: Disk Fragmenter
 */

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

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

    disk_part_1: [..] int;
    defer array_free(disk_part_1);

    creating_file := true;
    file_index := 0;
    max_file_index := 0;

    file_disk_positions: [..] int;
    file_sizes: [..] int;
    defer array_free(file_disk_positions);
    defer array_free(file_sizes);

    for input {
        // For some reason, leaving this out (and thus treating the trailing
        // newline as a size of 218, due to how the size is calculated) doesn't
        // seem to affect the results? To be safe, I'm going to keep it in, just
        // in case it's only a quirk with my input specifically.
        if it == #char "\n" {
            continue;
        }

        // We need the size twice if we're creating a file, so it's better to
        // define it up here.
        size := it - #char "0";

        block: int;
        if creating_file {
            block = file_index;

            if file_index > max_file_index {
                max_file_index = file_index;
            }

            file_index += 1;

            array_add(*file_disk_positions, disk_part_1.count);
            array_add(*file_sizes, size);
        } else {
            block = -1;
        }

        for 1..size {
            array_add(*disk_part_1, block);
        }

        creating_file = !creating_file;
    }

    // Needed to detect gaps in part 1.
    file_size_total := 0;
    for file_sizes {
        file_size_total += it;
    }

    // We need to do this before the disk is modified for part 1. This doesn't
    // need to be a resizeable array because unlike in part 1, we won't be
    // popping blocks off it like it's a stack.
    disk_part_2 := array_copy(disk_part_1);
    defer array_free(disk_part_2);

    while part_1_loop := true {
        block := pop(*disk_part_1);
        if block == -1 {
            continue;
        }

        for disk_part_1 {
            if it == -1 {
                disk_part_1[it_index] = block;
                break;
            }
        }

        // If there are no remaining gaps between files, we're finished.
        for disk_part_1 {
            if it == -1 {
                break;
            }

            if it_index == file_size_total - 1 {
                break part_1_loop;
            }
        }
    }

    // Because it's guaranteed in part 1 that there will be no gaps between
    // files, we can stop looping here as soon as we reach an empty block.
    checksum_part_1 := 0;
    for disk_part_1 {
        if it == -1 {
            break;
        }

        checksum_part_1 += it * it_index;
    }

    print("Part 1: %\n", checksum_part_1);

    // You have to mark for loops with #v2 right now for the new reversing
    // behavior to work. This will eventually no longer be required, so if I
    // remember I'll remove the #v2 here when that happens.
    for #v2 < file_index: 0..max_file_index {
        position := file_disk_positions[file_index];
        size := file_sizes[file_index];

        moved_file := false;
        for new_position: 0..position - 1 {
            end := new_position + size - 1;

            for new_position..end {
                if disk_part_2[it] != -1 {
                    continue new_position;
                }
            }

            for new_position..end {
                disk_part_2[it] = file_index;
            }

            moved_file = true;

            // There's a kind of unusual loop structure here, where if we reach
            // the end of the loop we always break. Maybe this could be
            // refactored for better clarity, though it reads okay to me right
            // now.
            break;
        }

        if moved_file {
            for position..position + size - 1 {
                disk_part_2[it] = -1;
            }
        }
    }

    // Unlike in part 1, there may be gaps between files, so we're forced to
    // iterate through the whole disk.
    checksum_part_2 := 0;
    for disk_part_2 {
        if it != -1 {
            checksum_part_2 += it * it_index;
        }
    }

    print("Part 2: %\n", checksum_part_2);
}

2 votes

Comment on Day 8: Resonant Collinearity in ~comp.advent_of_code

lily

December 8

Link

I found this pretty easy compared to the last couple days. I was confused about how the puzzle worked when first reading it, but once I figured that out I had almost no struggles implementing a...

I found this pretty easy compared to the last couple days. I was confused about how the puzzle worked when first reading it, but once I figured that out I had almost no struggles implementing a solution. I should probably split the Vector2_Int stuff into a separate file at this point, since it seems to be getting used in almost every puzzle...

Solution (Jai)

/* Advent of Code 2024
 * Day 08: Resonant Collinearity
 */

#import "Basic";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

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

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    (a: Vector2_Int, b: Vector2_Int) -> bool {
        return a.x == b.x && a.y == b.y;
    }
);

// Finds all valid antinodes, moving outwards from an antenna. This is called
// twice for each antenna pair.
find_antinodes :: (
    antenna: Vector2_Int,
    slope: Vector2_Int,
    width: int,
    height: int
) -> [] Vector2_Int {
    antinode := antenna;
    antinodes: [..] Vector2_Int;

    while true {
        array_add(*antinodes, antinode);

        antinode.x += slope.x;
        antinode.y += slope.y;

        if
            antinode.x < 0 || antinode.x >= width
            || antinode.y < 0 || antinode.y >= height
        {
            break;
        }
    }

    return antinodes;
}

// Adds the current antinode in a for loop to the correct tables. Saves some
// repetition lower down.
add_antinode :: () #expand {
    // The first antinode is on the antenna itself, so the second one is what is
    // relevant for part 1.
    if `it_index == 1 && !table_contains(*`antinodes_part_1, `it) {
        table_add(*`antinodes_part_1, `it, #run {});
    }

    if !table_contains(*`antinodes_part_2, `it) {
        table_add(*`antinodes_part_2, `it, #run {});
    }
}

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

    lines := split(input, "\n");
    width := lines[0].count;
    height := lines.count - 1;

    antennas: Table(u8, [..] Vector2_Int);
    for line, y: lines {
        if line == "" {
            continue;
        }

        for char, x: line {
            if char == #char "." {
                continue;
            }

            antenna_group := table_find_pointer(*antennas, char);
            if antenna_group == null {
                new_group: [..] Vector2_Int;
                table_add(*antennas, char, new_group);
                antenna_group = table_find_pointer(*antennas, char);
            }

            array_add(antenna_group, .{x, y});
        }
    }

    antinodes_part_1, antinodes_part_2: Vector2_Int_Set;
    for antenna_group: antennas {
        for index_1: 0..antenna_group.count - 1 {
            for index_2: 0..antenna_group.count - 1 {
                if index_2 == index_1 {
                    continue;
                }

                antenna_1 := antenna_group[index_1];
                antenna_2 := antenna_group[index_2];

                for find_antinodes(
                    antenna_1,
                    .{antenna_1.x - antenna_2.x, antenna_1.y - antenna_2.y},
                    width,
                    height
                ) {
                    add_antinode();
                }

                for find_antinodes(
                    antenna_2,
                    .{antenna_2.x - antenna_1.x, antenna_2.y - antenna_1.y},
                    width,
                    height
                ) {
                    add_antinode();
                }
            }
        }

        array_free(antenna_group);
    }

    print(
        "Part 1: %\nPart 2: %\n",
        antinodes_part_1.count,
        antinodes_part_2.count
    );
}

4 votes

Comment on Day 7: Bridge Repair in ~comp.advent_of_code

lily

December 7

Link

Not at all happy with my solution today; it's really slow and just the first thing I thought of to do. These kinds of "place the operators" puzzles have always stumped me for some reason. I had to...

Not at all happy with my solution today; it's really slow and just the first thing I thought of to do. These kinds of "place the operators" puzzles have always stumped me for some reason. I had to write a permutation finding procedure manually, since nothing like that comes with the compiler, but that didn't take too long.

Solution (Jai)

/* Advent of Code 2024
 * Day 07: Bridge Repair
 */

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

Operator :: enum {
    ADD;
    MULTIPLY;
    CONCATENATE;
}

// Finds all permutations of an arbitrary length made up of elements from a
// given array. Repeats are allowed.
find_permutations :: (elements: [] $T, length: int) -> [][..] T {
    permutations: [..][..] T;
    queue: [..][..] T;

    for elements {
        permutation: [..] T;
        array_add(*permutation, it);
        array_add(*queue, permutation);
    }

    while queue.count {
        permutation := pop(*queue);
        if permutation.count == length {
            array_add(*permutations, permutation);
            continue;
        }

        for elements {
            new_permutation: [..] T;
            array_copy(*new_permutation, permutation);
            array_add(*new_permutation, it);
            array_add(*queue, new_permutation);
        }
    }

    return permutations;
}

is_equation_possible :: (
    required_result: int,
    numbers: [] int,
    operators: [] Operator
) -> bool {
    // Not much of an ingenious solution here. There is probably a faster way to
    // solve this than bruteforcing (again...), but this works well enough.
    for operators: find_permutations(operators, numbers.count - 1) {
        result := numbers[0];
        for 1..numbers.count - 1 {
            if operators[it - 1] == {
                case .ADD; result += numbers[it];
                case .MULTIPLY; result *= numbers[it];

                case .CONCATENATE;
                    power := 10;
                    next_number := numbers[it];

                    while power <= next_number {
                        power *= 10;
                    }

                    result *= power;
                    result += next_number;
            }
        }

        array_free(operators);

        if result == required_result {
            return true;
        }
    }

    return false;
}

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

    total_part_1 := 0;
    total_part_2 := 0;

    for split(input, "\n") {
        if it == "" {
            continue;
        }

        parts := split(it, ": ");
        required_result := string_to_int(parts[0]);

        numbers: [..] int;
        for split(parts[1], " ") {
            array_add(*numbers, string_to_int(it));
        }

        if is_equation_possible(required_result, numbers, .[.ADD, .MULTIPLY]) {
            total_part_1 += required_result;
        }

        if is_equation_possible(
            required_result,
            numbers,
            .[.ADD, .MULTIPLY, .CONCATENATE]
        ) {
            total_part_2 += required_result;
        }
    }

    print("Part 1: %\nPart 2: %\n", total_part_1, total_part_2);
}

1 vote

Comment on Day 6: Guard Gallivant in ~comp.advent_of_code

lily

December 6 (edited December 6)

Link

This takes about 4 seconds on my machine in release mode, and about 15 in debug... so, I feel there has to be a smarter way to solve this. Or maybe my code specifically is just very bad, I don't...

This takes about 4 seconds on my machine in release mode, and about 15 in debug... so, I feel there has to be a smarter way to solve this. Or maybe my code specifically is just very bad, I don't know.

EDIT: Okay, after reading about people getting better execution times than me in Python, I'm almost sure I did something wrong. Might take another stab at this later today.

EDIT 2: I fixed it! It now takes half a second in debug mode, and about 50 milliseconds in release mode. Much better. It turns out all I had to do was replace the set used for cycle detection with an array, and the program became an order of magnitude faster. I've replaced the code below with the new solution.

Solution (Jai)

/* Advent of Code 2024
 * Day 06: Guard Gallivant
 */

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

using Hash_Table :: #import "Hash_Table";
#poke_name Hash_Table operator ==;

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

// Maybe the guard doesn't have to be a struct, but it makes the program more
// readable and doesn't have any performance impact. It's also possible
// "direction" could be an enum, but then the simulation code would be a little
// less clean...
Guard :: struct {
    position, direction: Vector2_Int;
}

// Inlining all these procedures makes the bruteforcing faster. Maybe.
operator == :: inline (a: Vector2_Int, b: Vector2_Int) -> bool {
    return a.x == b.x && a.y == b.y;
}

Vector2_Int_Table :: Table(Vector2_Int, void, (vector: Vector2_Int) -> u32 {
    return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
});

// This function behaves differently depending on which part of the puzzle it is
// supposed to be solving. This is important to avoid unnecessarily wasting time
// on recording the unique positions visited by the guard during part 2, which
// slows the bruteforcing down considerably. While this procedure returns
// multiple values (the set of unique positions, and whether the guard entered a
// loop), the first one will always be an empty set during part 2.
simulate_guard :: inline (
    map: [..][..] bool,
    width: int,
    height: int,
    initial_guard: Guard,
    part: int
) -> Vector2_Int_Table, bool {
    unique_positions: Vector2_Int_Table;

    // This is _much_ faster than using a set. I'm keeping this as a flat array
    // to avoid unnecessary allocations - I tried using a flat array for the map
    // itself too, but the overhead of calculating the index constantly seemed
    // to slow the program down very slightly (by milliseconds - I'm splitting
    // hairs here!).
    previous_guard_states := NewArray(width * height, [4] bool);
    defer array_free(previous_guard_states);

    guard := initial_guard;
    while true {
        // It looks a little weird, but using #run {} allows you to add keys to
        // a table with void as the value type (which is useful to lower memory
        // usage when using a table as a set).
        if part == 1 {
            if !table_contains(*unique_positions, guard.position) {
                table_add(*unique_positions, guard.position, #run {});
            }
        } else {
            position_index := guard.position.x * width + guard.position.y;

            direction_index: int;
            if      guard.direction == .{1, 0}  direction_index = 0;
            else if guard.direction == .{0, 1}  direction_index = 1;
            else if guard.direction == .{-1, 0} direction_index = 2;
            else if guard.direction == .{0, -1} direction_index = 3;

            if previous_guard_states[position_index][direction_index] {
                return unique_positions, true;
            } else {
                previous_guard_states[position_index][direction_index] = true;
            }
        }

        guard.position.x += guard.direction.x;
        guard.position.y += guard.direction.y;

        if
            guard.position.x < 0 || guard.position.x >= width
            || guard.position.y < 0 || guard.position.y >= height
        {
            break;
        }

        if map[guard.position.y][guard.position.x] {
            guard.position.x -= guard.direction.x;
            guard.position.y -= guard.direction.y;
            guard.direction = .{-guard.direction.y, guard.direction.x};
        }
    }

    return unique_positions, false;
}

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

    map: [..][..] bool;
    guard: Guard;
    guard.direction = .{0, -1};

    for line, y: split(input, "\n") {
        if line == "" {
            continue;
        }

        row: [..] bool;
        for char, x: line {
            array_add(*row, ifx char == #char "#" then true else false);

            if char == #char "^" {
                guard.position = .{x, y};
            }
        }

        array_add(*map, row);
    }

    width := map[0].count;
    height := map.count;

    unique_positions, _ := simulate_guard(map, width, height, guard, 1);
    print("Part 1: %\n", unique_positions.count);

    loop_causing_obstructions := 0;
    for unique_positions {
        map[it_index.y][it_index.x] = true;

        _, entered_loop := simulate_guard(map, width, height, guard, 2);
        if entered_loop {
            loop_causing_obstructions += 1;
        }

        map[it_index.y][it_index.x] = false;
    }

    print("Part 2: %\n", loop_causing_obstructions);
}

2 votes

Comment on Day 5: Print Queue in ~comp.advent_of_code

lily

December 5

Link

This one was pretty fun! I managed to squeeze everything into one loop through the input. Part 2 was pretty easy, since the ordering rules can just be used as a comparison procedure (that's the...

This one was pretty fun! I managed to squeeze everything into one loop through the input. Part 2 was pretty easy, since the ordering rules can just be used as a comparison procedure (that's the "correct" thing to call functions in Jai... I'm not used to it...). There's probably a far more efficient way to solve it than that, but oh well.

Solution (Jai)

/* Advent of Code 2024
 * Day 05: Print Queue
 */

#import "Basic";
#import "File";
#import "Hash_Table";
#import "Sort";
#import "String";

// I'm not sure how to make page_compare() work without this being global.
ordering_rules: [..][2] int;

// The ordering rules map nicely to a comparison procedure. It feels really
// inefficient to iterate through the whole rules array for every comparison,
// but I'm not sure how else it could be done.
page_compare :: (a: int, b: int) -> int {
    for ordering_rules {
        if it[0] == a && it[1] == b {
            return -1;
        } else if it[0] == b && it[1] == a {
            return 1;
        }
    }

    return 0;
}

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

    read_all_rules := false;
    correct_middle_page_sum := 0;
    incorrect_middle_page_sum := 0;

    for split(input, "\n") {
        // The two parts of the input are separated by a blank line. As usual,
        // we need to ignore the trailing newline if one exists in the input,
        // but this time we can't ignore the first one.
        if it == "" {
            if read_all_rules {
                continue;
            } else {
                read_all_rules = true;
            }
        }

        if !read_all_rules {
            pages := split(it, "|");
            array_add(
                *ordering_rules,
                .[string_to_int(pages[0]), string_to_int(pages[1])]
            );

            continue;
        }

        pages: [..] int;
        page_indices: Table(int, int);

        for split(it, ",") {
            page := string_to_int(it);
            array_add(*pages, page);
            table_add(*page_indices, page, it_index);
        }

        correctly_ordered := true;
        for ordering_rules {
            first_index,  found_first  := table_find(*page_indices, it[0]);
            second_index, found_second := table_find(*page_indices, it[1]);

            if found_first && found_second && first_index > second_index {
                correctly_ordered = false;
                break;
            }
        }

        if correctly_ordered {
            correct_middle_page_sum += pages[pages.count / 2];
        } else {
            sorted_pages := quick_sort(pages, page_compare);
            incorrect_middle_page_sum += sorted_pages[sorted_pages.count / 2];
        }
    }

    print(
        "Part 1: %\nPart 2: %\n",
        correct_middle_page_sum,
        incorrect_middle_page_sum
    );
}

3 votes

Comment on Day 4: Ceres Search in ~comp.advent_of_code

lily

December 4

Link

This one was kind of uninteresting to me. I knew how I was going to solve it nearly instantly upon reading the problem text. Maybe it's not a clever solution, but then I don't know that this...

This one was kind of uninteresting to me. I knew how I was going to solve it nearly instantly upon reading the problem text. Maybe it's not a clever solution, but then I don't know that this puzzle really deserves a clever solution. It's just a word search. Part 2 was even easier - I solved it in only a couple minutes.

Solution (Jai)

/* Advent of Code 2024
 * Day 04: Ceres Search
 */

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

// The Vector2 struct in the Math module uses floats, which we don't want since
// we're using this struct as a modifier for array indices.
Vector2_Int :: struct {
    x, y: int;
}

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

    rows := split(input, "\n");
    rows.count -= 1; // We're assuming a trailing newline.

    xmas_count := 0;
    for row, y: rows {
        for char, x: row {
            if char == #char "X" {
                // There's no point checking for the remaining letters if there
                // isn't space for them anyway.
                right_allowed := x <= row.count - 4;
                left_allowed  := x >= 3;

                if right_allowed && slice(row, x + 1, 3) == "MAS" {
                    xmas_count += 1;
                }

                if left_allowed && slice(row, x - 3, 3) == "SAM" {
                    xmas_count += 1;
                }

                directions: [..] Vector2_Int;

                if y <= rows.count - 4 {
                    array_add(*directions, .{0, 1});
                    if right_allowed array_add(*directions, .{1, 1});
                    if left_allowed  array_add(*directions, .{-1, 1});
                }

                if y >= 3 {
                    array_add(*directions, .{0, -1});
                    if right_allowed array_add(*directions, .{1, -1});
                    if left_allowed  array_add(*directions, .{-1, -1});
                }

                for direction: directions {
                    found_letters: [3] u8;

                    scan_x := x;
                    scan_y := y;

                    for 0..2 {
                        scan_x += direction.x;
                        scan_y += direction.y;
                        found_letters[it] = rows[scan_y][scan_x];
                    }

                    if xx found_letters == "MAS" {
                        xmas_count += 1;
                    }
                }
            }
        }
    }

    print("Part 1: %\n", xmas_count);

    x_mas_count := 0;
    for y: 1..rows.count - 2 {
        for x: 1..rows[y].count - 2 {
            // The middle character will always be A.
            if rows[y][x] == #char "A" {
                // Maybe there's a better way to do this.
                if (
                    (
                        rows[y - 1][x - 1] == #char "M"
                        && rows[y + 1][x + 1] == #char "S"
                    ) || (
                        rows[y - 1][x - 1] == #char "S"
                        && rows[y + 1][x + 1] == #char "M"
                    )
                ) && (
                    (
                        rows[y + 1][x - 1] == #char "M"
                        && rows[y - 1][x + 1] == #char "S"
                    ) || (
                        rows[y + 1][x - 1] == #char "S"
                        && rows[y - 1][x + 1] == #char "M"
                    )
                ) {
                    x_mas_count += 1;
                }
            }
        }
    }

    print("Part 2: %\n", x_mas_count);
}

1 vote

Comment on Day 3: Mull It Over in ~comp.advent_of_code

lily

December 3

Link

Someone has written a regex module for Jai, but it doesn't have an in-built way to find all matches, so I wasn't able to use it. Luckily, it wasn't too bad to solve this without regex - I just...

Someone has written a regex module for Jai, but it doesn't have an in-built way to find all matches, so I wasn't able to use it. Luckily, it wasn't too bad to solve this without regex - I just used a sliding window and verified the instructions manually. A little verbose, maybe, but good enough.

Solution (Jai)

/* Advent of Code 2024
 * Day 03: Mull It Over
 */

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

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

    result_sum := 0;
    result_sum_conditional := 0;
    mul_enabled := true;

    // The shortest valid instruction is 4 characters long (do()), so
    // technically with this range, if do() appeared at the very end of the
    // input, we would ignore it. However, that's not a concern, since at that
    // point there is no more room for mul() instructions anyway, meaning the
    // do() instruction would be effectively useless.
    for 0..input.count - 9 {
        // Don't waste time checking slices that aren't even a possibility.
        // The only valid instructions start with m (mul) or d (do/don't).
        if input[it] != #char "m" && input[it] != #char "d" {
            continue;
        }

        // The maximum instruction size is 12 (a mul() instruction with two
        // three-digit numbers).
        instruction := slice(
            input,
            it,
            ifx it >= input.count - 12 then input.count - it else 12
        );

        end_index := find_index_from_left(instruction, #char ")");
        if end_index == -1 {
            continue;
        }

        trimmed_instruction := slice(instruction, 0, end_index + 1);
        if slice(trimmed_instruction, 0, 4) == "mul(" {
            numbers := split(
                slice(trimmed_instruction, 4, trimmed_instruction.count - 5),
                ","
            );

            if numbers.count == 2 {
                valid := true;
                for numbers {
                    all_numbers := true;
                    for it {
                        if it < #char "0" || it > #char "9" {
                            all_numbers = false;
                            break;
                        }
                    }

                    if !all_numbers {
                        valid = false;
                        break;
                    }
                }

                if valid {
                    result := (
                        string_to_int(numbers[0]) * string_to_int(numbers[1])
                    );

                    result_sum += result;
                    if mul_enabled {
                        result_sum_conditional += result;
                    }
                }
            }
        } else if trimmed_instruction == {
            case "do()";    mul_enabled = true;
            case "don't()"; mul_enabled = false;
        }
    }

    print("Part 1: %\nPart 2: %\n", result_sum, result_sum_conditional);
}

3 votes

Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code

lily

December 2

Link

There's probably a smarter way to do part 2... but I couldn't be bothered to figure it out. The brute-force method was good enough for me. Incidentally, there should really be a sign()...

There's probably a smarter way to do part 2... but I couldn't be bothered to figure it out. The brute-force method was good enough for me.

Incidentally, there should really be a sign() implementation in the Math module. Not that it's hard to write one myself - it just feels like an odd gap in the standard library.

Solution (Jai)

/* Advent of Code 2024
 * Day 02: Red-Nosed Reports
 */

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

sign :: (n: int) -> int {
    if n > 0 return 1;
    if n < 0 return -1;
    return 0;
}

is_report_safe :: (report: [] int) -> bool {
    difference_sign := 0;
    for 1..report.count - 1 {
        difference := report[it] - report[it - 1];

        if difference_sign == 0 {
            difference_sign = sign(difference);
        } else if sign(difference) != difference_sign {
            return false;
        }

        if abs(difference) < 1 || abs(difference) > 3 {
            return false;
        }
    }

    return true;
}

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

    reports: [..][..] int;
    for split(input, "\n") {
        if it == "" {
            continue;
        }

        report: [..] int;
        for split(it, " ") {
            array_add(*report, string_to_int(it));
        }

        array_add(*reports, report);
    }

    safe_reports := 0;
    mostly_safe_reports := 0;

    for report: reports {
        if is_report_safe(report) {
            safe_reports += 1;
            mostly_safe_reports += 1;
        } else {
            for 0..report.count - 1 {
                modified_report := array_copy(report);
                array_ordered_remove_by_index(*modified_report, it);

                if is_report_safe(modified_report) {
                    mostly_safe_reports += 1;
                    break;
                }
            }
        }
    }

    print("Part 1: %\nPart 2: %\n", safe_reports, mostly_safe_reports);
}

4 votes

Comment on Day 1: Historian Hysteria in ~comp.advent_of_code

lily

December 1

Link

I'm trying out the Jai language for the first time, after getting into the beta recently (I didn't expect I'd be qualified enough to get in, but I'll take what I can get!). Probably not the...

I'm trying out the Jai language for the first time, after getting into the beta recently (I didn't expect I'd be qualified enough to get in, but I'll take what I can get!). Probably not the smartest choice for solving puzzles quickly, but I'll take the opportunity to learn something new. It's an interesting language. This solution is a little verbose and maybe not optimal or the best / most idiomatic way to do things in Jai, but at least it solves the problem.

Solution

/* Advent of Code 2024
 * Day 01: Historian Hysteria
 */

#import "Basic";
#import "File";
#import "Hash_Table";
#import "Math";
#import "Sort";
#import "String";

int_compare :: (a: int, b: int) -> int {
    if a > b return 1;
    if a < b return -1;
    return 0;
}

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

    left_column: [..] int;
    right_column: [..] int;

    for split(input, "\n") {
        numbers := split(it, "   ");
        if numbers.count < 2 {
            break;
        }

        array_add(*left_column, string_to_int(numbers[0]));
        array_add(*right_column, string_to_int(numbers[1]));
    }

    quick_sort(left_column, int_compare);
    quick_sort(right_column, int_compare);

    difference_sum := 0;
    for 0..left_column.count - 1 {
        difference_sum += abs(left_column[it] - right_column[it]);
    }

    print("Part 1: %\n", difference_sum);

    right_column_occurrences: Table(int, int);
    similarity := 0;

    for left_column {
        occurrences, success := table_find(*right_column_occurrences, it);
        if !success {
            occurrences = 0;
            for other: right_column {
                if other == it {
                    occurrences += 1;
                }
            }

            table_set(*right_column_occurrences, it, occurrences);
        }

        similarity += it * occurrences;
    }

    print("Part 2: %\n", similarity);
}

4 votes