Pour ce genre d'opérations, avec ffmpeg, j'ai un fichier avec des fonctions bash dedans, il suffit de le sourcer et on peut les utiliser :
On a d'abord une série de fonctions pour extraire quelques infos à partir de ffprobe. La première série extrait une info spécifique d'un fichier, la seconde liste ces infos pour chaque fichier dans la ligne de commande, avec des couleurs, et enfin la dernière fonction ffinfo regroupe un peu tout en une ligne.
Et il faudrait que je la réécrive, puisqu'à l'origine elle devait peu servir donc tant pis si on exécute 5 fois ffprobe, mais en pratique c'est la seule que j'utilise.
Avec des codes ANSI pour les couleurs aussi.
Ensuite une multifonction (au moins suisse) de conversion.
Elle est assez imbitable, mais elle fait ce qu'elle prétend faire dans le Usage : Usage ff [unmap] [format:mkv|mk4|mp4|ogm|mp3|ogg|opus|audio] [scale width] [destination directory] file [files|non existant destination file]
Il y a une variable d'environnement CRF=22, qu'on peut bien sûr modifier en ligne de commande.
En gros, elle prend un fichier source, le balance à la destination, et converti.
L'option unmap permet de virer des infos inconvertibles, comme parfois des chapitrages qui ne passent pas d'un avi vers un mkv, ou un truc du genre. Par défaut on copie tous les flux, en transformant l'audio et la vidéo, avec unmap on converti l'audio et la vidéo, on copie les sous-titres, et on oublie le reste. Quand ça plante j'essaie avec unmap, voilà.
Ensuite le format de sortie, ça fait des choix en fonction de mes besoins ponctuels, pas du tout en fonction des besoins du monde entier :
* mkv : par défaut, conversion x265 vers fichier .mkv
* mk4 : conversion x264 vers fichier .mkv, pour compatibilité avec un matériel plus ancien.
* mp4 : conversion x264 vers .mp4, pour compatibilité windows sans VlC.
* ogm : pour faire de l'ogg/vorbis en .ogm, en pratique je n'utilise jamais.
Et les formats d'extraction audio mp3, ogg, opus qui convertissent le flux audio dans le format mentionné, et enfin audio pour extraire le format audio sans y toucher.
L'option suivante est intéressante : elle permet de redimensionner à la largeur souhaitée, en conservant le ratio. Donc pour passer de 4k à fullHD on va mettre 1920, si on veut faire tourner la vidéo sur la vieille machine qui gère pas le fullHD on va mettre 720 par exemple, on aura en 16/9è une vidéo en 720x405.
Après, soit on met [fichier source] [fichier destination], le fichier de destination est facultatif, il sera construit à partir du nom du fichier source - soit on met [répertoire de destination] [plein de fichiers source…], et là aussi les noms de fichiers de destination sont construits à partir de noms des fichiers sources.
On pourra noter si on arrive à déchiffrer les hiéroglyphe bashiques de la 4ème dynastie et demi de l'empire sed, que le nom de fichier est nettoyé : les espaces deviennent des _, on vire ce qui est après le premier ., des trucs du genre. Ça peut être très pourri si la vidéo s'appelle ma.video.de.vacances.avi on va avoir ma.mkv avec le nommage automatique. Bien fait.
Attention aussi, c'est codé avec des moufles, donc l'ordre des options est impératif, c'est comme ça, et c'est tout. Autant dire que je lance toujours ff sans rien d'abord pour me rappeler de l'ordre, sinon je fais n'importe quoi.
Donc typiquement on va faire pour un lot avec une qualité plus basse : $ CRF=28; ff 720 ~/tmp/ ~/vidéos_à_traiter/* où on notera bien le mix de paramètres et de variable d'environnement, pour l'incohérence.
Et enfin la dernière fonction pratique, qui attends qu'un fichier existe, par exemple si on le télécharge et qu'il est en .part, et qu'il a son nom définitif, sans le .part, à la fin du téléchargement, ou si on le construit par ailleurs, et qu'il est déplacé dans le répertoire de traitement. Puis qui attends qu'il n'y ait pas d'autre processus ffmpeg qui tourne. Et enfin qui appelle ff. La syntaxe est incohérente avec celle de ff c'est pour mieux embrouiller les gens :
ffifo(){# Wait for {file} to be available, then wait for no ffmpeg process to run, then call ff()# ffifo file.part file.srtlocalDIR=$(dirname "$1")localFILE=$(basename "$1" .part)shiftlocalDEST=$1shiftecho"ff $@ \"$DIR/$FILE\" \"$DEST\""while[ ! -f "$DIR/$FILE"];doecho -n .; sleep 10;donewhile[$(pidof ffmpeg > /dev/null &&echo1)];doecho -n °; sleep 10;doneechoecho"# $DIR/$FILE"
ff $@"$DIR/$FILE""$DEST"}
Ça ne fonctionne qu'en mode source->destination pas en lots, et toutes les options de ff sont mises à la fin plutôt qu'au début.
Donc on va faire :
ffifo ~/Téléchargements/ma_vidéo_de_chat.touyube.[TROLOL].4K.x437.aac.dolby.camrip.webm.part ~/Mes_Vidéos/Chats/une_autre_vidéo_de_chats.mp4 720# Qui appellera plus tard :# ff 720 [src...].webm [dest...].mp4
Et aller se préparer un thé.
Dès que le téléchargement en cours est terminé, la conversion va commencer, et si on en fait deux en parallèle, le premier va convertir et le second attendre que le premier ait terminé avant de démarrer.
Pas de surcharge bourrine de la machine, merci !
Et même pas besoin d'attendre le nez devant l'écran que le téléchargement se termine.
Après on peut envoyer ça à sa cousine qui pourra montrer sa super vidéo de chats en classe à tous ses élèves de terminale sur son PC de l'éducation nationale, avec un format et une qualité que la poussive machine saura probablement appréhender.
$ ls -sh /usr/bin/micro
12M /usr/bin/micro
$ ldd /usr/bin/micro
libresolv, libpthread, (mais pas libtinfo et libdl)
mg, connais pas, pas dispo, flemme de chercher surtout si le site est mort ça va pas être facile, mais apparemment jove semble assez imbattable (sauf par ed).
Franchement je reste sur joe, parce que ça permet de choisir entre joe, jmacs, jpico, et jstar, avec un seul binaire.
Pour moi c'est jmacs, pour d'autres c'est au choix.
Par habitude aussi :)
C'est marrant, en terminal, j'utilise joe en mode jmacs, mais pas emacs directement.
Côté légèreté on fait difficilement mieux.
Ya challenge avec nano, au binaire plus petit mais avec plus de libs.so.
Généralement l'insulte le podcast le temps de ressortir le téléphone et d'appuyer sur la touche « saute-moi 30s ».
Les insultes c'est pour pas entendre la pub, je préfère, c'est plus courtois et éducatif.
Comme le dit Renault en dessous, en fait, on parle de n'importe quoi là.
Vu que ça concerne les entreprises.
Donc une entreprise française qui s'arrange pour payer 3% d'impôts à FiscalParadise Island, va en payer 12% en France pour rattrapper le coup.
Ce qui n'empêchera pas FiscalParadise de continuer à proposer des taux bas, mais ça rend son intérêt nettement moindre.
J'aime bien ça !
Déjà j'ai ajouté un certain nombre de paquet qu'on m'ont parut intéressants, et que parfois j'utilise au quotidien.
Et puis j'en récupère d'autres quand les mainteneurs tournent.
Et j'aime bien soutenir les gens qui viennent sur LinuxFR présenter leurs projets, je maintiens Glewlwyd, un système assez efficace de gestion d'authentification (Oauth2 etc.) présenté ici par son auteur Babelouest.
Certes, c'est pour Slackware, pas la distrib la plus répandue, mais les scripts sont parfaitement compréhensibles par n'importe quel mainteneur de n'importe quelle distrib : c'est du shell très standard, et basé sur un seul outil externe : makepkg qui prend un répertoire et en fait un paquet Slackware.
Donc c'est très facile de s'en inspirer pour faire un paquet sur une autre distribution. Je ne sais pas si ça se fait en pratique, mais ça m'arrive de regarder ce qu'il se passe chez ArchLinux quand j'ai un soucis, pour voir s'ils l'ont résolu ou comment.
Donc ajouter un jeu que je peux faire découvrir à mes enfants, en leur disant que c'est moi qui l'ai rendu disponible (oui, ils ont pas le choix pour le moment, ils sont sous Slackware, voilà), ça me fait plaisir :)
Ah, donc le cas inverse d'un Bangladais qui viendrait toucher un SMIC en France, et comme là-bas ça correspondrait à un salaire de ministre, il serait taxé à 45%, ce qui est ingérable ici.
Pour ta dernière question, c'est facile : si une telle loi passe, je pense surtout que le pays de destination va juste faire évoluer ses taxes pour prendre la part entière des 15%, et ne rien laisser au pays d'origine, rien à perdre, tout à gagner, et pour l'employé c'est pareil, voire plus simple puisque taxé à un seul endroit.
Dilemme moral résolu…
Et le salaire il ne dépend pas du niveau de vie du pays où tu travailles ?
Quand je lis 15%, je lis 15% moi.
Donc mettons un français part vivre par exemple au Bangladesh. Cette personne bosse localement, pour un salaire normal là-bas, donc absolument minuscule en France, bah sa taxe de 15% de son salaire ridicule, soit peu de choses, mais tout de même 15% rapport au niveau de vie local.
Que veux-tu faire de plus ou de différent ?
Quel cas poserait problème ?
La façon dont c'est utilisé. Pour faire du code sans code, construire des algorithmes complexes à base de modules maison, et de templating Jinja.
C'est devenu extraordinairement difficile de savoir comment fonctionne un playbook.
En plus certains rôles, certaines tasks, utilisent des variables d'environnement, définies très loin de là.
C'est du bricolage très éloigné de l'utilité normale d'ansible…
Je suis plus traumatisé par l'utilisation qui est faite que par ansible lui-même, mais j'en viens à haïr le yaml+jinja…
Je n'avais pas eu le temps de m'y mettre plus tôt, mais c'est chose faite, le slackbuild de Blupimania est prêt, et sera disponible dans le dépôt dès demain probablement.
Il a fallut taper un peu dessus, parce que la Slackware 15.0 a une version un poil trop ancienne de SDL2_image et SDL2_mixer.
Comme pour la dernière version de Planetblupi avec SDL2_ttf.
J'embarque les versions à jour dans le répertoire du jeu, recompilés pour l'occasion, et youplà.
C'est rigolo comme jeu, j'étais complètement passé à côté des blupis dans les années 90.
Flûte, mon beau-père est décédé d'Alzheimer et de son diabète alors qu'il venait de chopper le Covid qui n'a fait que l'achever.
Ma grand-mère court toujours à 96 ans.
Et le taux de mortalité dans ma commune, pourtant si caractéristique et si généralisable à l'ensemble du village planétaire, est resté stable.
Mes propres doses de vaccin n'ont pas été fichues de m'achever, malgré tous mes efforts !
Et je n'ai absolument aucune connaissance qui soit décédée depuis le Covid19 alors qu'elle était vaccinée, excepté mon beau-père sus-cité, alors que leur taux de vaccination reflète la moyenne nationale.
Je me vois dans l'extrême obligation de décorréler le vaccin de tous ces évènements perturbants, selon mon étude scientifiquement empirique, et je sais de quoi je parle, j'ai plusieurs diplômes post-bac, j'ai travaillé dans des labos de recherche, ma tante est médecin, mes parents ingénieurs, et mes frères et sœurs sont tous docteurs, et j'ai déjà gagné plusieurs fois à Pandémie, et ma fille fait du Triathlon, et je bois du thé.
Oui, ça fonctionne parce que le nombre de coupe est faible dans un problème plutôt grand (1 coupe pour 1000 arêtes), et que les coupes sont assez éloignées.
J'ai supposé que ça pouvait être le cas, et j'ai gagné.
Après j'ai eu la chance de prendre un sommet initial assez éloigné de mes coupes. Par hasard en fait parce que si on regarde l'algo, je prend le dernier sommet source défini dans les données.
Et j'ai pris celui là parce que je l'avais sous la main à la fin de l'analyse des données, donc c'était vraiment sans arrière pensée : lui ou un autre, qu'importe ?
Et en fait, ça m'aurait été très difficile de comprendre pourquoi l'algo bloque à un moment, quelle est la topologie du graphe, et pourquoi je ne peux plus avancer, et comment savoir comment avancer.
Parce que sur téléphone c'est pénible, difficile à lire, prise de tête. Si ça avait raté, j'aurais probablement dû partir sur une toute autre idée (une exploration en largeur, en notant la taille des liens possibles ? du brute force trop long probablement. D'autres simplifications, trouver des zones fermées et les réduire ? Récursivement ?), voire attendre d'enfin récupérer un ordinateur.
Après vérification, mon hack, au lieu de tout ajouter, pourrait ajouter 1 seul sommet au hasard parmi les sommets possibles.
Je tombe sur la solution, mais pas toujours pour le coup, en y allant au pif, je tombe parfois sur un mauvais chemin.
Je sais déjà que ça peut fonctionner, parce que ça fonctionne en les ajoutant tous, mais ça veut surtout dire qu'on peut brancher sur une exploration 1 par 1 de tous les sommets possibles, quand on coince avec l'algo de base, et faire une exploration.
On doit pouvoir avoir un algo capable de nous assurer qu'on trouve une solution.
Encore une fois, tout ça fonctionne parce qu'on sait qu'on a trois sommets à couper hein.
C'est un brin moche mais voilà, on peut retomber sur nos pieds.
Ah, et côté perfs, on est sous la seconde pour l'exécution en python.
Je ne suis pas sûr que ça aurait été beaucoup plus long si j'avais codé à l'arrache ma propre fonction pour les diviseurs, plutôt que d'utiliser sympy : on n'en calcule pas tant que ça, et au bout du compte les nombres ne sont pas si grands, avec de l'ordre de 200 diviseurs, et une racine carrée autour de 10 millions, ça se réduit assez vite, c'est pas vraiment là qu'on va perdre du temps.
Avec sympy c'est immédiat.
On perd probablement plus de temps à charger le module, from sympy import divisors prend un temps visible dans un shell python, ça doit être la majeure partie de la seconde qui part là-dedans !
Bien sûr, ici, je sais que j'ai un dx, dy et dz, et l'algorithme ne s'adapte pas à une éventuelle situation où on n'en n'aurait que deux sur trois, mais à part de forcer à faire du code plus propre, ça ne changerait pas grand chose à l'algorithme final qui n'utilise que dz et dx et valide le dy recalculé.
Et comme dit plus haut, je calcule un paquet de fois la solution à partir de toutes les parallèles en z, alors qu'une seule suffit.
Bref, un algo plus générique ne serait pas beaucoup plus complexe, il faudrait formaliser mieux.
Par contre si on n'a de parallèles que sur un seul axe, je coince a priori. Il faudrait essayer des valeurs possibles sur un autre axe, en supposant qu'elles ne soient pas trop grandes, ce qui est le cas puisque dx=-242, dy=-49, dz=209, donc en explorant depuis 0 en positif et négatif, on va mettre quelques centaines de tests pour trouver la solution.
Et c'est nettement pire si on n'a aucune parallèle sur aucun axe…
La force brute en essayant au pif des dx, dy et dz sans en connaître aucun, devrait permettre de tomber sur la solution en quelques dizaines de millions de tests, ce qui reste faisable, et probablement assez rapide (quelques minutes ? une heure max ?) sur un ordinateur moderne.
Ma solution est beaucoup plus rapide : 0,07s, donc assez négligeable devant le temps de démarrage de python.
Mais…
Je ne sais pas qu'elle fonctionne, je le constate.
Et ça exploite très fortement le fait qu'on ait trois liens à couper, sans cette information je ne sais pas quand m'arrêter, l'algo n'est plus du tout le même.
En gros je fais l'hypothèse que deux liens à couper ne sont pas proches (partageant un même sommet), et que je vais avoir un peu de chance.
Je pars d'un sommet, au pif, mais ça rate s'il s'agit d'un sommet d'une des arêtes à supprimer. Là je me dis que si je ne trouve pas de solution, je peux prendre un autre sommet au pif, normalement, au bout du 7è je suis certain d'avoir au moins essayé avec un sommet qui n'est pas dans une des arêtes à supprimer.
Là ça a fonctionné directement.
Je considère comme « exploré » toutes ses arêtes, et les sommets directement connectés.
Et j'itère :
* Je considère l'ensemble des arêtes liées à tous mes sommets, et pas déjà explorées.
* Je considère l'ensemble des nouveaux sommets accessibles via ces arêtes.
* Pour chacun de ces nouveaux sommets, si il est accédé par au moins deux des nouvelles arêtes, je l'ajoute.
* Et je reconstruit l'ensemble des arêtes explorées à partir des liens possibles entre mes sommets explorés.
* Il me reste un ensemble d'arêtes considérées, mais rejetées, et qui seront à nouveau considérées le coup d'après.
* Si je n'ajoute aucun nouveau sommet, j'ai a priori fini.
Normalement, si il n'y a pas deux arêtes à couper qui partagent un même sommet, je ne peux pas « traverser » ces arêtes avec mon algorithme.
Il se trouve que ça s'arrête très très vite sans donner de résultat, donc j'ai juste essayé un truc :
* Si l'ensemble des arêtes que je peux atteindre mais que je n'ai pas considérées n'est pas de taille 3, alors j'ajoute unilatéralement toutes les arêtes possibles : je ne suis pas allé assez loin, il faut que j'avance, et c'est la méthode la plus naïve pour avancer.
À noter que ça peut foirer si l'un de ces nouvelles arêtes et une des arêtes à couper.
Je n'ai pas regardé dans le détail, mais je pense que ce problème n'existe qu'au démarrage, il faudrait peut-être partir directement à deux arêtes de distance de mon sommet d'origine (la suite me prouvera que j'ai raison pour le démarrage, mais tort globalement).
Bref, ça a fonctionné puisqu'après mon algorithme s'est arrêté à trois arêtes accessibles mais mises de côté, et là on sait que c'est le bon résultat, pif paf, terminé.
L'algorithme mériterait bien plus de vérifications, et éventuellement une boucle sur un sommet de démarrage différent, jusqu'à tomber sur une solution.
Il faudrait au minimum identifier quand est-ce que j'ai besoin de mon hack pour avancer un peu plus loin dans le noir, peut-être faire une exploration en branches pour ajouter un sous-ensemble et tester, histoire de s'assurer qu'on va trouver un truc viable, ou tout explorer sans trouver.
Mais ça a fonctionné du premier coup.
On peut noter qu'il y a 1502 sommets et 3363 arêtes dans mes données, donc au final démarrer depuis un des sommets à éviter, ça serait surtout beaucoup de malchance, c'est la taille du problème qui m'a incité à tester cette approche, en me disant que j'avais plus de chance de tomber dans le « gras » du problème que pile là où il ne fallait pas.
J'ai cherché des simplifications, un peu, avant, comme de simplifier les triangles (A<->B<->C<->A), mais autant ça donne un peu quelque chose sur les données de test (on peut brute-forcer la recherche sans soucis : prendre trois arêtes et voir si on a coupé en deux), c'est inutile sur les données réelles, on simplifie de 42 arêtes, sur 3363 ça change rien.
Par contre, en nettoyant mon code, je vois que le « hack » sert trois fois : à 15 sommets à explorer (1ère itération, donc dès le début), à 54 sommets à explorer (3ème itération), puis à 217 sommets à explorer (345 déjà validés, 13ème itération !), et là on est quand même assez loin, on aurait très facilement pu mal tomber, sachant que le résultat arrive à 18 itérations.
Bilan, je dirais que j'ai plutôt eu de la chance avec mon sommet de départ…
Voilà le code nettoyé :
fromsysimportstdintest=stdin.isatty()r1,r2=(54,0)iftestelse(562912,0)t1,t2="Étape 1","Étape 2"ok,nok="\033[38;5;118m✓\033[0m","\033[38;5;196m✗\033[0m"data=(__doc__iftestelsestdin.read()).strip().splitlines()ex1=ex2=0nodes=set()flinks=set()fordindata:a=d.replace(":","").split(" ")nodes.update(a)s=a.pop(0)forbina:flinks.add(frozenset((s,b)))S=s# Soit S un sommet quelconquedefexplore(s,links):explinks={iforiinlinksifsini}expnodes={aforiinexplinksforaini}newnodes=expnodes.difference([s])print(expnodes,explinks,newnodes)i=0whilenewnodes:i+=1newlinks={iforiinlinksifi.intersection(expnodes)}.difference(explinks)exploring=[_foriinnewlinksfor_iniif_notinexpnodes]newnodes={iforiinexploringifexploring.count(i)>1}expnodes.update(newnodes)explinks.update(iforiinlinksifi.issubset(expnodes))# Hack when stopping too early: adding everything linkedifnotnewnodesandlen(newlinks.difference(explinks))>3:newnodes=set(exploring).difference(expnodes)expnodes.update(newnodes)print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")returnexpnodes,newlinks.difference(explinks)a,b=explore(S,flinks)iflen(b)!=3:print("ERROR, wrong result ahead")ex1=len(a)*(len(nodes)-len(a))
Pour une fois, mes expérimentations téléphoniques pour coder moins et avoir de la chance rapidement, ont portées leurs fruits, j'étais le premier surpris :)
Mais c'est rude de faire du code aussi approximatif, et de s'en contenter au bout du compte, ça heurte vraiment ma façon de penser.
Enfin, c'est pour ça que j'ai validé cette étoile avant la seconde du jour précédent.
C'est celui qui m'a le plus gonflé sur téléphone.
Pas la partie 1 bien sûr, encore expédiée assez vite dès que je m'y suis mis (c'est à dire une fois le jour précédent terminé).
La partie 2.
Où les données de test laissent entrevoir plein de simplifications qui ne fonctionnent pas avec le vrai problème.
Et une résolution finale qui ne fonctionne pas sur les données de test !
J'ai assez modélisé mes trajectoires de grêlon, pour faire des opérations en masse, je cherchais des simplifications, des translations, pivots, etc, mais je n'ai jamais réussi à résoudre autre chose que les données de test comme ça : à chaque fois il fallait tester au moins un paramètre final, et le plus complexe à tester a au final une valeur de 57 milliard et quelques au minimum, donc on ne va pas l'atteindre comme ça, en cherchant…
C'est le temps nécessaire à notre caillou pour atteindre un élément.
On tombe pas dessus par hasard.
Dans les données de test, c'est 1, ça simplifie grandement le problème.
En fait, il faut comprendre le problème.
On choisit un point d'origine et une trajectoire : Traj(x=393358484426865.0, y=319768494554521.0, z=158856878271783.0, dx=-242, dy=-49, dz=209)
À partir de là on choisit des entiers, grands, ça va de quelques dizaines de milliards à probablement mille milliards (j'ai un 943 538 374 225 pour un grêlon), ça définit des points de départ sur notre trajectoire.
De chacun de ces points on choisit une direction, et on fait reculer notre grêlon du temps nécessaire à atteindre le point en question.
Voilà, on a notre problème posé, on oublie la trajectoire initiale, il faut la retrouver.
Facile à construire, pas simple à démêler…
Et franchement, il faut trouver des simplifications.
Et là on les trouve avec une première constatation : ce qui se passe en x, y et z est presque entièrement décorrélé, pour trouver dx, dy ou dz, on n'a besoin de se concentrer que sur la coordonnée en question. Après on fera une corrélation sur l'écart en temps entre deux grêlons, qu'on peut connaître pour dx, dy ou dz, et qui sera donc égale pour les autres, et permet de faire une triangulation.
Et une seconde constatation, sur un axe on a des grêlons parallèles, c'est à dire qui ont le même dx, le même dy ou le même dz.
Et ça va nous aider.
C'est même la seule simplification que j'ai trouvé pour réussir à résoudre ce problème.
Parce que si entre deux grêlons on a un dx identique, ça veut dire que l'écart en x entre ces deux grêlon est une constante.
Et donc qu'on parcourt cette écart avec un nombre entier d'étapes, chacune d'un nombre entier de décalages.
Donc pour deux grêlons a et b parallèles en x, donc a.dx==b.dx, on a que l'écart en x (a.x - b.x) est divisible par r.dx-a.dx ou r est notre trajectoire résultat à trouver. On cherche r.dx.
Et ben on va chercher les diviseurs de a.x - b.x, sans connaître le sens on va tous les prendre en positif ou négatif, on ajoute a.dx, et on a des valeurs possibles de r.dx.
Et on cherche les valeurs communes entre tous les éléments parallèles en x, on aura réduit drastiquement nos possibilités de r.dx.
En pratique, si on n'oublie pas de considérer les diviseurs en négatif ou positif (parce qu'on ne sait pas dans quel sens on va, on a juste deux grêlons au pif), on va trouver une seul valeur pour dx, dy et dz.
On a la direction parfaite de notre caillou !
Ça aurait pu rater, on aurait pu avoir des choix et devoir tester parmi ces choix lesquels seraient les bons, mais on sent que même si on en avait eu plusieurs, ça n'aurait pas été trop explosif, et si l'algo pour finir le boulot est pas trop pourri on pouvait tout tester.
Là, suite à une erreur de ma part, j'ai aussi pondu un algorithme capable de calculer dy si on connaît dx et dz !
Sauf que ça foirait, à cause de mon erreur, mais j'ai corrigé et poursuivi, en pratique je calcule la solution pour tous les grêlons parallèles deux à deux en x, et je valide cette solution en montrant qu'ils donnent tous le même résultat. Ça m'a permis de débugger et d'être absolument certain d'avoir le bon résultat au bout du compte.
En pratique, quand on a dx, dy, et dz, il suffit de prendre deux grêlons parallèles selon n'importe quel axe, et on va avoir la solution.
On calcule le nombre d'étapes (microsecondes) pour que notre caillou passe de l'un à l'autre, ce qui est facile si on a compris l'algorithme qui a permit de trouver les dx, dy et dz : on divise l'écart en x a.x-b.x par r.dx-a.dx qui sont connus.
Sachant le temps séparant ces deux chocs, on peut calculer l'écart en y ou en z, constaté parce que nos grêlons ne sont pas parallèles en y ou z, et ça va nous permettre de savoir de combien d'étapes dans le temps il faut remonter pour combler cet écart, et faire en sorte de bien percuter les deux grêlons, en x, y et z.
En pratique mon algorithme, que je n'ai pas simplifié, calcule dy à partir de la connaissance de dx et dz sur des grêlons parallèles en z, c'est pas trop compliqué une fois qu'on a le nombre d'étapes à remonter dans le temps, et on valide déjà qu'on trouve pour tous la bonne valeur de dy. Puis on fait remonter effectivement dans le temps notre caillou depuis sa percussion avec a pour trouver un point de départ.
J'ai juste validé que r.x était identique pour tous, mais tant que ce n'était pas le cas c'était que j'avais une erreur dans mes formules.
Les maths sont simples, mais prise de tête et il faut bien se torturer les neurones.
Au final je fais bien trop de calculs, qui me donnent tous le même résultat, heureusement, et ça prend moins d'une seconde malgré tout.
Voici donc le code, avec trop de méthodes inutilisées dans mes Trajectoires, et des noms de variable bien trop peu lisibles.
Heureusement le code n'est pas trop complexe, et reste a peu près lisible.
Il y a un hack au milieu pour les données de test, puisqu'on n'a pas assez de parallèles pour trouver dx, dy et dz, je force les valeurs, connues, pour valider la seconde partie de l'algorithme.
Mais ça aurait pu faire l'objet d'un développement intéressant pour valider sur un ensemble de valeurs possible, si on n'avait pas eu un dx, dy et dz unique à l'issue de la première partie.
Rendant nécessaire de tester plusieurs cas et de vérifier qu'on ait bien un même résultat. Ça aurait été immonde à débugger par contre…
J'ai tout de même utilisé sympy pour les diviseurs, pour le coup c'était quand même plus simple que de coder une fonction moi-même.
fromsysimportstdinfromdataclassesimportdataclassfromfunctoolsimporttotal_orderingfromsympyimportdivisorstest=Falsedata=stdin.read().strip().splitlines()ex1=ex2=0m0,m1=(7,27)iftestelse(200000000000000,400000000000000)@total_ordering@dataclass(frozen=True)classTraj:x:int=0y:int=0z:int=0dx:int=0dy:int=0dz:int=0@propertydefa(self):returnself.dy/self.dx@propertydefb(self):returnself.y-self.x*self.dy/self.dxdef__mul__(self,other):# t = (x-x0)/dx# y = y0+dy*(x-x0)/dx = a*x+b# b = y0-x0*dy/dx# a = dy/dx# x = (B-b)/(a-A)ifself.a==other.a:return0,0,-1,-1x=(other.b-self.b)/(self.a-other.a)y=self.a*x+self.breturnx,y,(x-self.x)/self.dx,(x-other.x)/other.dxdef__lt__(self,other):returnself.tzero<other.tzerodef__add__(self,n):returnTraj(self.x+self.dx*n,self.y+self.dy*n,self.z+self.dz*n,self.dx,self.dy,self.dz)def__sub__(self,other):returnTraj(self.x-other.x,self.y-other.y,self.z-other.z,self.dx,self.dy,self.dz)def__truediv__(self,other):returnTraj(self.x,self.y,self.z,self.dx-other.dx,self.dy-other.dy,self.dz-other.dz)def__neg__(self):returnTraj(-self.x,-self.y,-self.z,-self.dx,-self.dy,-self.dz)@propertydeftzero(self):return-self.z/self.dzifself.dzelse0# dataD=[Traj(*(int(x)forxinline.replace(" ","").replace("@",",").split(",")))forlineindata]# ex1fori,dinenumerate(D):forfinD[i+1:]:x,y,t,tt=d*fifx>=m0andx<=m1andy>=m0andy<=m1andt>0andtt>0:ex1+=1# ex2defcorrelate(trucs):dds=[d[0]fordintrucs]dds={dfordinddsifdds.count(d)>1}X={d:sorted(xfordx,xintrucsifd==dx)fordindds}Z={dx:{s*di+dxforx1inxfordiindivisors(x0-x1)forsin[1,-1]}fordx,(*x,x0)inX.items()}returnset.intersection(*Z.values())defrecorrelate(trucs,dx,dy,dz):dds=[d.dzfordintrucs]dds={dfordinddsifdds.count(d)>1}X={d:sorted((_for_intrucsif_.dz==d),key=lambdaf:f.z)fordindds}Y=[{"dy":(x0.y-x1.y-step0*(x0.dy-x1.dy))/step+x0.dy,"x0":x0,"x1":x1,"step":step,"xp":xp,"step0":step0,"src":Traj(x1.x-x1.dx*step0,x1.y-x1.dy*step0,x1.z-x1.dz*step0,dx,dy,dz)+step0,}for_,(*x,x0)inX.items()forx1inxforstepin[(x0.z-x1.z)/(dz-x0.dz)]ifstepforxpin[(x0.x-x1.x)-(dx-x0.dx)*step]forstep0in[xp/(x0.dx-x1.dx)]]returnY,{h["dy"]forhinY},{h["src"].xforhinY}PDX=correlate([(d.dx,d.x)fordinD])PDY=correlate([(d.dy,d.y)fordinD])PDZ=correlate([(d.dz,d.z)fordinD])print(PDX,PDY,PDZ)PDX,PDY,PDZ=(-3,1,2)iftestelse(PDX.pop(),PDY.pop(),PDZ.pop())Y,dys,xs=recorrelate(D,PDX,PDY,PDZ)print(Y)print(dys)print(xs)print(sorted(-h["step0"]forhinY))# This searches for a hailstone going parallel to our rock in one axis.# Turns out that won't be useful, but it could lead to an easy way for initial position# for d in D:# if d.dx == PDX or d.dy == PDY or d.dz == PDZ:# print(d)T=Y[0]["x1"]R=Y[0]["src"]print(R)ex2=R.x+R.y+R.zr1,r2=(2,47)iftestelse(16779,871983857253169)print(f"{'ok' if ex1 == r1 else 'nok'}: {ex1}")print(f"{'ok' if ex2 == r2 else 'nok'}: {ex2}")
J'ai pas trop nettoyé le code hein.
Et dans la version téléphone, j'utilise s et o au lieu de self et other dans la classe Traj (qui ne va quand même pas s'appeler Trajectory non plus, trop long…), tout pour écrire le moins possible !
Pour moi, les ennuis ont commencés : pas d'ordinateur, pas de clavier, juste mon petit téléphone qui ne permet pas vraiment de voir les données avec du recul, et l'extrême pénibilité de coder avec un clavier tactile, toujours à basculer pour chercher les chiffres, les opérations, les =, :, les (), [] et {}.
Bref, pénible, donc on code avec des variables à une ou deux lettres, on fait les algos les plus courts à écrire, et on tâtonne.
La première partie reste assez simple, je n'ai pas mis bien longtemps et le temps de calcul sur téléphone est assez ridicule.
Pour la seconde j'ai tenté de laisser tourner des heures avec l'algo brute-force bête et méchant, mais à part flinguer la batterie on n'arrive pas à grand chose, soyons honnêtes.
Donc être malins.
Et là je l'ai pas été, j'ai tout de suite tenté de réduire le problème aux nœuds d'exploration : les cases où il y a 3 ou 4 directions possibles, et je note les distances entre ces nœuds, puis j'explore le graphe réduit des nœuds.
Sauf que j'ai cru ce problème trop complexe pour mon téléphone, et cherché à simplifier : trouver des nœuds qui sont des passages obligés.
J'étais encouragé par le fait qu'il y en a dans les données de test.
Ça veut dire qu'on peut découper le graphe simplifié en plusieurs graphes qui s'enchaînent.
Donc je code, je débugge, ça marche, je lance sur les données réelles, il me laisse avec comme seul noeud intermédiaire le noeud d'arrivée, et tout ça n'a servi à rien.
Sauf que la réponse tombe malgré tout sans trop d'attente, le problème réduit est suffisamment simple pour que la force brute s'en empare.
Ça met ~10s sur mon PC (avec pypy bien sûr, pour le coup), pas loin de 2 minutes sur le téléphone.
Je n'ai pas cherché plus loin, et j'ai juste remis le code au propre, en virant l'exploration inutile des nœuds intermédiaires, avant de le poster.
La première passe, sur la carte complète, permet aussi de lister les nœuds et la distance les séparant. Techniquement, il pourrait en manquer, puisque l'exploration se fait avec les contraintes de glissement, ça n'est pas le cas, j'ai misé sur cette simplification parce que la denrée qui me manquait vraiment c'était du temps pour coder correctement les choses.
Je me rappelle cependant avoir tenté plein de trucs et finalement avoir été déçu de la simplicité du bidule qui fournit finalement la solution, bref.
Au passage, j'utilise une pile de chemins en cours d'exploration, un deque() bien utile pour ça, plutôt qu'une fonction récursive, on fait exploser la limite de récursivité bien trop vite sur le téléphone. Donc j'ai une boucle et une FIFO d'états à faire avancer, c'est pas trop violent sur la RAM, et on n'atteint pas les limites.
Donc je commence, et j'ai pas fini, les codes dont je n'ai aucune réelle certitude de l'exactitude en toutes circonstances, ça sera pire dans les jours qui viennent.
fromsysimportstdinfromcollectionsimportdequedata=stdin.read().strip().splitlines()W=len(data[0])H=len(data)MAX=W*HM="".join(data)+"#"*WS=M.index(".")F=data[-1].index(".")+MAX-WD={"<":(-1,),">":(1,),"v":(W,),"^":(-W,),".":(1,-1,W,-W)}NODES={}defrexplore(start,end,nodes):"""Exploring full problem, storing path length between nodes A node is a crossroad in the maze : where 3 or 4 destinations are possible. Start and End are also nodes. """defnextpos(pos,previous):fordinD.get(M[pos],0):y=pos+dify>=0andynotinpreviousandM[y]!="#":yieldpos+dnodes[start]={}nodes[end]={}stack=deque()# Current exploring position, [previous positions leading there], last node visitedstack.append((start+W,[start],start))whilestack:x,path,last=stack.pop()yy=list(nextpos(x,path+[x]))ifx==endorlen(yy)>1:# We are on a nodeifxnotinnodes:nodes[x]={}nodes[last][x]=max(nodes[last].get(x,0),len(path)-path.index(last))nodes[x][last]=nodes[last][x]last=xifx==end:# End of the path, yielding ityieldpathcontinueforyinyy:# following all available pathsstack.append((y,path+[x],last))ex1=max(len(q)forqinrexplore(S,F,NODES))defexplore2(start,end):"""Dumb exploration of node graph Small enough that brute-force wins the day fast enough (~10s) """stack=deque([(start,[],0)])whilestack:pos,path,score=stack.pop()ifpos==end:yield(score,path)continuefornode,valin[_for_inNODES[pos].items()if_[0]notinpath]:stack.append((node,path+[pos],score+val))ex2,P=max(explore2(S,F))
Quand je code en Python, ya pas photo, c'est emacs le meilleur IDE.
Quand je code en C, les IDE sont majoritairement équivalents, man est mon principal ami, donc c'est mon shell le plus utile.
Quand je code en ansible, de toute façon, quel que soit l'IDE, je souffre, et mon principal allié est de ne pas avoir internet, ni de jeu vidéo installé sur ma machine, histoire de bien me contraindre à avancer, faut aussi que je décharge complètement mon téléphone, et que j'oublie le câble USB ailleurs, sinon ça avance pas.
Quand je code en JS… Ah, non, j'ai arrêté ça, le PHP aussi.
Bref, je suis pas prêt de lâcher mon emacs, en vrai.
C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…
J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
Déjà les coordonnées sont en 1 dimension : x+y*10+z*100, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.
J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.
fromsysimportstdinfromfunctoolsimporttotal_orderingfromcollectionsimportdequefromitertoolsimportchaindata=deque(stdin.read().strip().splitlines())@total_orderingclassBloc:def__init__(self,blocdef=None,blocname=None,cubes=None):self.name=blocnameifcubes:self.cubes=cubesself.alt=min(cubes)//100returnx,y,z=zip(*((int(__)for__in_.split(","))for_inblocdef.split("~")))self.cubes={a+b*10+c*100forainrange(min(x),max(x)+1)forbinrange(min(y),max(y)+1)forcinrange(min(z),max(z)+1)}self.alt=min(z)def__iter__(self):forpinself.cubes:yieldpdef__eq__(self,o):returnself.alt==o.altdef__lt__(self,o):returnself.alt<o.altdef__contains__(self,_):return_inself.cubesdef__repr__(self):returnf"Bloc#{self.name}({self.cubes})"def__neg__(self):alt=min(_//100for_inself.cubes)*100-100returnBloc(blocname=self.name,cubes={alt+_%100for_inself.cubes})def__pos__(self):alt=max(_//100for_inself.cubes)*100+100returnBloc(blocname=self.name,cubes={alt+_%100for_inself.cubes})def__sub__(self,x):self.cubes={_-100*xfor_inself.cubes}classUniverse:def__init__(self):self.zone=set(range(100))self.blocs={}def__contains__(self,_):# True if bloc can be placed in universereturnnotself.zone.intersection(_.cubes)defadd(self,_):self.zone.update(_)forpin_:self.blocs[p]=_.namedata.extendleft(["0,0,0~9,9,0"])blocs=sorted(Bloc(line,i)fori,lineinenumerate(data))ground=blocs.pop(0)universe=Universe()universe.add(ground)forblocinblocs:while-blocinuniverse:bloc-1universe.add(bloc)# Blocs under each blocdown={bloc.name:{universe.blocs[p]forpin-blocifpinuniverse.blocs}forblocinblocs}cannot={blocfor_indown.values()iflen(_)==1forblocin_}.difference({0})ex1=len(blocs)-len(cannot)
Et l'exercice 2, prenez peur !
topof={}partial={}forblocinsorted(blocs,reverse=True):name=bloc.nameifnamenotintopof:topof[name]=set()# Handling partially supported blocksmypartial=partial.pop(name,set())ifmypartial:replay=Truewhilereplay:replay=Falsenewpart=set()# All blocs partially supported elsewhereotherpart=set(chain.from_iterable(vfork,vinpartial.items()ifknotintopof[name]))for_inmypartial:if_notinotherpart:# That bloc isn't supported by someone else elsewhere, it is mine!topof[name].add(_)topof[name].update(topof.get(_,[]))replay=True# We'll have to restart the search here, because the world changed.else:newpart.add(_)mypartial=newpartifmypartial:partial[name]=mypartial# Sending down my informationsup=topof.get(name,set()).union({name})downward=list(down.get(name,[]))iflen(downward)==1:# Supported by only one other bloc, sending what I'm actively supportingtopof[downward[0]]=topof.get(downward[0],set()).union(up)# Sending known partial information downforblocindownward:partial[bloc]=partial.get(bloc,set()).union({name}).union(partial.get(name,{}))partial.pop(name,None)ex2=sum(len(topof[bloc])forblocincannot)
J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
Et… bah ça marche, en tapant bien sur le code.
Ah non, on manipule des chiffres ou des lettres, réunis en ensembles, en listes, en dictionnaires.
Parfois on peut représenter ce qu'il se passe, parfois pas trop.
Et on doit faire gaffe à pas trop demander de calculs à la machine, sinon ça peut prendre des mois.
[^] # Re: Mes propres fonctions shell
Posté par Yth (Mastodon) . En réponse à la dépêche Archiver ses vidéos : retour d’expérience. Évalué à 2.
Ah c'est fou, ils ont dû faire un effort pour le retirer ffprobe, c'est construit et installé par défaut dans le make install de ffmpeg !
Mais effectivement l'affichage est sensiblement le même avec ffmpeg -i, outre le message d'erreur.
# Mes propres fonctions shell
Posté par Yth (Mastodon) . En réponse à la dépêche Archiver ses vidéos : retour d’expérience. Évalué à 10.
Pour ce genre d'opérations, avec ffmpeg, j'ai un fichier avec des fonctions
bashdedans, il suffit de le sourcer et on peut les utiliser :On a d'abord une série de fonctions pour extraire quelques infos à partir de
ffprobe. La première série extrait une info spécifique d'un fichier, la seconde liste ces infos pour chaque fichier dans la ligne de commande, avec des couleurs, et enfin la dernière fonctionffinforegroupe un peu tout en une ligne.Et il faudrait que je la réécrive, puisqu'à l'origine elle devait peu servir donc tant pis si on exécute 5 fois ffprobe, mais en pratique c'est la seule que j'utilise.
Avec des codes ANSI pour les couleurs aussi.
Par exemple :
Ensuite une multifonction (au moins suisse) de conversion.
Elle est assez imbitable, mais elle fait ce qu'elle prétend faire dans le Usage :
Usage ff [unmap] [format:mkv|mk4|mp4|ogm|mp3|ogg|opus|audio] [scale width] [destination directory] file [files|non existant destination file]Il y a une variable d'environnement CRF=22, qu'on peut bien sûr modifier en ligne de commande.
En gros, elle prend un fichier source, le balance à la destination, et converti.
L'option unmap permet de virer des infos inconvertibles, comme parfois des chapitrages qui ne passent pas d'un avi vers un mkv, ou un truc du genre. Par défaut on copie tous les flux, en transformant l'audio et la vidéo, avec unmap on converti l'audio et la vidéo, on copie les sous-titres, et on oublie le reste. Quand ça plante j'essaie avec unmap, voilà.
Ensuite le format de sortie, ça fait des choix en fonction de mes besoins ponctuels, pas du tout en fonction des besoins du monde entier :
* mkv : par défaut, conversion x265 vers fichier .mkv
* mk4 : conversion x264 vers fichier .mkv, pour compatibilité avec un matériel plus ancien.
* mp4 : conversion x264 vers .mp4, pour compatibilité windows sans VlC.
* ogm : pour faire de l'ogg/vorbis en .ogm, en pratique je n'utilise jamais.
Et les formats d'extraction audio mp3, ogg, opus qui convertissent le flux audio dans le format mentionné, et enfin audio pour extraire le format audio sans y toucher.
L'option suivante est intéressante : elle permet de redimensionner à la largeur souhaitée, en conservant le ratio. Donc pour passer de 4k à fullHD on va mettre 1920, si on veut faire tourner la vidéo sur la vieille machine qui gère pas le fullHD on va mettre 720 par exemple, on aura en 16/9è une vidéo en 720x405.
Après, soit on met [fichier source] [fichier destination], le fichier de destination est facultatif, il sera construit à partir du nom du fichier source - soit on met [répertoire de destination] [plein de fichiers source…], et là aussi les noms de fichiers de destination sont construits à partir de noms des fichiers sources.
On pourra noter si on arrive à déchiffrer les hiéroglyphe bashiques de la 4ème dynastie et demi de l'empire sed, que le nom de fichier est nettoyé : les espaces deviennent des
_, on vire ce qui est après le premier., des trucs du genre. Ça peut être très pourri si la vidéo s'appellema.video.de.vacances.avion va avoirma.mkvavec le nommage automatique. Bien fait.Attention aussi, c'est codé avec des moufles, donc l'ordre des options est impératif, c'est comme ça, et c'est tout. Autant dire que je lance toujours
ffsans rien d'abord pour me rappeler de l'ordre, sinon je fais n'importe quoi.Donc typiquement on va faire pour un lot avec une qualité plus basse :
$ CRF=28; ff 720 ~/tmp/ ~/vidéos_à_traiter/*où on notera bien le mix de paramètres et de variable d'environnement, pour l'incohérence.Et enfin la dernière fonction pratique, qui attends qu'un fichier existe, par exemple si on le télécharge et qu'il est en .part, et qu'il a son nom définitif, sans le .part, à la fin du téléchargement, ou si on le construit par ailleurs, et qu'il est déplacé dans le répertoire de traitement. Puis qui attends qu'il n'y ait pas d'autre processus ffmpeg qui tourne. Et enfin qui appelle
ff. La syntaxe est incohérente avec celle deffc'est pour mieux embrouiller les gens :Ça ne fonctionne qu'en mode source->destination pas en lots, et toutes les options de ff sont mises à la fin plutôt qu'au début.
Donc on va faire :
Et aller se préparer un thé.
Dès que le téléchargement en cours est terminé, la conversion va commencer, et si on en fait deux en parallèle, le premier va convertir et le second attendre que le premier ait terminé avant de démarrer.
Pas de surcharge bourrine de la machine, merci !
Et même pas besoin d'attendre le nez devant l'écran que le téléchargement se termine.
Après on peut envoyer ça à sa cousine qui pourra montrer sa super vidéo de chats en classe à tous ses élèves de terminale sur son PC de l'éducation nationale, avec un format et une qualité que la poussive machine saura probablement appréhender.
[^] # Re: oui mais si on veut éditer un texte ?
Posté par Yth (Mastodon) . En réponse au journal Emacs, le dinosaure fait de la résistance. Évalué à 4.
En simplifiant par linux-vdso, libtinfo, libc, ld-linux et libdl, on a ça :
$ ls -sh /usr/bin/joe
676K /usr/bin/joe
$ ldd /usr/bin/joe
libm, libncurses, libutil
$ ls -sh /usr/bin/nano
316K /usr/bin/nano
$ ldd /usr/bin/nano
libz, libmagic, libncursesw, liblzma, libbz2, libpthread
$ ls -sh /usr/bin/jove
228K /usr/bin/jove
$ ldd /usr/bin/jove
ø
$ ls -sh /usr/bin/zile
256K /usr/bin/zile
$ ldd /usr/bin/zile
libacl, libncursesw, libpthread, libattr
$ ls -sh /usr/bin/micro
12M /usr/bin/micro
$ ldd /usr/bin/micro
libresolv, libpthread, (mais pas libtinfo et libdl)
mg, connais pas, pas dispo, flemme de chercher surtout si le site est mort ça va pas être facile, mais apparemment jove semble assez imbattable (sauf par ed).
Franchement je reste sur joe, parce que ça permet de choisir entre joe, jmacs, jpico, et jstar, avec un seul binaire.
Pour moi c'est jmacs, pour d'autres c'est au choix.
Par habitude aussi :)
[^] # Re: oui mais si on veut éditer un texte ?
Posté par Yth (Mastodon) . En réponse au journal Emacs, le dinosaure fait de la résistance. Évalué à 2.
C'est marrant, en terminal, j'utilise joe en mode jmacs, mais pas emacs directement.
Côté légèreté on fait difficilement mieux.
Ya challenge avec nano, au binaire plus petit mais avec plus de libs.so.
[^] # Re: Pareil ici
Posté par Yth (Mastodon) . En réponse au journal La publicité sur Radio France - podcasts, direct et appli. Évalué à 5.
Généralement l'insulte le podcast le temps de ressortir le téléphone et d'appuyer sur la touche « saute-moi 30s ».
Les insultes c'est pour pas entendre la pub, je préfère, c'est plus courtois et éducatif.
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 5. Dernière modification le 10 janvier 2024 à 15:37.
Comme le dit Renault en dessous, en fait, on parle de n'importe quoi là.
Vu que ça concerne les entreprises.
Donc une entreprise française qui s'arrange pour payer 3% d'impôts à FiscalParadise Island, va en payer 12% en France pour rattrapper le coup.
Ce qui n'empêchera pas FiscalParadise de continuer à proposer des taux bas, mais ça rend son intérêt nettement moindre.
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 3.
Mais si l'impôt minimal mondial est de 15%, ça n'est pas aussi valable pour les gens qui travaillent et paient leurs impôts dans leur propre pays ?
[^] # Re: Slackbuild dans les tuyaux !
Posté par Yth (Mastodon) . En réponse à la dépêche Libération du jeu Blupimania. Évalué à 3.
J'aime bien ça !
Déjà j'ai ajouté un certain nombre de paquet qu'on m'ont parut intéressants, et que parfois j'utilise au quotidien.
Et puis j'en récupère d'autres quand les mainteneurs tournent.
Et j'aime bien soutenir les gens qui viennent sur LinuxFR présenter leurs projets, je maintiens Glewlwyd, un système assez efficace de gestion d'authentification (Oauth2 etc.) présenté ici par son auteur Babelouest.
Certes, c'est pour Slackware, pas la distrib la plus répandue, mais les scripts sont parfaitement compréhensibles par n'importe quel mainteneur de n'importe quelle distrib : c'est du shell très standard, et basé sur un seul outil externe : makepkg qui prend un répertoire et en fait un paquet Slackware.
Donc c'est très facile de s'en inspirer pour faire un paquet sur une autre distribution. Je ne sais pas si ça se fait en pratique, mais ça m'arrive de regarder ce qu'il se passe chez ArchLinux quand j'ai un soucis, pour voir s'ils l'ont résolu ou comment.
Donc ajouter un jeu que je peux faire découvrir à mes enfants, en leur disant que c'est moi qui l'ai rendu disponible (oui, ils ont pas le choix pour le moment, ils sont sous Slackware, voilà), ça me fait plaisir :)
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 3.
Ah, donc le cas inverse d'un Bangladais qui viendrait toucher un SMIC en France, et comme là-bas ça correspondrait à un salaire de ministre, il serait taxé à 45%, ce qui est ingérable ici.
Pour ta dernière question, c'est facile : si une telle loi passe, je pense surtout que le pays de destination va juste faire évoluer ses taxes pour prendre la part entière des 15%, et ne rien laisser au pays d'origine, rien à perdre, tout à gagner, et pour l'employé c'est pareil, voire plus simple puisque taxé à un seul endroit.
Dilemme moral résolu…
[^] # Re: Illisible
Posté par Yth (Mastodon) . En réponse au lien L’impôt minimum mondial de 15 % est lancé. Évalué à 3.
Et le salaire il ne dépend pas du niveau de vie du pays où tu travailles ?
Quand je lis 15%, je lis 15% moi.
Donc mettons un français part vivre par exemple au Bangladesh. Cette personne bosse localement, pour un salaire normal là-bas, donc absolument minuscule en France, bah sa taxe de 15% de son salaire ridicule, soit peu de choses, mais tout de même 15% rapport au niveau de vie local.
Que veux-tu faire de plus ou de différent ?
Quel cas poserait problème ?
[^] # Re: le bit de poids faible
Posté par Yth (Mastodon) . En réponse au lien la manière la plus efficace de déterminer si un nombre est pair. Évalué à 3.
La façon dont c'est utilisé. Pour faire du code sans code, construire des algorithmes complexes à base de modules maison, et de templating Jinja.
C'est devenu extraordinairement difficile de savoir comment fonctionne un playbook.
En plus certains rôles, certaines tasks, utilisent des variables d'environnement, définies très loin de là.
C'est du bricolage très éloigné de l'utilité normale d'ansible…
Je suis plus traumatisé par l'utilisation qui est faite que par ansible lui-même, mais j'en viens à haïr le yaml+jinja…
[^] # Re: Journal franchement malhonnête !
Posté par Yth (Mastodon) . En réponse au journal J’ai tenté de libérer une habitation, mais l’ayant-droit nous a mis des bâtons dans les roues. Évalué à 4.
C'est pas vendu avec les frigos ça ?
De série ?
# Slackbuild dans les tuyaux !
Posté par Yth (Mastodon) . En réponse à la dépêche Libération du jeu Blupimania. Évalué à 5.
Merci pour ton nouveau portage Mathieu !
Je n'avais pas eu le temps de m'y mettre plus tôt, mais c'est chose faite, le slackbuild de Blupimania est prêt, et sera disponible dans le dépôt dès demain probablement.
Il a fallut taper un peu dessus, parce que la Slackware 15.0 a une version un poil trop ancienne de SDL2_image et SDL2_mixer.
Comme pour la dernière version de Planetblupi avec SDL2_ttf.
J'embarque les versions à jour dans le répertoire du jeu, recompilés pour l'occasion, et youplà.
C'est rigolo comme jeu, j'étais complètement passé à côté des blupis dans les années 90.
[^] # Re: Journal franchement malhonnête !
Posté par Yth (Mastodon) . En réponse au journal J’ai tenté de libérer une habitation, mais l’ayant-droit nous a mis des bâtons dans les roues. Évalué à 6.
Ouhlà, tu veux pas savoir comment elle les a tricotées ses sources !
[^] # Re: Ont-ils bien modélisé les milliers de morts dus à l'Hydroxychloroquine ?
Posté par Yth (Mastodon) . En réponse au journal jeu libre Covid-25 !. Évalué à 8.
Flûte, mon beau-père est décédé d'Alzheimer et de son diabète alors qu'il venait de chopper le Covid qui n'a fait que l'achever.
Ma grand-mère court toujours à 96 ans.
Et le taux de mortalité dans ma commune, pourtant si caractéristique et si généralisable à l'ensemble du village planétaire, est resté stable.
Mes propres doses de vaccin n'ont pas été fichues de m'achever, malgré tous mes efforts !
Et je n'ai absolument aucune connaissance qui soit décédée depuis le Covid19 alors qu'elle était vaccinée, excepté mon beau-père sus-cité, alors que leur taux de vaccination reflète la moyenne nationale.
Je me vois dans l'extrême obligation de décorréler le vaccin de tous ces évènements perturbants, selon mon étude scientifiquement empirique, et je sais de quoi je parle, j'ai plusieurs diplômes post-bac, j'ai travaillé dans des labos de recherche, ma tante est médecin, mes parents ingénieurs, et mes frères et sœurs sont tous docteurs, et j'ai déjà gagné plusieurs fois à Pandémie, et ma fille fait du Triathlon, et je bois du thé.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Oui, ça fonctionne parce que le nombre de coupe est faible dans un problème plutôt grand (1 coupe pour 1000 arêtes), et que les coupes sont assez éloignées.
J'ai supposé que ça pouvait être le cas, et j'ai gagné.
Après j'ai eu la chance de prendre un sommet initial assez éloigné de mes coupes. Par hasard en fait parce que si on regarde l'algo, je prend le dernier sommet source défini dans les données.
Et j'ai pris celui là parce que je l'avais sous la main à la fin de l'analyse des données, donc c'était vraiment sans arrière pensée : lui ou un autre, qu'importe ?
Et en fait, ça m'aurait été très difficile de comprendre pourquoi l'algo bloque à un moment, quelle est la topologie du graphe, et pourquoi je ne peux plus avancer, et comment savoir comment avancer.
Parce que sur téléphone c'est pénible, difficile à lire, prise de tête. Si ça avait raté, j'aurais probablement dû partir sur une toute autre idée (une exploration en largeur, en notant la taille des liens possibles ? du brute force trop long probablement. D'autres simplifications, trouver des zones fermées et les réduire ? Récursivement ?), voire attendre d'enfin récupérer un ordinateur.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Après vérification, mon hack, au lieu de tout ajouter, pourrait ajouter 1 seul sommet au hasard parmi les sommets possibles.
Je tombe sur la solution, mais pas toujours pour le coup, en y allant au pif, je tombe parfois sur un mauvais chemin.
Je sais déjà que ça peut fonctionner, parce que ça fonctionne en les ajoutant tous, mais ça veut surtout dire qu'on peut brancher sur une exploration 1 par 1 de tous les sommets possibles, quand on coince avec l'algo de base, et faire une exploration.
On doit pouvoir avoir un algo capable de nous assurer qu'on trouve une solution.
Encore une fois, tout ça fonctionne parce qu'on sait qu'on a trois sommets à couper hein.
C'est un brin moche mais voilà, on peut retomber sur nos pieds.
[^] # Re: Pas de Z3, mais au moins Z^3 neurones grillés
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 24. Évalué à 2. Dernière modification le 03 janvier 2024 à 10:46.
Ah, et côté perfs, on est sous la seconde pour l'exécution en python.
Je ne suis pas sûr que ça aurait été beaucoup plus long si j'avais codé à l'arrache ma propre fonction pour les diviseurs, plutôt que d'utiliser sympy : on n'en calcule pas tant que ça, et au bout du compte les nombres ne sont pas si grands, avec de l'ordre de 200 diviseurs, et une racine carrée autour de 10 millions, ça se réduit assez vite, c'est pas vraiment là qu'on va perdre du temps.
Avec sympy c'est immédiat.
On perd probablement plus de temps à charger le module,
from sympy import divisorsprend un temps visible dans un shell python, ça doit être la majeure partie de la seconde qui part là-dedans !Bien sûr, ici, je sais que j'ai un dx, dy et dz, et l'algorithme ne s'adapte pas à une éventuelle situation où on n'en n'aurait que deux sur trois, mais à part de forcer à faire du code plus propre, ça ne changerait pas grand chose à l'algorithme final qui n'utilise que dz et dx et valide le dy recalculé.
Et comme dit plus haut, je calcule un paquet de fois la solution à partir de toutes les parallèles en z, alors qu'une seule suffit.
Bref, un algo plus générique ne serait pas beaucoup plus complexe, il faudrait formaliser mieux.
Par contre si on n'a de parallèles que sur un seul axe, je coince a priori. Il faudrait essayer des valeurs possibles sur un autre axe, en supposant qu'elles ne soient pas trop grandes, ce qui est le cas puisque
dx=-242, dy=-49, dz=209, donc en explorant depuis 0 en positif et négatif, on va mettre quelques centaines de tests pour trouver la solution.Et c'est nettement pire si on n'a aucune parallèle sur aucun axe…
La force brute en essayant au pif des dx, dy et dz sans en connaître aucun, devrait permettre de tomber sur la solution en quelques dizaines de millions de tests, ce qui reste faisable, et probablement assez rapide (quelques minutes ? une heure max ?) sur un ordinateur moderne.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 25. Évalué à 2.
Ma solution est beaucoup plus rapide : 0,07s, donc assez négligeable devant le temps de démarrage de python.
Mais…
Je ne sais pas qu'elle fonctionne, je le constate.
Et ça exploite très fortement le fait qu'on ait trois liens à couper, sans cette information je ne sais pas quand m'arrêter, l'algo n'est plus du tout le même.
En gros je fais l'hypothèse que deux liens à couper ne sont pas proches (partageant un même sommet), et que je vais avoir un peu de chance.
Je pars d'un sommet, au pif, mais ça rate s'il s'agit d'un sommet d'une des arêtes à supprimer. Là je me dis que si je ne trouve pas de solution, je peux prendre un autre sommet au pif, normalement, au bout du 7è je suis certain d'avoir au moins essayé avec un sommet qui n'est pas dans une des arêtes à supprimer.
Là ça a fonctionné directement.
Je considère comme « exploré » toutes ses arêtes, et les sommets directement connectés.
Et j'itère :
* Je considère l'ensemble des arêtes liées à tous mes sommets, et pas déjà explorées.
* Je considère l'ensemble des nouveaux sommets accessibles via ces arêtes.
* Pour chacun de ces nouveaux sommets, si il est accédé par au moins deux des nouvelles arêtes, je l'ajoute.
* Et je reconstruit l'ensemble des arêtes explorées à partir des liens possibles entre mes sommets explorés.
* Il me reste un ensemble d'arêtes considérées, mais rejetées, et qui seront à nouveau considérées le coup d'après.
* Si je n'ajoute aucun nouveau sommet, j'ai a priori fini.
Normalement, si il n'y a pas deux arêtes à couper qui partagent un même sommet, je ne peux pas « traverser » ces arêtes avec mon algorithme.
Il se trouve que ça s'arrête très très vite sans donner de résultat, donc j'ai juste essayé un truc :
* Si l'ensemble des arêtes que je peux atteindre mais que je n'ai pas considérées n'est pas de taille 3, alors j'ajoute unilatéralement toutes les arêtes possibles : je ne suis pas allé assez loin, il faut que j'avance, et c'est la méthode la plus naïve pour avancer.
À noter que ça peut foirer si l'un de ces nouvelles arêtes et une des arêtes à couper.
Je n'ai pas regardé dans le détail, mais je pense que ce problème n'existe qu'au démarrage, il faudrait peut-être partir directement à deux arêtes de distance de mon sommet d'origine (la suite me prouvera que j'ai raison pour le démarrage, mais tort globalement).
Bref, ça a fonctionné puisqu'après mon algorithme s'est arrêté à trois arêtes accessibles mais mises de côté, et là on sait que c'est le bon résultat, pif paf, terminé.
L'algorithme mériterait bien plus de vérifications, et éventuellement une boucle sur un sommet de démarrage différent, jusqu'à tomber sur une solution.
Il faudrait au minimum identifier quand est-ce que j'ai besoin de mon hack pour avancer un peu plus loin dans le noir, peut-être faire une exploration en branches pour ajouter un sous-ensemble et tester, histoire de s'assurer qu'on va trouver un truc viable, ou tout explorer sans trouver.
Mais ça a fonctionné du premier coup.
On peut noter qu'il y a 1502 sommets et 3363 arêtes dans mes données, donc au final démarrer depuis un des sommets à éviter, ça serait surtout beaucoup de malchance, c'est la taille du problème qui m'a incité à tester cette approche, en me disant que j'avais plus de chance de tomber dans le « gras » du problème que pile là où il ne fallait pas.
J'ai cherché des simplifications, un peu, avant, comme de simplifier les triangles (
A<->B<->C<->A), mais autant ça donne un peu quelque chose sur les données de test (on peut brute-forcer la recherche sans soucis : prendre trois arêtes et voir si on a coupé en deux), c'est inutile sur les données réelles, on simplifie de 42 arêtes, sur 3363 ça change rien.Par contre, en nettoyant mon code, je vois que le « hack » sert trois fois : à 15 sommets à explorer (1ère itération, donc dès le début), à 54 sommets à explorer (3ème itération), puis à 217 sommets à explorer (345 déjà validés, 13ème itération !), et là on est quand même assez loin, on aurait très facilement pu mal tomber, sachant que le résultat arrive à 18 itérations.
Bilan, je dirais que j'ai plutôt eu de la chance avec mon sommet de départ…
Voilà le code nettoyé :
Pour une fois, mes expérimentations téléphoniques pour coder moins et avoir de la chance rapidement, ont portées leurs fruits, j'étais le premier surpris :)
Mais c'est rude de faire du code aussi approximatif, et de s'en contenter au bout du compte, ça heurte vraiment ma façon de penser.
Enfin, c'est pour ça que j'ai validé cette étoile avant la seconde du jour précédent.
# Pas de Z3, mais au moins Z^3 neurones grillés
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 24. Évalué à 2.
C'est celui qui m'a le plus gonflé sur téléphone.
Pas la partie 1 bien sûr, encore expédiée assez vite dès que je m'y suis mis (c'est à dire une fois le jour précédent terminé).
La partie 2.
Où les données de test laissent entrevoir plein de simplifications qui ne fonctionnent pas avec le vrai problème.
Et une résolution finale qui ne fonctionne pas sur les données de test !
J'ai assez modélisé mes trajectoires de grêlon, pour faire des opérations en masse, je cherchais des simplifications, des translations, pivots, etc, mais je n'ai jamais réussi à résoudre autre chose que les données de test comme ça : à chaque fois il fallait tester au moins un paramètre final, et le plus complexe à tester a au final une valeur de 57 milliard et quelques au minimum, donc on ne va pas l'atteindre comme ça, en cherchant…
C'est le temps nécessaire à notre caillou pour atteindre un élément.
On tombe pas dessus par hasard.
Dans les données de test, c'est 1, ça simplifie grandement le problème.
En fait, il faut comprendre le problème.
On choisit un point d'origine et une trajectoire :
Traj(x=393358484426865.0, y=319768494554521.0, z=158856878271783.0, dx=-242, dy=-49, dz=209)À partir de là on choisit des entiers, grands, ça va de quelques dizaines de milliards à probablement mille milliards (j'ai un 943 538 374 225 pour un grêlon), ça définit des points de départ sur notre trajectoire.
De chacun de ces points on choisit une direction, et on fait reculer notre grêlon du temps nécessaire à atteindre le point en question.
Voilà, on a notre problème posé, on oublie la trajectoire initiale, il faut la retrouver.
Facile à construire, pas simple à démêler…
Et franchement, il faut trouver des simplifications.
Et là on les trouve avec une première constatation : ce qui se passe en x, y et z est presque entièrement décorrélé, pour trouver dx, dy ou dz, on n'a besoin de se concentrer que sur la coordonnée en question. Après on fera une corrélation sur l'écart en temps entre deux grêlons, qu'on peut connaître pour dx, dy ou dz, et qui sera donc égale pour les autres, et permet de faire une triangulation.
Et une seconde constatation, sur un axe on a des grêlons parallèles, c'est à dire qui ont le même dx, le même dy ou le même dz.
Et ça va nous aider.
C'est même la seule simplification que j'ai trouvé pour réussir à résoudre ce problème.
Parce que si entre deux grêlons on a un dx identique, ça veut dire que l'écart en x entre ces deux grêlon est une constante.
Et donc qu'on parcourt cette écart avec un nombre entier d'étapes, chacune d'un nombre entier de décalages.
Donc pour deux grêlons a et b parallèles en x, donc a.dx==b.dx, on a que l'écart en x (a.x - b.x) est divisible par
r.dx-a.dxou r est notre trajectoire résultat à trouver. On cherche r.dx.Et ben on va chercher les diviseurs de
a.x - b.x, sans connaître le sens on va tous les prendre en positif ou négatif, on ajoute a.dx, et on a des valeurs possibles de r.dx.Et on cherche les valeurs communes entre tous les éléments parallèles en x, on aura réduit drastiquement nos possibilités de r.dx.
En pratique, si on n'oublie pas de considérer les diviseurs en négatif ou positif (parce qu'on ne sait pas dans quel sens on va, on a juste deux grêlons au pif), on va trouver une seul valeur pour dx, dy et dz.
On a la direction parfaite de notre caillou !
Ça aurait pu rater, on aurait pu avoir des choix et devoir tester parmi ces choix lesquels seraient les bons, mais on sent que même si on en avait eu plusieurs, ça n'aurait pas été trop explosif, et si l'algo pour finir le boulot est pas trop pourri on pouvait tout tester.
Là, suite à une erreur de ma part, j'ai aussi pondu un algorithme capable de calculer dy si on connaît dx et dz !
Sauf que ça foirait, à cause de mon erreur, mais j'ai corrigé et poursuivi, en pratique je calcule la solution pour tous les grêlons parallèles deux à deux en x, et je valide cette solution en montrant qu'ils donnent tous le même résultat. Ça m'a permis de débugger et d'être absolument certain d'avoir le bon résultat au bout du compte.
En pratique, quand on a dx, dy, et dz, il suffit de prendre deux grêlons parallèles selon n'importe quel axe, et on va avoir la solution.
On calcule le nombre d'étapes (microsecondes) pour que notre caillou passe de l'un à l'autre, ce qui est facile si on a compris l'algorithme qui a permit de trouver les dx, dy et dz : on divise l'écart en x
a.x-b.xparr.dx-a.dxqui sont connus.Sachant le temps séparant ces deux chocs, on peut calculer l'écart en y ou en z, constaté parce que nos grêlons ne sont pas parallèles en y ou z, et ça va nous permettre de savoir de combien d'étapes dans le temps il faut remonter pour combler cet écart, et faire en sorte de bien percuter les deux grêlons, en x, y et z.
En pratique mon algorithme, que je n'ai pas simplifié, calcule dy à partir de la connaissance de dx et dz sur des grêlons parallèles en z, c'est pas trop compliqué une fois qu'on a le nombre d'étapes à remonter dans le temps, et on valide déjà qu'on trouve pour tous la bonne valeur de dy. Puis on fait remonter effectivement dans le temps notre caillou depuis sa percussion avec a pour trouver un point de départ.
J'ai juste validé que r.x était identique pour tous, mais tant que ce n'était pas le cas c'était que j'avais une erreur dans mes formules.
Les maths sont simples, mais prise de tête et il faut bien se torturer les neurones.
Au final je fais bien trop de calculs, qui me donnent tous le même résultat, heureusement, et ça prend moins d'une seconde malgré tout.
Voici donc le code, avec trop de méthodes inutilisées dans mes Trajectoires, et des noms de variable bien trop peu lisibles.
Heureusement le code n'est pas trop complexe, et reste a peu près lisible.
Il y a un hack au milieu pour les données de test, puisqu'on n'a pas assez de parallèles pour trouver dx, dy et dz, je force les valeurs, connues, pour valider la seconde partie de l'algorithme.
Mais ça aurait pu faire l'objet d'un développement intéressant pour valider sur un ensemble de valeurs possible, si on n'avait pas eu un dx, dy et dz unique à l'issue de la première partie.
Rendant nécessaire de tester plusieurs cas et de vérifier qu'on ait bien un même résultat. Ça aurait été immonde à débugger par contre…
J'ai tout de même utilisé sympy pour les diviseurs, pour le coup c'était quand même plus simple que de coder une fonction moi-même.
J'ai pas trop nettoyé le code hein.
Et dans la version téléphone, j'utilise s et o au lieu de self et other dans la classe Traj (qui ne va quand même pas s'appeler Trajectory non plus, trop long…), tout pour écrire le moins possible !
# Les ennuis commencent...
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 23. Évalué à 2.
Pour moi, les ennuis ont commencés : pas d'ordinateur, pas de clavier, juste mon petit téléphone qui ne permet pas vraiment de voir les données avec du recul, et l'extrême pénibilité de coder avec un clavier tactile, toujours à basculer pour chercher les chiffres, les opérations, les =, :, les (), [] et {}.
Bref, pénible, donc on code avec des variables à une ou deux lettres, on fait les algos les plus courts à écrire, et on tâtonne.
La première partie reste assez simple, je n'ai pas mis bien longtemps et le temps de calcul sur téléphone est assez ridicule.
Pour la seconde j'ai tenté de laisser tourner des heures avec l'algo brute-force bête et méchant, mais à part flinguer la batterie on n'arrive pas à grand chose, soyons honnêtes.
Donc être malins.
Et là je l'ai pas été, j'ai tout de suite tenté de réduire le problème aux nœuds d'exploration : les cases où il y a 3 ou 4 directions possibles, et je note les distances entre ces nœuds, puis j'explore le graphe réduit des nœuds.
Sauf que j'ai cru ce problème trop complexe pour mon téléphone, et cherché à simplifier : trouver des nœuds qui sont des passages obligés.
J'étais encouragé par le fait qu'il y en a dans les données de test.
Ça veut dire qu'on peut découper le graphe simplifié en plusieurs graphes qui s'enchaînent.
Donc je code, je débugge, ça marche, je lance sur les données réelles, il me laisse avec comme seul noeud intermédiaire le noeud d'arrivée, et tout ça n'a servi à rien.
Sauf que la réponse tombe malgré tout sans trop d'attente, le problème réduit est suffisamment simple pour que la force brute s'en empare.
Ça met ~10s sur mon PC (avec pypy bien sûr, pour le coup), pas loin de 2 minutes sur le téléphone.
Je n'ai pas cherché plus loin, et j'ai juste remis le code au propre, en virant l'exploration inutile des nœuds intermédiaires, avant de le poster.
La première passe, sur la carte complète, permet aussi de lister les nœuds et la distance les séparant. Techniquement, il pourrait en manquer, puisque l'exploration se fait avec les contraintes de glissement, ça n'est pas le cas, j'ai misé sur cette simplification parce que la denrée qui me manquait vraiment c'était du temps pour coder correctement les choses.
Je me rappelle cependant avoir tenté plein de trucs et finalement avoir été déçu de la simplicité du bidule qui fournit finalement la solution, bref.
Au passage, j'utilise une pile de chemins en cours d'exploration, un deque() bien utile pour ça, plutôt qu'une fonction récursive, on fait exploser la limite de récursivité bien trop vite sur le téléphone. Donc j'ai une boucle et une FIFO d'états à faire avancer, c'est pas trop violent sur la RAM, et on n'atteint pas les limites.
Donc je commence, et j'ai pas fini, les codes dont je n'ai aucune réelle certitude de l'exactitude en toutes circonstances, ça sera pire dans les jours qui viennent.
[^] # Re: le bit de poids faible
Posté par Yth (Mastodon) . En réponse au lien la manière la plus efficace de déterminer si un nombre est pair. Évalué à 3.
Quand je code en Python, ya pas photo, c'est emacs le meilleur IDE.
Quand je code en C, les IDE sont majoritairement équivalents, man est mon principal ami, donc c'est mon shell le plus utile.
Quand je code en ansible, de toute façon, quel que soit l'IDE, je souffre, et mon principal allié est de ne pas avoir internet, ni de jeu vidéo installé sur ma machine, histoire de bien me contraindre à avancer, faut aussi que je décharge complètement mon téléphone, et que j'oublie le câble USB ailleurs, sinon ça avance pas.
Quand je code en JS… Ah, non, j'ai arrêté ça, le PHP aussi.
Bref, je suis pas prêt de lâcher mon emacs, en vrai.
[^] # Re: En binaire et en puissances de 2
Posté par Yth (Mastodon) . En réponse au message Advent of Code, jour 13. Évalué à 2.
Pertinent, je n'ai pas révisé mon opération logiques depuis un moment, je n'ai plus les réflexes…
Je vais me rafraîchir ça.
# On fait tomber des trucs, mais on fait pas de Tetris.
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 22. Évalué à 2.
C'est le dernier jour où je vais avoir le temps de la faire, la suite ça sera peut-être dans une semaine…
J'ai inventé un algo un peu tordu, assez efficace, rude à piger, donc à débugger.
Déjà les coordonnées sont en 1 dimension :
x+y*10+z*100, on va simplifier, surtout qu'on ne fait que des mouvements vers le bas, aucun test aux bornes à faire.J'ajoute un bloc de 10x10 en 0 pour poser le bazar.
Une structure de Blocs assez modélisée, une autre pour l'Univers bien plus simple et à la fin un algo tordu.
Et l'exercice 2, prenez peur !
J'ai pas vraiment le temps de remettre au propre, en gros je pars du haut, et je « pose » les blocs les uns sur les autres, en notant ceux qui sont partiellement posés, et où.
Et puis à chaque bloc, j'essaie de simplifier par ceux qui ne sont partiellement posés plus que sur lui.
Et… bah ça marche, en tapant bien sur le code.
[^] # Re: Pas d'exemple
Posté par Yth (Mastodon) . En réponse au message Advent of Code 2023, jour 20. Évalué à 2.
Ah non, on manipule des chiffres ou des lettres, réunis en ensembles, en listes, en dictionnaires.
Parfois on peut représenter ce qu'il se passe, parfois pas trop.
Et on doit faire gaffe à pas trop demander de calculs à la machine, sinon ça peut prendre des mois.