14
\$\begingroup\$

Task

Given a ASCII diagram of a loop

e.g.

....................
......@@@@@.........
......@...@.........
.....@@...@@@@@.....
....@@........@.....
....@........@@.....
....@@@@@@@@@@......
....................
....................

And a location on the loop

e.g.

(7,1)

You must find the inside and outside of the loop

e.g.

00000000000000000000
00000011111000000000
00000011111000000000
00000111111111100000
00001111111111100000
00001111111111100000
00001111111111000000
00000000000000000000
00000000000000000000

Specifications

  • You may take input for the diagram as a string separated by newlines or obvious equivalent

  • You will receive a coordinate on the loop (0 or 1 indexed) as part of your input. You may place your origin at any place you wish. You may take this coordinate in (<row>, <column>), (<column>, <row>) or as the linear position on the string. You may receive these data in any reasonable method. All characters on the loop will be the same as the character at that index.

  • Preferred output is a 2 dimensional array of truthy and falsy values, however strings of 1 and 0 separated by newlines or any obvious equivalent of the later two are accepted. The inside and outside must have different truth values but it does not matter which is which.

  • A loop is defined as a group of characters such that they are all the same character (e.g. @) and so that every character in the loop has a path to the original character (The character at the coordinate of input) that only passes through that same character (Taxicab geometry No diagonals).

  • The inside is all the loop itself and the places that cannot reach the edge of the diagram without crossing the loop.

  • The outside is everywhere else

  • This is

Test Cases

PasteBin

\$\endgroup\$
  • \$\begingroup\$ Can we also take the coordinates as linear coordinate in the string? \$\endgroup\$ – flawr Jan 17 '17 at 16:15
  • \$\begingroup\$ @flawr You may. \$\endgroup\$ – Sriotchilism O'Zaic Jan 17 '17 at 16:16
  • \$\begingroup\$ Are we allowed to take the diagram as a matrix of characters, sth. like [['.', '.'],['.', '@']] instead of a string with newlines? \$\endgroup\$ – hbaderts Jan 17 '17 at 16:19
  • \$\begingroup\$ @hbaderts That is an obvious equivalent \$\endgroup\$ – Sriotchilism O'Zaic Jan 17 '17 at 16:20
  • 1
    \$\begingroup\$ @WheatWizard Thanks for the additional test case! I would however recommend to put them into a snippet or in a gist / pastebin, in order to make the challenge a bit more decluttered=) \$\endgroup\$ – flawr Jan 17 '17 at 21:41
6
\$\begingroup\$

MATLAB, 163 159 146 78 bytes

function m=f(m,y,x);[~,i]=bwfill(m~=m(y,x),x,y,8);m=m*0;m(i)=1;m=bwfill(m,'h')

Thanks @rahnema1 for -66 bytes!!!

Now it does work on Try it online! BUT a few adjustments were needed, as MATLAB and Octave are not entirely compatible.

Explanation

First we make a binary image that just masks all the characters that are equal to the initial character. Then we determine the connected component the initial character is in.

% determine the connected component that is contains initial character

[~,i]=bwfill(m~=m(y,x),x,y,8);     % i contains the indices of the connected component
m=m*0;m(i)=1;                      % create an image of the connected component

After that we create an image of that connected component and apply fill all the "holes" in the image.

m=bwfill(m,'h')
\$\endgroup\$
  • \$\begingroup\$ I think for golfing Octave is better so you may reduce it to at least 72 bytes \$\endgroup\$ – rahnema1 Jan 17 '17 at 22:23
  • \$\begingroup\$ @rahnema1 I already started in MATLAB, so I'm not gonna change this submission now, but thanks for the suggestion=) \$\endgroup\$ – flawr Jan 17 '17 at 22:28
5
\$\begingroup\$

MATLAB: 67 bytes

function A=f(A,r,c),A=bwlabel(A==A(r,c),4);A=imfill(A==A(r,c),'h');

A couple caveats:

  • A is assumed to be a character array.
  • Indices in MATLAB are 1-based, with rows indexed first. It is assumed these changes would be made to the function input (i.e. the question example would be called as output = f(A,2,8)).
  • bwlabel and imfill are part of the Image Processing Toolbox.
\$\endgroup\$
  • 1
    \$\begingroup\$ welcome to codegolf! \$\endgroup\$ – rahnema1 Jan 17 '17 at 22:46
  • \$\begingroup\$ @rahnema1: Amazed I didn't visit sooner, since I did some golfing on SO before this site was born. \$\endgroup\$ – gnovice Jan 17 '17 at 22:48

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.