Follow

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.

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 https://en.wikipedia.org/wiki/Chinese_remainder_theorem to find the solution.

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 https://gist.github.com/randrew/c7fa048f0079fa6058853f076221da7a

any hint?

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

@shironeko @l3kn that seems to give nonsense results

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

Num m = (id - t) % id;

?

that doesn't give correct results.

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?

> 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

@l3kn @shironeko yup

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.

Eliot Blennerhassett@bigblen@mastodon.nzoss.nzAoC 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 https://nbviewer.jupyter.org/urls/git.sr.ht/~eliotb/code_advent_2020/blob/master/00_core.ipynb