#2023 AoC Day 11

133 messages · Page 1 of 1 (latest)

coarse helm
#

oh god please i hope not ||travelling salesman|| in part 2

#

||it's not travelling salesman||

#

OFF BY ONE! OFF BY ONE!

acoustic fog
#

well

#

I tried to ||way overcompliate it at first||

#

but then I ||did the simple thing||; rank 757

merry coral
# coarse helm OFF BY ONE! OFF BY ONE!

I'm guessing you did what I also almost did ||and not immediately realise that "make it one million times larger" actually only means "add 999999 blank rows", not "add a million blank rows"?||

coarse helm
#

that is exactly what i did

acoustic fog
coarse helm
#

key to success here is ||not actually expanding the universe||, which i suspected might come up in part 2 if ||it wasn't travelling salesman||

📎 SPOILER_2023-11.py
acoustic fog
#

||Expanding the universe was just fine for me HaiShrug ||

stiff hollow
#

|| Surely the day after the problem is hella tedious because I didn't adopt the cornball strategy of mapping it to a larger grid, they aren't going to have a problem where part 2 penalizes you for just mapping it to a larger grid, surely... ||

#

|| 😛 ||

#

|| (and don't call them Shirley) ||

coarse helm
#

also found that ||adding rows but removing columns was easier when constructing my empty sets, which was fun||

tribal nova
#

Boo yeah I shouldn't have figured out how to do the thing I did in P1

merry coral
coarse helm
#

just realised i could ||cut out the work completely in part 2 because of how i modified part 1 trying to debug||

📎 SPOILER_2023-11.py
plain parrot
#

That sense of crushing despair when "This seems like a simple modification" turns into "My answer does not match example anymore and I don't know why"

verbal hawk
#

I was confused by making that exact same mistake for about 15 seconds, then I re-read the problem and went "whoops"

south whale
#

Sigh... I don't want to do this...

coarse helm
#

we will think no less of you if you choose to not

verbal hawk
#

This one isn't too bad, though. It's easier than yesterday!

#

also, I got to use one of my favorite Haskell functions:
||```haskell
pairsOf :: [a] -> [(a, a)]
pairsOf ls = [ (x, y) | (x:xs) <- tails ls, y <- xs ]

#

It's just such a silly thing to do.

south whale
#

my brain is already thinking... but since I can see spoiler text, I know what Part 2 is, so I'm going to have a big think before I even begin to come up with other approaches...

#

amusingly, the harddest part of this is, given R, working out the empty rows/columns...

verbal hawk
#

Aw man, I can't even give you spoilered hints in case you want them, because that doesn't do anything.

winged flume
#

well, I just lost ~20 minutes to a stupid issue:
||a 12 digit number isn't gonna fit into an int ya dummy, of course it's just gonna give you random nonsense||
also, rather than ||expanding the grid, I just noted which spaces were empty, and added 1000000 to the path if I hit them, instead of the 1 for a nonempty space. this did make it easy to eventually figure out the right solution by counting how many times I "crossed the empty", at that point the solution it becomes even easier: base distance + crossings * (expansion factor - 1)||

twilit talon
#

today was pretty straightforward, though I was worried what part 2 was going to be. sadly, did not wake up early enough for leaderboards (but it was early enough that I can nap for an hour before getting ready for work now :) )

south whale
#

Done it

#

Since I knew what was up, I had time to plan, and so I think I got quite neat code

#

I ||got the coords of each galaxy, worked out where the gaps where, then inflated the coords by each gap in between, then a simple n^2 step to sum distances||

#

...and that was a Sunday puzzle!

verbal hawk
#

It may not scale difficulty exactly like the NYT crossword

south whale
#

it is common wisdom (aka some guy down the pub said) that weekends are harder

coarse helm
#

this is a monday puzzle btw

unkempt cave
#

I spent longer on part 1 than part 2 because ||expanding the universe|| actually ended up more finnicky than just ||counting crossings||

coarse helm
unkempt cave
#

I'm not convinced day 5 was actually that hard

plain parrot
#

It was hard if you didn't do it the right way because part 2 value set was extremely large

south whale
coarse helm
verbal hawk
scarlet epoch
sonic bone
#

||You can't trick me with your fancy diagonal paths, I know a Manhattan distance when I see one!||

south whale
#

|| 👍 ||

plain parrot
#

|| I'll never forget Manhattan metric|| because we spent almost entire semester using it as an example for Topology 101

verbal hawk
#

L1 and L2 get used all the time. When do we get a problem based on L3?

south whale
#

Give me L∞!

verbal hawk
#

I think if that's defined, all distances will be either 0 or 1

south whale
#

L inf is basically max.

verbal hawk
#

Oh, I see

#

The diagonal seems weird, though

#

Eh, I guess the root of 2 approaches 1, so it's fine also

scarlet epoch
#

|| In part 1 I parsed the input directly to a list of vector positions which meant the "expanding" was not an issue except for the fact I didn't have a 2d vector class that used longs, fixed that now. Worked around it originally.||

nimble panther
#

Hello yes it's me joining the off-by-one crew for part 2

ripe drift
#

OK, I think I probably did today's in a standard way. Good Monday-morning problem, I think.

Part 1: Naive. Though I initially thought ||I was supposed to sum the distances to the closest galaxies, not all galaxies.|| Thankfully I noticed the problem quickly because my example output was way too small.

Part2: ||Store a list of offsets for X and Y values, add them while converting the base representation into a coordinate system.|| I tried the solution to part 1 first, because I wasn't sure whether Python strings would die on these inputs or not. Turns out they do.

#

Python numbers are so nice, I wasn't sure if Python strings had some hidden niceties too like they were secretly ropes or something that can better handle the stupid operations I was doing to them.

fickle parcel
#

I need to learn not to try and solve this at work. It's like an ADHD simulator with people bothering me every 2 minutes.

unkempt cave
#

the fact that python has arbitrary precision integers helps out a ton in a lot of AoC puzzles

ripe drift
#

I try to solve it while having my morning coffee. If I finish my coffee, it's time for real work and I can pick it up again at lunch.

#

Yeah, the numbers thing is why I use Python even though I hate Python more every year I do AOC.

#

Every year I learn new ways that Python does not do what I expect it to do.

#

This year it's how lambdas and closures work (or rather, how they don't seem to work).

unkempt cave
#

python's lambdas are notoriously bad, they were intentionally designed to be bad because the BDFL didn't like functional programming

ripe drift
#

But thankfully it has partial functions which do work the way I expect them to work.

unkempt cave
#

what was it about closures that didn't work how you expect?

#

closing over a loop variable?

ripe drift
#

Let me see... There was a day where we had to pass numbers through a bunch of maps, for seeds or something? And I wanted my maps to be closures over the values in that instance of the loop. Something like this:

for x in (..):
  someFunction = lambda y: x + y
  someStructure[key] = (..., someFunction)
...
result = someStructure[key][-1](value)

But that didn't work. The variable x wasn't correctly captured in the lambda's definition. I ended up currying another function with the partial:

def someFunction(x, y):
  return x+y
for x in (..):
  someClosure = partial(someFunction, x)
...
result = someStructure[key][-1](value)

And that worked fine.

unkempt cave
#

yep, that's a footgun a lot of people hit

#

not unique to python either, golang has the same issue as do many other languages

ripe drift
#

I'm not entirely sure how Python binds local variables to lambdas, but it's not what I expected.

unkempt cave
#

the closure has a reference to the outer scope, and variables are looked up in that outer scope

#

so x is "whatever the value of x in the parent scope is right now"

ripe drift
#

Oh, is that all it is? But x is defined only in the loop? How can it even be expected to work this way??

unkempt cave
#

well technically x isn't only defined in the loop, when the loop exits x retains the last value it had while looping

#

but if you say, explicitly deleted x, you'd get a NameError (no such variable) if you tried to use it inside the closure later

ripe drift
#

It is amazing how bad a language can be and still be this popular.
(In before Java jokes)

unkempt cave
#

for example:

>>> def f():
...     return lambda y: x + y
... 
>>> g = f()
>>> g(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in <lambda>
NameError: name 'x' is not defined
#

note that the name error doesn't occur until the lambda is executed

nimble panther
unkempt cave
#

just to drive home the point that this is a dynamic lookup, watch what happens when i define a new global x, after the fact:

# 
>>> x = 1
>>> g(0)
1
#

all variable lookups in python search all containing scopes in order until the first scope where the variable is set.
normally that's just local scope and global scope. In a closure, it's local scope + the parent scope + global scope

ripe drift
#

Would this behaviour also work this way if I'd used a local def instead of a lambda?

unkempt cave
#

yes

ripe drift
#

OK, then I'm really glad I looked to currying as my next step, because I'd considered using def briefly to see if that made a difference.

unkempt cave
#

def foo(): return bar is (mostly) identical to foo = lambda: bar

#

the (mostly) comes down to things like "does the function have a human-readable name in a traceback"

ripe drift
#

Makes sense. Thank you for enlightening me into this nonsense.

sonic bone
merry coral
#

The closure-in-a-loop footgun exists in some form in pretty much every language that has both closures and mutable variables. Python, Javascript, Go... it's a common problem.

sonic bone
#

C++ of course takes the kitchen sink approach and lets you specify whether a lambda captures by value or by reference.

merry coral
#

Some languages manage to avoid it in various ways... Java requires all captured variables to be final to sidestep the issue. C++, in typical fashion, lets you explicitly specify if variables are captured by copy or by reference. Javascript has let keyword which changes the loop semantics.

#

Ruby has loops be usually implemented as function calls already, so each loop body is its own entire scope

acoustic fog
#

That's a useful amount of control for C++ though

acoustic fog
vale wadi
#

I wrote a nice quick solution to part 2, then spent an hour manually verifying and debugging only to realize I was modifying the input data in a way that created a repeating off by one error 🙃

fickle parcel
#

*reading part 2*
AHHHHHHHHHH!

#

OK, OK, this is fine. I can fix it. This is fine...

verbal hawk
# unkempt cave python's lambdas are notoriously bad, they were intentionally designed to be bad...

Also, doesn't understand functional programming.

[...] makes it possible to easily implement concepts that superficially resemble concepts from functional languages, like currying, map, and reduce. The primitive operations that are necessary to implement those concepts are built in Python, where in functional languages, those concepts are the primitive operations. You can write reduce() in a few lines of Python. Not so in a functional language.

#

like... what? he thinks these things are primitives in functional programming?

fickle parcel
#

Human kind has many ways of describing Hell. Flaming tar pits, loneliness, other people, the island from Lost, the It's a Small World After All ride.

#

To me, Hell is explaining how my Excel sheet for Day 11 works.

#

And/or my thought process in tackling this problem.

steel pike
#

my spreadsheet is fairly nice. this one's fairly gentle on excel

fickle parcel
#

I've certainly made a few decisions and my ass is very much bitten.

steel pike
#

well it's not that gentle if the choice you made for part 1 was ||oh? there's only 6 empty columns? i'll manually inflate. but obviously that's not viable for part 2. but it's not too bad to just add penalties to the coordinates||

fickle parcel
#

It's 100% what I did

steel pike
#

i mean it's what i did too

fickle parcel
#

I'm happy with my decision to continue with Excel and not converting my new input to LUA because that would have been a nightmare.

steel pike
#

anyway on first reading i thought the problem was find ||the pairing between the galaxies with minimal sum of distances and that's a much much much harder problem lmao||

fickle parcel
#

Solved.

#

The problem itself is not that difficult ||abs(x1-x2)+abc(y1-y2)|| It's just arranging all the ducks in a row.

#

Once again, a crime has been solved using math,

ripe drift
#

Like all crime, it was also committed by math.

steel pike
#

well, this would have been a significantly more unpleasant problem in excel with a different metric

civic coral
#

Missed a bunch of days due to life stuff, but had a chance to get back to today: Part 1 ||I did the naïve thing and just expanded the array, which turned out to be a mistake when I got to part 2||

SPOILER_image.png
steel pike
#

did you also fall into the other trap? ||which is adding 1000000 instead of 999999||?

civic coral
#

Part 2: ||Refactoring it for part 2 made things a lot simpler and faster, though slightly more edge case management with the list of arrays||

SPOILER_image.png
vale wadi
civic coral
#

it's LabVIEW, but basically yes

twilit talon
#

because this is wild and cool

civic coral
#

go for it

#

let me know what their reactions are 😉

verbal hawk
#

One of my friends joked that the spoiler warning isn't necessary, no one can read it anyway. (Another friend just complained about how painful LabVIEW is for complex stuff, despite being easy to get started with...)

civic coral
#

it really bogs down for complex math, but it works well for control systems