Unable to load image
/h/slackernews House Femboy Founder
@L's profile picture @L's hat
L ong/Nose :marseylongpost: Serial Serious Replyer :marseylongpost:  7mo ago (text post) 574 thread views #227358

rDrama Advent of Code Day 8: RegEx Bootcamp Edition

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)

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

No email address required.

>"I know a magical language that lets me talk to computers. I use it to compulsively solve problems for elves at 3 o'clock in the morning."

:#marseymeds:

Jump in the discussion.

No email address required.

Me when

:#marseycommitted:

Me when I tell the hospital staff that the scribbles I smeared in feces on my cell wall , [ ->+< ] > [ - < + > ] are actually a language that lets you talk to computers and have them do stuff for you

Jump in the discussion.

No email address required.

Nice trick, making the second number much larger to confuse brute-forcers. Totally didn't work on me :marseysulk:

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

Mainly showing off two things: passing functions to other functions, and the collect macro, which can turn an iterable into a seq, set, or table.

Jump in the discussion.

No email address required.

What language is this?

Jump in the discussion.

No email address required.

Nim: https://nim-lang.org

Jump in the discussion.

No email address required.

The 20 lines chad vs the 80 lines virgin :chuditsover:

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

Jump in the discussion.

No email address required.

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

kek

Jump in the discussion.

No email address required.

Never even began for sheepshaggers

Jump in the discussion.

No email address required.

Took me a second to realize what to do. Fun puzzle!

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

Jump in the discussion.

No email address required.

tfw I'm running Python 3.8 and so don't have math.lcm

Jump in the discussion.

No email address required.

Yeah, it's all fun and games if you try to run LCM in a browser with six 5 digit integer values :marseysuicide:

Also, it's REALLY fun if you forget that you started your cycle count at zero instead of one, so all your values are off by 1. What do you mean 1.40657e24 is too high, AOC?

Jump in the discussion.

No email address required.

That's nice! Makes me want to learn python properly

Jump in the discussion.

No email address required.

just finished this one, and man it sucked donkey balls. The answer was kind of BS in my opinion, but I guess I deserved it for never closely examining the real data. I mean I was scratching my head trying to figure out how to do this checking with loops. I thought that there may be cycles that had multiple Z values in it, and cycles the double back thru the same value (just on the other side) or on the same side but at a different point in the instruction set

I wrote an algorithm that I thought was decently fast. I had an index value of 0, I plugged it into the first cycle to determine what step it corresponded with. Then I went through the other cycles and checked if I could get an integer number of steps. But this algorithm too just hung and hung. Well turns out that the real answer was in the motherfricking TRILLIONS of steps. What in the goddarn.

Anyways paging !codecels: is there a general algorithm for this problem, where

  • A cycle may have multiple Zs

  • The Z is not necessarily at (or near) the end of the cycle?

Feel free to call me an idiot, I proudly represent all r-slurs

Jump in the discussion.

No email address required.

Yes, but rather than do that I opted to just use Mathematica's FindInstance (I get Mathematica for free through my university). Turns out there's no offset here anyways and you can just use the LCM, and when I measured my indexes I had an off-by-one error and was left scratching my head bc everything made sense but it was saying my answer was wrong :/

Jump in the discussion.

No email address required.

:#marsey57:

Jump in the discussion.

No email address required.

if the data is already so contrived to be applicable to some non-universal math shit you forgot in the second year of udnergrad we should be allowed to try and guess all the number combinations for the correct solution and by guessing i mean of course just entering all the numbers from 1 to something blatantly high into the solution window just like i guessed the chinese slit-eye theorem correctly in the exam back in my undergrad studies frickign r-slurred advnt of codecels throw in a proof and watch the number of solutions decrease to 50 (all done by math nerds)

Jump in the discussion.

No email address required.

This, 100% this

Jump in the discussion.

No email address required.

The general problem is a system of linear congruences, i.e. solve for x when ax≡b mod m. Complicated by the fact you don't have to solve for every congruence, but just one congruence per cycle (in fact it's impossible by definition to solve for two distinct Z's in the same cycle, otherwise they'd be in the same place), and there's no way of knowing which combination is solvable (i.e. which Z's make up the first intercept).

The trick is to realise the general case is hard, the lcm case is easy, and there are simple tests you can do to prove the lcm is the solution.

Jump in the discussion.

No email address required.

Yeah you went through the exact same process I did until everyone here started saying "oh its just like that lol" and while I'm not satisfied with that I guess I accept it

Jump in the discussion.

No email address required.

trillions is peanuts for a computer. rewrite the problem as matrix multiplication, precompute a few million iterations by taking the matrix exponent, then run that fricker on a gpu. it would clean up in no time.

Jump in the discussion.

No email address required.

So...many...lines... I hate mathsstrags and their paint-by-numbers tricks

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

Jump in the discussion.

No email address required.

Part 2. Python is great

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

Jump in the discussion.

No email address required.

>still outside the top 5

:#marseyrain:

⎕PP←20
D←≢d←⊃r←⊃⎕NGET'8.in'1
k l r←↓⍉↑(∊∘⎕A⊆⊢)¨2↓r ⋄ lr←l,⍥⊂¨r
i←1 ⋄ s←0
x←{j←⍸k∊⊂⍵ ⋄ q←1+'R'=i⊃d ⋄ i⊢←1+D|i ⋄ q⊃j⊃lr}
x⍣{s⊢←s+1 ⋄ ⍺≡'ZZZ'}⊢'AAA'
⎕←s
⎕←^/{i←1 ⋄ s←0 ⋄ _←x⍣{s⊢←s+1 ⋄ 'Z'≡3⊃⍺}⊢⍵ ⋄ s}¨k⌷⍨⊂⍸∊'A'=¯1↑¨k
Jump in the discussion.

No email address required.

The leaderboard is pretty impressive %age wise, wonder when it drops off

Jump in the discussion.

No email address required.

Last year the largest drop-offs were after days 11 and 15

Jump in the discussion.

No email address required.

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

@everyone the leadboard doesn't rank you :marseyhmm:

Jump in the discussion.

No email address required.

I split the 16th place with someone and there's no 17th because of that.

Jump in the discussion.

No email address required.

:#marseywhirlyhatpat:

yeah I'm r-slured

Jump in the discussion.

No email address required.

I feel like you are pretty fricked if you don't pick up on the trick to this one. Otherwise, easy https://i.rdrama.net/images/17020146594500475.webp

Jump in the discussion.

No email address required.

Easy and fun

I wonder how long it takes without using lcm

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

Jump in the discussion.

No email address required.

I considered doing this but I didn't think it would work because there's multiple results ending in Z.

Is there only one possible Z ending per value? How do you guarantee periodicity?

Jump in the discussion.

No email address required.

I ran the loops on real data and checked that they all are multiples of the command sequence length. They are all prime numbers (multiplied by that) too, by the way.

Looking at the data, and not even with a naked eye, is an integral part of some of the AoC puzzles.

Jump in the discussion.

No email address required.

In this case it seems less like looking at the data and more like intuitively guessing "what might they have done?" and checking if your hunch was right.

Makes sense though, I'll have to try to be a little more wary of that going forwards and just listen to my intuition

Jump in the discussion.

No email address required.

In this case it seems less like looking at the data and more like intuitively guessing "what might they have done?" and checking if your hunch was right.

I'd call it a confirmed educated guess. It's not like I assumed that there would be no Z's in the middle of each full cycle and proceeded to implement the full algorithm and checked if the final answer is correct. I actually printed out the cycle lengths divided by the command sequence length first. They were cleanly divisible resulting in prime numbers.

Jump in the discussion.

No email address required.

Well I'm disappointed, my solution doesn't assume complete loops, which makes things a lot more complicated.

Jump in the discussion.

No email address required.

Consider each starting point Sn. Let Sn(k) be the kth successor of Sn following the directions. (Whichever node you are on after following k many directions)

Assuming the problem has a solution all Sn have an m such that Sn(m) = ZZZ. Call it Xn.

If for some An only one succesor = ZZZ thn trivially the answer is Xn. Otherwise there must be a cycle in the succesors of An starting at the Xnth succesor (the succesor that equals ZZZ). Let the length of this cycle be Cn.

If a solution exists it is of the form Xn + Cn * k where k is some positive integer. (These are the only points the succesors of An = ZZZ). Rephrase this as SOLUTION = Xn mod Cn. Im fudging this a bit since Xn can be greater than Cn but that can be repaired later.

We have one of these modulus equations for each starting point. SOLUTION = X1 mod C1 = X2 mod C2....... this equation is solvable with Chinese Remainder Theorum.

In this case the data is aranged such that the CR solution reduces into finding an LCM.

Wait, the succesors can pass through ZZZ multiple times per cycle frick

Jump in the discussion.

No email address required.

Feed in each A-value, then feed back in each resulting Z-value:

11567  XCZ
19637  CFZ
15871  SFZ
21251  PPZ
12643  ZZZ
19099  TQZ

11567  XCZ
19637  CFZ
15871  SFZ
21251  PPZ
12643  ZZZ
19099  TQZ

This guarantees strongly suggests the loops are simple and the lcm is the solution. If any Z-value found a different Z-value, or had a different number of steps, you'd be dealing with linear congruences, but that's too much of a pain in the ass for day 8.

If you want to prove the loops are simple, check that every loop length is a multiple of the LRLRLRLLR sequence length. But that's way too much formality for AoC, you've gotta go with your intuition.

Jump in the discussion.

No email address required.

You can't guarantee it in general, but the guy who writes the problems tailored all the inputs to go around in circles. All the periods in my input were between 10 and 20 thousand and always arrived at the same endpoint. It was clearly very intentional, like I think he imagined people would try to brute force it (which seriously doesn't work unless you want to wait for a very long time) then they would have to put some debug output statements in their loop, which is how I eventually figured out what the heck was going on.

Jump in the discussion.

No email address required.

It would take 21,003,205,388,413 loops.

Jump in the discussion.

No email address required.

I let it run for like 5 minutes at one point. It wasn't even close to being done. I think it might take a couple hours.

Jump in the discussion.

No email address required.

The Z positions and loop-back points all being conveniently consistent with the size of the total number of steps for each made this one a lot less hard than it could've been

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

Jump in the discussion.

No email address required.

Yeah, some of us did a fair bit of extra work by assuming that wouldn't be the case.

Jump in the discussion.

No email address required.

Classic Eric, LCM even though there's no guarantee that LCM should give the right answer.

Jump in the discussion.

No email address required.

>does every Z lead back to itself? yes

>does every ZZ loop have the same length as the AZ loop? yes

>is every loop length a multiple of the LR length? yes

There's your guarantee.

Jump in the discussion.

No email address required.

:#marseychristmaself:

Snapshots:

https://carbon.vercel.app:

https://adventofcode.com/2023:

Jump in the discussion.

No email address required.

Regex makes me feel :marseyschizoshaking:

Jump in the discussion.

No email address required.

FYI I'm picking the least voted-for option each day just to make your life a little worse :#marseydealwithit:

Jump in the discussion.

No email address required.

Top Poster of the Day:
J
Current Registered Users: 26,836
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 non-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:

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 real them at least once a month. We also reserve the right to ignore enforcement of the guidelines at the discretion of the janitorial staff. Be funny, or at least compelling, and pretty much anything legal is welcome provided it's on-topic, and even then.

[[[ 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 LOG /h/slackernews MODS /h/slackernews EXILEES /h/slackernews FOLLOWERS /h/slackernews BLOCKERS
Live commit: 441c078
Link copied to clipboard
Action successful!
Error, please refresh the page and try again.