Pas en reste les chinois - Solution

On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Thomas en début de semaine !

Pour la première partie, la réponse est 6568. Pour la seconde partie, la réponse est 554865447501099.

Pour la première, la solution est assez simple. Il suffit de déterminer par combien il faut multiplier le numéro du bus pour obtenir le nombre qui est après notre timestamp. On cherche donc à diviser le timestamp par le numéro du bus. Puisqu'on travaille avec des nombres entiers, le résultat de la division, si elle ne tombe pas juste, sera en dessous du timestamp. Dans ce cas il faut rajouter 1 au quotient, avant de le remultiplier par le numéro de bus pour obtenir le timestamp que l'on cherche. Autrement, si la division tombe juste, ce numéro de bus sera la base de notre solution. Il faut ensuite récupérer le plus petit des timestamps et enfin appliquer la formule de l'énoncé pour avoir le résultat final.

Par contre, pour la seconde, itérer jusqu'au nombre attendu n'est pas raisonnable, et risque de prendre beaucoup de temps de calcul. En étudiant les entrées on remarque que tous les numéros de bus sont premiers.

On comprend également que l'on cherche la solution au système d'équations pour l'entrée 7,13,x,x,59,x,31,19 tel que :

(n + 0) % 7  = 0
(n + 1) % 13 = 0
(n + 4) % 59 = 0
(n + 6) % 31 = 0
(n + 7) % 19 = 0

Ou noté de façon mathématique :

    n ≡ 0 [mod  7]
n + 1 ≡ 0 [mod 13]
n + 4 ≡ 0 [mod 59]
n + 6 ≡ 0 [mod 31]
n + 7 ≡ 0 [mod 19]

Donc

n ≡ 0 [mod  7]
n ≡ -1 [mod 13]
n ≡ -4 [mod 59]
n ≡ -6 [mod 31]
n ≡ -7 [mod 19]

Soit

n ≡  0 [mod  7]
n ≡ 12 [mod 13]
n ≡ 55 [mod 59]
n ≡ 25 [mod 31]
n ≡ 12 [mod 19]

Ou encore

n % 7  = 0
n % 13 = 12
n % 59 = 55
n % 31 = 25
n % 19 = 12

On se retrouve dans le cas typique du problème des restes chinois tel qu'il peut être exposé ici : https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8medesrestes_chinois#Exemple

Voici une solution proposée en kotlin

package org.grorg.aoc

class NotFoundSolutionException: Exception("No solution has been found")

fun solveDay13p1(input: List<String>): Int {
    val start = input[0].toInt()
    return input[1]
        .split(",")
        .asSequence()
        .filter { it != "x" }
        .map { it.toInt() }
        .map { Pair(it, if (start % it == 0) start else it * (start / it + 1)) }
        .minByOrNull { (_, b) -> b }
        ?.let { (a, b) -> (b - start) * a }
        ?: throw NotFoundSolutionException()
}

fun findModulus1(x: Long, modulus: Long) = generateSequence(0) { it + 1 }
    .filter { (x * it % modulus) == 1L }
    .first()

fun solveDay13p2(input: List<String>): Long {
    val elements = input[1]
        .split(",")
        .asSequence()
        .zip(generateSequence(0) { it + 1 })
        .filter { (a, _) -> a != "x" }
        .map { (a, b) ->
            val al = a.toLong()
            Pair(al, (al - b) % al)
        }
        .toMap()
    val m = elements.keys.reduce(Long::times)
    val mn = elements.map { (a, _) -> Pair(a, findModulus1(m / a, a)) }.toMap()
    return elements.keys
        .map { elements[it]!! * (m / it) * mn[it]!! }
        .reduce(Long::plus) % m
}

A bientôt pour un nouveau #KataOfTheWeek !

TakiVeille

TakiVeille