Oczyść błotniste ryby quartata

To wyzwanie jest na cześć zwycięzców kategorii Rookie of the Year w konkursie Best of PPCG 2015 : muddyfish (bo nie jestem językiem, którego szukasz! ) I quartata (za Implementowanie maszyny prawdy ). Gratulacje!

tło

W najgłębszych okopach oceanu żyje rzadka i nieuchwytna ryba w kształcie kwadratu zwana quartata-fish . Wygląda jak szybowiec z automatu komórkowego Game of Life. Oto dwie ryby quartata o różnych rozmiarach:

-o-
--o
ooo

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

Udało ci się zrobić zdjęcie kwarty-ryby, ale ryba jest raczej trudna do zobaczenia, ponieważ jest pokryta błotem. Teraz musisz napisać program do czyszczenia zdjęcia.

Wkład

Twoje dane wejściowe to prostokątna siatka 2D znaków .-o#, podana jako ciąg oddzielony znakiem nowej linii. Jeśli chcesz, możesz użyć potoków |zamiast nowych linii jako separatorów i możesz założyć jeden separator końcowy i / lub poprzedni.

Dane wejściowe będą zawierały dokładnie jedną ćwiartkę-rybę o pewnej długości boku 3*n, gdzie n ≥ 1jest liczbą całkowitą dodatnią, otoczoną okresami .reprezentującymi dno oceanu. Ryba zawsze będzie miała orientację przedstawioną powyżej. Na tej siatce zostanie nałożony dokładnie jeden niepusty prostokątny obszar skrótów #, który reprezentuje kroplę błota. Kropla może częściowo lub całkowicie pokryć quartata-fish. Przykładem może być

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

Wydajność

Twój wynik będzie generowany z danych wejściowych poprzez zastąpienie wszystkich .-oskrótów znakami , tak aby siatka zawierała dokładnie jedną rybę quartata. Zawsze będzie istniał unikalny sposób prawidłowego wykonania tej zamiany; w szczególności kropla błota całkowicie przykryje rybę tylko wtedy, gdy jej rozmiar wynosi 3 × 3. Wyjście powinno używać tego samego separatora co wejście. Dla powyższego wejścia, poprawne wyjście byłoby

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

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma żadnych ograniczeń czasowych: jeśli Twoje zgłoszenie ostatecznie zostanie zatrzymane, biorąc pod uwagę nieograniczony czas i zasoby, nic ci nie jest.

Przypadki testowe

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
źródło

Czy jest ok, jeśli istnieje prawdopodobieństwo, że wpis nie zakończy się (zła losowość), mimo że szanse na to są bardzo niskie? Czy możesz także zmieniać znaki inne niż pojedynczy znak nowej linii?

— Niebieski

@muddyfish Tak, aby odpowiedzieć na pierwsze pytanie (musi ostatecznie zakończyć się prawdopodobieństwem 1, zakładając idealną losowość, ale teoretycznie może trwać wiecznie), nie na sekundę (znaki są ustalone).

— Zgarb

więc czy prawdopodobieństwo powtórzenia się 0,9 jest w porządku?

— Niebieski

@muddyfish Jeśli generujesz losowe siatki w pętli, aż jedna pasuje, to nic nie szkodzi.

— Zgarb

Ważny sprawdzian: ......|......|......|...###|...###|...###(w przypadku, gdy rozwiązanie próbuje wszystkich możliwych współrzędne lewego górnego i próbuje dopasować 6x6 nad obszarem)

— SP3000

Odpowiedzi:

Python 2, 433 411 bajtów

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);_

Wychodzi z NameError. Oddziela rurę wejściową.

Mieszam tutaj tabulatory i spacje. SE nie wyświetla poprawnie kart.

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

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

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

(Uwaga: dodatkowe spacje na początku są tylko dla ładności i nie są w rzeczywistości drukowane)

— niebieski
źródło

Możesz pozbyć się dodatkowych zakładek w kodzie i zastąpić je pojedynczymi spacjami, aby zmniejszyć liczbę bajtów (to znaczy, jeśli weźmiesz pod uwagę białe znaki przy liczeniu bajtów w kodzie).

— R. Kap

JavaScript (ES6), 291 bajtów

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')

Wyjaśnienie

Pobiera siatkę wejściową jako ciąg rozdzielany znakiem nowej linii. Nie do końca gra w golfa, zrobi więcej, gdy będę miał czas.

Działa przez:

Uzyskanie każdej możliwej pozycji i wielkości ryby w granicach siatki wejściowej.
Dla każdej pozycji / rozmiaru buduje łańcuch siatki z rybą w tej pozycji.
Sprawdza, czy jest to poprawny wynik, iterując każdą postać. Jeśli każdy znak pasuje lub jest skrótem, generuje ciąg znaków.

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>

Rozwiń fragment kodu

— użytkownik 81655
źródło

Python 2, 325 bajtów

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('#','.')

Na razie źle gra w golfa - for .. in range(...)są wrakiem kompletnego pociągu. Wejścia / wyjścia łańcuchy rozdzielone znakiem nowej linii.

Liczba bajtów obecnie zakłada tylko wcięcia spacji - w razie potrzeby zmienię tabulatory / spacje później, kiedy skończę grać w golfa.

— Sp3000
źródło