Comment trouver une formule "black magic"
Bonjour,
j'étais sur https://codegolf.stackexchange.com/questions/223314/number-of-coins-needed-to-make-change/
En gros c'est un problème de code pour chercher le nombre minimal de pièce/billet pour obtenir une valeur quelconque.
En regardant les réponses, je tombe sur ça (en python) :
f=lambda x:x and int("0112212233"[x%10])+f(x/10)
C'est une fonction récursive qui ajoute les résultats de chaque dizaine, je comprends ce qu'elle fait.
Un peu plus tard je tombe sur une autre réponse :
f=lambda n:n and(n%10)**55%767%4+f(n/10)
Là est ma question comment à partir du tableau [0->9] =>[0,1,1,2,2,1,2,2,3,3]
on peut en arriver à trouver la fonction (((n%10)^55)%767)%4 ?
[Edit]
Le gars a juste fait un brute force,
j'ai fait un petit programme pour tester ça :
Le dernier modulo 4 est logique mais le reste...
j'étais sur https://codegolf.stackexchange.com/questions/223314/number-of-coins-needed-to-make-change/
En gros c'est un problème de code pour chercher le nombre minimal de pièce/billet pour obtenir une valeur quelconque.
En regardant les réponses, je tombe sur ça (en python) :
f=lambda x:x and int("0112212233"[x%10])+f(x/10)
C'est une fonction récursive qui ajoute les résultats de chaque dizaine, je comprends ce qu'elle fait.
Un peu plus tard je tombe sur une autre réponse :
f=lambda n:n and(n%10)**55%767%4+f(n/10)
Là est ma question comment à partir du tableau [0->9] =>[0,1,1,2,2,1,2,2,3,3]
on peut en arriver à trouver la fonction (((n%10)^55)%767)%4 ?
[Edit]
Le gars a juste fait un brute force,
j'ai fait un petit programme pour tester ça :
#This was brute-forced. I wrote a short script that tried n**p%m%4 for 1<p<100 and 1<m<10000. #I think I've tried n*p%m%4 and n*p%m0%m1%4 before that but could only get 9 correct results that way. – Arnauld 5 mins ago #liste recherché goal = [0,1,1,2,2,1,2,2,3,3] def f(p,m) : tab = [] for i in range(10): tab.append( i**p%m%4) return tab for p in range(1,1000): for m in range(1,1000): rslt = f(p,m) if rslt == goal: print('found p= ' + str(p )+ ', m= ' + str(m) + ' rslt = ' + str(rslt))Effectivement je trouve :
found p= 55, m= 767 rslt = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3] found p= 403, m= 767 rslt = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3] found p= 751, m= 767 rslt = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3] found p= 875, m= 941 rslt = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3]Après pourquoi cette formule " i**p%m%4"? (ou ces formules comment écrite dans le commentaires)
Le dernier modulo 4 est logique mais le reste...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Et de fil en aiguille, l'objectif du jeu, c'est de trouver un code le plus court possible pour dire :
Comment on arrive à cette formule alambiquée : renvoyer $(n^{55})%767%4 ?
Par tatonnement !
On sait que la fonction doit renvoyer une valeur entre 0 et 3, donc on se dit qu'on va utiliser la fonction modulo 4. Surtout qu'il faut simplement 2 caractères pour coder ce calcul.
Ensuite, toujours la même contrainte, on veut un code le plus court possible.
Donc on teste des fonctions de type (n^b)%c%4, on teste plein de valeurs de b et c, et pour chaque valeur de b et c, on regarde si pour les 10
nombres 0 à 9, on trouve bien la valeur voulue.
Si oui, bingo on a un code très court qui convient.
Ce petit simili-programme devrait afficher bingo pour b=55 et c=767
Les équations de la forme n*p%m ou n^p%m sont les plus courtes à écrire en langage informatique
et l'algo de brute-force suffisamment rapide vu qu'il n'a pas besoin de tourner en temps réel.
En tout cas merci pour l'explication
Pour donner du contexte je suis ces fils sur stack car j'aime bien programmer et si je trouve des manières plus élégante,plus courtes, ou moins lourdes selon certain critères définis sans trop perdre de lisibilité, ça m’intéresse.
Et la je vois une transformation d'une liste à une autre avec des Black Magic Number et sur le coup je me suis dis que c'etait peut être facile de faire cette transformation sans faire du bruteforce à outrance.