# Clean the muddy quartata-fish

This challenge is in honor of the Rookie of the Year category winners of Best of PPCG 2015: muddyfish (for I'm not the language you're looking for!) and quartata (for Implement a Truth-Machine). Congratulations!

## Background

In the deepest trenches of the ocean, there lives a rare and elusive square-shaped fish called the quartata-fish. It looks like the glider from the Game of Life cellular automaton. Here are two quartata-fish of different sizes:

-o-
--o
ooo

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


You have managed to snap a photo of the quartata-fish, but the fish is rather hard to see since it's covered in mud. Now you'll have to write a program to clean up the photo.

## Input

Your input is a rectangular 2D grid of the characters .-o#, given as a newline-separated string. If you want, you can use pipes | instead of newlines as the separators, and you may assume one trailing and/or preceding separator.

The input will contain exactly one quartata-fish of some side-length 3*n, where n ≥ 1 is a positive integer, surrounded by periods . that represent the ocean floor. The fish will always be in the orientation depicted above. Overlaid on this grid, there will be exactly one non-empty rectangular region of hashes #, which represents a blob of mud. The blob may cover the quartata-fish partially or entirely. An example input would be

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


## Output

Your output shall be generated from the input by replacing all the hashes with the characters .-o, so that the grid contains exactly one quartata-fish. There will always be a unique way to perform this replacement properly; in particular, the blob of mud will cover the fish entirely only if its size is 3×3. The output shall use the same separator as the input. For the above input, the correct output would be

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


## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time bounds: if your submission would eventually halt given unlimited time and resources, you're fine.

## Test cases

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.........
.........................

• Is it ok if the entry has a probability it won't finish (bad randomness) even though the chances of that are extremely low? Also are you allowed to change characters other than the single newline-pipe? – Blue Apr 3 '16 at 20:07
• @muddyfish Yes to first question (it must eventually finish with probability 1, assuming perfect randomness, but may theoretically run forever), no to second (the characters are fixed). – Zgarb Apr 3 '16 at 20:21
• so is a probability of 0.9 recurring ok? – Blue Apr 3 '16 at 20:23
• @muddyfish If you're generating random grids in a loop until one fits, that's ok. – Zgarb Apr 3 '16 at 21:05
• Important test case: ......|......|......|...###|...###|...### (in case a solution tries all possible top-left coordinates, and tries to fit a 6x6 over the area) – Sp3000 Apr 4 '16 at 6:41

## Python 2, 433 411 bytes

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


Exits with a NameError. Takes input pipe separated.

I'm mixing tabs and spaces here. SE doesn't render tabs properly.

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

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

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


(Note extra spaces at the start are for prettiness only and aren't actually printed)

• You can get rid of the extra tabs in your code and replace them with single spaces to cut down on a few bytes (that is, if you took the white space into consideration when counting the bytes in your code). – R. Kap Apr 4 '16 at 4:22

# JavaScript (ES6), 291 bytes

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


## Explanation

Takes input grid as a newline separated string. Not completely golfed, will do more when I get time.

It works by:

• Getting every possible position and size of a fish in the bounds of the input grid.
• For each position/size, it builds a grid string with a fish in that position.
• Checks if this is the correct output by iterating over every character. If each character either matches or is a hash, it outputs the built string.

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>

## Python 2, 325 bytes

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


A badly golfed solution for now – the for .. in range(...)s are an utter train wreck. Inputs/outputs newline separated strings.

The byte count currently assumes space indents only – I'll switch to mixed tabs/spaces later when I'm done golfing, if necessary.