Können Sie diese Zahl durch Verdoppeln und Umordnen erreichen?

34

Inspiriert von dieser Frage auf Math.SE .

Beginnend mit können 1Sie wiederholt eine der folgenden zwei Operationen ausführen:

  • Verdopple die Zahl.

    oder

  • Ordnen Sie die Ziffern nach Belieben neu an, mit der Ausnahme, dass keine führenden Nullen vorhanden sein dürfen.

Ein Beispiel aus dem verlinkten Math.SE-Beitrag können wir 1000über die folgenden Schritte erreichen:

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

Welche Zahlen können Sie mit diesem Verfahren erreichen und welche ist die kürzeste Lösung?

Die Herausforderung

NBestimmen Sie bei einer positiven ganzen Zahl die kürzestmögliche Folge von ganzen Zahlen, die Nmit dem obigen Verfahren erreicht werden kann, sofern dies möglich ist. Wenn es mehrere optimale Lösungen gibt, geben Sie eine davon aus. Wenn keine solche Sequenz existiert, sollten Sie eine leere Liste ausgeben.

Die Sequenz kann in jedem geeigneten, eindeutigen Zeichenfolge- oder Listenformat vorliegen.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Testfälle

Hier ist eine Liste aller erreichbaren Nummern bis einschließlich 256. Die erste Spalte ist die Nummer (Ihre Eingabe), die zweite Spalte ist die optimale Anzahl von Schritten (mit denen Sie die Gültigkeit Ihrer Lösung überprüfen können) und die dritte Spalte ist eine optimale Reihenfolge, um dorthin zu gelangen:

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}

Wenn Sie noch mehr Testdaten wünschen, finden Sie hier die gleiche Tabelle bis einschließlich 1.000 .

Jede Nummer, die nicht in diesen Tabellen erscheint, sollte eine leere Liste ergeben (vorausgesetzt, die Nummer liegt im Bereich der Tabelle).

code-golf sequence number-theory path-finding permutations Martin Ender
quelle
Gibt es irgendwelche Grenzen für die Ausführungszeit?
Fatalize
2
@Fatalize nein, verrückt werden.
Martin Ender
Ich nehme an, dass eine möglicherweise unendliche Ausführungszeit nicht akzeptabel ist. Muss es theoretisch enden?
Fatalize
@Fatalize Ah ja, wie immer .
Martin Ender
Was ist, wenn es mehr als ein Ergebnis gibt: [1, 2, 4, 8, 16, 32, 64, 46, 92, 29] [1, 2, 4, 8, 16, 32, 23, 46, 92, 29]
Dbramwell

Antworten:

18

Pyth, 43 Bytes

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

Demonstration.

Dies beginnt mit der Generierung aller möglichen Doppel- oder Neuanordnungssequenzen. Da ich es jedoch eigentlich beenden wollte, fügte ich einen Kurzschluss hinzu.

Es wird entweder ausgeführt, bis eine Lösung gefunden wurde, oder für eine Anzahl von Iterationen, die der Eingabe entsprechen. An diesem Punkt gibt es auf und kehrt zurück [].

Dies ist garantiert genug Iterationen. Erstens wissen wir, dass diese vielen Iterationen dank der Beispielergebnisse für alle n <= 1000 ausreichen. Für größere Zahlen gilt das folgende Argument:

Erstens muss jeder Schritt des Prozesses die Anzahl der Stellen beibehalten oder erhöhen.

Zweitens können drei Zahlen, die alle Umordnungen voneinander sind, niemals alle in kürzester Reihenfolge auftreten, da es schneller gewesen wäre, nur eine einzige Umordnung von der ersten zur letzten durchzuführen.

Drittens sind alle Vielfachen von 3 nicht erreichbar, da weder eine Verdopplung noch eine Umlagerung ein Vielfaches von 3 aus einem Nicht-Vielfachen von 3 ergeben kann.

Die längste mögliche Sequenz, die mit einer bestimmten Zahl endet, ist also gleich der Summe der doppelten Anzahl von Ziffernsätzen mit weniger oder gleich so vielen Ziffern wie der Eingabe, und wenn die Ziffern nicht zu einem Vielfachen von 3 summieren.

Die Anzahl solcher Ziffernsätze für jede Anzahl von Ziffern:

4 - 474
5 - 1332
6 - 3330

Außerdem wissen wir aus den Beispielen, dass keine kürzeste Sequenz, die mit einer dreistelligen Zahl endet, länger als 26 ist. Daher ist eine Obergrenze der Sequenzlängen:

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

In jedem Fall ist die Obergrenze niedriger als eine Zahl mit der Anzahl der Ziffern

Die Anzahl der Ziffernsätze kann nicht um mehr als den Faktor 10 anwachsen, wenn die Anzahl der Ziffern um eins erhöht wird, da die neuen Nummern durch die letzte Ziffer in Gruppen unterteilt werden können, von denen jede nicht mehr Sätze haben kann als mit einer geringeren Ziffer.

Somit ist die Obergrenze niedriger als jede Zahl mit so vielen Ziffern für alle möglichen Ziffern, die größer oder gleich 4 sind. Dies vervollständigt den Beweis, dass eine Anzahl von Iterationen, die der Eingabe entsprechen, immer ausreicht.

isaacg
quelle
Sind Sie sicher, dass eine der Eingabe entsprechende Anzahl von Iterationen ausreicht? Theoretisch würde die Obergrenze nicht um die nächstgrößere Potenz von 10 liegen (da die Sequenz beliebig oft abnehmen kann).
Martin Ender
@ MartinBüttner Guter Punkt. Ich denke, es sollte einen Beweis dafür geben, dass die Eingabe immer ausreicht, aber ich werde sie vorerst bearbeiten.
Isaacg
@ MartinBüttner Der Nachweis, dass Iterationen gleich Eingaben sind, ist immer ausreichend.
Isaacg
Ah, sehr nett. :) (Interessanterweise brauchen Sie bis zu 100.000 Stufen nicht mehr als 26 Stufen.)
Martin Ender
Ich glaube es wäre schneller alle schritte nicht länger als die eingabe aufzuzählen?
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).

Beispiel: a(92,Z).AusgängeZ = [1, 2, 4, 8, 16, 32, 64, 46, 92]

Ich habe noch nicht überprüft, ob dies für N> 99 funktioniert, da es sehr lange dauert, aber ich sehe keinen Grund, warum es nicht funktioniert.

Tödlich
quelle
2

Julia, 306 245 218 Bytes

Ich arbeite immer noch daran Golf zu spielen. Stellt eine ungolfed Version zur Verfügung, sobald ich fertig bin.

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

Haskell, 246 Bytes

Ich bin mir nicht ganz sicher, ob dies funktioniert, wenn die Reihenfolge, die zuerst niedriger abweicht (um niedriger sortiert zu werden), immer kürzer ist, wie zum Beispiel

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

ist kürzer als

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

was ich getestet habe, um bis zu 1000 wahr zu sein.

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

Mit (LinqPad) anrufen:

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

Habe noch keine Zahlen über 99 getestet. Wenn du Zeit hast -> viel Glück ;-)

edit: ungolfed version:

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

Probieren Sie es online aus

Ich habe lange darauf gesessen, es ist weder sehr kurz noch sehr schnell und ich bin mir nicht sicher, ob ich die Energie / Motivation habe, es zu verbessern, also poste ich es einfach.

aditsu
quelle