---
# System prepended metadata

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

---

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

## 第5章 

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

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

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

in JavaScript
```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

```ruby=
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

```

```rb=
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

書いてるところ...
```javascript
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 
```javascript=
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:


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


>[name=teruya]

```ruby=
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]

```ruby=
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