Divisibilidade do prefixo

Nov 02 2020

Inspiração

Dado um número inteiro positivo \$1 \le n \le 9\$, saída toda positiva \$n\$números inteiros de dígitos \$i\$ para o qual o seguinte é verdadeiro:

  • Cada dígito de \$1\$para \$n\$aparece exatamente uma vez em \$i\$. Portanto, \$i\$os dígitos de são uma permutação dos dígitos de \$1\$para \$n\$.
  • \$i\$é divisível por \$n\$
  • Removendo o dígito mais à direita de \$i\$produz outro inteiro \$i_{\text{trunc}(1)}\$que é divisível por \$n-1\$
  • Removendo o dígito mais à direita de \$i_{\text{trunc}(1)}\$produz outro inteiro \$i_{\text{trunc}(2)}\$que é divisível por \$n-2\$
  • E assim por diante, até \$i_{\text{trunc}(n-1)}\$, que é divisível por 1.

Por exemplo, para \$n = 3\$, um desses inteiros é \$321\$, as \$321\$é divisível por \$3\$, \$32\$por \$2\$e \$3\$ por 1.

Para \$n = 4, 5, 7\$, não existem tais números inteiros. Neste caso, você pode saída de qualquer coisa que não pode ser confundida com uma possível saída (por exemplo 0, [], nada, etc.). Para \$n = 3, 6\$, você pode gerar os dois números em qualquer formato em que os dois números estejam claramente separados um do outro.

Este é o código-golfe, então o código mais curto em bytes vence.

Se você usar um método de tabela de pesquisa, brownie points \${}^\dagger\$ são concedidos se você também incluir uma versão que calcule a saída correta.

\${}^\dagger\$Os pontos brownie podem ou não estar na forma de um voto positivo

Casos de teste

Esses casos são exaustivos, então você nunca receberá (ou terá que lidar com) uma entrada não incluída aqui.

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

Respostas

5 ovs Nov 02 2020 at 19:28

05AB1E , 8 bytes

LœJʒηāÖP

Experimente online!

Comentado :

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 bytes

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

Experimente online!

Produz uma lista de strings.


71 bytes

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

Experimente online!

Apenas um código rígido chato e direto. Produz um único número ou uma lista de dois números ou 0 para nenhuma saída.

Nenhum dos outros métodos que tentei parecia ser mais curto do que este. Por exemplo, uma ideia é gerar números como prefixos de um único número, gerando semelhantes 123654/10**(6-i).

Um método de objeto fornece o mesmo comprimento. Infelizmente, não podemos usar o muito mais curto .popporque torna a função não reutilizável porque modifica a lista a cada chamada.

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

Experimente online!

O aliasing da constante mais longa também dá o mesmo comprimento:

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

Experimente online!

4 xash Nov 02 2020 at 18:43

J , 42 37 bytes

Calcula os números.

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

Experimente online!

  • 1+i. 1 ... n
  • i.@!…@A. todas as permutações possíveis de 1 ... n
  • 10&#.\ converter cada prefixo de uma permutação em um número
  • 0(…)@|: transpor a matriz e ...
  • #\|] 1 ... n mod os prefixos, por exemplo 1 2 3 | 1 12 123
  • 0=[:+/some o resultado; é 0?
  • {:#~ em seguida, pegue o último prefixo da permutação (a própria permutação)
3 user Nov 02 2020 at 22:36

Scala, 81 80 bytes

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

Experimente no Scastie

Explicação:

| =>                          //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

Carvão , 25 bytes

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

Experimente online! O link é para a versão detalhada do código. Muito lento para n>5no TIO. Explicação:

Nθ

Entrada n.

ΦEXχθIι

Liste todos os inteiros iaté 10ⁿ, de modo que ...

⬤…·¹θ

... para cada número inteiro lde 1a n...

›№ιIλ﹪I…ιλλ

lé um dígito de ie o lprefixo -caracter de ié divisível por l.

Versão de 28 bytes ligeiramente mais rápida:

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

Experimente online! O link é para a versão detalhada do código. Explicação: Gera os dígitos na base em n+1vez da base 10, possibilitando a conclusão n=6no TIO.

Versão de 29 bytes mais rápida usando uma tabela de pesquisa compactada:

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

Experimente online! O link é para a versão detalhada do código.

2 J42161217 Nov 02 2020 at 18:38

Linguagem Wolfram (Mathematica) , 78 bytes

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

Experimente online!

-8 bytes de @att

2 Razetime Nov 03 2020 at 03:47

Husk , 15 bytes

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

Experimente online!

Quase o mesmo que a outra pergunta, exceto com parâmetros.

2 Noodle9 Nov 02 2020 at 18:44

C (gcc) -lm, 67 101 96 bytes

Adicionados 34 bytes para corrigir um bug gentilmente apontado por xnor .
Economizei 5 bytes graças ao tetocat !!!

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;}

Experimente online!

Solução baseada em pesquisa total. Se houver duas soluções: gera um para stdoute retorna o outro. Se houver apenas uma resposta, ela é simplesmente retornada. Devoluções \$0\$ se não houver resposta.

Rodada de bônus para pontos de brownie

C (gcc) , 232 212 bytes

Economizei incríveis 20 bytes graças ao roofcat !!!

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);}}

Experimente online!

Calcula os números corretos por meio de cálculos e os envia para stdout. Não produz nada se não houver resposta. Tempo esgotado no TIO para \$n=9\$mas faz todos eles no 3m36.499smeu laptop.

2 JonathanAllan Nov 02 2020 at 18:44

Jelly ,  11  10 bytes

-1 graças a caird coinheringaahing !

Este é um método ingênuo, poderia haver um mais conciso.

Œ!JḍḌƤẠƲƇḌ

Um Link monádico aceitando \$n\$que resulta 0se nenhum for encontrado ou uma lista de números válidos.

Experimente online! Ou veja o conjunto de testes .

Como?

Œ!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 bytes

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

Experimente online!

1 Arnauld Nov 02 2020 at 22:55

JavaScript (V8) , 97 bytes

Uma função recursiva que calcula e imprime os inteiros correspondentes.

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)

Experimente online!


JavaScript (ES6), 59 bytes

A codificação permanente é obviamente mais curta.

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

Experimente online!

att Nov 03 2020 at 02:48

Wolfram Language (Mathematica) , 71 bytes

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

Experimente online!

Ligue como f[][n]. Imprime os resultados.

EngineerToast Nov 03 2020 at 13:32

Excel, 64 bytes

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

A entrada está em A1. A resposta embutida no código é mais curta do que o cálculo seria.