Codingame : Shadows of the Knight

Bonjour à tous !

Je fait juste le point sur cette épreuve sympathique qui nous à été proposée pour le "codingame : Shadows of the Knight" !


Le synopsis est simple : Le Jocker à encore frappé et à posé une bombe dans une pièce pleine d’otages !
Heureusement, la bombe émet de la chaleur, et Batman demande donc à Alphred de lui programmer un détecteur pour retrouver les otages.

Le détecteur retourne U, UL, L, DL, D, DR, R, ou UR pour indiquer dans quelle direction la bombe se situe.
Notre chevalier noir pourra se déplacer et réutiliser le bidule, jusqu’à, on l’espère, retrouver les otages.
Oui parce que bien sur, ses déplacements sont comptés.

Une implantation naïve permettra de résoudre les premiers exemples de vérification (des fichiers fournis avec différent immeubles, emplacement de bombe et positions de départ).
Mais les derniers sont plus récalcitrants : on manque de temps !

Alors, soit Alphred travaille pour le Jocker (hum, perspective intéressante), soit, il y a une autre méthode...

Il faudra implémenter une recherche par dichotomie, et on pourra voir Batman voler en zigzaguant sur toute la façade de l'immeuble pour trouver la bombe. Et sauver, dans tous les cas proposés, les otages.

Yipee !

Exemple proposé dans le sujet :


Mais les choses se corsent ensuite...
Le Jocker met un bouclier thermique sur ses bombes, et le détecteur ne peut plus hélas que dire à Batman si il est plus près ou plus loin de la bombe qu'a son précédent mouvement...

Plus compliqué à résoudre, d'autant que la mémoire est limitée (il peut y avoir jusqu'a 10000*10000 fenêtres, plus de 95Mo si on prends un char par fenêtre outch !)

Et là, pour ma part, le Jocker m'a vaincu 4 fois sur cinq...

Voilà voilà, si vous appréciez ce genre de concours, n'hésitez pas, ils sont relativement fréquents et gratuits, et on dispose en généra de trois heures pour répondre à l'énoncé.
Pi on peut s'entrainer sur les anciens sujets aussi.
Alors, n'hésitez plus, allez y jeter un œil

J'ai voulu participer hier, mais finalement je ne pouvais pas être chez moi à ce moment là.
Je n'avais jamais participé pour ce concours, maintenant grâce à toi, je vois quel peut-être les sujets.

Ca me fait penser quand on fait la recherche d'une personne sous une avalanche avec des ARVA, la machine nous dit si on est près où loin, certain modèle peuvent même nous donner une direction approximative. Du coup, on fait des dichotomie et des évaluations de gradients de potentiels ( comme un ordinateur mais dans la vie réel ^^).

Du coup, toi, tu as essayé de faire quoi d'intéressant pour trouver rapidement les bombes ?

La première une dichotomie toute bête, la seconde par contre, je n'avais pas le bagage mathématique nécessaire (enfin, j'ai pas trouvé un truc simple quoi), donc je suis parti sur un truc comme suit :

On défini une zone de recherche (au départ toute la zone) et un type de recherche (horizontale ou verticale, horizontale par défaut, et, dans le cas d'une zone en 1*X ou X*1, le type qui convient).

Ensuite, on place Batman à un côté de la zone, puis on le déplace à l'opposé (selon le type).
On ne regarde que le second résultat (plus chaud, plus froid ou pareil) ce qui permet de savoir dans quelle moitiée se trouve la bombe.

On ajuste la taille de la zone à la moitié correspondante et on change le type de recherche.

On recommence jusqu'a avoir trouvé.

Le problème de cette méthode, c'est que je n'utilise que la moitié des déplacements pour avoir des informations...
Du coup, je perds beaucoup de temps et je réussi pas souvent à libérer les otages ...

Mais avec ça, je suis quand même 112eme sur 641, et 6eme dans la catégorie "C"   

Si ça t'intéresse :
http://www.codingame.com/cg/#!report:338754b7fd47a52865778beba0bf84d0c8748e

Pourquoi que la moitié des déplacements donnent des informations?
Est-ce que ça change si tu mettais Batman dans les coins plutôt qu'au milieu d'un côté?
Après y'a sûrement moyen de privilégier les tests impairs en se décollant du bord pour profiter d'une ligne en plus. XD

Je connaissais pas les coding games. Ca a l'air marrant! Et stressant, comme un mini-exam. :p
Moi qui ai presque raté mon examen d'algo cause stress, je crois pas que j'aurai assez de niveau/focus. ^^"

bha quand je me déplace vers le premier point, je ne sauvegarde même pas la données que j'aurais pu avoir, je ne traite que la seconde.
Donc, avec mon algo, un déplacement sur deux sert à rien.

Ensuite, pour les diagonales, on perds l'avantage de diviser l'espace en rectangles. Donc mon algo serait totalement inéficasse.

Juste pour info, vous pouvez encore "jouer".
C'est juste que maintenant, c'est plus noté...

J'y ai participé, un peu tard, mais j'y ai participé. J'ai eu un score de ~35%.
J'ai juste fait la première question. La deuxième était plus basé sur les mathématiques (j'aurais calculé la perpendiculaire entre les deux points et appliquer un cercle pour obtenir un masque de collision, mais je ne connaissais pas les formules) et j'ai été un peu découragé, surtout avec le temps qui m'a mis pas mal la pression.
D'ailleurs, ça me motive à reprendre les mathématiques, je n'ai pas eu de cursus là-dedans (j'ai fais des études en sciences politiques pour finalement finir développeur...) et je suis en train d'apprendre le haskell pour cette raison.

Mon report sur coding games
Pour la première, j'ai fais un algo absolument dégueulasse mais qui fonctionnait (et le nom de mes variables sont whoops).
J'ai utilisé un ensemble mathématique contenant l'ensemble des points de la grille. Puis, à chaque tour, je recalculais un ensemble contenant l'ensemble des points où serait situé la bombe, que j'ai soustrait de mon ensemble général. Et je sautais en plein milieu de la zone qu'il me restait à explorer. En cas d'incertitude (deux cases), un coup de random.
Ça fonctionnait bien, et dans les temps (edit: en fait, je viens de regarder le reporting, et pas temps que ça... Mon algo aurait mérité quelques ajustements). Mais je me suis fait dégager sur le dernier test car la grille était trop grande, et ma consommation mémoire trop importante. J'aurais certainement pu optimiser ce dernier algorithme ceci dit, j'ai codé comme un petit goret. J'ai utilisé les ensembles parce qu'en python, ils ont des bonnes performances (un truc avec la complexité 0(1), linéaire. Faudrait aussi que je revois ces histoires de complexité) et que j'ai l'habitude de les utiliser pour le traitement et l'analyse de texte (ce que je fais quotidiennement à mon boulot).
Merci pour le coup de la dichotomie, je viens de regarder et c'est vraiment idiot que je n'y ai pas pensé de moi-même.

Je participe de temps en temps à ces coding-games, quand ma vie familiale me le permet. J'avais bien cartonné celui où il fallait se déplacer dans un labyrinthe, et j'avais vraiment trouvé cool celui avec la mission sur mars, où il fallait déplacer une capsule qui tentait d’atterrir sur Mars, où il fallait tenir compte de la gravité, de la vitesse du vent et du relief.
Là où j'ai vraiment eu du mal au départ de ces coding games, c'est avec la manière des entrées/sorties.
En gros, les entrées, c'est sur stdin, et les sorties sur stdout. C'est vraiment très idiot, mais je ne comprenais pas au début qu'il fallait faire des inputs à chaque tour de boucle. Une fois pigée, plus de problème.

Je veux dire, dans les coins comme ça: