[java] AoC Day 13 Part 2 with Chinese Remainder Theorem
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
- public String partTwo() {
- long time = 0;
- //Time after the time, where the bus should come
- int[] dtime = new int[9];
- //Times, the bus arrives
- int[] modulos = new int[9];
- //Fill dtime and modulos from input
- int index = 0;
- for(int i = 0; i < ids.length; i++){
- if(ids[i] != -1) {
- modulos[index] = ids[i];
- dtime[index] = i;
- index++;
- }
- }
- //Product of all modulos
- long M = 1;
- for (int m : modulos) {
- M *= m;
- }
- //Calculate with the Chinese Remainder Theorem
- for (int i = 0; i < modulos.length; i++) {
- //Get greatest common divider in form 1 = my * modulos[i] + lam * (M / modulos[i])
- Solution res = ExtendedEuclidianAlghorithm.getGCD(M / modulos[i], modulos[i]);
- //Add this to the time, according to the CRT
- time += res.lam * (M / modulos[i]) * dtime[i];
- }
- return "" + Math.abs(time % M);
- }
Editor
You can edit this paste and save as new: