Bisakah Anda mencapai nomor ini dengan menggandakan dan menata ulang?

34

Terinspirasi oleh pertanyaan ini pada Math.SE .

Dimulai dengan 1Anda dapat berulang kali melakukan salah satu dari dua operasi berikut:

  • Gandakan jumlahnya.

    atau

  • Susun ulang digitnya dengan cara apa pun yang Anda inginkan, kecuali tidak boleh ada angka nol di depan.

Mengambil contoh dari pos Math.SE yang tertaut, kita dapat mencapai 1000melalui langkah-langkah berikut:

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

Nomor mana yang dapat Anda jangkau dengan proses ini dan apa solusi terpendek?

Tantangan

Dengan bilangan bulat positif N, tentukan urutan bilangan bulat terpendek yang mungkin dicapai Ndengan proses di atas, jika memungkinkan. Jika ada beberapa solusi optimal, output salah satunya. Jika tidak ada urutan seperti itu, Anda harus menampilkan daftar kosong.

Urutan mungkin dalam format string atau daftar yang nyaman, tidak ambigu.

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).

Ini adalah kode golf, jadi jawaban tersingkat (dalam byte) menang.

Uji Kasus

Berikut adalah daftar semua nomor yang dapat dijangkau hingga dan termasuk 256. Kolom pertama adalah nomor (input Anda), kolom kedua adalah jumlah langkah optimal (yang dapat Anda gunakan untuk memeriksa validitas solusi Anda) dan yang ketiga kolom adalah salah satu urutan optimal untuk sampai ke sana:

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}

Jika Anda ingin lebih banyak data pengujian, berikut adalah tabel yang sama hingga dan termasuk 1.000 .

Angka apa pun yang tidak muncul pada tabel ini harus menghasilkan daftar kosong (asalkan angkanya dalam kisaran tabel).

code-golf sequence number-theory path-finding permutations Martin Ender
sumber
Apakah ada batasan waktu eksekusi?
Fatalkan
2
@Faktalisasi tidak, gila.
Martin Ender
Saya kira waktu eksekusi berpotensi tak terbatas tidak dapat diterima? Secara teori harus mengakhiri?
Fatalkan
@Fatalize Ah ya, seperti biasa .
Martin Ender
Bagaimana ketika ada lebih dari satu hasil: [1, 2, 4, 8, 16, 32, 64, 46, 92, 29] [1, 2, 4, 8, 16, 32, 23, 46, 92, 29]
dbramwell

Jawaban:

18

Pyth, 43 byte

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

Demonstrasi.

Ini dimulai dengan menghasilkan semua kemungkinan urutan ganda atau mengatur ulang. Namun, karena saya benar-benar ingin melihatnya selesai, saya menambahkan hubungan pendek.

Entah itu berjalan sampai menemukan solusi, atau untuk sejumlah iterasi yang sama dengan input, pada titik mana ia menyerah dan kembali [].

Ini dijamin untuk iterasi yang cukup. Pertama, kita tahu bahwa banyak iterasi ini cukup untuk semua n <= 1000, berkat hasil contoh. Untuk angka yang lebih besar, argumen berikut ini berlaku:

Pertama, setiap langkah proses harus mempertahankan atau menambah jumlah digit.

Kedua, tiga angka yang semuanya menata ulang satu sama lain tidak akan pernah bisa muncul dalam urutan terpendek, karena akan lebih cepat untuk hanya melakukan penataan ulang tunggal dari yang pertama ke yang terakhir.

Ketiga, semua kelipatan 3 tidak dapat dijangkau, karena penggandaan maupun penataan ulang tidak dapat menghasilkan kelipatan 3 dari yang bukan kelipatan 3.

Dengan demikian, urutan terpanjang yang mungkin berakhir pada angka yang diberikan sama dengan jumlah dua kali jumlah set digit dengan kurang dari atau sama dengan banyak digit input, dan di mana digit tidak menjumlahkan kelipatan 3.

Jumlah digit tersebut ditetapkan untuk setiap jumlah digit:

4 - 474
5 - 1332
6 - 3330

Selain itu, kita tahu dari contoh-contoh bahwa tidak ada urutan terpendek yang berakhir dengan angka 3 digit lebih panjang dari 26. Jadi, batas atas panjang urutan adalah:

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

Dalam setiap kasus, batas atas lebih rendah dari angka apa pun dengan jumlah digit

Jumlah set digit tidak dapat tumbuh lebih dari faktor 10 ketika jumlah digit bertambah satu, karena angka baru dapat dipisahkan menjadi grup dengan digit terakhir, masing-masing tidak dapat memiliki lebih banyak set daripada yang ada dengan lebih sedikit angka.

Dengan demikian, batas atas akan lebih rendah dari angka mana pun dengan banyak digit untuk semua kemungkinan jumlah digit lebih besar dari atau sama dengan 4, yang melengkapi bukti bahwa sejumlah iterasi yang sama dengan input selalu cukup.

isaacg
sumber
Apakah Anda yakin jumlah iterasi yang sama dengan input sudah cukup? Secara teori tidak akan batas atas berada di sekitar kekuatan 10 yang lebih besar berikutnya (karena urutan dapat menurun secara sewenang-wenang).
Martin Ender
@ MartinBüttner Poin bagus. Saya pikir harus ada bukti bahwa input selalu cukup, tetapi saya akan mengeditnya sekarang.
isaacg
@ MartinBüttner Bukti bahwa iterasi yang sama dengan input selalu cukup ditambahkan.
isaacg
Ah, sangat bagus. :) (Menariknya, bahkan hingga 100.000 Anda tidak perlu lebih dari 26 langkah.)
Martin Ender
Saya percaya akan lebih cepat untuk menyebutkan semua langkah tidak lebih dari input?
John Dvorak
7

SWI-Prolog, 252 byte

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

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

Saya belum memeriksa apakah ini bekerja untuk N> 99 karena waktu yang diperlukan, tetapi saya tidak melihat alasan mengapa itu tidak berhasil.

Fatalisasi
sumber
2

Julia, 306 245 218 byte

Masih berusaha bermain golf ini. Akan memberikan versi yang tidak diklik setelah saya selesai.

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

Haskell, 246 byte

Saya tidak sepenuhnya yakin apakah ini bekerja, itu tidak jika urutan yang pertama menyimpang lebih rendah (untuk diurutkan lebih rendah) selalu lebih pendek, seperti misalnya

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

lebih pendek dari

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

yang saya uji benar hingga 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
sumber
1

C # 655 byte

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

Panggilan dengan (LinqPad):

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

Belum menguji angka di atas 99. Jika Anda punya waktu -> semoga berhasil ;-)

sunting: versi yang tidak disatukan:

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

Cobalah online

Saya sudah duduk di ini untuk waktu yang lama, itu tidak terlalu pendek atau cepat, dan saya tidak yakin saya memiliki energi / motivasi untuk memperbaikinya, jadi saya hanya mempostingnya.

aditsu
sumber