10

Ini adalah teka-teki umum yang telah Anda pecahkan secara manual. Sekarang ini saatnya untuk menulis algoritma untuk menyelesaikannya.

Ada batang korek api dengan jumlah yang sama dan berjajar di dua sisi yang berbeda menghadap ke arah masing-masing. Ada satu ruang kosong di antara mereka. Katakan sesuatu seperti gambar berikut (jika jumlah total batang korek adalah 4).

masukkan deskripsi gambar di sini

Setiap tongkat dapat meluncur satu langkah ke arah depan (jika ruang depan langsung bebas), atau dapat dilompati satu tongkat di depan mereka, dan mendarat ke ruang bebas (jika ruang itu gratis). Pergerakan ke arah sebaliknya tidak dimungkinkan (bahkan ruangnya gratis). Tidak ada reverse jump juga diperbolehkan. Hanya satu gerakan yang diizinkan dalam satu langkah.

Sekarang, Anda harus menulis sebuah algoritma untuk menemukan langkah-langkah minimum yang diperlukan dengan menggunakan mana semua batang korek api sisi kiri akan mendarat di sisi kanan dan semua batang korek api sisi kanan akan mendarat di sisi kiri.

Misalnya: Jika ada total 2 batang korek api (1 di setiap sisi) maka langkah-langkahnya adalah:

masukkan deskripsi gambar di sini

Catatan: Pada gambar di atas, tongkat sisi kiri dipindahkan terlebih dahulu. Solusi lain ada ketika tongkat sisi kanan bergerak terlebih dahulu. Tetapi untuk masalah ini, Anda harus memberikan hanya satu solusi dan itu juga dengan asumsi bahwa tongkat sisi kiri bergerak terlebih dahulu.

Gambar berikut menjelaskan gerakan dengan 4 batang korek api (2 di setiap sisi):

masukkan deskripsi gambar di sini

Catatan: Pada gambar di atas, tongkat sisi kiri dipindahkan terlebih dahulu. Solusi lain ada ketika tongkat sisi kanan bergerak terlebih dahulu. Tetapi untuk masalah ini, Anda harus memberikan hanya satu solusi dan itu juga dengan asumsi bahwa tongkat sisi kiri bergerak terlebih dahulu.

[Asumsi: Input dapat berupa angka genap antara 02 hingga 14 (yaitu 1 hingga 7 batang korek api di setiap sisi). Untuk input di luar rentang ini, Anda tidak perlu melakukan validasi apa pun, tidak perlu memberikan pesan kesalahan apa pun. Catatan: Dalam output, setiap langkah dipisahkan oleh '|' karakter (pipa). Programmer COBOL harus selalu menganggap PIC 9 (2) sebagai ukuran input & juga dapat menganggap output ditetapkan panjang maksimum 450 karakter, diisi dengan spasi di sebelah kanan.]

Input sampel:

Output sampel:

01To02|03To01|02To03|

Input sampel:

Output sampel:

02To03|04To02|05To04|03To05|01To03|02To01|04To02|03To04|

Input sampel:

Output sampel:

03To04|05To03|06To05|04To06|02To04|01To02|03To01|05To03|07To05|06To07|04To06|02To04|03To02|05To03|04To05|

code-challenge pengguna2076421
sumber

Jika Anda tidak dapat memasukkan gambar secara langsung, dapatkah Anda memberikan tautan kepada orang lain untuk mengeditnya?

Peter Taylor

2

Saya membuat beberapa gambar cepat. Semoga mereka sesuai dengan maksud penulis asli.

primo

3

Kondisi untuk kemenangan?

Shmiddty

3

APL 129

Kode di bawah ini mengambil input dan output layar ke layar dalam format yang ditentukan:

n←n,n++\1↓z←(⌽z),((¯1*~2|n)×n⍴2),z←⌽∊(¯1*2|⍳n)×¨1,((⍳(n←.5×⍎⍞)-1)⍴¨2),¨1⋄(∊(((¯2↑¨'0',¨⍕¨n),¨⊂'To'),¨(¯2↑¨'0',¨⍕¨n-z)),¨⊂'|')~' '

Sepertiga yang baik dari kode diambil memformat output. Logikanya lengkap dengan kemunculan simbol ⋄ dalam kode.

Di bawah ini adalah hasil untuk input 08 sebagai cek:

04To05|06To04|07To06|05To07|03To05|02To03|04To02|06To04|08To06|09To08|07To09|05To07|03To05|01To03|02To01|04To02|06To04|08To06|07To08|05To07|03To05|04To03|06To04|05To06|

Graham
sumber

1

Saya selalu merasa APL selingkuh>. <

Shmiddty

@Shmiddty Saya takut bahwa bahasa berbasis simbol murni seperti APL, J, GolfScript dll kemungkinan besar akan memenangkan kode golf terhadap lebih banyak bahasa berbasis kata yang lebih jelas;)

Graham

3

Javascript 178 174 161

prompts untuk nkemudian alerts jawaban. (Tidak ada 0bantalan)

Terbaru:

t=1+(m=prompt(s=i='')/2);for(z=Math.abs;i++<m*2;)for(j=m-z(m-i),s+=(t+=a=(m%2^z(m+.5-i)%2-.5)*-2+1)+'To'+(t-a)+'|';j--;)s+=(t+=a=i%2*4-2)+'To'+(t-a)+'|';alert(s)

2:

z=Math.abs;t=m=prompt(o=[])/2;t++;for(s=i='';i++<m*2;)for(j=m-z(m-i),o.push((z(m+.5-i)%2-.5)?-1:1);j--;)o.push(i%2?2:-2);o.map(function(a){s+=(t+=a)+'To'+(t-a)+'|'});alert(s)

1:

t=m=prompt(o=[])/2+1;for(s=i='';++i<m;)for(j=i,o.push(i%2?-1:1);j--;)o.push(i%2?2:-2);o.concat(o.slice().reverse().slice(m-1)).map(function(a){s+=(t+=a)+'To'+(t-a)+'|'});alert(s)

Ini menggunakan konsep bahwa polanya dicerminkan:

Key
R='Jump Right'
r='Shift Right'
L='Jump Left'
l='Shift Left'
m='Move'
j='Jump'

Jadi, di mana n=2, pola pergerakannya adalah:

rLr
mjm

Yang setara dengan

+1 -2 +1

Pola ini berulang seperti ( n=8)

rLlRRrLLLlRRRRlLLLrRRlLr
mjmjjmjjjmjjjjmjjjmjjmjm
+1 -2 -1 +2 +2 +1 -2 -2 -2 -1 +2 +2 +2 +2 -1 -2 -2 -2 +1 +2 +2 -1 -2 +1

Kita dapat melihat beberapa pola di sini:

Gerakan bergantian antara kiri dan kanan
Jumlah gerakan dalam arah tertentu meningkat dari 1 ke n/2, yang berulang 3 kali, kemudian menurun kembali ke 1.
Jenis gerakan bergantian antara menggeser dan melompat, jumlah pergeseran dalam satu baris menjadi konstan 1, dan jumlah lompatan berurutan meningkat dari 1 hingga n/2kemudian menurun kembali ke 1.
Penjumlahan dari gerakan selalu 0. (Tidak yakin apakah ini benar-benar relevan)

n=14:

rLlRRrLLLlRRRRrLLLLLlRRRRRRrLLLLLLLrRRRRRRlLLLLLrRRRRlLLLrRRlLr
mjmjjmjjjmjjjjmjjjjjmjjjjjjmjjjjjjjmjjjjjjmjjjjjmjjjjmjjjmjjmjm

Output sampel:

f(2):

1To2|3To1|2To3|

f(8):

4To5|6To4|7To6|5To7|3To5|2To3|4To2|6To4|8To6|9To8|7To9|5To7|3To5|1To3|2To1|4To2|6To4|8To6|7To8|5To7|3To5|4To3|6To4|5To6|

f(40):

20To21|22To20|23To22|21To23|19To21|18To19|20To18|22To20|24To22|25To24|23To25|21To23|19To21|17To19|16To17|18To16|20To18|22To20|24To22|26To24|27To26|25To27|23To25|21To23|19To21|17To19|15To17|14To15|16To14|18To16|20To18|22To20|24To22|26To24|28To26|29To28|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|12To13|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|31To30|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|10To11|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|33To32|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|8To9|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|35To34|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|6To7|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|37To36|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|4To5|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|39To38|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|2To3|4To2|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|40To38|41To40|39To41|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|1To3|2To1|4To2|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|40To38|39To40|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|4To3|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|37To38|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|6To5|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|35To36|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|8To7|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|33To34|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|10To9|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|31To32|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|12To11|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|29To30|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|14To13|16To14|18To16|20To18|22To20|24To22|26To24|28To26|27To28|25To27|23To25|21To23|19To21|17To19|15To17|16To15|18To16|20To18|22To20|24To22|26To24|25To26|23To25|21To23|19To21|17To19|18To17|20To18|22To20|24To22|23To24|21To23|19To21|20To19|22To20|21To22|

Berikut beberapa kode semu untuk mendemonstrasikan metodenya:

var mid=cursor=N/2,delta
cursor++                 // the cursor is where the empty space is.
for(i=0; i++<N;){
  delta = (mid%2^abs(mid+.5-i)%2-.5)*-2+1;  // 1 or -1
  print((cursor+delta) + 'To' + cursor + '|')
  cursor+=delta
  for(j=mid-abs(mid-i);j--;)
  {
    delta = i%2*4-2  // 2 or -2
    print((cursor+delta) + 'To' + cursor + '|')
    cursor+=delta
  }
}

Shmiddty
sumber

2

Anda benar bahwa polanya lebih jelas dengan l/L/r/Rdan m/j. Saya suka ide memisahkan jarak bergerak dari arah

Gordon Bailey

2

C - 216 213

Solusi saya didasarkan pada dua fakta:

Bidang "ke" adalah bidang "dari" dari langkah sebelumnya (karena Anda selalu membuat slot kosong di tempat Anda bergerak, dan Anda selalu pindah ke slot kosong)
Ada pola yang sangat teratur untuk jarak dan arah yang dipindahkan. Untuk 3 kasus uji pertama, mereka adalah:

1 -2 1

1 -2 -1 2 2 -1 -2 1

1 -2 -1 2 2 1 -2 -2 -2 1 2 2 -1 -2 1

Dengan pemikiran itu saya pada dasarnya hanya menulis sebuah program untuk menghasilkan dan melanjutkan pola itu. Saya cukup yakin pasti ada cara rekursif yang sangat indah dan jauh lebih elegan untuk menulis ini, tetapi saya belum menemukan jawabannya:

#include <stdio.h>

int main(int argc, const char *argv[])
{
   int upper_bound = atoi(argv[1]) / 2;
   int len;
   int from;
   int to = upper_bound + 1;
   int direction = 1;
   int i;

   for(len = 1; len <= upper_bound; ++len){
      for(i = len-1; i >=0; --i){
         from = to - direction*(1 + (i!=0));
         printf("%02dTo%02d|",from,to);
         to = from;
      }
      direction*=-1;
   }
   for(i=1; i < len; ++i){
      from = to - direction*2;
      printf("%02dTo%02d|",from,to);
      to = from;
   }
   direction*=-1;
   for(--len; len >= 0; --len){
      for(i = 0; i < len; ++i){
         from = to - direction*(1 + (i!=0));
         printf("%02dTo%02d|",from,to);
         to = from;
      }
      direction*=-1;
   }
   return 0;
}

Dan bermain golf (meskipun ini tantangan kode, bukan golf):

#define B {F=T-D*(1+(i!=0));printf("%02dTo%02d|",F,T);T=F;}D*=-1; L,F,T,D,i;main(int U,char**A){U=atoi(A[1])/2;T=U+1;D=1;for(L=1;L<=U;++L){for(i=L-1;i>=0;--i)B}for(i=1;i<L;++i)B for(--L;L>=0;--L){for(i=0;i<L;++i)B}}

#define B {F=T-D*(1+(i!=0));printf("%02dTo%02d|",F,T);T=F;}D*=-1;
L,F,T,D,i;main(int U){scanf("%d",&U);U/=2;T=U+1;D=1;for(L=1;L<=U;++L){for(i=L-1;i>=0;--i)B}for(i=1;i<L;++i)B for(--L;L>=0;--L){for(i=0;i<L;++i)B}}

Gordon Bailey
sumber

Ketika saya menjalankan versi golf Anda, saya mendapatkan segfault.

artistoex

Oh maaf, saya lupa menyebutkan bahwa input diberikan sebagai argumen baris perintah - jika Anda menjalankannya tanpa argumen itu akan segfault. Tapi sebenarnya sekarang setelah Anda menyebutkannya, saya tidak tahu mengapa saya pikir argumen baris perintah akan lebih pendek dari scanf. Saya memperbarui jawaban saya dengan versi yang lebih baik.

Gordon Bailey

Pola ini lebih terlihat ketika Anda menggunakan L / R / l / r (besar makhluk "melompat"): N(2)=rLr, N(4)=rLlRRlLr, N(6)=rLlRRrLLLrRRlLr, dll

Shmiddty

2

Mathematica

Pendekatan ini membangun Nesturutan ukuran dan arah gerakan, yang diformat sebagai {fromPosition,toPosition}, dimulai dengan posisi n, di mana nmengacu pada jumlah pasangan yang cocok. Kemudian Foldurutan menjadi fungsi yang dimulai dengan bergerak {n, n+1}.

z@n_:=(p=1;h@t_:=Append[{Table[2 (-1)^t,{t}]},{(-1)^(t+1)}];
k=Join[Reverse@Drop[#,n],#]&[Flatten@Nest[Prepend[#,h[p++]]&,{},n]];
Fold[Append[#,{#[[-1,1]]-#2,#[[-1,1]]}]&,{{n,n+k[[1]]}},Rest@k])

z[1]

{{1, 2}, {3, 1}, {2, 3}}

z[4]

{{4, 5}, {6, 4}, {7, 6}, {5, 7}, {3, 5}, {2, 3}, {4, 2}, {6, 4}, { 8, 6}, {9, 8}, {7, 9}, {5, 7}, {3, 5}, {1, 3}, {2, 1}, {4, 2}, {6, 4}, {8, 6}, {7, 8}, {5, 7}, {3, 5}, {4, 3}, {6, 4}, {5, 6}}

z[7]

{{7, 8}, {9, 7}, {10, 9}, {8, 10}, {6, 8}, {5, 6}, {7, 5}, {9, 7}, { 11, 9}, {12, 11}, {10,12}, {8, 10}, {6, 8}, {4, 6}, {3, 4}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {14, 13}, {12, 14}, {10, 12}, {8, 10}, {6, 8} , {4, 6}, {2, 4}, {1, 2}, {3, 1}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, { 13, 11}, {15, 13}, {14, 15}, {12, 14}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {2, 4}, {3, 2}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {12, 13}, {10, 12} , {8, 10}, {6, 8}, {4, 6}, {5, 4}, {7, 5}, {9, 7}, {11, 9}, {10, 11}, { 8, 10}, {6, 8}, {7, 6}, {9, 7}, {8, 9}}

Memvisualisasikan Swaps

r,, bdan omerupakan gambar atau kecocokan merah, kecocokan biru, dan tanpa kecocokan, masing-masing.

cocok

Berikut ini format keluaran dari zuntuk menampilkan swap dengan kecocokan.

swaps[n_]:=FoldList[Grid[{Permute[#[[1,1]],Cycles[{#2}]],Range[2n+1]}]&,
Grid[{Join[Table[r,{n}],{o},Table[b,{n}]],Range[2n+1]}],z[n]]

swapMatches[n_]:=Grid[Partition[swaps[n],2,2,1,""],Dividers->All]

swapsmenghasilkan daftar negara dengan menggunakan pasangan yang dipesan zsebagai perintah untuk mengubah daftar awal dan daftar berikutnya.

swaps[1]

swaps1

swapMatches menampilkan status dalam kotak.

swapMatches[2]

swaps2

swapMatches[3]

swaps3

DavidC
sumber

0

Javascript 191

function f(N) {
    n=N>>=i=c=a='1';n++
    s=z='0'
    for(k=b='34';i<N;k=i%2?a+=z+z:b+='44',i++)c=k+c
    t=''
    i=N*(N+1)/2
    l=2*i+N
    for(;l;n+=(i>=1?r=c[i-1]:i<=-N?c[-i-N]:k[1])-2,t+=(s=n>9?'':z)+n+a+'|',--l,--i)a='To'+s+n
    return t
}

Karakter dihitung menggunakan grep =|tr -d \ |wc -c

artisoex
sumber

1

Hai dan selamat datang di codegolf! Saya pikir Anda akan menemukan solusi Anda tidak menghasilkan output yang benar untuk semua kasus uji ( jsfiddle.net/SJwaU ). Untuk input 02, nilainya benar, tetapi tidak ada jejaknya |. Untuk dua kasus lainnya, nilainya jauh, dan format 10juga salah. Juga tidak yakin tentang metode penghitungan karakter Anda. Mengapa Anda hanya menghitung fungsi tubuh dikurangi pengembaliannya?

Gordon Bailey

@ Gordon Ups, sepertinya saya membuat kesalahan dalam pengoptimalan terbaru saya. Terima kasih telah menunjukkan. Saya menghitung tubuh hanya karena pada REPL, itu yang Anda butuhkan. Saya sudah menempatkan fungsi dekorasi hanya demi kenyamanan.

artistoex

Anda perlu menghitung spasi yang relevan (misalnya baris baru) terhadap total Anda.

Shmiddty

@shmiddty tr -d \ |wc -cmemperhitungkan jalur - jalur baru

artistoex

Bertukar angka [tertutup]

Jawaban:

APL 129

Javascript 178 174 161

C - 216 213

Mathematica

Javascript 191