#2023 AoC Day 12

99 messages · Page 1 of 1 (latest)

lapis olive
#

...I ... I don't ...

calm hearth
#

Huh... || Picross ||

fiery robin
#

"Oh, sorry, common mistake! This is actually the onsen! The hot springs are next door."

You look in the direction the researcher is pointing and suddenly notice the massive metal helixes towering overhead. "This way!"

#

Imagine that twist on road quest

rich swift
#

Alright AoC has instantly stopped being fun tonight. I don't feel well, I'm putting way too much pressure on myself because of leaderboards, and I've put aside other things that I should have done instead so I could compete tonight. Gonna sign off, go to sleep, try to take a breather, and then keep at it later. Good luck, y'all.

charred delta
#

well that was very slow for me today

#

but I did end up with a pretty clean solution, at least

topaz gale
#

... I honestly don't really know where to go with this. Like, i'm familiar with the concept, but I don't know how to solve this efficiently enough.

#

I've come up with two different solutions and both are running away in the background in the hope that they come back with an answer while I try to think of a third

fiery robin
#

heh. This was something that was a big deal during my ICPC days

#

The faculty advisor always went on about how it's important to ||detect failure and bail out as soon as possible||

sullen lynx
#

Picross, anyone?

charred delta
#

I'm sad I never got to do ICPC

#

because covid

sullen lynx
#

I don't think I can solve this. I'm just gonna nope

distant onyx
#

ooh. I know this is a ||combinatorial problem about permutations|| but I don't know it off the top of my head. I do have an idea for a naive but not brute force solution but dunno if it'll work

lapis olive
#

I refuse to brute force it, but I can only see a faint image of another way...

#

Took 22 minutes for 100 people to finish Part 2...

onyx radish
#

I went through 3 different approaches to get one that would be good enough for part 2

#

|| the first key recognition is that the list of group sizes determines how many # there are total, and so how many remaining ? are # is known exactly, the problem is just where to put them ||

#

|| but then just going through every possibility isn't fast enough for the big version, so i switched to going through each allowed choice for the beginning of the string and treating the rest as a subproblem with memoization, with early exit to 0 combinations whenever it's no longer possible to fit the necessary #||

topaz gale
#

my brain hurts

onyx radish
#

|| It's tricky to think about how for the # case you need to consume the right number of consecutive # and the following . (or the ending of the input), but once you have that, the no-op leading . case, and the arrangements(?..stuff..) = arrangements(#..stuff..) + arrangements(...stuff..) recurrence, that's the whole solution ||

#

|| I wonder if there's some algorithm for this specific problem, to put bounds on the positions of the runs of # directly given the runs of ? and the lists of group sizes, but at any rate if so I'm not going to independently rediscover it in an hour 😄 ||

onyx radish
latent sapphire
#

is it just me or is day significantly more difficult? I don't even know where to begin; this is going to be one of those that will stump me for the whole day

lapis olive
#

It feels like a lot harder... but it's not odd or a weekend! Oh no, our assumed trends!

topaz gale
#

... oh, ffs it's because I implemented your plan as attempt4 and then was still calling attempt3 in the mainline

#

well, I guess I have the star now at least. Still sad that I had to read a spoiler to get there. I just really thought that that approach could never work and I was trying to do something much more clever, but all my more-clever ideas were just... not getting there, even a little bit.

onyx radish
#

|| It took me writing a whole brute force solution, using it for part one, and then having it just take too long to get anywhere in part 2 for me to even try it this way... but I'm definitely going to remember for the future that this approach works well when there are a bunch of short independent sections of uncertainty to find all the combinations for ||

topaz gale
#

... ok so the one clue I actually needed to pilfer from epsilon_vee's code is ||aggressive memoisation... that once you've placed the first few blocks, and you're trying to place the later blocks, you can easily end up in a state you've seen before and can pull that from the memo. I don't know why this didn't occur to me at all. Applying that to my own solution also runs super quick.||

mint panther
#

backburnering this

topaz gale
ornate pebble
#

When I got over my initial "surely this won't be good enough" reaction, my first attempt worked well.

abstract garden
#

ugh

#

why is this the one that's so evil

ornate pebble
#

||I step through the string character by character, counting runs. If I hit a ?, I split into two sub-calls, one for each option. I aggressively return early as soon as I find a contradiction. Finally, I slap a memoize around the while thing.||

abstract garden
#

finally got there

distant onyx
#

ok, I knew I needed to ||cache/memoize seen states|| but I got lost in the recursion and had to rewrite and try and be less smart (|| just go character by character instead of trying to be fancy with regexes||). also, p2 then rewarded me for using python because ||multiplying strings and lists is so handy||

#

lesson I am learning this aoc: gotta stop trying to be elegant out of the box. just do the straightforward thing

latent sapphire
#

oh bloody heck finally done, but it runs relatively slow on java (~2s), which is concerning. || There were so many edge cases I missed in my recursion method in part 1 and it was a nightmare to debug, but luckily the only issue I had in part 2 other than employing memo-isation was not including "?" between repeats and changing int to long. I have no idea how to elegantly decompose the problem for DP, i'm sure the other answers here can have better ideas||

fierce plank
#

Todays mood:

SPOILER_image0.jpg
latent sapphire
#

Hmm maybe I should try || just processing the whole thing as a string, instead of what I did which was to transform the string into a list of contiguous sections of "#" and "?" (e.g. "?#.?#.....?#?" becomes ["?#", "?#", "?#?"]), because the number of dots between each contiguous section doesn't matter. Maybe that might improve performance ||

Update: turns out it is slower, and my original approach is faster (at least for the way I solved it)

fierce plank
runic plume
#

I've done a lot of || nonograms so I know a lot of the mental tricks for resolving the unknowns, but I'm unsure how best to express them and it is likely poisoning my approach ||

bold phoenix
#

Jesus, I ||implemented caching wrong|| at the start, then spent like four hours trying to ||find some way to combine results from the simple case into the complex case (which I don't think can be done)||, only to see that ||everyone else also just cached the recursive results|| and doing that properly. 🤦‍♂️😤

#

The fun part of today for me was getting to abuse booleans as ints 🙂

bold phoenix
dense matrix
#

oof, I think I may not be attempting this one.

twilit dock
#

I'm completely stumped today. I always get hung up on problems where I don't know if I should be ||culling my search tree more|| or ||finding some way to memoize things||. I've tried both. The former is way too slow, the latter yields incorrect results for even miniscule inputs and I don't know what's wrong.

#

I've sunk way too much time into this already.

loud whale
#

i dunno. maybe i'm being naive. and i'm only on part 1 still. but solving a several by hand seems to suggest you can ||cull pretty dang aggressively||

sleek jasper
#

recognized the problem immediately. with some help from the internet came to a solution for part 1 based on ||building all the possible lines using combinations, then culling each line as I found a contradiction|| that ran fine (24ms on C#, slightly above but largely in line with numbers I've seen so far. went to part 2 ||editing my imputs to account for the unfolding was easy, but then my solution just decided that no, we're not doing this in a reasonable time||

patent lagoon
#

I'm currently only ||culling the search tree and not using memoization|| and my with the program running on all 16 cores of my Laptop I think it's going to be done in a few hours. But reading the comments here I'm going to have to try ||memoization||, it just really won't work well with my current approach

patent lagoon
sleek jasper
#

||I mean, I just started mine and started watching the handball match that just started, I'll see where it's at when that game finishes
but also I'm doing this to learn, so I'll probably be looking into the fancypants things mentioned here to see if and how I can implement those and to what effect||

patent lagoon
sleek jasper
#

I think I would do that, because that way at least I know how it works

distant onyx
twilit dock
#

I have found one of the major bugs in my code, but it's still very slow. ||I feel like what I need is smarter culling. Caching is helping but it's definitely not working the way I expect. I'm getting an intermediate result for one of my rows as being in the hundreds of trillions, which seems a little large to me so I'm not sure if this strategy is even right at all. It's managed to get to 25 out of 1000 rows, though, in about 5 minutes, which is much better than all of my previous attempts.||

lapis olive
#

At best, I might be able to do this by reimplementing someone else's code in R... at worst, just gonna copy someone's python code and run that directly...

#

[I hit the worst point often]

charred delta
#

Maybe I should share my code here, since it seems like people are having a rough time today

#

My part 2 solution (python 3)
||```py
@cache
def m(a,b):
if len(a)==0:
return "#" not in b
c=0
for i in range(1,len(b)):
if "#" not in b[:i] and "." not in b[i:i+a[0]] and i+a[0]<=len(b):
c+=m(a[1:],b[i+a[0]:])
return c

for line in lines:
s = "."+((line.split()[0]+"?")*5)[:-1]
v = tuple(ints(line)*5)
o += m(v,s)

twilit dock
#

Thank you for that but I'm not yet ready to look at another solution yet.
There's definitely something wrong with my ||caching, because I can see from debug output that it should be matching on lots of sparser inputs (ones with lots of small runs of springs), but it's clearly not matching. The rationale I have is that a string like ..#. isn't different from .#.., in the sense that all suffixes you would attach to both would have the same number of combinations. But something about how I'm implementing it is wrong.||

twilit dock
#

I scrapped what I had and did it again from scratch. Ran in 662 ms. Let's see if the answer is right.

#

It was right.

#

I don't have any idea why my first ||cache|| didn't work. My new one, as far as I understand it, is functionally identical, but it works and the other one didn't.

flint prawn
#

Do you have to use caching to do part 2 in a reasonable amount of time?

charred delta
sleek jasper
#

C# specific question about part 2: ||trying to implement memoization. I've got a recursive function that takes string, List<int>, int and returns a int. I've made a static Dictionary that has a key of Tuple<string, List<int>, int>, k,v pairs get added to the dictionary fine, but I seem to be unable to find the value if I call the function with the same input. if I inspect the dictionary I can also see what seem to be double keys from when it "should" have found it the first time||

charred delta
#

Also maybe ||strings||, I'm not a C# expert

sleek jasper
#

okay, I think the issue was ||the List<int>, fortunately I know I'll be sending in the same List, so I can just use the length of it instead||

#

yeah that sure did something ||1430173 calls of my recursive function -> 497 calls (for the example)||

#

now back to the classic issue of thinking that everything should work, and the example working out, but the site disagreeing with your answer

twilit dock
#

Oof. That's the worst. I've managed to go this far without that problem. Though today I technically cheated because on a different Discord server someone left spoilers which if why I even considered the strategy I ended up using.

Every year, I forget about ||memoization|| entirely.

runic plume
#

I don't like my answer, but it worked. I'll have to review other solutions and/or clean it up.

sleek jasper
#

I think this is the second puzzle I've had to get inspiration from here on how to adjust to part 2 ||I'm just not used to thinking about solutions that need to run at scale, so I'm not familiar with any of the strategies to deal with that||

just got my answer in, and it runs in ~300ms, so very happy with that

#

as for the issues I had, in order of finding them ||once again the data was too big for c# ints, should get used to thinking about the size of my numbers. Error where I didn't check if the last block I placed would end up next to a confirmed spring, had to load up someone else's solution to find that one by realising some of the lines that should have a single possibillity ended up having two||

lapis olive
#

we are getting into standard AoC here. Part 1 relatively modest, Part 2 EXPONENTIAL!!!!

#

oooh, someone did an R solution! steals

calm hearth
#

Hmmm, annoying.
My part 1 solution works for the example data, but not for the real data (runs, but gives a too-high solution)
I already did a bunch of interation to catch all the cases from the example, but now that it catches those, I don't really know how identify any more issues

#

Maybe I should just rewrite from scratch with what I've learned, and hope it's something in my patchwork iterative improvements

runic plume
lapis olive
calm hearth
#

Good idea - I might come back to that later

charred delta
#

one issue I ran into that gave me a too-high solution despite having a correct output for the example input was ||I accidentally allowed pieces to be placed past the end of the map||

#

honestly the example input isn't great - it's a lot less constrained than many of the real test cases

runic plume
#

|| Adding caching brought my solution down to 185ms, now I just need to clean up the logic itself ||

flint prawn
#

I gave in and reimplemented @ornate pebble's solution for part 2

twilit dock
#

I have no idea how to make this solution fast without some form of ||caching||. I am amazed.

calm hearth
#

Ah, figured out part 1, time to be overwhelmed, I assume

runic plume