Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
MrQueasy
Nov 15, 2005

Probiot-ICK
I thought I was being clever reusing Day 10 for part1 of Day 18.

Adbot
ADBOT LOVES YOU

Ihmemies
Oct 6, 2012

MrQueasy posted:

I thought I was being clever reusing Day 10 for part1 of Day 18.

I did the same. It was not too bad, because 18 A was quick.

18B was quick too, because even the test data pointed out that the result will be absurd, figure out a better way to calculate an area than flood filling it :D

So I did not get stuck with it, instead I searched for "how to calculate an absurdly large area with math" instead, result was Shoelace formula.

Day 17 was hell though and I could not figure it out until pointed that pathfinding crate is better for djisktra than petgraph, since pathfinding allows you to customize the parameters of the search easily enough.

Ihmemies fucked around with this message at 12:27 on Dec 18, 2023

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
Gonna have to throw out my part 1 solution and start over, I think.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
had to also throw out my second attempt but got it on the third try, which was more or less an extension of day 10. i should have done that from the start.

Vanadium
Jan 8, 2005

Not hyped for this one because I ended up just googling "polygon formula" (and these formulas are magic, geometrists are wizards) for part 2 and I just couldn't figure out how to make a cute terminal animation for it. :colbert:

The Chairman
Jun 30, 2003

But you forget, mon ami, that there is evil everywhere under the sun

Vanadium posted:

Not hyped for this one because I ended up just googling "polygon formula" (and these formulas are magic, geometrists are wizards) for part 2 and I just couldn't figure out how to make a cute terminal animation for it. :colbert:

this one was pretty personally satisfying because unlike a bunch of previous problems where it's like "remember algorithms class" or "remember this fact about number theory", the solution to this one was straight out of the surveying class I took in college so I was able to whip up a solution that worked for both parts on the first try while all the programmers I know had their flood fill solutions blow up in part 2

Ihmemies
Oct 6, 2012

I did not even think about trying my solution for A to B. I immediately thought there must be a better way to do it. If I can't see how many zeroes a number has from a quick glance, it has too many. And that was on test data :D

Surprise T Rex
Apr 9, 2008

Dinosaur Gum

Cybernetic Vermin posted:

a book i highly recommend for anyone wanting to self-study a bit with a fairly proper focus on "real" problems is "the algorithm design manual": https://www.amazon.com/Algorithm-Design-Manual-Computer-Science/dp/3030542580/

very practical-minded, gentle introduction to each part, but has enough depth that i don't think there's a meaningful level between it and just committing to taocp and/or research papers.

I will add this to my list. I’ve just started reading Grokking Algorithms atm and while it’s super basic and assumes I’m a novice hobby coder that’s probably about the level I need for being properly introduced to big O and stuff I think.

might start day 3 today :v:

Its a Rolex
Jan 23, 2023

Hey, posting is posting. You emptyquote, I turn my monitor on; what's the difference?
I hosed up implementing shoelace algorithm for part B like 3 different times yesterday, along with a couple other approaches. Skill issue, but I really wasn't enthused about the second half yesterday at all and wasted too much time on it.

I was hoping for something interesting around the colors, not another resolve the problem with a sparse representation followup.

I'm finding the surprise second half more frustrating than anything at this point. Sometimes it's nice when the problem builds off itself. But when the second part can require an entirely different representation than the first, I just feel irritated that I need to start over.

Day 17 was good about that, IMO: it was about generalizing your rules instead of finding an efficient representation

Vanadium
Jan 8, 2005

Day 19 feels like day 5 multiple times at the same time, with extra parsing and light recursion. I had an obvious off-by-one error in part two, making me look at those ranges way to long and go "these basically describe a bunch of 4d hypercuboids and I'm trying to calculate the volume. Maybe my problem is that they overlap and I'm double-counting the intersections!" and then I messed up my check-for-overlap thing too and was confused until I looked back to what I was doing in the first place and realized that of course there's no overlap because we're only slicing up a volume. :eng99:

I'm definitely running out of steam a bit, but it'll be over soon, right?

Ihmemies
Oct 6, 2012

I finally managed to get my part process queue working, in day 19, only to get to part B.

Now what am I going to do, I have no idea. I barely even understand what the task wants me to calculate.

E: perhaps one way is to calculate which ranges of possible XMAS values are even accepted by the rules, and iterate those somehow instead of everything..?

Ihmemies fucked around with this message at 18:34 on Dec 19, 2023

MrQueasy
Nov 15, 2005

Probiot-ICK

Ihmemies posted:

I finally managed to get my part process queue working, in day 19, only to get to part B.

Now what am I going to do, I have no idea. I barely even understand what the task wants me to calculate.

E: perhaps one way is to calculate which ranges of possible XMAS values are even accepted by the rules, and iterate those somehow instead of everything..?

I know what to do for part 2 but I just haven't spent the brain power to implement it.


Create a tree where descending down into a node creates a modified set of ranges for each param,

then DFS my way into a list of acceptable ranges,

then do the math

Theoretically not too bad, my brain just didn't want to do it at 11pm last night.

Cybernetic Vermin
Apr 18, 2005

i've used up the last of my dumb luck of 2023: reading 19b i groaned so very deeply, but somehow my first attempt worked without revision or debugging.

basic idea would be to write a recursive function do_the_thing(xmas_tuple, action), where xmas_tuple is of the form ((x_min, x_max), (m_min, m_max), (a_min, a_max), (s_min, s_max)), and action is the name of a "function", "A", or "R". then do_the_thing should return a *collection* of such 4-tuples-of-ranges which describe all that make it through the action. for 'A' it is just [xmas_tuple], for 'R' it is empty, and for a function it walks through it splitting the tuples according to conditionals. very finicky though.

multiply up the max-min's of each tuple, sum those, and that's the answer.


i don't like this one that much despite having made it through, i was real lucky and there's so much room to do an off by one or otherwise mess up a range somewhere, and it is then *extremely* tedious debugging

MrQueasy
Nov 15, 2005

Probiot-ICK
Ugh, it took me forever to understand how a then b then ... n should work with the recursion.


pre:
  class WorkflowHandler(private val workflows: Map<String, List<Rule>>) {
        private fun handleStandard(
            rule: Rule.Standard,
            sum: Long,
            rr: RatingRange,
        ): Ior<Long, RatingRange> {
            val (rrt, rrf) = rule.split(rr)
            val newSum: Long =
                sum +
                    when (val o = rule.output) {
                        RuleOutput.Accepted -> rrt.size()
                        is RuleOutput.NextRule -> crop(rrt, o.name)
                        else -> 0L
                    }
            return (newSum to rrf).bothIor()
        }

        private fun handleAuto(
            rule: Rule.Automatic,
            sum: Long,
            rr: RatingRange,
        ): Ior<Long, RatingRange> {
            return (
                sum +
                    when (val o = rule.output) {
                        RuleOutput.Accepted -> rr.size()
                        is RuleOutput.NextRule -> crop(rr, o.name)
                        else -> 0L
                    }
            ).leftIor()
        }

        fun crop(
            ratingRange: RatingRange = RatingRange(),
            wfName: String = "in",
        ): Long {
            return workflows.getValue(wfName)
                .fold(ratingRange.rightIor() as Ior<Long, RatingRange>) { ior, rule ->
                    ior.fold(
                        fa = { it.leftIor() },
                        fb = {
                            when (rule) {
                                is Rule.Standard -> handleStandard(rule, 0L, it)
                                is Rule.Automatic -> handleAuto(rule, 0L, it)
                            }
                        },
                        fab = { left, right ->
                            when (rule) {
                                is Rule.Standard -> handleStandard(rule, left, right)
                                is Rule.Automatic -> handleAuto(rule, left, right)
                            }
                        },
                    )
                }.leftOrNull() ?: 0L
        }
    }

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
Huh, day 20 is another callback to a previous level.

Cybernetic Vermin
Apr 18, 2005

just getting started on 20, and already decided that this is one of those where i will commit hard to a complicated solution to a because i think i have a good guess at what b is. wish me luck.

e: bah, i had the right *kind* of guess, but i still did not write it in a way that lets me reuse a to any great extent.

e2: also having pondered a bit i suspect this is one of those which would be made a lot easier by being willing to analyze ones input a bit, but i am not really willing to do that, so this might get really tricky. as it stands it seems like a model checking problem that is likely PSPACE-hard, and the instance is large, so actually general solution is probably not a thing one can do

Cybernetic Vermin fucked around with this message at 13:45 on Dec 20, 2023

MrQueasy
Nov 15, 2005

Probiot-ICK

Jabor posted:

Huh, day 20 is another callback to a previous level.

obviously it’s because we’re falling back down through the islands

day 20 part 2 is a reverse engineering question in disguise, just with Xilinx instead of assembly

Vanadium
Jan 8, 2005

I wasted probably literally hours total on part 2 because I was inspecting and looking for cycles in the state of a bunch of modules rather than in the pulses they're sending. I did log [spoilers]all pulses instead for a while but not like per edge[/spoiler] so didn't get more out of it than "huh that sure is a sequence of strings of ones and zeroes".

Neslepaks
Sep 3, 2003

no real phone ins for me this year, having to work for every star

i'm only up to day 7 and i'm considering career change

MrQueasy
Nov 15, 2005

Probiot-ICK

Neslepaks posted:

no real phone ins for me this year, having to work for every star

i'm only up to day 7 and i'm considering career change

puzzles are different than real world problems. do not give up, skeleton!

learning how to solve silly puzzles is meant to be pleasurable in the doing, not something “useful”. there’s definitely a ramp up as you lean the “language” of the puzzles. Sudoku has x wings and jellyfish, American crosswords have an editor dependent way of writing clues, etc.

And looking up hints is the best way to learn how to do these tricks.

Vanadium
Jan 8, 2005

day 21 part 2 has me completely stumped rip

ok maybe not completely but idk i guess the gimmick is that you can just draw a diamond and you probably have almost the right number and you only really need to look at those edges in detail, but i have no intuition how to extrapolate accurately

edit: ok nm solved it, looks like the input was carefully generated so all the stuff i worried about wasn't an issue, which feels kinda cheap

i'm getting a bit tired of this style of part 2

Vanadium fucked around with this message at 23:06 on Dec 21, 2023

Cybernetic Vermin
Apr 18, 2005

got discouraged by 20b and haven't checked the days since. but i think i at least have a solid idea. what annoys me is that it for sure doesn't work in general, but i think it'll cover most "easy" instances.

betalarmannen
Jan 13, 2007

Pillbug
I think that solving 20b generally would be roughly solving halting problem. the input format allows building a microprocessor and they kinda did

Cybernetic Vermin
Apr 18, 2005

betalarmannen posted:

I think that solving 20b generally would be roughly solving halting problem. the input format allows building a microprocessor and they kinda did

it is in pspace as there's an amount of state linear in the size of the input.

i largely assume everyone's input is a slight perturbation of a binary adder or some such, they presumably have some schema to push the final bit exponentially many steps into the run. but I don't want to assume the details of that in implementation

cool av
Mar 2, 2013

even though I cringed when I saw it was 3d, day 22 was a bit of a relief compared to the last two (which I still haven’t finished)

Vanadium
Jan 8, 2005

Yeah day 22 was more relaxing. I eyeballed the size/dimensions of the input and figured I could get away with something stupid to begin with, and was positively surprised when I kept getting away with doing the stupid thing in part 2.

I got a bit sidetracked actually defining a bunch of custom types with like utility methods and something approaching abstraction to represent individual bricks and the space with bricks in it because I figured I'd probably have to switch to some sparse representation for part 2 and it might be a fun exercise to try to do that without breaking the interface. Turns out I could just do part 2 by running the code from part 1 a ton of times with some extra record keeping and it was, like, not impressively fast, but done in a minute or two.

I think I lost most time (outside of looking up to do basic poo poo in python) to off-by-one errors, fixing the off-by-one errors, and then trying to rewrite the code to be more reusable while reintroducing the off-by-one errors.

Cybernetic Vermin posted:

i largely assume everyone's input is a slight perturbation of a binary adder or some such, they presumably have some schema to push the final bit exponentially many steps into the run. but I don't want to assume the details of that in implementation

Does Santa ever publish the input generation code after it's over?

The Chairman
Jun 30, 2003

But you forget, mon ami, that there is evil everywhere under the sun

cool av posted:

even though I cringed when I saw it was 3d, day 22 was a bit of a relief compared to the last two (which I still haven’t finished)

problems like 22 are my favorite because they enable both a naive simulation that can take a minute and a more abstract solution that solves in under a second, but the input is reasonable enough that if you just want to do the simulation method you're not punished for it

MrQueasy
Nov 15, 2005

Probiot-ICK
day 22 part 2… need pruning tips

apparently the longest path reaches several spaces at times where the distance is smaller than on shorter paths

The Chairman
Jun 30, 2003

But you forget, mon ami, that there is evil everywhere under the sun

MrQueasy posted:

day 22 part 2… need pruning tips

apparently the longest path reaches several spaces at times where the distance is smaller than on shorter paths

do the search depth-first instead of breadth-first

MrQueasy
Nov 15, 2005

Probiot-ICK

The Chairman posted:

do the search depth-first instead of breadth-first

:ughh:

Vanadium
Jan 8, 2005

I tried a whole bunch of more or less clever pruning things and in the end I got the answer from a more or less brute force thing I left running on the other monitor for a few hours. I'm gonna have to sleep on this one I think.

Cybernetic Vermin
Apr 18, 2005

finally gave in and solved 20b and 21b by analyzing the inputs carefully, completing the year.

must say, i think the problem quality was extremely good this year outside of 20b and possibly 21b. sometimes i come around on a problem once i've had a moment to think after solving, but 20b was as a description entirely hopeless (no real heuristics or optimizations possible for what is just general logic), and even admitting that input analysis is sometimes an intended part it was a real crude take in this instance.

21b might have a general solution, but i did not spot one i thought had good chances. even if it does though i think it was a pretty crude simplification to apply to the input.

very subjective, but one can compare with day 23, which i think was a really nice problem. longest path is np-complete so a fully general solution does (likely) not exist, but i expect any number of approaches would solve it probably a clean dfs brute-force with tight enough code, there's probably some memoization possible, to make my own crude python reasonably quick i just contracted the graphs by replacing paths with no branches by a single weighted edge

all-in-all a good year though. learned a few new tricks (mostly abusing the networkx library for various graph stuff).

MrQueasy
Nov 15, 2005

Probiot-ICK
finished finally…

24 part 2 was the killer for me. I knew how I needed to solve it, but I couldn’t recall any of the language of linear algebra that I needed to find the specific algorithms to implement. its Gaussian elimination, and you only need 3 hailstones to solve it once you remember how cross products work well, that and fighting with how your particular language handles really large floating point variables

this year was pretty good and fun IMO. but i have to give it a few demerits for not having a Game of Life simulation, as those are my favorites.

MrQueasy fucked around with this message at 00:37 on Dec 30, 2023

echinopsis
Apr 13, 2004

by Fluffdaddy

DrPossum posted:

more like advent of chode

Cybernetic Vermin
Apr 18, 2005


wb

echinopsis
Apr 13, 2004

by Fluffdaddy

DrPossum posted:

more like advent of chode

echinopsis
Apr 13, 2004

by Fluffdaddy

DrPossum posted:

more like advent of chode

Adbot
ADBOT LOVES YOU

akadajet
Sep 14, 2003

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply