Buat pola alternatif

8

Masalah

Anda diberi urutan bola berwarna (merah Rdan hijau G). Salah satu urutan yang mungkin adalah:

RGGGRRGGRGRRRGGGRGRRRG

Dalam gerakan sesedikit mungkin, Anda harus membuatnya sehingga setiap bola memiliki warna yang berbeda dengan tetangganya (yaitu urutan bergantian.)

RGRGRGRGRGRGRGRGRGRGRG

Anda harus menulis sebuah program yang dapat mengubah urutan yang tidak berurutan (dalam hal ini string) dengan jumlah "R" dan "G" yang sama menjadi urutan di mana item berganti. Satu contoh sesi di bawah ini, untuk algoritma naif ( <adalah input ke program, >adalah output. Tidak perlu untuk memasukkan tanda sisipan pada input atau output.)

< RGGGRRGGRGRRRGGGRGRRRG
> RGGRGRGGRGRRRGGGRGRRRG
> RGRGGRGGRGRRRGGGRGRRRG
> RGRGRGGGRGRRRGGGRGRRRG
> RGRGRGGRGGRRRGGGRGRRRG
> RGRGRGGRGRGRRGGGRGRRRG
> RGRGRGGRGRGRGRGRGGRRRG
> RGRGRGGRGRGRGRGRGRGRRG
> RGRGRGGRGRGRGRGRGRGRGR
> RGRGRGRGGRGRGRGRGRGRGR
> RGRGRGRGRGGRGRGRGRGRGR
> RGRGRGRGRGRGGRGRGRGRGR
> RGRGRGRGRGRGRGGRGRGRGR
> RGRGRGRGRGRGRGRGGRGRGR
> RGRGRGRGRGRGRGRGRGGRGR
> RGRGRGRGRGRGRGRGRGRGGR
> RGRGRGRGRGRGRGRGRGRGRG (15 moves)

Kemungkinan lain adalah mengeluarkan "5,7" misalnya untuk menunjukkan pertukaran posisi 5 dan 7.

Anda mungkin posisi baik merah atau hijau pertama, dan Anda tidak harus konsisten. Setiap urutan akan memiliki panjang yang sama dengan setiap urutan lainnya.

Anda hanya dapat menukar dua huruf apa pun di setiap gerakan (tidak perlu berdekatan).

Kriteria Menang

Program harus menunjukkan setiap langkah dari proses sortir. Program yang membuat total gerakan paling sedikit untuk semua string di bawah ini, menang. Jika ada seri, kode terpendek akan menang.

Input String

String berikut akan digunakan untuk menguji program:

GGGGGGGGGGRRRRRRRRRR
GGRRGGRRGGRRGGRRGGRR
RRGGGGRRRRGGGGRRRRGG
GRRGRGGGGRRRGGGGRRRR
GRGGGRRRRGGGRGRRGGRR
RGRGRGRGRGRGRGRGRGRG

Urutan terakhir harus menghasilkan nol gerakan.

Thomas O
sumber
Tidakkah seharusnya "Anda hanya dapat menukar dua pasangan dalam setiap gerakan" baca "Anda hanya dapat menukar dua huruf dalam setiap gerakan"?
DavidC
@ Bung sangat bagus, saya akan memperbaikinya.
Thomas O
Adakah persyaratan agar huruf tertentu memulai urutan yang diurutkan?
dmckee --- mantan moderator kucing
@ dmckee Dari pertanyaan - "Anda dapat menentukan posisi Merah atau Hijau terlebih dahulu, dan Anda tidak harus konsisten."
Thomas O
2
Masalah yang bagus untuk dikerjakan. Saya sarankan Anda meminta orang untuk memposting beberapa contoh input dan output mereka. Dengan cara ini, mereka yang tidak memprogram dalam bahasa yang dipilih dapat membuat evaluasi tentang kesesuaian output untuk input masing-masing.
DavidC

Jawaban:

5

Python, 140 122 119 115

r=raw_input()
f=lambda x:[i for i in range(x,len(r),2)if x-(r[i]!=max('RG',key=r[::2].count))]
print zip(f(0),f(1))
grc
sumber
1
Secara teknis Anda tidak perlu penugasan s. Ini akan menghemat beberapa karakter lagi.
kojiro
Ya, sama-sama. Saya harus melakukan sesuatu yang pintar setelah Anda mengalahkan apa yang saya kerjakan.
kojiro
3

APL 46

((2|y)/y←(i≠↑i)/n),[.1](~2|y)/y←(i=↑i)/n←⍳⍴i←⍞

Menjalankan uji yang diberikan menghasilkan:

GGGGGGGGGGRRRRRRRRRR
11 13 15 17 19
 2  4  6  8 10

GGRRGGRRGGRRGGRRGGRR
3 7 11 15 19
2 6 10 14 18

RRGGGGRRRRGGGGRRRRGG
3 5 11 13 19
2 8 10 16 18

GRRGRGGGGRRRGGGGRRRR
3 5 11 17 19
4 6  8 14 16

GRGGGRRRRGGGRGRRGGRR
7  9 13 15 19
4 10 12 14 18

RGRGRGRGRGRGRGRGRGRG

Solusi di atas menggunakan indeks asal 1 dengan swap yang diberikan di kolom matriks hasil. Dua karakter dapat disimpan jika vektor input i diinisialisasi dengan string input sebelum dieksekusi daripada menjadi input pada saat eksekusi.

Graham
sumber
3

GolfScript (47 karakter)

:S;4,{S,,{.S=1&3*\1&2*^1$=},\;}%2/{zip}%{,}$0=`

Misalnya (menggunakan test case yang jauh lebih mudah untuk memeriksa kebenaran daripada yang disarankan, yang semuanya memiliki banyak jawaban yang benar):

< RRGGRGRGRGRGRGRGRGRG
> [[1 2]]

Output adalah daftar pasangan tanpa indeks untuk ditukar.

Peter Taylor
sumber
Jika [[1 2]] berarti menukar huruf pada posisi 1 dan 2, hasilnya akan tampak sama dengan input. Mohon klarifikasi.
DavidC
4
@ Bung, orang aneh apa yang mulai menghitung jam 1?
Peter Taylor
3
(Tanganku terangkat).
DavidC
2

Python, 213 karakter

I=raw_input()
def M(S,T):
 S=list(S);m=[]
 while S!=list(T):z=zip(S,T);x=z.index(('R','G'));y=z.index(('G','R'));m+=[(x,y)];S[x],S[y]='GR'
 return m
N=len(I)/2
x=M(I,N*'RG')
y=M(I,N*'GR')
print[x,y][len(x)>len(y)]

Mmenemukan bergerak diperlukan untuk mengkonversi Ske T. Itu melakukan ini dengan berulang kali menemukan Rdan Gkeluar dari posisi dan menukar mereka. Kami kemudian menemukan urutan langkah yang lebih pendek untuk mendapatkan salah satu RGRG...RGatau GRGR...GR.

Harus menemukan urutan gerakan yang optimal untuk setiap input.

Keith Randall
sumber
2

Mathematica 238

Kode

f[x_] := With[{g = "GRGRGRGRGRGRGRGRGRGR", c = Characters, p = Position},
y = c[x]; s = c[g]; {v = Equal @@@ ({s, y}\[Transpose]), 
w = Not /@ v}; {vv = Thread[{y, v}], ww = Thread[{y, w}]};
((Flatten /@ {p[#, {"R", False}], p[#, {"G", False}]}) &[If[Count[Equal @@@ 
({s, y}\[Transpose]), False] < 10, vv, ww]])\[Transpose]]

NB: \[Transpose]adalah karakter tunggal, "t", ditulis dalam Mathematica ]

Contohnya

f@"GGGGGGGGGGRRRRRRRRRR"
f@"GGRRGGRRGGRRGGRRGGRR"
f@"RRGGGGRRRRGGGGRRRRGG"
f@"GRRGRGGGGRRRGGGGRRRR"
f@"GRGGGRRRRGGGRGRRGGRR"
f@"RGRGRGRGRGRGRGRGRGRG"
f@"GRGRGRGRGRGRGRGRGRGR"

{{12, 1}, {14, 3}, {16, 5}, {18, 7}, {20, 9}}
{{4, 1}, {8, 5}, {12, 9}, {16, 13}, {20, 17}}
{{2, 3}, {8, 5}, {10, 11}, {16, 13}, {18, 19}}
{{2, 1}, {10, 7}, {12, 9}, {18, 13}, {20, 15}}
{{2, 1}, {6, 3}, {8, 5}, {16, 11}, { 20, 17}}
{}
{}

DavidC
sumber
2

Mathematica 134 atau 124

Tergantung pada bagaimana Anda menghitung "Transpose []" yang pada Mathematica hanya satu karakter (tidak ada representasi di sini). Spaces ditambahkan untuk kejelasan

G = 0; R = 1; 
x_~ d ~ y__:= Transpose[Position[Symbol /@ Characters@x - PadLeft[{}, 20, {y}], #, 1] &
                                                                                 /@ {1, -1}]
f = SortBy[{d[#, 0, 1], d[#, 1, 0]}, Length][[1]] &

Sampel:

f@"GGGGGGGGGGRRRRRRRRRR"
f@"GGRRGGRRGGRRGGRRGGRR"
f@"RRGGGGRRRRGGGGRRRRGG"
f@"GRRGRGGGGRRRGGGGRRRR"
f@"GRGGGRRRRGGGRGRRGGRR"
f@"RGRGRGRGRGRGRGRGRGRG"
f@"GRGRGRGRGRGRGRGRGRGR"

Keluaran

{{{11}, {2}}, {{13}, {4}}, {{15},  {6}}, {{17},  {8}}, {{19}, {10}}}
{{{3},  {2}}, {{7},  {6}}, {{11}, {10}}, {{15}, {14}}, {{19}, {18}}}
{{{1},  {4}}, {{7},  {6}}, {{9},  {12}}, {{15}, {14}}, {{17}, {20}}}
{{{2},  {1}}, {{10}, {7}}, {{12},  {9}}, {{18}, {13}}, {{20}, {15}}}
{{{2},  {1}}, {{6},  {3}}, {{8},   {5}}, {{16}, {11}}, {{20}, {17}}}
{}
{}
Belisarius
sumber
Pengodean sangat ekonomis. Penggunaan fungsi murni yang bagus.
DavidC
@ Bung Terima kasih :). Saya yakin PadLeft[{}, 20, {y}], #, 1]dapat dikompresi lebih sedikit
Dr. belisarius
2

Javascript - 173 karakter

a=prompt(w=[[],[]]).split('');for(i=a.length,f=a[0];i--;)if(i%2<1&&a[i]!=f)w[0].push(i);else if(i%2>0&&a[i]==f)w[1].push(i);for(i=w[0].length;i--;)alert(w[0][i]+','+w[1][i])

Sebuah tantangan besar, membuat saya sibuk selama beberapa waktu.
Di sini kode hasil untuk kasus uji:

GGGGGGGGGGRRRRRRRRRR: [10, 1] [12, 3] [14, 5] [16, 7] [18, 9]
GGRRGGRRGGRRGGRRGGRR: [ 2, 1] [ 6, 5] [10, 9] [14,13] [18,17]
RRGGGGRRRRGGGGRRRRGG: [ 2, 1] [ 4, 7] [10, 9] [12,15] [18,17]
GRRGRGGGGRRRGGGGRRRR: [ 2, 3] [ 4, 5] [10, 7] [16,13] [18,15]
GRGGGRRRRGGGRGRRGGRR: [ 6, 3] [ 8, 9] [12,11] [14,13] [18,17]
RGRGRGRGRGRGRGRGRGRG:
codeporn
sumber
1

PHP - 34 bergerak - 193 karakter

$l=strlen($a=$_GET["a"]);$n=$a[0]=="R"?"G":"R";while($i<$l){if($a[++$i]!=$n){echo$o."
";$o=$a=substr($a,0,$i).$n.preg_replace("/".$n."/",$n=="R"?"G":"R",substr($a,$i+1),1);}$n=$n=="R"?"G":"R";}

Mungkin masih mencoba untuk memperbaiki ini ...

red_green.php?a=GGGGGGGGGGRRRRRRRRRR

GRGGGGGGGGGRRRRRRRRR
GRGRGGGGGGGGRRRRRRRR
GRGRGRGGGGGGGRRRRRRR
GRGRGRGRGGGGGGRRRRRR
GRGRGRGRGRGGGGGRRRRR
GRGRGRGRGRGRGGGGRRRR
GRGRGRGRGRGRGRGGGRRR
GRGRGRGRGRGRGRGRGGRR
GRGRGRGRGRGRGRGRGRGR
Aurel300
sumber
itu bisa lebih baik digunakan $argv[0]sebagai gantinya, menghemat 2 byte / masing-masing. Dan akan lebih valid, karena $argvsering digunakan untuk input melalui CMD
RedClover