lily's recent activity

Comment on Day 11: Reactor in ~comp.advent_of_code

lily

16 hours, 14 minutes ago

Link

Glad to have an easy day for a change! Just a simple recursive search with memoization (not needed for part 1, but it doesn't hurt). Part 2 is just the product of the solutions to three separate...

Glad to have an easy day for a change! Just a simple recursive search with memoization (not needed for part 1, but it doesn't hurt). Part 2 is just the product of the solutions to three separate problems solved the same way as part 1. Would've finished this quicker if I hadn't wasted time writing a naive BFS solution that would take forever to finish executing, but oh well. I wonder what tomorrow will be like... this feels a bit like the calm before the storm.

Solution (Lily)

var outputs: Hash[String, List[String]] = []
for line in File.read_to_string("inputs/day_11.txt").split("\n"): {
    var parts = line.split(": ")
    outputs[parts[0]] = parts[1].split(" ")
}

var cached_paths: Hash[String, Integer] = []
define paths_between(start: String, end: String): Integer {
    if start == end: {
        return 1
    }

    if start == "out": {
        return 0
    }

    var key = start ++ end

    with cached_paths.get(key) as Some(paths): {
        return paths
    }

    var paths = 0
    for output in outputs[start]: {
        paths += paths_between(output, end)
    }

    cached_paths[key] = paths
    return paths
}

print("Part 1: {}".format(paths_between("you", "out")))

var queue = ["svr"]
var first_midpoint = ""

do: {
    var device = queue.shift()

    if device == "dac": {
        first_midpoint = "dac"
        break
    }

    if device == "fft": {
        first_midpoint = "fft"
        break
    }

    for output in outputs[device]: {
        queue.push(output)
    }
} while queue

var second_midpoint = (first_midpoint == "dac" ? "fft" : "dac")

print("Part 2: {}".format(
    paths_between("svr", first_midpoint)
    * paths_between(first_midpoint, second_midpoint)
    * paths_between(second_midpoint, "out")
))

2 votes

Comment on Day 10: Factory in ~comp.advent_of_code

lily

20 hours, 1 minute ago (edited 19 hours, 23 minutes ago)

Link

Whew, this was difficult... I came very close to throwing in the towel. I'm not the strongest with linear algebra, so part 2 took me a lot of Googling and looking at examples of Gaussian...

Whew, this was difficult... I came very close to throwing in the towel. I'm not the strongest with linear algebra, so part 2 took me a lot of Googling and looking at examples of Gaussian elimination. I eventually arrived at a solution that runs in just over a second on my machine, which I'm happy enough with. I ended up with a lot more code than I'd prefer for an Advent of Code problem, but maybe that's just the way it has to be with today's puzzle.

Explanation

For part 1, I just iterated through all the combinations until I found one that worked. I wanted to iterate through them in ascending order of number of presses, so that I didn't have to go through every combination - after some searching I discovered Gosper's hack, which let me do it with bitsets (which is maybe more efficient than the alternative?).

Part 2 was rough. I realized I needed to solve linear systems almost immediately, but actually doing so was another story. I've never really done linear algebra before, so it took me a while (and a couple hints taken from other people's descriptions of their solutions) to figure out how to even start. What I ended up doing is:

Build an augmented matrix for the given machine.
Use Gaussian elimination over the matrix, and find the pivot and free columns.
Iterate through all possible combinations of values for the free variables and back-substitute. Find the solution with the smallest sum of its coefficients, and add that sum to the total. This is the inefficient part - I know each button can't be pressed any more times than the counter it affects with the lowest required joltage, but those bounds seem to be a little too large, which slows things down a lot. I couldn't figure out how to get the bounds any lower, though.

Solution (Lily)

var total_presses_for_lights = 0
var total_presses_for_joltages = 0

for line in File.read_to_string("inputs/day_10.txt").split("\n"): {
    var parts = line.split(" ")

    var lights: List[Boolean] = []
    parts.shift().slice(1, -1).to_bytestring().each_byte(|char|
        lights.push(char == '#')
    )

    var max_light_index = lights.size() - 1

    var required_state = 0
    for i, light in lights.reverse(): {
        if light: {
            required_state |= 1 << i
        }
    }

    var buttons: List[List[Integer]] = []
    var required_joltages: List[Integer] = []

    for part in parts: {
        var numbers = part
            .slice(1, -1)
            .split(",")
            .map(String.parse_i)
            .map(Option.unwrap)

        if part[0] == '(': {
            buttons.push(numbers)
        else:
            required_joltages = numbers
            break
        }
    }

    var button_count = buttons.size()
    var max_button_index = button_count - 1
    var button_mask_limit = 1 << button_count
    var reached_required_state = false

    for presses in 1...button_count: {
        var button_mask = (1 << presses) - 1
        while button_mask < button_mask_limit: {
            var state = 0

            for button_index in 0...max_button_index: {
                if button_mask & 1 << max_button_index - button_index: {
                    for light_index in buttons[button_index]: {
                        state ^= 1 << max_light_index - light_index
                    }
                }
            }

            if state == required_state: {
                total_presses_for_lights += presses
                reached_required_state = true
                break
            }

            # Use Gosper's hack to find the next combination of presses with the
            # same length. This lets us avoid having to iterate through every
            # combination to find the shortest working one.
            var c = button_mask & -button_mask
            var r = button_mask + c
            button_mask = (((r ^ button_mask) >> 2) / c) | r
        }

        if reached_required_state: {
            break
        }
    }

    var rows = required_joltages.map_with_index(|joltage, index|
        buttons.map(|button| button.any(|i| i == index).to_i()).push(joltage)
    )

    var width = buttons.size()
    var height = rows.size()

    var row = 0
    var pivot_columns: List[Integer] = []
    var free_columns: List[Integer] = []

    for column in 0...width - 1: {
        var pivot = -1

        for i in row...height - 1: {
            if rows[i][column]: {
                pivot = i
                break
            }
        }

        if pivot == -1: {
            free_columns.push(column)
            continue
        }

        var temp = rows[row]
        rows[row] = rows[pivot]
        rows[pivot] = temp

        for i in row + 1...height - 1: {
            var value = rows[i][column]
            if value: {
                var pivot_value = rows[row][column]
                for j in 0...width: {
                    rows[i][j] = rows[i][j] * pivot_value - rows[row][j] * value
                }
            }
        }

        row += 1
        pivot_columns.push(column)
    }

    var free_variable_combinations = 1
    var free_variable_bounds = free_columns.map(|column|
        # Buttons can't possibly be pushed more times than the counter they
        # affect with the lowest required joltage.
        var bound = buttons[column].fold(-1, (|minimum, index|
            var joltage = required_joltages[index]

            if joltage < minimum || minimum == -1: {
                return joltage
            }

            minimum
        )) + 1

        free_variable_combinations *= bound
        bound
    )

    var free_column_count = free_columns.size()
    var free_variables = List.repeat(free_column_count, 0)

    var minimum_presses = -1

    for _ in 1...free_variable_combinations: {
        var solution = List.repeat(width, 0)

        for i, column in free_columns: {
            solution[column] = free_variables[i]
        }

        var valid = true

        for i in pivot_columns.size() - 1...0 by -1: {
            var column = pivot_columns[i]
            var joltage = rows[i][width]

            for j in column + 1...width - 1: {
                joltage -= rows[i][j] * solution[j]
            }

            var value = rows[i][column]

            if joltage % value: {
                valid = false
                break
            }

            joltage /= value

            if joltage < 0: {
                valid = false
                break
            }

            solution[column] = joltage
        }

        for i in 0...free_column_count - 1: {
            free_variables[i] += 1
            if free_variables[i] == free_variable_bounds[i]: {
                free_variables[i] = 0
            else:
                break
            }
        }

        if !valid: {
            continue
        }

        var presses = solution.fold(0, (|sum, value| sum + value))
        if presses < minimum_presses || minimum_presses == -1: {
            minimum_presses = presses
        }
    }

    total_presses_for_joltages += minimum_presses
}

print("Part 1: {}\nPart 2: {}".format(
    total_presses_for_lights, total_presses_for_joltages
))

1 vote

Comment on Day 9: Movie Theater in ~comp.advent_of_code
lily
2 days, 8 hours ago (edited 2 days, 7 hours ago)
Link Parent
The general case of this would be pretty tricky, yeah (and probably pretty slow, at least with a naive approach... my solution isn't the fastest as it is). I can confirm my program returns the...

The general case of this would be pretty tricky, yeah (and probably pretty slow, at least with a naive approach... my solution isn't the fastest as it is). I can confirm my program returns the wrong answer for your test input here. Since these kinds of quirks in the input are generally consistent across all inputs for a given puzzle, though, I don't mind taking advantage of them where possible.

1 vote

Comment on Day 9: Movie Theater in ~comp.advent_of_code

lily

2 days, 15 hours ago

Link

Not especially happy with my solution, but it does the job. Runs in just under a second on my machine. The idea is, if none of the lines between red tiles are overlapping with the rectangle, then...

Not especially happy with my solution, but it does the job. Runs in just under a second on my machine. The idea is, if none of the lines between red tiles are overlapping with the rectangle, then the rectangle is inside the loop. The time complexity of this seems pretty bad, but I unfortunately don't have the time to figure out how to make it more efficient right now.

Solution (Lily)

import (abs) math

var tiles_x: List[Integer] = []
var tiles_y: List[Integer] = []
var tile_count = 0

for line in File.read_to_string("inputs/day_09.txt").split("\n"): {
    var parts = line.split(",")
    tiles_x.push(parts[0].parse_i().unwrap())
    tiles_y.push(parts[1].parse_i().unwrap())
    tile_count += 1
}

var lines = List.fill(tile_count, (|index|
    var next_index = index + 1
    if next_index == tile_count: {
        next_index = 0
    }

    var x1 = tiles_x[index]
    var y1 = tiles_y[index]
    var x2 = tiles_x[next_index]
    var y2 = tiles_y[next_index]

    if x1 == x2: {
        return (y1 <= y2 ? <[x1, x2, y1, y2]> : <[x1, x2, y2, y1]>)
    }

    (x1 < x2 ? <[x1, x2, y1, y2]> : <[x2, x1, y1, y2]>)
))

var max_index = tile_count - 1

var largest_area_all_tiles = 0
var largest_area_red_and_green_tiles = 0

for i in 0...max_index: {
    for j in i + 1...max_index: {
        var x1 = tiles_x[i]
        var y1 = tiles_y[i]
        var x2 = tiles_x[j]
        var y2 = tiles_y[j]

        var area = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)

        if area > largest_area_all_tiles: {
            largest_area_all_tiles = area
        }

        if area <= largest_area_red_and_green_tiles: {
            continue
        }

        if x1 > x2: {
            var temp = x1
            x1 = x2
            x2 = temp
        }

        if y1 > y2: {
            var temp = y1
            y1 = y2
            y2 = temp
        }

        var inside = true
        for line in lines: {
            if line[1] > x1 && line[0] < x2 && line[3] > y1 && line[2] < y2: {
                inside = false
                break
            }
        }

        if inside: {
            largest_area_red_and_green_tiles = area
        }
    }
}

print("Part 1: {}\nPart 2: {}".format(
    largest_area_all_tiles, largest_area_red_and_green_tiles
))

3 votes

Comment on Day 8: Playground in ~comp.advent_of_code

lily

3 days, 14 hours ago (edited 3 days, 14 hours ago)

Link

Really enjoyed this one! Definitely the hardest so far this year. I finished an initial solution in just under an hour, but took some extra time to clean it up and improve performance (switching...

Really enjoyed this one! Definitely the hardest so far this year. I finished an initial solution in just under an hour, but took some extra time to clean it up and improve performance (switching to a minheap rather than pushing to a list and running quicksort afterward sped things up quite a bit). I think it could still stand to be a little more efficient, but it is what it is; the vast majority of the time is spent calculating and inserting the distances into the minheap, and I'm not sure how to optimize that code any further.

I'm glad I thought ahead and wrote a binary heap in advance. Most recent years have had at least one pathfinding puzzle, which is what I intended it for, but it came in handy for today!

Solution (Lily)

import (Heap) "modules/heap"

var boxes = File.read_to_string("inputs/day_08.txt").split("\n").map(|line|
    line.split(",").map(String.parse_i).map(Option.unwrap)
)

var max_index = boxes.size() - 1
var tuples: Heap[Tuple[Integer, Integer, Integer]] = Heap(|a, b| a[2] < b[2])

for i in 0...max_index: {
    for j in i + 1...max_index: {
        var box_1 = boxes[i]
        var box_2 = boxes[j]

        var delta_x = box_2[0] - box_1[0]
        var delta_y = box_2[1] - box_1[1]
        var delta_z = box_2[2] - box_1[2]

        tuples.push(<[i, j, (
            delta_x * delta_x + delta_y * delta_y + delta_z * delta_z
        )]>)
    }
}

var circuits = List.fill(boxes.size(), (|index| [index => unit]))

var circuit_indices: Hash[Integer, Integer] = []
for i in 0...max_index: {
    circuit_indices[i] = i
}

var connections = 0
while tuples.size(): {
    var tuple = tuples.pop()
    var index_1 = circuit_indices[tuple[0]]
    var index_2 = circuit_indices[tuple[1]]

    if index_1 != index_2: {
        var circuit = circuits[index_1]
        circuits[index_2].keys().each(|key|
            circuit[key] = unit
            circuit_indices[key] = index_1
        )

        circuits.delete_at(index_2)
        circuit_indices.each_pair(|key, index|
            if index > index_2: {
                circuit_indices[key] -= 1
            }
        )
    }

    connections += 1
    if connections == 1000: {
        print("Part 1: {}".format(circuits
            .sort(|a, b| b.size() - a.size())
            .slice(0, 3)
            .fold(1, (|product, circuit| product * circuit.size()))
        ))
    }

    if circuits.size() == 1: {
        print("Part 2: {}".format(boxes[tuple[0]][0] * boxes[tuple[1]][0]))
        break
    }
}

Heap implementation

# order_test should return whether the first value should be given higher
# priority than the second value. It determines whether the heap is a min or max
# heap. Operators aren't functions in Lily, and we can't fully qualify generic
# types, so unfortunately the function has to be defined manually even for
# primitive types supporting the < and > operators.
class Heap[A](private var @order_test: Function(A, A => Boolean)) {
    private var @values: List[A] = []

    public define size: Integer {
        return @values.size()
    }

    public define push(value: A): self {
        @values.push(value)

        var current_index = @values.size() - 1
        while current_index > 0: {
            var parent_index = (current_index - 1) / 2

            var current_value = @values[current_index]
            var parent_value = @values[parent_index]

            if @order_test(parent_value, current_value): {
                break
            }

            @values[current_index] = parent_value
            @values[parent_index] = current_value

            current_index = parent_index
        }

        return self
    }

    public define pop: A {
        var size = @values.size()

        if size == 0: {
            raise RuntimeError("Cannot pop from an empty heap.")
        }

        if size == 1: {
            return @values.pop()
        }

        var root_value = @values[0]
        @values[0] = @values.pop()
        size -= 1

        var current_index = 0
        do: {
            var left_index = current_index * 2 + 1
            var right_index = left_index + 1

            var has_left = left_index < size
            var has_right = right_index < size

            if !has_left && !has_right: {
                break
            }

            var child_index = (has_left ? (has_right ? (
                @order_test(@values[left_index], @values[right_index])
                ? left_index
                : right_index
            ) : left_index) : right_index)

            var current_value = @values[current_index]
            var child_value = @values[child_index]

            if @order_test(current_value, child_value): {
                break
            }

            @values[current_index] = child_value
            @values[child_index] = current_value

            current_index = child_index
        } while true

        return root_value
    }
}

1 vote

Comment on Day 7: Laboratories in ~comp.advent_of_code
lily
4 days, 4 hours ago
Link Parent
I didn't think about that case, actually! A splitter on the left edge wouldn't crash my program, since Lily supports Python-style negative indexing on lists, but the answer would be wrong. Another...

I didn't think about that case, actually! A splitter on the left edge wouldn't crash my program, since Lily supports Python-style negative indexing on lists, but the answer would be wrong.

Another convenience of the input I noticed is that the starting location is always in the exact center of the first row. So, I could simplify that line by just dividing the size by 2 instead of manually searching for the first S character.

Comment on Day 7: Laboratories in ~comp.advent_of_code

lily

4 days, 16 hours ago

Link

Surprisingly easy problem - I'd thought we would be getting to the more involved ones by now. I liked the part 2 twist, though. The trick here is one that's been used in prior puzzles, so I...

Surprisingly easy problem - I'd thought we would be getting to the more involved ones by now. I liked the part 2 twist, though. The trick here is one that's been used in prior puzzles, so I figured it out pretty quickly, but I did have to scrap all my original part 1 code.

Solution (Lily)

var lines = File.read_to_string("inputs/day_07.txt").split("\n")

var beam_counts = List.repeat(lines[0].size(), 0)
beam_counts[lines[0].find("S").unwrap()] = 1

var splits = 0

for line in lines: {
    for i, char in line: {
        if char != '^': {
            continue
        }

        var count = beam_counts[i]
        if count > 0: {
            beam_counts[i - 1] += count
            beam_counts[i + 1] += count
            beam_counts[i] = 0

            splits += 1
        }
    }
}

print("Part 1: {}\nPart 2: {}".format(
    splits, beam_counts.fold(0, (|sum, count| sum + count))
))

2 votes

Comment on Day 6: Trash Compactor in ~comp.advent_of_code
lily
4 days, 18 hours ago
Link Parent
I had to copy the input into Notepad++ instead of Sublime Text, since my Sublime config automatically trims trailing whitespace. It pays to have more than one editor around, I suppose. (I think if...

I had to copy the input into Notepad++ instead of Sublime Text, since my Sublime config automatically trims trailing whitespace. It pays to have more than one editor around, I suppose. (I think if you put a cursor at the end of every line Sublime won't do it, though - maybe that's also the case in VS Code?)
Comment on Day 6: Trash Compactor in ~comp.advent_of_code
lily
5 days, 4 hours ago
Link Parent
Possibly that would be cleaner, yeah, though maybe less efficient. I did update my code today to parse from right-to-left rather than left-to-right, which simplified things a little bit.

Possibly that would be cleaner, yeah, though maybe less efficient. I did update my code today to parse from right-to-left rather than left-to-right, which simplified things a little bit.

Comment on Day 6: Trash Compactor in ~comp.advent_of_code

lily

5 days, 15 hours ago (edited 5 days, 5 hours ago)

Link

Well, I figured we'd get to the parsing puzzle eventually. I got stuck for a while after I realized the columns weren't all the same size in the real input. I'm not especially happy with my...

Well, I figured we'd get to the parsing puzzle eventually. I got stuck for a while after I realized the columns weren't all the same size in the real input. I'm not especially happy with my parsing logic, but it appears to do the job, and at this point I think I'm better off not messing with it any further.

I will admit I tend to dislike these kinds of puzzles somewhat, since parsing text formats (especially column-based ones like this) is pretty finicky and not all that enjoyable to me. This one was at least interesting, though - I'll give it that.

Solution (Lily)

define add(sum: Integer, number: Integer): Integer {
    return sum + number
}

define multiply(product: Integer, number: Integer): Integer {
    return product * number
}

var lines = File.read_to_string("inputs/day_06.txt").split("\n")
var number_rows = lines.size() - 1

var numbers_horizontal: List[Integer] = List.repeat(number_rows, 0)
var factors_horizontal: List[Integer] = List.repeat(number_rows, 1)
var numbers_vertical: List[Integer] = []

var total_horizontal = 0
var total_vertical = 0

var skip_column = false
for column in lines[0].size() - 1...0 by -1: {
    if skip_column: {
        skip_column = false
        continue
    }

    var number_vertical = 0
    for i, number_horizontal in numbers_horizontal: {
        var char = lines[i][column]
        if char != ' ': {
            var digit = char - '0'
            numbers_horizontal[i] += digit * factors_horizontal[i]
            factors_horizontal[i] *= 10
            number_vertical = number_vertical * 10 + digit
        }
    }

    numbers_vertical.push(number_vertical)

    var char = lines[number_rows][column]
    if char == '+': {
        total_horizontal += numbers_horizontal.fold(0, add)
        total_vertical += numbers_vertical.fold(0, add)
    elif char == '*':
        total_horizontal += numbers_horizontal.fold(1, multiply)
        total_vertical += numbers_vertical.fold(1, multiply)
    else:
        continue
    }

    for i in 0...number_rows - 1: {
        numbers_horizontal[i] = 0
        factors_horizontal[i] = 1
    }

    numbers_vertical.clear()
    skip_column = true
}

print("Part 1: {}\nPart 2: {}".format(total_horizontal, total_vertical))

2 votes

Comment on Day 5: Cafeteria in ~comp.advent_of_code
lily
6 days, 4 hours ago
Link Parent
I was curious myself whether there was a way to do the merging without sorting the list of ranges first. Your logic looks pretty close to my own, though, so maybe that is the best way to do it...?...

I was curious myself whether there was a way to do the merging without sorting the list of ranges first. Your logic looks pretty close to my own, though, so maybe that is the best way to do it...? Performance seems fine in any case, so it probably doesn't matter much anyway.

2 votes

Comment on Day 5: Cafeteria in ~comp.advent_of_code

lily

6 days, 5 hours ago (edited 6 days, 2 hours ago)

Link

I keep expecting the problems to suddenly get harder, but I guess we haven't reached that point yet. Surprisingly easy day, though part 2 was pretty interesting. I'm not sure what I'm doing here...

I keep expecting the problems to suddenly get harder, but I guess we haven't reached that point yet. Surprisingly easy day, though part 2 was pretty interesting. I'm not sure what I'm doing here is the most efficient way to do it (nor am I entirely convinced it does the job in all cases, though it works fine for my input), but it was the first thing I could think of.

(Updated to use Lily's List methods instead of manual loops. It's almost certainly no more efficient than what I had before, but I thought it might be a better showcase of some of Lily's features.)

Solution (Lily)

var line_groups = File
    .read_to_string("inputs/day_05.txt")
    .split("\n\n")
    .map(|string| string.split("\n"))

var ranges = line_groups[0]
    .map(|line|
        var endpoints = line.split("-")
        <[endpoints[0].parse_i().unwrap(), endpoints[1].parse_i().unwrap()]>
    )
    .sort(|a, b| a[0] - b[0])
    .accumulate([].@(List[Tuple[Integer, Integer]]), (|merged_ranges, range|
        if merged_ranges: {
            var previous = merged_ranges[-1]
            if range[0] <= previous[1]: {
                if range[1] > previous[1]: {
                    previous[1] = range[1]
                }
            else:
                merged_ranges.push(range)
            }
        else:
            merged_ranges.push(range)
        }
    ))

print("Part 1: {}\nPart 2: {}".format(
    line_groups[1].map(|line| line.parse_i().unwrap()).count(|id|
        ranges.any(|range| id >= range[0] && id <= range[1])
    ),
    ranges.fold(0, (|sum, range| sum + range[1] - range[0] + 1))
))

2 votes

Comment on Day 4: Printing Department in ~comp.advent_of_code

lily

December 4

Link

Relatively easy problem (easier than yesterday's, I think), though I took some time today to make my solution more efficient. The naive bruteforce solution only took about half a second to run on...

Relatively easy problem (easier than yesterday's, I think), though I took some time today to make my solution more efficient. The naive bruteforce solution only took about half a second to run on my machine, so it wasn't critical to improve it, but I could tell there was room for improvement and so wanted to give it a try. Probably my solution here is somewhat overengineered (it also has some repetitive code), but it runs more or less instantly, so I'm happy enough with it.

Solution (Lily)

import (Set, integer_pair_hash) "modules/set"

var lines = File.read_to_string("inputs/day_04.txt").split("\n")

var width = lines[0].size()
var height = lines.size()

var adjacent = List.fill(height, (|_| List.repeat(width, -1)))

for y, line in lines: {
    for x, char in line: {
        if char != '@': {
            continue
        }

        var count = 0

        for delta_y in -1...1: {
            var adjacent_y = y + delta_y
            if adjacent_y < 0 || adjacent_y >= height: {
                continue
            }

            for delta_x in -1...1: {
                if delta_y == 0 && delta_x == 0: {
                    continue
                }

                var adjacent_x = x + delta_x
                if adjacent_x < 0 || adjacent_x >= width: {
                    continue
                }

                if lines[adjacent_y][adjacent_x] == '@': {
                    count += 1
                }
            }
        }

        adjacent[y][x] = count
    }
}

var to_remove: Set[Tuple[Integer, Integer]] = Set(integer_pair_hash)
for y, row in adjacent: {
    for x, count in row: {
        if count >= 0 && count < 4: {
            to_remove.add(<[x, y]>)
        }
    }
}

print("Part 1: {}".format(to_remove.size()))

var total_rolls_removed = 0

do: {
    var to_remove_new: Set[Tuple[Integer, Integer]] = Set(integer_pair_hash)

    to_remove.each(|position| adjacent[position[1]][position[0]] = -1)
    to_remove.each(|position|
        var x = position[0]
        var y = position[1]

        for delta_y in -1...1: {
            var adjacent_y = y + delta_y
            if adjacent_y < 0 || adjacent_y >= height: {
                continue
            }

            for delta_x in -1...1: {
                if delta_y == 0 && delta_x == 0: {
                    continue
                }

                var adjacent_x = x + delta_x
                if adjacent_x < 0 || adjacent_x >= width: {
                    continue
                }

                var row = adjacent[adjacent_y]

                if row[adjacent_x] < 0: {
                    continue
                }

                row[adjacent_x] -= 1

                if row[adjacent_x] < 4: {
                    to_remove_new.add(<[adjacent_x, adjacent_y]>)
                }
            }
        }
    )

    total_rolls_removed += to_remove.size()
    to_remove = to_remove_new
} while to_remove.size()

print("Part 2: {}".format(total_rolls_removed))

Set module

class Set[A](private var @hash_function: Function(A => Integer)) {
    private var @hashes: Hash[Integer, Unit] = []
    private var @values: List[A] = []

    public define size: Integer {
        return @hashes.size()
    }

    public define add(value: A) {
        var hash = @hash_function(value)
        if !@hashes.has_key(hash): {
            @hashes[hash] = unit
            @values.push(value)
        }
    }

    public define remove(value: A) {
        @hashes.delete(@hash_function(value))
    }

    public define contains(value: A): Boolean {
        return @hashes.has_key(@hash_function(value))
    }

    public define each(fn: Function(A)) {
        @values.each(fn)
    }
}

define integer_pair_hash(pair: Tuple[Integer, Integer]): Integer {
    var first = pair[0]
    var second = pair[1]

    return (
        first >= second
        ? first * first + first + second
        : first + second * second
    )
}

1 vote

Comment on Day 3: Lobby in ~comp.advent_of_code
lily
December 3 (edited December 3)
Link
Got stuck on this last night (probably was just too tired), so I had to come back to it today. Luckily, it didn't take me too long after that. For part 1 I was originally building each individual...
Got stuck on this last night (probably was just too tired), so I had to come back to it today. Luckily, it didn't take me too long after that. For part 1 I was originally building each individual combination, which ended up being way too slow for part 2, so I scrapped my old code and came up with a new solution, which runs pretty much instantly on my machine.
Explanation

I eventually realized that caring about combinations at all was the wrong approach. As an example, let's say we're trying to find the maximum joltage with three batteries from the bank 482651:

First, find the largest battery excluding the last two, since we need two more batteries after this one. The largest battery out of 4826 is 8.

Next, find the largest battery that comes after our first one, but before the last in the bank, since we need one more battery after this one. The largest battery out of 2651 is 6.

Finally, find the largest battery that comes after our second one. The largest battery out of 51 is 5.

So, the maximum joltage is 865. I'm not sure what the time complexity of this is, but it seems pretty efficient.

Probably others arrived at something like this too, though I haven't looked at many other solutions yet.
Solution (Lily)

define find_maximum_joltage( line: String, size: Integer, batteries: Integer ): Integer { var index = 0 var joltage = 0 do: { var largest = 0 for i in index...size - batteries: { var battery = line[i] - '0' if battery > largest: { largest = battery index = i } } index += 1 joltage = joltage * 10 + largest batteries -= 1 } while batteries > 0 return joltage } var output_joltage_two_batteries = 0 var output_joltage_twelve_batteries = 0 for line in File.read_to_string("inputs/day_03.txt").split("\n"): { var size = line.size() output_joltage_two_batteries += find_maximum_joltage(line, size, 2) output_joltage_twelve_batteries += find_maximum_joltage(line, size, 12) } print("Part 1: {}\nPart 2: {}".format( output_joltage_two_batteries, output_joltage_twelve_batteries ))
3 votes

Comment on Day 2: Gift Shop in ~comp.advent_of_code

lily

December 2

Link

To be honest, I didn't really know what I was doing with this one. Still don't have a clue how to do it in a "smart" way. I just bruteforced it, and it takes a couple seconds to run, which I'm not...

To be honest, I didn't really know what I was doing with this one. Still don't have a clue how to do it in a "smart" way. I just bruteforced it, and it takes a couple seconds to run, which I'm not super happy with, but I'll take the win for tonight. Maybe I'll come back to it in the morning and see if I can figure out a nicer solution. I'm doing a lot of string copying right now, which I think is the main source of overhead.

Solution (Lily)

var invalid_sum_half_width = 0
var invalid_sum_any_width = 0

for range in File.read_to_string("inputs/day_02.txt").split(",").map(|string|
    string.split("-").map(String.parse_i).map(Option.unwrap)
): {
    for id in range[0]...range[1]: {
        var string = id.to_s()
        var size = string.size()
        var half_width = size / 2

        if string.slice(0, half_width) == string.slice(half_width): {
            invalid_sum_half_width += id
            invalid_sum_any_width += id
            continue
        }

        for width in 1...size: {
            if size % width: {
                continue
            }

            var left = 0
            var right = width
            var previous = string.slice(left, right)
            var invalid = true

            do: {
                left += width
                right += width

                var current = string.slice(left, right)

                if current != previous: {
                    invalid = false
                    break
                }

                previous = current
            } while right < size

            if invalid: {
                invalid_sum_any_width += id
                break
            }
        }
    }
}

print("Part 1: {}\nPart 2: {}".format(
    invalid_sum_half_width, invalid_sum_any_width
))

4 votes

Comment on Day 1: Secret Entrance in ~comp.advent_of_code
lily
December 1
Link Parent
Just a coincidence! I found the language earlier this year when looking through a list on GitHub of embeddable scripting languages, and thought it looked interesting. I have contributed some...

Just a coincidence! I found the language earlier this year when looking through a list on GitHub of embeddable scripting languages, and thought it looked interesting. I have contributed some functionality to the standard library (mainly a sort method for lists and a small UTF-8 module), but I'm not the developer of the language itself.

4 votes
Comment on Day 1: Secret Entrance in ~comp.advent_of_code
lily
December 1 (edited December 2)
Link
Doing this year in a little-known scripting language I've been writing a game with in my spare time (https://lily-lang.org). It's an embeddable scripting language like Lua, but with static typing...
Doing this year in a little-known scripting language I've been writing a game with in my spare time (https://lily-lang.org). It's an embeddable scripting language like Lua, but with static typing - an interesting niche I haven't really seen covered elsewhere.

I agree with others that this was harder than the typical Day 1 puzzle, but it still wasn't too bad. I took some time after initially solving it to try to figure out a cleaner solution, but eventually just gave up and committed my original code. The input was small enough it didn't really matter.
Solution (Lily)

var dial = 50 var times_zero_was_reached = 0 var times_zero_was_reached_or_passed = 0 for line in File.read_to_string("inputs/day_01.txt").split("\n"): { var amount = line.slice(1).parse_i().unwrap() if line[0] == 'R': { dial += amount while dial >= 100: { dial -= 100 times_zero_was_reached_or_passed += 1 } else: if dial == 0: { dial = 100 - amount else: dial -= amount } while dial < 0: { dial += 100 times_zero_was_reached_or_passed += 1 } if dial == 0: { times_zero_was_reached_or_passed += 1 } } if dial == 0: { times_zero_was_reached += 1 } } print("Part 1: {}\nPart 2: {}".format( times_zero_was_reached, times_zero_was_reached_or_passed ))
4 votes
Comment on How many valid JSON strings are there? in ~comp
lily
September 27
Link Parent
I think this might have changed at some point. From what I remember when I wrote my own JSON parser a few months ago, the latest JSON specification doesn't restrict the type of top-level values;...

I think this might have changed at some point. From what I remember when I wrote my own JSON parser a few months ago, the latest JSON specification doesn't restrict the type of top-level values; it only mandates that there be only one. But I know some older JSON parsers only allow objects and arrays to be top-level. It's possible older versions of the spec had such a restriction, but it was removed? (To be fair, there's really not much of a point to a JSON document containing only a single string or number...)

Honestly, the JSON specification has always been a little wishy-washy. The fact that JSON parsers are allowed to parse anything they want, as long as valid JSON documents still work correctly, feels a little weird to me. It means there are a lot of slightly different, incompatible versions of JSON out there.

3 votes
Comment on What programming/technical projects have you been working on? in ~comp
lily
September 24
Link Parent
If you want more information, https://github.com/Jai-Community/Jai-Community-Library/wiki is the most comprehensive public documentation I know of. The beta distribution comes with quite extensive...

If you want more information, https://github.com/Jai-Community/Jai-Community-Library/wiki is the most comprehensive public documentation I know of. The beta distribution comes with quite extensive documentation of its own, but it's not available anywhere online to my knowledge.

The annotations are nice, though I wouldn't mind them being typed in some way - as of now they're just raw strings you have to handle yourself. They're certainly not the most unique part of the language, though. I'm pretty sure other languages have similar features.

2 votes
Comment on What programming/technical projects have you been working on? in ~comp
lily
September 24 (edited September 24)
Link Parent
It's an interesting systems programming language that's still in closed beta (though I don't think it's all that hard to get in these days). C-like, with a few safety improvements (eg. bounds...
It's an interesting systems programming language that's still in closed beta (though I don't think it's all that hard to get in these days). C-like, with a few safety improvements (eg. bounds checks, array views, defer), though nowhere near what Rust does in that respect. Its "big idea" is incredibly powerful metaprogramming - almost anything you can think of can be done at compile time (similar to Zig's comptime), including generating new code, and extensive type info can be retrieved at both compile time and runtime.

What this means for my parser is that I can define all my data types as regular structs, with annotations to indicate specific attributes (in this case, the chunk indices in the binary format, and whether the fields should still be serialized even at their default values; I have some other annotations, too, though they're not in this example), which looks something like:
```
Troop :: struct {
    name           : string;                     @1
    members        : Sparse_Array(Troop_Member); @2 @persist
    auto_alignment : bool;                       @3
    terrain_set    : [..] u8;                    @5 @persist
    appear_randomly: bool;                       @6
    pages          : Sparse_Array(Troop_Page);   @11 @persist
}
```
Then, I automatically generate parsing and serialization code for those structs at compile time. The result is a dramatically smaller amount of code, and (in my opinion, at least) a much more workable and understandable codebase.
4 votes

lily's recent activity

Comment on Day 11: Reactor in ~comp.advent_of_code

Comment on Day 10: Factory in ~comp.advent_of_code

Comment on Day 9: Movie Theater in ~comp.advent_of_code

Comment on Day 9: Movie Theater in ~comp.advent_of_code

Comment on Day 8: Playground in ~comp.advent_of_code

Comment on Day 7: Laboratories in ~comp.advent_of_code

Comment on Day 7: Laboratories in ~comp.advent_of_code

Comment on Day 6: Trash Compactor in ~comp.advent_of_code

Comment on Day 6: Trash Compactor in ~comp.advent_of_code

Comment on Day 6: Trash Compactor in ~comp.advent_of_code

Comment on Day 5: Cafeteria in ~comp.advent_of_code

Comment on Day 5: Cafeteria in ~comp.advent_of_code

Comment on Day 4: Printing Department in ~comp.advent_of_code

Comment on Day 3: Lobby in ~comp.advent_of_code

Comment on Day 2: Gift Shop in ~comp.advent_of_code

Comment on Day 1: Secret Entrance in ~comp.advent_of_code

Comment on Day 1: Secret Entrance in ~comp.advent_of_code

Comment on How many valid JSON strings are there? in ~comp

Comment on What programming/technical projects have you been working on? in ~comp

Comment on What programming/technical projects have you been working on? in ~comp