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

## 第5章

- 5.5と5.6を読む
- 任意参加
- ファシリテーター: hsy

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

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=tsujita]

5,5で力尽きてしまいました・・・・
このサイトを見てました
https://mathwords.net/hensyukyori

def edit_distance(str1, str2)
  m = str1.length
  n = str2.length
  dp = Array.new(m + 1) { Array.new(n + 1) }
  (0..m).each { |i| dp[i][0] = i }
  (0..n).each { |j| dp[0][j] = j }
  (1..m).each do |i|
    (1..n).each do |j|
      dp[i][j] = [dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]].min + 1
      dp[i][j] = dp[i - 1][j - 1] if str1[i - 1] == str2[j - 1]
    end
  end
  dp[m][n]
end

require 'rspec'

describe 'levenshtein_distance' do
  it 'returns 3 for "kitten" and "sitting"' do
    expect(levenshtein_distance("kitten", "sitting")).to eq(3)
  end

  it 'returns 2 for "flaw" and "lawn"' do
    expect(levenshtein_distance("flaw", "lawn")).to eq(2)
  end

  it 'returns 0 for "kitten" and "kitten"' do
    expect(levenshtein_distance("kitten", "kitten")).to eq(0)
  end

  it 'returns 7 for "" and "sitting"' do
    expect(levenshtein_distance("", "sitting")).to eq(7)
  end
end

>[name=hsu]

難しくてyoutubeとみました．．．

https://alchemist-al.com/algorithms/edit-distance

書いてるところ...

function minDistance(word1, word2) {
 let m = word1.length
 let n = word2.length
 let edit
 let dp = Array(n)

  for(let i =0; i < m; i++) {
    dp[i] = Array(m)
    for(let j= 0; j < n; j++) {
      edit =1
      if(word1[i]=== word2[j]) {
        edit = 0
      }
    　　　　　　　　　　　　　
      dp[i][j] = Math.min(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j]+ edit)
   
   }
 }
 return ?
}


console.log(minDistance('a','b'))

chatGPT

function levenshteinDistance(a, b) {
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;
  
  let matrix = [];
  
  for (let i = 0; i <= b.length; i++) {
    matrix[i] = [i];
  }
  
  for (let j = 0; j <= a.length; j++) {
    matrix[0][j] = j;
  }
  
  for (let i = 1; i <= b.length; i++) {
    for (let j = 1; j <= a.length; j++) {
      if (b.charAt(i-1) == a.charAt(j-1)) {
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, matrix[i][j-1] + 1, matrix[i-1][j] + 1);
      }
    }
  }
  
  return matrix[b.length][a.length];
}

This function takes in two strings, a and b, as input and returns an integer representing the Levenshtein distance between the two strings.
You can use it like this:

let distance = levenshteinDistance("kitten", "sitting");
console.log(distance);

>[name=teruya]

T = %w(a l g o r i t h m)
S = %w(l o g i s t i c)
dp = Array.new(S.size + 1) { Array.new(T.size + 1) }

dp[0] = (0..T.size).to_a
(1..S.size).each do |i|
  dp[i][0] = i
end

pp dp

(1..S.size).each do |s_pos|
  (1..T.size).each do |t_pos|
    change_min = S[s_pos - 1] == T[t_pos - 1] ? dp[s_pos - 1][t_pos - 1] : dp[s_pos - 1][t_pos - 1] + 1
    delete_min = dp[s_pos - 1][t_pos] + 1
    insert_min = dp[s_pos][t_pos - 1] + 1

    dp[s_pos][t_pos] = [change_min, delete_min, insert_min].min
  end
end

pp dp

=> 
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
 [1, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [2, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [3, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [4, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [5, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [6, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [7, nil, nil, nil, nil, nil, nil, nil, nil, nil],
 [8, nil, nil, nil, nil, nil, nil, nil, nil, nil]]
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
 [1, 1, 1, 2, 3, 4, 5, 6, 7, 8],
 [2, 2, 2, 2, 2, 3, 4, 5, 6, 7],
 [3, 3, 3, 2, 3, 3, 4, 5, 6, 7],
 [4, 4, 4, 3, 3, 4, 3, 4, 5, 6],
 [5, 5, 5, 4, 4, 4, 4, 4, 5, 6],
 [6, 6, 6, 5, 5, 5, 5, 4, 5, 6],
 [7, 7, 7, 6, 6, 6, 5, 5, 5, 6],
 [8, 8, 8, 7, 7, 7, 6, 6, 6, 6]]

>[name=okura]

書くことがない（多分本の内容もよくわかっていない）

[アルゴリズム図鑑](https://apps.apple.com/jp/app/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%9B%B3%E9%91%91/id1047532631)がほしくなる。

https://ruby-doc.org/stdlib-3.0.1/libdoc/minitest/rdoc/Minitest/Benchmark.html

## 振り返り
>[name=tsujita]

先週のペアプロがなかったら今日は1mmもわからなかったと思います

>[name=hsu]

good AI

>[name=teruya]

また今日も二次元DPで頭がバグりました

> [name=okura]

require 'matrix'
require 'benchmark/ips'

a = Array.new(100) { Array.new(100) { rand } }
m = Matrix.build(100) { rand }

Benchmark.ips do |x|
  x.report("Matrix#each") do
    m[10, 10]
  end
  x.report("2 dimension array") do
    a[10][10]
  end

  x.compare!
end

Warming up --------------------------------------
         Matrix#each     1.116M i/100ms
   2 dimension array     2.184M i/100ms
Calculating -------------------------------------
         Matrix#each     11.188M (± 3.0%) i/s -     56.941M in   5.094470s
   2 dimension array     21.457M (± 2.3%) i/s -    109.182M in   5.091213s

Comparison:
   2 dimension array: 21457462.7 i/s
         Matrix#each: 11188067.8 i/s - 1.92x  (± 0.00) slower

【悲報】Matrixさん、遅い

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- chen
- 読む範囲を決める
- 6.1 , 6.2