Plus compliqué, mais très intéressant

Bon, là, je dois avouer que j’ai un peu galéré sur le problème 18. Pas vraiment à cause des maths, en fait, mais plutôt à cause des notions tordues de delegate, de this, de it, de owner …
Vous noterez donc l’usage abusif de l’expando, mais aussi, ce que je trouve très mignon, la déclaration de comparateur comme une closure avec un opérateur de comparaison sympa. Bon, c’est une solution brute force, j’en suis bien conscient, et je vais essayer de l’améliorer (ce qui à la réflexion doit se faire « facilement » en retournant le problème, c’est-à-dire en considérant qu’on part de toutes les bases, et en éliminant à chaque fois celle qui donne une somme inférieure). Je crois même que je posterais cette solution améliorée (parce qu’après tout, elle doit aussi bien me permettre de résoudre le problème 67.
EDIT Mais c’est que je suis parfois pas malin, moi !
En fait, ma solution est déjà pas mauvaise, puisqu’elle ne calcule que l’arbre des meilleures sommes. Son seul inconvénient est que, pour faire ça, elle doit quand même déjà calculer toutes les sommes de base, ce qui est long. Et, surtout, son principal inconvénient et qu’elle effectue le calcul de manière récursive, ce qui pose des problèmes de piles d’exécution (surtout que Groovy, pour un appel de méthode interprété, effectue en fait un gros paquet d’appels non interprétés). Je crois que je vais passer à une solution sans expando, mais avec de groooosses balades dans des tableaux, ce qui était en fait la solution à laquelle je pensais initialement.

 

EDIT2 bon, après cinq minutes de cogitations, j’ai trouvé la solution « optimale », celle qui va me permettre de travailler sur des tableaux de taille infinie, ou presque, sans souffrir de piles d’appels infinies.

 

 

Et celle-là a toutes les chances de marcher pour le problème 67, ce que je vais vérifier maintenant. Ce qui est un succès aussi phénoménal qu’il est rapide (parce que même avec cette quantité astronomique de chiffres, j’obtiens la réponse dans la seconde !).
Publicités

Une réflexion sur “Plus compliqué, mais très intéressant

  1. Pingback: Vite fait | riduidel's wordpress

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s