Escreva um programa para encontrar um número composto por 9 dígitos, no qual cada um dos dígitos de 1 a 9 aparece apenas uma vez. Esse número também deve atender a esses requisitos de divisibilidade:
- O número deve ser divisível por 9.
- Se o dígito mais à direita for removido, o número restante deverá ser divisível por 8.
- Se o dígito mais à direita do novo número for removido, o número restante deverá ser divisível por 7.
- E assim por diante, até que haja apenas um dígito (que será necessariamente divisível por 1).
Crédito Dávid Németh
Respostas:
CJam - 26
É aleatório, mas funciona muito rápido com o interpretador java . Pode levar alguns minutos com o intérprete online .
Explicação:
1
empurra 1 (a ser explicado mais adiante){…}g
é um loop do-while;
remove um valor da pilha (inicialmente o 1 com o qual começamos)9,
faz com que o array [0 ... 8]:)
incremente os elementos do array, resultando em [1 ... 9]_
duplica o arraymr
embaralha o arrays
converte em string0@
0 e depois coloca a outra cópia do array no topo{…}/
é um loop for-each (sobre os números 1 ... 9)_
duplica o número atual (vamos chamá-lo de "k" )3$
copia a sequência numérica da pilha<i
obtém a substring com os primeiros k caracteres, depois converte em\%
swaps inteiros com a outra cópia de k e obtém o restante (% k)+
adiciona o restante ao valor anterior na pilha (inicialmente 0 a partir de cima )Neste ponto, temos a sequência numérica na pilha, seguida de um 0 se o número corresponder a todos os requisitos (ou seja, todos os restantes foram 0) ou um valor diferente de 0.
A parte superior da pilha se torna a condição de loop do-while. Ele é acionado e o loop continua se a condição for verdadeira.
Se encontrarmos a solução, a condição é 0 (false), o loop termina e o restante da pilha (a sequência numérica) é impressa.
Se não for a solução, a condição é o valor diferente de 0 (true) e o loop continua com a sequência na pilha. A string é exibida no início da próxima iteração (então o loop espera um valor na pilha, e esse é o motivo do 1 inicial).
Obrigado Dennis por tornar o código mais curto e complicado: p
fonte
0{;9,:)_mrsT@{_3$<i\%+}/}g
Javascript (E6) 105
125 134Construção recursiva do número, cada etapa verifica a divisibilidade.
Tempo de execução próximo a 0 s
Sem E / S neste momento, pois o OP solicitou que um programa localizasse o número, e o número é encontrado e registrado automaticamente no console
Golf mais Cortesia de MT0
Golfe
Feio
Bônus
Com três pequenas alterações, você pode usar a mesma função para encontrar números mais longos usando a base> 10. Por exemplo, na base 14 ...
Ungolfed
fonte
(Q=(n,d,b)=>([(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],d>9&&(Q.z=n),Q.z))('',1,'123456789')
(Q=(n,d,b)=>Math.max(...[(m=n+(s=[...b]).splice(i,1))%d||Q(m,d+1,s)for(i in b)],n))('',1,'123456789')
Perl, 56
Uso:
perl -E '...'
Resultado:
381654729
Este programa é realmente lento . Como em mais de 3,5 horas.
Como um exercício mais divertido, decidi desenvolver um algoritmo extremamente rápido:
O procedimento acima é executado em 0,00095 segundos e confirma que há apenas uma solução para esse problema.
fonte
Python3,
214,199,184,176,174,171,165,150146resultado:
Este é o meu primeiro roteiro de golfe. Espero que você goste :)
fonte
Pitão , 33 caracteres
Para testá-lo, coloque o código acima como entrada padrão no link no título.
Após compilar no Python 3.4:
Explicação:
=Y]k
:Y=['']
FkY
: para k em F:~Y
: Adicionar a Yf
: Filtrar por>ql{TlT
: Todos os elementos exclusivos e%vTlT
: eval (elemento)% len (elemento) = 0m+k
`d
Na lista de k + repr (d)r1T
: para d de 1 a 9.)
: Fim do looppk
: imprimir kfonte
Ruby, 66
78caracteresO tempo de execução é de ~ 8 segundos (saída impressa após 3 s).
Isso não para depois de encontrar o primeiro número; portanto, tecnicamente, imprime todos os números que atendem aos critérios - mas, como existe apenas um número, não faz diferença.
Rubi 1.8, 63
Essencialmente a mesma solução acima. No Ruby 1.8, matrizes são convertidas em strings chamando-as implicitamente
Array#join
, para que possamos salvar a chamada para isso. Curiosamente, o código também roda muito mais rápido no Ruby 1.8 que 2.0 (tempo total de execução de 4,5 segundos, saída impressa após 1,6 s).fonte
GolfScript (35 caracteres)
Demonstração online
Isso cria prefixos que satisfazem a condição.
fonte
Haskell
129121Aqui está minha tentativa amadora de Haskell (sugestões / melhorias seriam muito apreciadas). Pode não ser o mais curto, mas é executado apenas
.19.65 segundos após as alterações de Flonk no meu sistema.fonte
<!-- language: lang-haskell -->
duas linhas antes do seu código para destacar a sintaxe!foldl1
Porém, separando a função em, você pode usá-la em vez desum
ouany
.import Data.List;f=foldl1$(+).(*10);main=print$[f x|x<-permutations[1..9],f[mod(read.take y.show$f x)y|y<-[9,8..1]]<1]!!0
f
função nomod
predicado para evitar escrever foldl1, embora os ciclos extras prejudiquem gravemente o desempenho.!!0
por uma chamada paraf
, que funciona porque há apenas um item na lista. A lista[9,8..1]
também pode ser substituída porx
, porque o pedido não importa. Fale sobre a reutilização de código!Javascript 75 (terminando)
Solução Bruteforce (super lenta)
Se você deseja ver o resultado nesta vida útil, atualize o valor inicial para algo como
a=c=38e7
Javascript 70 (sem terminação)
E apenas por diversão, uma força bruta aleatória que roda muito mais rápido: (somente ES6)
fonte
Pitão,
142,139,125124Essencialmente, o mesmo que a solução da @ Ventero, se eu entendi seu código corretamente, mas em Python (grande parte do crédito é para @Greg Hewgill).
fonte
r(9,1,-1)
porr(9)
, pois a ordem da iteração realmente não importa.r(1,9)
porque%0
é um erro.r(1, 9)
em Python.permutations("123456789")
e''.join(s[:i])
é provavelmente menor do que o que você tem (e, em seguida, você pode eliminarr=range
)Scala (128 caracteres)
Minha facada nisso ...
fonte
(2 to 8)
eforall
.Perl, 72
Uso:
perl -M5.010 find-9-digits.pl
Resultado:
381654729
Este programa está lento . Pode levar mais de 10 segundos, porque embaralha os dígitos "123456789", mas o embaralhamento tem uma falha.
Ungolfed:
Joguei o código que embaralha a matriz de dígitos 1..9:
use List'Util shuffle;shuffle 1..9
(34 caracteres)sort{(-1,1)[rand 2]}1..9
(24 caracteres)sort{.5<=>rand}1..9
(19 caracteres)sort(2-rand 4}1..9
(18 caracteres)sort{4-rand 8}1..9
(18 caracteres)O Perl espera que o bloco de classificação compare $ a e $ b de maneira consistente. Meus blocos de ordenação nunca mais olhar para $ a e $ b . Eles retornam uma ordem aleatória para que o tipo se torne um embaralhamento.
Se eu usasse
sort{.5<=>rand}1..9
, meu programa seria executado mais rapidamente. Esse compara 0,5 com uma flutuação aleatória de 0,0 a 1,0, excluindo 1,0, para uma chance de 1/2 que $ a <$ b , e uma chance de quase 1/2 que $ a> $ b . ( Cuidado: este é um "embaralhamento da Microsoft" , que não é um embaralhamento justo. Isso tem um viés porque.5<=>rand
não fornece um pedido consistente.)Suponha que eu jogue fora um personagem e use muito pior
sort(2-rand 4}1..9
. O Perl espera que o bloco de classificação retorne um número inteiro, mas2-rand 4
é um número flutuante. É uma flutuação aleatória de -2,0 a 2,0, excluindo -2,0. O Perl trunca esse flutuador em direção a zero, com estes resultados:Quando $ a == $ b , Perl não muda bem. Portanto, meu programa faria mais shuffles, até obter shuffles suficientes onde
2-rand 4
não retornava 0 com muita frequência. Meu programa seria tão lento que pode levar mais de um minuto.Eu uso
sort{4-rand 8}1..9
, então há apenas uma chance de 1/4 que $ a == $ b , e meu programa usa menos shuffles.fonte
CJam, 35 bytes
Após aproximadamente 27 minutos, isso produz a seguinte saída:
Como funciona
fonte
Python 2 (78)
Não há necessidade de gerar permutações, apenas tente cada número e verifique se seus dígitos mais 0 são distintos. Demora um pouco para correr.
fonte
SWI-Prolog 84
É um pouco enganador, porque a lista de dígitos precisa ser fornecida na consulta:
No entanto, é o que torna esse código interessante: você pode resolver o problema para qualquer lista de dígitos. Por exemplo:
fonte
Python 2-114
Nem mesmo a menor solução Python, mas estou compartilhando assim mesmo:
fonte
Bash + coreutils, 159 bytes
Isso é meio longo, mas acho que o algoritmo é talvez um dos mais rápidos, considerando que este é um script de shell (geralmente lento) que roda em menos de 0,1 segundo.
O algoritmo é mais ou menos assim:
grep
)$d
(o número do dígito) usandobc
, com uma expressão gerada porprintf
Observe que tomamos alguns atalhos, mas acho que estes são matematicamente sólidos:
fonte
C ++, 187
Eu só tinha que tentar isso em C ++. Obviamente, não será a solução mais curta, mas aqui está:
retorna o número em vez de imprimi-lo para salvar alguns caracteres (maldita incluir). Nos sistemas POSIX, é claro que isso será convertido em um sinal de 8 bits sem sinal e, portanto, não está correto - mas o programa calculará um número correto.
Ungolfed (requer C ++ 11):
fonte
T-SQL 2005+ - 203
T-sql não é um idioma de golfe muito competitivo ...
Deve ser executado no banco de dados mestre. Você pode substituir o primeiro CTE por isso para torná-lo independente de banco de dados, mas depois usa mais alguns caracteres (e requer 2008)
Formação legível:
Basicamente, continuamos adicionando dígitos na parte de trás do
r
número que ainda não vimos na string e certificando-nos de que a nova string ainda esteja no módulo 0 do nível atual. Inicializamos R para\
, este é realmente o único truque neste código. O que é uma maneira louca de defini-lo como 0 nomoney
tipo de dados. Acho que é uma maneira de você digitar em\
vez de moeda.$
também faz a mesma coisa no T-SQL, mas$l
tenta interpretar uma pseudo coluna que não existe e gera um erro. Isso evita a preocupação de usarint
o que causaria um estouro normalmente na 10ª concatenação, forçando-nos a realmente verificar o nível. Edit: Curiosidade O T-sql, mesmo em 2014, não tem uma maneira integrada de transformar uma string em uma tabela de valores (por exemplo, nenhuma função dividida), então também podemos reutilizar nossaA
tabela duas vezes para iterar os caracteres no R. restritoAs regras de precedência T-Sql são irritantes, portanto, temos que usar concatenação numérica (* 10 + n), em vez de concatenação de strings.
fonte
with A as(select 1n union all select n+1 from A where n<9),
PHP, 89 bytes
versão aleatória, 89 bytes:
embaralha uma sequência contendo os dígitos e testa a divisibilidade em um loop.
Corra com
-nr
.loop de força bruta, 90 bytes, muito lento:
loops de 100000001, testa a divisibilidade no loop interno e sai quando encontra uma solução.
função recursiva, 94 bytes, muito rápido:
acrescenta um dígito que ainda não está no número, se for dada a divisibilidade por comprimento, recursar (ou imprimir).
Isso explora que há apenas uma solução. sem isso,
print$e>8?$x:f($x,$e+1)
tinha que serprint$e>8?"$x\n":f($x,$e+1)
(+3 bytes, imprimir todas as soluções) ou($e>8?die("$x"):f($x,$e+1))
(+4 bytes, sair na primeira solução) ou as soluções seriam impressas sem um delimitador.Ligue com
f();
-
TiO
A versão de força bruta não possui TiO por razões óbvias, mas você pode tentar as outras duas .
O tempo de execução da chamada de função é medido em linha (algo entre 2 e 4 milissegundos);
o tempo de execução total é medido pelo site (geralmente entre 50 e 500 ms).
fonte