# frozen_string_literal: true
require 'set'

def array_to_puzzle(list)
  Array.new(9) { |i| list[i] << (i * 4) }.inject(:+)
end

def puzzle_point(puzzle, point)
  puzzle & (0xF << point)
end

def clear_point(puzzle, point_list)
  point_list.inject(puzzle) do |acc, point|
    acc & ~(0xF << point)
  end
end

def find_zero_point(puzzle)
  0.step(32, 4).find { |point| puzzle_point(puzzle, point).zero? }
end

checked_puzzles = Set.new
current_puzzles = Set.new

input_puzzle = array_to_puzzle(Array.new(3) { gets.split.map(&:to_i) }.flatten)
current_puzzles.add(input_puzzle)
count = 0

goal_puzzle = array_to_puzzle([1, 2, 3, 4, 5, 6, 7, 8, 0])

loop do
  next_puzzles = Set.new
  current_puzzles.each do |puzzle|
    if puzzle == goal_puzzle
      puts count
      exit
    end

    zero_point = find_zero_point(puzzle)
    y, x = (zero_point / 4).divmod(3)
    if x != 2
      next_puzzles.add(clear_point(puzzle, [zero_point, zero_point + 4]) |
                       (puzzle_point(puzzle, zero_point + 4) >> 4))
    end
    if x != 0
      next_puzzles.add(clear_point(puzzle, [zero_point, zero_point - 4]) |
                       (puzzle_point(puzzle, zero_point - 4) << 4))
    end
    if y != 2
      next_puzzles.add(clear_point(puzzle, [zero_point, zero_point + 12]) |
                       (puzzle_point(puzzle, zero_point + 12) >> 12))
    end
    if y != 0
      next_puzzles.add(clear_point(puzzle, [zero_point, zero_point - 12]) |
                       (puzzle_point(puzzle, zero_point - 12) << 12))
    end
  end
  checked_puzzles.merge(current_puzzles)
  current_puzzles = next_puzzles - checked_puzzles
  count += 1
end