Confinement, Sha25, Garderie Pokémon

Confinement.. confinement, le confinement est long et pour m’occuper, j’ai participé aux différents challenges proposés par h25

Je vous présente ici comment j’ai abordé un des problèmes proposé, “La garderie Pokémon”

Sacha est hyper fier de ses Pokémon, mais ils n’arrêtent pas de se reproduire ! Au début, c’était simple de tous les nommer, mais Sacha commence à en avoir marre et leur donne de drôles de surnoms : “Spiderman”, “Cheh”, ou encore “Wallah je suis un chacal Le tripe des roulacast chegt conduit !”.

Mais quand cette folie reproductrice prendra-t-elle fin ? Nous avons réussi à modéliser la taille de la population de ses Pokémon en utilisant le programme ci-dessous, mais nos machines ne semblent pas assez puissantes pour calculer ce nombre…

 def populationPokemon(n):
    if n < 2: return n
    return 6 * populationPokemon(n - 1) + populationPokemon(n - 2)

g = int('32903905359313255964904129932564771028998351965079821940'
        '08099620749553008294238402646316547811776426326359030169'
        '09079308918506201129702284041405145021002484474836195640'
        '74719170089161988770537600785662834746353811567064992523'
        '90663500040041259863067380286549300862141509763106539137627339561')

print(populationPokemon(g)%100000007)`

Première impression, le nombre est grand, très GRAND, très très GRAND !

Il parait immédiatement que le calcul direct ne pourra pas aboutir. La récursion est une impasse, les astuces classiques comme la mémoization ne suffiront pas non plus.

\[u_{n} = 6 \times u_{n-1} + u_{n-2}\]

La formule ressemble à celle de la suite de Fibonacci, qui est un exercice très classique pour de l’optimisation. Mes souvenirs me rapellent deux choses, on peut trouver une formule analytique et il peut être modélisé comme un produit matriciel.

La formule analytique

Je commence ma recherche documentaire sur wikipédia, c’est un problème bien étudié, mais ça semble bien compliqué.

Le produit matriciel

J’en ai des souvenirs assez brumeux, mais je recherche à construire la matrice correspondant au problème. J’utilise un calculateur en ligne pour tester les cxxxx de coefficients à mettre dans la matrice.

\[\begin{pmatrix} 6 & 1 \\ 1 & 0 \end{pmatrix} \times \begin{pmatrix} u_{n-1} \\ u_{n-2} \end{pmatrix} = \begin{pmatrix} 6 \times u_{n-1} + u_{n-2}\\ u_{n-1} \end{pmatrix}\]

La matrice est construite, il reste maintenant à l’élever à la puissance LE NOMBRE ENORME pour arriver au résultat.

Une implémentation de la classe matrice, avec le modulo (inhabituel)

il faut se méfier des overflows :(

final static int MODULO = 100_000_007; // H25
static class Matrice {
	int a,b,c,d;

	public Matrice(int a, int b, int c, int d) {
		super();
		this.a = a;
		this.b = b;
		this.c = c;
		this.d = d;
	}
	
	public void square() {
		long at = ((long) a)*a + ((long) b)*c;
		long bt = ((long) a)*b + ((long) b)*d;
		long ct = ((long) a) *c + ((long) c)*d;
		long dt = ((long) b) *c + ((long) d)*d;
		a= (int) (at % MODULO);
		b= (int) (bt % MODULO);
		c= (int) (ct % MODULO);
		d= (int) (dt % MODULO);
	}
	
	public Matrice pow(BigInteger exp) {
		Matrice result = new Matrice(a, b, c, d);
		Matrice x = new Matrice(a, b, c, d);
		BigInteger TWO = BigInteger.valueOf(2);
		while (!exp.equals(BigInteger.ZERO)) {
			if (exp.mod(TWO).equals(BigInteger.ONE)) {
				result.mul(x);
			}
			x.square();
			exp = exp.divide(TWO);
		}
		return result;
	}

	private void mul(Matrice x) {
		long at = ((long) a) * x.a + ((long) b) * x.c;
		long bt = ((long) a) * x.b + ((long) b) * x.d;
		long ct = ((long) c) * x.a + ((long) d) * x.c;
		long dt = ((long) c) * x.b + ((long) d) * x.d;
		a= (int) (at % MODULO);
		b= (int) (bt % MODULO);
		c= (int) (ct % MODULO);
		d= (int) (dt % MODULO);
	}
}

Je teste avec fibonacci, puis avec le sujet.

public static void main(String[] args) {
	long start = System.nanoTime();
	Matrice fib = new Matrice(6,1,1,0);
	BigInteger b = new BigInteger("3290390535931325596490412993256477102899835196507982194008099620749553008294238402646316547811776426326359030169090793089185062011297022840414051450210024844748361956407471917008916198877053760078566283474635381156706499252390663500040041259863067380286549300862141509763106539137627339561");
	Matrice res= fib.pow(b);
	long end = System.nanoTime();
	System.out.println(res.d + " in " + (end - start)/1_000_000 + "ms");
}

43101863 in 7ms

Done.

Le calcul est incroyablement rapide !!! L’exponentiation rapide a réduit le nombre de multiplications à 1394.

Cet exercice m’a permis de me replonger rapidement dans le calcul matriciel, quelques galères sur les overflows et un effet whaoua lors du run.

Have fun & KeepCoding !