Bersihkan ikan quartata yang berlumpur

27

Tantangan ini untuk menghormati pemenang kategori Rookie of the Year dari Best of PPCG 2015 : muddyfish (karena saya bukan bahasa yang Anda cari! ) Dan quartata (untuk Implementasikan Mesin Kebenaran ). Selamat!

Latar Belakang

Di parit terdalam samudera, hiduplah seekor ikan berbentuk persegi yang langka dan sulit ditangkap yang disebut ikan quartata . Itu seperti peluncur dari Game of Life, otomat seluler. Berikut adalah dua ikan quartata dengan ukuran berbeda:

-o-
--o
ooo

--oo--
--oo--
----oo
----oo
oooooo
oooooo

Anda telah berhasil mengambil foto ikan quartata, tetapi ikannya agak sulit dilihat karena tertutup lumpur. Sekarang Anda harus menulis sebuah program untuk membersihkan foto.

Memasukkan

Input Anda adalah kotak 2D persegi panjang karakter .-o#, diberikan sebagai string yang dipisahkan baris baru. Jika Anda mau, Anda bisa menggunakan pipa |daripada baris baru sebagai pemisah, dan Anda dapat mengasumsikan satu trailing dan / atau pemisah sebelumnya.

Input akan berisi persis satu quartata-fish dengan panjang sisi tertentu 3*n, di mana n ≥ 1bilangan bulat positif, dikelilingi oleh periode .yang mewakili dasar laut. Ikan akan selalu dalam orientasi yang digambarkan di atas. Overlay pada grid ini, akan ada persis satu wilayah hash persegi panjang yang tidak kosong #, yang mewakili gumpalan lumpur. Gumpalan dapat menutupi ikan quartata sebagian atau seluruhnya. Contoh input akan menjadi

............
..--oo--....
..--oo--....
..---#####..
..---#####..
..ooo#####..
..oooooo....

Keluaran

Output Anda akan dihasilkan dari input dengan mengganti semua hash dengan karakter .-o, sehingga kisi-kisi berisi persis satu quartata-fish. Akan selalu ada cara unik untuk melakukan penggantian ini dengan benar; khususnya, gumpalan lumpur akan menutupi ikan sepenuhnya hanya jika ukurannya 3x3. Keluaran harus menggunakan pemisah yang sama dengan input. Untuk input di atas, output yang benar adalah

............
..--oo--....
..--oo--....
..----oo....
..----oo....
..oooooo....
..oooooo....

Aturan dan penilaian

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Tidak ada batasan waktu: jika kiriman Anda pada akhirnya akan berhenti karena waktu dan sumber daya yang tidak terbatas, Anda baik-baik saja.

Uji kasus

Input:
.......
...-o-.
...--o.
##.ooo.
##.....
Output:
.......
...-o-.
...--o.
...ooo.
.......

Input:
...-o-.
...-#o.
...ooo.
.......
Output:
...-o-.
...--o.
...ooo.
.......

Input:
.........
.###.....
.###.....
.ooo.....
Output:
.........
.-o-.....
.--o.....
.ooo.....

Input:
.....
.###.
.###.
.###.
Output:
.....
.-o-.
.--o.
.ooo.

Input:
......
......
......
...###
...###
...###
Output:
......
......
......
...-o-
...--o
...ooo

Input:
###o--....
###o--....
###-oo....
###-oo....
###ooo....
###ooo....
###.......
Output:
--oo--....
--oo--....
----oo....
----oo....
oooooo....
oooooo....
..........

Input:
............
..--oo--....
..--oo--....
..---#####..
..---#####..
..ooo#####..
..oooooo....
Output:
............
..--oo--....
..--oo--....
..----oo....
..----oo....
..oooooo....
..oooooo....

Input:
...--oo--....
.#########...
.#########...
.#########...
...oooooo....
...oooooo....
.............
.............
Output:
...--oo--....
...--oo--....
...----oo....
...----oo....
...oooooo....
...oooooo....
.............
.............

Input:
..............
..............
.########.....
.########.....
.########-....
.########-....
.########o....
.########o....
.########o....
.########o....
.########.....
..............
Output:
..............
..............
..............
..............
....--oo--....
....--oo--....
....----oo....
....----oo....
....oooooo....
....oooooo....
..............
..............

Input:
.................
.................
..---ooo---......
..--#########....
..--#########....
..--#########....
..--#########....
..--#########....
..oo#########....
..oo#########....
..oo#########....
....#########....
Output:
.................
.................
..---ooo---......
..---ooo---......
..---ooo---......
..------ooo......
..------ooo......
..------ooo......
..ooooooooo......
..ooooooooo......
..ooooooooo......
.................

Input:
.........................
.........................
....----oooo----.........
....----########.........
....----########.........
....----########.........
....----########.........
....----########.........
....----########.........
....----########.........
....oooo########.........
....oooo########.........
....oooooooooooo.........
....oooooooooooo.........
.........................
Output:
.........................
.........................
....----oooo----.........
....----oooo----.........
....----oooo----.........
....----oooo----.........
....--------oooo.........
....--------oooo.........
....--------oooo.........
....--------oooo.........
....oooooooooooo.........
....oooooooooooo.........
....oooooooooooo.........
....oooooooooooo.........
.........................
code-golf ascii-art grid Zgarb
sumber
Apakah boleh jika entri memiliki probabilitas tidak akan selesai (keacakan yang buruk) meskipun peluangnya sangat rendah? Anda juga dapat mengubah karakter selain dari pipa baris tunggal?
Biru
@muddyfish Ya untuk pertanyaan pertama (pada akhirnya harus diselesaikan dengan probabilitas 1, dengan asumsi keacakan sempurna, tetapi secara teoritis dapat berjalan selamanya), tidak ke kedua (karakter diperbaiki).
Zgarb
jadi apakah probabilitas 0,9 berulang ok?
Biru
@muddyfish Jika Anda membuat grid acak dalam satu lingkaran sampai satu cocok, tidak apa-apa.
Zgarb
Kasing uji penting: ......|......|......|...###|...###|...###(jika suatu solusi mencoba semua koordinat kiri-atas yang memungkinkan, dan mencoba memasukkan 6x6 pada area)
Sp3000

Jawaban:

9

Python 2, 433 411 byte

import re;i,o,l,j=input(),range,lambda s,r:s.replace(*r),"".join;i=l(l(l(i,".1"),"#."),"| ");s=o(len(i))
for x in s:
 for y in s:
    for q in s:
     r=map(list,l(l(i,"o."),"-.").split(" "))
     try:
        for v in o(q):r[x+v][y:y+q]=["".join(c*(q/3)for c in b)for b in["-o-","--o","ooo"]][3*v/q]
        m=re.match(i," ".join(j(i)for i in r))
     except:0
     if sum("-"in p for p in r)and m:print"|".join(l(j(i),"1.")for i in r);_

Keluar dengan a NameError. Membagi pipa input.

Saya mencampur tab dan spasi di sini. SE tidak membuat tab dengan benar.

'###o--....|###o--....|###-oo....|###-oo....|###ooo....|###ooo....|###.......'
 --oo--....|--oo--....|----oo....|----oo....|oooooo....|oooooo....|..........

'.....|.###.|.###.|.###.'
 .....|.-o-.|.--o.|.ooo.

'...-o-.|...-#o.|...ooo.|.......'
 ...-o-.|...--o.|...ooo.|.......

(Perhatikan ruang ekstra di awal hanya untuk kecantikan dan tidak dicetak)

Biru
sumber
Anda dapat menyingkirkan tab tambahan dalam kode Anda dan menggantinya dengan spasi tunggal untuk mengurangi beberapa byte (yaitu, jika Anda mempertimbangkan ruang putih saat menghitung byte dalam kode Anda).
R. Kap
4

JavaScript (ES6), 291 byte

g=>eval('w=g.search`\n`;h=g.length/w|0;for(n=(w<h?w:h)/3|0;s=n*3;n--)for(x=w+1-s;x--;)for(y=h+1-s;y--;[...g].every((c,i)=>c==o[i]|c=="#")?z=p:0)for(p="",i=h;i--;)p=(l=[,"-o-","--o","ooo"][(i-y)/n+1|0],l?"."[t="repeat"](x)+l.replace(/./g,c=>c[t](n))+"."[t](w-x-s):"."[t](w))+(p?`\n`:"")+p;z')

Penjelasan

Mengambil kisi masukan sebagai string yang dipisahkan baris baru. Tidak sepenuhnya golf, akan berbuat lebih banyak ketika saya punya waktu.

Ini bekerja dengan:

  • Dapatkan setiap posisi dan ukuran ikan yang mungkin dalam batas-batas kisi masukan.
  • Untuk setiap posisi / ukuran, itu membangun string grid dengan ikan di posisi itu.
  • Periksa apakah ini adalah output yang benar dengan mengulangi setiap karakter. Jika setiap karakter cocok atau hash, itu menghasilkan string yang dibangun.

var solution =

g=>
  eval(`

    // Get size of input grid
    w=g.search\`\n\`;
    h=g.length/w|0;

    // Check every possible size (n) and position (x and y) of fish
    for(n=(w<h?w:h)/3|0;s=n*3;n--)
      for(x=w+1-s;x--;)
        for(y=h+1-s;y--;

          // Check if possible solution matches input grid
          [...g].every((c,i)=>c==p[i]|c=="#")?z=p:0
        )

          // Create possible solution grid
          for(p="",i=h;i--;)
            p=(
              l=[,"-o-","--o","ooo"][(i-y)/n+1|0],
              l?
                "."[t="repeat"](x)+
                l.replace(/./g,c=>c[t](n))+
                "."[t](w-x-s)
              :"."[t](w)
            )+(p?\`\n\`:"")+p;
    z
  `)
<textarea id="input" rows="6" cols="40">..............
..............
.########.....
.########.....
.########-....
.########-....
.########o....
.########o....
.########o....
.########o....
.########.....
..............</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
Luaskan cuplikan

pengguna81655
sumber
4

Python 2, 325 byte

def f(s):
 s=map(list,s.split());R=range;L=len(s);M=len(s[0])
 for h in R(L/3*3,0,-3):
  for x in R(M-h+1):
   for y in R(L-h+1):
    if all(s[v%L][v/L]in".-#o #"[0<=v%L-y<h>v/L-x>=0::2]for v in R(L*M)):
     for k in R(h*h):s[y+k/h][x+k%h]="-o"[482>>k/h*3/h*3+k%h*3/h&1]
     return'\n'.join(map(''.join,s)).replace('#','.')

Solusi golf buruk untuk saat ini - ini for .. in range(...)adalah kecelakaan kereta api total. Input / output string yang dipisahkan baris baru.

Hitungan byte saat ini mengasumsikan hanya ruang indentasi - saya akan beralih ke tab / spasi campuran nanti ketika saya selesai bermain golf, jika perlu.

Sp3000
sumber