AoC 2020 day 13, part 2, can't solve

I don't know how to solve this problem. Is there some bit of math knowledge about prime numbers I'm missing? I don't know much about number theory.

I've never had to look at a hint for an AoC day before, and I don't want to start now, so I might drop out.

I don't recognize any of the people on the Merveilles leaderboard who are still participating.

· · Web · · ·

AoC 2020 day 13, part 2, can't solve

@cancel I had to do some eyeballing and maths using my brain to extract some useful constraints before I could get workable code. AFAIK everyone's input is different.

If integer N == x*prime1 == y * prime2 this means prime1 and prime2 are factors of N. Without knowing x and y, can still say N==k*prime1*prime2

You can peek at my solution here nbviewer.jupyter.org/urls/git.

AoC 2020 day 13, part 2, can't solve

@cancel The problem can be expressed as a system of congruences, then you can use the en.wikipedia.org/wiki/Chinese_ to find the solution.

AoC 2020 day 13, part 2, can't solve

@l3kn @cancel I did this in the end. Had to look up the theorem. Not sure I'm a fan of this kind of task for AoC.

AoC 2020 day 13, part 2, can't solve

@l3kn yeah I never would have figured that out on my own

AoC 2020 day 13, part 2, can't solve

@l3kn oh yeah, you're still participating. I *do* recognize you :)

AoC 2020 day 13, part 2, can't solve

@l3kn I read a little bit of that page, then stopped, and tried to figure it out again, but I still can't get it. What am I doing wrong? This works for all of the examples, but never terminates for the real input gist.github.com/randrew/c7fa04

any hint?

AoC 2020 day 13, part 2, can't solve

@cancel @l3kn seems like you can just do (d+id)%id and the result will be the wait time for that bus to depart.

AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn that doesn't use 'm' in the loop, so it will never terminate

AoC 2020 day 13, part 2, can't solve

@cancel @l3kn yeah, I'm saying you can calculate m directly.

AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn that seems to give nonsense results

AoC 2020 day 13, part 2, can't solve

@cancel @l3kn hmm, I took a closer look at the code, it seems to be doing something different than what I had in mind (from reading the question)

AoC 2020 day 13, part 2, can't solve

@cancel @l3kn what I had in mind:
for each id, calculate wait time (arrival timestamp + id) % id , if it's smaller than the current minimum, update the current minimum. at the end, output the answer.

AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn did you do day 13? is that how yours' works?

AoC 2020 day 13, part 2, can't solve

@cancel @l3kn okay, I just joined, and got my answer accepted. minor hiccup. it was actually (id- arrival timestamp) % id. lol I messed up the sign.

AoC 2020 day 13, part 2, can't solve

Num m = (id - t) % id;
?
that doesn't give correct results.

re: AoC 2020 day 13, part 2, can't solve

@cancel @l3kn well, you are doing it in a completely different way, so that's to be expected.

re: AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn you're replying to a thread where I posted my code. I didn't know we were talking about something else?

re: AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn Sorry, I'm not trying to be rude. I'm genuinely confused about what's going on here.

re: AoC 2020 day 13, part 2, can't solve

@cancel @l3kn > what I had in mind:
> for each id, calculate wait time (arrival timestamp + id) % id , if it's smaller than the current minimum, update the current minimum. at the end, output the answer.

it was for this algorithm. I'm still reading your code trying to figure out how you intended to do it, maybe explain it a little bit?

re: AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn I don't really have an intuition for how it works. I just permuted multiplying and adding things together, and this happens to give correct answers for the example inputs.

re: AoC 2020 day 13, part 2, can't solve

@shironeko @l3kn I jiggled the terms around more, after someone else told me to, and now it works for the real input.

re: AoC 2020 day 13, part 2, can't solve

@cancel @shironeko I had a similar problem where the offset (`i` in your program) was larger than the modulus (`id`), fixed it by using `i % id` as the offset.

re: AoC 2020 day 13, part 2, can't solve

AoC 2020 day 13, part 2, can't solve

@cancel I'm still plodding along. :) I can't do them every day, so it's constant catch up.

AoC 2020 day 13, part 2, can't solve

@cancel The computer is running the brute force solution while I write this. It will probably take some more minutes 😂

AoC 2020 day 13, part 2, can't solve

@cancel (I'm agarciamontoro in the leaderboard, btw)

AoC 2020 day 13, part 2, can't solve

@cancel I looked up other peoples solutions and it’s definitely some real number theory stuff. I was brute forcing it and my computer didn’t get close in an hour so I stopped.

Merveilles is a community project aimed at the establishment of new ways of speaking, seeing and organizing information — A culture that seeks augmentation through the arts of engineering and design. A warm welcome to any like-minded people who feel these ideals resonate with them.