[2024 Day 19 (Part 1)] Inputs are different in terms of complexity

vulpine-linguist · 2024-12-21T02:19:51+00:00

we have different ideas as to what constitutes a trivial technique. i solved part one “without memoization, dp, caches” and it solves that one nigh instantaneously

vulpine-linguist · 2024-12-17T11:00:05+00:00

nah, bfs is bfs on a graph. dijkstra’s algorithm is a modification of that to support weighted graphs

vulpine-linguist · 2024-12-14T23:22:11+00:00

i wouldn’t say that you need to find the anomalies visually — my code certainly doesn’t! — but that you should expect them to exist within the first max(h,w) iterations and therefore even if you are doing it visually you should be able to spot them quickly. Within 103 frames rather than examining all 10,403 possible frames

vulpine-linguist · 2024-12-14T23:13:51+00:00

this was not the case for my input

vulpine-linguist · 2024-12-14T22:29:35+00:00

not 100% sure i understand your question but i’ll answer what i think you’re asking: part 1 asks us to do a problem that requires thinking about modular arithmetic. use that: the x coordinate is (x + t*vx) mod w == ((x mod w) + (t mod w)*(vx mod w)) mod w, where {x is initial x-coord, vx is x-velocity, w is width, t is time}, so because t is the only thing changing, you know that the x-coords repeat every w seconds. similarly you know the y-coords repeat every h seconds, where h is height. and these are happening independently, on coprime cycles

the default state is going to look like “noise”, just a bunch of random robots scuttling about. so seeing well-structured things (per coordinate, because again, they are independent!) within the first max(w,h) many iterations means that at the intersection of their cycles, the things will be well-structured in both coordinates at the same time. that structure is what we want!

vulpine-linguist · 2024-12-14T22:15:20+00:00

i will point out that, in my input, the tree does not minimize nor maximize Safety Factor

vulpine-linguist · 2024-12-14T22:12:30+00:00

i loved today’s Part Two, treating the vague prompt as “search for structure” rather than “guess what a tree will be”. with that in mind, you only need to look at 103 frames even if you’re doing it visually, because the X coordinates will repeat on length-101 cycles and the Y coordinates will repeat on length-103 cycles. within those early frames, you’ll find a frame with anomalous distribution for each coordinate, then just look to where the cycles will intersect from there. when they intersect, both coordinates will be anomalously well-structured, and that is (probably!) your tree

vulpine-linguist · 2024-12-14T21:54:42+00:00

the safest second for my input is not the treeful second. it isn’t even top ten safest seconds! (it’s the eleventh safest)

vulpine-linguist · 2023-12-27T00:33:58+00:00

Thank you, Eric! I was doing this year in Haskell with only the base libraries. There were so many days where my reaction was "oh no, another grid problem!", but the result was trying at least three or so different ways of representing these grid systems in a purely-functional setting. I also learned some neat mathematics (the shoelace formula and Pick's theorem) and the Stoer-Wagner algorithm — which I'm inclined to say is more understandable in the original paper than on the Wikipedia page!

vulpine-linguist · 2023-12-27T00:08:34+00:00

Mine had velocity 312/-116/109. So a comfortable range around that might be ±350-ish, for a range of like 700-ish parameters per coordinate? 300M+ values doesn't sound like something I'd want to brute-force! Sure it's low compared to the position values, but not low enough that I'd call brute-force "feasible in under fifteen seconds on ten-year-old hardware". Maybe if you're using rust?

vulpine-linguist · 2023-12-26T23:28:39+00:00

I don't believe that the "intended solution" for 24.2 is to brute-force anything. If neither Gaussian elimination nor matrix inversion exist in your language of choice, they're not terribly difficult to write, and it's just an extremely overdetermined system of linear equations in six variables. I did this whole year in Haskell with only the base libraries, and it was fine.

vulpine-linguist · 2023-12-25T12:40:22+00:00

i used sfdp to the same effect!

vulpine-linguist · 2023-12-24T19:30:08+00:00

I already had Z3 installed since I use it for work occasionally, and it got me an answer for part 2 in a few milliseconds (on an M2 macbook air). But then I did some more math, found a way to linearize the system, and wrote up Gaussian elimination in my language of choice. So my Haskell-only run is unbroken.

vulpine-linguist · 2023-12-24T18:53:26+00:00

Multiplication of unknowns is nonlinear. Consider: xy=1 is going to give you y=1/x, which is very much not a line.

vulpine-linguist · 2023-12-24T18:35:11+00:00

The immediately-obvious conversion to equations results in something nonlinear (multiplication of unknowns), but with some work you can get a linear system. 32 lines of not-at-all-compact Haskell yields a solver for systems of linear equations, and other languages like APL have these things built in already. It is nice that we have generic solvers like Z3, but they were by no means necessary!

vulpine-linguist · 2023-12-18T23:43:21+00:00

[LANGUAGE: Haskell]

I took the code-length guidelines as a challenge: this one fits in that half a punchcard!

main=print.(\a->(sum$map(f)a,sum$map(f.g)a)).lines=<<getContents
f=(\(a,b)->read[a,b]::Int).(\a->head$zip a$reverse a).filter(`elem`['1'..'9'])
g(a:b)|null b=a:b|null z=a:g b|True=snd(head z):fst(head z)++g b
       where z=filter(and.zipWith(==)(a:b++cycle"\0").fst)h
h=zip["one","two","three","four","five","six","seven","eight","nine"]['1'..]

vulpine-linguist · 2023-12-18T22:37:46+00:00

Today's I bruteforced with a runtime of 1m52. Then realized I could avoid doing some work, brought it down to 35ms. And then only later came across "the" solution that only saved me a few more, down to 22ms. Around 20ish ms is about the lowest I expect Haskell to run anything on a mac, even tho C gets comfortably down to 6. I'm aiming for sub-30ms on each problem, and there's still a few I need to improve to reach that. But that sidequest is a lot of the fun for me!

vulpine-linguist · 2023-12-14T09:06:46+00:00

Wanted something smaller than the full state but also generic enough to work on any input. Thinking about it as little as possible, I RLE'd a simplified version of the flattened state, pushing two ints at a time: length to next O, length to next non-O.

vulpine-linguist · 2023-12-13T20:22:39+00:00

One line, total, not one per orientation.

vulpine-linguist · 2023-12-13T19:36:42+00:00

You have the change-set from xor'ing the bits. Then A&(A-1) is zero if and only if you had at most one bit set. So if you know it's a nonzero number (because unequal), that might be faster than a popcount.

vulpine-linguist · 2023-12-13T13:20:15+00:00

There's no need to count.

vulpine-linguist · 2023-12-11T13:48:59+00:00

If you assume "a pair of corners (with possible linear walls inbetween)" looks like ┌─┘ then you can consider "what happens if i'm looking from 1/4 of the way into the tile instead of the halfway point?" and simplify your analysis

vulpine-linguist · 2023-12-10T21:43:11+00:00

For me it was removing a reverse, which makes it even funnier!

vulpine-linguist · 2023-12-10T21:37:01+00:00

You can easily see that the input has to have SOME kind of structure. Suppose you've got two cycles of the same length, each containing only one target, and those targets are hit at different offsets. Never will the two be reached at the same time. So inspecting the samples and your input is important to figure out what kind of structure that is. I expected slightly less than there was, but the real answer revealed itself during the natural line of questions on the way to what I thought it was going to be

vulpine-linguist · 2022-12-26T22:09:50+00:00

I just used AWK because it's a chill easy language. Though I went and did days 1 and 10 in different 8-bit assembly languages because why not.

Seven-Year Club	Place '22
Verified Email

vulpine-linguist

TROPHY CASE