¿Puedes alcanzar este número duplicando y reorganizando?

34

Inspirado por esta cuestión en Math.SE .

Comenzando con 1usted, puede realizar repetidamente una de las siguientes dos operaciones:

  • Duplica el número.

    o

  • Reorganice sus dígitos de la forma que desee, excepto que no debe haber ceros a la izquierda.

Tomando un ejemplo de la publicación vinculada Math.SE, podemos llegar a 1000través de los siguientes pasos:

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

¿Qué números puede alcanzar con este proceso y cuál es la solución más corta?

El reto

Dado un número entero positivo N, determine la secuencia más corta posible de números enteros para alcanzar Ncon el proceso anterior, si es posible. Si hay varias soluciones óptimas, envíe cualquiera de ellas. Si no existe tal secuencia, debe generar una lista vacía.

La secuencia puede estar en cualquier formato de cadena o lista conveniente y sin ambigüedades.

Puede escribir un programa o función, tomando entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), valor de retorno de función o parámetro de función (out).

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

Aquí hay una lista de todos los números alcanzables hasta 256. La primera columna es el número (su entrada), la segunda columna es el número óptimo de pasos (que puede usar para verificar la validez de su solución) y la tercera La columna es una secuencia óptima para llegar allí:

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}

Si desea aún más datos de prueba, aquí está la misma tabla hasta 1,000 inclusive .

Cualquier número que no aparezca en estas tablas debería generar una lista vacía (siempre que el número esté en el rango de la tabla).

code-golf sequence number-theory path-finding permutations Martin Ender
fuente
¿Hay algún límite en el tiempo de ejecución?
Fatalize
2
@ Fatalize no, enloquece.
Martin Ender
Sin embargo, ¿supongo que un tiempo de ejecución potencialmente infinito no es aceptable? Tiene que terminar teóricamente?
Fatalize
@ Fatalize Ah sí, como siempre .
Martin Ender
¿Qué pasa cuando hay más de un resultado: [1, 2, 4, 8, 16, 32, 64, 46, 92, 29] [1, 2, 4, 8, 16, 32, 23, 46, 92, 29]
dbramwell

Respuestas:

18

Pyth, 43 bytes

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

Demostración.

Esto comienza generando todas las posibles secuencias dobles o de reordenamiento. Sin embargo, como realmente quería verlo terminar, agregué un corto circuito.

Se ejecuta hasta que encuentra una solución, o para un número de iteraciones igual a la entrada, en cuyo punto se da por vencido y regresa [].

Esto garantiza que haya suficientes iteraciones. Primero, sabemos que esta cantidad de iteraciones es suficiente para todos n <= 1000, gracias a los resultados del ejemplo. Para números más grandes, el siguiente argumento es válido:

Primero, cada paso del proceso debe mantener o aumentar el número de dígitos.

Segundo, tres números que son todos reordenamientos uno del otro nunca pueden aparecer en una secuencia más corta, porque hubiera sido más rápido hacer un solo reordenamiento desde el primero hasta el último.

Tercero, todos los múltiplos de 3 son inalcanzables, ya que ni la duplicación ni la reorganización pueden producir un múltiplo de 3 a partir de un no múltiplo de 3.

Por lo tanto, la secuencia más larga posible que termina en un número dado es igual a la suma de dos veces el número de conjuntos de dígitos con menos o igual a tantos dígitos como la entrada, y donde los dígitos no suman un múltiplo de 3.

El número de tales conjuntos de dígitos para cada número de dígitos:

4 - 474
5 - 1332
6 - 3330

Además, sabemos por los ejemplos que la secuencia más corta que termina con un número de 3 dígitos tiene una longitud mayor que 26. Por lo tanto, un límite superior de las longitudes de secuencia es:

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

En cada caso, el límite superior es más bajo que cualquier número con el número de dígitos

El número de conjuntos de dígitos no puede crecer en más de un factor de 10 cuando el número de dígitos se incrementa en uno, porque los nuevos números se pueden separar en grupos por el último dígito, cada uno de los cuales no puede tener más conjuntos de los que había con uno menos dígito.

Por lo tanto, el límite superior será menor que cualquier número con tantos dígitos para todos los números posibles de dígitos mayores o iguales a 4, lo que completa la prueba de que un número de iteraciones igual a la entrada siempre es suficiente.

isaacg
fuente
¿Estás seguro de que una cantidad de iteraciones iguales a la entrada es suficiente? En teoría, el límite superior no estaría alrededor de la próxima potencia mayor de 10 (ya que la secuencia puede disminuir arbitrariamente a menudo).
Martin Ender
@ MartinBüttner Buen punto. Creo que debería haber una prueba de que la entrada siempre es suficiente, pero la editaré por ahora.
isaacg
@ MartinBüttner Prueba de que las iteraciones iguales a la entrada siempre se agregan lo suficiente.
isaacg
Ah, muy bien :) (Curiosamente, incluso hasta 100,000 no necesita más de 26 pasos.)
Martin Ender
¿Creo que sería más rápido enumerar todos los pasos que no sean más largos que la 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).

Ejemplo: a(92,Z).salidasZ = [1, 2, 4, 8, 16, 32, 64, 46, 92]

Todavía no he comprobado que esto funciona para N> 99 debido al tiempo que lleva, pero no veo ninguna razón por la que no funcionaría.

Fatalizar
fuente
2

Julia, 306 245 218 bytes

Todavía estoy trabajando en esto. Proporcionará una versión sin golf una vez que haya terminado.

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
fuente
1

Haskell, 246 bytes

No estoy completamente seguro de si esto funciona, si la secuencia que primero diverge más abajo (como para ser ordenada más abajo) siempre es más corta, como por ejemplo

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

es más corto que

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

que probé para ser verdad hasta 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
fuente
1

C # 655 bytes

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

Llamar con (LinqPad):

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

No he probado números superiores a 99. Si tienes tiempo -> buena suerte ;-)

editar: versión sin golf:

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
fuente
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

Pruébalo en línea

He estado sentado en esto durante mucho tiempo, no es muy corto ni rápido, y no estoy seguro de tener la energía / motivación para mejorarlo, así que solo lo estoy publicando.

aditsu
fuente