Você pode alcançar esse número dobrando e reorganizando?

34

Inspirado por esta pergunta em Math.SE .

Começando com 1você pode executar repetidamente uma das duas operações a seguir:

  • Dobre o número.

    ou

  • Reorganize seus dígitos da maneira que desejar, exceto que não deve haver zeros à esquerda.

Tomando um exemplo da postagem vinculada do Math.SE, podemos acessar 1000as seguintes etapas:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 125, 250, 500, 1000

Quais números você pode alcançar com esse processo e qual é a solução mais curta?

O desafio

Dado um número inteiro positivo N, determine a menor seqüência possível de números inteiros para alcançar Ncom o processo acima, se possível. Se houver várias soluções ideais, produza qualquer uma delas. Se essa sequência não existir, você deve exibir uma lista vazia.

A sequência pode estar em qualquer formato conveniente, inequívoco de sequência ou lista.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Casos de teste

Aqui está uma lista de todos os números alcançáveis, incluindo 256. A primeira coluna é o número (sua entrada), a segunda coluna é o número ideal de etapas (que você pode usar para verificar a validade da sua solução) e a terceira coluna é uma sequência ideal para chegar lá:

1       1       {1}
2       2       {1,2}
4       3       {1,2,4}
8       4       {1,2,4,8}
16      5       {1,2,4,8,16}
23      7       {1,2,4,8,16,32,23}
29      10      {1,2,4,8,16,32,23,46,92,29}
32      6       {1,2,4,8,16,32}
46      8       {1,2,4,8,16,32,23,46}
58      11      {1,2,4,8,16,32,23,46,92,29,58}
61      6       {1,2,4,8,16,61}
64      7       {1,2,4,8,16,32,64}
85      12      {1,2,4,8,16,32,23,46,92,29,58,85}
92      9       {1,2,4,8,16,32,23,46,92}
104     15      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104}
106     14      {1,2,4,8,16,32,64,128,256,265,530,305,610,106}
107     14      {1,2,4,8,16,32,23,46,92,29,58,85,170,107}
109     18      {1,2,4,8,16,32,23,46,92,184,368,386,772,277,554,455,910,109}
116     12      {1,2,4,8,16,32,23,46,92,29,58,116}
122     7       {1,2,4,8,16,61,122}
124     16      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,124}
125     11      {1,2,4,8,16,32,64,128,256,512,125}
128     8       {1,2,4,8,16,32,64,128}
136     18      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,136}
140     15      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,140}
142     16      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,142}
145     17      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,145}
146     18      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,146}
148     11      {1,2,4,8,16,32,23,46,92,184,148}
149     16      {1,2,4,8,16,32,64,128,182,364,728,287,574,457,914,149}
152     11      {1,2,4,8,16,32,64,128,256,512,152}
154     17      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154}
158     16      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158}
160     14      {1,2,4,8,16,32,64,128,256,265,530,305,610,160}
161     13      {1,2,4,8,16,32,23,46,92,29,58,116,161}
163     18      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,163}
164     18      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,164}
166     20      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166}
167     17      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,167}
169     23      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229,458,916,169}
170     13      {1,2,4,8,16,32,23,46,92,29,58,85,170}
176     17      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176}
182     9       {1,2,4,8,16,32,64,128,182}
184     10      {1,2,4,8,16,32,23,46,92,184}
185     16      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,185}
188     23      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,185,370,740,470,940,409,818,188}
190     18      {1,2,4,8,16,32,23,46,92,184,368,386,772,277,554,455,910,190}
194     16      {1,2,4,8,16,32,64,128,182,364,728,287,574,457,914,194}
196     23      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229,458,916,196}
203     16      {1,2,4,8,16,32,64,128,256,265,530,305,610,160,320,203}
205     13      {1,2,4,8,16,32,64,128,256,512,125,250,205}
208     16      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208}
209     19      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,145,290,209}
212     8       {1,2,4,8,16,61,122,212}
214     15      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214}
215     11      {1,2,4,8,16,32,64,128,256,512,215}
218     9       {1,2,4,8,16,32,64,128,218}
221     8       {1,2,4,8,16,61,122,221}
223     14      {1,2,4,8,16,32,23,46,92,29,58,116,232,223}
227     20      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,361,722,227}
229     20      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229}
230     16      {1,2,4,8,16,32,64,128,256,265,530,305,610,160,320,230}
232     13      {1,2,4,8,16,32,23,46,92,29,58,116,232}
233     22      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166,332,233}
235     19      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176,352,235}
236     19      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,632,236}
238     19      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,832,238}
239     25      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166,332,233,466,932,239}
241     16      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,241}
244     8       {1,2,4,8,16,61,122,244}
247     21      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,632,362,724,247}
248     17      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,124,248}
250     12      {1,2,4,8,16,32,64,128,256,512,125,250}
251     11      {1,2,4,8,16,32,64,128,256,512,251}
253     19      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176,352,253}
256     9       {1,2,4,8,16,32,64,128,256}

Se você deseja ainda mais dados de teste, aqui está a mesma tabela, incluindo 1.000 .

Qualquer número que não apareça nessas tabelas deve gerar uma lista vazia (desde que o número esteja no intervalo da tabela).

code-golf sequence number-theory path-finding permutations Martin Ender
fonte
Existem limites no tempo de execução?
Fatalize 19/08/2015
2
@Fatalize não, enlouqueça.
Martin Ender
Suponho que tempo de execução potencialmente infinito não seja aceitável? Tem que terminar teoricamente?
Fatalize 19/08/2015
@ Fatalize Ah sim, como de costume .
Martin Ender
Que tal quando houver mais de um resultado: [1, 2, 4, 8, 16, 32, 64, 46, 92, 29] [1, 2, 4, 8, 16, 32, 23, 46, 92, 29]
dbramwell

Respostas:

18

Pitão, 43 bytes

?}QKhu?Jf}QTGJsm+Ld+yedsMfnhT\0.p`edGQ]]1KY

Demonstração.

Isso começa gerando todas as sequências duplas ou reorganizadas possíveis. No entanto, como eu realmente queria vê-lo terminar, adicionei um curto-circuito.

Ele é executado até encontrar uma solução ou para um número de iterações iguais à entrada; nesse ponto, ele desiste e retorna [].

É garantido que sejam iterações suficientes. Primeiro, sabemos que essas muitas iterações são suficientes para todos n <= 1000, graças aos resultados do exemplo. Para números maiores, o seguinte argumento é válido:

Primeiro, cada etapa do processo deve manter ou aumentar o número de dígitos.

Segundo, três números que são todos rearranjos um do outro nunca podem aparecer em uma sequência mais curta, porque teria sido mais rápido fazer apenas um rearranjo do primeiro ao último.

Terceiro, todos os múltiplos de 3 são inacessíveis, porque nem a duplicação nem o rearranjo podem produzir um múltiplo de 3 a partir de um não múltiplo de 3.

Assim, a sequência mais longa possível que termina em um determinado número é igual à soma do dobro do número de conjuntos de dígitos com menos ou igual a tantos dígitos quanto a entrada e onde os dígitos não somam um múltiplo de 3.

O número desses conjuntos de dígitos para cada número de dígitos:

4 - 474
5 - 1332
6 - 3330

Além disso, sabemos pelos exemplos que nenhuma sequência mais curta que termina com um número de 3 dígitos é maior que 26. Assim, um limite superior dos comprimentos da sequência é:

4: 474 * 2 + 26 = 974
5: 974 * 2 + 1332 = 3638
6: 3330 * 2 + 3638 = 10298

Em cada caso, o limite superior é menor que qualquer número com o número de dígitos

O número de conjuntos de dígitos não pode aumentar mais do que um fator de 10 quando o número de dígitos é aumentado em um, porque os novos números podem ser separados em grupos pelo último dígito, cada um dos quais não pode ter mais conjuntos do que havia com menos um. dígito.

Portanto, o limite superior será menor que qualquer número com tantos dígitos para todos os números possíveis de dígitos maiores ou iguais a 4, o que completa a prova de que sempre é suficiente um número de iterações iguais à entrada.

isaacg
fonte
Você tem certeza de que um número de iterações iguais à entrada é suficiente? Em teoria, o limite superior não seria o próximo maior poder de 10 (já que a sequência pode diminuir arbitrariamente com frequência).
Martin Ender
@ MartinBüttner Bom ponto. Acho que deve haver uma prova de que a entrada é sempre suficiente, mas vou editá-la por enquanto.
Isaacg
@ MartinBüttner Prova de que iterações iguais à entrada são sempre adicionadas o suficiente.
Isaacg
Ah, muito legal. :) (Curiosamente, mesmo até 100.000 você não precisa de mais do que 26 passos.)
Martin Ender
Eu acredito que seria mais rápido enumerar todas as etapas não mais do que a entrada?
John Dvorak
7

SWI-Prolog, 252 bytes

a(N,Z):-findall(X,b(N,[1],X),R),sort(R,[Z|_]);Z=[].
b(N,[A|T],Z):-n(A,C),n(N,M),length(C,L),length(M,O),L=<O,((A=N,reverse([A|T],Z));(A\=N,(B is A*2;permutation(C,D),\+ nth0(0,D,48),n(B,D),\+member(B,[A|T])),b(N,[B,A|T],Z))).
n(A,B):-number_codes(A,B).

Exemplo: a(92,Z).saídasZ = [1, 2, 4, 8, 16, 32, 64, 46, 92]

Ainda não verifiquei se isso funciona para N> 99 por causa do tempo que leva, mas não vejo razão para que não funcione.

Fatalizar
fonte
2

Julia, 306 245 218 bytes

Ainda trabalhando nisso. Fornecerá uma versão não destruída assim que terminar.

s->(M=s=[s];while 1∉s C=0;for i=1:size(s,1) p=2;for j=permutations(dec(s[i])) j[1]>48&&j[end]%2<1&&(l=int(j);l=l÷p;l∉M&&(M=[M,l];S=[l s[i,:]];C==0?C=S:C=[C;S]));p=1end;end;C==0&&return [];s=C;end;sortrows(s)[1,:])
Glen O
fonte
1

Haskell, 246 bytes

Não tenho muita certeza se isso funciona, mas se a sequência que primeiro diverge mais baixo (como classificada abaixo) é sempre mais curta, como por exemplo

[1,2,4,8,16,32,64,128,256,512,125,250,500,1000]

é mais curto que

[1,2,4,8,16,32,64,128,256,512,251,502,250,500,1000]

que eu testei para ser verdade até 1000.

import Data.List
h l|mod(e l)2==0=l:h(div(e l)2:l)|0<1=[l]
s l=map((:l).read)(filter((/='0').e)(permutations$show$e l))
e=head
m=map e
n f=m.groupBy(\a b->e a==e b).sort.concatMap f
w l|e(e l)==1=[nub$e l]|m x/=m l=w x|0<1=[[]] where x=n h(n s l)
Leif Willerts
fonte
1

Bytes em C # 655

List<int> C(int i,List<int> x,int a){x.Add(a);if(a==i)return x;List<int> o=null;string s=a.ToString(),m=i.ToString();var res=G(s,s.Length);foreach (var r in res)if (r.First()!='0'){var l=int.Parse(new String(r.ToArray()));if(!x.Contains(l)&&l.ToString().Length<=m.Length){var n=C(i,x.ToList(),l);if(n!=null&&(o==null||o.Count()>n.Count()))o=n;}}if ((a*2).ToString().Length>m.Length)return o;var p = C(i, x.ToList(), a * 2);if (p!=null&&(o==null||o.Count()>p.Count()))o=p;return o;}IEnumerable<IEnumerable<T>> G<T>(IEnumerable<T> l,int i){return i==1?l.Select(t =>new T[]{t}):G(l,i-1).SelectMany(t=>l.Where(e=>!t.Contains(e)),(a,b)=>a.Concat(new T[]{b}));}

Ligue para (LinqPad):

var i = 64;
C(i,new List<int>(),1).Dump();

Não testou números acima de 99. Se você tiver tempo -> boa sorte ;-)

edit: versão não destruída:

List<int> C(int i, List<int> x, int toAdd, bool removeLast)
{
    x.Add(toAdd);

    if ( toAdd == i )
    {
        return x;
    }
    else
    {
        List<int> shortest = null;
        if ( toAdd > 9 )
        {
            var res = G(toAdd.ToString(), toAdd.ToString().Length);

            foreach ( var r in res )
            {
                if ( r.First () != '0' )
                {
                    var resi = int.Parse(new String(r.ToArray()));

                    if ( !x.Contains(resi) && resi.ToString().Length <= i.ToString().Length )
                    {
                        var resPerm = C(i, x.ToList(), resi, false);
                        if ( resPerm != null )
                        {
                            if ( shortest == null || shortest.Count() > resPerm.Count() )
                            {
                                shortest = resPerm;
                            }
                        }
                    }
                }
            }
        }
        if ( (toAdd * 2).ToString().Length > i.ToString().Length )
        {
            return shortest;
        }
        var resDouble = C(i, x.ToList(), toAdd * 2, false);
        if ( resDouble != null )
        {
            if ( shortest == null || shortest.Count() > resDouble.Count() )
            {
                shortest = resDouble;
            }
            return shortest;
        }

        return shortest;
    }
}
IEnumerable<IEnumerable<T>> G<T>(IEnumerable<T> l,int i)
{
    return i==1?l.Select(t => new T[]{t}):G(l,i-1).SelectMany(t=>l.Where(e=>!t.Contains(e)),(a,b)=>a.Concat(new T[]{b}));
}
Stephan Schinkel
fonte
0

CJam, 83

ri:N_1a:Xa:Y;{X,{XI=__se!{c~},:i^\2*|NA*,&X-_YI=f+Y\+:Y;X\+:X;}fI}*X#_){Y=W%}{;L}?p

Experimente online

Estou sentado nisso há um longo tempo, não é muito curto nem rápido, e não tenho certeza se tenho energia / motivação para melhorá-lo, então estou postando.

aditsu
fonte