Pouvez-vous atteindre ce nombre en doublant et en réarrangeant?

34

Inspiré par cette question sur Math.SE .

En commençant par, 1vous pouvez effectuer plusieurs fois l'une des deux opérations suivantes:

  • Double le nombre.

    ou

  • Réorganisez ses chiffres comme vous le souhaitez, sauf qu'il ne doit pas y avoir de zéros au début.

En prenant un exemple tiré de l'article Math.SE lié, nous pouvons atteindre 1000via les étapes suivantes:

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

Quels numéros pouvez-vous atteindre avec ce processus et quelle est la solution la plus courte?

Le défi

Avec un nombre entier positif N, déterminez N, si possible , la séquence d’entiers la plus courte possible. S'il existe plusieurs solutions optimales, indiquez l'une d'entre elles. Si aucune séquence de ce type n'existe, vous devez générer une liste vide.

La séquence peut être dans une chaîne ou un format de liste pratique et non ambigu.

Vous pouvez écrire un programme ou une fonction en prenant l’entrée via STDIN (ou l’alternative la plus proche), un argument de ligne de commande ou une argumentation de fonction et en générant le résultat via STDOUT (ou l’alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).

C'est le code de golf, donc la réponse la plus courte (en octets) gagne.

Cas de test

Voici une liste de tous les nombres joignables jusqu’à 256. La première colonne est le nombre (votre entrée), la deuxième colonne indique le nombre optimal d’étapes (que vous pouvez utiliser pour vérifier la validité de votre solution) et la troisième. colonne est une séquence optimale pour y arriver:

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 vous voulez encore plus de données de test, voici la même table jusqu’à 1 000 inclus .

Tout nombre n'apparaissant pas sur ces tables devrait donner une liste vide (à condition que le nombre soit dans la plage du tableau).

code-golf sequence number-theory path-finding permutations Martin Ender
la source
Y at-il des limites sur le temps d'exécution?
Fataliser
2
@ Fatalize non, devenez fou.
Martin Ender
Je suppose que le temps d'exécution potentiellement infini n'est pas acceptable cependant? Il doit théoriquement se terminer?
Fataliser
@ Fatalize Ah oui, comme d'habitude .
Martin Ender
Qu'en est-il lorsqu'il y a plus d'un résultat: [1, 2, 4, 8, 16, 32, 64, 46, 92, 29] [1, 2, 4, 8, 16, 32, 23, 46, 92, 29]
dbramwell

Réponses:

18

Pyth, 43 octets

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

Manifestation.

Cela commence par générer toutes les séquences doubles ou réorganisées possibles. Cependant, comme je voulais le voir finir, j’ai ajouté un court-circuit.

Il s'exécute jusqu'à ce qu'il trouve une solution, ou pour un nombre d'itérations égal à l'entrée, puis abandonne et revient [].

Ceci est garanti pour être assez d'itérations. Premièrement, nous savons que ces nombreuses itérations sont suffisantes pour tout n <= 1000, grâce aux exemples de résultats. Pour les plus grands nombres, l'argument suivant est le suivant:

Premièrement, chaque étape du processus doit soit maintenir, soit augmenter le nombre de chiffres.

Deuxièmement, trois numéros qui sont tous des réarrangements l'un de l'autre ne peuvent jamais apparaître dans l'ordre le plus court, car il aurait été plus rapide de ne faire qu'un seul réarrangement du premier au dernier.

Troisièmement, tous les multiples de 3 sont inaccessibles, car ni le doublage ni le réarrangement ne peuvent produire un multiple de 3 à partir d'un non-multiple de 3.

Ainsi, la séquence la plus longue possible se terminant par un nombre donné est égale à la somme de deux fois le nombre d'ensembles de chiffres avec moins ou égal à autant de chiffres que l'entrée, et où les chiffres ne totalisent pas un multiple de 3.

Le nombre de ces ensembles de chiffres pour chaque nombre de chiffres:

4 - 474
5 - 1332
6 - 3330

De plus, nous savons d'après les exemples qu'aucune séquence la plus courte se terminant par un nombre à 3 chiffres n'a une longueur supérieure à 26. Ainsi, une limite supérieure des longueurs de séquence est la suivante:

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

Dans chaque cas, la limite supérieure est inférieure à tout nombre comportant le nombre de chiffres

Le nombre de jeux de chiffres ne peut pas croître de plus d'un facteur 10 lorsque le nombre de chiffres est augmenté d'un, car les nouveaux numéros peuvent être séparés en groupes par le dernier chiffre, chacun ne pouvant pas avoir plus de jeux qu'il n'y en a eu avec un moins. chiffre.

Ainsi, la limite supérieure sera inférieure à tout nombre comportant autant de chiffres pour tous les nombres possibles de chiffres supérieurs ou égaux à 4, ce qui complète la preuve qu'un nombre d'itérations égal à l'entrée est toujours suffisant.

isaacg
la source
Êtes-vous sûr qu'un nombre d'itérations égal à l'entrée est suffisant? En théorie, la limite supérieure ne serait pas proche de la prochaine puissance 10 (car la séquence peut décroître de manière arbitraire).
Martin Ender
@ MartinBüttner Bon point. Je pense qu'il devrait y avoir une preuve que l'entrée est toujours suffisante, mais je vais la modifier pour le moment.
isaacg
@ MartinBüttner La preuve que les itérations égales à l'entrée est toujours suffisante.
isaacg
Ah, très gentil. :) (Fait intéressant, même jusqu'à 100 000, vous n'avez pas besoin de plus de 26 étapes.)
Martin Ender
Je crois qu'il serait plus rapide d'énumérer toutes les étapes pas plus longtemps que l'entrée?
John Dvorak
7

SWI-Prolog, 252 octets

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).

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

Je n'ai pas encore vérifié que cela fonctionne pour N> 99 à cause du temps que cela prend, mais je ne vois aucune raison pour que cela ne fonctionne pas.

Fataliser
la source
2

Julia, 306 245 218 octets

Je travaille toujours sur le golf. Fournira une version non-golfée une fois que j'ai terminé.

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
la source
1

Haskell, 246 octets

Je ne suis pas tout à fait sûr que cela fonctionne, mais si la séquence qui diverge en premier (comme pour être trié en bas) est toujours plus courte, comme par exemple

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

est plus court que

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

que j'ai testé pour être vrai jusqu'à 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
la source
1

C # 655 octets

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

Appeler avec (LinqPad):

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

N'a pas testé les nombres supérieurs à 99. Si vous avez le temps -> bonne chance ;-)

edit: version non-golfée:

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
la source
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

Essayez-le en ligne

Cela fait longtemps que je suis assis là-dessus. Ce n’est ni très court ni rapide, et je ne suis pas sûr d’avoir l’énergie / la motivation pour l’améliorer, alors je le publie simplement.

Aditsu
la source