14
\$\begingroup\$

Your challenge, should you choose to accept it, is to take as input:

  1. A program in DirectionLang (as an ASCII string consisting of DirectionLang instructions)
  2. A list of pairs of integers, henceforth known as the pretty places. This list may be taken in any reasonable format.

You should then output a truthy value if the program halted at a pretty place, and a falsey value otherwise.

DirectionLang

A DirectionLang instruction is hereby defined to be either

  1. <: Decrement the x coordinate by 1.
  2. >: Increment the x coordinate by 1.
  3. ^: Increment the y coordinate by 1.
  4. V: Decrement the y coordinate by 1.
  5. S: Skip the next instruction if the program is currently at a pretty place.

A DirectionLang program is executed by performing each instruction, in order. A DirectionLang program starts at the origin (coordinates (0, 0)). A DirectionLang program halts when every instruction has been executed.

If a DirectionLang program ends with an S, then its behavior is undefined.

If a DirectionLang program has no instructions, then its behavior is undefined.

DirectionLang is quite obviously not Turing complete, as there is not a way of looping.

Test cases

"<>^^" [(0, 2), (0, 0)] -> True
"<>^^" [(0, 1)] -> False
"S^>>" [(0, 0), (2, 0)] -> True
"<SS^" [(-1, 0), (-1, 1)] -> True
"<SS^" [(-1, 0), (-1, -1)] -> False
"S^>>" [(2, 0)] -> False
"S^>>V" [(2, 0)] -> True
\$\endgroup\$
2
  • 2
    \$\begingroup\$ May we take complex integers as input instead of pairs of integers? \$\endgroup\$
    – M Virts
    Jun 1 at 17:27
  • \$\begingroup\$ Yes, that is a reasonable format! \$\endgroup\$ Jun 1 at 17:29

8 Answers 8

4
\$\begingroup\$

JavaScript (Node.js), 101 bytes

Expects (program_string)(pretty_places). Returns \$0\$ or \$1\$.

s=>a=>Buffer(s+0).map(n=>(p=a.some(a=>x+[,y]==a),+s)?s=0:(n%=5)-3?y-=~-"121"[x+=n%3-1,n]:s=p,x=y=0)|p

Try it online!

How?

The ASCII codes of the DirectionLang instructions are unique modulo \$5\$. Furthermore, the value of \$dx\$ can be easily deduced from them with an additional modulo \$3\$. We use a short lookup string for \$dy\$.

 char. | c  | n = c mod 5 | dx = (n mod 3) - 1 | dy = -~-"121"[n]
-------+----+-------------+--------------------+------------------
  "<"  | 60 |      0      |         -1         |        0
  ">"  | 62 |      2      |          1         |        0
  "^"  | 94 |      4      |          0         |        1
  "V"  | 86 |      1      |          0         |       -1
  "S"  | 83 |      3      |         n/a        |       n/a
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Very nice. Do you generally find these formulas with an automated search or just by fiddling? \$\endgroup\$
    – Jonah
    Jun 1 at 16:34
  • 2
    \$\begingroup\$ The mod 5 was the first thing I tried and the mod 3 was then obvious. I did try an automated search of random formula for dy but it didn't return anything shorter than the lookup string. \$\endgroup\$
    – Arnauld
    Jun 1 at 16:49
3
\$\begingroup\$

Python, 128 bytes

-39 bytes thanks to Wheat Wizard and -12 bytes thanks to ovs.

def f(p,l):
 s=a=0
 while p:h=p[0];s+=abs('< >'.find(h))-1;a+=abs('V ^'.find(h))-1;p=p[1+(h=='S'and(s,a)in l):]
 return(s,a)in l

Attempt This Online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can do it with abs: s+=abs('< >'.find(h))-1;a+=abs('V ^'.find(h))-1 \$\endgroup\$
    – Wheat Wizard
    Jun 1 at 10:46
3
\$\begingroup\$

JavaScript, 118 111 bytes

-7 bytes thanks to Arnauld!

p=>g=([d,...r],x=0,y=0,i='S>V ^'.indexOf(d),P=p.some(a=>x+[,y]==a))=>d?g(r.slice(!i&P),i<2?x+i:x,i<2?y:y+i-3):P

Try it online!

A recursive function expecting input as f(p)(d), where p is a 2D array of pretty places, and d is a string of instructions. Outputs true if in a pretty place, otherwise false.

Ungolfed and Explained

p => g = (       // p = pretty places (PP's), g = recursive func
  [d, ...r],     // split instruction string and look at first char
  x = 0, y = 0,  // set default x and y
  i = 'S>V ^'.indexOf(d),   // find index of command
  P = p.some(a => x + [, y] == a)  // check if we are at PP
) => d ?  // check if we are at end of input
  g(      // if not, recurse
    r.slice(!i & P),       // if char is 'S' and at PP, skip one
    i < 2 ? x + i : x,     // if i < 2, change x by i
    i < 2 ? y : y + i - 3  // if i >= 2, change y by i-3
  ) :
  P       // if at end, return P

Previous Answer, 125 121 bytes

-4 bytes thanks to Steffan!

p=>g=([d,...r],x=0,y=0,P=!p.every(([u,v])=>u-x||v-y))=>d?g(r.slice(P&d=='S'),x+~~{'<':-1,'>':1}[d],y+~~{V:-1,'^':1}[d]):P

Try it online!

A recursive function expecting input as f(p)(d), where p is a 2D array of pretty places, and d is a string of instructions. Outputs true if in a pretty place, otherwise false.

Ungolfed and Explained

p => g = (       // p = pretty places (PP's), g = recursive func
  [d, ...r],     // split instruction string and look at first char
  x = 0, y = 0,  // set default x and y
  P = !p.every(([u, v]) => u - x || v - y)  // check if we are at PP
) => d ?  // check if we are at end of input
  g(      // if not, recurse
    r.slice(P & d == 'S'),          // if char is 'S' and at PP, skip one
    x + ~~{'<': -1, '>': 1}[d],  // increment x by lookup
    y + ~~{V: -1, '^': 1}[d]     // increment y by lookup
  ) :
  P       // if at end, return P
\$\endgroup\$
3
  • 1
    \$\begingroup\$ y+({v:-1,'^':1}[d]|0) can be y+~~{v:-1,'^':1}[d] to save two bytes. Same with x+({'<':-1,'>':1}[d]|0) \$\endgroup\$
    – Steffan
    Jun 1 at 2:01
  • 2
    \$\begingroup\$ You can save 7 bytes with P=p.some(a=>x+[,y]==a). \$\endgroup\$
    – Arnauld
    Jun 1 at 8:20
  • \$\begingroup\$ @Arnauld Nice find, I didn't think to compare them as strings, thank you! \$\endgroup\$ Jun 1 at 21:01
2
\$\begingroup\$

Charcoal, 42 bytes

FA«J⊟ι⊟ι1»J⁰¦⁰FSF¬∧υΣ⊟υ≡ιS⊞υKKM✳⊗⌕^<VιT¹¦¹

Try it online! Link is to verbose version of code. Takes the pretty places as the first argument and outputs 1 if the directions end on a pretty place, nothing if not. Explanation:

FA«

Loop over the pretty places.

J⊟ι⊟ι

Jump to those coordinates. (Note that on canvas they are actually rotated 90° from the description but I rotate the movements to compensate.)

1

Mark each pretty place with a 1.

»J⁰¦⁰

Jump back to the origin.

FS

Loop over the instructions.

F¬∧υΣ⊟υ

If the previous instruction was not an S or we were not at a pretty place, then...

≡ιS

... if the current instruction is an S then...

⊞υKK

... save the current cell for the check on the next loop, otherwise...

M✳⊗⌕^<Vι

... move in the appropriate direction.

T¹¦¹

Delete the canvas except for the current cell.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 112 105 102 bytes

-7 bytes using the (c mod 5) formula from Arnauld's JavaScript answer

s,p=input()
x=y=0
while s:k=(x,y)in p;exec'xyxky--+++'[ord(s[0])%5::5]+'=1';s=s[1+k/2:]
print(x,y)in p

Try it online!

Accepts input from STDIN as <DirectionLang string>, <pretty places>

\$\endgroup\$
1
\$\begingroup\$

[Ruby (2.7.0)], 143 bytes

x=0i
y=!p
_,d,v=t.split ?"
a={?<=>-1,?>=>1,?^=>1i,?V=>-1i,?S=>0}
(d+?S).chars.map{|c|x+=a[c]if y
y=y&&c==?S?!v.match("(#{x.rect*', '})"):!p}
!y

Decided to try using complex numbers. Probably would be easier to do x,y and separate increment statements. The "a" hash is what we add to x for each character, the "y" is "yes" for if we should do the next line. We add an 'S' on the end to force the final comparison and return !y. Converting the complex number to "(x, y)" was pretty costly. Just uses a string match to see if the place is nice.

I should point out that "t" is the variable containing the full test string (the "program" and the nice values), if you needed it to be stdin, you'd need to change that to a gets or such. The final statement is the return value (!y), you'd need a "p !y" or $> or such if you want it printed. Right now you can test/run it by wrapping it in a def like:

def directionLang(t)
   <code golf above>
end

[edit]

Actually I just wrote it without complex numbers and was surprised that it grew. There'd probably be a better way to handle the addition, but here's the basic code:

x=y=0
m=!p
_,d,v=t.split ?"
(d+?S).chars.map{|c|x+=(c==?<)?-1:(c==?>)?1:0if m
y+=(c==?V)?-1:(c==?^)?1:0if m
m=m&&c==?S?!v.match("(#{x}, #{y})"):!p}
!m
\$\endgroup\$
0
1
\$\begingroup\$

MATL, 39 38 35 33 bytes

x0Ti"@2\?y1GmY~}J@k11\Q^/+T]]x1Gm

Inputs are: a vector of complex coordinates, then a string.

Try it online! Or verify all test cases.

How it works

x          % Input: numeric vector of complex coordinates. Delete
0          % Push 0. This is the complex coordinate where the program starts
T          % Push true. This is the interpret state: if false, the next
           % instruction should be skipped
i"         % Input: string containing the instrunctions. For each instruction:
  @2\      %   Push current instruction (converted to ASCII code), modulo 2
  ?        %   If nonzero (this is true only for 'S')
    y      %     Duplicate from below: push copy of current coordinate
    1Gm    %     Is it in the first input, i.e. is it pretty? Gives true or false
    Y~     %     XOR with interpret state. This toggles the interpret state.
           %     So if the state was true, it is now set to false because the
           %     current instruction is 'S' and the current coordinate is pretty.
           %     If the state was false, that means that the current instruction
           %     should have been skipped. So we simply set the interpret state
           %     to true
  }        %   Else (the current instruction is not 'S', but may need skipping)
    J      %     Push j (imaginary unit)
    @k     %     Push current instruction converted to lowercase
    11\    %     (Convert to ASCII code) modulo 11
    Q      %     Add 1
    ^      %     Power. This gives -1 for '<', 1 for '>', -j for '^', j for 'V'.
           %     Note that the values for '^' and 'V' are reversed
    /      %     Divide the current interpret state (true: 1, or false: 0) by
           %     the above value. Dividing, instead of multiplying, has the
           %     effect of reversing the values for '^' and 'V' (and not those
           %     for '<' and '>'), and gives 0 if the interpret state is false 
    *      %     Add the result to the current coordinate, to update it
    T      %     Push interpret state (note that it has been consumed) as true
  ]        %   End
]          % End
x          % Delete interpret state
1Gm        % Is the current coordinate a member of the first input? Gives true
           % or false. Implicit display
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Wow, you beat Charcoal! Incredible answer. \$\endgroup\$ Jun 1 at 22:17
1
\$\begingroup\$

Java 10, 168 bytes

P->C->{var r=0>1;int x=0,y=0,f=9;for(var c:(P+0).getBytes()){r=0>1;for(var t:C)r|=x==t[0]&y==t[1];y+=f<1&r|c%7>3?0:c%6-3;x+=f<1&r|c%9<6?0:c%5-1;f=f<1?9:c%83;}return r;}

Try it online.

Explanation:

P->C->{          // Method with String + 2D int-array parameters & boolean return
  var r=0>1;     //  PrettyPlace-flag, starting at false
  int x=0,y=0,   //  x,y coordinates, starting at 0,0
      f=9;       //  Skip-flag, starting at non-0
  for(var c:(P+0)//  Append a trailing dummy '0' to the path-String (to determine
                 //  if we're at a PrettyPlace after the last input-character)
            .getBytes()){
                 //  Loop over the characters as codepoints:
    r=0>1;       //   Reset the PrettyPlace-flag to false
    for(var t:C) //   Loop over the input-coordinates:
      r|=        //    Check if any is truthy for the PrettyPlace-flag:
         x==t[0]&y==t[1];
                 //     Where an input-coordinate matches the current x,y
    y+=          //   Modify the y-coordinate by increasing with:
       f<1       //    If the skip-flag is 0,
       &r        //    and the PrettyPlace-flag is truthy
       |c%7>3?   //    Or if the current character is 'S'/'^'/'V':
         0       //     Leave y the same by increasing with 0
       :         //    Else (the current character is '<'/'>'):
         c%6-3;  //     Add -1 if '<', or add 1 if '>'
    x+=          //   Modify the x-coordinate by increasing with:
       f<1       //    If the skip-flag is 0,
       &r        //    and the PrettyPlace-flag is truthy
       |c%9<6?   //    Or if the current character is 'S'/'<'/'>':
         0       //     Leave x the same by increasing with 0
       :         //    Else (the current character is '^'/'V'):
         c%5-1;  //     Add -1 if 'V', or add 1 if '^' 
    f=           //   Change the skip-flag to:
      f<1?       //    If the skip-flag was 0 this iteration:
        9        //     Reset it back to non-0
      :          //    Else:
        c%83;}   //     Set it to `c` modulo-83 (0 for 'S', non-0 otherwise)
  return r;}     //  After the loop, return the last PrettyPlace-flag as result

How the magic numbering works for the characters:

Character c c%7>3 c%6-3 c%9<6 c%5-1 c%83
'<' 60 true false -1 60
'>' 62 true false 1 62
'^' 94 false 1 true 11
'V' 86 false -1 true 3
'S' 83 true true 0
\$\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.