あらすじ

RubyKaigi2019でエイチームのブースでライブコーディングをしました。
お題は箱入り娘と呼ばれるパズルの解法探索。

経緯

エイチームブースでパズルを提供したものの、３日間で70名程がチャレンジし散っていく猛者たち。

エイチームブースの様子！みなさん引き続きパズルに悪戦苦闘中！#RubyKagi2019 #rubykaigi pic.twitter.com/OvaGDnDgd4
— 【公式】エイチーム人事広報 (@ateam_jinjikoho) 2019年4月19日

「これ、プログラムで解いたほうが速いんじゃね？」

結果

ライブコーディングチャレンジは失敗。

パズルをLIVEコーディングで解いてみる挑戦！

ごめんなさい。
再度、出直して挑戦します( ´•̥ ω •̥` ) pic.twitter.com/3ZGS8M7YZW
— 【公式】エイチーム人事広報 (@ateam_jinjikoho) 2019年4月20日

失敗した理由

コードが汚くなりすぎてデバッグできなくなった

要因を深掘りしてみよう

一度きりだし、適当に思いつきで書けばいいと考えた
全体的な見通しを立てきらずに見切り発車でデータ構造を作った
何も考えずに深さ優先で再帰したので、どこで何が起こっているか把握しづらくなった

こんなところです。
そして恥ずかしい限りですが、その時のコードを晒す！

汚いコード

resolve_puzzle.rb


# コマの種類
# 0 : ターゲット
# 1,2,3,4 : 1つのやつ
# 11,12,13,14 : 縦長
# 50 : 横長
# 100 : 空白

INITIAL_STATE =
[
  [1,nil,nil,2],
  [11,3,4,12],
  [11,50,50,12],
  [13,0,0,14],
  [13,0,0,14]
]

@dead_ends = []
@states = {}

def is_single?(state, row, col)
  return nil if row < 0 || row > 4 || col < 0 || col > 3
  1 <= state[row][col].to_i && state[row][col].to_i <= 4
end

def is_virtical?(state, row, col)
  return nil if row < 0 || row > 4 || col < 0 || col > 3
  11 <= state[row][col].to_i && state[row][col].to_i <= 14
end

def is_horizonal?(state, row, col)
  return nil if row < 0 || row > 4 || col < 0 || col > 3
  !state[row][col].nil? && state[row][col] == 50
end

def is_square?(state, row, col)
  return nil if row < 0 || row > 4 || col < 0 || col > 3
  !state[row][col].nil? && state[row][col] == 0
end

def next_state_of(state)
  @states[state] ||= detect_next_state(state)
end

def detect_next_state(state)
  blank_spaces = detect_blank_spaces(state)
  next_states = detect_square_moves(state, blank_spaces) +
                detect_horizonal_moves(state, blank_spaces) +
                detect_virtical_moves(state, blank_spaces) +
                detect_single_moves(state, blank_spaces)
  next_states.compact
end

def detect_single_moves(state, blank_spaces)
  states = []
  blank_spaces.each do |row,col|
    states << move(state, row, col-1, :right) if is_single?(state, row, col-1)
    states << move(state, row, col+1, :left) if is_single?(state, row, col+1)
    states << move(state, row-1, col, :down) if is_single?(state, row-1, col)
    states << move(state, row+1, col, :up) if is_single?(state, row+1, col)
  end
  states.compact
end

def detect_virtical_moves(state, blank_spaces)
  states = []
  blank_spaces.each do |row,col|
    if is_virtical?(state, row-1, col)
      tmp_state = move(state, row-1, col, :down)
      states << move(tmp_state, row-2, col, :down)
    end
    if is_virtical?(state, row+1, col)
      tmp_state = move(state, row+1, col, :up)
      states << move(tmp_state, row+2, col, :up)
    end
  end
  row = blank_spaces[0][0]
  col = blank_spaces[0][1]
  if col == blank_spaces[1][1] && row + 1 == blank_spaces[1][0]
    if is_virtical?(state, row, col - 1) && is_virtical?(state, row + 1, col - 1) && state[row][col-1] == state[row+1][col-1]
      tmp_state = move(state, row, col - 1, :right)
      states << move(tmp_state, row + 1, col - 1, :right)
    end
    if is_virtical?(state, row, col + 1) && is_virtical?(state, row + 1, col + 1) && state[row][col+1] == state[row+1][col+1]
      tmp_state = move(state, row, col + 1, :left)
      states << move(tmp_state, row + 1, col + 1, :left)
    end
  end
  states.compact
end

def detect_horizonal_moves(state, blank_spaces)
  states = []
  blank_spaces.each do |row,col|
    if is_horizonal?(state, row, col - 1)
      tmp_state = move(state, row, col - 1 , :right)
      states << move(tmp_state, row, col - 2, :right)
    end
    if is_horizonal?(state, row, col + 1)
      tmp_state = move(state, row, col + 1, :left)
      states << move(tmp_state, row, col + 2, :left)
    end
  end
  row = blank_spaces[0][0]
  col = blank_spaces[0][1]
  if col + 1 == blank_spaces[1][1] && row == blank_spaces[1][0]
    if is_horizonal?(state, row - 1, col)  && is_horizonal?(state, row - 1, col + 1)
      tmp_state = move(state, row - 1, col, :down)
      states << move(tmp_state, row - 1, col + 1, :down)
    end
    if is_horizonal?(state, row + 1, col) && is_horizonal?(state, row + 1, col + 1)
      tmp_state = move(state, row + 1, col, :up)
      states << move(tmp_state, row + 1, col + 1, :up)
    end
  end
  states.compact
end

def detect_square_moves(state, blank_spaces)
  states = []
  row = blank_spaces[0][0]
  col = blank_spaces[0][1]
  if col == blank_spaces[1][1] && row + 1 == blank_spaces[1][0]
    if is_square?(state, row, col - 1) && is_square?(state, row + 1, col - 1)
      tmp_state = move(state, row, col - 1, :right)
      tmp_state = move(tmp_state, row, col - 2, :right)
      tmp_state = move(tmp_state, row + 1, col - 1, :right)
      states << move(tmp_state, row + 1, col - 2, :right)
    end
    if is_square?(state, row, col + 1) && is_square?(state, row + 1, col + 1)
      tmp_state = move(state, row, col + 1, :left)
      tmp_state = move(tmp_state, row, col + 2, :left)
      tmp_state = move(tmp_state, row + 1, col + 1, :left)
      states << move(tmp_state, row + 1, col + 2, :left)
    end
  end
  if col + 1 == blank_spaces[1][1] && row == blank_spaces[1][0]
    if is_square?(state, row - 1, col)  && is_square?(state, row - 1, col + 1)
      tmp_state = move(state, row - 1, col, :down)
      tmp_state = move(tmp_state, row - 2, col, :down)
      tmp_state = move(tmp_state, row - 1, col + 1, :down)
      states << move(tmp_state, row - 2, col + 1, :down)
    end
    if is_square?(state, row + 1, col) && is_square?(state, row + 1, col + 1)
      tmp_state = move(state, row + 1, col, :up)
      tmp_state = move(tmp_state, row + 2, col, :up)
      tmp_state = move(tmp_state, row + 1, col + 1, :up)
      states << move(tmp_state, row + 2, col + 1, :up)
    end
  end
  states.compact
end

# direction : :left, :right, :up, :down
def move(org_state, row, col, direction)
  state = state_copy(org_state)
  return nil unless state[row][col]
  return nil if row < 0 || row > 4 || col < 0 || col > 3
  case direction
  when :left
    return nil if col <= 0 || !state[row][col-1].nil?
    state[row][col - 1] = state[row][col]
    state[row][col] = nil
  when :right
    return nil if col >= 3 || !state[row][col+1].nil?
    state[row][col + 1] = state[row][col]
    state[row][col] = nil
  when :up
    return nil if row <= 0 || !state[row-1][col].nil?
    state[row-1][col] = state[row][col]
    state[row][col] = nil
  when :down
    return nil if row >= 4 || !state[row+1][col].nil?
    state[row+1][col] = state[row][col]
    state[row][col] = nil
  end
  state
end

def show_state(state)
  state.each do |row|
    row.each do |col|
      print col ? "%02d" % col : "**"
      print " "
    end
    print "\n"
  end
end

def state_copy(state)
  copied = []
  state.each do |row|
    new_row = []
    row.each do |col|
      new_row << col
    end
    copied << new_row
  end
  copied
end

def detect_blank_spaces(state)
  blank_spaces = []
  state.each_with_index do |row, row_n|
    next unless row.include? nil
    row.each_with_index do |col, col_n|
      blank_spaces << [row_n, col_n] if col.nil?
    end
  end
  blank_spaces
end

def clear?(state)
  [state[0][1], state[0][2], state[1][1], state[1][2]].all?{|n| n == 0}
end

def recursive_detect(state)
  return if @dead_ends.include? state
  return if @states[state] # 探索済み
  next_states = next_state_of(state)

  @dead_ends << state if next_states.size == 0
  return next_states.find {|s| clear?(s)} if next_states.any? {|s| clear?(s)}
  # raise "cleared!" if next_states.any? {|s| clear?(s)}
  cleared_state = []
  next_states.each do |s|
    result = recursive_detect(s)
    cleared_state += [state, result] if result
    return cleared_state
  end
  cleared_state
end

def show_result(states)
  states.compact.each_with_index do |s, i|
    next if s.empty?
    puts "##{i}"
    show_state(s)
    puts "--------------"
  end
end

cleared_state = recursive_detect(INITIAL_STATE)
show_result cleared_state

次は

ゲームのモデリングをきちんとして再挑戦します。
実施は4/28予定！