Kunci sepeda kombinasi

46

Skenarionya

Setelah seharian bekerja keras di kantor dan menjelajah stackexchange.com , saya akhirnya keluar dari pintu pada pukul 16:58, sudah lelah dengan hari itu. Karena saya masih magang, moda transportasi saya saat ini adalah bersepeda. Saya menuju ke Peugeot Reynolds 501 saya yang tepercaya , tapi sebelum saya bisa berlayar, saya harus membuka kunci. Kunci adalah kunci kombinasi empat digit standar (0-9), melalui bingkai dan roda depan. Ketika saya mencoba untuk tetap terjaga, saya menarik tangan saya untuk memasukkan dalam kombinasi. Kunci sepeda kombinasi

Tantangan

Karena jari saya sangat lelah, saya ingin memutar kunci ke kombinasi yang benar dengan gerakan paling sedikit. Satu gerakan didefinisikan sebagai rotasi oleh satu posisi (36 derajat), misalnya ada satu gerakan dari 5737ke 5738. Namun, saya dapat menangkap hingga tiga cincin berturut-turut pada saat yang sama, dan memutarnya sebagai satu , yang hanya dihitung sebagai satu gerakan. Misalnya hanya ada satu gerakan dari 5737ke 6837atau ke 5626. Pindah dari 5737ke 6838bukan satu gerakan, karena angka nomor 1,2 dan 4 telah bergerak ke arah yang sama, tetapi secara independen dari angka 3.

Oleh karena itu, untuk kombinasi yang diberikan, saya dapat melihat pada kunci sepeda (bilangan bulat 4 digit), berapa jumlah gerakan terendah yang dapat saya buat untuk membuatnya tidak terkunci, dan ya, saya dapat memutar ke arah mana saja kapan saja. Maksud saya, saya dapat mengubah beberapa digit dalam satu arah dan digit lainnya di arah lain: tidak semua gerakan saya akan menjadi berlawanan arah jarum jam atau searah jarum jam untuk setiap pembukaan kunci.

Karena saya malas, kode pembuka kunci saya adalah 0000.

Ini adalah kode golf saya tidak bisa repot menulis banyak kode, jadi program terpendek dalam jumlah byte menang.

Input dari stdin, dan kode Anda harus menampilkan kombinasi yang dapat saya lihat di setiap langkah setelah setiap gerakan, termasuk 0000 di akhir. Setiap output kombinasi harus dipisahkan oleh spasi / baris baru / koma / periode / ampersand.

Contohnya

Input: 1210
0100
0000

Input: 9871
9870
0980
0090
0000

Input: 5555
4445&3335&2225&1115&0005&0006&0007&0008&0009&0000

Input: 1234
0124 0013 0002 0001 0000

Saya mencoba memposting ini di http://bicycles.stackexchange.com , tetapi mereka tidak menyukainya ...

Penafian: Golf pertama, jadi apa pun yang rusak / informasi yang hilang beri tahu saya! Saya juga melakukan semua contoh dengan tangan, jadi mungkin ada solusi yang melibatkan lebih sedikit gerakan!

EDIT: Untuk jawaban yang memiliki banyak jalur solusi dengan jumlah gerakan yang sama (hampir semuanya), tidak ada solusi yang disukai.

Lui
sumber
18
Selamat datang di PPCG; tantangan pertama yang sangat bagus!
Gagang Pintu
4
Ini terlihat kokoh bagiku! Selamat datang di PPCG!
Mego
1
Tantangan yang bagus. Bisakah saya bertanya apa yang harus menjadi output untuk kasus: 7478 dan 3737?
noisyass2
1
@ noisyass2 Terima kasih; Jawaban flawr memberikan yang berikut: 7478 8588 9698 0708 0808 0908 0008 0009 0000 dan 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Hanya dengan melihat 3737, ini masuk akal: Melihat 3 digit pertama saja: Jika saya memindahkan semua tiga pertama sekaligus, dibutuhkan 3 gerakan untuk angka 1 dan 3, dan kemudian 4 gerakan lagi untuk angka 2, sehingga totalnya tujuh. Sedangkan jika saya bergerak masing-masing secara terpisah, masing-masing membutuhkan 3 gerakan, dengan demikian 9 gerakan.
Lui
1
Saya ingin tahu apakah judul "Kunci Kombinasi" (atau "Kunci Sepeda") mungkin menarik lebih banyak penonton.
DavidC

Jawaban:

10

Matlab, 412 327 byte

Golf (Berkat @AndrasDeak untuk bermain golf s!):

s=dec2bin('iecbmgdoh'.'-97)-48;s=[s;-s];T=1e4;D=Inf(1,T);P=D;I=NaN(T,4);for i=1:T;I(i,:)=sprintf('%04d',i-1)-'0';end;G=input('');D(G+1)=0;for k=0:12;for n=find(D==k);for i=1:18;m=1+mod(I(n,:)+s(i,:),10)*10.^(3:-1:0)';if D(m)==Inf;D(m)=k+1;P(m)=n-1;end;end;end;end;n=0;X='0000';while n-G;n=P(n+1);X=[I(n+1,:)+48;X];end;disp(X)

Kode ini menggunakan beberapa pemrograman dinamis untuk menemukan 'jalur' terpendek dari nomor yang diberikan untuk 0000hanya menggunakan langkah-langkah yang mungkin. Tantangannya pada dasarnya adalah jalur terpendek prioblem (atau Anda mungkin dapat mempertimbangkan langkah-langkah sebagai kelompok komutatuve), tetapi kesulitan datang dengan implementasi yang efisien . Struktur dasar adalah dua array 10.000 elemen, satu untuk menyimpan jumlah langkah untuk sampai ke indeks itu, yang lain untuk menyimpan pointer ke 'simpul' sebelumnya dalam grafik kami. Ini secara bersamaan menghitung 'jalur' ke semua angka yang mungkin lainnya.

Contoh:

9871
0981
0091
0001
0000

1210
0100
0000

Examples by @noisyass:

7478
8578
9678
0788
0899
0900
0000

3737
2627
1517
0407
0307
0207
0107
0007
0008
0009
0000

Own Example (longest sequence, shared with 6284)

4826
3826
2826
1826
0826
0926
0026
0015
0004
0003
0002
0001
0000    

Kode Lengkap (termasuk beberapa komentar):

%steps
s=[eye(4);1,1,0,0;0,1,1,0;0,0,1,1;1,1,1,0;0,1,1,1];
s=[s;-s];


D=NaN(1,10000);%D(n+1) = number of steps to get to n
P=NaN(1,10000);%P(n+1) was last one before n

I=NaN(10000,4);%integer representation as array
for i=0:9999; 
    I(i+1,:)=sprintf('%04d',i)-'0';
end

G=9871; % define the current number (for the golfed version replaced with input('');
D(G+1)=0;
B=10.^(3:-1:0); %base for each digit

for k=0:100; %upper bound on number of steps;
    L=find(D==k)-1;
    for n=L; %iterate all new steps
        for i=1:18; %search all new steps
            m=sum(mod(I(n+1,:)+s(i,:),10) .* [1000,100,10,1]);
            if isnan(D(m+1))
                D(m+1) = k+1;
                P(m+1)=n;
            end
        end
    end
end
n=0;%we start here
X=[];
while n~=G
    X=[I(n+1,:)+'0';X];
    n=P(n+1);
end
disp([I(G+1,:)+'0';X,''])
cacat
sumber
Bagus! Sebagai pengguna yang sebagian besar pengguna Matlab, saya bertanya-tanya seberapa bagus harganya.
Lui
1
Untuk input 6444kode Anda memberikan 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, sedangkan saya menemukan jawabannya menjadi 6444 6333 6222 6111 6000 7000 8000 9000 0000. Jawaban saya adalah 8 langkah, Anda adalah 10. Saya tidak dapat melihat masalah, dan tampaknya ada di sana baik dalam versi golf dan ungolfed. Ini diperbaiki dalam suntingan terbaru Anda.
Lui
1
Saya baru saja memperbaiki kesalahan kecil dalam kode. Di sbaris terakhir seharusnya [0,1,1,1]. Maka Anda mendapatkan solusi 8 langkah juga! Saya minta maaf atas ketidaknyamanan =)
flawr
1
@Lui Ada ruang obrolan matlab / oktaf , antara lain itu semacam Pangkalan untuk bahasa golf Matlab yang diturunkan dari bahasa Inggris.
flawr
1
untuk 4826, saya menemukan solusi 11 langkah: 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000
noisyass2
4

Batch - 288 byte

Bahkan jika Anda mengatakan mereka harus berurutan (berdering), saya berasumsi dengan logika (mengikuti contoh) bahwa saya dapat melewatkan yang di tengah, mulai dari 1234hingga 0224.

set / px =
atur a =% x: ~ 0,1% & set b =% x: ~ 1,1% & set c =% x: ~ 2,1% & set d =% x: ~ 3,1%
: l
@echo% x% & jika% a% == 0 (jika% d% NEQ 0 set / iklan = d-1) set lain / aa = a-1
@jika% b% NEQ 0 set / ab = b-1
@Jika% c% NEQ 0 set / ac = c-1
@jika% x% NEQ 0000 set x =% a %% b %% c %% d% & goto l

Ini adalah solusi Batch saya: 236 byte.


Edit: solusi yang diperbaiki

set / px =
atur a =% x: ~ 0,1% & set b =% x: ~ 1,1% & set c =% x: ~ 2,1% & set d =% x: ~ 3,1%
: l
@echo% x% & set k = 1 & jika% a% == 0 (jika% d% NEQ 0 set / ad = d-1 & set k = 0) set lain / aa = a-1 & set k = 1
@jika% b% NEQ 0 jika% k% == 1 set / ab = b-1 & set k = 0
@jika% c% NEQ 0 jika% k% == set / ac = c-1
@jika% x% NEQ 0000 set x =% a %% b %% c %% d% & goto l

Solusi baru (diperbaiki sesuai dengan komentar yang mendasarinya) adalah 288 byte.

ribut
sumber
Saya belum melihat jawaban Anda secara mendalam, tetapi saya berjuang untuk mengikuti logika Anda di paragraf pertama. Contoh mana yang secara spesifik Anda maksud? Dan contoh Anda pergi dari 1234ke 0224adalah tidak satu gerakan. Idenya adalah bahwa dengan hanya menggunakan dua jari saya dapat memegang hingga tiga cincin berturut-turut dengan satu genggaman.
Lui
Maksud saya, jika Anda dapat memindahkan 3 dering berturut-turut, masuk akal untuk berpikir bahwa Anda juga dapat memindahkan yang pertama dan ketiga, menghindari yang kedua. Atau haruskah saya mengubah kode saya?
Noize
Asumsi Anda salah; Anda harus mengubah kode Anda. Apakah Anda melihat logika seperti yang dijelaskan dalam komentar di atas?
Lui
Kode diperbaiki. Saya memeriksa beberapa jenis kombinasi yang berbeda dan bagi saya sepertinya perlu waktu yang lebih singkat.
Kebisingan
Ini tampaknya hanya menghitung ke bawah, sehingga dibutuhkan lebih lama dari yang diperlukan untuk kombinasi dengan angka tinggi (mis. 18 gerakan untuk 9999)
faubi
2

Haskell - 310 byte

import Data.Char
import Data.List
r=replicate
h=head
a x=map(:x)[map(`mod`10)$zipWith(+)(h x)((r n 0)++(r(4-j)q)++(r(j-n)0))|j<-[1..3],n<-[0..j],q<-[1,-1]]
x!y=h x==h y
x#[]=(nubBy(!)$x>>=a)#(filter(![(r 4 0)])x)
x#y=unlines.tail.reverse.map(intToDigit<$>)$h y
main=do x<-getLine;putStrLn$[[digitToInt<$>x]]#[]

Ini berfungsi dengan berulang kali membuat daftar kombinasi baru dengan menerapkan setiap belokan yang mungkin untuk setiap kombinasi yang telah tercapai hingga salah satunya adalah kombinasi yang tepat. Duplikat dihapus dari daftar pada setiap iterasi untuk menjaga penggunaan memori tumbuh secara eksponensial.

Sebagai solusi brute force, ini sangat tidak efisien dan dapat memakan waktu beberapa menit untuk berjalan.

Saya tidak punya banyak pengalaman dengan Haskell, jadi beberapa hal mungkin bisa dilakukan dengan lebih baik.

faubi
sumber
Tampak seperti dasar yang kuat untuk pendekatan Anda. Saya belum berpengalaman dengan Haskell, atau (yang saya tahu) cara mengkompilasi / menjalankannya. Google cepat tidak memberikan saya di mana pun saya bisa mencobanya. Apakah Anda dapat memberikan tautan yang memungkinkan saya mencobanya? Terima kasih.
Lui
@Lui Dapat dikompilasi dengan Glasgow Haskell Compiler , tetapi selain mengunduh dan menggunakan itu saya tidak tahu cara untuk menjalankannya.
faubi