Triangular Grids: Simply Connected Polyiamonds

Question

While we're on a triangular grids kick, I'd like to point out that there is an equivalent to polyominoes on a triangular grid. They are called polyiamonds, and they are shapes formed by gluing equilateral triangles together along their edges. In this challenge you are going to be deciding which subsets of a triangular grid are polyiamonds, and whether they have holes in them. Because it only takes 9 triangles to make a polyiamond with a hole in it, your code needs to be as short as possible.

The grid

We'll use Martin's triangular grid layout for the input:

a triangular grid

Pay attention to the fact that the centers of the triangles form a roughly rectangular grid and that the top left triangle "points" upward. We can describe a subset of this grid, then, by giving a rectangular "star map" indicating which triangles are included and which are not included. For instance, this map:

** **
*****

corresponds to the smallest polyiamond which contains a hole:

9-iamond with hole

Holes

A polyiamond which contains a hole like the example above (a region not a part of the polyiamond, which is surrounded on all sides by regions which are) is not, topologically speaking, simply connected.

The Challenge

Write a function or program which takes as input a "star map" as described above and output a truthy if and only if the indicated subset of the triangular grid is a simply connected polyiamond.

More Examples

*** ***
*******

corresponds to the polyiamond

13-iamond with no hole

which is simply connected.

---

* *
** **
 ***

corresponds to the polyiamond

9-iamond with no hole

which is simply connected.

---

** **
*** **
 ****

corresponds to the non-polyiamond

13 triangles which are nothing interesting

which would not be simply connected even if it were a polyiamond.

Input Spec

• The input will consist only of asterisks, spaces, and line feeds.
• The first character of input will always be a space or asterisk (corresponding to the upward pointing triangle in the top left corner of the grid).
• There will always be at least one asterisk on the first and last lines.
• There is NO guarantee that lines after the first line won't be empty. Two linefeeds in a row may appear in a legitimate input.
• Line lengths need not all be the same.

Winning Condition

This is code-golf, so shortest answer in bytes wins.

Test Cases

Truthy maps:

1) *
2) *
 *
3) **
4) *** ***
 *******
5) * *
 ** **
 ***
6) *
 **
 *
7) **
 ***
 ****
8) ****
 ** *
 *****
9) ***********
 ** ** **
 **** ** **
 **
 ************

Falsy maps:

1) *
 *
 *
2) * *
3) *
 *
4) **
 **
5) ***
 ***
6) ** **
 *****
7) ** **
 *** **
 ****
8) *
 *
9) *****
 ** *
 *****

• Level River St: nice question. If triangular grids are going to become a thing, may I suggest that they be represented as for example AV VA\nVAVAV instead of ** **\n*****as it makes it easier for a human to visualize. I already made an edit to one of Martin's ASCII diagrams.
• quintopia: I wasnt particularly concerned with human readability, no. I wanted to do whatever would be easier for a program to read while remaining small.
• Michael Klein: So basically, false iff there is a section only "connected" by corners?
• quintopia: Or if there are parts which are not connected at all. Martin put it this way: True iff the figure and ground are both connected along edges, so that 2 flood-fills are sufficient to recolor the plane.

Answer 1

Snails, 95 bytes

F&
lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}\*}+l\ ,~a~|{\ (lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}+~

This really suffered from duplication, as I haven't implemented macros or any kind of back-reference. What it does is to check that for each star, there exists a path to the leftmost star on the top line; and for each space, there is a path to an edge of the grid.

F& ,, option F: pad lines with spaces to the length of the longest
 ,, option &: print 1 iff match succeeds from every cell
lr ,, direction left or right, or
 | =((ul.)2 ,l~a~) d ,, direction down, if we are an even number of orthogonal moves from the top left
 | !((ul.)2 ,l~a~) u ,, or, direction up if we are odd number of moves from the top left
 } \* ,, literal '*'
}+ ,, 1 or more times
l\ ,~a~ ,, check that we are on the leftmost * in the top line
| ,, the part before this is for starting on '*'; part after for starting on ' '
{ \ ,, literal ' '
 ( lr ,, direction left or right, or
 | =((ul.)2 ,l~a~) d ,, same drill as before...
 | !((ul.)2 ,l~a~) u 
}+ ,, 1 or more times
~ ,, end on an out of bounds cell

• quintopia: I don't understand how it works, but it totally works.

Answer 2

CJam, (削除) 101 (削除ここまで) 98 bytes

qN/_z,f{' e]}{S2*f+W%z}4*:eeee::f+:~{_(aL{+_{_2,.+12,ドル.-@_:+1&!2*(a.+}%2${a1$&},\;@1$-@@}h;\;-}2*!

Try it online.

I finally overcame my fear of implementing a flood fill in CJam. It's about as ugly as I expected, and it can most definitely be golfed.

The general idea is to perform two flood-fills (which are actually implemented as removals from the list of unvisited cells). The first pass will remove all spaces that are reachable from the edge. The second pass will then pick the first * in reading order and remove all the triangles reachable from that. If and only if the resulting list is empty, the polyiamond was simply connected:

• If the polyiamond had a hole, the first flood fill is unable to reach and remove that hole.
• If the input consists of several disconnected polyiamonds, the second flood fill is unable to reach and remove all of them.