#AoC 2023 | Day 5 | Solutions & Spoilers

1285 messages · Page 2 of 2 (latest)

smoky crane
#

I now get it

small sun
#

I am now print-debugging my solution becaue my brain can't let it go

regal vapor
umbral prism
#

they were given in the example

smoky crane
#

First you think: I can just brute force this.
Then you think: wait no, no I need to work based on ranges and offsets and that gets you pt 1
Then in Pt 2 you think: I can just brute force this.
Then you think: wait no I need to work on ranges with ranges.
And then you get it!

regal vapor
#

If a brute force is a thing, it will always work for P1

small sun
#

WAIT

#

WAIT

umbral prism
#

79 14 55 13 = range(79,79+14) range(55, 55+13)

regal vapor
#

that I have full confidence in

rocky orbit
#

well

#

technically

smoky crane
rocky orbit
#

you don't have to use ranges

regal vapor
small sun
#

thank

rocky orbit
#

there's actually an alternative solution someone showed me where you kind of work backwards

clever geode
rocky orbit
#

and find the lowest valid possible output

regal vapor
smoky crane
#

Im not massive fan of the mathys optimisation stuff. Im still resentful of that bus one about 2 years ago

hallow wren
#

you aren't using enough force if bruteforce doesn't work

smoky crane
#

(I think its becasuse im bad at maths)

umbral prism
hallow wren
clever geode
#

Oh i see mb

smoky crane
small sun
regal vapor
#

will that fix it?

#

if so that's hilarious

small sun
#

I believe so

regal vapor
#

I wait with anticipation

rocky orbit
#

was cleaning it up a little and pycharm gave me this warning, lol

SPOILER_image.png
umbral prism
small sun
clever geode
#

Ok i understand the first line the only thing i dont get is how you get the second range atm

regal vapor
small sun
#

I might could actually do this one

#

BRB

smoky crane
hallow wren
#

i just know that last years file system is something i have no idea how to do. 2021 it is then

umbral prism
# clever geode Ok i understand the first line the only thing i dont get is how you get the seco...

that was the code block. #1181459209422917683 message
so you start with a list of seed ranges. for each one you apply a rule.splitting them up any that are matched get converted and saved until after this group is done. Any that are not matched are new ranges to be checked by the next rule in this group.
after all the rules are checked, you have a collection of remaining new ranges, plus all the ones you saved this group.

odd frigate
regal vapor
#

I will restrict my debugging offers only to solutions that run in less than 10 secs

odd frigate
#

Both parts (with part 2 not giving correct output) is 0.0013396998401731253

#

def less than 10 sec

regal vapor
#

ok will maybe look

clever geode
#

i dont get the conversion process at all

umbral prism
# odd frigate Anyone able to review Part 2 of this for me. For some reason, I am unable to see...

on a quick glance:

                    # Updating seed_range
                    start: int = dest + (curr_seed.start - section_range.start)
                    end: int = dest + (curr_seed.end - section_range.end)
                    curr_seed = SingleRange(start, end)
                    break

in this case when the match is inside your seed range, do you end up with 3 new ranges? The matched range which is saved for the next group, and the before the match and the after the match ranges, which are now looked at for the next rule in this group.

small sun
#

We will be waiting for

image.png
hallow wren
umbral prism
clever geode
#

I cant thank you enough for the help man but i really really have to go now or il be a zombie tommorow

hallow wren
#

good night

clever geode
#

you to

clever geode
hallow wren
#

yeah should sleep. aoc is adicting. i got things to so that aren't code XD

small sun
#

TRAITOR

hallow wren
#

chem lab protocol

clever geode
clever geode
hallow wren
#

!e print("Traitor"> "traitor")

celest coveBOT
#

@hallow wren :white_check_mark: Your 3.12 eval job has completed with return code 0.

False
odd frigate
# umbral prism on a quick glance: ```py # Updating seed_range ...

If I understood this correct, when going through a seed range, I check that range. If the range is 1) to the left, I cut it off and add it back to be processed in the next section, 2) same process. Then in the end, and that is the part you shared, the curr_seed range will be inside of the section range, which is then considered done.

Maybe I am understanding the problem incorrectly

hallow wren
#

you do have to keep the ones outside as well. just separate

umbral prism
regal vapor
#

imagine if it's wrong after 2 hours lol

small sun
regal vapor
#

“Knock, knock.”
“Who’s there?”
very long pause….
“Doggo's solution.”

#

Works better IRL but you get the idea

odd frigate
#

oh my

#

read that too many times to get it

regal vapor
#

oh wrong doggo lol not you XD

odd frigate
#

ouch

umbral prism
odd frigate
#

ahh

oblique linden
# 
with open("05.txt", "r") as f:
    sections = f.read()[:-1].split("\n\n")


# Part 1
class RangeMapping:
    def __init__(self):
        self.func = {}

    def __getitem__(self, n: int) -> int:
        for k, v in self.func.items():
            if n in k:
                return v[n - k[-1] - 1]
        return n

    def get(self, n: range) -> list[range]:
        res = []
        for k, v in self.func.items():
            if n[-1] < k[0] or n[0] > k[-1]:
                continue
            elif k[0] <= n[0] <= k[-1] and n[-1] > k[-1]:
                res.append(range(v[n[0] - k[-1] - 1], v[-1] + 1))
                n = range(k[-1] + 1, n[-1] + 1)
            elif k[0] <= n[-1] <= k[-1] and n[0] < k[0]:
                res.append(range(v[0], v[n[-1] - k[-1] - 1] + 1))
                n = range(n[0], k[0])
            elif k[0] <= n[0] <= k[-1] and k[0] <= n[-1] <= k[-1]:
                res.append(range(v[n[0] - k[0]], v[n[-1] - k[-1] - 1] + 1))
                break
            elif n[0] < k[0] < k[1] < n[-1]:
                res.append(range(v[0], v[-1] + 1))
                res.extend(self.get(range(n[0], k[0])))
                res.extend(self.get(range(k[-1] + 1, n[-1])))
                break
        else:
            if not any(r[0] <= n[0] and r[-1] >= n[-1] for r in res):
                res.append(n)
        return res
# 
maps = [RangeMapping() for _ in range(len(sections) - 1)]
seeds = list(map(int, sections[0].split(": ")[1].split()))
for i, section in enumerate(sections[1:]):
    for line in section.splitlines()[1:]:
        end, start, step = map(int, line.split())
        maps[i].func.update({range(start, start + step): range(end, end + step)})

min_val = float("inf")
for seed in seeds:
    orig_seed = seed
    for m in maps:
        seed = m[seed]
    if seed < min_val:
        min_val = seed
print(min_val)

# Part 2
all_seeds = [
    [range(seeds[i], seeds[i] + seeds[i + 1])] for i in range(0, len(seeds), 2)
]
all_intervals = []
for interval in all_seeds:
    for m in maps:
        new_interval = []
        for i, part in enumerate(interval):
            new_interval.extend(m.get(part))
        interval = new_interval
    all_intervals.extend(interval)
print(min(all_intervals, key=lambda x: x[0])[0])
regal vapor
#

I do love a good old for-else

small sun
# small sun We will be waiting for

Have to leave work now, but ~2h, starting at ~5, puts me at about ~7pm, which with a ~30 minute drive home, puts me right on schedule
Also this car really gets great mileage

IMG_1944.jpg
#

_about to go open my CodeSpace on my phone to make sure that it doesn’t time out _

#

I have like literally one line left on my Rust rewrite
It already got the right answer for part 1
So I’ll have something that’s hopefully much faster if I do get the wrong answer

fresh oak
#

This is essentially what I ended up doing, took about 10 minutes to run

brittle ledge
#

nice variable, salt

image.png
umbral prism
small sun
#

Hey

#

I'm still waiting

#

Count your wins

#

I'm 99% sure my Rust version is ready, but I'm scared of running it and running out of RAM

small sun
#

I shipit'ed it

#

173 minutes into Python and 36 minutes into Rust

north marsh
brittle ledge
north marsh
#

thought about adding __add__ to Gaps that will shift the intervals, but so far Gaps only requires the types to support __lt__

regal vapor
small sun
#

I just want to have some answer before....

#

IT FINISHED

regal vapor
#

It finished?!

small sun
# 
@shenanigansd ➜ .../advent_of_code/2023/05/python (main) $ time python aoc_2023_05.py 
196167384
125742456

real    184m37.737s
user    175m54.507s
sys     0m13.278s
regal vapor
#

But is it correct

small sun
north marsh
#

is that brute forcing?

#

insane

regal vapor
small sun
north marsh
#

you could've written an interval set library in that time

small sun
regal vapor
#

It works and that’s all that matters

small sun
#

Now to see how long Rust BTW takes

north marsh
small sun
umbral prism
#

speedy!

small sun
# umbral prism speedy!

It was pointed out to me that I forgot --release
Sub 10 minutes now

@shenanigansd ➜ /workspaces/scratchpad (main) $ time cargo run --release --bin aoc-2023-05
   Compiling aoc-2023-05 v0.1.0 (/workspaces/scratchpad/events/advent_of_code/2023/05/rust)
    Finished release [optimized] target(s) in 1.00s
     Running `target/release/aoc-2023-05`
196167384
125742456

real    7m8.438s
user    7m1.666s
sys     0m0.543s
umbral prism
#

Now that's quite a difference!

tepid jetty
#

Final runtime was: 205 minutes for a full-brute force of part 2.

odd frigate
#

Eish 🙈😆

gusty olive
ember rivet
#

Could someone help me understand day 5 part 2? I've seen the youtube video but still don't really understand it

tepid jetty
ember rivet
# tepid jetty Anything in particular?

I can understand how you can see overlaps mostly, but what gets me is what happens if there are overlaps - the un-overlapped stuff gets mapped to itself

fierce harbor
# 
file = open("Day5text", "r")
text = [i.strip("\n") for i in file.readlines()]

seeds = text[0][7:]
seed2soil = text[3:8]
soil2fert = text[11:53]
fert2water = text[56:94]
water2light = text[97:143]
light2temp = text[146:172]
temp2humid = text[175:182]
humid2loc = text[185:200]

loclist = []

print(seeds)


def dataConversion(input, listofrows):
    input = int(input)
    desranges = []
    souranges = []
    diff = -1
    for row in listofrows:
        row = row.strip().split()
        desstart = int(row[0])
        soustart = int(row[1])
        rangl = int(row[2])
        desranges.append((desstart, desstart + rangl - 1))
        souranges.append((soustart, soustart + rangl - 1))
    for i in range(len(souranges)):
        if input >= souranges[i][0] and input <= souranges[i][1]:
            diff = souranges[i][1] - input
        if diff != -1:
            return desranges[i][1] - diff

    return input

for seed in seeds.split():
    soil = dataConversion(seed, seed2soil)
    print(soil)
    fert = dataConversion(soil, soil2fert)
    water = dataConversion(fert, fert2water)
    light = dataConversion(water, water2light)
    temp = dataConversion(light, light2temp)
    humid = dataConversion(temp, temp2humid)
    loc = dataConversion(humid, humid2loc)
    loclist.append(loc)

print(min(loclist))
#

why doesnt this work?

brittle ledge
north marsh
brittle ledge
north marsh
#

i mean, i wrote it

#

!pypi mind_the_gaps

celest coveBOT
brittle ledge
#

yeah okay xD

#

i thought it was from someone else

#

when you said "it's a interval set library"

#

but that's pretty cool

north marsh
# 
>>> from mind_the_gaps import *
>>> a = Gaps([0 <= x, x < 1, 5 <= x, x < 6])
>>> b = Gaps([.5 < x, x <=7])
>>> print(a, b, a | b, a - b)
{[0, 1), [5, 6)} {(0.5, 7]} {[0, 7]} {[0, 0.5]}

does this basically, but the numbers can be, like, datetimes are whatever

brittle ledge
#

i was about to say why not 0 <= x < 1 before i realized x is your dark magic xD

north marsh
#

yeah, previous version of the library did have 0 <= x < 1, but it required some hacks with operator chaining, and it was easy to quietly user error

brittle ledge
#

oh so you can do it :O

#

but probably really hacky yeah

north marsh
#

a closed interval can be made easily though

>>> print(Gaps([1, 2, 3, 4, 5, 6]))
{[1, 2], [3, 4], [5, 6]}
brittle ledge
#

awesome

#

i'm guessing you didn't even have to chunk the seeds input

#

because your constructor does it automatically?

#

as in, it already recognizes groups of 2

north marsh
#

yeah, it takes a list of endpoints instead of a list of intervals

#

can also construct from string:

>>> print(Gaps.from_string("{(-inf, 0], [1, inf)}"))
{(-inf, 0], [1, inf)}

but that only works for ints and floats

brittle ledge
#

pretty cool

#

the code for var.py is so clean

#

i'll check out the rest too sometime

north marsh
#

the line sweep algorithm is cool, i use a version of it in rects too

brittle ledge
#

oh i've heard that term thrown around here and there

#

never dug into it though

#

some geometry algorithm?

north marsh
#

yeah, it's a geometric algorithm

livid current
#

I got Day 5 Part 1! Hoo-ray!

#

now for me to try to understand the part 2

#

looks like I"ll just brute force the second part 😦

regal vapor
livid current
regal vapor
#

Right - that’s how I did it too

#

It can be a bit fiddle-y to code up though

#

I needed tests as a leading light to get me to the right answer

livid current
regal vapor
#

you can brute force today but depending on how you implement it you could wait a while

livid current
#

ok, i think i got a idea now. but, i think i'll try that tomorrow

wide tide
#

i've spent the past hour trying to re-wrap my head around how to do this "properly", but i feel like i may just be making an even further-complicated solution than necessary 😩

#

even the simple goal of "flatten two consecutive maps into a list of parallel maps" seems harder than it should be

#

i may give that reverse-map approach a go at some point instead, which is still rather bruteforcey but allegedly a bit less so

regal vapor
livid current
#

I drawn schematics to do this too

wide tide
#

though that is now making me realise that doesn't solve the real issue of having to check every value in the given ranges of seeds...

regal vapor
wide tide
#

i think the actual optimisation idea clicked for me (allowing the map rules to be applied to entire ranges of numbers, rather than just individual ones) :P

regal vapor
#

For one person on here their solution was hours

livid current
#

closer now, but now I'm in a infinite loop issue with the optimized solution for part 2 😦

regal vapor
#

Debugging/unit testing time

livid current
#

well, I think I fixed it!

#

i'm not sure if this is correct, but it appears there are 128 intersections+non-intersections

#

ok, it's not correct. something, somewhere, something went wrong.

livid current
#

looks like i'm going to solve day 5 part 2 soon. what went wrong with me reading my drawings of intersection wrong

#

Fixed it and now it works!

image.png
livid current
#

@royal ocean here's the solution: that's going to be really hard to explain, but in my code that I give. I pop the last range on the available list of ranges and treat it as the auxiliary ranges. Then it involves a loop to check whether the auxiliary range overlap with the current map range. The rest involves checking how they intersect, and split the ranges into 2 or 3 sections, or even move on to the other map without split, and when there is no more map to check for that range, I move it into the list of range that has been checked. I posted my code though it'll be a while to understand, but like @elder oar it involves interval arithmetic.

royal ocean
#

Okay cool

#

Ah okay ur also checking ranges right?

#

I was thinking of a DSU sol at first for part 2 but ranges came out to be better sol 🤔

livid current
# royal ocean Okay cool

yeah. you should draw lines. call the top line auxiliary range. call the bottom line the source range. Have small lines as ending of line. And then you can see how to split them or even if splitting them is necessary

royal ocean
#

My range split logic was somewhat wrong ig

#

cuz my optimal sol never worked for that one

#

did u also took 4 cases?

livid current
#

there's 6 cases

#

7 actually

elder oar
#

Here's mine lol

#

??? isn't there a bot for this

# 
def intersect_ranges(ranges: builtins.list[builtins.range], map: Table):
    out_ranges: builtins.list[builtins.range] = []
    for range in ranges:
        splits = [range]
        for src, dest, len in map.ranges:
            next_splits = []
            for split in splits:
                if split.start < src and split.stop < src:
                    next_splits.append(split)
                elif split.start < src and split.stop < src + len:
                    next_splits.append(builtins.range(split.start, src))
                    out_ranges.append(builtins.range(dest, split.stop - src + dest))
                elif split.start < src and split.stop >= src + len:
                    next_splits.append(builtins.range(split.start, src))
                    out_ranges.append(builtins.range(dest, dest + len))
                    next_splits.append(builtins.range(src + len, split.stop))
                elif split.start < src + len and split.stop < src + len:
                    out_ranges.append(
                        builtins.range(
                            split.start - src + dest, split.stop - src + dest
                        )
                    )
                elif split.start < src + len and split.stop >= src + len:
                    out_ranges.append(
                        builtins.range(split.start - src + dest, dest + len)
                    )
                    next_splits.append(builtins.range(src + len, split.stop))
                else:
                    next_splits.append(split)
            splits = next_splits
        out_ranges.extend(splits)
    return simplify_ranges(out_ranges)
#

(complicated)

#

here's my new one, with the interval arithmetic I added to my aoc library

def intersect_ranges(ranges: multirange, map: Table):
    out = multirange()
    for range, offset in map.ranges:
        intersection = range & ranges
        if intersection:
            out |= intersection + offset
            ranges -= intersection
    return out
royal ocean
#

Made library function wow 🛐

elder oar
#

I mean I was already overloading range (to add the fluent methods from my iter overload to it), might as well also add interval arithmetic

#

¯_(ツ)_/¯

royal ocean
livid current
royal ocean
#

|-------------------------|
|--------------------|

|-----------------------|
|--------------------|

              |-----------------------|

|-----------------------------|

|---------------------------------|
|-----------------------|

#

What other cases am I missing?

elder oar
#

|-----| |-----|

royal ocean
elder oar
#

(it's still a case)

royal ocean
#

I push the same range to next map

royal ocean
livid current
#

almost there

royal ocean
#

so total 5 right?

livid current
#

just gotta find my phone to take a picture

elder oar
#

My solution has

1
|---|
      |---|

2
|-----|
    |-----|

3
|---------|
    |-|

4
    |-|
|---------|

5
    |-----|
|-----|

6
      |---|
|---|
#

Not sure what the 7th is

livid current
#

Top is Auxiliary Range. Bottom is Source Range

elder oar
#

Aren't cases 3 and 4 equivalent?

livid current
#

You split them in different way, so no, they're not the same

elder oar
#

I mean, I didn't

royal ocean
#

I will rewrite day 5 part 2 today after today's advent

elder oar
#

Oh wait I think it's just that you wrote case 4 upside-down lol

royal ocean
#

GLHF guys for today's advent : )

elder oar
#

GLHF

livid current
#

@royal ocean I guess this helps?

royal ocean
#

so Imma implement the sol again today

#

once I get done with that can I ping you?

livid current
#

sure

royal ocean
#

Thanks : )

trim turret
#

!pypi aoc

celest coveBOT
elder oar
#

Lol

livid current
vivid lake
#

!pip aoc-lube

celest coveBOT
elder oar
#

'aoc-glue' lmao

#

That's like, the opposite of aoc-lube

clever geode
#

.bookmark

clever geode
#

.bookmark

clever geode
#

Im kinda stuck on solving part 2, if i have found my intersection in my source and destination row what do i do next?

livid current
clever geode
#

I was looking at this and my code has identical results until there start to appear mutliple ranges, i dont understand how those mutliple ranges form

livid current
clever geode
#

Atleast in that example

#

And then just add the shift?

#

Or what does modifying mean exactly in this case

livid current
clever geode
cedar oasis
# 
for pair in seed_pairs:
    for seed in range(pair[0], pair[0] + pair[1]):
        for current_map in maps_data:
            for i in range(len(current_map)):
                destination_range = current_map[i][0]
                source_range = current_map[i][1]
                range_length = current_map[i][2]

                if seed in range(source_range, source_range + range_length + 1):
                    seed = (seed - (source_range - destination_range))
                    break 
            

        final_seeds.append(seed)
#

i know im brute forceing it

#

but what would be an effcient method

#

using a set?

elder oar
cedar oasis
#

yes

elder oar
#

Interval arithmetic

#

You essentially want to be doing all your operations on ranges of values, rather than individual ones

cedar oasis
#

be warned the brute force method took me all day to get so

#

i aint that smart

elder oar
#

So possible seeds = (0..=4000), map (1000..2000) => (0..1000) => possible soils = (0..1000) or (2000..=4000)

cedar oasis
#

hmmm

#

i legitmately have no clue how to implement that but i shall. try

clever geode
#

after like 3 days i finally understand whats going on here

#

now i can finally finish this when im back from vacation

#

and then solve the other like 10 days i missed

clever geode
#

.bookmark

clever geode
#

LETS GOOOOOOO

image.png
arctic zodiac
#

nice

regal vapor
#

Very nice! Day 5 isn't easy - completing it is pretty good :)

clever geode
#

Thanks

#

Only had to rewrite 5 times lol

#

Technically i still have a bug since i didnt think of ranges being non-inclusive but it worked to i am to lazy to fix it now