Divisibilité des préfixes

Nov 02 2020

Inspiration

Étant donné un entier positif \$1 \le n \le 9\$, sortie tous les positifs \$n\$-digit entiers \$i\$ pour lequel ce qui suit est vrai:

  • Chaque chiffre de \$1\$à \$n\$apparaît exactement une fois dans \$i\$. Par conséquent, \$i\$Les chiffres de sont une permutation des chiffres de \$1\$à \$n\$.
  • \$i\$est divisible par \$n\$
  • Suppression du chiffre le plus à droite de \$i\$donne un autre entier \$i_{\text{trunc}(1)}\$qui est divisible par \$n-1\$
  • Suppression du chiffre le plus à droite de \$i_{\text{trunc}(1)}\$donne un autre entier \$i_{\text{trunc}(2)}\$qui est divisible par \$n-2\$
  • Et ainsi de suite, jusqu'à ce que \$i_{\text{trunc}(n-1)}\$, qui est divisible par 1.

Par exemple, pour \$n = 3\$, l'un de ces nombres entiers est \$321\$, comme \$321\$est divisible par \$3\$, \$32\$par \$2\$et \$3\$ par 1.

Pour \$n = 4, 5, 7\$, il n'y a pas de tels entiers. Dans ce cas, vous pouvez tout de sortie qui ne peut être confondue avec une sortie possible (par exemple 0, []rien, etc.). Pour \$n = 3, 6\$, vous pouvez afficher les deux nombres dans n'importe quel format dans lequel les deux nombres sont clairement séparés l'un de l'autre.

C'est du code-golf donc le code le plus court en octets l'emporte.

Si vous utilisez une méthode de table de recherche, les points brownie \${}^\dagger\$ sont attribués si vous incluez également une version qui calcule la sortie correcte.

\${}^\dagger\$Les points brownie peuvent ou non prendre la forme d'un vote favorable

Cas de test

Ces cas sont exhaustifs, vous ne recevrez donc jamais (ou devrez gérer) une entrée non incluse ici.

n -> i
1 -> [1]
2 -> [12]
3 -> [123, 321]
4 -> []
5 -> []
6 -> [123654, 321654]
7 -> []
8 -> [38165472]
9 -> [381654729]

Réponses

5 ovs Nov 02 2020 at 19:28

05AB1E , 8 octets

LœJʒηāÖP

Essayez-le en ligne!

Commenté :

L         # push [1..n]
 œ        # push all permutations
  J       # join each permutation into a number
   ʒ      # filter those numbers on:
    η     #   each prefix ...
      Ö   #   ... is divisible ...
     ā    #   ... by its index
       P  #   take the product (all)
5 xnor Nov 02 2020 at 21:12

Python 2 , 68 octets

lambda n:[`s`[:n]for s in 321654,381654729,123654][380712>>n*2&3::2]

Essayez-le en ligne!

Sort une liste de chaînes.


71 octets

lambda n:[0,1,12,[123,321],0,0,[123654,321654],0,38165472,381654729][n]

Essayez-le en ligne!

Juste un hardcode ennuyeux. Produit un seul nombre, ou une liste de deux nombres, ou 0 pour aucune sortie.

Aucune des autres méthodes que j'ai essayées ne semblait susceptible d'être plus courte que celle-ci. Par exemple, une idée est de générer des nombres comme préfixes d'un seul nombre, générant comme 123654/10**(6-i).

Une méthode objet donne la même longueur. Malheureusement, nous ne pouvons pas utiliser la plus courte .popcar elle rend la fonction non réutilisable car elle modifie la liste à chaque appel.

[0,1,12,[123,321],0,0,[123654,321654],0,38165472,381654729].__getitem__

Essayez-le en ligne!

Le crénelage de la constante la plus longue donne également la même longueur:

lambda n,c=381654729:[0,1,12,[123,321],0,0,[123654,321654],0,c/10,c][n]

Essayez-le en ligne!

4 xash Nov 02 2020 at 18:43

J , 42 37 octets

Calcule les nombres.

0({:#~0=[:+/#\|])@|:i.@!10&#.\@A.1+i.

Essayez-le en ligne!

  • 1+i. 1… n
  • i.@!…@A. toutes les permutations possibles de 1… n
  • 10&#.\ convertir chaque préfixe d'une permutation en un nombre
  • 0(…)@|: transposez la matrice et…
  • #\|] 1… n mod les préfixes, par ex. 1 2 3 | 1 12 123
  • 0=[:+/additionnez le résultat; est-ce 0?
  • {:#~ puis prenez le dernier préfixe de la permutation (la permutation elle-même)
3 user Nov 02 2020 at 22:36

Scala, 81 80 octets

| =>1.to(|).mkString.permutations.filter{i=>1 to|forall(r=>i.take(r).toInt%r<1)}

Essayez-le dans Scastie

Explication:

| =>                          //n, the input
  1.to(|)                     //Range to n
    .mkString                 //Turn it into a string
    .permutations             //Get all permutations
    .filter{ i =>             //Filter them
      1 to | forall(r =>      //For every r from 1 to n
        i.take(r).toInt       //The number made from i's first r digits
          % r < 1             //Should be divisible by r
      )
    }
2 Neil Nov 02 2020 at 19:50

Charbon , 25 octets

NθΦEXχθIι⬤…·¹θ›№ιIλ﹪I…ιλλ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Trop lent pour n>5sur TIO. Explication:

Nθ

Entrée n.

ΦEXχθIι

Liste tous les nombres entiers ijusqu'à 10ⁿ, tels que ...

⬤…·¹θ

... pour chaque entier lde 1à n...

›№ιIλ﹪I…ιλλ

lest un chiffre de iet le lpréfixe -character de iest divisible par l.

Version 28 octets légèrement plus rapide:

NθΦEX⊕θθ⍘ι⊕θ⬤…·¹θ›№ιIλ﹪I…ιλλ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication: Génère les chiffres en base n+1au lieu de base 10, permettant ainsi de compléter n=6sur TIO.

Version 29 octets la plus rapide utilisant une table de recherche compressée:

§⪪”)‴a3HSGS⸿Dπ¬Z⦄O<ε≔<πUθ8”0N

Essayez-le en ligne! Le lien est vers la version verbeuse du code.

2 J42161217 Nov 02 2020 at 18:38

Wolfram Language (Mathematica) , 78 octets

(f=FromDigits)/@Select[Permutations@Range[s=#],f@#[[;;k]]~Mod~k~Sum~{k,s}<1&]&

Essayez-le en ligne!

-8 octets de @att

2 Razetime Nov 03 2020 at 03:47

Husk , 15 octets

mdföΛIṠz¦ŀmdḣPḣ

Essayez-le en ligne!

Almos thte même que l'autre question, sauf avec des paramètres.

2 Noodle9 Nov 02 2020 at 18:44

C (gcc) -lm, 67 101 96 octets

Ajout de 34 octets pour corriger un bogue gentiment signalé par xnor .
Sauvé 5 octets grâce à plafonnier !!!

f(n){write(1,"321654",n-3&&n-6?0:n);n=n<4?123/exp10(3-n):n>7?381654729/exp10(9-n):n-6?0:123654;}

Essayez-le en ligne!

Solution basée sur la recherche totale. S'il y a deux solutions: stdoutrenvoie l' une vers et renvoie l'autre. S'il n'y a qu'une seule réponse, elle est simplement renvoyée. Retours \$0\$ s'il n'y a pas de réponse.

Tour de bonus pour les points brownie

C (gcc) , 232 212 octets

Économisé un énorme 20 octets grâce à plafonnier !!!

p;m;j;char b[9],c[9];d;i;f(n){for(d=0,i=n;i;)d+=9*d+i--;for(sprintf(c,"%d",d);d/++i;)if(sprintf(b,"%d",i),qsort(b,n,1,L"\xf06be0f\xd02917beǃ"),!strcmp(b,c)){for(p=0,m=n,j=i;j;j/=10)p|=j%m--;p||printf("%d ",i);}}

Essayez-le en ligne!

Calcule les nombres corrects par le biais du calcul et les renvoie vers stdout. Ne produit rien s'il n'y a pas de réponse. Expiration du délai sur TIO pendant \$n=9\$mais les fait tous 3m36.499ssur mon ordinateur portable.

2 JonathanAllan Nov 02 2020 at 18:44

Gelée ,  11  10 octets

-1 grâce à caird coinheringaahing !

C'est une méthode naïve, il pourrait y en avoir une plus laconique.

Œ!JḍḌƤẠƲƇḌ

Un lien monadique acceptant \$n\$qui donne 0si aucun n'est trouvé ou une liste de nombres valides.

Essayez-le en ligne! Ou voir la suite de tests .

Comment?

Œ!JḍḌƤẠƲƇḌ - Link: n
Œ!         - all permutations of [1..n]
        Ƈ  - filter keep those (p for p in Œ!) for which:
       Ʋ   -   last four links as a monad f(p):
  J        -     range of length = [1..n]
     Ƥ     -     apply to prefixes (of p):
    Ḍ      -       un-decimal
   ḍ       -     divides? (vectorises)
      Ạ    -     all truthy?
         Ḍ - un-decimal
1 KjetilS. Nov 02 2020 at 20:41

Perl 5 , 64 octets

sub{grep"@_"==y///c,1,12,123,321,123654,321654,$x=38165472,$x.9}

Essayez-le en ligne!

1 Arnauld Nov 02 2020 at 22:55

JavaScript (V8) , 97 octets

Une fonction récursive qui calcule et imprime les entiers correspondants.

f=(n,s='987654321'.slice(-n),d,p)=>p%d?0:s?[...s].map(v=>f(n,s.replace(v,''),-~d,[p]+v)):print(p)

Essayez-le en ligne!


JavaScript (ES6), 59 octets

Le codage en dur est évidemment plus court.

n=>[,1,12,[321,123],,,[321654,123654],,q=38165472,q+[9]][n]

Essayez-le en ligne!

att Nov 03 2020 at 02:48

Wolfram Language (Mathematica) , 71 octets

f[s_:0,l_:0]=0!=##2&&l∣s&&If[l<#,##~f[10s+i,l+1]~i~Do~{i,#},Print@s]&

Essayez-le en ligne!

Appelez comme f[][n]. Imprime les résultats.

EngineerToast Nov 03 2020 at 13:32

Excel, 64 octets

=CHOOSE(A1,1,12,"123,321",,,"123654,321654",,38165472,381654729)

L'entrée est entrée A1. La réponse codée en dur est plus courte que le calcul ne le serait.