34

Buat program atau fungsi untuk menguraikan satu angka dengan membalik (membalikkan sekitar titik tengah) hanya baris dan kolom.

Memasukkan

Input akan berupa grid digit 9x9 dalam bentuk string 9 baris seperti berikut:

Format input ini tidak dapat dinegosiasikan - solusi apa pun yang "kreatif" dengan format input akan dianggap tidak valid.

Keluaran

Output harus berupa daftar gerakan flip yang, bila diterapkan pada input dalam urutan yang diberikan, harus membuat ulang kisi target.

Contoh output (bukan solusi untuk contoh input sebelumnya):

28IF5D3EAB9G3

Format output ini juga tidak bisa dinegosiasikan. Seharusnya tidak ada baris baru atau spasi di output, hanya karakter 1- 9dan A- I(karakter huruf kecil dapat diterima sebagai pengganti karakter huruf besar jika Anda mau).

Kisi target (kondisi yang harus Anda buat ulang) adalah sebagai berikut:

Angka 1- angka - 9harus digunakan sebagai instruksi untuk membalikkan baris, dan huruf A- Iharus digunakan untuk kolom. Ini ditunjukkan di bawah ini dengan grid dalam keadaan dipulihkan.

     ABCDEFGHI
     |||||||||
     vvvvvvvvv
1 -> 123456789
2 -> 234567891
3 -> 345678912
4 -> 456789123
5 -> 567891234
6 -> 678912345
7 -> 789123456
8 -> 891234567
9 -> 912345678

Jadi 8cara membalik baris kedua dari bawah, dan Fcara membalik kolom keenam.

Dalam hal tidak ada solusi yang mungkin, program harus berakhir tanpa mengeluarkan apa pun.

Contohnya

Memasukkan:

Keluaran:

Dalam hal ini hanya baris teratas yang perlu dibalik untuk kembali ke status sasaran.

Memasukkan:

Keluaran:

Dalam hal ini hanya kolom akhir (kolom I) yang perlu dibalik untuk membuat ulang kondisi tujuan.

Memasukkan:

Keluaran:

2I

Dalam hal ini kita perlu membalik baris 2dan kemudian membalik kolom Iuntuk kembali ke status sasaran.

Catatan:

Harap sertakan contoh penggunaan dalam jawaban Anda.
Output yang diberikan tidak harus menjadi urutan terpendek yang akan mengembalikan status tujuan - urutan apa pun yang mengembalikan status tujuan akan dilakukan selama ia bekerja (yaitu selama saya bisa mengujinya)
Saya akan berusaha untuk menguji setiap jawaban dan memilih semua yang berhasil dan jelas telah berusaha bermain golf.
Ini adalah kompetisi terbuka - saya akan menerima jawaban terpendek minggu depan, tetapi jika jawaban yang lebih baru berlaku yang lebih pendek di setiap titik di masa depan saya akan mengubah jawaban yang diterima untuk mencerminkan itu .
Bounty telah ditetapkan pada 200 reputasi untuk jawaban terpendek yang diterima pada 23:59:59 (GMT) pada 26/01/2014 Bounty diberikan kepada Howard untuk solusi GolfScript 268 karakternya .

Pengujian

Berikan jawaban program Anda untuk tiga kisi pengujian berikut dengan jawaban Anda:

Saya telah membuat program Python kecil untuk menghasilkan grid yang valid untuk tujuan pengujian:

import random

def output(array):
  print '\n'.join([''.join(row) for row in array])

def fliprow(rownum, array):
  return [row[::1-2*(rownum==idx)] for idx,row in enumerate(array)]

def flipcol(colnum, array):
  return zip(*fliprow(colnum, zip(*array)))

def randomflip(array):
  op=random.randint(0,1)
  row=random.randint(0,9)
  if(op==1):
    return fliprow(row, array)
  else:
    return flipcol(row, array)

def jumble(array):
  arraycopy=array
  for i in range(10, 1000):
    arraycopy=randomflip(arraycopy)
  return arraycopy

startarray=[
['1','2','3','4','5','6','7','8','9'],
['2','3','4','5','6','7','8','9','1'],
['3','4','5','6','7','8','9','1','2'],
['4','5','6','7','8','9','1','2','3'],
['5','6','7','8','9','1','2','3','4'],
['6','7','8','9','1','2','3','4','5'],
['7','8','9','1','2','3','4','5','6'],
['8','9','1','2','3','4','5','6','7'],
['9','1','2','3','4','5','6','7','8']]

print output(jumble(startarray))

code-golf Gareth
sumber

8

Saya baru saja menulis solusi singkat yang secara acak membalik baris / kolom sampai selesai. Setelah 500 juta iterasi masih belum memecahkan puzzle pertama yang Anda berikan (di mana Anda hanya perlu membalikkan baris 1). Keacakan tampaknya tidak menjadi solusi yang dapat digunakan untuk masalah ini!

Josh

3

@Josh Tidak mengejutkan. Masalah ini tampaknya sangat mirip dengan memecahkan kubus rubik. Saya pikir semacam pencarian pertama akan menjadi kekuatan brutal terbaik. Yang sedang berkata, algoritma acak secara teoritis harus berakhir pada akhirnya, dan tampaknya sesuai dengan aturan yang ditentukan.

Cruncher

4

Kekuatan kasar tidak diperlukan. Pertimbangkan fakta bahwa setiap kotak petak hanya dapat berakhir di salah satu dari empat posisi: lokasi yang benar, membalik X, membalik Y, atau membalik XY. Ini dapat membantu Anda untuk memperlakukan mental grid sebagai (0,0) menjadi ubin paling tengah. Jika Anda memecahkan genteng (-2, 4), satu-satunya lokasi target jumlah bisa menjadi adalah (-2, 4), (2, 4), (2, -4), atau (-2, -4).

Tn. Llama

2

@Cruncher: Menggunakan seluruh baris / kolom membalik membuat itu tidak mungkin. Misalnya, coba ambil yang paling atas 1 ( A1) dan pindahkan ke B1. Anda bisa mendapatkan 1ke posisi itu B1, tetapi itu akan menjadi ubin dari B9, bukan ubin dari A1. Karena kita hanya diperbolehkan membalik seluruh baris / kolom, angka 1 paling atas hanya akan berada di salah satu dari empat sudut terluar. Jika saya salah aturan, tolong beri tahu saya.

Tn. Llama

7

Selamat, Gareth. Ini adalah masalah yang dirancang dengan sangat baik. Juga, cukup menantang.

DavidC

7

GolfScript, 300 279 268 karakter

n%`{\5,{.9+}%{;.2/\2%},\;''{1${.9/7+7*+}%+:z;}:?~{{.9<77*{\zip\9-}>:Z~{1$!{-1%}*\(\}@%\Z;}/}:E~{:^;{:c;.`{[\E[.^=\8^-=]{.c=\8c-=}%[^c+^8c-+8^-c+16c-^-]{9%49+}%=}+[[]]:K[[8^- 17c-][^9c+]1$]{:s;{[[]s.+.2$+]{1$+}/}%.&}/\,K+0=z?E}5,/}5,/{{+9%)}+9,%''*}9,%={z:u;}*}+1024,/u

Perhatikan bahwa kode ini sangat lambat (juga karena manipulasi blok-kode yang berat) dan mungkin berjalan beberapa menit. Kode ini sangat un-golfscript-ish dengan banyak variabel dan loop eksplisit.

Saya telah menulis solusi yang lebih analitik yang berjalan kurang dari satu detik. Saya benar-benar mematahkan yang selama golf. Sayangnya, saya tidak dapat mundur atau memperbaiki kode dalam dua hari terakhir. Karenanya, saya membuat versi coba-dan-periksa yang lebih pendek.

Jawaban untuk teka-teki yang diberikan di atas:

1A2C4D9G9G9G9G1C1C1C1C9F9F9F9F1D1D1D1D2A2A2A2A8H8H8H8H2B2B2B2B2C2C8F8F2D2D2D2D3A3A7I7I3B3B7H7H7G7G7G7G3D3D7F7F6I6I6I6I4A4A4A4A6H6H6H6H6G6G4C4C4C4C6F6F4D4D

1AB39I9I1A1A9I9I1B1B9F9F8I8I8I8I2B2B8H8H8G8G8G8G2D2D2D2D3A3A3A3A7H7H7H7H3C3C3C3C3D3D7F7F6I6I4A4A6I6I4B4B4B4B6G6G4C4C4C4C6F6F6F6F4D4D

1A34D9I9I9I9I1A1A1A1A1B1B1B1B9G9G1C1C1C1C9F9F9F9F1D1D9F9F8I8I2A2A2A2A8H8H8H8H2C2C2C2C8F8F2D2D8F8F7I7I7I7I3A3A3B3B7G7G7G7G3C3C3C3C6I6I6I6I6H6H6H6H4B4B4B4B6G6G6G6G4C4C6G6G6F6F4D4D6F6F

Howard
sumber

Yah, ini akan menjadi pekerjaan yang cukup sulit untuk mengalahkan ini ...

Gareth

Sepertinya saya salah ...

Gareth

@ Gareth Saya tahu ini adalah tantangan yang akan sulit dengan skrip golf melawan misalnya Mathematica.

Howard

1

@ Howard - pendekatan apa yang Anda gunakan? Apa itu 'versi coba-dan-periksa' yang Anda sebutkan?

SergeyS

24

Mathematica 582 575 503 464 282

Untuk bertarung dengan penulis naskah golf saya harus menggunakan artileri berat!

i = "986553229
264564891
759176443
643982153
567891234
526917874
685328912
891732537
117644378";

a=Array;h@M_:=Join@@a[9(M〚##〛/. 9->9⌈2Random[]⌉)+Abs[{##}-5]&,n={9,9}];
For[i_~t~j_:=i{#2,10-#2}+j#-9&~a~{9,4},!ListQ[e=GroupElementToWord[
PermutationGroup[Cycles/@Join[1~t~9,9~t~1]],
h[ToCharacterCode@StringSplit@i-48]~FindPermutation~h@a[Mod[8+##,9,1]&,n]]],];
e~IntegerString~36<>""

Keluaran:

g69g69g8g8g7g7gd96d96d8d8d7d7dh6h64a6a46d6d4g4g6b6b7h7h7c7c2a8a27b7bd8db8b7f7fg8g82c2c94a4a3a3aigfdc91

Di sini PermutationGroup[...]mengatur kemungkinan membalik dan GroupElementToWord[...]memecahkan masalah (sekitar 0.2detik). Masalah utama adalah bahwa sulit untuk mengidentifikasi korespondensi antara posisi 9di grid awal dan akhir. Untuk bermain golf saya melakukannya secara acak (butuh beberapa detik). Ada beberapa peringatan tetapi orang bisa mengabaikannya.

Lainnya untuk menguji kisi:

g69g69g8g8g7g7gh89h89h7h7h6h6hf6f6g6g64f4f4h4hg7g73g3g2a8a28d8db8b83d3dg8g82c2c9a3a643a3a2g9f9d9c9ga
h89h89h7h7h6h6h6h6h6f6f6g6g6d6d3a7a37g7g7h7h3c3c2a8a27b7b8d8d2f2f8b8b3f3f2b2ba2a764a8aih9g9c9gb1i

Ini sepenuhnya mereproduksi contoh:

1
i
2i

Solusi sebelumnya (464)

tanpa fungsi bawaan yang pintar dan dengan runtime 4 ms:

M=ToCharacterCode@StringSplit@i-48;
S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;
A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};
u=s/@Join@@A;
H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;
MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

Semua baris baru di sini tidak perlu.

Keluaran:

3b9i9i1a1a1a1a9i9i1a1a9h9h1b1b1b1b9h9h9g9g1c1c9g9g9f9f1d1d9f9f8h8h2b2b8f8f8f8f7i7i7h7h3b3b3b3b7h7h3b3b7h7h7g7g3c3c7g7g3c3c7f7f6i6i4a4a6h6h4b4b4b4b6g6g4c4c6g6g4c4c6f6f4d4d4d4d6f6f4d4d6f6f4d4d

Dua kisi uji lainnya:

13ab9i9i1a1a9i9i9h9h1b1b1b1b9h9h9f9f8i8i8i8i8h8h2b2b2b2b8h8h8h8h8g8g8g8g8f8f2d2d2d2d8f8f2d2d7i7i3a3a3a3a7i7i7h7h3b3b7h7h3b3b7g7g3c3c3c3c7g7g3c3c7f7f3d3d3d3d7f7f7f7f6i6i4a4a6i6i6h6h4b4b4b4b6h6h4b4b6g6g4c4c4c4c6f6f4d4d4d4d6f6f4d4d6f6f
2bc9i9i1a1a9i9i9g9g1c1c9g9g1c1c9f9f1d1d1d1d8i8i8i8i8h8h2b2b2b2b8f8f2d2d7i7i7h7h3b3b3b3b7h7h3b3b7g7g3c3c7f7f3d3d3d3d7f7f3d3d6i6i4a4a4a4a6h6h4b4b6g6g6g6g6f6f4d4d

Visualisasi:

anim = Reap[Fold[Function[{m, i}, 
 If[i > 9, (Sow@Grid[#, Background -> {i - 9 -> Pink, None}] & /@ {m, #}; #) &@
   Transpose@MapAt[Reverse, Transpose@m, i - 9], (Sow@Grid[#, 
         Background -> {None, i -> Pink}] & /@ {m, #}; #) &@
   MapAt[Reverse, m, i]]], M, IntegerDigits[FromDigits[S, 36], 36]]];

ListAnimate[Join[{#, #} &@Grid@M, anim[[2, 1]], {#, #} &@Grid@anim[[1]]], 5]

masukkan deskripsi gambar di sini

String input idapat dihasilkan secara acak oleh

M = Array[Mod[8 + ##, 9, 1] &, {9, 9}];
(M[[#]] = Reverse@M[[#]]; M[[All, #2]] = Reverse@M[[All, #2]];) & @@@
   RandomInteger[{1, 9}, {10000, 2}];
i = ToString /@ # <> "\n" & /@ M <> ""

Diskusi singkat

Membalik hanya dapat menukar elemen-elemen ini ("quadruple"):
Dimungkinkan untuk menukar elemen-elemen ini secara terpisah dari elemen-elemen lain hanya jika urutan awal dan akhir memiliki tanda tangan yang sama.
Membalik keempat elemen ini membentuk kelompok bolak - balik derajat 4 (= kelompok rotasi tetrahedral). Setiap elemen dari grup ini adalah komposisi 2 elemen pembangkit. Jadi jika kita mengetahui posisi awal dan akhir kita dapat menguraikan transformasi yang sesuai sebagai kombinasi dari membalik sederhana.

Detail

Untuk sportif saya memposting rincian sebelum akhir hadiah!

M=ToCharacterCode@StringSplit@i-48;

Konversikan string ike matriks M.

S="";s=Signature;H=(S=S<>{#,#2+9}~IntegerString~36)&;

Kami akan menambahkan karakter ke S. Sekarang ini adalah string kosong. H[i,j]akan menambahkan karakter i( 1,2,3,...,9) dan karakter j( a,b,c,...,idi base-36).

A=(m=M〚##〛)-9Mod[m+##,2]&[s@{2#3,5}#,2#2#3~Mod~2-#2]&~Array~{4,4,4};

Saya mengonversi elemen sebagai

masukkan deskripsi gambar di sini

untuk mendapatkan matriks target dalam bentuk berikut

masukkan deskripsi gambar di sini

Lalu ada dua langkah utama dalam algoritma saya

Temukan flip untuk mendapatkan tanda tangan seperti pada matriks target (mis. Tanda tangan {-7,-1,1,7}is 1dan tanda tangan {-6,2,-2,6}is -1):

u=s/@Join@@A;
H@@({k,l}=#&@@@#~Position~1&/@{v=u〚13;;〛;{h=#2u〚2〛,-#u〚5〛,-#u〚9〛}&@@v,v〚4〛=u〚4〛h;v});
A〚k〛=A〚k,;;,{2,1,3,4}〛;A〚;;,l〛=A〚;;,l,{3,2,1,4}〛;

Putar setiap "empat kali lipat" untuk mendapatkan urutan yang benar:
```
MapIndexed[4#≠#4&&H@@@If[#2<3,#0[#3,#,#2,#4];k,#0[#,#3,#4,#2];10-k]&@@
If[s@#<0,#〚{1,3,2,4}〛,#]&@Ordering[k={#2,#2};#]&,A,{2}];
```
Ini adalah bagian paling tidak trivial dari algoritma. Misalnya, transformasi 1b1bakan dikonversi {-7,-1,1,7}menjadi {-1,1,-7,7}. Transformasi 9h9hakan dikonversi {-7,-1,1,7}menjadi {-7,7,-1,1}. Jadi kami punya dua peta
```
{1,2,3,4} -> {2,3,1,4}
{1,2,3,4} -> {1,4,2,3}
```
dan kami ingin mengonversi pemesanan acak {x,y,z,w}ke {1,2,3,4}. Metode sederhana adalah (kecuali pencarian acak)
```
repeat   
{x, y, z, w} -> If[z < 3, {y, z, x, w}, {x, w, y, z}]
until {1,2,3,4}
```
Saya tidak bisa membuktikannya, tetapi berhasil!

Langkah terakhir adalah

M〚5,1〛<5&&5~H~{};M〚1,5〛<5&&{}~H~5;S

Itu melakukan membalik sepele dari baris tengah dan kolom tengah dan mengembalikan hasilnya.

ybeltukov
sumber

@ Gareth Dapatkah saya menggunakan karakter kecil dalam output? Ini menyelamatkan saya sejumlah karakter.

ybeltukov

Ya, saya akan menerima karakter huruf kecil di output (saya akan mengubah pertanyaan untuk mencatat ini). Saya tidak memiliki Mathematica sehingga dapatkah beberapa pengguna Mathematica lainnya mengkonfirmasi bahwa kode tersebut benar-benar menghasilkan keluaran? Saya telah memvalidasi tiga solusi pengujian dan semuanya benar, jadi +1. Pekerjaan yang baik!

Gareth

Hanya ingin tahu - apa kinerja dari pendekatan Anda? Apakah Anda menguji input yang dihasilkan oleh ribuan flips?

SergeyS

@SergeyS Ya, dibutuhkan sekitar 50 ms :)

ybeltukov

@ Gareth, saya menulis ulang program saya, bisakah Anda memeriksa hasilnya? Tes saya menunjukkan bahwa semuanya benar.

ybeltukov

7

J 487 438

q=:3 :'(>:9|+/~i.9)=/&((,{;/(,.8&-)y){])g'
l=:2 :0
:
o=:o,(m+x){a.
x&(|.@{`[`]})&.v y
)
r=:49 l]
c=:97 l|:
w=:2 :'g=:4 v^:(4=(<m){g)g'
p=:_1=C.!.2@,@:I.@q
t=:2 :'for_i.>:i.3 do.g=:i v^:(p m*i)g end.'
z=:2 :0
'i j I J'=.y,8-y
g=:".'(',(,' ',.,(I.m{q y){,;._1 n),'])^:2 g'
)
d=:3 :0
g=:9 9$".,_ list,' ',.y
o=:''
0 4 w c
4 0 w r
0 1 t c
g=:0 c^:(-.(p 1 0)=p 1 2)g
1 0 t r
for_k.>,{;~i.4 do.0 z';;jcir;irjc;Irjc'k
3 z';;IrJc;JcIr;'k end.o
)

d adalah kata kerja yang mengambil string grid dalam format yang ditentukan dan mengembalikan string solusi dalam format yang ditentukan.

Contoh penggunaan:

   d '987654321',LF,'234567891',LF,'345678912',LF,'456789123',LF,'567891234',LF,'678912345',LF,'789123456',LF,'891234567',LF,'912345678'
bcda2341a1a1b1b1c1c1d1da2a2b2b2c2c2d2d2a3a3b3b3c3c3d3d3a4a4b4b4c4c4d4d4

Sekarang menerima salah satu jenis baris baru.

Solusi untuk kisi uji:

b3a1a11b1bc9c99g9gd9d99f9fb8b8f8f87i7i7h7hc3c3g7g77f7fa6a64b4bh6h6c4c4g6g6d6d6f6f6
cd24a9a91c1c1d1d9f9fa2a2i8i88h8hc2c2g8g82d2d3b3bh7h7d3d37f7fa6a64b4bg6g64d4d6f6f
bc2a9a99i9ic1c1g9g91d1df9f9i8i8b2b2h8h82c2cd8d87i7ib3b3c7c7d3d34a4ai6i6b6b6g6g6d6d6

Saya cukup baru di J; ini mungkin bisa bermain golf lebih jauh.

Memeriksa kisi yang tidak valid / tidak terpecahkan menimbulkan penalti 123 karakter. Saya tidak berpikir jawaban lain sampai saat ini memiliki pengecekan kesalahan tersebut.

Untuk melakukannya, ubah baris pertama dmenjadi ini:

if.-.+./89 90=#y do.0 return.end.if.-.*./(/:~y)=/:~(#y)$'123456789',LF do.0 return.end.g=:9 9$".,_ list,' ',.y

dan baris terakhir untuk ini:

3 z';;IrJc;JcIr;'k end.if.*./,g=>:9|+/~i.9 do.o return.end.0

Saya telah memilih untuk mengembalikan 0kesalahan seperti mengembalikan string kosong tidak dapat dibedakan dengan menyelesaikan kisi yang sepenuhnya terpecahkan. Perhatikan bahwa ini mengasumsikan baris baru UNIX (lagi).

AlliedEnvy
sumber

Selamat, Anda baru saja memimpin. :-)

Gareth

Sepertinya input Anda bukan satu string seperti yang dipersyaratkan oleh aturan, atau saya melewatkan sesuatu?

SergeyS

@SergeyS: Anda mungkin bingung. Sejauh yang saya tahu, J tidak memiliki cara untuk menempatkan pelarian (seperti baris baru) dalam string literal. Konstruksi 'a', LF, 'b' dalam J mirip dengan "a" + "\ n" + "b" dalam bahasa di mana + bekerja untuk menambahkan string.

AlliedEnvy

Oke, itu masuk akal daripada, terima kasih.

SergeyS

Saya baru saja membaca bagian tentang file-file dari buku APL 1962, dan saya pikir @ AlliedEnvy benar. Ini adalah bagaimana data akan muncul ke program jika dibaca dari file dalam format pertanyaan. The LFs mewakili partisi dari file sekuensial.

luser droog

5

C # 540 399

Nah, kinerja yang dikorbankan (sekarang membutuhkan waktu hingga 30 detik), memperkenalkan variabel dinamis, logika solusi yang sedikit berubah. Dan ya, sekarang mengharapkan input sebagai satu string dengan jeda baris (seperti yang disyaratkan dalam aturan).

Tentu saja C # tidak memiliki fungsi matematika yang sudah ditentukan, sehingga akan sulit untuk bertarung dengan Mathematica guys. Namun demikian, ini adalah tantangan besar, terima kasih kepada penulis!

string S(string _){for(i=0,e=1>0;e;){
for(h=v=j=0;j<89;)m[j/10,j%10+9]=_[j++]-49;a="";
for(j=i++;j>0;v++,j/=2)if(j%2>0)F(v);
for(;h<9&(h<4|!e);h+=j/36,j%=36)if((e=m[h,g=j++%9+9]!=(t=(h+g)%9))|m[v=8-h,g]==t){F(v);F(g);F(v);F(g);}
}return a;}void F(int z){for(f=z<9;++l<9;)m[0,l]=m[f?z:l,f?9+l:z];for(;l-->0;)m[f?z:l,f?9+l:z]=m[0,8-l];a+=(char)(z+=f?49:56);}
dynamic h,v,i,j,e,t,l=-1,g,a,m=new int[9,19],f;

Kisi uji:

3B9A9A9B9B9C9C9D9D9F9F9G9G9H9H9I9I9B9B9C9C9D9D9F9F9G9G9H9H9C9C9D9D9C9C9D9D8B8B8F8F8H8H8B8B8F8F8B8B8H8H7B7B7C7C7F7F7H7H7I7I7H7H6A6A6B6B6C6C6D6D6F6F6H6H6A6A6B6B6D6D6F6F6D6D6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

13AB9A9A9B9B9F9F9H9H9A9A9B9B9H9H9I9I8B8B8D8D8F8F8G8G8H8H8I8I8B8B8G8G8H8H8I8I8H8H7A7A7B7B7C7C7D7D7F7F7G7G7I7I7A7A7D7D7F7F7I7I7F7F6A6A6B6B6C6C6D6D6F6F6G6G6H6H6I6I6A6A6C6C6F6F6I6I6A6A6A6A5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

2BC9A9A9C9C9D9D9F9F9A9A9D9D9I9I8B8B8D8D8H8H8I8I8B8B8D8D8I8I7B7B7C7C7D7D7F7F7G7G7H7H7I7I7C7C7C7C7G7G6A6A6B6B6D6D6F6F6G6G6I6I6A6A6B6B6D6D6G6G6D6D6F6F5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I5A5A5B5B5C5C5D5D5E5E5F5F5G5G5H5H5I5I

Solusi Lama (540)

Bekerja kurang dari satu detik pada input apa pun (diuji pada ribuan kisi yang dihasilkan secara acak). Panjang maksimum string output adalah 165 (awalnya semua grid diselesaikan dalam tidak lebih dari 82 membalik, tetapi selama golf saya mengorbankan ini).

string S(string[]_){for(i=0;i<1<<18;){
for(j=0;j<81;)m[j/9+49,j%9+65]=_[j/9][j++%9]-49;a="";char g,h='1',v='9',b,x=h,y;
for(j=i;j>0;x=x==v?'A':++x,j/=2)if(j%2>0)F(x);j=i+1;
for(i+=1<<19;h<58;h++,v--)for(g='A',b='I';g<74;g++,b--){
t=(h+g-6)%9;e=m[h,g];q=m[v,g];i=h>52&t!=e?j:i;
if(e!=t|q==t){x=q==t?v:g;y=q==t?g:v;
if(m[h,b]==t){x=b;y=h;}
F(x);F(y);F(x);F(y);}}}return a;}
void F(char z){var f=z<65;for(l=0;l<4;l++){n=m[d=f?z:49+l,s=f?65+l:z];m[d,s]=m[o=f?z:57-l,u=f?73-l:z];m[o,u]=n;}a+=z;}
int i,j,q,e,t,l,s,d,n,u,o;int[,]m=new int[99,99];string a;

Jawab misalnya 1:

15A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

Jawab misalnya 2:

19AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5D
5DE5E55F5F5G5G5H5H5I5I

Jawab misalnya 3:

129AI1I1H1H1G1G1F1F19F9F9G9G9H9H9I9I8A8AI8I87A7AI7I76A6AI6I65A5A5B5B5C5C5
D5DE5E55F5F5G5G5H5H5I5I

Jawaban untuk kotak tes:

346B9A9AH1H1C9C9D9D99F9F9G9GH9H99I9IB8B8F8F87B7B7C7C7F7FH7H77I7I6A6A6B6BC6C66D6DG6G6H6H66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

1346ABA9A9H1H19F9FH9H99I9IH2H28D8D8F8FG8G8I8I8I3I37B7B7C7CF3F37G7GI7I7H4H4D6D66F6F5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

2BCA9A99C9CF1F19F9F9I9IH2H2D8D88H8HI8I87B7BC7C77D7D7F7F7H7H7I7II4I4B6B6D6D6G6G66I6I5A5A5B5B5C5C5D5DE5E55F5F5G5G5H5H5I5I

Sergey
sumber

Saya hanya mengunduh Mono untuk Mac saya sekarang sehingga saya dapat menguji program itu sendiri, tetapi saya sudah memiliki validator yang menjalankan solusi yang diberikan pada grid yang diberikan dan memberi tahu saya apakah solusi tersebut merupakan solusi yang valid untuk grid itu - dan itu mengatakan kepada saya bahwa tiga contoh solusi yang Anda berikan kepada saya tidak valid. Saya hanya menyelidiki mengapa sekarang.

Gareth

Aha! Saya sudah tahu apa yang terjadi di sini! Jawaban Anda yang diberikan tampaknya adalah jawaban untuk 3 contoh dan bukan tiga kisi uji (yang lebih rendah di pertanyaan). Mereka memang solusi yang tepat untuk kisi-kisi itu, meskipun mereka sedikit lebih lama dari 1,, Adan 2Iyang merupakan solusi paling sederhana - tetapi itu sebenarnya tidak masalah karena saya tidak menilai panjang solusi kisi :-) Jika Anda bisa mengedit dan berikan jawaban untuk 3 kisi pengujian (saya akan melihat apakah saya bisa menjalankan ini di Mac saya sekarang) saya bisa memberi Anda +1 Anda.

Gareth

@ Gareth - oops, saya tidak terjawab jawaban untuk kotak tes, terima kasih telah menunjukkan itu. Saya telah menambahkannya sekarang ke jawaban saya.

SergeyS

Luar biasa, terima kasih untuk itu. Mereka semua divalidasi baik-baik saja. Xamarin tidak akan berjalan di Mac saya untuk beberapa alasan, jadi saya harus menguji program di tempat kerja dalam beberapa jam.

Gareth

@ Gareth - Sebenarnya tidak ada yang spesifik untuk C # dalam kode itu, orang mungkin dapat mengubahnya ke Jawa atau bahkan C ++ tanpa banyak rasa sakit dan ... golf beberapa karakter dari itu :) Juga merasa bebas untuk mengubahnya ke GolfScript atau sesuatu yang lebih ringkas - ini mungkin muncul dua kali atau lebih pendek;)

SergeyS

Kotak Flippin '

Jawaban:

GolfScript, 300 279 268 karakter

Mathematica 582 575 503 464 282

Solusi sebelumnya (464)

Diskusi singkat

Detail

J 487 438

C # 540 399

Solusi Lama (540)