Unable to load image

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
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.

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.

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.

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.

Link copied to clipboard
Action successful!
Error, please refresh the page and try again.