Reprise du message précédent :

Si tu fais toutes les translations possibles ça ne passe pas. En revanche, tu peux n'essayer que les translations dont tu sais qu'elles on au moins une correspondance : la liste des p[i] - p[j].

j'suis même pas sûr d'avoir compris tout l'énoncé...
 

C'est un peu plus compliqué que ça : Il existe au moins un chemin de scanner en scanner qui parcourt tous les scanners, tel que chaque paire a au moins 12 beacons en commun.

Ah ouais, comme ça c'est plus clair. Mais pas beaucoup plus simple à appréhender.

Hein?

Je l'ai pas la...

Je suis largué sur ce truc.

... Du coup en fait tu cherches à matcher le premier scanner avec le second, puis tu le realigne et le recalé a 0,0 du premier,, et tu recommences entre le second et le troisième?

 
Notes que normalement tu peux calculer le 3e vecteur à partir des deux autres (règle de la main droite), et il devrait être possible d’énumérer les deux autres programmatiquement.

Quelqu'un qui a un algo qui fonctionne pourrait lister la réduction de [[[[[7, 0], [7, 7]], [[7, 7], [7, 8]]], [[[7, 7], [8, 8]], [[7, 7], [8, 7]]]], [7, [5, [[3, 8], [1, 4]]]]] ?
Je viens de vérifier ligne par ligne à la mano ce que m'a gerbé mon algo et je trouve : [[[[7, 7], [7, 8]], [[9, 5], [8, 7]]], [[[7, 8], [0, 8]], [[8, 9], [9, 0]]]]
L'exemple donne : [[[[7, 7], [7, 8]], [[9, 5], [8, 7]]], [[[6, 8], [0, 8]], [[9, 9], [9, 0]]]]  
 
 
edit : trouvé

Non, peut-être que le premier ne matche qu'avec le troisième, et le deuxième avec le troisième également par exemple...

On peut vérifier chaque paire, la complexité est N^4 ça passe pour  N = 20.

Ah ouais, classe!

bon j'ai toppé un algo sur reddit, si c'est une erreur d'arrondi je me pends

Merci pour les explications niveau voisins & autres.
Celui d'aujourd'hui me laisse absolument froid, je vais prendre le temps de faire ceux d'hier et avant-hier.

bon je vais vivre, quasiment à la fin de la réduction y'a eu 2 splits dans la même opération

Alors j'ai fait un truc bête comme moi :
je parcours récursivement la liste, j'incrémente 2 compteurs à chaque fois que je tombe pas sur une liste. Si je tombe sur une liste je rafraîchis une liste d'embranchements (0 si je suis à gauche, 1 si je suis à droite) pour les 4 niveaux d'imbrication. J'arrête d'incrémenter le 1er compteur (prev) dès que je suis arrivé à une explosion et je ne touche plus à la liste d'imbrications (a,b,c,d), j'arrête d'incrémenter le 2ème compteur (tot) qu'une fois la liste entièrement parcourue
prev == 0 : leftmost (nœud (0,0,0,0))
prev == tot-2 : rightmost (nœud (1,1,1,1))
ensuite je reparcours : à prev j'ajoute l[a][b][c][d][0] (sauf si leftmost), à prev+3 j'ajoute l[a][b][c][d][1] (sauf si rightmost) et l[a][b][c][d]=0

Je viens de relire et de le repasser, j'avais déduit ça en partie, mais j'avais pas mis le doigt sur l'algo exact.
Ça explique que ça marchait dans beaucoup de cas, mais pas tous. Merci.

edit: je passe tous les cas que je passais avant mais je fail encore ceux que je foirais avant, il doit encore y avoir une couille.
edit2 : y'avait une off-by-one à la con, évidemment

Putain on avait bien besoin de cette merde, tiens
https://twitter.com/mattblaze/statu [...] 6354029574

Chuis toujours pas sorti des ronces.
 

Je l’ai eu ça je crois. Tu fais bien explode en premier, et split seulement quand il ne reste rien à explode ?

c'est mon cas, je l'ai décrit plus haut
il manquait une vérif pour pas splitter à gauche et à droite dans le même temps
 
t'es pu très loin du bout et la part 2 est une formalité

Mon implem de reduce (explode et split modifient l'arbre en place et renvoient true s'ils ont changé un truc, false sinon).

public void reduce(BinaryTreeNode<Integer> result) {
    while (true) {
        if (explode(result)) continue;
        if (split(result)) continue;
        break;
    }
}

 
T'entends quoi par là ? Je cherche le premier noeud splittable en DFS à gauche d'abord, puis je split dessus, par design je peux pas split 2 fois en même temps.

En quelles étapes tu réduits ça : [[[[7,7],[7,8]],[[9,5],[8,0]]],[[[9,10],20],[8,[9,0]]]]  
moi j'avais un bug, ça explosait pas entre 2 splits et j'avais exactement la même sortie que toi sur le même vecteur de test
[[9,10],20] donnait [[9,[5,5]],[10,10]] en 1 seul split mais ptêt que tu fais 2 splits sans explode au milieu

Il est supposé exploser entre le split de 20 et le split de 10 ?

J'ai 3 plafonniers à poser, un moteur de volet roulant en panne à débloquer pour pouvoir fermer le volet, je crois que je vais me résoudre à pomper une soluce de reddit et à essayer de comprendre ce qu'elle fait pour le d19

En me disant que pour demain comme c'est lundi il proposera un truc moins lourdingue

public void reduce(BinaryTreeNode<Integer> result) {
    while (true) {
        if (explode(result)) continue;
        if (split(result)) continue;
        break;
    }
}

J'ai le même algo. Est-ce que explode retourne dès qu'il a trouvé un truc à faire (tu dois pas faire deux explodes en une seule passe) ?

Oui, explode ne fait exploser qu'un seul et unique nœud.

Ok en fait dans ce cas là, je dois split le 10 et non pas le 20 à partir de la première étape.
Il y a une couille dans mon split.

edit: le parcours du split était merdeux, tous les tests sont verts.

Injecte cette merde directement dans mes veines.

dat good shit

dat feeling  

J'ai vu des cas de vols de voiture aussi.  

public void reduce(BinaryTreeNode<Integer> result) {
    while (true) {
        if (explode(result)) continue;
        if (split(result)) continue;
        break;
    }
}

public void reduce(BinaryTreeNode<Integer> result) {
    while (explode(result) || split(result)) {
    }
}

Tu peux simplifier comme ça.  
A défaut d'arriver à résoudre, je fais de la revue de code
 

Gg
La partie 2 est triviale.

J'ai un problème sur la partie 2, putain
J'ai probablement perdu 10 points de QI pendant la journée.

Ah c'est con ça
Un pb dans l'algo à faire ou bien t'as l'algo mais la réponse est fausse ?
Bon courage.

Laissez tomber, je crois que je viens juste de me faire niquer par la mutabilité. Je vais faire un hack dégueulasse

C'était marrant, au fur et à mesure des réductions, ça changeait toutes les valeurs en même temps

Mon pote est presque sourd, mais je lui ai acheté un casque à conduction osseuse et il arrive de nouveau à écouter de la musique (d'une seule oreille) et même à entendre des appels téléphoniques.

Meilleur achat et cadeau de Noël ever.

Merci à ceux qui ont parlé de ces trucs ici.

Chez moi ça marche pas mieux  

 
ça marche bien contre la surdité de transmission (oreille moyenne). Par contre si c'est ton oreille interne qui est moisie, ya rien à faire

Wé j'ai testé et je confirme, mal branlé à l'intérieur.
Y a de fortes chances que ça se limite pas qu'à l'oreille d'ailleurs  

AoC du jour fait ! Sans doute l'effet Dunning-Kruger, je n'ai pas perçu la difficulté en lisant l'énoncé. Donc j'ai fait une solution simple (simpliste ?) qui fonctionne : https://pastebin.com/HMdnZdrL