15
\$\begingroup\$

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2017 Day 11.

Obligatory why me and not Bubbler link

After having rescued a child process lost on a hexagonal infinite grid, you hear someone else screaming for help. You turn around, and unsurprisingly, there is another program looking for its own child process. "Help! It's gotten lost in an infinite octagonal grid!"

Well, it's not all octagonal, obviously. Instead, it's actually a 4-8-8 tiling:

An octagonal tile (X) has eight neighbors, indicated by eight directions (N, NE, E, SE, S, SW, W, NW). A square tile (Y) has only four neighbors in cardinal directions (N, E, S, W).

The program gives you the path taken by the child process. The initial tile is an octagon. You try following the directions one by one, and ... something's wrong in the middle. "Look, it can't move diagonally from a square tile, you see?"

Given a sequence of movements, determine if it is valid on the 4-8-8 grid, assuming the initial position of an octagon.

Input: A list of strings entirely consisting of N, NE, E, SE, S, SW, W, NW. Or a single string containing these strings with a single delimiter (space, comma, newline, or any other char that is not one of NESW) in between. (If the input is ["N", "E", "NW", "NE", "E", "SE"] then you can take it as e.g. "N,E,NW,NE,E,SE")

Output: A value indicating whether it is valid or not. You can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Truthy:

[]
["S"]
["SW"]
["N", "E", "NW", "NE"]
["NE", "SE", "SW", "NW", "N", "E", "S", "W"]

Falsy:

["N", "E", "NW", "NE", "E", "SE"]
["NE", "SE", "N", "E", "S", "SW", "NW", "W"]
["N", "NW"]
Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ Can we take it as, say, xx x xx xx x x xx xx x or something? \$\endgroup\$
    – emanresu A
    Commented Dec 12, 2021 at 0:52
  • \$\begingroup\$ @emanresuA > Or a single string containing these strings with a single delimiter (space, comma, newline, or any other char that is not one of NESW) in between \$\endgroup\$
    – lyxal
    Commented Dec 12, 2021 at 0:54
  • \$\begingroup\$ I meant, can we take it without distinquishing between NESW and replacing them all with a single character? \$\endgroup\$
    – emanresu A
    Commented Dec 12, 2021 at 0:55
  • \$\begingroup\$ @emanresuA I'mma say no to that, because that doesn't seem in the spirit of Bubbler's original challenge. \$\endgroup\$
    – lyxal
    Commented Dec 12, 2021 at 1:15
  • \$\begingroup\$ Would something like , be allowed as delimiter? It is not a single character but arguably a single delimiter. \$\endgroup\$
    – loopy walt
    Commented Dec 12, 2021 at 16:30

21 Answers 21

Reset to default
8
\$\begingroup\$

Regex (any), 27 bytes

^((.\n.\n)*..\n?)*(.\n)*.?$

Matches valid strings, taking input as a newline-separated string. There's probably a way to golf this regex. This version thanks to @AnttiP.

Javascript, 34 bytes

/^((.\n.\n)*..\n?)*(.\n)*.?$/.test

Try it online!

^                          From the start...
 (             )*          Match 0+ times...
  (      )*                Match 0+ times...
   .\n.\n                  A pair of 1-char strings
           ..\n?           Followed by a 2-char string with possible separator (in case this is the end)
 (             )*          This block will match 2-char strings until the end as long as the 1-char strings are paired
                 (.\n)*    Match any amount of . after this
                       .?$ Match possible trailing . at the end

This relies on the fact that length 1 strings modify the parity of whether we're on an octagon or square, and whether diagonal (length-2 strings) are valid.

Old version, 35 bytes

^(((\S\S )*\S ){2})*(\S\S )*\S \S\S

Matches invalid strings, taking input space-separated.

^                                   From the start...
 ((           ){2})*                Match an even number of times...
   (\S\S )*                         Possibly any amount of length-2 strings                      
           \S                       Followed by a length-1 string
                    (\S\S )*        Possibly match any amount of length-2 strings
                            \S \S\S Match a length-1 string followed by a length-2 string.
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ A shorter regex is ^((.\n.\n)*..\n?)*(.\n)*.?$. This matches valid strings. Using newlines as separators saves 2 bytes, for a total of -8 bytes. \$\endgroup\$
    – AnttiP
    Commented Dec 12, 2021 at 16:48
  • \$\begingroup\$ It amazes me how much everyone is still struggling to golf their regexes down... \$\endgroup\$
    – Neil
    Commented Dec 13, 2021 at 10:06
8
\$\begingroup\$

Python 2, 45, 44, 36 bytes (@Jonathan Allan)

lambda a:`a.title()`[1::2]>`a`[1::2]

Try it online!

Older versions

lambda a:repr(a.title())[1::2]>repr(a)[1::2]

Try it online!

lambda a:(A:=repr(a.title())[1::2])>A.upper()

Try it online!

Explanation (all versions)

This expects a backslash- (or tab- or newline-) separated string and returns True for invalid and False for valid paths.

It works by detecting odd-length stretches of single-character commands followed by at least one double-character command.

The idea is essentially: if we had X for principal directions and XY for the others we could just concatenate take every other character and check for Ys.

Almost as good is to title-case the input string which puts a capital instead of X and a small instead of Y.

Now, I found no cheap way of getting rid of the delimiter, but almost as good we use backslash or tab or newline and apply repr. This replaces each separator with its two-character escaped representation such that they do not interfere with parity.

It remains to check for any lowercase letters which we do by comparing with upper whether any differences with the non title cased inputs have survived the skipping step.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ In Python 2 you can use backticks in place of repr calls, so lambda a:`a.title()`[1::2]>`a`[1::2] saves eight. \$\endgroup\$
    – Jonathan Allan
    Commented Dec 12, 2021 at 21:14
7
\$\begingroup\$

R, 46 43 42 bytes

Edit: -1 byte thanks to pajonk

function(s)any(cumsum(x<-nchar(s))%%2&x>1)

Try it online!

Function notvalid: outputs TRUE if the path is not valid, FALSE if it's a valid path.

How?
If the path is valid, then 2-character moves (that can only be from an octagon) always move to an octagon; 1-character moves flip between octagons & squares. So, we're in a square if we've had an odd number of 1-character moves.
Invalid moves are attempted 2-character moves from squares, so we need to check if any of these co-incide with positions after an odd number of 1-character moves.

any(...) = is this question TRUE value at any position:
cumsum(x)%%2 = have we had an odd number of 1-character moves?
&x>1 = and, if so, is x currently 2?

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Won't cumsum instead of diffinv work for -1 byte? \$\endgroup\$
    – pajonk
    Commented Dec 12, 2021 at 14:45
6
\$\begingroup\$

Jelly, 6 bytes

ẈÄPƝḂẸ

A mondadic Link that accepts a list of lists of characters and yields 0 if valid or 1 if invalid.

Try it online!

How?

The only way to reach a square is via a sequence of an odd number of cardinal directions, after which if a diagonal direction is given the input is invalid. The cardinal directions are length one, while diagonal ones are length two. Thus if the cumulative sum of lengths of the input contains two odd numbers in a row it is an invalid instruction.

ẈÄPƝḂẸ - Link: instuctions
Ẉ      - length of each instruction
 Ä     - cumulative sums -> odd when taken to a square given a valid prefix
   Ɲ   - for neighbours:
  P    -   product (only odd * odd is odd)
    Ḃ  - is odd? (vectorises)
     Ẹ - any?
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Ruby, 33 32 29 bytes

->l{l.all?{|y|y[1]?l:[l=!l]}}

Try it online!

Look ma, no regex!

How?

Reuse l as a flag that is initialized with a truthy value, and translates as true->octagon, false->square. The sequence is invalid if we have to move diagonally (y[1] is true when y is 2 characters long) from a square (l is false). If y is only 1 character, we are moving from an octagon to a square or viceversa, so we have to flip the flag. This is enclosed in an array to make the operation return a truthy value.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Vyxal, 9 bytes

vL:‹$¦∷*a

Try it Online!

There's got to be a better way to do this. Outputs reversed - 1 for invalid, 0 for valid,

vL        # Lengths
     ¦∷   # Cumulative sums modulo 2, tracking when on a square and when not  
    $  *  # Multiplied by
  :‹      # Those same lengths decremented
          # Each one is only true when on a square *and* trying to move diagonally
          # Which is invalid    
        a # Are any true? If so, there's an invalid one somewhere.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 15 bytes

⬤θ›³⁺﹪Ｌ⪫…θκω²Ｌι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean i.e. - for valid, nothing for invalid. Explanation: An input is valid if the cumulative length modulo 2 plus the length of the current item never exceeds 2.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Retina 0.8.2, 20 bytes

^(\w,?($|\w($|,)))*$

Try it online! Link includes test cases. Explanation: The regular expression only matches valid movements, i.e. those that only contain paired or trailing orthogonal directions. 18 bytes if newlines are allowed as separators:

^(.¶?($|.($|¶)))*$

Try it online! Link includes test suite that splits on comma for convenience.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 32 bytes

a->t=0;[t=[1-t,t*x][#d]|d<-a];t'

Try it online!

Here t is the state of the current tile: 0 means octagon, 1 means square.

When the direction has length 1, we just set t to 1-t. If the length is 2, we multiply t by x, so 0 remains 0, while 1 becomes a polynomial. If t is a polynomial, 1-t and t*x are also polynomials. So invalid states are represented by polynomials.

Finally, we take the derivative of t. The derivative of a constant is 0, which is falsy. The derivative of non-constant polynomials are truthy.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python,  48  47 bytes

f=lambda a,o=1:o>1or a and f(a[1:],len(a[0])-o)

A recursive function that accepts a list of strings and returns an empty list ([]) if the input is valid or True if not.

Try it online!

How?

a is our list of instructions.

o starts off as 1 (,o=1) and is a flag that indicates whether we are on an octagon (1) or square (0), this is updated for the next iteration by subtracting the current flag value from the current instruction length (len(a[0])-o).

If we try to go diagonally from a square then o becomes 2 (since \$2-0=2\$) and then the next iteration's evaluation of o>1 causes a return value of True.

We drop the first (now executed) instruction from a (a[1:]) in order to perform the next iteration and if we find ourselves with an empty list the instructions were valid and or a causes this empty list to be returned.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

R, 55 bytes

f=function(x,o=1)o>1||length(x)&&f(x[-1],nchar(x[1])-o)

Try it online!

Port of @Jonathan Allan's recursive answer.

Outputs flipped TRUE/FALSE.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Rust, 80 56 bytes

|p:&[&str]|p.iter().fold(0,|a,b|a+a%b.len()^b.len()&1)<2

Try it online!

  • -24 bytes by using fold and boolean operations (thanks @AnttiP)
Improve this answer
\$\endgroup\$
3
  • 2
    \$\begingroup\$ A fold is shorter: |p:&[&str]|p.iter().fold(0,|a,b|a+a%2%b.len()^b.len()&1)<2 -22 bytes \$\endgroup\$
    – AnttiP
    Commented Dec 12, 2021 at 14:06
  • \$\begingroup\$ I looked into using fold but didn't consider using XOR, thanks! \$\endgroup\$
    – Ezhik
    Commented Dec 12, 2021 at 14:12
  • 1
    \$\begingroup\$ Further -2 bytes: |p:&[&str]|p.iter().fold(0,|a,b|a+a%b.len()^b.len()&1)<2 (the %2 is redundant) \$\endgroup\$
    – AnttiP
    Commented Dec 12, 2021 at 14:15
2
\$\begingroup\$

Python3, 82 bytes:

f=lambda x,s=0:((b:=len(x[0])==1)or s%2==0)and f(x[1:],s+b)if x else s%2==0 or s<2

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

BQN, 13 bytesSBCS

∨˝2|·×⟜»·+`≠¨

Run online!

Exact port of Jonathan Allan's Jelly answer. There are a few things that can be varied, e.g. 1∊1‿1⍷·≠`2|≠¨ works at the same length, but I couldn't find anything shorter.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Ruby, 39 34 bytes

->i{/^((.,){2}*(.\w,)*)*.,.\w/!~i}

Try it online!

Method takes string with commas and returns true if the path is valid. The regexp looks for invalid path which is essentially an odd one-letter direction followed by a two-letter.

Thanks to ovs for very useful suggestions and -5 bytes!

Another less golfy but more interesting for me version doesn't work on TIO but takes arrays instead of strings and is 54 bytes:

f=->t{c=0;t.chunk{_1[1]?1:2}.all?{2>c+=_1*c+_2.size%_1}}

p f[[]]
p f[["S"]]
p f[["SW"]]
p f[["N", "E", "NW", "NE"]]
p f[["NE", "SE", "SW", "NW", "N", "E", "S", "W"]]
# falsy
p f[["N", "E", "NW", "NE", "E", "SE"]]
p f[["NE", "SE", "N", "E", "S", "SW", "NW", "W"]]
p f[["N", "NW"]]
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ As there will be no consecutive commas in the input, some of the \w can be . instead. And you can actually swap to the order of arguments to !~ saving another byte: tio.run/… \$\endgroup\$
    – ovs
    Commented Dec 12, 2021 at 14:15
2
\$\begingroup\$

Turing Machine Code, 97 77 bytes

0 _ _ r halt
0 * * r 1
1 _ _ r 2
1 * * r 3
2 * * r 3
3 _ _ r 0
3 * * r halt-r

Try it online

Takes space-separated input, thanks to AntiP for saving 20 bytes

Haven't tested on my Java implementation yet

Improve this answer
\$\endgroup\$
1
2
\$\begingroup\$

Husk, 8 bytes

ṁ%2Ẋ*∫mL

Try it online!

Approach based on Jonathan Allan's Jelly answer. Outputs zero (falsy) for valid paths, non-zero (truthy) for non-valid paths.

      mL  # get the lengths of the input strings
     ∫    # and calculate the cumulative sum
          # (so odd numbers indicate we're in a square)
   Ẋ*     # product of all adjacent pairs
          # (so odd numbers indicate a 2-character move
          # attempted from within a square)
ṁ%2       # map 'modulo 2' to all elements (gets odd numbers)
          # and output sum (non-zero if any elements were odd)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Thue, 84 bytes

@::=:::
S::=N
E::=N
W::=N
aN,::=b
aNN,::=a
bN,::=a
a,::=~1
b,::=~1
bNN::=~0
::=
a@,,

Takes comma-separated input

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Rather than X, can you not map three of the cardinal directions to be the same as the fourth? \$\endgroup\$
    – Neil
    Commented Dec 13, 2021 at 9:50
  • \$\begingroup\$ @Neil that is true, unfortunately while I was testing that I noticed that this version doesn't always work if the last direction is two letters so I need to fix that \$\endgroup\$
    – SuperJedi224
    Commented Dec 13, 2021 at 18:50
  • \$\begingroup\$ Ok that should be fixed now \$\endgroup\$
    – SuperJedi224
    Commented Dec 13, 2021 at 18:53
1
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

FreeQ[Or@@StringLength@#/. 1||1->3,1||2]&

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

TypeScript Types, 107 bytes

type M<T,A=1,B=0,D="N"|"S"|"E"|"W">=T extends[infer C,...infer T]?C extends D?M<T,B,A>:A extends 1?M<T>:0:1

Finally, one that didn't benefit from //@ts-ignore!

Try It Online!

Ungolfed / Explanation

// DiagA: whether non-orthogonal moves are currently allowed
// DiagB: wtherer non-orthogonal moves are allowed in the other type of cell
type Main<Arr, DiagA = 1, DiagB = 0, OrthoDir = "N" | "S" | "E" | "W"> =
  // Check the first string in Arr
    Arr extends [infer Dir, ...infer Rest]
        ? Dir extends OrthoDir
      // If it's orthogonal, switch the type of cell
      ? Main<Rest, DiagB, DiagA>
      : DiagA extends 1
        // Otherwise, if diagonals are allowed, move into an octagonal cell (the default)
        ? Main<Rest>
        // Otherwise, return false
        : 0
    // The array is empty; return true
    : 1
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

ηJ€gü*Éà

Input as a list of strings. Outputs 1 for invalid grids and 0 or an empty string "" for valid grids (only 1 is truthy in 05AB1E, so this falls under the "output truthy/falsy using your language's convention (swapping is allowed)" rule).

Port of @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

Explanation:

η         # Get the prefixes of the (implicit) input-list
 J        # Join each inner prefix-list together to a single string
  €g      # Get the length of each string
    ü     # For each overlapping pair:
     *    #  Multiply them together
      É   # Check for each whether it's odd
       à  # And check if any were odd by leaving the maximum
          # (after which the result is output implicitly)

Empty or single-item inputs are [] after the ü*, which is why they result in an empty string "".

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.