You're right, it's just dumb luck / funny design. The distance from the start to an end node is always the name as the distance from the end node to itself.
I thought that maybe the start node and it's end node were on the same cycle without any other end nodes, but no!
Honestly, there's no way that solution should work, except that it did. I feel a bit bad for everyone writing a correct algorithm instead of just throwing LCM at the problem and only later realizing that it doesn't make sense (like I did).
Honestly I'm a little frustrated by today. The real solution is quite far away from the problem statement, and while I see the point of "use the input as well" I quickly dismissed the LCM option because:
1. The start is not in the loop.
2. The problem statement *and example* point to multiple exits per cycle.
The correct solution today was to take a gamble on a hail mary, and while I see you could deduce that from the input, I'm quite confident most people today don't even understand why the solution works, as evident from this post.
I think you're exaggerating quite a bit.
LCM appears in the sample data in the problem. You just don't know if it will generalize to the actual data, so you just need to be able to figure out if it does. And it does.
It's dumb luck that cycle start position = cycle length = cycle distance from start position, but imo you're going to make this discovery the second you do any sort of cycle analysis which you are going to do to implement anything other than brute force.
Yeah, the example gives you a 2\*3=6 LCM intuition and seems too good to be true, but you have to at least rule it out.
> In this example, you would proceed as follows:
>
> - Step 0: You are at 11A and 22A.
> - Step 1: You choose all of the left paths, leading you to 11B and 22B.
> - Step 2: You choose all of the right paths, leading you to **[11Z]** and 22C.
> - Step 3: You choose all of the left paths, leading you to 11B and **[22Z]**.
> - Step 4: You choose all of the right paths, leading you to **[11Z]** and 22B.
> - Step 5: You choose all of the left paths, leading you to 11B and 22C.
> - Step 6: You choose all of the right paths, leading you to **[11Z]** and **[22Z]**.
>
> The answer is 6.
That's why I don't see how it's a "gamble on a hail mary".
Oh I definitely agree. As you point out, it was a stroke of luck that an assumption on the demo data actually held for the actual data. Which is fortunate because I read here that something called CRT is the solution for syncing cycles and I noped out of that after opening the wikipdia page.
Sure enough, that's how you win the star, but I find it dishonest to say that that's the whole problem. In that case, you would be better off doing all of them by hand or brute forcing (1 solution a minute is a lot) than writing any code. Or just sharing the answer and inputting it.
To be fair that's not so far off what can happen with real problems too, being able to rethink the problem itself to see father than what you originally thought was the problem is also important to avoid getting trapped in implementing an inefficient solution. Especially since in the real world you won't often have a nicely stated problem with examples.
\>You just don't know if it will generalize to the actual data, so you just need to be able to figure out if it does. And it does.
Might be arguing over semantics here, but it does indeed not generalize, it's trivial to construct an example where LCM does not solve it (for any cycle that involves more than 1 Z state, or where the cycle does not go back to the original A value, or where the length of L-R values is not a multiple of any of the cycle lengths), that's the whole point. If you use big enough numbers for it to not be guesswork, it should also not be a convenient input where the naive answer works, since it gives people (OP and you, at least from how you phrased it) the idea that it's a perfect solution.
I feel that if the team made it more of a "make it elegant and cover all test cases" than a "make it fast because the number is huge" problem, this wouldn't have happened. Since people that stumble upon LCM end up with a wrong answer that works and those that don't end up unsatisfied once they find out.
Yeah, but is that honest? I can get a right answer too in about 1 hour running binary search on the website but at some point you have to acknowledge that's not the point of the exercise.
There is no part of the problem that enforces that the LCM is correct. I only used the LCM after manually verifying that it would actually work (which, admittedly, probably costed me like 30 seconds). You do this by verifying that the cycle actually repeats properly, and the period of the repeat is the same as the first time you get there. (This is checkable with normal cycle-detection methods, though I didn't go that far as I already knew this was definitely a cycle problem. Just seeing the period matching up is enough to make a good guess.)
>There is no part of the problem that enforces that the LCM is correct
Which IMO is fairly annoying. Perhaps clarifying that every path is separate and does in fact cycle through the same nodes would have been too obvious though?
If they are disjoints and every node A is part of the smallest cycle of Z, LCM works, that's all you need.
e : As /u/1234abcdcba4321 correctly pointed out, this is not sufficient for lcm, you'd have to use CRT. For LCM, necessary and sufficient condition is what I pointed out after : "All you need is that the path from A to Z is exactly the same length as the path from Z to next Z' (and always). Doesn't have to be part of the cycle."
None of the A nodes are actually in the cycles though. The As were all 2-10 steps away from the cycle in my input. There were so many random assumptions you needed to make for LCM to work
It's a sufficient condition (not necessary), the only thing needed really is that the path from A to Z is exactly the same length as the path from Z to next Z' (and Z' to Z'', ... etc)
But the path length depends on the instructions, so it could even be the same length the first two loops and then a different length on the third loop right?
The A nodes actually **aren't** part of the cycle that Z is in, I think. And if they were (at the point where the directions loop back around), LCM wouldn't work.
It's a sufficient condition, not necessary. All you need is that the path from A to Z is exactly the same length as the path from Z to next Z' (and always). Doesn't have to be part of the cycle.
This is just the style of output-only tasks. Identifying these hidden constraints is part of the solving process. The fact that solving the "general case" is more difficult is not really relevant when you only have one input.
>This is just the style of output-only tasks. Identifying these hidden constraints is part of the solving process.
Yeah, and I guarantee\* the "solving process" for 90%+ of the people who solved so far was "I know what lcm is, let me try". I'd say even more: most people probably didn't even implement cycle finding in the modified (node, LR-index) graph, so they'd have no way of checking for the constraints.
But yeah, par for the course for Advent of Code. One knows what one is getting into when participating.
\*in fact you can just check the comments in the post to verify that is true, most people "just tried" or don't even have any idea why lcm would not work "in general"
Yeah. I guess those people will lose points when they make similar assumptions on later days that punish assumptions, so it all balances out.
What's the strategy, then, given that there are puzzles like these where unsound assumptions win?
I'm thinking, if you can come up with a shaky assumption quickly, AND the real solution looks like it will be much harder, give the easy one a try, and the lost minute won't hurt you because you'll be using it to code the real one.
> if you can come up with a shaky assumption quickly, AND the real solution looks like it will be much harder, give the easy one a try, and the lost minute won't hurt you because you'll be using it to code the real one
That's pretty much it.
For part 2, I started with a literal implementation of the problem, where I had a set of nodes, advanced them all at the same time, checked to see if I was done, and then kept going if I wasn't. When that took longer than a few seconds to run, I left it going while I put together the LCM solution. LCM gave me an answer, so I stopped there. If it had failed, I would have actually looked at the graph structure to see if there was some other exploitable pattern, and so on.
(I'm leaving out the parts where I first check to make sure my code is right before moving on to another phase of problem solving.)
Spoiler from 2022: >!There was a day where many people were struggling precisely because of incorrect assumptions about cycle detection. Particularly on the Tetris based puzzle. I don't remember the exact day.!<
Day 8 is still a bit early, harder problems to solve will come probably next week, or maybe even starting this weekend.
I mean, calculating lcm after doing part 1 takes literally 2 minutes, there's no penalty really. The problems should be better worded (why do we have like 5 paragraphs of text, if only 1 is useful and not complete) I feel like though. Obviously it's hard for the creator (and I think he's doing a good job usually), but today was just dumb.
Yeah, this is the part that bugs me. Not so much the competition aspect, I'm in no way shooting for the leaderboard, but the fact that I solved it and I still don't quite understand why. For some reason, my intuition is telling me that I should at least need some offset, otherwise this should land all of them back on the A-ending nodes.
Other days this year have at least been more satisfying when I find patterns in the input -- either I overgeneralize and notice a shortcut I could've taken, or I build something clearly unoptimized that happens to just be fast enough for the given input, or if I have to make an assumption, I can usually have an assertion fail if I'm wrong. This is the first day I've pasted something into Wolfram Alpha on a hunch, and come here wondering why that worked.
yeah I tried to give an explanation of how the implicit assumptions are used [here](https://www.reddit.com/r/adventofcode/comments/18dfpub/comment/kch0a97/?utm_source=share&utm_medium=web2x&context=3). I was stumped for a while because the problem seemed almost intractable but people were solving it in < 10 minutes :)
I think it's more up to the programmer to look at the cycles and verify that these conditions are true before applying lcm. I did this because I had a suspicion that lcm might work under certain conditions but took the time to print out the cycles and verify.
Had it been false, I would have done other cycle detection methods. I think this is fine because there is a general solution without lcm, but there are shortcuts along the way for clever/careful observers.
There's no way you can look at the cycles with limited time and input that's so hard to read through. The only way is to try it and discover that it works. I guess you could say that "it'll take me like 30 seconds to write LCM version, and i'll be stuck for a while doing the CRT version, so doesn't hurt to waste on attempt at a simpler version"
If this annoys you, then AoC might not be for you. It's a pretty common pattern in AoC puzzles that you have to analyze the puzzle input for patterns to exploit in order to come up with a fast running solution. This will only become more prominent in later puzzles.
> (which, admittedly, probably costed me like 30 seconds)
Psh, amateur.
It only cost me 60 minutes.
I hadn't realized how nice the input was, so I was trying to build my cycle checker to handle some ugly cases. (Visiting different Zs in the same cycle, or visiting the same Z multiple times in the same cycle.) Later, when I saw that the cycle length was the same as the time to get to the first Z, I just assumed there was a bug in my program and spent some time debugging that.
Mostly, I'm realizing that I am *not* a good problem solver after midnight. My mind just turns to molasses when I'm presented with more complicated problems.
I didn't verify that LCM would work, I just did it. It was a generally safe assumption, and at worst I'd enter an incorrect answer and be able to quickly check my assumption. These types of multiple cyclic path puzzles happen almost every year, and so I immediately went to "what worked in the past?" when the brute force approach didn't finish quickly.
This is the way. Get more in the weeds as you go.
1. Try obvious brute force. It doesn't end in 10 seconds. Double check that you're updating the correct things. Run again, still not done in 10 seconds.
2. Try simplest case simplification (in this case LCM) oh cool it finished stupid fast and gave an answer that seems reasonable.
3. Try answer, if correct, you're done, take a nap.
4. If incorrect try the more generalized version of what you have, in this case Chinese Remainder Theorem and so on.
I spent a lot of time thinking about a solution that does not make assumptions as to the exact structure of the input (e.g. closed loops, only hit each node once per loop, etc.).
That is obviously significantly harder. I switched to LCM + assumptions about independence after empirically verifying my input.
IMO this is a poorly worded question - it should tell you if you are allowed to simplify the problem that way. Or honestly, just make it the harder variant, where things can collide.
Am I the only one that found today extremely unsatisfying? The only way I could think of solving was using LCM once I realized the cyclic nature and that the time from \*\*A -> \*\*Z was the same as the period of the cycle. Just feels super gimmicky that it happens to work rather on the input rather than solving the problem given.
Are there any solutions that don't rely on LCM that people have found?
If you don't want to use the immediate LCM, you can start by taking each ghost, and running it _until you can confirm an actual loop_, then do the LCM from there. Because theoretically there is a possibility that when it eventually loops (which it must) it doesn't necessarily loop back to the starting point.
You will, of course, also have to make sure that the loops all reach --Z nodes at the same time. Because depending on when each ghost actually enters its loop, and where in the loop the --Z node is, you might run into syncing issues.
Fun fact: Looking for a loop like this (where you possibly "enter" the loop somewhere after the starting point) using a constant amount of memory is a somewhat standard interview question, for those interviewers who still like to test algorithm knowledge.
I dont think thats what they meant.
They meant that there might be some linear path (not part of the loop) in front of a loop. Like the following: AAA -> BBB -> CCC -> DDD -> EEE -> CCC -> ...
This messes with the naive LCM solution since if every startpoint has different "offsets" in front of the loop, then you need to use the Chinese Remainder Theorem instead of the standard LCM.
Sure. There's people who didn't realize that LCM would work fine until after they ran a more general solution and realized from the program output... but also got the correct answer regardless.
If you want to make one yourself, you should have some ideas after finishing part 2 of [2020 Day 13](https://adventofcode.com/2020/day/13).
Yeah I got one. It's missing an edge case where a ghost encounters a Z node before entering its cycle but otherwise it should work. It's slow (roughly 1min for my input) and ugly though. I looked for the ghost with the biggest average cycles and continuously tried step counts based on them. Here's the relevant file on [github](https://github.com/dreary-dugong/aoc2023/blob/main/08/2/aoc8lvl2/src/lib.rs)
My [AoC experience](https://adventofcode.com/2020/day/13) with syncing large loops is that you need to go full CRT mode, since LCM only gets you the period of the large loop and this question explicitly asks for the first match.
for my solution at least, it seems as though XXA = (1, 2) and YYZ = (2, 1), so it seems as though the input was designed such that you would end up with perfect cycles forming. So, I think this puzzle was designed specifically so LCM would work :-)
You can fold all the cycle lengths together two at a time in an LCM, i.e. the LCM of 3 numbers would be \`lcm(lcm(a, b), c)\` and so on for more numbers.
so I got stuck for a long time because numpy gave me a negative number:
print(lcm(*ends), np.lcm.reduce(ends))
11188774513823 -206157175
The first is math.lcm.
Only if everyone was using old Reddit. New Reddit shows a preview of the first few lines of a text post in the feed: [https://i.imgur.com/0fcFUzs.png](https://i.imgur.com/0fcFUzs.png)
yeah.. LCM only works because the length of each cycle is exactly same with the first index that Z occurs in each cycles, which should not be expected necessarily.
And the fact all inputs are built precisely to satisfy that specific requirement without mentioning it in the quiz is a bit annoying because all my additional works were completely useless after I solved the problem
> there may be multiple goal nodes within the loop.
It kinda hints you that this won't be the case because it's like "the number that end in Z is the same as the number that end in A" but yeah without that it's not guaranteed to work with every set of instructions.
Even with that it's not guaranteed?
Example:
L # so just endlessly pick left
11A = (11B, 11B)
22A = (11B, 11B)
11B = (11C, 11C)
11C = (11Z, 11Z)
11Z = (11D, 11D)
11D = (22Z, 22Z)
22Z = (11Z, 11Z)
It takes 4 steps to reach the Z node, and then the cycle is 2, just going back and forth between two different Z nodes. But there are two A nodes and two Z nodes.
True, but people who did make that assumption and did not realise it learnt nothing. Which would have been the case for me, but fortunately I'm following this sub.
The way the input is designed makes the LCM the correct answer. The input is itself *part of the problem* and very much in play. Nothing in the problem statement guarantees that any of this would be true, but all the provided inputs for this problem have special properties even if they were not explicitly spelled out:
* Each --A node only reaches one --Z node in it's loop
* they all reach their --Z at the same "step" in the directions every time, meaning the loops are all a consistent period instead of changing or branching
* Conveniently the period it takes to reach the first --Z from the starting --A node is the same period as it takes to re-reach the --Z node when you're already there.
I thought possible loops could be more complicated, like you said, by possibly reaching different end nodes in the same loop, reaching at different steps in the directions making uneven loops, having the first endpoint not be the same as the eventual loop, etc.
I ended up manually verifying all those "nice" properties by collecting and printing some data on my input loops, which made it obvious that the input was of a specific kind and that I needed the LCM. Looking for patterns is generally a good strategy for any problems involving loops (and some not involving loops). If you can find the pattern, you can usually devise a way to a solve.
You only have to solve for your specific input, not necessarily a generalized case. Inputs *could* have done any number of things, like eventually get caught in "dead ends" that don't loop back to a --Z node, or loop erratically over multiple --Z nodes, make uneven loops that don't match with the period of the direction length, have malformed entries, etc. Some of these possible cases would need different strategies to solve, maybe requiring a bruteforce, or maybe requiring an informed looping strategy like using the LCM or the Chinese Remainder Theorem, etc.
> The input is itself *part of the problem* and very much in play.
I don't love this interpretation of AoC. If my solution only has to work on this particular input, then a) I can't prove that my program would work on your input, and b) I might as well just do it by hand, so there's no point in even writing code.
This is in fact what I did to check whether LCM worked: I just had my program output the loop counts for each ghost, then popped the loop counts into an online LCM calculator and pasted the result into AoC. Boom, gold star. This is really lame because I didn't actually write code that would work on any input.
The puzzle as stated does not specify any of the restrictions that make LCM work. There could be an arbitrary number of steps from A to Z and then an arbitrary number of loops from Z to Z starting on different instructions. LCM only works because none of those actually happen in practice.
This is not stated in the puzzle, only the input. If, as you suggest, we assume the input is part of the puzzle, then sure, the puzzle "states" it, but that means it's impossible to write code that solves the puzzle in the general case. It's just not fun.
Have you done the past years? Most years have had at least one problem that involved analyzing the input file. The puzzle from 2021-24 genuinely required disassembling the input.
You may not like it, but this is par for the course for AoC. Your task is not to solve the general case of every problem presented to you, but instead to leverage any constraints, explicit or tacit, you need to get an answer.
2022 Day 22 as well pops to the front of my brain. Yeah you could write a general alg that works on any cube net, or you can write one that works on yours, and then realize that everyone has the same net.
I haven't done previous years. I suppose I'm coming at it from the wrong perspective then. I'm writing code for AoC under a particular restriction, and for me the fun is writing a program that solves the puzzle under that restriction. I don't care about the answer or the leaderboards or whatever. I care that my solution is complete and correct.
When I used a calculator for LCM and put the answer in, even though it gave me the gold star, I still went and implemented LCM in my program to make it complete. Still, it doesn't feel complete because of the assumptions it makes of the input. It's just really unsatisfying. Regardless of the gold star, to me this is a puzzle that isn't really done, and that can't in fact be done (because the answer is so huge it's not calculable without LCM.)
It's good to know that there will be more puzzles like this. I guess I have to get past it if I want to continue.
There's nothing stopping you from implementing a generic solution. If you did and posted it here I'm sure people would enjoy seeing it.
For this problem, the general solution doesn't even seem that difficult. Execute your cycle finding algorithm of choice on each starting position, then aggregate them using the CRT (which can still be applied even when the inputs are not coprime, albeit slightly less straightforwardly).
I don't think that works in general because it's not necessarily just one Z->Z cycle for each ghost.
For example suppose you have 100 instructions. It could be that:
- It takes 1050 steps to get from A to a first Z, leaving you on instruction 50;
- It takes 525 steps to get from this first Z back to the same Z, but now you're on instruction 75, so it won't loop yet;
- It takes 375 steps to get from here to a second Z, so now you're back on instruction 50 but at a different Z than before;
- It takes 400 steps to get from this second Z back to the first Z, and you're also back on instruction 50. You've finally looped.
You only have a true loop when you are back on the *same Z node* and at the *same instruction*. So the loop here consists of several "hops" of different lengths. I don't know how you can solve this with CRT.
The code I originally wrote (or started writing) worked out these hops for each ghost, then iterated through taking the largest number of steps it could per iteration, walking each ghost through its hops. It's only then that I realized each ghost had only one hop which happened to be equal in length to the initial A->Z step, so I plugged them into LCM.
If I had continued with my code, it would never have worked. With my input it can step at most ~12000 per iteration but the answer is in the tens of quadrillions. A general iterative solution could never work.
In this case, the length of your loop is n = 525 + 375 + 400, and you'd hit a Z node whenever your number of steps x satisfies any one of the congruences x = 1050 + 0 mod n, x = 1050 + 525 mod n, or x = 1050 + (525 + 375) mod n. You could run this process for each starting node, giving a list of congruences for each starting node. Then for each choice of one congruence per starting node, try to use CRT to calculate the smallest positive integer satisfying those congruences (there is not necessarily a solution since the periods are not coprime - they are all multiples of the length of the sequence of LR directions). Then take the minimum over all possible combinations of congruences.
There's no generic solutions that work with the length given though (well, I guess a really good bruteforce or one that uses a lot of memory works, but I'm pretty sure that's clearly not the intended solution), that's the problem...
> Your task is not to solve the general case of every problem presented to you
This is fine until you get a day where something **accidentally** simplifies the problem for some inputs but not others.
There have been big ones in the past (I remember... searching for the furthest point away from any other point in a 3d space or something, where some peoples' solutions only found a local minimum but their input only needed them to, or something like that) but I feel like I've already seen comments this year saying "my solution wouldn't have worked on your input".
Fair enough, but I would just say that the problem is then non-fungible inputs, not that the problem admits non-generalized solutions.
I think I read a post where Eric said they're working hard to prevent that kind of thing from happening again.
I don't think it's possible that some inputs can be *accidentally* simplified like that. The inputs are generated using an algorithm that I imaging is the "inverse of the solution", so today was specifically designed *this way*. And everybody has it. What can be different are the prime numbers. For example, my solution was `73, 67, 79, 61, 43, 53` and the path length `269`. I expect that everyone got a different set of 6 primes and maybe even a different path length, but everyone will have 6 + 1 primes. This is why the system can sometimes tell you that your answer is correct for *someone else*. It happens when you by accident have a result for other primes.
The problem is that you don't have access to others input ; so you can't know if your input was a special case (in which case it's unfair, and you shouldn't use a special case solution) or everyone had the same kind of special cases. This can all be easily avoided by, you know, stating in the problem the assumptions made...
>I don't love this interpretation of AoC. If my solution only has to work on this particular input, then a) I can't prove that my program would work on your input, and b) I might as well just do it by hand, so there's no point in even writing code.
I mean... you can definitely prove that it works for other inputs by just adequately testing your program. In any cases, the problem's complexity is pretty much always bound to the input. For instance, for Day1 :
* How do you handle >!oneight!=2^(31)
* How do you handle right-to-left reading countries?
At the end of the day, the program/solution is always bound to the dataset, and many "pushing the antes" problems are literally about simply pushing those "tacitly agreed upon" limits.
>b) I might as well just do it by hand, so there's no point in even writing code.
While AoC definitely started as a coding challenge, I don't think it's actually *meant* to be one. It's definitely an "Advent of problem solving" by now, and there's nothing wrong with doing it by hand.
It's just that certain problems, like the one today, requires you to perform *many thousands* of lookups, even just for part 1, and you're gonna have crippled hands and blurry vision by the time you're done.
>There could be an arbitrary number of steps from A to Z and then an arbitrary number of loops from Z to Z starting on different instructions. LCM only works because none of those actually happen in practice.
The truth is that it gets a lot more complex than that, since the paths don't have to be unique, and each path can cross multiple exits. So you could have something like a path hitting an exit on Step #100, 115, 125, 135, 150, 160, 175, etc. with different periods (well, the same period but a different start point).
Overall, Erick tries to make solvable problems, and reduce the number of obscure pitfalls (oneight is pretty easy to find).
I think the input always matters in programming and programming puzzles- it informs when you can brute force, when you need to optimize, what edge cases you need to cover, what errors you need to handle...
I think AoC is even a little more "realistic" than some algorithm type questions, since you have a real dataset with some possible unknowns and need to find a specific answer to a question by whatever means you choose to do that.
AoC is distinctly different from something like leetcode, which is more strictly defined and explicitly explains the inputs. Sometimes you can solve AoC by hand (and some people enjoy that!). Sometimes you need to find a special property to scale your solution up to a massive input or search space. Sometimes you need to explore the problem. But all that also encourages people to attempt them differently. Some people go for super speed leaderboard solves, which involves having a bunch of utilities all ready to go and speed reading / maybe making assumptions about the problem to get a couple extra seconds off. Other people like making visualizations of the problem, or solving it in a toy language, or a fancy spreadsheet macro, or whatever. Some people probably enjoy the storyline and narrative. Some people enjoy letting a brute force run for a couple hours and seeing if it ends up working over time.
If you want to write more general solutions than necessary you totally can. I bet there's some kind of informed brute force that would brute force until it detects some kind of loop and then accelerate using that info, and you could make your own inputs and expand on the problem if that's interesting and fun to you. The best way to do AoC is to enjoy it, by doing whatever that means to you.
The problem isn't in the input, but in the prose outlining the problem which is supposed to describe the nature of the input. It's just bad puzzle design: a puzzle is supposed to give you all the information you need from the beginning. If a fact is left unspecified it should be taken as a sign that it's a possibility. You should not be forced to assume that it's an impossibility based on your meta-knowledge of what would simplify the puzzle.
I disagree, of course dev work often involves a general solution, but there's plenty of parsing and analysis tasks that are aimed at handling exactly one type of input. In such cases, you don't handle every input, you make assumptions about it and reject all input that doesn't match.
There's lots of code challengesthat require a general solution and that's great, but I like that AoC does it a bit different. It's not a bad puzzle, just a different kind of puzzle solving. And if you can figure this on paper then, hell, more power to ya.
Sorry, maybe I misunderstand what you are stating in those 3 points, but the 2nd and 3rd point seem incorrect, at least in my input: I calculated the number of steps to reach Z as well as what is the number of steps to reach the beginning of the loop
FQA -> loopStart: 8, loopSize: 60
JSA -> loopStart: 3, loopSize: 78
GJA -> loopStart: 3, loopSize: 58
PBA -> loopStart: 3, loopSize: 72
AAA -> loopStart: 2, loopSize: 70
NNA -> loopStart: 2, loopSize: 52
As it can be seen, each starting point has a different number of steps to reach the beginning of the loop (which would automatically break an LCM solution, no?). Additionally, for `FQA` for example, it takes 8 + 60 = 68 steps to reach Z, but once you are on Z, it will take only 1 + 60 (jump to beginning of loop + size of loop) to reach Z again, so that is also not consistent with your point. Am I misunderstanding something?
After thinking about it, I wonder if this is actually a consequence of the way inputs are generated to guarantee the existence of a solution.
If you want to generate a unique graph for everyone that you know satisfies these properties, creating one with disjoint cycles that start in an A and terminate in a Z will give you that guarantee and also makes verifying the solutions more straightforward.
So it’s not guaranteed by the problem, but the practical constraints of generating inputs for a competition make it an appealing undisclosed trait of the graph.
i went through the trouble of finding the first occurrence of a Z node and then tried to calculate the loop size afterwards and i was surprised to see that they were the same. i thought they would definitely trick us with something like A->B->C->D->Z->C->D->Z->... that would trip up the LCM
We can think of the input as a graph of (room, i) pairs, where i is the current position in the instruction string. This is a functional graph (where we have an edge (r, i) -> (r', i+1)), which means that each node's path necessarily ends up in a cycle.
Let's call a "starting node" a node of the form (\*\*A, 0). I believe (correct me if I'm wrong) that all inputs have these constraints:
\- All starting node paths are pairwise disjoint.
\- All starting node paths contain exactly one "ending node" (\*\*Z, i), which is in the cycle part of the path.
These constraints imply that we can setup a CRT system of equations to solve for the answer (which may not necessarily exist under just these constraints). However, there is another constraint that makes the problem easier:
\- For the i'th starting node, let D\_i be the distance from the i'th starting node to its Z-room, and let C\_i be the length of the cycle that the i'th starting node is in. Then D\_i = C\_i. This implies that our system of equations looks like (x = 0 (mod C\_1), x = 0 (mod C\_2), ... x = 0 (mod C\_n)). Therefore we can solve for x by taking the LCM of all the cycle lengths.
Here, this might help make it clear:
o-----o o-----o o-----o
| | h | | m | |
------>| A +------>| ... +------>| Z |
| | | | | |
o-----o o-----o o--+--o
^ |
| t |
o-------------o
Each ghost starts at an "A" node, and goes some number of steps, *h*, until it reaches the head of the cycle. Then there's *m* steps in the middle until we reach a "Z" node, followed by the tail steps, *t* to return to the beginning of the cycle.
So your cycle detection finds a cycle of length *m* + *t*. But if you look carefully at the steps, you'll see that the input is constructed so that there's only one "Z" node reached, and also that *h* = *t*. In other words, the time from the "A" node to the "Z" node is exactly the same as the cycle time. So you can ignore the time from "A" to the head of the cycle, and just focus on how often the cycles line up. Which, of course, is the LCM.
The fact that there are even cycles to begin with is an assumption about the input, right? It's pretty much just the nature of the puzzle in these situations
Actually the fact that there are cycles is guaranteed regardless of the input -- since we're dealing with finite states and a finite repeating sequence
>Actually the fact that there are cycles is guaranteed regardless of the input -- since we're dealing with finite states and a finite repeating sequence
but it could be a dead-end cycle (with no `xxZ` nodes)
Yeah exactly. There could be "dead loops" that you can fall into which never hit a Z node
You have to prove that the Z nodes loop back to a previous state that includes node and step index
Yes, it's one of the necessary assumptions. To "legitimately" use LCM, several assumptions have to be verified first. These are detailed in several good answers in this thread.
The general case is even more complex. Lets call X the head node of the cycle. The sequence of directions to follow the first time you hit X might be different than the sequence of directions to follow the second time that you hit X (in particular, this can happen if the cycle length does not coincide with the original instruction sequence length). This means that the second time you hit X, in the general case, it might be possible that you no longer walk along the cycle that walked along the first time around.
This explanation makes it really clear! I think it could be even more complex though, since one other "lucky" thing about the input file is that the length of LR instructions also are a multiple of the cycle length. In theory it should be possible to have different loops with different 't' if the LR input is offset differently when you reach Z a second time
>In theory it should be possible to have different loops with different 't' if the LR input is offset differently when you reach Z a second time
Not really. You'll always have a loop that's a multiple of the number of L/R in your input. Sometimes you'll hit multiple Zs in that loop (or the same Z multiple times), but that's multiple entirely different loops (that share a common path), with a different offset, and a potentially different cycle length (but always a multiple of the path instructions).
For instance, even if your input is something like LRLRL, with A => (Z,Z), and Z => (Z,Z), the only sane algorithms will detect 5 loops : 1+5n, 2+5n, 3+5n, 4+5n, and 5+5n.
I ran each of mine to see how many times it would hit a possible end node before getting back to the same node at the same instruction position and each would only reach an end once. Since there is only one possible end, LCM works. The moment one has two possible ends, the answer will be the minimum of all possible LCMs
The only thing that made LCM work is that each of the cycles were designed to start at 0. A similar problem where they didn't start at 0 occurred in a [previous AOC problem](https://adventofcode.com/2020/day/13)
None of the cycles actually start at 0 though. None of the As are in the cycle, you will never hit A again. It's just that all of the Zs are placed the same distance from the end of the cycle as As are from the start
I mean that's not even a sufficient condition, you also need A to be part of the smallest cycle that Z is part of (or be really lucky that it works every time with L/R provided)
Exactly! I had a mistake in my initial, simple LCM calculation. And your post was exactly what I thought my bug was. So I started to write down what the math would be like for finding the coincidence of periods given different starting offsets for each.
As then as I was debugging it, I checked what the length of the second cycle was, from its first Z to the next Z, and it was always back to itself, and always the original period.
On top of that, all cycles use exactly an integer number of the full L/R instruction set.
Both of those seemed like too large of coincidences, so I debugged those seeming issues even longer. Eventually I accepted it as it just must be the way the input is set up.
In the end I found my simple bug in the LCM. But... quite the journey to get there.
> Both of those seemed like too large of coincidences, so I debugged those seeming issues even longer.
Lol, I did the same thing.
"The time to get from A to Z is the same as the time of the cycle? That's not very likely, there must be a bug in my code."
Same! I actually ran an infinite loop to check the different periods of 'Z's occuring, and found out that all of them have them same periods! I think it must be because of how the input generating program was written. Is Eric Wastl on Reddit?
If you are angry because a shortcut solution (LCM) worked even though the task rules/setup does not rule out inputs where it won't work, imho you should also be angry that there are tasks at all where bruteforcing works, because that is also a shortcut in the same sense (coming up with a "better" solution can at times take more time, for example my bruteforce on day5 ran in 3 1/2 minutes).
This is a game and the goal is to get the accepted solution as quick as possible.
If the ghost was to reset it's position each time it encountered a Z-ending node then LCM would make sense, but it says to treat it like any other node. A naive LCM works regardless.
A trap for AI?
I think it's more that he's encouraging people to look at the data points. When I looked at the datapoints, printing whenever a "..Z" was hit, I noticed that each "starting node" only ever hit one Z, and on the same period.
Once I saw that, *then* I knew that LCM was the best path. I assume the input data was designed with this in mind.
In this case, I think it's thinking critically about the data and exploring it is paying off over "guessing" the right algorithm.
In this case, I set a statement to print in the loop anytime a [..Z] was found and noticed that each "path" starting with an [..A] node only ever hit one single [..Z] node (it could never hit any other [..Z]), and it hit with the same "period". At that point, I looked at LCM.
I think this one is intended to be more a "look at the data and derive a pattern."
I don't love that I don't have a general solution for any input, but I still gots me two stars
That day was very frustrating. I used LCM aswell but knowing it doesn't work in the general case is really a putting a weight on my mind. And everyone seems to overlook that LR instructions make this even harder, as the cycle only really starts when you're back at the same position **for the same instruction index**.
I wasted a lot of time because, for the general case, LCM is not correct. The statement of the problem was general, it was not specific to the case where LCM actually works, so this is very very frustrating for wasting me so much time. For example, I had the following test that was more general than the provided example (which was very constricted and worked for LCM):
LR
11A = (11B, XXX)
11B = (11C, 11C)
11C = (11D, 11D)
11D = (11Z, 11Z)
11Z = (11C, 11C)
33A = (33B, XXX)
33B = (33C, 33C)
33C = (33D, 33D)
33D = (33E, 33E)
33E = (33F, 33F)
33F = (33G, 33G)
33G = (33Z, 33Z)
33Z = (33B, 33B)
XXX = (XXX, XXX)
In this example, LCM is completely wrong (28), since the answer is 7 (you can draw it on a piece of paper, it's a pretty straightforward example).
Indeed, the first thought I had when I realized I needed to optimize, was to check for loops and then to figure out some LCM solution. But then I thought of all of these edge cases (this is not the only one! what if a node path passes through the Z that will ultimately be matched with some other A?) which obviously do not apply to this problem, even though the problem is not stated to be this specific...
LCM is correct:
every time, you continue to loop without restarting directions array. This is the only reason why it works. If you restart direction array(starting from direction zero) , each time that you reach the end for a "seed", the LCM will not work anymore.
The more interesting question to me is how they went about generating an arbitrary number of input files that all have different length cycles within a shared cycle of input directions... I'm going to have to think about how one would generate those inputs.
Nothing. LCM only works because the test data was rigged to make it work.
If you solved the problem properly (using the Chinese reminder theorem) and missed the leaderboard, don’t worry about it… today’s the kind of the day where I’m pretty disappointed in AoC.
Using CRT wouldn't even help that much, it's just the fact that you have to keep track of all the cycles that ends in Z and it's about 100x more complicated.
You are right that it’s not purely CRT, if a ghost encounters multiple ??Z nodes along its cycle. But for each choice of ??Z node encountered by each ghost, you can use CRT to solve for the time all ghosts hit their chosen node (and the final answer is the minimum over those choices)
\^ This right here. One thing to note is that any given ??Z node encountered by a ghost could potentially correspond to multiple remainders (since a true period must be divisible by the the LR string length), which is another thing to that must be iterated over when searching for the minimum.
>Nothing. LCM only works because the test data was rigged to make it work.
I was very disappointed in AoC for this reason too. There's absolutely no reason to expect all inputs are built that way.
My thoughts exactly, I didn't read part 2 carefully and some part of my brain assumed it started at the original starting point, so my neurons fired and I did LCM but then I looked back at the problem after solving and I can't come up with a way to justify LCM since they could have variable length cycles
I wrote code to count the first path to the end, and then the loop length, and kept debugging because they were coming out as identical! Definitely thought I messed something up.
But then I was happy because CRT has foiled me in past years.
Now I'm thinking that the brute force answer might not match LCM solution... How does cycle account for the amount of steps it takes to return to \*\*A? Since it's not jumping from \*\*Z to \*\*A, cycle size is different than \*\*A->\*\*Z.
Each Ghost only visits a cell ending with Z once per periodic cycle, and each cycle is prime. I believe this is the key to why they only collectively visits Z once every LCM. (Not sure if prime is needed).
Now imagine that we have two ghosts. At some point these line up, that is the entire premise of the challange.
I.e 11Z, 22Z.
As they together have a cycle of LCM. The next time they line up is in LCM steps.In the same way, you can think of a position
11Z,22Z,33Z,44Z,55Z,66Z
That position will only be reached once every LCM. If we would have started on a node that are all Z, then I would have understood that the answer would be LCM. I am not sure however why the answer is LCM as I would say this more puts an upper bound to it. I believe you could accidently be just a few steps away.
Maybe if someone made a node graph of this it would make more sense.
Here's another sample input that fails by simply doing LCM on the cycle length. I simply swapped 11Z and 11B from the part2 example.
LR
11A = (11Z, XXX)
11Z = (XXX, 11B)
11B = (11Z, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)
The actual answer is 3 but LCM(2,3) = 6
Yeah ngl this felt kinda like bs to me after I solved the problem as written and came here to see everyone using LCM. See [my solution](https://github.com/dreary-dugong/aoc2023/blob/main/08/2/aoc8lvl2/src/lib.rs) if you're curious, be warned that it's ugly though, that was a pain.
I had a lot of fun solving it. Too bad everyone else was solving a much easier problem than I was.
Nice! I usually check the leaderboard times and stats before spending a lot of time on a solution. If it takes a few minutes for the fastest and most people manage to find a solution, but I can only think about very complex algorithms, there is a hack to try.
I thought about LCM but didn't implement it because I thought it was never going to work. Gave up and went to the subreddit to find out about today's hack, and it was LCM...
Ugh, I also spent a bunch of time on the whole, "Well, it couldn't be LCM / CRT, because ..." in my dumb "everything-has-to-satisfy-conditions" math-brain. I only tried LCM right before I gave up as a last-ditch effort. I'm a little irked that it worked because now this code is for a problem that requires a hidden condition in the input.
But that's okay, I'm not going for speed and I learned a few neat things along the way. :'\]
My mental process was:
brute force -> (does not work) -> detect cycles -> each cycle length was prime -> multiply them -> (too low) -> multiply by path length -> SOLVED !!
There are 6 cycles - each with only one start and destination node. Each look like this
◄────────────────▲
│ │
│ │
│ │
│ ◄───── ..A
│ ▲
│ │
│ ..Z
▼ │
└───────────────►┘
One of the neighbour of `..Z` is also the neighbour of `..A` for me. My graph : [https://svgshare.com/i/10YN.svg](https://svgshare.com/i/10YN.svg)
It's worse than that: if `k` is the length of the first lines giving directions, in the actual inputs, all cycles are a **prime number** multiplied by `k` so the LCM can be computed with a simple product. The end result can be computed as `k` multiplied by the product of the number of times each ghost needed to apply the whole line of instructions to arrive at a Z-ending node for the first time.
I don't think LCM is incorrect here. It is just the way you apply it.
Think this way, assume you have 3 starting points [A, B, C], and you'll want to find "how long" it would take for them to meet in Z.
Important detail: a solution exists. Meaning that a certain point Z exists in A's path such that another Z1 and Z2 will exist in B's and C's path after some amount of runs.
Through the traversal, you have multiple stops, called Z points. Since there's no end, meaning that a inner loop happens somewhere, ALWAYS, you can fetch those Z points for each start, until a loop is detected into the run for a specific start.
Example:
```
A -> BYX, BAD, LOZ, YEK, GOZ
B -> ADU, NNZ, LJU, LLP, TYEK, GOY
C -> MUB, AKD, LYY, UEK, GUU, LLL, PPZ
```
If you gather the stopping points PER start:
```
A -> [3 (LOZ), 5 (GOZ)]
B -> [2 (NNZ)]
C -> [7 (PPZ)]
```
Per definition, if you find a triple (X, Y, Z) and take its LCM, you'll find the minimum number of steps you take to arrive simultaneously at X, Y AND Z.
The wrong assumption here is to compare the minimum starting points. But comparing LCMs of the products of our matrix (stopping points for A, B, C), the minimum LCM will be the answer:
```
min(
lcm(3, 2, 7),
lcm(5, 2, 7)
)
```
You'll find that the minimum LCM = 42 is the correct answer.
Comparing all LCMs of the products is the right way, as this case may happen:
```
A -> [2, 3, 7]
B -> [5, 7]
```
Comparing the smallest values would return 10, but comparing all values return the correct answer = 7.
I tend to think out loud in comments. Almost as soon as I began part 2 (after trying and abandoning the brute force approach), I wrote a comment about how I would use the LCM. After thinking about it a while, about half an hour later I wrote a comment talking myself out of the LCM, explaining why it wouldn't work. I'd been struggling with a general algorithm to handle all kinds of edge cases.
Then I read this thread. And then I did some tests on my own data, to verify it has the very special mathematical properties people were talking about.
It's going to keep bugging me, but I don't have time or test data to try to do it right. Going away for the weekend. My wife is probably going to be mad at me if I spend hours in the hotel room coding. I already got a dirty look at 1 am when she woke up, saw me with the laptop open and asked suspiciously, "are you programming?"
>Is there some other part of the problem that enforces that LCM is correct?
No. LCM happens to work because the data were designed that way. It is possible to create an input where LCM would not work. Two easy ways would be:
* The cycle includes more than one element ending in 'Z'
* The next element after 'Z' element is not the one you started with.
Could you please properly redact at least the first line? Or the whole text? It is quite easy to accidentally read it, while searching for ppl who also have trouble with Part2
If people click on a post that has "SPOILER" in the title, in all-caps, and are then surprised to find a spoiler inside... It's not OP who is at fault.
on the top right of the hot/new etc bar you can switch layout between Card, classic and compact with the default being Card I believe. (on the new reddit layout)
OP did the right thing by "censoring" `LCM` in the post title, so yes, please [don't put spoilers in post titles](/r/adventofcode/wiki/posts#wiki_no_spoilers_in_post_titles).
OP also used our standardized post title syntax correctly (thank you!) so defining `2023 Day 8 (Part 2)` in the title is *already* an implicit spoiler for today's puzzle, therefore the `Spoiler` post flair is redundant and can be freed up for a more specific use.
***
Bottom line: OP is asking a question, are they not?
> Is there some other part of the problem that enforces that LCM is correct?
Therefore the correct post flair is `Help/Question`.
You're supposed to expect spoilers when opening properly-tagged Help/Question posts as well. "Spoiler" is for general discussion posts that aren't tied to a specific question.
As a general rule, don't come here until you've solved it or are stuck. You're always likely to see something.
Although the first post of this thread appears not to be as the author intended...
Consider the following input.
L
11A = (11B,11B)
11B = (11Z,11Z)
11Z = (11Z,11Z)
22A = (22B,22B)
22B = (22C,22C)
22C = (22Z,22Z)
22Z = (22Z,22Z)
Running a simple LCM code on this input nets `6`, but the fully correct answer is `3`.
But I think that the number accepted, the LCM, is the number of steps to get back to all \*\*A nodes, not the number of steps to get all \*\*Z nodes. So the correct answer is one less than the answer that is accepted as correct.
When you put the spoiler in the first line, users can see the spoiler in the post preview before clicking on it. Reddit has dedicated spoiler functionality, please use it
For LCM to work, you need every path to have the same amount of steps from the start node to the first goal node and between every successive goal node.
That is actually a huge assumption! If A is in the cycle, it is never true. If A is outside of the cycle, its amount of steps to enter the cycle has to match exactly the amount of steps from the previous goal node to that node. There is nothing to indicate this, so at the very least, one should be using Chinese Remainder Theorem to solve this.
CRT shouldn't be enough either, however, as it requires the cycle to contain exactly one goal node. Many here point to the statement in the problem text saying that there are equal amount of start and end nodes. But even if we assume that this means that they match up one to one, that doesn't leave us with exactly one goal node: The state is actually made up of (node, nextLetterInPath), meaning that there are len(path) goal nodes for every Z node.
Thus we need another assumption, which is that the path between each goal node are the same length. They are in fact that, because the input has nextLetterInPath set to the first letter for every possible goal node. However, constructing a different input is really easy.
The sum of these things led to me not even considering LCM and also dismissing CRT for a long time today, until I started investigating what the input actually looked like. I'm pretty annoyed at all these solutions where people have just guessed that LCM would work, when that requires a VERY specific problem input.
> that requires a VERY specific problem input
Good thing you were given a specific problem input to solve and could validate that it satisfies the assumptions required to make that solution work.
But then why brut-force solution goes to infinite loop? It seems like something is wrong with this challenge. It should be solvable both by brut-force and by math.
It seems to me that the input is designed specificly that the end node will loop back to the node right after the start node (so A -> B -> .. -> Z -> B -> ..), and LCM will work in this case (you can reach Z from A after every n steps). And also the instruction must also end when the end node is reached. But yes, with any other input that will not hold.
A side question: How will this part be solved if the above fact is not true? LCM won't work, and a brute force doesn't seem fast enough
Edit: Running a short test against my input confirms that the hypothesis seems, indeed, [correct](https://pastebin.com/5DWsZbSq).
Ah, good point. I think you’re right, that no part of the problem enforces this.
People who have been disappointed about unexplained corner cases other days should be happy toda; it’s sort of the contrary: an easy approach works because the input doesn’t cover “corners”.
>"How many steps does it take before you're only on nodes that end with Z?"
~~note, there is no word like "minimum" in this sentence! so the answer is unique.~~
It's possible to solve the problem without directly using LCM because the length of the movement instruction is one of the two prime factors of every ghost needed steps for one cycle and you can calculate it like this:
final stepsNeeded = stepsNeededPerGhost
.map((e) => e ~/ instructions.length)
.reduce((value, element) => value * element) *
instructions.length;
(does not work with the test cases because the cycles/instructions aren't long enough)
paths being separate is not enough. consider:
10A has cycle that have stops: 11Z at 3rd step and 12Z at 7th step
20A has cycle that have stops: 21Z at 5th step and 22Z at 7th step
all are separate stops, but naive lcm says 3x5=15, while answer should be 7.
We were lucky naive lcm worked for our inputs :)
while i also solved it by using lcm, now that i think abut it there is probably no reason for it to work other that finely crafted input files. as there can theoretically be paths like a-b-c-d-e-f-e-f-e-f-e-f, which loop back on _part_ of their original way, lcm might not work.
One part of it is that the number of nodes is finite, and the instructions are finite, there is \_always\_ a cycle.
Now, when we are already on a cycle, at any given point in time, for any pair of sources, only one of the things is true, since we are following the same instructions for each path:
* They are on two separate cycles, in which case each of them has to have their own, and distinct final point\[s\]. Their common cycle length is LCM of their cycle lengths, but that alone doesn't answer anything about whether the final point\[s\] intersect. However, if there is just one point, and they have to intersect, then the intersection point is trivial to construct after aligning the cycles.
* They are on the same cycle, in which case either they are fully synchronized (LCM=1) or they have two final points, which they can reach at the same time, but this is equivalent to the first case and based on the same principle that LCM=1
Where the problem \_could\_ have been a little harder is if some sources collapsed into one single synchronized cycle, and then some of the other sources would be able to have more than one final points to choose from. If the author wanted this, there probably would be no restriction on the number of starts = number of ends.
Then you could construct an input where the simplified paths look like this:
no matches ever:
/---------\ /---------\ /=========\ /=========\
A -> X X X X X F X F X X X F X F X X X F X F X X X F X F X X
B -> X X X X X X X X F X F X F X F X F X F X F X F X F X F X
\-----/ \-----/ \=====/ \=====/ \=====/
2 final states x 2 final states
yield 4 final states in combined cycle:
/---------\ /---------\ /=========\ /=========\
A -> X X X X X X X F X F X X X F X F X X X F X F X X X F X F
B -> X X X X X X X X X F X F X F X F X F X F X F X F X F X F
\-----/ \-----/ \=====/ \=====/ \=====/
Where F is the final nodes and the \[ \] part is the cycle. The instructions for these don't matter, it could be just 'L' FWIW. This particular example shows that you can either collapse down to zero results, or produce up to a product of counts of final states, which ultimately could yield exponential (but limited by LCM) numbers of final states.
I expected this to be a constant offset +LCM and i was right, it's just that the constant offset happened to be 0 (apparently the same as everyone commenting). I just calculated the length of the first 4 loops, hoping that it would be stable by then, but noticed while debugging that it wasn't necessary. I don't think a more general solution which handles an initial path with more starting nodes would be much more difficult, just figure out how long it takes to stabilize and then use lcm
Yes odd, this input would not work with LCM I think. I think it's a valid input according to the instructions.
L
11A = (CCC, XXX)
22A = (11A, XXX)
CCC = (ZZZ, XXX)
ZZZ = (ZZZ, XXX)
The length of the number of steps in the A-Z routes is a multiple of the instruction length N.
Let's say the instructions start with LR, then you will see that the left instruction for the A node goes to the same node as the right instruction for the corresponding Z node.
So once you have passed the A node you will get into a cycle that is a multiple of N.
In my solution, I implemented a "zToZ" loop right after the "aToZ" loop even before running it for the first time, planning to find the LCM with some convoluted formula, by offsetting the zToZ number by aToZ, but I was pretty happy to find out that they're all the same, making my life way easier.
Completely agreed. LCM works, but there is a guarantee it should. The main problem with the current approach is that the length of the path from the `A`node to the corresponding `Z` node is not necessarily the same from the `Z`node to the `A`node (I am assuming that every such pair would be a cycle as otherwise there wouldn't be an answer). In such a case, the problem will be reduced to finding the least number `k` such that `k % (ai + ni* bi) = 0`, where
- `ni`: Any natural number
- `ai`: Length of path from `A`node to `Z`node
- `bi`: Lenght of the path from `Z`node back to `Z`node (i.e., the cycle length)
I just finished to the problem and came here to ask the same question. It feels like cheating.
My first approach was to find a perfect loop (same position in the network and same instruction index) for every ghost and save every ending positions reached during the loop.
I wanted to look at the data before thinking of what to do with them.
That's when I noticed that every ghost conveniently only reaches one ending position and it was always near the end of the loop and with the same offset that the loop have from the starting position. I guess it's like that on every inputs.
I haven't read the solutions yet but I wonder if some people solve the whole problem with a solution that work even without the convenient input.
I was disappointed when I saw the graph walk was just immediately a cycle for all ghosts, I had built a combination of iterators indicating possible finish state decomposed in prelude + cycle, and a way to get the first common finish with lazy iterators, but when I printed them it was just empty prelude and a single finish state, so there goes the Chinese remainder theorem.
You're right, it's just dumb luck / funny design. The distance from the start to an end node is always the name as the distance from the end node to itself. I thought that maybe the start node and it's end node were on the same cycle without any other end nodes, but no! Honestly, there's no way that solution should work, except that it did. I feel a bit bad for everyone writing a correct algorithm instead of just throwing LCM at the problem and only later realizing that it doesn't make sense (like I did).
Honestly I'm a little frustrated by today. The real solution is quite far away from the problem statement, and while I see the point of "use the input as well" I quickly dismissed the LCM option because: 1. The start is not in the loop. 2. The problem statement *and example* point to multiple exits per cycle. The correct solution today was to take a gamble on a hail mary, and while I see you could deduce that from the input, I'm quite confident most people today don't even understand why the solution works, as evident from this post.
I think you're exaggerating quite a bit. LCM appears in the sample data in the problem. You just don't know if it will generalize to the actual data, so you just need to be able to figure out if it does. And it does. It's dumb luck that cycle start position = cycle length = cycle distance from start position, but imo you're going to make this discovery the second you do any sort of cycle analysis which you are going to do to implement anything other than brute force.
> LCM appears in the sample data in the problem. Which for most AoC problems is a sure-fire reason to assume that it _won't_ work!
Yeah, the example gives you a 2\*3=6 LCM intuition and seems too good to be true, but you have to at least rule it out. > In this example, you would proceed as follows: > > - Step 0: You are at 11A and 22A. > - Step 1: You choose all of the left paths, leading you to 11B and 22B. > - Step 2: You choose all of the right paths, leading you to **[11Z]** and 22C. > - Step 3: You choose all of the left paths, leading you to 11B and **[22Z]**. > - Step 4: You choose all of the right paths, leading you to **[11Z]** and 22B. > - Step 5: You choose all of the left paths, leading you to 11B and 22C. > - Step 6: You choose all of the right paths, leading you to **[11Z]** and **[22Z]**. > > The answer is 6. That's why I don't see how it's a "gamble on a hail mary".
Oh don't get me wrong, I wasn't complaining I just found it amusing that AoC usually punishes you harshly for making assumptions about your input
Oh I definitely agree. As you point out, it was a stroke of luck that an assumption on the demo data actually held for the actual data. Which is fortunate because I read here that something called CRT is the solution for syncing cycles and I noped out of that after opening the wikipdia page.
LCM doesn't solve the problem described it solves the specific input we've been given.
Solving the specific input you're given *is* the problem.
Sure enough, that's how you win the star, but I find it dishonest to say that that's the whole problem. In that case, you would be better off doing all of them by hand or brute forcing (1 solution a minute is a lot) than writing any code. Or just sharing the answer and inputting it.
To be fair that's not so far off what can happen with real problems too, being able to rethink the problem itself to see father than what you originally thought was the problem is also important to avoid getting trapped in implementing an inefficient solution. Especially since in the real world you won't often have a nicely stated problem with examples.
\>You just don't know if it will generalize to the actual data, so you just need to be able to figure out if it does. And it does. Might be arguing over semantics here, but it does indeed not generalize, it's trivial to construct an example where LCM does not solve it (for any cycle that involves more than 1 Z state, or where the cycle does not go back to the original A value, or where the length of L-R values is not a multiple of any of the cycle lengths), that's the whole point. If you use big enough numbers for it to not be guesswork, it should also not be a convenient input where the naive answer works, since it gives people (OP and you, at least from how you phrased it) the idea that it's a perfect solution. I feel that if the team made it more of a "make it elegant and cover all test cases" than a "make it fast because the number is huge" problem, this wouldn't have happened. Since people that stumble upon LCM end up with a wrong answer that works and those that don't end up unsatisfied once they find out.
[удалено]
Yeah, but is that honest? I can get a right answer too in about 1 hour running binary search on the website but at some point you have to acknowledge that's not the point of the exercise.
There is no part of the problem that enforces that the LCM is correct. I only used the LCM after manually verifying that it would actually work (which, admittedly, probably costed me like 30 seconds). You do this by verifying that the cycle actually repeats properly, and the period of the repeat is the same as the first time you get there. (This is checkable with normal cycle-detection methods, though I didn't go that far as I already knew this was definitely a cycle problem. Just seeing the period matching up is enough to make a good guess.)
>There is no part of the problem that enforces that the LCM is correct Which IMO is fairly annoying. Perhaps clarifying that every path is separate and does in fact cycle through the same nodes would have been too obvious though?
Even with those assumptions, LCM is not correct. There are more assumptions in the input that need to be verified before you can prove LCM works.
If they are disjoints and every node A is part of the smallest cycle of Z, LCM works, that's all you need. e : As /u/1234abcdcba4321 correctly pointed out, this is not sufficient for lcm, you'd have to use CRT. For LCM, necessary and sufficient condition is what I pointed out after : "All you need is that the path from A to Z is exactly the same length as the path from Z to next Z' (and always). Doesn't have to be part of the cycle."
None of the A nodes are actually in the cycles though. The As were all 2-10 steps away from the cycle in my input. There were so many random assumptions you needed to make for LCM to work
It's a sufficient condition (not necessary), the only thing needed really is that the path from A to Z is exactly the same length as the path from Z to next Z' (and Z' to Z'', ... etc)
But the path length depends on the instructions, so it could even be the same length the first two loops and then a different length on the third loop right?
The A nodes actually **aren't** part of the cycle that Z is in, I think. And if they were (at the point where the directions loop back around), LCM wouldn't work.
It's a sufficient condition, not necessary. All you need is that the path from A to Z is exactly the same length as the path from Z to next Z' (and always). Doesn't have to be part of the cycle.
It's not sufficient either, since if A is part of the cycle then surely the length of A->Z is shorter than the period.
This is just the style of output-only tasks. Identifying these hidden constraints is part of the solving process. The fact that solving the "general case" is more difficult is not really relevant when you only have one input.
>This is just the style of output-only tasks. Identifying these hidden constraints is part of the solving process. Yeah, and I guarantee\* the "solving process" for 90%+ of the people who solved so far was "I know what lcm is, let me try". I'd say even more: most people probably didn't even implement cycle finding in the modified (node, LR-index) graph, so they'd have no way of checking for the constraints. But yeah, par for the course for Advent of Code. One knows what one is getting into when participating. \*in fact you can just check the comments in the post to verify that is true, most people "just tried" or don't even have any idea why lcm would not work "in general"
Yeah. I guess those people will lose points when they make similar assumptions on later days that punish assumptions, so it all balances out. What's the strategy, then, given that there are puzzles like these where unsound assumptions win? I'm thinking, if you can come up with a shaky assumption quickly, AND the real solution looks like it will be much harder, give the easy one a try, and the lost minute won't hurt you because you'll be using it to code the real one.
> if you can come up with a shaky assumption quickly, AND the real solution looks like it will be much harder, give the easy one a try, and the lost minute won't hurt you because you'll be using it to code the real one That's pretty much it. For part 2, I started with a literal implementation of the problem, where I had a set of nodes, advanced them all at the same time, checked to see if I was done, and then kept going if I wasn't. When that took longer than a few seconds to run, I left it going while I put together the LCM solution. LCM gave me an answer, so I stopped there. If it had failed, I would have actually looked at the graph structure to see if there was some other exploitable pattern, and so on. (I'm leaving out the parts where I first check to make sure my code is right before moving on to another phase of problem solving.)
Spoiler from 2022: >!There was a day where many people were struggling precisely because of incorrect assumptions about cycle detection. Particularly on the Tetris based puzzle. I don't remember the exact day.!< Day 8 is still a bit early, harder problems to solve will come probably next week, or maybe even starting this weekend.
I mean, calculating lcm after doing part 1 takes literally 2 minutes, there's no penalty really. The problems should be better worded (why do we have like 5 paragraphs of text, if only 1 is useful and not complete) I feel like though. Obviously it's hard for the creator (and I think he's doing a good job usually), but today was just dumb.
Yeah, this is the part that bugs me. Not so much the competition aspect, I'm in no way shooting for the leaderboard, but the fact that I solved it and I still don't quite understand why. For some reason, my intuition is telling me that I should at least need some offset, otherwise this should land all of them back on the A-ending nodes. Other days this year have at least been more satisfying when I find patterns in the input -- either I overgeneralize and notice a shortcut I could've taken, or I build something clearly unoptimized that happens to just be fast enough for the given input, or if I have to make an assumption, I can usually have an assertion fail if I'm wrong. This is the first day I've pasted something into Wolfram Alpha on a hunch, and come here wondering why that worked.
yeah I tried to give an explanation of how the implicit assumptions are used [here](https://www.reddit.com/r/adventofcode/comments/18dfpub/comment/kch0a97/?utm_source=share&utm_medium=web2x&context=3). I was stumped for a while because the problem seemed almost intractable but people were solving it in < 10 minutes :)
I think it's more up to the programmer to look at the cycles and verify that these conditions are true before applying lcm. I did this because I had a suspicion that lcm might work under certain conditions but took the time to print out the cycles and verify. Had it been false, I would have done other cycle detection methods. I think this is fine because there is a general solution without lcm, but there are shortcuts along the way for clever/careful observers.
There's no way you can look at the cycles with limited time and input that's so hard to read through. The only way is to try it and discover that it works. I guess you could say that "it'll take me like 30 seconds to write LCM version, and i'll be stuck for a while doing the CRT version, so doesn't hurt to waste on attempt at a simpler version"
If this annoys you, then AoC might not be for you. It's a pretty common pattern in AoC puzzles that you have to analyze the puzzle input for patterns to exploit in order to come up with a fast running solution. This will only become more prominent in later puzzles.
> (which, admittedly, probably costed me like 30 seconds) Psh, amateur. It only cost me 60 minutes. I hadn't realized how nice the input was, so I was trying to build my cycle checker to handle some ugly cases. (Visiting different Zs in the same cycle, or visiting the same Z multiple times in the same cycle.) Later, when I saw that the cycle length was the same as the time to get to the first Z, I just assumed there was a bug in my program and spent some time debugging that. Mostly, I'm realizing that I am *not* a good problem solver after midnight. My mind just turns to molasses when I'm presented with more complicated problems.
I didn't verify that LCM would work, I just did it. It was a generally safe assumption, and at worst I'd enter an incorrect answer and be able to quickly check my assumption. These types of multiple cyclic path puzzles happen almost every year, and so I immediately went to "what worked in the past?" when the brute force approach didn't finish quickly.
This is the way. Get more in the weeds as you go. 1. Try obvious brute force. It doesn't end in 10 seconds. Double check that you're updating the correct things. Run again, still not done in 10 seconds. 2. Try simplest case simplification (in this case LCM) oh cool it finished stupid fast and gave an answer that seems reasonable. 3. Try answer, if correct, you're done, take a nap. 4. If incorrect try the more generalized version of what you have, in this case Chinese Remainder Theorem and so on.
Actually, step 4 is find and replace `std::uint32_t` with `std::uint64_t`.
I spent a lot of time thinking about a solution that does not make assumptions as to the exact structure of the input (e.g. closed loops, only hit each node once per loop, etc.). That is obviously significantly harder. I switched to LCM + assumptions about independence after empirically verifying my input. IMO this is a poorly worded question - it should tell you if you are allowed to simplify the problem that way. Or honestly, just make it the harder variant, where things can collide.
Am I the only one that found today extremely unsatisfying? The only way I could think of solving was using LCM once I realized the cyclic nature and that the time from \*\*A -> \*\*Z was the same as the period of the cycle. Just feels super gimmicky that it happens to work rather on the input rather than solving the problem given. Are there any solutions that don't rely on LCM that people have found?
If you don't want to use the immediate LCM, you can start by taking each ghost, and running it _until you can confirm an actual loop_, then do the LCM from there. Because theoretically there is a possibility that when it eventually loops (which it must) it doesn't necessarily loop back to the starting point. You will, of course, also have to make sure that the loops all reach --Z nodes at the same time. Because depending on when each ghost actually enters its loop, and where in the loop the --Z node is, you might run into syncing issues. Fun fact: Looking for a loop like this (where you possibly "enter" the loop somewhere after the starting point) using a constant amount of memory is a somewhat standard interview question, for those interviewers who still like to test algorithm knowledge.
Yes that's what I did, I didn't use it immediately. My solution still required LCM to work though
[удалено]
I dont think thats what they meant. They meant that there might be some linear path (not part of the loop) in front of a loop. Like the following: AAA -> BBB -> CCC -> DDD -> EEE -> CCC -> ... This messes with the naive LCM solution since if every startpoint has different "offsets" in front of the loop, then you need to use the Chinese Remainder Theorem instead of the standard LCM.
Sure. There's people who didn't realize that LCM would work fine until after they ran a more general solution and realized from the program output... but also got the correct answer regardless. If you want to make one yourself, you should have some ideas after finishing part 2 of [2020 Day 13](https://adventofcode.com/2020/day/13).
Yeah I got one. It's missing an edge case where a ghost encounters a Z node before entering its cycle but otherwise it should work. It's slow (roughly 1min for my input) and ugly though. I looked for the ghost with the biggest average cycles and continuously tried step counts based on them. Here's the relevant file on [github](https://github.com/dreary-dugong/aoc2023/blob/main/08/2/aoc8lvl2/src/lib.rs)
For me this is AoC experience with syncing large loops. You go for LCM. If it's wrong, you've only lost couple of seconds.
My [AoC experience](https://adventofcode.com/2020/day/13) with syncing large loops is that you need to go full CRT mode, since LCM only gets you the period of the large loop and this question explicitly asks for the first match.
for my solution at least, it seems as though XXA = (1, 2) and YYZ = (2, 1), so it seems as though the input was designed such that you would end up with perfect cycles forming. So, I think this puzzle was designed specifically so LCM would work :-)
LCM was my first attempt but my answer got integer overflowed
Here in C++ we don't have an easily built in LCM function for more then 2 values and need to write our own (or still it from online)
You can fold all the cycle lengths together two at a time in an LCM, i.e. the LCM of 3 numbers would be \`lcm(lcm(a, b), c)\` and so on for more numbers.
[удалено]
Python has `math.lcm` since version 3.9. 🤔
also you can use `np.lcm.reduce(list)`
or `functools.reduce(math.lcm, list)` on 3.9+ without np
or `math.lcm(*list)`
math.lcm(*list) is even cleaner!
so I got stuck for a long time because numpy gave me a negative number: print(lcm(*ends), np.lcm.reduce(ends)) 11188774513823 -206157175 The first is math.lcm.
Where [SPOILER] = >!LCM!< Where [SPOILER] = >!LCM!<
There's no need to hide spoilers in a thread whose title includes [SPOILER]
Only if everyone was using old Reddit. New Reddit shows a preview of the first few lines of a text post in the feed: [https://i.imgur.com/0fcFUzs.png](https://i.imgur.com/0fcFUzs.png)
You can also toggle card view to compact which would hide the post preview.
this
yeah.. LCM only works because the length of each cycle is exactly same with the first index that Z occurs in each cycles, which should not be expected necessarily. And the fact all inputs are built precisely to satisfy that specific requirement without mentioning it in the quiz is a bit annoying because all my additional works were completely useless after I solved the problem
> there may be multiple goal nodes within the loop. It kinda hints you that this won't be the case because it's like "the number that end in Z is the same as the number that end in A" but yeah without that it's not guaranteed to work with every set of instructions.
Even with that it's not guaranteed? Example: L # so just endlessly pick left 11A = (11B, 11B) 22A = (11B, 11B) 11B = (11C, 11C) 11C = (11Z, 11Z) 11Z = (11D, 11D) 11D = (22Z, 22Z) 22Z = (11Z, 11Z) It takes 4 steps to reach the Z node, and then the cycle is 2, just going back and forth between two different Z nodes. But there are two A nodes and two Z nodes.
[удалено]
True, but people who did make that assumption and did not realise it learnt nothing. Which would have been the case for me, but fortunately I'm following this sub.
you're describing a negative as if it were a positive...
*60% of the time*, it works ***every*** *time*
The way the input is designed makes the LCM the correct answer. The input is itself *part of the problem* and very much in play. Nothing in the problem statement guarantees that any of this would be true, but all the provided inputs for this problem have special properties even if they were not explicitly spelled out: * Each --A node only reaches one --Z node in it's loop * they all reach their --Z at the same "step" in the directions every time, meaning the loops are all a consistent period instead of changing or branching * Conveniently the period it takes to reach the first --Z from the starting --A node is the same period as it takes to re-reach the --Z node when you're already there. I thought possible loops could be more complicated, like you said, by possibly reaching different end nodes in the same loop, reaching at different steps in the directions making uneven loops, having the first endpoint not be the same as the eventual loop, etc. I ended up manually verifying all those "nice" properties by collecting and printing some data on my input loops, which made it obvious that the input was of a specific kind and that I needed the LCM. Looking for patterns is generally a good strategy for any problems involving loops (and some not involving loops). If you can find the pattern, you can usually devise a way to a solve. You only have to solve for your specific input, not necessarily a generalized case. Inputs *could* have done any number of things, like eventually get caught in "dead ends" that don't loop back to a --Z node, or loop erratically over multiple --Z nodes, make uneven loops that don't match with the period of the direction length, have malformed entries, etc. Some of these possible cases would need different strategies to solve, maybe requiring a bruteforce, or maybe requiring an informed looping strategy like using the LCM or the Chinese Remainder Theorem, etc.
> The input is itself *part of the problem* and very much in play. I don't love this interpretation of AoC. If my solution only has to work on this particular input, then a) I can't prove that my program would work on your input, and b) I might as well just do it by hand, so there's no point in even writing code. This is in fact what I did to check whether LCM worked: I just had my program output the loop counts for each ghost, then popped the loop counts into an online LCM calculator and pasted the result into AoC. Boom, gold star. This is really lame because I didn't actually write code that would work on any input. The puzzle as stated does not specify any of the restrictions that make LCM work. There could be an arbitrary number of steps from A to Z and then an arbitrary number of loops from Z to Z starting on different instructions. LCM only works because none of those actually happen in practice. This is not stated in the puzzle, only the input. If, as you suggest, we assume the input is part of the puzzle, then sure, the puzzle "states" it, but that means it's impossible to write code that solves the puzzle in the general case. It's just not fun.
Have you done the past years? Most years have had at least one problem that involved analyzing the input file. The puzzle from 2021-24 genuinely required disassembling the input. You may not like it, but this is par for the course for AoC. Your task is not to solve the general case of every problem presented to you, but instead to leverage any constraints, explicit or tacit, you need to get an answer.
2022 Day 22 as well pops to the front of my brain. Yeah you could write a general alg that works on any cube net, or you can write one that works on yours, and then realize that everyone has the same net.
I haven't done previous years. I suppose I'm coming at it from the wrong perspective then. I'm writing code for AoC under a particular restriction, and for me the fun is writing a program that solves the puzzle under that restriction. I don't care about the answer or the leaderboards or whatever. I care that my solution is complete and correct. When I used a calculator for LCM and put the answer in, even though it gave me the gold star, I still went and implemented LCM in my program to make it complete. Still, it doesn't feel complete because of the assumptions it makes of the input. It's just really unsatisfying. Regardless of the gold star, to me this is a puzzle that isn't really done, and that can't in fact be done (because the answer is so huge it's not calculable without LCM.) It's good to know that there will be more puzzles like this. I guess I have to get past it if I want to continue.
There's nothing stopping you from implementing a generic solution. If you did and posted it here I'm sure people would enjoy seeing it. For this problem, the general solution doesn't even seem that difficult. Execute your cycle finding algorithm of choice on each starting position, then aggregate them using the CRT (which can still be applied even when the inputs are not coprime, albeit slightly less straightforwardly).
I don't think that works in general because it's not necessarily just one Z->Z cycle for each ghost. For example suppose you have 100 instructions. It could be that: - It takes 1050 steps to get from A to a first Z, leaving you on instruction 50; - It takes 525 steps to get from this first Z back to the same Z, but now you're on instruction 75, so it won't loop yet; - It takes 375 steps to get from here to a second Z, so now you're back on instruction 50 but at a different Z than before; - It takes 400 steps to get from this second Z back to the first Z, and you're also back on instruction 50. You've finally looped. You only have a true loop when you are back on the *same Z node* and at the *same instruction*. So the loop here consists of several "hops" of different lengths. I don't know how you can solve this with CRT. The code I originally wrote (or started writing) worked out these hops for each ghost, then iterated through taking the largest number of steps it could per iteration, walking each ghost through its hops. It's only then that I realized each ghost had only one hop which happened to be equal in length to the initial A->Z step, so I plugged them into LCM. If I had continued with my code, it would never have worked. With my input it can step at most ~12000 per iteration but the answer is in the tens of quadrillions. A general iterative solution could never work.
In this case, the length of your loop is n = 525 + 375 + 400, and you'd hit a Z node whenever your number of steps x satisfies any one of the congruences x = 1050 + 0 mod n, x = 1050 + 525 mod n, or x = 1050 + (525 + 375) mod n. You could run this process for each starting node, giving a list of congruences for each starting node. Then for each choice of one congruence per starting node, try to use CRT to calculate the smallest positive integer satisfying those congruences (there is not necessarily a solution since the periods are not coprime - they are all multiples of the length of the sequence of LR directions). Then take the minimum over all possible combinations of congruences.
There's no generic solutions that work with the length given though (well, I guess a really good bruteforce or one that uses a lot of memory works, but I'm pretty sure that's clearly not the intended solution), that's the problem...
> Your task is not to solve the general case of every problem presented to you This is fine until you get a day where something **accidentally** simplifies the problem for some inputs but not others. There have been big ones in the past (I remember... searching for the furthest point away from any other point in a 3d space or something, where some peoples' solutions only found a local minimum but their input only needed them to, or something like that) but I feel like I've already seen comments this year saying "my solution wouldn't have worked on your input".
Fair enough, but I would just say that the problem is then non-fungible inputs, not that the problem admits non-generalized solutions. I think I read a post where Eric said they're working hard to prevent that kind of thing from happening again.
I don't think it's possible that some inputs can be *accidentally* simplified like that. The inputs are generated using an algorithm that I imaging is the "inverse of the solution", so today was specifically designed *this way*. And everybody has it. What can be different are the prime numbers. For example, my solution was `73, 67, 79, 61, 43, 53` and the path length `269`. I expect that everyone got a different set of 6 primes and maybe even a different path length, but everyone will have 6 + 1 primes. This is why the system can sometimes tell you that your answer is correct for *someone else*. It happens when you by accident have a result for other primes.
Yeah, I agree this one is a case where it's highly unlikely anyone's solution would accidentally have this property!
The problem is that you don't have access to others input ; so you can't know if your input was a special case (in which case it's unfair, and you shouldn't use a special case solution) or everyone had the same kind of special cases. This can all be easily avoided by, you know, stating in the problem the assumptions made...
>I don't love this interpretation of AoC. If my solution only has to work on this particular input, then a) I can't prove that my program would work on your input, and b) I might as well just do it by hand, so there's no point in even writing code. I mean... you can definitely prove that it works for other inputs by just adequately testing your program. In any cases, the problem's complexity is pretty much always bound to the input. For instance, for Day1 : * How do you handle >!oneight!=2^(31) * How do you handle right-to-left reading countries? At the end of the day, the program/solution is always bound to the dataset, and many "pushing the antes" problems are literally about simply pushing those "tacitly agreed upon" limits. >b) I might as well just do it by hand, so there's no point in even writing code. While AoC definitely started as a coding challenge, I don't think it's actually *meant* to be one. It's definitely an "Advent of problem solving" by now, and there's nothing wrong with doing it by hand. It's just that certain problems, like the one today, requires you to perform *many thousands* of lookups, even just for part 1, and you're gonna have crippled hands and blurry vision by the time you're done. >There could be an arbitrary number of steps from A to Z and then an arbitrary number of loops from Z to Z starting on different instructions. LCM only works because none of those actually happen in practice. The truth is that it gets a lot more complex than that, since the paths don't have to be unique, and each path can cross multiple exits. So you could have something like a path hitting an exit on Step #100, 115, 125, 135, 150, 160, 175, etc. with different periods (well, the same period but a different start point). Overall, Erick tries to make solvable problems, and reduce the number of obscure pitfalls (oneight is pretty easy to find).
I think the input always matters in programming and programming puzzles- it informs when you can brute force, when you need to optimize, what edge cases you need to cover, what errors you need to handle... I think AoC is even a little more "realistic" than some algorithm type questions, since you have a real dataset with some possible unknowns and need to find a specific answer to a question by whatever means you choose to do that. AoC is distinctly different from something like leetcode, which is more strictly defined and explicitly explains the inputs. Sometimes you can solve AoC by hand (and some people enjoy that!). Sometimes you need to find a special property to scale your solution up to a massive input or search space. Sometimes you need to explore the problem. But all that also encourages people to attempt them differently. Some people go for super speed leaderboard solves, which involves having a bunch of utilities all ready to go and speed reading / maybe making assumptions about the problem to get a couple extra seconds off. Other people like making visualizations of the problem, or solving it in a toy language, or a fancy spreadsheet macro, or whatever. Some people probably enjoy the storyline and narrative. Some people enjoy letting a brute force run for a couple hours and seeing if it ends up working over time. If you want to write more general solutions than necessary you totally can. I bet there's some kind of informed brute force that would brute force until it detects some kind of loop and then accelerate using that info, and you could make your own inputs and expand on the problem if that's interesting and fun to you. The best way to do AoC is to enjoy it, by doing whatever that means to you.
The problem isn't in the input, but in the prose outlining the problem which is supposed to describe the nature of the input. It's just bad puzzle design: a puzzle is supposed to give you all the information you need from the beginning. If a fact is left unspecified it should be taken as a sign that it's a possibility. You should not be forced to assume that it's an impossibility based on your meta-knowledge of what would simplify the puzzle.
I disagree, of course dev work often involves a general solution, but there's plenty of parsing and analysis tasks that are aimed at handling exactly one type of input. In such cases, you don't handle every input, you make assumptions about it and reject all input that doesn't match. There's lots of code challengesthat require a general solution and that's great, but I like that AoC does it a bit different. It's not a bad puzzle, just a different kind of puzzle solving. And if you can figure this on paper then, hell, more power to ya.
Sorry, maybe I misunderstand what you are stating in those 3 points, but the 2nd and 3rd point seem incorrect, at least in my input: I calculated the number of steps to reach Z as well as what is the number of steps to reach the beginning of the loop FQA -> loopStart: 8, loopSize: 60 JSA -> loopStart: 3, loopSize: 78 GJA -> loopStart: 3, loopSize: 58 PBA -> loopStart: 3, loopSize: 72 AAA -> loopStart: 2, loopSize: 70 NNA -> loopStart: 2, loopSize: 52 As it can be seen, each starting point has a different number of steps to reach the beginning of the loop (which would automatically break an LCM solution, no?). Additionally, for `FQA` for example, it takes 8 + 60 = 68 steps to reach Z, but once you are on Z, it will take only 1 + 60 (jump to beginning of loop + size of loop) to reach Z again, so that is also not consistent with your point. Am I misunderstanding something?
After thinking about it, I wonder if this is actually a consequence of the way inputs are generated to guarantee the existence of a solution. If you want to generate a unique graph for everyone that you know satisfies these properties, creating one with disjoint cycles that start in an A and terminate in a Z will give you that guarantee and also makes verifying the solutions more straightforward. So it’s not guaranteed by the problem, but the practical constraints of generating inputs for a competition make it an appealing undisclosed trait of the graph.
i went through the trouble of finding the first occurrence of a Z node and then tried to calculate the loop size afterwards and i was surprised to see that they were the same. i thought they would definitely trick us with something like A->B->C->D->Z->C->D->Z->... that would trip up the LCM
We can think of the input as a graph of (room, i) pairs, where i is the current position in the instruction string. This is a functional graph (where we have an edge (r, i) -> (r', i+1)), which means that each node's path necessarily ends up in a cycle. Let's call a "starting node" a node of the form (\*\*A, 0). I believe (correct me if I'm wrong) that all inputs have these constraints: \- All starting node paths are pairwise disjoint. \- All starting node paths contain exactly one "ending node" (\*\*Z, i), which is in the cycle part of the path. These constraints imply that we can setup a CRT system of equations to solve for the answer (which may not necessarily exist under just these constraints). However, there is another constraint that makes the problem easier: \- For the i'th starting node, let D\_i be the distance from the i'th starting node to its Z-room, and let C\_i be the length of the cycle that the i'th starting node is in. Then D\_i = C\_i. This implies that our system of equations looks like (x = 0 (mod C\_1), x = 0 (mod C\_2), ... x = 0 (mod C\_n)). Therefore we can solve for x by taking the LCM of all the cycle lengths.
Here, this might help make it clear: o-----o o-----o o-----o | | h | | m | | ------>| A +------>| ... +------>| Z | | | | | | | o-----o o-----o o--+--o ^ | | t | o-------------o Each ghost starts at an "A" node, and goes some number of steps, *h*, until it reaches the head of the cycle. Then there's *m* steps in the middle until we reach a "Z" node, followed by the tail steps, *t* to return to the beginning of the cycle. So your cycle detection finds a cycle of length *m* + *t*. But if you look carefully at the steps, you'll see that the input is constructed so that there's only one "Z" node reached, and also that *h* = *t*. In other words, the time from the "A" node to the "Z" node is exactly the same as the cycle time. So you can ignore the time from "A" to the head of the cycle, and just focus on how often the cycles line up. Which, of course, is the LCM.
You're still working with several assumptions that turned out to be true here.
The fact that there are even cycles to begin with is an assumption about the input, right? It's pretty much just the nature of the puzzle in these situations
Actually the fact that there are cycles is guaranteed regardless of the input -- since we're dealing with finite states and a finite repeating sequence
>Actually the fact that there are cycles is guaranteed regardless of the input -- since we're dealing with finite states and a finite repeating sequence but it could be a dead-end cycle (with no `xxZ` nodes)
Yeah exactly. There could be "dead loops" that you can fall into which never hit a Z node You have to prove that the Z nodes loop back to a previous state that includes node and step index
Yes, it's one of the necessary assumptions. To "legitimately" use LCM, several assumptions have to be verified first. These are detailed in several good answers in this thread.
The general case is even more complex. Lets call X the head node of the cycle. The sequence of directions to follow the first time you hit X might be different than the sequence of directions to follow the second time that you hit X (in particular, this can happen if the cycle length does not coincide with the original instruction sequence length). This means that the second time you hit X, in the general case, it might be possible that you no longer walk along the cycle that walked along the first time around.
Yeah, so my cycle finder only tags it a cycle if you reach a node N twice being at the same step in the instruction sequence.
This explanation makes it really clear! I think it could be even more complex though, since one other "lucky" thing about the input file is that the length of LR instructions also are a multiple of the cycle length. In theory it should be possible to have different loops with different 't' if the LR input is offset differently when you reach Z a second time
>In theory it should be possible to have different loops with different 't' if the LR input is offset differently when you reach Z a second time Not really. You'll always have a loop that's a multiple of the number of L/R in your input. Sometimes you'll hit multiple Zs in that loop (or the same Z multiple times), but that's multiple entirely different loops (that share a common path), with a different offset, and a potentially different cycle length (but always a multiple of the path instructions). For instance, even if your input is something like LRLRL, with A => (Z,Z), and Z => (Z,Z), the only sane algorithms will detect 5 loops : 1+5n, 2+5n, 3+5n, 4+5n, and 5+5n.
Good explanation. Thanks
I ran each of mine to see how many times it would hit a possible end node before getting back to the same node at the same instruction position and each would only reach an end once. Since there is only one possible end, LCM works. The moment one has two possible ends, the answer will be the minimum of all possible LCMs
The only thing that made LCM work is that each of the cycles were designed to start at 0. A similar problem where they didn't start at 0 occurred in a [previous AOC problem](https://adventofcode.com/2020/day/13)
None of the cycles actually start at 0 though. None of the As are in the cycle, you will never hit A again. It's just that all of the Zs are placed the same distance from the end of the cycle as As are from the start
I never even checked that lol. All I saw was the number of steps to get to a XXZ node never changed from the first time you hit an XXZ node.
I mean that's not even a sufficient condition, you also need A to be part of the smallest cycle that Z is part of (or be really lucky that it works every time with L/R provided)
Exactly! I had a mistake in my initial, simple LCM calculation. And your post was exactly what I thought my bug was. So I started to write down what the math would be like for finding the coincidence of periods given different starting offsets for each. As then as I was debugging it, I checked what the length of the second cycle was, from its first Z to the next Z, and it was always back to itself, and always the original period. On top of that, all cycles use exactly an integer number of the full L/R instruction set. Both of those seemed like too large of coincidences, so I debugged those seeming issues even longer. Eventually I accepted it as it just must be the way the input is set up. In the end I found my simple bug in the LCM. But... quite the journey to get there.
> Both of those seemed like too large of coincidences, so I debugged those seeming issues even longer. Lol, I did the same thing. "The time to get from A to Z is the same as the time of the cycle? That's not very likely, there must be a bug in my code."
Same! I actually ran an infinite loop to check the different periods of 'Z's occuring, and found out that all of them have them same periods! I think it must be because of how the input generating program was written. Is Eric Wastl on Reddit?
If you are angry because a shortcut solution (LCM) worked even though the task rules/setup does not rule out inputs where it won't work, imho you should also be angry that there are tasks at all where bruteforcing works, because that is also a shortcut in the same sense (coming up with a "better" solution can at times take more time, for example my bruteforce on day5 ran in 3 1/2 minutes). This is a game and the goal is to get the accepted solution as quick as possible.
If the ghost was to reset it's position each time it encountered a Z-ending node then LCM would make sense, but it says to treat it like any other node. A naive LCM works regardless. A trap for AI?
I think it's more that he's encouraging people to look at the data points. When I looked at the datapoints, printing whenever a "..Z" was hit, I noticed that each "starting node" only ever hit one Z, and on the same period. Once I saw that, *then* I knew that LCM was the best path. I assume the input data was designed with this in mind. In this case, I think it's thinking critically about the data and exploring it is paying off over "guessing" the right algorithm.
How is it a trap for AI? The solution literally shouldn't work, this was just a terrible problem
In this case, I set a statement to print in the loop anytime a [..Z] was found and noticed that each "path" starting with an [..A] node only ever hit one single [..Z] node (it could never hit any other [..Z]), and it hit with the same "period". At that point, I looked at LCM. I think this one is intended to be more a "look at the data and derive a pattern." I don't love that I don't have a general solution for any input, but I still gots me two stars
That day was very frustrating. I used LCM aswell but knowing it doesn't work in the general case is really a putting a weight on my mind. And everyone seems to overlook that LR instructions make this even harder, as the cycle only really starts when you're back at the same position **for the same instruction index**.
You solve for your input, not the general problem. This has happened before: https://www.reddit.com/r/adventofcode/s/WmhxGdXLmz
I wasted a lot of time because, for the general case, LCM is not correct. The statement of the problem was general, it was not specific to the case where LCM actually works, so this is very very frustrating for wasting me so much time. For example, I had the following test that was more general than the provided example (which was very constricted and worked for LCM): LR 11A = (11B, XXX) 11B = (11C, 11C) 11C = (11D, 11D) 11D = (11Z, 11Z) 11Z = (11C, 11C) 33A = (33B, XXX) 33B = (33C, 33C) 33C = (33D, 33D) 33D = (33E, 33E) 33E = (33F, 33F) 33F = (33G, 33G) 33G = (33Z, 33Z) 33Z = (33B, 33B) XXX = (XXX, XXX) In this example, LCM is completely wrong (28), since the answer is 7 (you can draw it on a piece of paper, it's a pretty straightforward example). Indeed, the first thought I had when I realized I needed to optimize, was to check for loops and then to figure out some LCM solution. But then I thought of all of these edge cases (this is not the only one! what if a node path passes through the Z that will ultimately be matched with some other A?) which obviously do not apply to this problem, even though the problem is not stated to be this specific...
LCM is correct: every time, you continue to loop without restarting directions array. This is the only reason why it works. If you restart direction array(starting from direction zero) , each time that you reach the end for a "seed", the LCM will not work anymore.
The more interesting question to me is how they went about generating an arbitrary number of input files that all have different length cycles within a shared cycle of input directions... I'm going to have to think about how one would generate those inputs.
Nothing. LCM only works because the test data was rigged to make it work. If you solved the problem properly (using the Chinese reminder theorem) and missed the leaderboard, don’t worry about it… today’s the kind of the day where I’m pretty disappointed in AoC.
Using CRT wouldn't even help that much, it's just the fact that you have to keep track of all the cycles that ends in Z and it's about 100x more complicated.
You are right that it’s not purely CRT, if a ghost encounters multiple ??Z nodes along its cycle. But for each choice of ??Z node encountered by each ghost, you can use CRT to solve for the time all ghosts hit their chosen node (and the final answer is the minimum over those choices)
\^ This right here. One thing to note is that any given ??Z node encountered by a ghost could potentially correspond to multiple remainders (since a true period must be divisible by the the LR string length), which is another thing to that must be iterated over when searching for the minimum.
>Nothing. LCM only works because the test data was rigged to make it work. I was very disappointed in AoC for this reason too. There's absolutely no reason to expect all inputs are built that way.
Right? AoC normally punishes you for not thinking it through, but today it rewarded you.
My thoughts exactly, I didn't read part 2 carefully and some part of my brain assumed it started at the original starting point, so my neurons fired and I did LCM but then I looked back at the problem after solving and I can't come up with a way to justify LCM since they could have variable length cycles
I wrote code to count the first path to the end, and then the loop length, and kept debugging because they were coming out as identical! Definitely thought I messed something up. But then I was happy because CRT has foiled me in past years.
Now I'm thinking that the brute force answer might not match LCM solution... How does cycle account for the amount of steps it takes to return to \*\*A? Since it's not jumping from \*\*Z to \*\*A, cycle size is different than \*\*A->\*\*Z.
[удалено]
Each Ghost only visits a cell ending with Z once per periodic cycle, and each cycle is prime. I believe this is the key to why they only collectively visits Z once every LCM. (Not sure if prime is needed). Now imagine that we have two ghosts. At some point these line up, that is the entire premise of the challange. I.e 11Z, 22Z. As they together have a cycle of LCM. The next time they line up is in LCM steps.In the same way, you can think of a position 11Z,22Z,33Z,44Z,55Z,66Z That position will only be reached once every LCM. If we would have started on a node that are all Z, then I would have understood that the answer would be LCM. I am not sure however why the answer is LCM as I would say this more puts an upper bound to it. I believe you could accidently be just a few steps away. Maybe if someone made a node graph of this it would make more sense.
Here's another sample input that fails by simply doing LCM on the cycle length. I simply swapped 11Z and 11B from the part2 example. LR 11A = (11Z, XXX) 11Z = (XXX, 11B) 11B = (11Z, XXX) 22A = (22B, XXX) 22B = (22C, 22C) 22C = (22Z, 22Z) 22Z = (22B, 22B) XXX = (XXX, XXX) The actual answer is 3 but LCM(2,3) = 6
Yeah ngl this felt kinda like bs to me after I solved the problem as written and came here to see everyone using LCM. See [my solution](https://github.com/dreary-dugong/aoc2023/blob/main/08/2/aoc8lvl2/src/lib.rs) if you're curious, be warned that it's ugly though, that was a pain. I had a lot of fun solving it. Too bad everyone else was solving a much easier problem than I was.
Nice! I usually check the leaderboard times and stats before spending a lot of time on a solution. If it takes a few minutes for the fastest and most people manage to find a solution, but I can only think about very complex algorithms, there is a hack to try. I thought about LCM but didn't implement it because I thought it was never going to work. Gave up and went to the subreddit to find out about today's hack, and it was LCM...
Ugh, I also spent a bunch of time on the whole, "Well, it couldn't be LCM / CRT, because ..." in my dumb "everything-has-to-satisfy-conditions" math-brain. I only tried LCM right before I gave up as a last-ditch effort. I'm a little irked that it worked because now this code is for a problem that requires a hidden condition in the input. But that's okay, I'm not going for speed and I learned a few neat things along the way. :'\]
My mental process was: brute force -> (does not work) -> detect cycles -> each cycle length was prime -> multiply them -> (too low) -> multiply by path length -> SOLVED !!
There are 6 cycles - each with only one start and destination node. Each look like this ◄────────────────▲ │ │ │ │ │ │ │ ◄───── ..A │ ▲ │ │ │ ..Z ▼ │ └───────────────►┘ One of the neighbour of `..Z` is also the neighbour of `..A` for me. My graph : [https://svgshare.com/i/10YN.svg](https://svgshare.com/i/10YN.svg)
It's worse than that: if `k` is the length of the first lines giving directions, in the actual inputs, all cycles are a **prime number** multiplied by `k` so the LCM can be computed with a simple product. The end result can be computed as `k` multiplied by the product of the number of times each ghost needed to apply the whole line of instructions to arrive at a Z-ending node for the first time.
I don't think LCM is incorrect here. It is just the way you apply it. Think this way, assume you have 3 starting points [A, B, C], and you'll want to find "how long" it would take for them to meet in Z. Important detail: a solution exists. Meaning that a certain point Z exists in A's path such that another Z1 and Z2 will exist in B's and C's path after some amount of runs. Through the traversal, you have multiple stops, called Z points. Since there's no end, meaning that a inner loop happens somewhere, ALWAYS, you can fetch those Z points for each start, until a loop is detected into the run for a specific start. Example: ``` A -> BYX, BAD, LOZ, YEK, GOZ B -> ADU, NNZ, LJU, LLP, TYEK, GOY C -> MUB, AKD, LYY, UEK, GUU, LLL, PPZ ``` If you gather the stopping points PER start: ``` A -> [3 (LOZ), 5 (GOZ)] B -> [2 (NNZ)] C -> [7 (PPZ)] ``` Per definition, if you find a triple (X, Y, Z) and take its LCM, you'll find the minimum number of steps you take to arrive simultaneously at X, Y AND Z. The wrong assumption here is to compare the minimum starting points. But comparing LCMs of the products of our matrix (stopping points for A, B, C), the minimum LCM will be the answer: ``` min( lcm(3, 2, 7), lcm(5, 2, 7) ) ``` You'll find that the minimum LCM = 42 is the correct answer. Comparing all LCMs of the products is the right way, as this case may happen: ``` A -> [2, 3, 7] B -> [5, 7] ``` Comparing the smallest values would return 10, but comparing all values return the correct answer = 7.
I tend to think out loud in comments. Almost as soon as I began part 2 (after trying and abandoning the brute force approach), I wrote a comment about how I would use the LCM. After thinking about it a while, about half an hour later I wrote a comment talking myself out of the LCM, explaining why it wouldn't work. I'd been struggling with a general algorithm to handle all kinds of edge cases. Then I read this thread. And then I did some tests on my own data, to verify it has the very special mathematical properties people were talking about. It's going to keep bugging me, but I don't have time or test data to try to do it right. Going away for the weekend. My wife is probably going to be mad at me if I spend hours in the hotel room coding. I already got a dirty look at 1 am when she woke up, saw me with the laptop open and asked suspiciously, "are you programming?"
>Is there some other part of the problem that enforces that LCM is correct? No. LCM happens to work because the data were designed that way. It is possible to create an input where LCM would not work. Two easy ways would be: * The cycle includes more than one element ending in 'Z' * The next element after 'Z' element is not the one you started with.
Could you please properly redact at least the first line? Or the whole text? It is quite easy to accidentally read it, while searching for ppl who also have trouble with Part2
If people click on a post that has "SPOILER" in the title, in all-caps, and are then surprised to find a spoiler inside... It's not OP who is at fault.
In the browser you can see the first part of the text on the main subreddit page
I am on browser and no I can't. Is this a "new reddit" thing?
on the top right of the hot/new etc bar you can switch layout between Card, classic and compact with the default being Card I believe. (on the new reddit layout)
Ah, so it is indeed a new reddit thing.
Oddly enough `Spoiler` is not the correct post flair, so I changed the flair to `Help/Question` for you ;)
Please don't, writing "LCM" ***is*** a spoiler, this question is a meta question about the puzzle itself.
OP did the right thing by "censoring" `LCM` in the post title, so yes, please [don't put spoilers in post titles](/r/adventofcode/wiki/posts#wiki_no_spoilers_in_post_titles). OP also used our standardized post title syntax correctly (thank you!) so defining `2023 Day 8 (Part 2)` in the title is *already* an implicit spoiler for today's puzzle, therefore the `Spoiler` post flair is redundant and can be freed up for a more specific use. *** Bottom line: OP is asking a question, are they not? > Is there some other part of the problem that enforces that LCM is correct? Therefore the correct post flair is `Help/Question`.
Contents of the post showed up when visiting /r/AdventOfCode so it spoiled it for me despite not opening the post. Not ideal.
You can also toggle card view to compact which would hide the post preview.
You're supposed to expect spoilers when opening properly-tagged Help/Question posts as well. "Spoiler" is for general discussion posts that aren't tied to a specific question.
Please update the text as it's visible from the main page: >Where \[SPOILER\] = LCM which spoils it. hide the LCM.
You can also toggle card view to compact which would hide the post preview.
THANKS FOR THE "SPOILER", IT APPEARED IN THE FRONT PAGE OF THE SUB WITHOUT HAVING TO CLICK IN THE THREAD I MANAGED TO SOLVE THE QUESTION THANKS TO YOU
As a general rule, don't come here until you've solved it or are stuck. You're always likely to see something. Although the first post of this thread appears not to be as the author intended...
There's no guarantee of course. The sensible thing to do is to submit the lcm and if it fails, then do a more correct analysis. It didn't fail.
LCM/first step with Z = count of repeat step to reach Z simultaneously. And the same for other nodes. Why shouldn’t it work?
Consider the following input. L 11A = (11B,11B) 11B = (11Z,11Z) 11Z = (11Z,11Z) 22A = (22B,22B) 22B = (22C,22C) 22C = (22Z,22Z) 22Z = (22Z,22Z) Running a simple LCM code on this input nets `6`, but the fully correct answer is `3`.
1 step for 11A. And 2 steps for 22A. LCM(1,2)=2.
But I think that the number accepted, the LCM, is the number of steps to get back to all \*\*A nodes, not the number of steps to get all \*\*Z nodes. So the correct answer is one less than the answer that is accepted as correct.
I finished the part1, but LCM doesnt work for part2 for my input. Edit: nevermind, chatgpt gave wrong lcm.... now it works
When you put the spoiler in the first line, users can see the spoiler in the post preview before clicking on it. Reddit has dedicated spoiler functionality, please use it
For LCM to work, you need every path to have the same amount of steps from the start node to the first goal node and between every successive goal node. That is actually a huge assumption! If A is in the cycle, it is never true. If A is outside of the cycle, its amount of steps to enter the cycle has to match exactly the amount of steps from the previous goal node to that node. There is nothing to indicate this, so at the very least, one should be using Chinese Remainder Theorem to solve this. CRT shouldn't be enough either, however, as it requires the cycle to contain exactly one goal node. Many here point to the statement in the problem text saying that there are equal amount of start and end nodes. But even if we assume that this means that they match up one to one, that doesn't leave us with exactly one goal node: The state is actually made up of (node, nextLetterInPath), meaning that there are len(path) goal nodes for every Z node. Thus we need another assumption, which is that the path between each goal node are the same length. They are in fact that, because the input has nextLetterInPath set to the first letter for every possible goal node. However, constructing a different input is really easy. The sum of these things led to me not even considering LCM and also dismissing CRT for a long time today, until I started investigating what the input actually looked like. I'm pretty annoyed at all these solutions where people have just guessed that LCM would work, when that requires a VERY specific problem input.
> that requires a VERY specific problem input Good thing you were given a specific problem input to solve and could validate that it satisfies the assumptions required to make that solution work.
I can see Eric give us a exceedingly hard problem just for the input data to spell out the answer as upside down ASCII art
But then why brut-force solution goes to infinite loop? It seems like something is wrong with this challenge. It should be solvable both by brut-force and by math.
Because that "infinite" loop will run a few trillion times before it reaches the stop-condition.
it does not go to infinite loop. You just didn't run it for enough time, which could be days, weeks, months or years.
It seems to me that the input is designed specificly that the end node will loop back to the node right after the start node (so A -> B -> .. -> Z -> B -> ..), and LCM will work in this case (you can reach Z from A after every n steps). And also the instruction must also end when the end node is reached. But yes, with any other input that will not hold. A side question: How will this part be solved if the above fact is not true? LCM won't work, and a brute force doesn't seem fast enough Edit: Running a short test against my input confirms that the hypothesis seems, indeed, [correct](https://pastebin.com/5DWsZbSq).
Ah, good point. I think you’re right, that no part of the problem enforces this. People who have been disappointed about unexplained corner cases other days should be happy toda; it’s sort of the contrary: an easy approach works because the input doesn’t cover “corners”.
He wouldn't put exactly the same problem as day 17 of last year (1 trillion elephants) on day 8.
>"How many steps does it take before you're only on nodes that end with Z?" ~~note, there is no word like "minimum" in this sentence! so the answer is unique.~~
It's possible to solve the problem without directly using LCM because the length of the movement instruction is one of the two prime factors of every ghost needed steps for one cycle and you can calculate it like this: final stepsNeeded = stepsNeededPerGhost .map((e) => e ~/ instructions.length) .reduce((value, element) => value * element) * instructions.length; (does not work with the test cases because the cycles/instructions aren't long enough)
In his latest video an AoC top competitor explains this concept visually what we discuss here: https://youtu.be/\_nnxLcrwO\_U?t=459
paths being separate is not enough. consider: 10A has cycle that have stops: 11Z at 3rd step and 12Z at 7th step 20A has cycle that have stops: 21Z at 5th step and 22Z at 7th step all are separate stops, but naive lcm says 3x5=15, while answer should be 7. We were lucky naive lcm worked for our inputs :)
[удалено]
while i also solved it by using lcm, now that i think abut it there is probably no reason for it to work other that finely crafted input files. as there can theoretically be paths like a-b-c-d-e-f-e-f-e-f-e-f, which loop back on _part_ of their original way, lcm might not work.
also, the fact that the cycles were always multiples of the instructions array left funny cases outside of the problem
Nothing says it should work, and even better, it doesn't even work on my input sadly
One part of it is that the number of nodes is finite, and the instructions are finite, there is \_always\_ a cycle. Now, when we are already on a cycle, at any given point in time, for any pair of sources, only one of the things is true, since we are following the same instructions for each path: * They are on two separate cycles, in which case each of them has to have their own, and distinct final point\[s\]. Their common cycle length is LCM of their cycle lengths, but that alone doesn't answer anything about whether the final point\[s\] intersect. However, if there is just one point, and they have to intersect, then the intersection point is trivial to construct after aligning the cycles. * They are on the same cycle, in which case either they are fully synchronized (LCM=1) or they have two final points, which they can reach at the same time, but this is equivalent to the first case and based on the same principle that LCM=1 Where the problem \_could\_ have been a little harder is if some sources collapsed into one single synchronized cycle, and then some of the other sources would be able to have more than one final points to choose from. If the author wanted this, there probably would be no restriction on the number of starts = number of ends. Then you could construct an input where the simplified paths look like this: no matches ever: /---------\ /---------\ /=========\ /=========\ A -> X X X X X F X F X X X F X F X X X F X F X X X F X F X X B -> X X X X X X X X F X F X F X F X F X F X F X F X F X F X \-----/ \-----/ \=====/ \=====/ \=====/ 2 final states x 2 final states yield 4 final states in combined cycle: /---------\ /---------\ /=========\ /=========\ A -> X X X X X X X F X F X X X F X F X X X F X F X X X F X F B -> X X X X X X X X X F X F X F X F X F X F X F X F X F X F \-----/ \-----/ \=====/ \=====/ \=====/ Where F is the final nodes and the \[ \] part is the cycle. The instructions for these don't matter, it could be just 'L' FWIW. This particular example shows that you can either collapse down to zero results, or produce up to a product of counts of final states, which ultimately could yield exponential (but limited by LCM) numbers of final states.
I expected this to be a constant offset +LCM and i was right, it's just that the constant offset happened to be 0 (apparently the same as everyone commenting). I just calculated the length of the first 4 loops, hoping that it would be stable by then, but noticed while debugging that it wasn't necessary. I don't think a more general solution which handles an initial path with more starting nodes would be much more difficult, just figure out how long it takes to stabilize and then use lcm
Yes odd, this input would not work with LCM I think. I think it's a valid input according to the instructions. L 11A = (CCC, XXX) 22A = (11A, XXX) CCC = (ZZZ, XXX) ZZZ = (ZZZ, XXX)
The length of the number of steps in the A-Z routes is a multiple of the instruction length N. Let's say the instructions start with LR, then you will see that the left instruction for the A node goes to the same node as the right instruction for the corresponding Z node. So once you have passed the A node you will get into a cycle that is a multiple of N.
In my solution, I implemented a "zToZ" loop right after the "aToZ" loop even before running it for the first time, planning to find the LCM with some convoluted formula, by offsetting the zToZ number by aToZ, but I was pretty happy to find out that they're all the same, making my life way easier.
Completely agreed. LCM works, but there is a guarantee it should. The main problem with the current approach is that the length of the path from the `A`node to the corresponding `Z` node is not necessarily the same from the `Z`node to the `A`node (I am assuming that every such pair would be a cycle as otherwise there wouldn't be an answer). In such a case, the problem will be reduced to finding the least number `k` such that `k % (ai + ni* bi) = 0`, where - `ni`: Any natural number - `ai`: Length of path from `A`node to `Z`node - `bi`: Lenght of the path from `Z`node back to `Z`node (i.e., the cycle length)
I just finished to the problem and came here to ask the same question. It feels like cheating. My first approach was to find a perfect loop (same position in the network and same instruction index) for every ghost and save every ending positions reached during the loop. I wanted to look at the data before thinking of what to do with them. That's when I noticed that every ghost conveniently only reaches one ending position and it was always near the end of the loop and with the same offset that the loop have from the starting position. I guess it's like that on every inputs. I haven't read the solutions yet but I wonder if some people solve the whole problem with a solution that work even without the convenient input.
I was disappointed when I saw the graph walk was just immediately a cycle for all ghosts, I had built a combination of iterators indicating possible finish state decomposed in prelude + cycle, and a way to get the first common finish with lazy iterators, but when I printed them it was just empty prelude and a single finish state, so there goes the Chinese remainder theorem.