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
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.
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 https://nbviewer.jupyter.org/urls/git.sr.ht/~eliotb/code_advent_2020/blob/master/00_core.ipynb