18
\$\begingroup\$

Hexagonal grids have been become a fairly popular twist for challenges about 2-dimensional data recently. However, it seems that the equally interesting triangular grids have been largely neglected so far. I'd like to rectify that with a rather simple challenge.

First, how do we represent a triangular grid? Consider the following example (ignore the right diagram for now):

enter image description here enter image description here

The cells neatly fall onto a regular grid (the difference to a regular grid being only which cells are considered adjacent):

1234567
89abcde
fghijkl
mnopqrs

Now, as the right diagram shows, a triangular grid has three main axes: a horizontal and two diagonal ones.

Highlighting these in the ASCII grid:

AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

The Challenge

You're given a rectangular string representing a triangular grid (where the top left corner is an upwards-pointing triangle). Most of the cells with be ., but exactly two cells will be #, e.g.:

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

Determine whether the two # are aligned along any of the three axes of the grid (i.e. whether they lie on a single row in any of the three directions highlighted above). For this example, the answer is "no".

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be a single string delimited by linefeeds or some other convenient character, or a list of strings. You may use any two (consistent) printable ASCII characters in place of . and #.

Output should be a truthy value if the highlighted cells are aligned and a falsy value otherwise.

Standard rules apply.

Test Cases

Truthy grids:

.#..#.

#
#

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

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

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

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

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

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

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

Falsy grids:

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

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

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

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

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

...........
.......#...
...........
...........
...........
...........
.#.........
\$\endgroup\$
3
\$\begingroup\$

Snails, 40 39 bytes

\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#

\#    ,, match '#'
{
  z |  ,, Either turn in any octinilear direction, or do all the other stuff before the }
  =(   ,, If this assertion succeeds, the starting cell is an "upwards-pointing triangle"
    ul.ul.`,  ,, Go one cell up or left twice, any number of times.
              ,, This should have been one byte shorter with ul.`2 , or ul.`2+? but 
              ,, the parsing of ` is buggy.
    l~a~   ,, Check that we are on the top-left cell by matching out-of-bounds to the left and then northeast
  )
  ( l.a3 |  ,, Move leftward once, then set direction to northwest; or
    .a   |  ,, Move right (the initial direction) once, then set direction to northeast; or
    d.ea5   ,, Move down once, then set direction to either northwest or northeast
}
.,    ,, Match any number of arbitrary chars (moving in the current direction)
\#    ,, match '#'
\$\endgroup\$
2
\$\begingroup\$

CJam, 47 bytes

Well, now that there is a shorter solution I no longer feel bad sharing my own. :) (Mostly to show that this isn't particularly difficult, even if you don't have a 2D pattern matching language...)

qN%:eeee::f+:~{S&},2f<:P0f=P::+Xf|P::-Xf|]::=:|

This uses spaces in place of # and really anything else for ..

Run all test cases online.

I really hate the duplication in P::+Xf|P::-Xf| but so far I haven't come up with anything to get rid of it.

Explanation

Don't read on if you want to figure out a solution for yourself.

First, the boring part: getting the two coordinate pairs of the two spaces in the input grid:

qN%   e# Read input and split into lines.
:ee   e# Enumerate the characters in each line. I.e. turn each character 'x into a pair
      e# [N 'x] where N is its horizontal 0-based index.
ee    e# Enumerate the lines themselves, turning each line [...] into [M [...]] where M
      e# is its vertical 0-based index.
::f+  e# This distributes the vertical index over the individual lines, by prepending it
      e# to each pair in that line. So now we've got a 2-D array, where each character 'x
      e# has been turned into [M N 'x].
:~    e# Flatten the outermost dimension, so that we have a flat list of characters with
      e# their coordinates.
{S&}, e# Filter only those lists that contain a space.
2f<   e# Truncate the two results to only their first two elements.
:P    e# Store the result in P.

Now the interesting part is how to determine whether those coordinates are aligned or not. My code computes all three axes separately:

  • The horizontal axis is trivial. Check whether the vertical coordinates match.
  • Let's look at the north-east diagonal. In the ASCII grid, there are always two antidiagonals that belong to each tri-grid diagonal:

    ....AV..
    ...AV...
    ..AV....
    

    We can identify the current antidiagonal by adding up the x and y coordinates:

    01234567
    12345678
    23456789
    

    So we'd want 0 and 1 to belong to the same diagonal, as well as 2 and 3, and 4 and 5 and so on. That means, once we have our anti-diagonal index we want to round up to the next odd number. In other words, we take the bitwise OR with 1. (We could also round down to the next even number by bitwise AND with -2 but that's more expensive in code.)

  • Now the south-east diagonals:

    .VA.....
    ..VA....
    ...VA...
    

    In order to give diagonals an index, we subtract the x from the y coordinate (representing negative numbers as letters):

    0abcdefg
    10abcdef
    210abcde
    

    In this case, we'd want 0 and 1 to belong to the same diagonal, as well as -1 and -2, or 2 and 3. So once again, we want to round up to the next odd number.

Here is the code for that:

0f=  e# The coordinates are still on the stack. Replace each with its vertical coordinate
     e# to check for the horizontal axis.
P    e# Push the coordinates again.
::+  e# Sum each pair to get an anti-diagonal index.
Xf|  e# OR each index with 1 to round up to the next odd number.
P    e# Push the coordinates again.
::-  e# In each pair, subtract the horizontal coordinate from the vertical, to
     e# get a diagonal index.
Xf|  e# OR each index with 1.
]    e# Wrap all three index pairs in an array.
::=  e# Check equality for each pair.
:|   e# Fold bitwise OR over the results to check if at least one pair of indices
     e# was equal.
\$\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.