Day 09 Discussion

[loud ridge]

Ladies

[lavish kettle]

i read part 1 and was like oh okay ez

not i don't wanna read part 2 at all

[pine pewter]

except that p2 might be the hardest part of the entire year

[loud ridge]

Not sure how to do part 2

[lavish kettle]

I got the brute force solution but it just takes to long lmfao

[slate trench]

seems like same as d8

for part1, just read, didn’t solve

[lavish kettle]

p1 is super easy

p2 is where the pain begins

[pine pewter]

I can't even see a brute force way

I think there must be some geometry formular with which you can solve p2 trivially

[lavish kettle]

brute force didn't work on the big input .

[pine pewter]

happened in the past

[lavish kettle]

i tried marking all points that can be inside the enclosed shaped and its just too many points

[pine pewter]

it's over

[lavish kettle]

ok i think i have somethign

[slate trench]

p1 is yesterday's but simpler, let's see p2 now

no idea how to parse p2 🙂

[pine pewter]

bro u doing day 9 or?

[slate trench]

yes I did d9p1 and now groking p2 which I guess just means there is an inside shape

[pine pewter]

groking
🤮 🤮 🤮 🤮 🤮 🤮 🤮 🤮

what's the point?

[lavish kettle]

groking also means to understand

.

not necessarily asking grok

lol

[pine pewter]

oh

ok then my bad

[slate trench]

yes it means trying to understand - not the musk abomination/appropriation

so it's just a ||polygon and they give us the order even|| (should I spoiler this)

[pine pewter]

wut

I didn't notice that

that changes everything

omg

[spring veldt]

isn't part 2 quite hard

semi naived part 1 in 16ms

[pine pewter]

very hard

[spring veldt]

definitely not an optimal solution but whatever

[spring veldt]

yeah lmao i reused code

||it's the same approach but you use a max heap instead of a min heap with a different cost function||

[pine pewter]

you should probably spoil this tbh

[spring veldt]

it's not a spoiler

[pine pewter]

I feel so stupid for not looking at the input closely

[pine pewter]

I just noticed that now lol

[spring veldt]

it's there in the image

[pine pewter]

fr

wut image

[spring veldt]

summoning the game engine devs on this

the example grids i mean

[spring veldt]

https://tenor.com/view/bop-bop-bop-shoebody-bop-squad-summon-dark-magic-gif-13983602502478731881

[pine pewter]

damn I'm sdumb af

[slate trench]

I'm making a "draw" version just for fun

including removing offset

[spring veldt]

wait why do I remember the math tech for this

unlocked sophomore year wisdom hold on

[loud ridge]

||Couldn't it also be concave?||

[slate trench]

||well I was wondering concave/convex yes|| but I don't know if it matters yet

[spring veldt]

||still a polygon, some parts of it do seem to be concave tho||

[loud ridge]

It does matter tho for the checks....

It works for the example but not for the actual input

[slate trench]

hmm Width: 96850 Height: 96672

that's ... a bit much

I thought I'd be cool and draw the input

[loud ridge]

Okay i gotta work, someone ping me with a hint after you get it

[pine pewter]

work at midnight twf bro

[loud ridge]

||What I mean is like this

@#@   @#@
###   ###
##@###@##
#########
@#######@

So now if you just check if the corners are all inside the red/green area it will still give a bad output
||

[loud ridge]

It's 8:40 am

[pine pewter]

my drawing is better

[pine pewter]

u not late for work then?

[spring veldt]

LOL that's the exact example I showed to my friend

down to the concave direction

to show him how hard this problem is

[loud ridge]

I've been at work since 7:30 Just didn't work

[slate trench]

rasterizer doesn't like it

panic: runtime error: slice bounds out of range [-2147442263:]

goroutine 1 [running]:
golang.org/x/image/vector.(*Rasterizer).floatingLineTo(0x102fc4618?, 0x2c80108?, 0x1?)
        /Users/dl/go/pkg/mod/golang.org/x/[email protected]/vector/raster_floating.go:60 +0x3fc
golang.org/x/image/vector.(*Rasterizer).LineTo(0x102850060?, 0x2b37d0?, 0x140?)
        /Users/dl/go/pkg/mod/golang.org/x/[email protected]/vector/vector.go:189 +0x24
grol.io/grol/extensions.createVectorImageFunctions.func2({0x102850060?, 0x140002b37d0?}, {0x1400002a178?, 0x102482e7c?}, {0x14000117140, 0x3, 0x1400002a1d8?})
        /Users/dl/dev/grol-io/grol/extensions/images.go:470 +0xb4

looks like go doesn't like a slice (image) with 9,362,489,679 pixels

kinda weird it's using signed int32 instead of int64 (on a 64bit os)

||it's the death star||

||see the hole ...|| these bastards

[spring veldt]

LOL

i have no idea how you even computed interiority but that is very funny

[slate trench]

just drew it at 1/10th scale

[spring veldt]

still don't know the algorithm tbh

wait

hmm

wait is this actually easy

i mayhaps have realised something

[slate trench]

the algo is ||

for pt := points[1:] {
    x := pt[0]
    y := pt[1]
    println("Line to:", x, y)
    image.line_to(img, x, y)
}
```||

[spring veldt]

how many points are there again

10**10?

[slate trench]

dimensions even after offset -minx,-miny are about 100k x 100k

[spring veldt]

yeah that's e10

theoretical idea

[slate trench]

10^5 * 10^5 = 10^10 yes

[spring veldt]

||draw all green points, start "flowing " from top to bottom. when you run into a red or green point, toggle the "interiority" flag on the tile. you can use this to compute interiority for all tiles but it's slow. you could alternatively mark each edge tile as an "off" or "on" tile||

[pine pewter]

based kek

[slate trench]

green or red is a... wait for it... red herring

[lavish kettle]

|| thats what i tried to do, its too many tiles to mark, memory suffers ||

[slate trench]

will sleep on it, it's getting late here but this is fun

[lavish kettle]

i think i'll just leave my brute force solution run over a few hours too

hopefully i get something

[lavish kettle]

guys i think my cpu isn't liking this

i think

.

[loud ridge]

Ugh so many edge cases

My thinking:
|| Loop over all possible rectangles like in p1
Loop over each edge of the rectangle
Check if it intersects with any of the edges of the big polygon ||
but i can't get the math to work

[spring veldt]

ooo

[lavish kettle]

|| thats what i am trying to do
generate all points that are on the edge or inside the enclosed polygon for all pairs of red tiles||

and its been at 100% 😢

i tried doing it all concurrently

checking of points

[hot rover]

The input is ||ordered|| right?

so you can || calculate the edges || and || flood fill||?

[spring veldt]

it's a 10^5 x 10^5 grid

[hot rover]

oww, only 10G xD

[spring veldt]

looking at my 32 GB of RAM

[hot rover]

otherwise ||raycasting|| to check if a point is ||inside the polygon||

All points of the edge in a rectangle should be inside

[loud ridge]

||But then you have to check every point on the edge, not only the corners||

[hot rover]

don't you have to do that anyways?

[loud ridge]

||You could check for intersections between every edge of the rectangle and every edge of the polygon, that should cover it, but couldn't get it to work||

[hot rover]

ah right, that should work

[opal blade]

i remember studying similar problem in my design and analysis of algorithms class (nearly 2 years ago) and i feel i could write equation and solve without making a giant grid in memory.

some modified version of ||convex hull|| would do the trick perhaps? and check if ||all corners of the rectangle with-in the area||.

[loud ridge]

The problem is that it's ||not convex :)||

[hot rover]

someone made an alternative test input

1,0
3,0
3,6
16,6
16,0
18,0
18,9
13,9
13,7
6,7
6,9
1,9

.#X#............#X#.
.XXX............XXX.
.XXX............XXX.
.XXX............XXX.
.XXX............XXX.
.XXX............XXX.
.XX#XXXXXXXXXXXX#XX.
.XXXXX#XXXXXX#XXXXX.
.XXXXXX......XXXXXX.
.#XXXX#......#XXXX#.

answer: 30

[opal blade]

I got an idea and then i looked at this and realized my idea is bad. ||thought i would check if all 4 corners of a rectangle is inside a some other rectangle||

[icy ridge]

My solution is not in Go but I am shocked nonetheless

day09_part2             time:   [1.8604 ms 1.9990 ms 2.1471 ms]
                        change: [−93.607% −93.303% −93.021%] (p = 0.00 < 0.05)
                        Performance has improved.

It's always a mf ||FixedBitSet|| and it's incredibly good at this

[slate trench]

that panic I get looks buggy as slice index should be 64bits

ah probably because of https://cs.opensource.google/go/x/image/+/refs/tags/v0.34.0:vector/raster_fixed.go;l=27

[slate trench]

bummer that discord doesn't take svg images

can't send svg so here is the... screenshot of the svg

[hot rover]

This case isn't in the actual input for what it is worth. My solution doesn't support it

I ||only check || if || an edge intersects||

[vast geode]

nobody give me any hints i hate getting hints. just was gonna say today is a mf

pretty sure i got the right idea but there's a bug somewhere

[vast geode]

i feel like this should help me but i don't think it does lol

[slate trench]

it’s mostly bitching how evil the aoc people are. apparently btw some people got a trapeze not a disc

[vast geode]

yeah this one is nasty lol

[slate trench]

I have a bug and it pisses me off - pretty close to throwing the towel 🙂

[vast geode]

ditto lol i'm like 99% sure this is the correct (enough) appraoch but i got a bug too

[vast geode]

yeah I might have to retry this one in go later on

[slate trench]

(╯°□°)╯︵ ┻━┻

[spring veldt]

didn't turn on my pc at all yesterday, was doing some irls

[slate trench]

I don't get it, I get "too high" for this:

that would imply it's a bad rectangle... but ... what's bad about it ?

[loud ridge]

@slate trench if I send you my input can you draw it? I wonder if they're all death stars

[slate trench]

weird, I re ran it and...

[slate trench]

sure, happy too! and I think there are 2 types: death stars and trapezes

same/similar:

leaderboard is borked btw it shows I did 10 which I haven't started

[slate trench]

nvm that's my auto dark mode

[vast geode]

after day 12 i'm gonna redo this one in go bc can't get part2 to work in elixir but i think i have right idea

[slate trench]

if you send me your input I can draw it, curious if you also got a death star like @loud ridge and I

[spring veldt]

stole someone else's p2 solution, not a math guy and its 3 am and i was tired and stressed over other shit and just wanted to get done with this

i knew the basic gist of what i had to do but the final formula was a pain

[vast geode]

im bout to but giving myself a few days.

[vast geode]

hmm so i've found the incorrect behavior aha

now how 2 fix is da question

[vast geode]

we might have done it boys

HAH