# Highlight the Bounding Box, Part II: Hexagonal Grid

You're given a hexagonal grid of the characters . and #, like this:

 . . . . . . . .
. . . . # . . .
. # . . . # . .
. . . # . . . .
. . . . . # . .
. . . . . . . .


Your task is to fill the entire axis-aligned bounding box of the # with further #:

 . . . . . . . .
. . # # # # . .
. # # # # # . .
. . # # # # # .
. . # # # # . .
. . . . . . . .


The axis-aligned bounding box is the smallest convex hexagonal shape which contains all the #. Note that in the case of the hexagonal grid, there are three axes to consider (W/E, SW/NE, NW/SE):

Here is another example to show that in some cases, one or more sides will contain only one #:

. . . . . . . .         . . . . . . . .
. # . . . . . .         . # # # # . . .
. . . . . # . .         . . # # # # . .
. . # . . . . .         . . # # # . . .
. . . . . . . .         . . . . . . . .


You can either view these as hexagons with degenerate sides, or you can draw the bounding box around them, like I have done above, in which case they are still hexagons:

Too hard? Try Part I!

## Rules

You may use any two distinct non-space printable ASCII characters (0x21 to 0x7E, inclusive), in place of # and .. I'll continue referring to them as # and . for the remainder of the specification though.

Input and output may either be a single linefeed-separated string or a list of strings (one for each line), but the format has to be consistent.

You may assume that the input contains at least one # and all lines are the same length. Note that there are two different "kinds" of lines (starting with a space or a non-space) - you may not assume that the input always starts with the same type. You may assume that the bounding box always fits inside the grid you are given.

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

## Test Cases

Each test case has input and output next to each other.

#    #

. .      . .
# . #    # # #
. .      . .

. #      . #
. . .    . # .
# .      # .

# .      # .
. . .    . # .
. #      . #

# .      # .
# . .    # # .
. #      # #

. #      # #
# . .    # # #
. #      # #

. . #    . # #
. .      # #
# . .    # # .

# . .    # # .
. .      # #
. . #    . # #

. . . . . . . .         . . . . . . . .
. . # . # . . .         . . # # # . . .
. . . . . . . .         . . . # # . . .
. . . # . . . .         . . . # . . . .

. . . . . . . .         . . . . . . . .
. . # . . . # .         . . # # # # # .
. . . . . . . .         . . . # # # # .
. . . # . . . .         . . . # # # . .

. . . . . . . .         . . . . . . . .
. # . . . . . .         . # # # # . . .
. . . . . # . .         . . # # # # . .
. . . . . . . .         . . . . . . . .

. . . . . . . .         . . . . . . . .
. # . . . . . .         . # # # # . . .
. . . . . # . .         . . # # # # . .
. . # . . . . .         . . # # # . . .

. . . . # . . .         . . # # # # . .
. # . . . # . .         . # # # # # . .
. . . # . . . .         . . # # # # # .
. . . . . # . .         . . # # # # . .

• My head is spinning trying to find any obvious pattern. You said 'hexagonal' but there are only two inputs form into hexagons in the test cases. I'm lost. Commented Aug 29, 2016 at 12:04
• @Anastasiya-Romanova秀 If you picture the shape as going through the centres of the outer characters, then yes some hexagons will have degenerate sides (like in the rectangular grid, where you can get cases where the rectangle reduces to a line). However, if you draw the rectangle around the characters (as I have done in the diagram), all the examples are hexagons (some of which have very short sides). Commented Aug 29, 2016 at 12:06
• @Anastasiya-Romanova秀 Does the new diagram help? Commented Aug 29, 2016 at 12:13
• I! looks like II if I have the wrong glasses on..
– Neil
Commented Aug 29, 2016 at 12:17
• @Neil Or, you know, too much alcohol ;) Commented Aug 29, 2016 at 12:35

# Pyth, 82 71 bytes

L,hbebMqH@S+GH1KhMyJs.e,Lkfq\#@bTUb.zA,ySm-FdJySsMJj.es.eXW&&gKkgG-kYgH+kYZ\.\#b.z
MqH@S[hGHeG)1j.es.eXW&&ghMJs.e,Lkfq\#@bTUb.zkgSm-FdJ-kYgSsMJ+kYZ\.\#b.z


Try it online!

### Explanation

• Let A be the point with the lowest y-coordinate and B the point with the highest y-coordinate.

• Let C be the point with the lowest (x-value minus y-value) and D the point with the highest.

• Let E be the point with the lowest (x-value plus y-value) and F the point with the highest.

Then it is equivalent to finding the coordinates which the y-coordinate is between A and B, the x-value minus y-value is between C and D, and the x-value plus y-value is between E and F.

• the first time when I could post a solution earlier, if only the SE android app could correctly handle tab characters (for some reason they disappeared when pasted) :/ Commented Aug 29, 2016 at 15:35
• @SargeBorsch I'm sorry :( Commented Aug 29, 2016 at 15:41
• haha why, it's SE Android app that made me fail :D Commented Aug 29, 2016 at 15:52

## Haskell, 256 254 243 bytes

import Data.List
f=z(\l->(,).(,))[0..]l)[0..]
q l=m(m(\e->min(snd e).(".#"!!).fromEnum.and.z($)(m(\x y->y>=minimum x&&y<=maximum x).transpose.m b.filter((==)'#'.snd).concat$l)$b e))l b=(m uncurry[const,(-),(+)]<*>).pure.fst z=zipWith m=map q.f  Thanks @Damien for golfing f! Input is taken as list of list of chars, output is provided the same way. Soo this was a beast to write. It's based on LeakyNun's idea using a maximum and minimum based filtering on the coordinates of the items. I'm really surprised by the fact that m=map actually saves bytes since it seems so costly. Explanation: Here's a slightly less butchered version (emphasis on slightly): import Data.List f=zipWith(\y l->zipWith(\x e->((y,x),e))[0..]l)[0..] p=map(\x y->y>=minimum x&&y<=maximum x).transpose.map b.filter((==)'#'.snd).concat q l=map(map(\e->min(snd e).(".#"!!).fromEnum.and.zipWith($)(p$l)$b e))l
b=(map uncurry[const,(-),(+)]<*>).pure.fst

• f is a function which assigns each char an index (y-index, x-index) while preserving the original structure of the list.

• b: Given an item of the indexed list, b computes [y-index, y - x, y + x].

• p: Given the indexed field, return 3 functions Int -> Bool, the first of which is the check of the y-index, the second of the difference and the third of the sum. min(snd e) takes care of the spaces (a space is smaller than both). This function is inlined in the golfed code.

• q given the indexed field, change all necessary . to # by checking if that specific field return True to every test function.

The final solution is then the composition of q and f.

• f=z(\y->z((,).(,)y)[0..])[0..] Commented Sep 1, 2016 at 7:06
• or h x=z x[0..] f=h$h.curry(,) Commented Sep 1, 2016 at 7:22 # Jelly, 45351342 41 bytes Ṁ€»\ ṚÇṚ«Çṁ" ŒDṙZL$ÇṙL’$ŒḌ«Ç ṚÇṚ«Ç n⁶aÇo⁶  This is a list of links; the last one has to be called on the input to produce the output. I/O is in form of string arrays, where . indicates empty and @ indicates filled. ### Background Let's consider the following example. . . . . . . . . . @ . . . . . . . . . . . @ . . . . @ . . . . .  By drawing a pair or parallel lines – the closest pair that encloses all filled positions – in each of the three directions, we can determine the hexagonal bounding box. In the implementation, we replace all characters between those two lines with @, and everything outside these lines with ., with the possible exception of diagonals that only contains spaces). For the horizontal axis, this gives ................ @@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@  for the falling diagonal axis, it gives ..@@@@@@@...... ...@@@@@@@...... ....@@@@@@@..... ....@@@@@@@....  and for the raising diagonal axis, it gives ....@@@@@@@@@... ...@@@@@@@@@.... ..@@@@@@@@@.... .@@@@@@@@@.... .  By taking the character-wise minimum of all three, since . < @, we get ............... ...@@@@@@@...... ....@@@@@@@.... ....@@@@@.... .  All that's left to do is restoring the spaces. ### How it works n⁶aÇo⁶ Main link. Argument: A (array of strings) n⁶ Not-equal space; yield 0 for spaces, 1 otherwise. aÇ Take the logical AND with the result the 4th helper link. This will replace 1's (corresponding to non-space characters) with the corresponding character that result from calling the link. o⁶ Logical OR with space; replaces the 0's with spaces.  ṚÇṚ«Ç 4th helper link. Argument: A Ṛ Reverse the order of the strings in A. Ç Call the 3rd helper link. Ṛ Reverse the order of the strings in the resulting array. Ç Call the 3rd helper link with argument A (unmodified). « Take the character-wise minimum of both results.  ŒDṙZL$ÇṙL’$ŒḌ«Ç 3rd helper link. Argument: L (array of strings) ŒD Yield all falling diagonals of L. This is a reversible operation, so it begins with the main diagonal. ZL$           Yield the length of the transpose (number of columns).
ṙ              Shift the array of diagonals that many units to the left.
This puts the diagonals in their natural order.
Ç          Call the helper link on the result.

# Python, 237 230 bytes

7 bytes thanks to Dennis.

def f(a):i=range(len(a[0]));j=range(len(a));b,c,d=map(sorted,zip(*[[x,x+y,x-y]for y in i for x in j if"?"<a[x][y]]));return[[[a[x][y],"#"][(a[x][y]>" ")*(b[0]<=x<=b[-1])*(c[0]<=x+y<=c[-1])*(d[0]<=x-y<=d[-1])]for y in i]for x in j]


Port of my answer in Pyth.

Takes array of lines as input, outputs 2D array of characters.

# R, 561 bytes

\(x){h=which;'?'=unlist;M=max;m=min;R="#";v=?Map(strsplit,x,"");'!'=length;L=!x;n=nchar(x[[1]]);N=L+n;o=grep(R,x);r=?Map(\(y)1:n+(y-1)*n,m(o):M(o));w=u=a=b={};for(j in 1:L){q=rep(" ",L-j);p=rep(" ",j);g=v[(j*n-n+1):(j*n)];w=c(w,q,g,p);u=c(u,p,g,q)};e=\(x)(x-1)%%N+1;k=\(w)e(h(w==R));d=M(k(w)):m(k(w));c=M(k(u)):m(k(u));for(j in 1:!w){q=\(w,d){if(w[j]=="."&&e(j)%in%d)w[[j]]=R;w};w=q(w,d);u=q(u,c)};for(j in 1:L){a=c(a,w[(j*N+1-j-n):(j*N-j)]);b=c(b,u[((j-1)*N+1+j):((j-1)*N+n+j)])};v[r[r%in%h(a==R&b==R)]]=R;Map(\(j)paste0(v[((j-1)*n+1):(j*n)],collapse=""),1:L)}


Attempt This Online!

Input: a list of strings

Output: a list of strings

I have no idea why this has to be sooo huge. Well, the task itself was quite challenging. I could save ~50 bytes outputting an array of characters instead of a list of strings, but that would break the challenge rules.

My first approach was to assign 3 coordinates to every element of the matrix, namely rows ===, and two diagonal columns \\\ and ///. Finding the row number of an element was too easy, while to get the diagonal columns indices it took some effort.

Figure 1.

Having all three coordinates (indices) of every # one should merely find the maxima and minima of #s in each coordinate and reconstruct the matrix where all the elements within the obtained minima to maxima become or stay #.

In the example above (Fig. 1) there are following extrema:

ROWS: min=2, max=4;
Column BLUE: min=3, max=6;
Column ORANGE: min=3, max=7


Or, graphically:

Figure 2.

Indeed, this is the right solution. I have managed to calculate the indices of \-column. The other one was more tricky. Yet another problem was to deal with both types of matrices - those which begin with a space and the other ones with a first dot/hash sign.

I have finished by writing some code which only worked on the test examples 2 to 4. :(

Then the answer from Dennis, (2016) has prompted me to try and to figure the indices in another way: adding spaces to the beginning and to the end of each row in such way that the columns will become perpendicular to the rows - once for \- and once for /-columns, of course.

This strategy is implemented in the above code snippet.

# TSQL, 768 bytes

I wrote a query to solve this - which I found quite difficult. It is not able to compete with all the excellent shorter answer. But wanted to post it anyway for those interested. Sorry about the length of the answer - hoping codegolf is also about different approachs.

Golfed:

DECLARE @ varchar(max)=
'
. . . . # . . .
. # . . . # . .
. . . # . . . .
. . . . . # . .
. . . . . . . .
'

;WITH c as(SELECT cast(0as varchar(max))a,x=0,y=1,z=0UNION ALL SELECT SUBSTRING(@,z,1),IIF(SUBSTRING(@,z,1)=CHAR(10),1,x+1),IIF(SUBSTRING(@,z,1)=CHAR(10),y+1,y),z+1FROM c WHERE LEN(@)>z)SELECT @=stuff(@,z-1,1,'#')FROM c b WHERE((exists(SELECT*FROM c WHERE b.y=y and'#'=a)or exists(SELECT*FROM c WHERE b.y<y and'#'=a)and exists(SELECT*FROM c WHERE b.y>y and'#'=a))and a='.')and(exists(SELECT*FROM c WHERE b.x<=x-ABS(y-b.y)and'#'=a)or exists(SELECT*FROM c WHERE b.x<=x+y-b.y and a='#'and b.y<y)and exists(SELECT*FROM c WHERE b.x<=x+b.y-y and a='#'and b.y>y))and(exists(SELECT*FROM c WHERE b.x>=x+ABS(y-b.y)and'#'=a)or exists(SELECT*FROM c WHERE b.x>=x-y+b.y and b.y<y and'#'=a)and exists(SELECT*FROM c WHERE b.x>=x-b.y+y and a='#'and b.y>y))OPTION(MAXRECURSION 0)PRINT @


Ungolfed:

DECLARE @ varchar(max)=
'
. . . . # . . .
. # . . . # . .
. . . # . . . .
. . . . . # . .
. . . . . . . .
'
;WITH c as
(
SELECT
cast(0as varchar(max))a,x=0,y=1,z=0
UNION ALL
SELECT
SUBSTRING(@,z,1),IIF(SUBSTRING(@,z,1)=CHAR(10),1,x+1),
IIF(SUBSTRING(@,z,1)=CHAR(10),y+1,y),
z+1
FROM c
WHERE LEN(@)>z
)
SELECT @=stuff(@,z-1,1,'#')FROM c b
WHERE((exists(SELECT*FROM c WHERE b.y=y and'#'=a)
or exists(SELECT*FROM c WHERE b.y<y and'#'=a)
and exists(SELECT*FROM c WHERE b.y>y and'#'=a)
)and a='.')
and
(exists(SELECT*FROM c WHERE b.x<=x-ABS(y-b.y)and'#'=a)
or exists(SELECT*FROM c WHERE b.x<=x+y-b.y and a='#'and b.y<y)
and exists(SELECT*FROM c WHERE b.x<=x+b.y-y and a='#'and b.y>y))
and(exists(SELECT*FROM c WHERE b.x>=x+ABS(y-b.y)and'#'=a)
or exists(SELECT*FROM c WHERE b.x>=x-y+b.y and b.y<y and'#'=a)
and exists(SELECT*FROM c WHERE b.x>=x-b.y+y and a='#'and b.y>y))
OPTION(MAXRECURSION 0)
PRINT @


Fiddle ungolfed

# GNU Octave, 212, 196 bytes

Maybe not really a golfer's favourite choice language, but that's what makes the challenge, isn't it? Assuming m is taken as a char matrix: 178 bytes stand alone and 196 if stuffed into a function.

golfed:

function k=f(m)[a,b]=size(m);[y,x]=ndgrid(1:a,1:b);t={y,y+x,x-y};k=m;s=x>0;for j=1:3l{j}=unique(sort(vec(t{j}.*(m==['#']))))([2,end]);s&=(l{j}(1)<=t{j})&(l{j}(2)>=t{j});endk(s&mod(x+y,2))=['#']end


ungolfed:

function k=f(m)
[a,b]=size(m);[y,x]=ndgrid(1:a,1:b);t={y,y+x,x-y};k=m;s=x>0;
for j=1:3
l{j}=unique(sort(vec(t{j}.*(m==['#']))))([2,end]);
s&=(l{j}(1)<=t{j})&(l{j}(2)>=t{j});
end
k(s&mod(x+y,2))=['#']
end


Explanation : we build a coordinate system, 3 axes - orthogonal to the hexagons sides, find max and min of each coordinate, then build a logical mask starting with 1 everywhere and logically and:ing each coordinate max and min constraint, finally re-setting each remaining "true" position to "#" char.

If you want to test it, you can just create m matrix like this:

m = [' . . . . . . . .. . . . # . . .  . # . . . # . .. . . # . . . .  . . . . . # . .. . . . . . . . ']; m = reshape(m,[numel(m)/6,6])';


and then call the f(m) and compare with m by building a matrix with both of them in:

['     before           after      ';m,ones(6,1)*'|',f(m)]

• (Belated) Welcome to PPCG! Octave answers are more than welcome. :) Two things though: 1) please include the code that you've actually counted(without unnecessary whitespace), so that people can check the score more easily. You can include a readable version separately. 2) It appears that your submission is a snippet which assumes the input to be stored in m and the output to be stored in k. Answers should always be full programs or callable functions. Commented Aug 30, 2016 at 14:53
• Thanks! Yes you are right, I have embedded k and m in a function f now and added a snippet constructing a first test m for validation. Commented Aug 30, 2016 at 15:28

# R, 225 bytes

\(a,u=strsplit(a,""),!=length){p=q={};for(n in 1:!a)for(m in 1:!el(u))if(u[[n]][m]>"A"){p=c(p,n);q=c(q,m)};'*'=\(a,b)a%in%min(b):max(b);for(x in 1:n)for(y in 1:m)if(u[[x]][y]>" "&x*p&(x+y)*(q+p)&(x-y)*(p-q))u[[x]][y]="#";u}


Attempt This Online!

Another shorter R golf. Calculation of the column coordinates: cols+rows and cols-rows as in the pythonian answer from leaky nun.