27
\$\begingroup\$

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.........
.........................
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Blue Apr 3 '16 at 20:07
  • \$\begingroup\$ @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). \$\endgroup\$ – Zgarb Apr 3 '16 at 20:21
  • \$\begingroup\$ so is a probability of 0.9 recurring ok? \$\endgroup\$ – Blue Apr 3 '16 at 20:23
  • \$\begingroup\$ @muddyfish If you're generating random grids in a loop until one fits, that's ok. \$\endgroup\$ – Zgarb Apr 3 '16 at 21:05
  • \$\begingroup\$ Important test case: ......|......|......|...###|...###|...### (in case a solution tries all possible top-left coordinates, and tries to fit a 6x6 over the area) \$\endgroup\$ – Sp3000 Apr 4 '16 at 6:41
9
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – R. Kap Apr 4 '16 at 4:22
4
\$\begingroup\$

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>

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.