Will this makina program halt?

Question

makina is a cell-based esolang composed of automata which move around a grid. These automata follow paths of instructions that direct their movement. Your task is to, given a makina program using only the below instructions (so a subset of normal makina) as input, output two distinct values depending on whether or not it is a loop. (If program flow comes to an arrow character that it has already visited then the program is a loop.)

Instructions

• ^>v< These instructions (arrows) set the direction of the automaton to the direction they point in.
• I This instruction halts automata going up or down, but does nothing to ones going left or right.
• H This instruction halts automata going left or right, but does nothing to ones going up or down.
• O This instruction does nothing to the automaton, acting like a sort of 4-way intersection.

All other characters (including spaces) halt the automaton, as does exiting the bounds of the program. The automaton starts in the top-left corner going right. You may assume programs are padded by spaces to be rectangular. This is code-golf, so shortest answer wins!

Testcases

Truthy

>>>v
v<<<

OOOv
H<<<
v

>>>v
v<I<
H>^
>^

>>>>v
v <<<

Falsey

>>>v
^<<<

>v
^O<
>^

Answer 1

Python, 182 187 bytes

def f(s):
    i=j=h=0;d=1;v={0}
    while 1:
        if(t:=(i,j,h,d))in v:return 0
        try:c=s[i][j];0/(c-32)/(c&16 or(c&3^h))
        except:return 1
        if c&16:h=c>>6;d=(c>>4&c&2)-1
        v|={t};i+=h*d;j+=d-h*d

Attempt This Online!

Edit: the previous version did return falsey if the automaton visited twice a cell with H or I. Thanks to @tsh for the useful comments on the challenge post.

Brief explanation:

• i and j are the coordinates of the current cell (i is the row index, j is the column index);
• v is the set of the previously visited cells; if the current cell was already in v, it means that the automaton does not halt (hence return 0);
• the try block assigns to c the symbol in the current cell; it also checks if the coordinates refer to a cell present in the input, if the cell contains a space, or if the automaton halts encountering a H or a I;
• h stores the direction of the movement; if h is 0 the automaton is moving horizontally, if h is 1 it is moving vertically;
• d stores the magnitude of the movement, can be -1 or +1

Answer 2

Ruby, 274 233 bytes

->b{b=b.lines.map &:chars;x=y=0;d=[1,0];i={?>=>d,?<=>[-1,0],?^=>[0,-1],?v=>[0,1],?H=>0,?I=>1};loop{a=b[y][x] rescue break;a=~/[><^v]/? (d=i[a];b[y][x]=0): a=~/[IH]/? (break if d[i[a]]!=0): a==?O? 0: a==0? v: break;x,y=x+d[0],y+d[1]}}

Try it online! I've only put a couple test cases in the TIO link because the test cases in the question aren't all sorted correctly. (Some marked falsy are actually truthy.)

Takes a string. Errors if the input doesn't terminate, runs without error (returns nil) if it does. I'm proud of the golfed case statement and use of inline rescue, an arguably useless feature that's only really applicable in an edge case like this. Still trying to figure out how to golf i (a direction lookup hash) as well as optimize control flow in the function itself.

Ungolfed code:

def simulate_makina program
  program = program.chomp.split(?\n).map(&:chars)
  x, y = 0, 0
  dir = [1, 0]
  dirs = {?> => [1, 0], ?< => [-1, 0], ?^ => [0, -1], ?v => [0, 1], ?H => 0, ?I =>1}
    
  loop do
    a = program[y][x] rescue break
    case a
    when /[><^v]/
      dir = dirs[a]
      program[y][x] = 0
    when /[IH]/
      break if dir[dirs[a]] != 0
    when ?O
      0 # nop
    when 0
      v # raises a NameError
    else
      break
    end
    x, y = x + dir[0], y + dir[1]
  end
end

Ruby, 252 211 bytes

->b{x=y=0;d=[1,0];i={?>=>d,?<=>[-1,0],?^=>[0,-1],?v=>[0,1],?H=>0,?I=>1};loop{a=b[y][x] rescue break;a=~/[><^v]/? (d=i[a];b[y][x]=0): a=~/[IH]/? (break if d[i[a]]!=0): a==?O? 0: a==0? v: break;x,y=x+d[0],y+d[1]}}

Alternative answer that takes, instead of a string, a 2d array of characters. Again, errors if the input doesn't terminate and returns if it does. Try it online!

Answer 3

JavaScript, 118 bytes

s=>[x=-1,y=0,d=4,...s+s].every(_=>d=1+'^<v>'.indexOf(c=s.split`
`[y+=(d-2)%2]?.[x+=(d-3)%2])||d*(c=='O'|c=='IH'[d%2]))

This answer disagree with the last 2 testcases.

f=

s=>[x=-1,y=0,d=4,...s+s].every(_=>d=1+'^<v>'.indexOf(c=s.split`
`[y+=(d-2)%2]?.[x+=(d-3)%2])||d*(c=='O'|c=='IH'[d%2]))

t= `
>>>v
v<<<

OOOv
H<<<
v

>>>v
^<<<

>v
^O<
>^

>>>v
v<I<
H>^
>^

>>>>v
v <<<

vv<v<X
>OOOOv
vOOOO<
>OOOOv
XO^<^<
`.trim().split(/\n\n+/);
t.forEach(s => {
  console.log(f(s));
});

Basic idea: A makina program with \$n\$ bytes source code will always terminate in at most \$2n\$ steps or it will never terminate.

Answer 4

Python 3.8 (pre-release), 248 bytes

def h(i):
 p=P=d=0;D=1;v=[]
 while 1:
  try:p+=d;P+=D;r=i[p][P]
  except:return 1
  if[p,P]in v:return 0
  if'H'==r and D or'I'==r and d or'<>^vHIO'.find(r)<0:return 1
  L=r in'<>^v';v+=[[p,P]]*L
  if L:d=r>']'and' v'.find(r);D=r<'?'and' >'.find(r)

Try it online!

Wrong output for fourth falsy case but it seems like the output should in fact be truthy (the automaton hits a space and halts). I am waiting for clarification from the OP on this. Works on all other testcases.

Nothing too complex; just moves around as dictated by the input. The only part of note here is how to check whether to halt at an H or I location. For H, this is done by checking that D, which is the horizontal movement variable, is truthy, because it is truthy if it is not zero, and if it is not zero then the automaton is moving from the left or right. If it is zero then it is moving from the top or bottom. Similar for I but we check d (vertical movement) instead.

+6 bytes to fix bug pointed out by @tsh in comments, which means that the output for the third "falsey" case is now 1. However, it would appear that this is the correct answer.

Answer 5

Charcoal, 56 bytes

ＷＳ⊞υιＰ⪫υ¶Ｗ⊕⌕⪪HIO>^<v¹ＫＫ¿‹ι⁴¿⁼⊖ι﹪φ²⎚Ｍ✳⊗φ«≔ιφ✳⊗φψ»≔ＫＫθ⎚⁼θψ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs - if the program does not halt, nothing if it halts. Explanation:

ＷＳ⊞υιＰ⪫υ¶

Input the instructions and print them to the canvas without moving the cursor.

Ｗ⊕⌕⪪HIO>^<v¹ＫＫ

While the character under the cursor is a valid instruction:

¿‹ι⁴

If this was an intersection-type character, then...

¿⁼⊖ι﹪φ²⎚

... if this intersection should halt the program then clear the canvas, causing the loop to exit, ...

Ｍ✳⊗φ

... otherwise move on through the intersection.

«≔ιφ✳⊗φψ»

Otherwise, update the direction, replace the current character with a null marker and move in the new direction.

≔ＫＫθ⎚⁼θψ

Output whether the cursor landed on a null marker, indicating an infinite loop.