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):
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
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 code-golf rules apply.
Truthy grids:
.#..#.
#
#
...........
...#.......
...........
...........
...........
.......#...
...........
...........
.......#...
...........
...........
...........
...#.......
...........
.#.........
...........
...........
...........
...........
.......#...
...........
...........
...#.......
...........
...........
...........
...........
.......#...
.........#.
...........
...........
...........
...........
...#.......
...........
...........
.......#...
...........
...........
...........
...........
...#.......
...........
.#.....#...
...........
...........
...........
Falsy grids:
#.....
.....#
.....#
#.....
...#.......
...........
...........
...........
...........
.......#...
...........
...........
...#.......
...........
...........
...........
...........
.........#.
.......#...
...........
...........
...........
...........
...#.......
...........
...........
.......#...
...........
...........
...........
...........
.#.........
1∊=/¯1 0 1∘.(⊥-2|⊣×⊥)⍸⍉⍎¨↑⎕
-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 #
.
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
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 .
.
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.
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:
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
#{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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP