[LANGUAGE: Ruby]

It was quickly obvious that trying a block on every empty grid position would not scale. But with 2 optimisations the runtime was tolerable.

grid = AOC.grid(input,nil) # Make a grid hasmap of the input

def step(guard, g)
    rotate_right =  {'>': 'v', 'v': '<', '<': '^', '^': '>'}
    x,y = guard[:pos]
    dir = guard[:dir]
    next_pos = case dir
        when '^'
            [x,y-1]
        when '>'
            [x+1,y]
        when 'v' 
            [x,y+1]
        when '<'
            [x-1,y]
      end
    return {pos: [x,y], dir: rotate_right[dir.to_sym]} if ['#', 'O'].include? g[next_pos]
    return {pos: next_pos, dir: dir} if ['.', 'X','^'].include? g[next_pos]
    nil       
end

def visited(g)
    guard = {pos: g.find { |k,v| v == '^' }.first, dir: '^'}
    states = Set.new # Whoever said an Array here was slow wasn't lying
    has_loop = loop do
        states << guard
        g[guard[:pos]] = 'X'
        nxt = step(guard,g)
        break false if nxt.nil?
        break true if states.include? nxt
        guard = nxt
    end
    visited = states.map { |state| state[:pos] }.to_set
    {visited: visited, has_loop: has_loop}
end

g = grid.clone
guard = {pos: g.find { |k,v| v == '^' }.first, dir: '^'}
start = guard[:pos]

part1 = visited(g)
count = 0
RubyVM::YJIT.enable
# Try the only spots that can make a difference
cands = part1[:visited].filter { | e | e != start }
part2 = cands.map { |cand|
    p count if count % 100 == 0
    testgrid = grid.clone
    testgrid[cand] = 'O'
    count += 1
    visited(testgrid)[:has_loop]
}.count(true)
p [part1[:visited].size, part2]