TransWikia.com

Alignment on Triangular Grids

Code Golf Asked on October 27, 2021

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:

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

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

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

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

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

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

3 Answers

APL (Dyalog Unicode), 36 27 bytes

1∊=/¯1 0 1∘.(⊥-2|⊣×⊥)⍸⍉⍎¨↑⎕

Try it online!

-9 bytes mostly from @Bubbler

Full program that returns 0 or 1. Takes input as an array of strings, where each character is 0 for . or 1 for #.

How?

Uses the same general strategy as Martin Ender's CJam Answer. The two diagonals are indexed as y+(-1)*x and y+1*x, both rounded up to the nearest odd number. The horizontal axis is indexed as y+0*x with no rounding.

1∊=/¯1 0 1∘.(⊥-2|⊣×⊥)⍸⍉⍎¨↑⎕
                         ↑⎕  ⍝ The input array of strings, converted to a matrix
                       ⍎¨    ⍝ Evaluate each character to obtain either 0 or 1
                     ⍸       ⍝ Find the (y,x) positions of both 1s
          ∘.                 ⍝ Outer product:
    ¯1 0 1                     ⍝ For each ⍺ in 1, 0, -1:
                               ⍝ And for each (y,x) position
            (⊥     )           ⍝ Compute (⍺×x)+y (convert to base ⍺)
                                 ⍝ (⍉-Transposed earlier to get x left of y)
             -2|⊣×⊥            ⍝ If odd and ⍺ is not 0: subtract 1
1∊=/                         ⍝ Check if the two positions have equal indices on any axis

Answered by fireflame241 on October 27, 2021

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.

Answered by Martin Ender on October 27, 2021

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 '#'

Answered by feersum on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP