Help us understand the problem. What is going on with this article?

箱入り娘をプログラムで社会に送り出す(結果:引きこもった)

あらすじ

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

image.png

経緯

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


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

結果

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

失敗した理由

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

要因を深掘りしてみよう

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

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


汚いコード
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予定!

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした