advent of code 2023

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > advent of code 2023

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

It turns out that the ancestors of the input value you provide are just a linear chain, with no situations where multiple nodes depend on a single node. Which I think means that the output value is a linear function of the input, making it very easy to solve numerically. But it's also tractable to solve analytically, since you can just walk down the tree saying "this tree node must evaluate to this constant value".

# ? Dec 21, 2022 11:47

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 00:56

The Chairman: Jun 30, 2003; But you forget, mon ami, that there is evil everywhere under the sun

I did part 2 like 50% by hand, I wrote a function to find the difference between the two sides of the tree, plugged in test values to get an idea of the shape of the function and narrowed down the interval where the difference flipped from positive to negative, and then did a naive search in that area

# ? Dec 21, 2022 14:51

Cybernetic Vermin: Apr 18, 2005

first go i did some regexing by hand, but fixing this up this is then my second laziest take

code:

from z3 import *
import re

inp=open("in").readlines()
inp=[re.sub('root: (\w+) \+ (\w+)',r'\1 == \2',l) for l in inp if l[0:4]!='humn']
stmts=[re.sub('([a-z]+)',r'Real("\1")',l).replace(":"," ==") for l in inp]

s=Solver()
for stmt in stmts:
    s.add(eval(stmt))
s.check()
print(f'{s.model()}')

# ? Dec 21, 2022 15:54

the talent deficit: Dec 20, 2003; self-deprecation is a very british trait, and problems can arise when the british attempt to do so with a foreign culture

i just did binary search with the root comparison changed to a subtraction operation for p2

# ? Dec 21, 2022 20:29

Cybernetic Vermin: Apr 18, 2005

the talent deficit posted:

i just did binary search with the root comparison changed to a subtraction operation for p2

despite my crude everything-is-a-nail solution i still avoid doing this kind of thing, i.e. using that the equation is linear, which is not part of the problem statement, but happens to be the case in the input.

but that's a weird hangup on my part, very much in aoc spirit to observe properties of the input.

# ? Dec 21, 2022 20:49

The Chairman: Jun 30, 2003; But you forget, mon ami, that there is evil everywhere under the sun

Cybernetic Vermin posted:

despite my crude everything-is-a-nail solution i still avoid doing this kind of thing, i.e. using that the equation is linear, which is not part of the problem statement, but happens to be the case in the input.

but that's a weird hangup on my part, very much in aoc spirit to observe properties of the input.

I don't feel especially bad about it, especially this year where there's already been a bunch of pathfinding/tree-crawling problems I've had to flail through or give up on; if I can find an easier-for-me if less clever way of solving it that doesn't involve traversing recursive data structures, I'll take it

# ? Dec 21, 2022 21:07

Cybernetic Vermin: Apr 18, 2005

The Chairman posted:

I don't feel especially bad about it, especially this year where there's already been a bunch of pathfinding/tree-crawling problems I've had to flail through or give up on; if I can find an easier-for-me if less clever way of solving it that doesn't involve traversing recursive data structures, I'll take it

yeah, absolutely do not mean anything bad about it, i've written so much garbage this and past years that i have no legs to stand on whining about generality.

let me instead turn this into what i originally had in mind: man smt solvers are great, so much power from an often very friendly library. don't miss out on poking at z3 at some point. great thing to have in the toolbox.

# ? Dec 21, 2022 21:11

MrQueasy: Nov 15, 2005; Probiot-ICK

I just built an AST and then played it back and forth it until only humn was on the left.

code:

 private tailrec fun unwrap(tree: MutableMap<String, MonkeyTree>, rootLabel: String): String {
        val root = tree[rootLabel] as MonkeyTree.Node
        when (val leftNode = tree[root.left]) {
            null -> return rootLabel
            is MonkeyTree.Node -> {
                when (tree[leftNode.right]) {
                    is MonkeyTree.Leaf -> {
                        tree[rootLabel] = root.copy(left = leftNode.left, right = root.left)
                        tree[root.left] = rearrangeOp(root.right, leftNode)  // converts a/C=b into  a= bC  (or a-C=b into a=b+C)
                    }
                    else -> {
                        tree[rootLabel] = root.copy(left = leftNode.right, right = root.left)
                        tree[root.left] = rearrangeOpR(root.right, leftNode) // converts C/a=b into a=C/b (or C-a=b into a=C-b)
                    }
                }
            }
            is MonkeyTree.Leaf -> tree[rootLabel] = root.copy(left = root.right, right = root.left)
        }
        return unwrap(tree, rootLabel)
    }

# ? Dec 21, 2022 22:02

the talent deficit: Dec 20, 2003; self-deprecation is a very british trait, and problems can arise when the british attempt to do so with a foreign culture

my favorite aoc puzzles are the dfs/bfs/astar/djikstra puzzles. the solve a system of linear equations are probably my least favorite (apart from the '90% of the problem is parsing the input' days which i mostly skip)

# ? Dec 22, 2022 04:11

MrQueasy: Nov 15, 2005; Probiot-ICK

the talent deficit posted:

my favorite aoc puzzles are the dfs/bfs/astar/djikstra puzzles. the solve a system of linear equations are probably my least favorite (apart from the '90% of the problem is parsing the input' days which i mostly skip)

I'm fairly certain day 21 was designed as a (Stacks + RPN + Tree) manipulation problem, not something that should be binsearched or stuffed into an equation solver.

The fact that you get non-unique answers when you use floor division is the best evidence for this

# ? Dec 22, 2022 05:15

MrQueasy: Nov 15, 2005; Probiot-ICK

Did you cut out an example cube to help you visualize?

# ? Dec 22, 2022 08:54

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

I didn't, but I definitely hard-coded the specific shape of my input instead of writing something to work for an arbitrary net.

# ? Dec 22, 2022 11:49

Lime: Jul 20, 2004

had fun spending way too long figuring out how to fold any input into a cube and not hardcode anything

ultimately, each face stores the basis of its local coordinate system. start by picking an arbitrary face then recursively walk to whatever faces are already known to be adjacent from the input. because each edge has to fold 90 degrees, it's easy to keep rotating the basis as you walk, depending on which side you left through. then to actually "fold" the cube, for each face's missing neighbors, look at what the normal of the neighbor would have to be and then find the face that has that normal.

when actually moving along the path in the problem, whenever i cross an edge, i just do some matching between the old basis and the new to figure out the new local coordinates from the old. i think this part would have been cleaner if i would have been explicit about the origin of each face and then just written a 4x4 matrix transform for the change in coordinates, but it wasn't too bad.

# ? Dec 22, 2022 13:46

Cybernetic Vermin: Apr 18, 2005

extremely invested in this year *not* figuring out the cube motions, will make *some* other functionality do the work for me. but wound up being a day of holiday cleaning and gift wrapping, so i think i'm putting it off until tomorrow.

i am generally really pleased with aoc this year. one can always debate whether it would be nicer if it was friendlier/less effort so you don't have to be a weirdo to stick all the way through, but there's usually a couple of days i really hate by this point past years. i guess one criticism i'd give is that relatively few of the recent days have been of the sort that's delightful in motion.

Cybernetic Vermin fucked around with this message at 17:32 on Dec 22, 2022

# ? Dec 22, 2022 17:29

fack you: Sep 12, 2002; For Life

I had the hubris to think I could learn assembly by doing advent of code this year...in Z80 assembly. Day 1, Part 1 is complete, although just browsing this thread and looking at the rest of the problems - I don't have much hope I'll complete more than a few days: https://github.com/coat/advent2022

# ? Dec 22, 2022 21:54

Lime: Jul 20, 2004

thought today's would look cooler in motion being a cellular automaton but it mostly looks like noise. the sparks at the edges are neat though

# ? Dec 23, 2022 20:49

gonadic io: Feb 16, 2011; >>=

today definitely felt like a freebie at this point

# ? Dec 24, 2022 03:40

MrQueasy: Nov 15, 2005; Probiot-ICK

the Game of Life puzzle is always my favorite. It seemed a little late this year.

# ? Dec 24, 2022 04:16

MrQueasy: Nov 15, 2005; Probiot-ICK

Phew. Day 24 was ANOTHER bfs.

But there were several "tricks" to reduce your overhead this time I think.

The ones I used for tree trimming:

The blizzards are at fixed positions at a given time modulo the column or row width.

You should never re-enter a square at the same modulo pair with a longer distance. (My reasoning: if it's the same modulo pair, all paths to the solution could have gotten there wiithout looping.

# ? Dec 24, 2022 08:52

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

Since you don't need to know the actual path, you can solve it the same way you'd evaluate an NFA on a string - compute the full set of positions you can possibly reach at t=1, use that to compute the full set at t=2, etc.

The only "trimming" needed is deduping positions that get reached in multiple ways.

# ? Dec 24, 2022 09:24

Cybernetic Vermin: Apr 18, 2005

the talent deficit posted:

my favorite aoc puzzles are the dfs/bfs/astar/djikstra puzzles. the solve a system of linear equations are probably my least favorite (apart from the '90% of the problem is parsing the input' days which i mostly skip)

well, has for the most part been your year

Jabor posted:

Since you don't need to know the actual path, you can solve it the same way you'd evaluate an NFA on a string - compute the full set of positions you can possibly reach at t=1, use that to compute the full set at t=2, etc.

The only "trimming" needed is deduping positions that get reached in multiple ways.

i too have been pretty lucky this year in that this is kind of my search default anyway, and has worked for all but the robot building one, where i cut the search space in very unprincipled ways.

today i predicted that there'd be more to it during part 1, so went through and did more pruning during part 1, but turns out part 2 does not really need it (though there's a bit of patience needed with the crude way i hacked it up).

Cybernetic Vermin fucked around with this message at 10:32 on Dec 24, 2022

# ? Dec 24, 2022 10:28

Athas: Aug 6, 2007; fuck that joker

Today's was absolutely delightful. I particularly enjoyed that the wind state for iteration i can be computed as a closed form of the initial state, and that the problem can be seen as a shortest-path through a cylinder, where the depth represents time. Probably my favourite pathfinding puzzle this year.

# ? Dec 24, 2022 12:23

gonadic io: Feb 16, 2011; >>=

Athas posted:

Today's was absolutely delightful. I particularly enjoyed that the wind state for iteration i can be computed as a closed form of the initial state, and that the problem can be seen as a shortest-path through a cylinder, where the depth represents time. Probably my favourite pathfinding puzzle this year.

yeah same tbh. note too that instead of having your loop time being lcm(w,h), or worse w*h, you can have two different lookup tables, one of which loops in w steps and checks only horizontal blizzards, and one of which loops in h steps and checks only vertical blizzards

# ? Dec 25, 2022 02:01

cool av: Mar 2, 2013

gonadic io posted:

yeah same tbh. note too that instead of having your loop time being lcm(w,h), or worse w*h, you can have two different lookup tables, one of which loops in w steps and checks only horizontal blizzards, and one of which loops in h steps and checks only vertical blizzards

cool, didn't think of that.

what approach would the lcm runtime come from? only thing I could think of is caching lcm(w,h) states each of which with w*h data but that seems quite different than what you're describing

# ? Dec 25, 2022 08:03

gonadic io: Feb 16, 2011; >>=

cool av posted:

cool, didn't think of that.

what approach would the lcm runtime come from? only thing I could think of is caching lcm(w,h) states each of which with w*h data but that seems quite different than what you're describing

if you keep with just one lookup table that does both vertical and horizontal blizzards, it repeats after LCM(w,h) time steps, not (just) w*h.

gonadic io fucked around with this message at 10:40 on Dec 25, 2022

# ? Dec 25, 2022 10:32

Athas: Aug 6, 2007; fuck that joker

https://futhark-lang.org/blog/2022-12-25-reflections-on-advent-of-code.html

# ? Dec 25, 2022 12:25

Cybernetic Vermin: Apr 18, 2005

final one was pretty neat, i did encode it in a dumb way recursively in order of significance setting digits to the one that minimizes the distance to the intended number, which works, but after having had my coffee i realize that nothing prevents you from computing the final number of digits, then computing the base-5 representation in the usual modulo-and-shift way, only on the number x+22...2

good problems this year, only ones i didn't like too much was 19 where i still don't know how it can be done really fast without making assumptions that could be unsound in general, and 22 where i just refused to go through with tedious hand-coding, but eventually arrived with a 2d stitching approach that was only a little better.

Cybernetic Vermin fucked around with this message at 14:05 on Dec 25, 2022

# ? Dec 25, 2022 14:02

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

You can also work it out in the regular modulo-and-divide way, but adding 1 to the number after dividing when the digit you just emitted was actually 5 below what it would have been in a normal place-value system.

# ? Dec 25, 2022 14:20

cool av: Mar 2, 2013

Cybernetic Vermin posted:

final one was pretty neat, i did encode it in a dumb way recursively in order of significance setting digits to the one that minimizes the distance to the intended number, which works, but after having had my coffee i realize that nothing prevents you from computing the final number of digits, then computing the base-5 representation in the usual modulo-and-shift way, only on the number x+22...2

good problems this year, only ones i didn't like too much was 19 where i still don't know how it can be done really fast without making assumptions that could be unsound in general, and 22 where i just refused to go through with tedious hand-coding, but eventually arrived with a 2d stitching approach that was only a little better.

agreed on 19 that one single handedly took out 3 days for me and I was playing catch-up for the rest

Jabor posted:

You can also work it out in the regular modulo-and-divide way, but adding 1 to the number after dividing when the digit you just emitted was actually 5 below what it would have been in a normal place-value system.

yeah I had a delightful moment realizing the way forward was basically implementing base-5 ToString with an adder carry-bit algorithm when you see a 3 or 4 digit

# ? Dec 25, 2022 17:55

cool av: Mar 2, 2013

also lol at the day 25 part 2 best times being 30 seconds slower than part 1

# ? Dec 25, 2022 17:57

The Chairman: Jun 30, 2003; But you forget, mon ami, that there is evil everywhere under the sun

I did a little writeup about how AOC went for me too: https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/2022/commentary.md

# ? Dec 26, 2022 02:36

echinopsis: Apr 13, 2004; by Fluffdaddy

DrPossum posted:

more like advent of chode

# ? Dec 29, 2022 02:54

echinopsis: Apr 13, 2004; by Fluffdaddy

DrPossum posted:

more like advent of chode

# ? Jan 8, 2023 02:35

FalseNegative: Jul 24, 2007; 2>/dev/null

Got my 50 stars! I had to look up tips and this thread was also a big help for some of the domains I didn't have much experience in (DFS pruning, modulo arithmetic). I also did it in rust this year so it gave me a chance to learn a bit more about structuring structs based on the borrowing rules involved. Overall I really liked this year.

If anyone's got recommendations for good algorithm / dynamic programming books though I'm all ears. I've got no formal education in those and wouldn't mind going deeper.

# ? Jan 8, 2023 03:09

MrQueasy: Nov 15, 2005; Probiot-ICK

I still have the factory day left. It gets the right answer for the examples in part 1, but not for my input. Haven't had the time to really sit down and learn why.

# ? Jan 8, 2023 03:23

Cybernetic Vermin: Apr 18, 2005

it is the kind of problem where in the real world you probably *should* use a solver, for robustness if nothing else. likely also the best bet for getting leaderboard in aoc if one cares about such things (one should not). i went for a dumber solution at the time, but the z3 solution is reasonably straightforward (input premassaged a bit):

Python code:

from z3 import *
import math

results=[]
for r in [eval(l) for l in open("in").readlines()]:
    s=Optimize()
    # res_i_j is the amount of the jth resource we have minute i
    res=[Int(f'res_0_{i}') for i in range(4)]
    # rob_i_j is the number of robots of type j we have minute i
    rob=[Int(f'rob_0_{i}') for i in range(4)]
    for i in range(4):
        s.add(res[i]==0)
        s.add(rob[i]==int(i==0))
    for i in range(1,33):
        nres=[Int(f'res_{i}_{j}') for j in range(4)]
        nrob=[Int(f'rob_{i}_{j}') for j in range(4)]
        exp=True
        for j in range(4):
            # The option to not build a robot, copy rob values, update res values
            exp=And(exp,nres[j]==res[j]+rob[j],nrob[j]==rob[j])
        for bpix,bp in enumerate(r):  # Option to use a blueprint
            sexp=True
            for j in range(4):
                # Check enough resources,
                sexp=And(sexp,res[j]-bp[j]>=0) # Enough resources?
                # New resources: old, plus robot production, minus blueprint cost
                sexp=And(sexp,nres[j]==res[j]+rob[j]-bp[j])
                if bpix==j:  # The robot built increments
                    sexp=And(sexp,nrob[j]==rob[j]+1)
                else:  # All other robot counts stay the same
                    sexp=And(sexp,nrob[j]==rob[j])
            exp=Or(exp,sexp)  # Or this option into main expression
        s.add(exp)
        res=nres
        rob=nrob
    # Maximize res_32_3
    h=s.maximize(res[3])
    assert s.check()
    results.append(s.model()[res[3]].as_long())

print(f'{math.prod(results[:3])}')

at any rate it is the sort of thing that's well worth learning, lot of toolbox utility for fairly limited effort. and for a lot of brute-force search problems it will likely be faster than what one invents.

# ? Jan 9, 2023 13:01

cool av: Mar 2, 2013

MrQueasy posted:

I still have the factory day left. It gets the right answer for the examples in part 1, but not for my input. Haven't had the time to really sit down and learn why.

when i had that problem it was my code allowing buying 2 different bots in one turn

# ? Jan 9, 2023 15:35

MrQueasy: Nov 15, 2005; Probiot-ICK

cool av posted:

when i had that problem it was my code allowing buying 2 different bots in one turn

It was because I used a min instead of a max for limiting the number of ore robots to make! :argh:

Just plain ol' graph traversal for me, thank you.

Kotlin code:

    enum class Resource { Ore, Clay, Obsidian, Geode }

    private val blueprintRegex =
        (
            """Blueprint (\d+): Each ore robot costs (\d+) ore. """ +
                """Each clay robot costs (\d+) ore. """ +
                """Each obsidian robot costs (\d+) ore and (\d+) clay. """ +
                """Each geode robot costs (\d+) ore and (\d+) obsidian."""
            ).toRegex()

    data class Supply<T : Comparable<T>>(val ore: T, val clay: T, val obsidian: T, val geode: T) :
        Comparable<Supply<T>> {

        operator fun get(type: Resource) =
            when (type) {
                Ore -> ore
                Clay -> clay
                Obsidian -> obsidian
                Geode -> geode
            }

        override fun compareTo(other: Supply<T>): Int {
            if (geode == other.geode) {
                if (obsidian == other.obsidian) {
                    if (clay == other.clay) {
                        return ore.compareTo(other.ore)
                    }
                    return clay.compareTo(other.clay)
                }
                return obsidian.compareTo(other.obsidian)
            }
            return geode.compareTo(other.geode)
        }
    }

    operator fun Supply<Int>.minus(b: Supply<Int>) =
        copy(
            ore = ore - b.ore,
            clay = clay - b.clay,
            obsidian = obsidian - b.obsidian,
            geode = geode - b.geode
        )

    operator fun Supply<Int>.plus(b: Supply<Int>) =
        copy(
            ore = ore + b.ore,
            clay = clay + b.clay,
            obsidian = obsidian + b.obsidian,
            geode = geode + b.geode
        )

    fun Supply<Int>.increment(type: Resource, n: Int = 1) =
        when (type) {
            Ore -> copy(ore = ore + n)
            Clay -> copy(clay = clay + n)
            Obsidian -> copy(obsidian = obsidian + n)
            Geode -> copy(geode = geode + n)
        }

    data class Factory(
        val id: Int,
        val minutes: Int = 0,
        val supply: Supply<Int> = intSupply(),
        val robots: Supply<Int> = intSupply(ore = 1),
        val costs: Supply<Supply<Int>>,
        val maxRobots: Supply<Int>
    ) : Comparable<Factory> {

        override fun compareTo(other: Factory): Int {
            if (minutes == other.minutes) {
                if (supply == other.supply) {
                    return -robots.compareTo(other.robots)
                }
                return -supply.compareTo(other.supply)
            }
            return minutes.compareTo(other.minutes)
        }

        fun canAfford(type: Resource) = Resource.values().all { supply[it] >= costs[type][it] }
        fun canEventuallyProduce(type: Resource) = Resource.values().all { costs[type][it] == 0 || robots[it] > 0 }

        fun build(type: Resource): Factory = copy(robots = robots.increment(type), supply = supply - costs[type])

        fun advanceTime() = copy(minutes = minutes + 1)

        fun produce() = copy(supply = supply + robots)

        val seenKey = "$robots"
        val seenValue = minutes
    }

    private fun Factory.findBestGeodeState(minutes: Int) =
        try {
            pqSearch(PriorityQueue(listOf(this)), minutes)
        } catch (e: CannotProduceGeodesException) {
            this
        }

    private fun haveSeenBetter(current: Factory, seen: MutableMap<String, Int>): Boolean =
        (seen[current.seenKey] ?: Int.MAX_VALUE) < current.seenValue

    private fun String.toFactory(): Factory {
        return blueprintRegex.matchEntire(this)!!.groupValues.drop(1).map { it.toInt() }.let { m ->

            Factory(
                id = m[0],
                costs = Supply(
                    ore = intSupply(ore = m[1]),
                    clay = intSupply(ore = m[2]),
                    obsidian = intSupply(ore = m[3], clay = m[4]),
                    geode = intSupply(ore = m[5], obsidian = m[6])
                ),
                maxRobots = intSupply(
                    ore = listOf(m[2], m[3], m[5]).max(),
                    clay = m[4],
                    obsidian = m[6],
                    geode = Int.MAX_VALUE
                )
            )
        }
    }

    fun intSupply(ore: Int = 0, clay: Int = 0, obsidian: Int = 0, geode: Int = 0) = Supply(ore, clay, obsidian, geode)

    private tailrec fun pqSearch(
        pq: PriorityQueue<Factory>,
        minutes: Int,
        seen: MutableMap<String, Int> = mutableMapOf()
    ): Factory {
        if (pq.isEmpty()) {
            throw CannotProduceGeodesException()
        }

        val current = pq.remove()

        if (current.minutes == minutes) {
            return current
        }

        if (haveSeenBetter(current, seen)) {
            return pqSearch(pq, minutes, seen)
        }
        seen[current.seenKey] = current.seenValue

        pq.addAll(
            Resource.values()
                .filter { current.canEventuallyProduce(it) }
                .mapNotNull { current.buildNextRobotOfType(it) }
                .filter { it.minutes <= minutes }
                .filterNot { haveSeenBetter(it, seen) }
                .ifEmpty {
                    listOf(current.produce().advanceTime())
                }
        )

        return pqSearch(pq, minutes, seen)
    }

    class CannotProduceGeodesException : Throwable()

    private fun Factory.buildNextRobotOfType(type: Resource): Factory? {
        if (robots[type] >= maxRobots[type]) {
            return null
        }
        var factory = copy()
        while (!factory.canAfford(type)) {
            factory = factory.produce().advanceTime()
        }
        return factory.produce().build(type).advanceTime()
    }

    fun part1(input: Sequence<String>): Int {
        return input
            .map { it.toFactory() }
            .map { it.findBestGeodeState(24) }
            .sumOf { it.id * it.supply.geode }
    }

    fun part2(input: Sequence<String>): Int {
        return input.take(3)
            .map { it.toFactory() }
            .map { it.findBestGeodeState(32) }
            .map { it.supply.geode }
            .reduce(Int::times)
    }

Advent of Code 2022 is now done and dusted for me. (anonymous user #2347253)

# ? Jan 9, 2023 19:58

echinopsis: Apr 13, 2004; by Fluffdaddy

DrPossum posted:

more like advent of chode

# ? Jan 16, 2023 08:38

Adbot: ADBOT LOVES YOU

# ? Jun 7, 2024 00:56

FalseNegative: Jul 24, 2007; 2>/dev/null

Day 19 was a hoot, along with 16. Thanks for the tip to look at solvers. My solution DFS with pruning got the following times:

Part 1 7.40ms
Part 2 439.31ms

So I was pretty pleased with that. It's by far the slowest solution, the next-worst was Day 23 at ~214ms. The entire year runs in 1.7s or so.

# ? Jan 16, 2023 14:29

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > advent of code 2023

«‹›15 »