# 問題解決力を鍛える！アルゴリズムとデータ構造

## 日程

2023/01/06

## 第4.4章〜

- 任意参加
- ファシリテーター: Chen

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所

>[name=teruya]

4.4 メモ化

この部分は前回（トリボナッチだけど）メモ化版を作ったので再掲

def memo_trib(num)
  return 0 if num == 0
  return 0 if num == 1
  return 1 if num == 2

  return $memo[num] if $memo[num]

  return $memo[num] = memo_trib(num - 1) + memo_trib(num - 2) + memo_trib(num - 3)
end

num = gets.to_i
$memo = Array.new(num + 1)
# $memo[0] = 0
# $memo[1] = 0
# $memo[2] = 1
puts memo_trib(num)
p $memo

4.5.1 部分和問題

説明を読むと難しく感じるが……再帰でひたすら分岐（数を選ぶ or 選ばない）して行って、
最終的に0を作れるかどうかという問題になる。

4.9

def func(checked_index, rest, nums)
  if checked_index == 0
    return true if rest == 0

    return false
  end

  # nums[checked_index - 1] を選ばない場合
  return true if func(checked_index - 1, rest, nums)

  # nums[checked_index - 1] を選ばない場合
  return true if func(checked_index - 1, rest - nums[checked_index - 1], nums)

  return false
end

nums = [3, 2, 6, 5]
rest = 14
checked_index = nums.size # [3, 2, 6, 5] の1つ外側のindex

puts func(checked_index, rest, nums)

章末問題4.6

nums = [3, 2, 6, 5]
rest = 14

# memo[いくつ目のnumまで調べたか][indexの数値を作れたか]
memo = Array.new(nums.size + 1) { Array.new(rest + 1) {false} }
memo[0][0] = true

puts '実行前'
memo.each { |row| p row.map { |bool| bool ? '⭕️' : '❎'} }
puts

nums.each_with_index do |num, index|
  memo[index].each_with_index do |bool, sum|
    next unless bool

    # num を足さない場合
    memo[index + 1][sum] = true
    # num を足す場合
    memo[index + 1][sum + num] = true if (sum + num) <= rest
  end
end

puts '実行後'
memo.each { |row| p row.map { |bool| bool ? '⭕️' : '❎'} }
puts

puts memo.last.last


>[name=tsujita]

> 4.4 メモ化

いわゆるキャッシュのこと、計算量が減る
再帰の中でうまく使うのがポイントというのはなんとなく理解しました

> 4.6 分割統治法

確かに無意識に使っていた・・！と思ったけど、これをアルゴリズムと認識してロジックに落とし込める自信はないです

>[name=okura]

### 4.4 メモ化して動的計画法へ

キャッシュは効くときと効かないときの差が激しい気がしている。普通にRailsアプリを書いているとあまり意味がないことも多い。

# resultが複数回呼ばれないと効果がない
def result
  @result ||= 'result'
end

# 引数があるのでこれはバグ
def result2(arg)
  @result ||= "result#{arg}"
end

### 4.5 再帰の例(3)：再帰関数を用いる全探索

こっちのほうがビット演算より可読性も高いと思う。「数を選ぶか選ばないかの2通り」をビット演算にエンコードするのは脳の負荷が高い…

### 4.6 分割統治法

分割統治法自体はとても汎用的な解法というか考え方だとは思うので、アルゴリズムが全面に出ない場合でも役に立ちそう。

### 章末問題

メソッドではなくてprocを使うことで変数の数を減らす工夫をしています。procを実行するときは`foo.()`みたいにドットが必要になる。

#### 4.5

うまくいかなかったバージョン。

n = gets.chomp.to_i
digit = n.digits.size

base = [3, 5, 7]
answers = []
0.upto(digit - 2) do |i|
  [3, 5, 7].repeated_permutation(i) do |a|
    result = a.empty? ? base : base + a
    result.permutation do |r|
      answers << r if r.join.to_i <= n
    end
  end
end
answers.uniq!
puts answers.size

ここでの敗因は`permutation`系のメソッドが実は結構重いことなんじゃないかと思っている。`repeated_permutation`を含めたループが3重になっているのがつらい。

うまくいったバージョン。

n = gets.chomp.to_i
digit = n.digits.size

result = 0

check = ->(num) {
  break 0 if num.join.to_i > n
  if num.include?(3) && num.include?(5) && num.include?(7)
    result += 1
  end
  [3, 5, 7].each do |i|
    check.(num + [i])
  end
}

[3, 5, 7].repeated_permutation(3) do |i|
  check.(i)
end

puts result

#### 4.6

a = gets.chomp.split(" ").map(&:to_i)
w = 10000000
cache = {}
check = ->(i, rest) {
  h = [i, rest].hash
  return cache[h] unless cache[h].nil?

  if i.zero?
    rest.zero?
  else
    if check.(i - 1, rest)
      cache[h] = true
    elsif check.(i - 1 , rest - a[i - 1])
      cache[h] = true
    else
      cache[h] = false
    end
  end
}

puts check.(a.size, w)

## 振り返り

>[name=teruya]

二次元DPは図で描けるけど、三次元以上になると描けないので頭がぶっ壊れます

>[name=tsujita]

だんだんちゃんと難しくなってきた・・

> [name=okura]

キャッシュは難しい。
これはあるあるだと思うけど、書いたコードが大規模なデータに耐えられるのかはしばしば実際に大規模なデータを投入してみるまでわからない（そして耐えられない）。

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める（2023/01/06）
-
- 読む範囲を決める
- 第５章2（動的計画法の例題）まで