Czy możesz osiągnąć ten numer, podwajając i zmieniając układ?

34

Zainspirowany tym pytaniem na Math.SE .

Zaczynając od 1, możesz wielokrotnie wykonać jedną z następujących dwóch operacji:

  • Podwój liczbę.

    lub

  • Zmień kolejność cyfr w dowolny sposób, z tym wyjątkiem, że nie może być żadnych zer wiodących.

Biorąc przykład z połączonego postu Math.SE, możemy dotrzeć, 1000wykonując następujące kroki:

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

Jakie liczby można osiągnąć dzięki temu procesowi i jakie jest najkrótsze rozwiązanie?

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą N, określ najkrótszą możliwą sekwencję liczb całkowitych do osiągnięcia Nw powyższym procesie, jeśli to możliwe. Jeśli istnieje kilka optymalnych rozwiązań, wypisz dowolne z nich. Jeśli taka sekwencja nie istnieje, powinieneś wypisać pustą listę.

Sekwencja może mieć dowolny dogodny, jednoznaczny ciąg lub format listy.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

Oto lista wszystkich osiągalnych liczb do 256 włącznie. Pierwsza kolumna to liczba (dane wejściowe), druga kolumna to optymalna liczba kroków (których można użyć do sprawdzenia poprawności rozwiązania) i trzecia kolumna jest jedną optymalną sekwencją, aby się tam dostać:

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}

Jeśli chcesz uzyskać jeszcze więcej danych testowych, oto ta sama tabela do 1000 włącznie .

Każda liczba nie pojawiająca się w tych tabelach powinna dać pustą listę (pod warunkiem, że liczba mieści się w zakresie tabeli).

code-golf sequence number-theory path-finding permutations Martin Ender
źródło
Czy są jakieś ograniczenia dotyczące czasu wykonania?
Fatalize
2
@ Fatalizuj nie, zwariuj.
Martin Ender,
Podejrzewam, że potencjalnie nieskończony czas wykonania jest niedopuszczalny? To musi teoretycznie zakończyć się?
Fatalize
@ Fatalizuj Ah tak, jak zwykle .
Martin Ender,
A jeśli wynik jest więcej niż jeden: [1, 2, 4, 8, 16, 32, 64, 46, 92, 29] [1, 2, 4, 8, 16, 32, 23, 46, 92, 29]
dbramwell,

Odpowiedzi:

18

Pyth, 43 bajty

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

Demonstracja.

Zaczyna się to od wygenerowania wszystkich możliwych sekwencji podwójnych lub przestawionych. Ponieważ jednak naprawdę chciałem, aby to się skończyło, dodałem zwarcie.

Działa albo dopóki nie znajdzie rozwiązania, albo przez szereg iteracji równych wejściowi, w którym to momencie poddaje się i wraca [].

Gwarantuje to wystarczającą liczbę iteracji. Po pierwsze wiemy, że dzięki tak wielu przykładowym wynikom wystarczy tyle iteracji dla wszystkich n <= 1000. W przypadku większych liczb obowiązuje następujący argument:

Po pierwsze, każdy etap procesu musi albo utrzymywać, albo zwiększać liczbę cyfr.

Po drugie, trzy liczby, które wszystkie są wzajemnie przestawione, nigdy nie mogą pojawić się w najkrótszej sekwencji, ponieważ szybsze byłoby wykonanie pojedynczej przegrupowania od pierwszej do ostatniej.

Po trzecie, wszystkie wielokrotności 3 są nieosiągalne, ponieważ ani podwojenie, ani przegrupowanie nie może dać wielokrotności 3 z wielokrotności 3.

Zatem najdłuższa możliwa sekwencja kończąca się na danej liczbie jest równa sumie dwukrotności liczby zestawów cyfr z mniejszą lub równą tylu cyfrom na wejściu, przy czym cyfry nie sumują się do wielokrotności 3.

Liczba takich zestawów cyfr dla każdej liczby cyfr:

4 - 474
5 - 1332
6 - 3330

Ponadto wiemy z przykładów, że żadna najkrótsza sekwencja zakończona trzycyfrową liczbą nie ma długości większej niż 26. Zatem górna granica długości sekwencji wynosi:

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

W każdym przypadku górna granica jest niższa niż dowolna liczba z liczbą cyfr

Liczba zestawów cyfr nie może wzrosnąć więcej niż o współczynnik 10, gdy liczba cyfr zostanie zwiększona o jeden, ponieważ nowe liczby można podzielić na grupy według ostatniej cyfry, z których każdy nie może mieć większej liczby zestawów niż z jedną mniejszą cyfra.

Zatem górna granica będzie niższa niż jakakolwiek liczba z taką liczbą cyfr dla wszystkich możliwych liczb cyfr większych lub równych 4, co uzupełnia dowód, że liczba iteracji równa wartości wejściowej jest zawsze wystarczająca.

isaacg
źródło
Czy na pewno wystarczy liczba iteracji równa wartości wejściowej? Teoretycznie górna granica nie byłaby wokół następnej większej potęgi 10 (ponieważ sekwencja może dowolnie zmniejszać się często).
Martin Ender,
@ MartinBüttner Dobra uwaga. Myślę, że powinien istnieć dowód, że dane wejściowe są zawsze wystarczające, ale na razie będę je edytować.
isaacg,
@ MartinBüttner Dowód, że iteracje równe wejściowi są zawsze dodawane w wystarczającym stopniu.
isaacg,
Ach, bardzo miło. :) (Co ciekawe, nawet do 100 000 nie potrzebujesz więcej niż 26 kroków.)
Martin Ender
Uważam, że szybsze byłoby wyliczenie wszystkich kroków nie dłużej niż wkład?
John Dvorak,
7

SWI-Prolog, 252 bajty

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

Przykład: a(92,Z).wyjściaZ = [1, 2, 4, 8, 16, 32, 64, 46, 92]

Nie sprawdziłem jeszcze, czy to działa dla N> 99 ze względu na czas, ale nie widzę powodu, dla którego to nie działałoby.

Fatalizować
źródło
2

Julia, 306 245 218 bajtów

Nadal pracuję nad golfem. Dostarczy wersję bez golfa, gdy skończę.

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
źródło
1

Haskell, 246 bajtów

Nie jestem do końca pewien, czy to działa, czy działa, gdy sekwencja, która najpierw rozbiera się niżej (aby zostać posortowana niżej) jest zawsze krótsza, jak na przykład

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

jest krótszy niż

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

który sprawdziłem, aby był prawdziwy do 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
źródło
1

C # 655 bajtów

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

Zadzwoń za pomocą (LinqPad):

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

Nie testowałem liczb powyżej 99. Jeśli masz czas -> powodzenia ;-)

edycja: wersja bez golfa:

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
źródło
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

Wypróbuj online

Siedzę nad tym od dłuższego czasu, nie jest on zbyt krótki ani szybki i nie jestem pewien, czy mam energię / motywację, aby to poprawić, więc po prostu to publikuję.

aditsu
źródło