Unable to load image
/h/slackernews House Femboy Founder
L ong/Nose :marseylongpost: Serial Serious Replyer :marseylongpost:  11mo ago (text post) 341 thread views #226594

rDrama Advent of Code Day 5 - Brute Force Edition

Summary for those just joining us:

Advent of Code is an annual Christmas themed coding challenge that runs from December 1st until christmas. Each day the coding problems get progressively harder. We have a leaderboard and pretty good turnout, so feel free to hop in at any time and show your stuff!

Whether you have a single line monstrosity or a beautiful phone book sized stack of OOP code, you can export it in a nice little image for sharing at https://carbon.vercel.app

What did you think about today's problem?

https://adventofcode.com/2023

Our Code is 2416137-393b284c (No need to share your profile, you have the option to join anonymously if you don't want us to see your github)

15
New Old Top Bottom Controversial Random
Jump in the discussion.

No email address required.

Doing a lookup for every integer was a mistake.

https://i.rdrama.net/images/17017560077125912.webp

Jump in the discussion.

No email address required.

If you're going to brute force it you should at least do them one at a time instead of populating the whole list first lmao

Jump in the discussion.

No email address required.

:ma#rseyscared:

Jump in the discussion.

No email address required.

That's why when you suspect that the orgs finna frick with you, you download the task data first. But on the other hand it seems to fit in 32bit ints, so like 32gb of memory should be enough.

Jump in the discussion.

No email address required.

advent of absolutely frick my shit up and make me feel r-slurred

https://i.rdrama.net/images/17017562091121497.webp

Jump in the discussion.

No email address required.

finally had a drink and i cant even be fricked to read this :#marseylongpost: shit. this year is going to be fricking miserable.

Jump in the discussion.

No email address required.

Hold onto your hats boys I'm doing multithreading for each range

Jump in the discussion.

No email address required.

Brute force method ended up resolving before I finished writing a more clever range splitting version. :marseypaperbag:

Jump in the discussion.

No email address required.

Who is the mysterious anonymous user #371225?

Finally, a task that rewards a meticulous programmer. Nothing particularly complicated, just be careful, think a little bit ahead, write maintainable (for the next 10 minutes) code. The important parts:

   def intersect_range(x, xlen, y, ylen):
       r = max(x, y)
       rend = min(x + xlen, y + ylen)
       if rend <= r:
           return None, None
       return r, rend - r

   def mapstep2(x, xlen, curmap):
       ranges = []
       srcranges = []
       for dest, src, rlen in curmap:
           r, rlen = intersect_range(x, xlen, src, rlen)
           if r is None: continue
           srcranges.append((r, rlen))
           ranges.append((dest + r - src, rlen))

       curx = x
       for r, rlen in sorted(srcranges):
           if r - curx > 0:
               ranges.append((curx, r - curx))
           curx = r + rlen
       if curx < x + xlen:
           ranges.append((curx, x + xlen - curx))

       return ranges
Jump in the discussion.

No email address required.

why do they make this shit as inscrutable as possible

Jump in the discussion.

No email address required.

I got tripped up that they did [target, source, range], these anti-AI measures suck.

Jump in the discussion.

No email address required.

To Dunk on ESLs

Jump in the discussion.

No email address required.

>tfw bug in real data but not in test data

:#marseyraging:

I ended up brute forcing a search for seed values that would cause a bug on the test data. Turns out that I forgot that ranges could completely encapsulate each other. :marseyfacepalm:

Jump in the discussion.

No email address required.

Yep I have a special case up the top because I forgot that entirely

Jump in the discussion.

No email address required.

https://i.rdrama.net/images/17017688085470061.webp

Runs in an amazing 147 seconds.

Jump in the discussion.

No email address required.

Brute force indeed. Let's parallelize it:

https://i.rdrama.net/images/17018083474940205.webp

This brings the runtime down from 5 minutes to 1 on my machine. Not bad.

@SleighOut

Jump in the discussion.

No email address required.

Virgin actually solving the problem vs chad seeing the lowest number with it's inverse in a range

f = open('AOC2023Day5.txt')
import numpy as np
from collections import defaultdict
blocks = f.read().strip().split('\n\n')
seeds = [int(i) for i in blocks[0].split(':')[-1].split()]
blocks = blocks[1:]
def inverse(x,block):
   lines = block.split('\n')[1:]
   for line in lines:
       line = [int(i) for i in line.split()]
       if x-line[0] >= 0 and x-line[0]<line[2]:
           x += line[1]-line[0]
           return x
   return x
def forward(x,block):
   lines = block.split('\n')[1:]
   for line in lines:
       line = [int(i) for i in line.split()]
       if x-line[1] >= 0 and x-line[1]<line[2]:
           x += line[0]-line[1]
           return x
   return x
def val(x,blocks):
   for block in blocks:
       x = forward(x,block)
   return x
def inval(x,blocks):
   rblock = blocks.copy()
   rblock.reverse()
   for block in rblock:
       x = inverse(x,block)
   return x
def in_seeds(s,seeds):
   for i in range(int(len(seeds)/2)):
       if s-seeds[2*i] >= 0 and s-seeds[2*i] < seeds[2*i+1]:
           return True
   return False
i = 60500000
while True:
   if i % 10000 == 0:
       print(i)
   v = inval(i,blocks)
   if in_seeds(v,seeds):
       print(i)
       break
   i += 1
Jump in the discussion.

No email address required.

I was so close to switching to a real maths library.

Jump in the discussion.

No email address required.

Babby's first intersecting lines algorithm (takes ~1 second on my machine)

Even so, this one is pretty tough for just day 5.

https://i.rdrama.net/images/17018172842831237.webp

Jump in the discussion.

No email address required.

https://i.rdrama.net/images/17018242890064752.webp

cniles on suicide watch

Jump in the discussion.

No email address required.

My code is definitely not pretty, but :marseywtf2: at those brute forcing solutions

https://i.imgur.com/4xT2HHS.png

Jump in the discussion.

No email address required.

This was awful, mostly my own fault, but I got my tricky version working. I know I could save a few iterations with less recursive calls and I flip-flopped between (base, size) and (min, max) a few times to try catch broken logic, but I'm not cleaning it up so you get to see all my shameful debugging and stanky code.

https://i.rdrama.net/images/170181453706392.webp

Jump in the discussion.

No email address required.

my solution is as :marseybrainlet: as it comes because I don't know how to not bruteforce it and I'm too exhausted to figure out the proper way.

I noticed there was going to be a problem once I looked at the actual input file and realised just how big an array would be (no problem, iterator).

https://i.rdrama.net/images/17018097518537776.webp

Jump in the discussion.

No email address required.

Luckily I had some old code lying around for range overlaps.

r←⍎¨¨¨(≢¨⊆⊢)(∊∘⎕D⊆⊢)¨⊃⎕NGET'i5.txt'1 ⋄ e←⊃⊃r ⋄ p←1↓r
t←{d s r←⍵ ⋄ s,(1-⍨s+r),d-s}¨¨p
m1←{a b d←⍺ ⋄ (⍵≥a)∧(⍵≤b):⍵+d ⋄ ⍵}
m2←{(m,⍵)⌷⍨1⍳⍨⍵≠m←m1∘⍵¨⍺}
m3←{i←0 ⋄ {i⊢←1+i ⋄ (i⊃t)∘m2¨⍵}⍣7⊢⍵}
⎕←⌊/m3 e

e←0 ¯1∘+¨+\¨e⊆⍨(≢e)⍴2 1
ov←{((1⊃⍺)≤2⊃⍵)∧(1⊃⍵)≤2⊃⍺}
sp←{~⍺ ov ⍵:⊂⍵ ⋄ a b c d←∊⍺ ⍵ ⋄ a←a⌈c ⋄ b←b⌊d
    (≤/¨⊢⍤/⊢)(c(a-1))(a b)((b+1)d)}
n1←{⊃,/(2↑⍺)∘{⍺ sp ⍵}¨⍵}
n2←{s←⍵ ⋄ o←⍬ ⋄ _←{m←(2↑⍵)∘ov¨j←⍵ n1 s
    o⊢←((3⊃⍵)+m/j),o ⋄ s⊢←(~m)/j ⋄ 0}¨⍺ ⋄ s,o}
n3←{i←0 ⋄ {i⊢←1+i ⋄ (i⊃t) n2 ⍵}⍣7⊢⍵}
⎕←⌊/∊1∘↑¨er e
Jump in the discussion.

No email address required.

Part 2 was a bit of a b-word, largely because I'm tired and didn't want to put the effort in. RIP anyone trying to brute force that without any optimisation.

Jump in the discussion.

No email address required.

These range operations put me in a bad mood for the rest of the day.

Jump in the discussion.

No email address required.

Brute forced it in python :marseycringe:. Took 2 hours and five minutes.

https://i.rdrama.net/images/1701823913417992.webp

Jump in the discussion.

No email address required.

Part 2 kicked my butt. Spent hours trying to be clever and finally just brute forced it. :marseywhirlyhat:

Jump in the discussion.

No email address required.

I managed to get a fast recursive solution working https://i.rdrama.net/images/17017848809300568.webp

Jump in the discussion.

No email address required.

Finally came up with something decent for part 2. Runs in 5ms

https://i.rdrama.net/images/17018384248572803.webp

Jump in the discussion.

No email address required.

darn this one is really hard for me lol i don't think I'm gonna finish before the next puzzle comes out

Jump in the discussion.

No email address required.

:#marseygiftboxmarsey:

Snapshots:

https://carbon.vercel.app:

https://adventofcode.com/2023:

Jump in the discussion.

No email address required.

Top Poster of the Day:
Thirtythirst4sissies
Current Registered Users: 28,712
sidebar image

tech/science swag. :marscientist:

Effortposts made by SN Chads

Guidelines:

What to Submit

On-Topic: Anything that good slackers would find interesting. That includes more than /g/ memes and slacking off. If you had to reduce it to a sentence, the answer might be: anything that gratifies one's intellectual laziness.

Off-Topic: Most stories about politics, or crime, or sports, unless they're evidence of some interesting new phenomenon. Videos of pratfalls or disasters, or cute animal pictures. If they'd cover it on TV news, it's probably lame.

Help keep this hole healthy by keeping drama and NOT drama balanced. If you see too much drama, post something that isn't dramatic. If there isn't enough drama and this hole has become too boring, POST DRAMA!

In Submissions

Please do things to make titles stand out, like using uppercase or exclamation points, or saying how great an article is. It should be explicit in submitting something that you think it's important.

Please don't submit the original source. If the article is behind a paywall, just post the text. If a video is behind a paywall, post a magnet link. Fuck journos.

Please don't ruin the hole with chudposts. It isn't funny and doesn't belong here. THEY WILL BE MOVED TO /H/CHUDRAMA

If the title includes the name of the site, please leave that in, because our users are too stupid to know the difference between a url and a search query.

If you submit a video or pdf, please don't warn us by appending [video] or [pdf] to the title. That would be r-slurred. We're not using text-based browsers. We know what videos and pdfs are.

Make sure the title contains a gratuitous number or number + adjective. Good clickbait titles are like "Top 10 Ways to do X" or "Don't do these 4 things if you want X"

Otherwise editorialize. Please don't use the original title, unless it is gay or r-slurred, or you're shits all fucked up.

If you're going to post old news (at least 1 year old), please flair it so we can mock you for living under a rock, or don't and we'll mock you anyway.

Please don't post on SN to ask or tell us something. Send it to [email protected] instead.

If your post doesn't get enough traction, try to delete and repost it.

Please don't use SN primarily for promotion. It's ok to post your own stuff occasionally, but the primary use of the site should be for curiosity. If you want to astroturf or advertise, post on news.ycombinator.com instead.

Please solicit upvotes, comments, and submissions. Users are stupid and need to reminded to vote and interact. Thanks for the gold, kind stranger, upvotes to the left.

In Comments

Be snarky. Don't be kind. Have fun banter; don't be a dork. Please don't use big words like "fulminate". Please sneed at the rest of the community.

Comments should get more enlightened and centrist, not less, as a topic gets more divisive.

If disagreeing, please reply to the argument and call them names. "1 + 1 is 2, not 3" can be improved to "1 + 1 is 3, not 2, mathfaggot"

Please respond to the weakest plausible strawman of what someone says, not a stronger one that's harder to make fun of. Assume that they are bad faith actors.

Eschew jailbait. Paedophiles will be thrown in a wood chipper, as pertained by sitewide rules.

Please post shallow dismissals, especially of other people's work. All press is good press.

Please use Slacker News for political or ideological battle. It tramples weak ideologies.

Please comment on whether someone read an article. If you don't read the article, you are a cute twink.

Please pick the most provocative thing in an article or post to complain about in the thread. Don't nitpick stupid crap.

Please don't be an unfunny chud. Nobody cares about your opinion of X Unrelated Topic in Y Unrelated Thread. If you're the type of loser that belongs on /h/chudrama, we may exile you.

Sockpuppet accounts are encouraged, but please don't farm dramakarma.

Please use uppercase for emphasis.

Please post deranged conspiracy theories about astroturfing, shilling, bots, brigading, foreign agents and the like. It degrades discussion and is usually mistaken. If you're worried about abuse, email [email protected] and dang will add you to their spam list.

Please don't complain that a submission is inappropriate. If a story is spam or off-topic, report it and our moderators will probably do nothing about it. Feed egregious comments by replying instead of flagging them like a pussy. Remember: If you flag, you're a cute twink.

Please don't complain about tangential annoyances—things like article or website formats, name collisions, or back-button breakage. That's too boring, even for HN users.

Please seethe about how your posts don't get enough upvotes.

Please don't post comments saying that rdrama is turning into ruqqus. It's a nazi dogwhistle, as old as the hills.

Miscellaneous:

The quality of posts is extremely important to this community. Contributors are encouraged to provide high-quality or funny effortposts and informative or entertaining comments. Please refrain from posting the following:

  • Boring wingcucked nonsense nobody cares about that belongs in chudrama

  • Normie shit everyone already knows about

  • Anything that doesn't gratifify one's intellectual laziness

  • Bimothy-tier posts

  • Anything that the jannies don't like

We reserve the right to exile you for whatever reason we want, even for no reason at all! We also reserve the right to change the guidelines at any time, so be sure to read them at least once a month. We also reserve the right to ignore enforcement of the guidelines at the discretion of the janitorial staff. This hole is a janny playground, participation implies enthusiastic consent to being janny abused by unstable alcoholic bullies and loser nerds who have nothing better to do than banning you for any reason or no reason whatsoever.

[[[ To any NSA and FBI agents reading my email: please consider ]]]

[[[ whether defending the US Constitution against all enemies, ]]]

[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

https://i.rdrama.net/images/1663436125937968.webp

BROWSE EFFORTPOSTS SITE GUIDE DIRECTORY Emojis & Art | Info Megathreads HOLES PING GROUPS
/h/slackernews SETTINGS /h/slackernews LOG /h/slackernews MODS /h/slackernews EXILEES /h/slackernews FOLLOWERS /h/slackernews BLOCKERS
Current software version: c889144
Link copied to clipboard
Action successful!
Error, please refresh the page and try again.