未経験者にプログラミングを教えて得られた知見と反省点

ちょっと前にプログラミングを勧めた

地元の後輩が何をしていいか分からず悩んでいるとのことで
「とりあえず損することはないからプログラミングをやっといたら?」
と責任があるのか無責任なのか分からない一言を発する

プログラミングを勧めている理由は
自身も情報学科ではなかったが独学でプログラミングを学習して世界変わったなと思っているため

これが約3ヶ月前のこと
入門しやすい

• python
• ruby
• vba

あたりをやればいいんじゃないかな?と細々と伝えたつもりが
なぜかJavaを選択(同期の友人が情報学科でJavaを勧められたそう)
組み込みとかやりたいなら、まぁいっかとは思いつつも
大学で授業受けたりするわけでもなく独学でのファースト言語がJavaだとつまずきそうだなぁ~と思ってた
(別にJavaをディスってるいるわけではないのでご了承ください)

1ヶ月ぐらいは適度に連絡を取り、状況報告を受けていた
基礎の文法が終わって今からポートフォリオ(自作のRPGだそう)を作り出すというところですという連絡が最終連絡だった
それから音沙汰なし。こちらから連絡するも返事は無かった

しかし、2ヶ月ぐらい経った頃、再び彼と会う機会があったので現状の確認がてら話を聞いてみた(Aとしとく)

僕「最近の学習の調子はどうなのよ?」
A「いや、正直飽きてしまいました」
(やっぱりな〜)
僕「何が面白くなかった?」
A「あっちをいじるとこっちがダメになって訳の分からないエラーが出ての繰り返しで...」
A「あと完成見えなくてモチベーションが保てません」

だいたい以下のどれかにつらみを感じて継続不可になる
いい感じに初学者あるあるにハマってるなと

• 入門言語の難易度の問題(学習コスト)
• 学び方の問題
• モチベーションの保ち方(進め方)の問題

Aの場合は
=> 入門言語の難易度の問題 から モチベーションの保ち方(進め方)の問題 へのリレーだった

そんなこんな話を聞いて一度、Pythonを教えてみることになった
以下、Pythonの入門記事ではないのでさらっと流してください

何を教えたのか

プログラミング言語のレクチャーで何に触れたのかをざっくりとまとめる
完全な初心者ではないものの、一度0からやりたいとのことだった

hello world
最も基本的な値の表示

print("hello world!")

値の型について
値には種類があるんやで〜という話

num = 3 #integer
text_val = "hello world" #string
f_num = 3.14 #float
is_match = True #bool

演算子
基本的なものだけ

5+6 #11
3.14 * 2 #6.28
"hello" + " world" #hello world
5 > 4 #True
5 < 4 #False
"hello" == "hello" #True
"hello" != "hello" #False

ifの文法

num = 10
if num > 5:
  print("over")
else:
  print("lower")

num = 5
if num > 5:
  print("over")
elif num == 5:
  print("equal")
else:
  print("lower")

この時点で一度、FizzBuzzを解かせてみる
ifの判定順(3かつ5の倍数=15の倍数か)に悩むものの、割とすんなり解いてくれた
%演算については事前に教えた

num = 15

if num % 15 == 0:
  print("FizzBuzz") #FizzBuzz
elif num % 3 == 0:
  print("Fizz")
elif num % 5 == 0:
  print("Buzz")
else:
  print(num)

配列について
まず、こういうのやめようなって話をした
なぜ配列が必要なのかを伝えたかった

score1 = 98
score2 = 40
score3 = 89
score4 = 100
score5 = 32
:
:
score100 = 54

配列使おうぜ

nums = [1,2,3,4,5]
fruits = ["apple", "banana", "peach", "orange"]
any = [True, None, 1, "banana", 3.14]

#値の取得(indexは0から始まる)
nums[0] #1
nums[4] #5
nums[5] #error!

思った通り、配列から値を全部取り出すにはどうすればええですか?と質問が来る
forってのがあると自然な流れでループ処理に行けた

forの文法について
ざっくりと

nums = [1,2,3,4,5]

for num in nums:
  print(num)

# 1
# 2
# 3
# 4
# 5

for i in range(0, 4):
  print(i)

# 0
# 1
# 2
# 3

for i in range(4):
  print(i)


# 0
# 1
# 2
# 3

さっきのFizzBuzzをfor組み合わせて書かせたくなったので
range(101)でFizzBuzzをやってもらった
また後で詳細は記述するがこの時点で割とつまっていた
20分ぐらいして上手く動く

for num in range(101):
  if num % 15 == 0:
    print("FizzBuzz") #FizzBuzz
  elif num % 3 == 0:
    print("Fizz")
  elif num % 5 == 0:
    print("Buzz")
  else:
    print(num)

# FizzBuzz
# 1
# 2
# Fizz
# 4
# Buzz
# Fizz

関数について&文法
時間も差し迫っていたので最後に関数について触れた
まずは関数が何なのかという説明をする(厳密な定義ではない)

#関数って何? => 値をもらったらその値を変化/変換するやつ

def add_10(x):
  return x + 10
  
#もらった値に+10変化(変換)している
print(add_10(10))

def greet(user):
  res = "hello " + user
  return res
  
#user名にhelloを付与
print(greet("okb"))

総まとめ

最後にFizzBuzzのfor内の処理を関数化してもらった
この部分でもかなりつまった

def fizzbuzz_func(num):
  if num % 15 == 0:
    return "FizzBuzz"
  elif num % 3 == 0:
    return "Fizz"
  elif num % 5 == 0:
    return "Buzz"
  else:
    return num

for num in range(0, 101):
  print(fizzbuzz_func(num))

#結果省略

1日で行なったことをまとめると

• 値の出力
• 変数と型について
• 演算子
• ifの文法
• FizzBuzz
• 配列
• forの文法
• 関数についてと文法
• FizzBuzzの関数化
• 他、いくつか例題

と割と盛りだくさんだった
この学習を通して何度かプログラミングを教える難しさを感じたので
前振りが長くなったが共有をしていく

print関数とかlen関数ってどこから呼ばれてるの? どこに書かれているの?

自分で関数を実装するようになって何度か聞かれた
どこにもprint()やらlen()を記述していないのになぜこれらのメゾットが使えるのかが分からないと言われた

def add_10(x):
  return x + 10

#どこにある?
#def print(val):
#:
#:
#:

print(add_10(5)) #15
#このprintはどこから呼ばれてるの!?

自分の中では「そういうもの、用意されているもの」という認識だったが
これが腑に落ちないらしい

この言語にはこういうメゾットがあって...という説明をすることで分かってもらえた
車を運転するのに内部構造を100％理解している必要はないのと同じことだが
低レイヤーの知識も説明できる程度に必要だと反省

書いた関数が実行されない

関数を遊びで作っている時に言われた

def greet(name):
  print("hello " + name)
  return True

「今、実装した関数が動かないんですが...」と言われコードを見てみると
関数の呼び出しが見つからなかった
これが書いてるだけで

def greet(name):
  print("hello " + name)
  return True

greet("okb")

という記述がない
これは関数は呼び出して初めて実行されるという認識が無かったために起きた

関数に取り組むまで単純なコードしか書いておらず
コードは上から下に順番に実行されるものだと(半分正解)思わせてしまった
関数は呼び出して初めて実行されるということをきちんと説明するべきだった

配列や関数の使い所がイメージできない

配列やら関数の文法を一通り、教えた後に例題に取り組んでいる時に発生した
書き方を知ったところで使い方が全くイメージできないとのこと

「配列や関数が便利なのは分かるが、じゃあ使うべきっていう境界線はどこにあるの?」

確かに。明確に言語化しようとするとかなり難しい
そもそも僕はプログラミングの記述に推奨はあっても100&の正解はないと思っている
同じ命題に対しても記述されたコードは余程のことがない限りは一致しない

完全パターンなんてものは存在しないため、「やってる内に分かってくるよ」としか言えなかった
自分の頭の中には「〜この時に使うべき」というべきレシピパターンがあるが言語化は出来ない

過去に自分が書いたコードを見せて、こういうところで使ったでと実物を見せてあげねばと反省
しかし、複雑すぎるものや可読性の悪いものを用意すると混乱を招くので要注意

総評

まぁ分かるけどピンとこない

今思えば、車を作るために各パーツの勉強をするのと
車を作ることを知らずに各パーツの勉強をするのとでは圧倒的に気持ちに差がでるなと思った

プログラミング教育では文法やお作法について最初に取り組むことが多いが
その前に、これからやることをマスターすることで最終的にこういったことが出来るようになります
ということを提示してあげられればと思った

理想形は先に作成物が決まっていて、文法を覚えながら作成物完成までのステップを辿っていくような
ディアゴスティーニのような形

これも個人によって好き嫌いが分かれるので用意するのは難しい

個人的所感をまとめておくと

• 文法のゴリ押しはNG
• 知ってる前提で話さない

またAにPythonを教える機会がありそうなので適宜、レポートをまとめたいと思う

【実装コード有り】Elixirで近しいデータを予想するためにk近傍法を実装した

k近傍法とは

ざっと説明するとAというデータとBというデータが
どれだけ近しいかを予測するためのアルゴリズム
仕組みは超簡単で以下のようなデータがあったとする

size(大きさ)は1~5の5段階
is_red(見た目)は1~5の5段階
has_seed(種があるかないか)は0or1

apple = %{size: 2, is_red: 5, has_seed: 0}
water_melon = %{size: 5, is_red: 1, has_seed: 1}

まずこのappleとwater_melonの2つのデータの距離(どれだけ似ているか)を計算する
値が小さければ小さいほど距離が近いということになる
算出にはシンプルに三角比でお馴染みのピタゴラスの定理を使う
ユークリッド距離と呼ばれているらしい

Elixirで計算してみると以下のようになる

• :math.pow() : 乗数を算出するErlangメゾット
• :math.sqrt() : 平方根を算出するErlangメゾット

sum_val = :math.pow(2-5, 2) + :math.pow(5-1, 2) + :math.pow(0-1, 2)
dis = :math.sqrt(sum_val)

iex> dis
5.0990195135927845

試しに青リンゴのデータを用意して距離を算出してみる

blue_apple = %{size: 3, is_red: 1, has_seed: 0}
sum_val = :math.pow(2-3, 2) + :math.pow(5-1, 2) + :math.pow(0-0, 2)
dis = :math.sqrt(sum_val)

iex> dis
4.123105625617661

さきほどよりは小さくなったが色の特徴量の数値が値に大きく影響しているのが分かる
(特徴量選択や正規化には触れない)

appleとの距離の算出結果が複数個あるとする(label: 分類名, dis: 距離)

cal_res = [
  %{label: :apple, dis: 1.0},
  %{label: :water_melon, dis: 5.0},
  %{label: :water_melon, dis: 2.0},
  %{label: :apple, dis: 2.5},
  %{label: :apple, dis: 1.5},
]

k近傍法では距離の値の小さいものからk個取得して多数決をとる
k = 3としてデータを取得する

fetch_data = [
  %{label: :apple, dis: 1.0},
  %{label: :water_melon, dis: 2.0},
  %{label: :apple, dis: 1.5},
]

取得したデータのラベルをまとめると

[:apple, :water_melon, :apple]

となり、このデータで多数決を取ると最終的な予想結果はappleとなる

Elixirでの実装

与えるデータがappleとorangeのどちらに似ているかを予想させてみる

fruits = [
  %{size: 2, is_red: 2, label: :orange},
  %{size: 2, is_red: 3, label: :orange},
  %{size: 4, is_red: 4, label: :apple},
  %{size: 1, is_red: 1, label: :orange},
  %{size: 5, is_red: 5, label: :apple},
  %{size: 3, is_red: 4, label: :apple},
]

#このデータはapple? orange?
target_data = %{size: 4, is_red: 3}

#取得する値の数(k)
knn_neighbor_num = 3

まずは全体のコードと結果を表示

defmodule KNN do
  def main(target_data, datas, knn_neighbor_num) do
    calc_res = calc_distance(target_data, datas, knn_neighbor_num)
    count_res = count_common_val_in_lst(calc_res)
    Enum.reduce(Map.keys(count_res), fn x, accum -> 
      if count_res[x] > count_res[accum] do
        x
      else
        accum
      end
    end)
  end
  def calc_distance(target_data, datas, knn_neighbor_num) do
    datas
      |> Enum.map(fn row ->
          calc_res = Enum.map(Map.keys(target_data), fn z -> :math.pow((target_data[z] - row[z]),2) end)
          %{score: :math.sqrt(Enum.sum(calc_res)), label: row[:label]}
        end)
      |> Enum.sort_by(&(&1.score))
      |> Enum.slice(0..knn_neighbor_num-1)
      |> Enum.map(&(&1.label))
  end

  def count_common_val_in_lst(lst), do: _count_common_val_in_lst(lst, %{}, [])
  defp _count_common_val_in_lst([], accum, _), do: accum
  defp _count_common_val_in_lst([head | tail], accum, labels) do
    case Enum.member?(labels, head) do
      true ->
        n_accum = Map.put(accum, head, accum[head]+1)
        _count_common_val_in_lst(tail, n_accum, labels)
      false -> 
        n_accum = Map.put(accum, head, 1)
        _count_common_val_in_lst(tail, n_accum, labels ++ [head])
    end
  end
end

IO.puts(KNN.main(target_data, fruits, knn_neighbor_num))
#apple

与えたデータはk近傍法ではappleと予想された
確かに、fruitsのデータと比べてみるとappleっぽい(適当

各関数について

calc_distance

ターゲットデータとその他(今回でいうとfruits)の距離の算出を行なっている
特徴量の数は変動するのでターゲットデータからkeyを生成するようにした
パイプとEnumめっさ使ってElixirっぽく書けた気がする

def calc_distance(target_data, datas, knn_neighbor_num) do
  datas
     |> Enum.map(fn row ->
        #列挙したデータとターゲットデータの距離を算出
        calc_res = Enum.map(Map.keys(target_data), fn z -> :math.pow((target_data[z] - row[z]),2) end)
        %{score: :math.sqrt(Enum.sum(calc_res)), label: row[:label]} 
      end)
    |> Enum.sort_by(&(&1.score)) #scoreの順にリストinマップをソート
    |> Enum.slice(0..knn_neighbor_num-1) #上位k個だけを取得
    |> Enum.map(&(&1.label)) #keyがラベルの値(appleとかorange)を返す
end

count_common_val_in_lst

calc_distanceの戻り値を使って各ラベルがいくつあるのかをカウントする
[apple, apple, banana, orange, orange, apple]というデータからは

res = %{
  apple: 3,
  banana: 1,
  orange: 2
}

というようなマップを生成する

def count_common_val_in_lst(lst), do: _count_common_val_in_lst(lst, %{}, [])
defp _count_common_val_in_lst([], accum, _), do: accum
defp _count_common_val_in_lst([head | tail], accum, labels) do
  #labels(記入したラベルを保持するためのaccum)にheadが存在しているかどうか
  case Enum.member?(labels, head) do
    true ->
      n_accum = Map.put(accum, head, accum[head]+1) #指定のラベルがkeyの値を上書き
      _count_common_val_in_lst(tail, n_accum, labels)
    false -> 
      n_accum = Map.put(accum, head, 1) #新規のラベルをkeyとして作成して1をセット
      _count_common_val_in_lst(tail, n_accum, labels ++ [head])
  end
end

main

上の2つの関数を組み合わせてcountしたmapを作成して
その値から一番カウントが大きな値を返す

def main(target_data, datas, knn_neighbor_num) do
  calc_res = calc_distance(target_data, datas, knn_neighbor_num)
  count_res = count_common_val_in_lst(calc_res)
  Enum.reduce(Map.keys(count_res), fn x, accum -> 
    if count_res[x] > count_res[accum] do
      x
    else
      accum
    end
  end)
end

データはこんな感じで変化していく

#calc_distance
calc_res =[
  %{score: 1, labels: apple},
  %{score: 4, labels: orange},
  %{score: 2, labels: apple},
]

#count_common_val_in_lst
count_res = %{
  apple: 2
  orange: 1
}

#last return
--> apple

可能な限りEnum.reduceとかでやりたい反面、中々上手くいかずに再帰関数を使うハメになる
個人的にaccumを2つもてるEnum.reduce_neo()みたいなのを作ろうと思った

【実装コード有り】Elixirでタイポ発見器を最長共通部分列を使って作る

プログラムでタイプミスを修正する難しさ

以下のような変数があったとする
user_input_textは自身で入力したテキストで"apple"と入力したつもりが
間違えて"anpple"と入力してしまっている

user_input_text = "anpple"
answer_text = "apple"

他にもタイプミスはいろんなパターンが考えられる

"aple"
"aale"
"applue"
"apule"

少し大袈裟なものもあるが、人間視点でいえば
「あ、こいつはappleって打ちたかったんやな〜」ってことが何となく分かる
従って添削する場合にappleと修正してあげれば良い

しかし、機械視点ではタイプミスから共通のパターンを見つけて修正するのは難しい

"aple" => "apple"
"aale" => "apple"
"applue" => "apple"
"apule" => "apple"

こんな時に使えるのが最長共通部分列たるもの

最長共通部分列とは

説明するよりも結果見た方が早いので"apple"と"anpple"の最長共通部分列を求めてみる
まずはこんな感じのテーブルを用意

wrong/answer	a	n	p	p	l	e
a	-	-	-	-	-	-
p	-	-	-	-	-	-
p	-	-	-	-	-	-
l	-	-	-	-	-	-
e	-	-	-	-	-	-

まずはのanswerの"apple"の"a"から見ていく
"a"の視点で行に"a"があった場合に、"a"の行に1で埋め込む

wrong/answer	a	n	p	p	l	e
a	1 #発見	1	1	1	1	1
p	-	-	-	-	-	-
p	-	-	-	-	-	-
l	-	-	-	-	-	-
e	-	-	-	-	-	-

さらにwrongのa列を調査済みにするために1で埋め込む

wrong/answer	a	n	p	p	l	e
a	1	1	1	1	1	1
p	1	-	-	-	-	-
p	1	-	-	-	-	-
l	1	-	-	-	-	-
e	1	-	-	-	-	-

この作業を繰り返し行う
値が一致しない場合は現在の最大値(この場合では1)を埋め込む

wrong/answer	a	n	p	p	l	e
a	1	1	1	1	1	1
p	1	1	2	2	2	2
p	1	1	2	-	-	-
l	1	1	2	-	-	-
e	1	1	2	-	-	-

wrong/answer	a	n	p	p	l	e
a	1	1	1	1	1	1
p	1	1	2	2	2	2
p	1	1	2	3	3	3
l	1	1	2	3	-	-
e	1	1	2	3	-	-

wrong/answer	a	n	p	p	l	e
a	1	1	1	1	1	1
p	1	1	2	2	2	2
p	1	1	2	3	3	3
l	1	1	2	3	4	4
e	1	1	2	3	4	-

wrong/answer	a	n	p	p	l	e
a	1	1	1	1	1	1
p	1	1	2	2	2	2
p	1	1	2	3	3	3
l	1	1	2	3	4	4
e	1	1	2	3	4	5

これでテーブルの埋め込みは完了 テーブルの最大値が最長共通部分列となる
今回は最長共通部分列が5となった

正解テキストが"banana"の場合はどうなるか
埋め込み過程については同作業なので省略

text	a	n	p	p	l	e
b	0	0	0	0	0	0
a	0	0	0	0	0	0
n	0	0	0	0	0	0
a	0	0	0	0	0	0
n	0	0	0	0	0	0
a	0	0	0	0	0	0

こんな感じの算出をプログラムで行いたい

Elixirでの実装

先にコードと結果をお見せします
Enum.reduce使ってスマートに書けないなぁと色々と試行錯誤したものの断念
アキュムレーターを2つ持たせられたり、条件に一致したら列挙を中止するなどがEnumでできたら嬉しい

defmodule Sample do
  def main(input_val, ans_val) when input_val == ans_val, do: :good
  def main(input_val, ans_val), do: _main(String.graphemes(input_val), ans_val, 0)
  defp _main([], _, counter), do: counter
  defp _main([head | tail], ans_val, counter) do
    str_lst = String.graphemes(ans_val)
    [_n_head | n_tail] = str_lst
    case type_judge(str_lst, head) do
      :hit -> _main(tail, List.to_string(n_tail), counter+1)
      :empty -> _main(tail, List.to_string(n_tail), counter)
    end
  end
  
  def type_judge([], _), do: :empty
  def type_judge([head | tail], compare_str) do
    if String.contains?(compare_str, head) do
      :hit
    else
      type_judge(tail, compare_str)
    end
  end
end

簡単なテストの実行をしてみる

tests = [
  Checker.main("apple", "anpple") == 5,
  Checker.main("apple", "apple") == :good,
  Checker.main("banana", "anpple") == 0,
  Checker.main("banana", "anapple") == 1,
  Checker.main("fish", "fosh") == 3
]

IO.inspect(tests)
#result:
#[true, true, true, true, true]

良い感じですね
動作に関しては問題なさげだけど、もっとシンプルなコードにしたい

コードの解説

main関数

#入力と答えの候補が一致している場合は終了
def main(input_val, ans_val) when input_val == ans_val, do: :good

#文字列をリストに変換して_mainに渡す
def main(input_val, ans_val), do: _main(String.graphemes(input_val), ans_val, 0)
defp _main([], _, counter), do: counter
defp _main([head | tail], ans_val, counter) do
  #正解テキストをリストに変換
  str_lst = String.graphemes(ans_val)
  #次の再帰用に先頭文字列を削除(スライスでやれればいいが...)
  [_n_head | n_tail] = str_lst
  case type_judge(str_lst, head) do
    :hit -> _main(tail, List.to_string(n_tail), counter+1)
    :empty -> _main(tail, List.to_string(n_tail), counter)
  end
end

type_judge
コードに関しては説明することは特になし
貰った文字列同士が一致しているか調べてるのみ
一致した場合に再帰せずに終了

def type_judge([], _), do: :empty
def type_judge([head | tail], compare_str) do
  if String.contains?(compare_str, head) do
    :hit
  else
    type_judge(tail, compare_str)
  end
end

今思えばこれただの「==」でよかったなと
思った通り、普通に動いてる

def type_judge([], _), do: :empty
def type_judge([head | tail], compare_str) do
  if compare_str == head do
    :hit
  else
    type_judge(tail, compare_str)
  end
end

tests = [
  Checker.main("apple", "anpple") == 5,
  Checker.main("apple", "apple") == :good,
  Checker.main("banana", "anpple") == 0,
  Checker.main("banana", "anapple") == 1,
  Checker.main("fish", "fosh") == 3
]

IO.inspect(tests)
#result:
#[true, true, true, true, true]

【実装コード有り】ElixirのMapSet(集合)の使い方と集合カバー問題を解くまで

Setは非推奨

元々、Elixirに実装されていたSetという集合のモジュールは現在、非推奨となっており
MapSetを使ってくれよなと公式が言っている

なのでよほどの理由がない限りはMapSetを使えばいいんじゃないかなと

MapSetの使い方

MapSetモジュールを使うことで集合を表現することが可能
集合はリストと異なり

• 同じデータを持つことができない

という特徴がある

lst = [1,1,2,3,4,4,5,6,7] #重複ok
set_ = [1,2,3,4,5,6,7] #重複は許可されない

新規集合の作成
MapSet.newメゾットを使うことで作成可能

iex> new_set = MapSet.new([1,2,3])
#MapSet<[1, 2, 3]>

#値の型は自由っぽい
iex> new_set = MapSet.new([:a, 1, false])
#MapSet<[1, :a, false]>

既存の集合への追加
MapSet.putメゾットを使う

new_set = MapSet.new([1,2,3])
iex> MapSet.put(new_set, 4)
#MapSet<[1, 2, 3, 4]>

集合同士の結合(和集合)
MapSet.unionメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,4,5])

iex> MapSet.union(a_set, b_set)
#MapSet<[1, 2, 3, 4, 5]>

集合同士の引き算(差集合)
MapSet.differenceメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,4,5])

#[1,2,3] - [2,4,5] ([4,5]はa_setに存在しないので影響なし)
iex> MapSet.difference(a_set, b_set)
#MapSet<[1, 3]>

両方の集合に含まれている要素を求める(積集合)
MapSet.intersectionメゾットを使う

a_set = MapSet.new([1,2,3])
b_set = MapSet.new([2,3, 4,5])

iex> MapSet.intersection(a_set, b_set)

集合の大きさの取得
MapSet.sizeメゾットを使う

a_set = MapSet.new([1,2,3])
iex> MapSet.size(a_set)
3

こいつで何ができるのか

一例として集合カバー問題というテーマに取り組む
これから以下の地域にそれぞれ野菜を届ける必要がある

#岐阜, 愛知, 三重, 京都, 静岡
delivery_regions = MapSet.new([:gihu, :aichi, :mie, :kyoto, :shizuoka])

現在、この地域に配達可能な業者が以下の5つ
それぞれの集合には配達可能な地域を記述してある

companies = %{
  neko: MapSet.new([:gihu, :mie, :shizuoka]),
  inu: MapSet.new([:mie, :kyoto]),
  saru: MapSet.new([:gihu, :kyoto, :aichi]),
  kani: MapSet.new([:mie, :aichi]),
  tori: MapSet.new([:aichi, :kyoto])
}

現状では全5地域に配達可能な企業がないため複数の企業に配達を依頼する必要がある
ではどの組み合わせを考えれば最も少ない企業数で配達が可能か
これが集合カバー問題といわれるものの一例です

Elixirでの実装

先にコードと実行結果をお見せします

defmodule Algo do
  def set_optimizer(delivery_regions, stations), do: _set_optimizer(delivery_regions, stations, MapSet.new())
  defp _set_optimizer(delivery_regions, stations, accum) do
    case delivery_regions == MapSet.new() do
      true -> accum
      false ->
        {best, states_coverted} = _set_update(delivery_regions, stations, Map.keys(stations), nil, MapSet.new())
        _set_optimizer(MapSet.difference(delivery_regions, states_coverted), stations, MapSet.put(accum, best))
    end
  end
  
  defp _set_update(_, _, [], best, accum), do: {best, accum}
  defp _set_update(need, stations, [head | tail], best, accum) do
    coverd = MapSet.intersection(need, stations[head])
    case MapSet.size(coverd) > MapSet.size(accum) do
      true -> _set_update(need, stations, tail, head, coverd)
      false -> _set_update(need, stations, tail, best, accum)
    end
  end
end

結果では:nekoと:saruの業者に頼むが良いと出ている
確かにそうだね

delivery_regions = MapSet.new([:gihu, :aichi, :mie, :kyoto, :shizuoka])
companies = %{
  neko: MapSet.new([:gihu, :mie, :shizuoka]),
  inu: MapSet.new([:mie, :kyoto]),
  saru: MapSet.new([:gihu, :kyoto, :aichi]),
  kani: MapSet.new([:mie, :aichi]),
  tori: MapSet.new([:aichi, :kyoto])
}
res = Algo.set_optimizer(delivery_regions, companies)
IO.inspect(res)
#result: #MapSet<[:neko, :saru]>

#全ての地域が含まれている
#:neko => [:gihu, :mie, :shizuoka]
#:saru => [:gihu, :kyoto, :aichi]

このモジュールは2つの再帰で動かしている
set_optimizerの関数で配達したい地域が全て満たされているかを判定させており
そうでない場合に再び再帰が行われる

set_optimizer

def set_optimizer(delivery_regions, stations), do: _set_optimizer(delivery_regions, stations, MapSet.new())
  defp _set_optimizer(delivery_regions, stations, accum) do
    #第1引数(配達したい地域)が空なら終了
    case delivery_regions == MapSet.new() do
      true -> accum
      false ->
        {best, states_coverted} = _set_update(delivery_regions, stations, Map.keys(stations), nil, MapSet.new())
        #_set_updateの結果を配達したい地域から引く
        _set_optimizer(MapSet.difference(delivery_regions, states_coverted), stations, MapSet.put(accum, best))
    end
end

_set_update

defp _set_update(_, _, [], best, accum), do: {best, accum} #companiesの列挙が終わった時に終了
defp _set_update(need, stations, [head | tail], best, accum) do
  #accum(1つ前の値)との差分をみる
  coverd = MapSet.intersection(need, stations[head])
  case MapSet.size(coverd) > MapSet.size(accum) do
    true -> _set_update(need, stations, tail, head, coverd) #頼む業者を更新&配達可能地域を保持
    false -> _set_update(need, stations, tail, best, accum) #更新なし
  end
end

こんなところでしょうか
最近の悩みはifとcaseの使い分けどうしようかという問題
今回のようなtrue, falseだけの単純な分岐ではifを使うべきとは思いつつも
個人的な可読性についてはcaseの方が上かなと

ただunlessには人権がない

Elixirでダイクストラ法を実装して最短経路を求めるまで

グラフと最短経路

こんなグラフのネットワークがあったとする

Start, A, B, Goalをそれぞれノードといい
6,2,3...のような数字をエッジの重み(ここでは距離)という

StartからGoalへの最短経路は見て分かるように

Start -> B -> A -> Goal

になるかと思う

これがこのグラフでのStartからGoalへの最短経路となる

ではこの最短経路をアルゴリズム使って求められへんの？っていう賢い人が現れる
それで開発されたのがダイクストラ法というアルゴリズム

しかし説明をすると長くなる & 図が大量に必要なので省略する
(すでに書籍や先駆者の有志の方が最高に分かりやすい説明をしてくださっているため)

「ダイクストラ法　解説」　などで検索してみてください

データ構造について

まずはデータの構造を定める
ここ数日、アルゴリズムの実装をして感じていることは
アルゴリズムのロジックを組む際の難易度はデータ構造に大きく依存するということ

シンプルなデータ構造で表現できた場合にはコードはあまり複雑にならない
データ構造に無駄があったり、欠陥があるとその分、コード部分で苦労をする

「このデータ構造が最もふさわしい」というベストアンサーは決めにくいが
シンプルであればシンプルであるほど良いというのが自分の中での答えかなと思ってます

ダイクストラ法に必要な3つのデータ

• グラフ情報(graph)
• コスト情報(costs)
• 親ノード情報(parents)

をそれぞれ以下のように定めた(書籍を参考に実装した)

グラフ情報

#それぞれのノードがどのノードに接続しているか(距離も付与)
#start: %{a: 6, b: 2},
#start --6--> a
#start --2--> b ということを表現している
graph = %{
  start: %{a: 6, b: 2},
  a: %{fin: 2},
  b: %{a: 3, fin: 5},
  fin: %{}
}

コスト情報

#startから接続しているノードまでの距離
#startと接続していないノードにはinfinityをセット
costs = %{
  a: graph.start.a,
  b: graph.start.b,
  fin: :infinity
}

親ノード情報

#startから接続しているノードのノード名
#そのほかはnilとしておく
parents = %{
  a: :start,
  b: :start,
  fin: nil
}

1つにまとめられそうな気もするが、あまり複雑化させるよりはいくつかに分別して方が経験上良い
データの準備は以上で次にコードを実装する

Elixirでのダイクストラ法の実装

まずは全体のコードをお見せします

defmodule Algo do
  def dijkstra(graph, costs, parents, processed) do
    node = _search_minimize_cost_in_graph(costs, processed)
    case node do
      :empty -> {costs, parents}
      _ ->
        neighbors = graph[node]
        {n_costs, n_parents} = _node_update(node, Map.keys(neighbors), costs[node], costs, neighbors, parents)
        dijkstra(graph, n_costs, n_parents, processed ++ [node])
    end
  end

  defp _node_update(_, [], _, costs, _, parents), do: {costs, parents}
  defp _node_update(node, [head | tail], cost, costs, neighbors, parents) do
    new_cost = cost + neighbors[head]
    if costs[head] > new_cost do
      n_costs = Map.put(costs, head, new_cost)
      n_parents = Map.put(parents, head, node)
      _node_update(node, tail, cost, n_costs, neighbors, n_parents)
    else
      _node_update(node, tail, cost, costs, neighbors, parents)
    end
  end
  
  def creater(res, start_atom, end_atom) do
    _creater(res, start_atom, end_atom, [end_atom])
  end
  def _creater(res, start_atom, next_atom, accum) do
    end_val = res[next_atom]
    if end_val == start_atom do
      [start_atom] ++ accum
    else
      _creater(res, start_atom, end_val, [end_val] ++ accum)
    end
  end

  defp _search_minimize_cost_in_graph(costs, processed) do
    rest_node = Map.keys(costs) |> Enum.filter(fn x -> x not in processed end)
    case rest_node == [] do
      true -> :empty
      false -> Enum.reduce(rest_node, :infinity, fn x, accum ->
        if accum > costs[x] do
          x
        else
          accum
        end
      end)
    end
  end
end

この先の説明部分については完全に自己満足なので
結果を先にお見せします

graph = %{
  start: %{a: 6, b: 2},
  a: %{fin: 1},
  b: %{a: 3, fin: 5},
  fin: %{}
}

costs = %{
  a: graph.start.a,
  b: graph.start.b,
  fin: :infinity,
}

parents = %{
  a: :start,
  b: :start,
  fin: nil
}

res = Algo.dijkstra(graph, costs, parents, [])
#res: {%{a: 5, b: 2, fin: 6}, %{a: :b, b: :start, fin: :a}}

{_a, b} = res
root = Algo.creater(b, :start, :fin)
#root: [:start, :b, :a, :fin]

別のグラフで試してみる

graph = %{
  start: %{a: 6, b: 2, c: 1},
  a: %{fin: 1},
  b: %{a: 3, fin: 5},
  c: %{a: 6, fin: 2},
  fin: %{}
}

costs = %{
  a: graph.start.a,
  b: graph.start.b,
  c: graph.start.c,
  fin: :infinity,
}

parents = %{
  a: :start,
  b: :start,
  c: :start,
  fin: nil
}

res = Algo.dijkstra(graph, costs, parents, [])
{_a, b} = res
root = Algo.creater(b, :start, :fin)

#root: [:start, :c, :fin]

良い感じですね 実装についてはここまでです
どんな動きをしているかが気になる方は以下をどうぞ

作成したモジュールについて

最短経路を求めるこのモジュールは4つの関数から成り立っている

• dijkstra(メイン関数)
• _node_update(条件に従いノード情報を更新する関数)
• creater(dijkstraの結果から最短経路を作成する関数)
• _search_minimize_cost_in_graph(最も手数が少ないノードを探索する関数)

順にコードを見ていく

dijkstra

def dijkstra(graph, costs, parents, processed) do
    #隣接しているノードの中で最も距離が近い(コストが低い)ノードを探索
    node = _search_minimize_cost_in_graph(costs, processed)
    case node do
      #もう探索できるノードがない場合
      :empty -> {costs, parents}
      _ ->
        #探索した最もコストの低いノードに隣接しているノードを取得(マッチ)
        neighbors = graph[node]
        #ノード情報をアップデート
        {n_costs, n_parents} = _node_update(node, Map.keys(neighbors), costs[node], costs, neighbors, parents)
        #今調べたノードを探索済み(accumに追加)して再帰
        dijkstra(graph, n_costs, n_parents, processed ++ [node])
    end
end

_node_update

#探索できるノードが無くなったら終了
defp _node_update(_, [], _, costs, _, parents), do: {costs, parents}
defp _node_update(node, [head | tail], cost, costs, neighbors, parents) do
  #次のノードまでの合計距離
  new_cost = cost + neighbors[head]
  #現時点で発見されているコストよりも別ルートの方が最短かどうか
  if costs[head] > new_cost do
    #コスト情報と親情報を上書き
    n_costs = Map.put(costs, head, new_cost)
    n_parents = Map.put(parents, head, node)
    _node_update(node, tail, cost, n_costs, neighbors, n_parents)
  else
    _node_update(node, tail, cost, costs, neighbors, parents)
  end
end

_node_updateが呼ばれる以前にこんなことが起きている

• Startから最もコストが低いノードはBノード
• Bノードに隣接しているノードを全て取得(Aとfin)

この情報を元に_node_updateが呼ばれる
例えばBノードからAノードへの探索をする場合には元々のコストは以下のようになっている

ノード名	距離(コスト)
A	6
B	2
fin	infinity

しかし、_node_updateが呼ばれ現状のAルートへの道のりよりも
Bを経由してAに行った方が近いことが分かる

head = :a #Aノード
new_cost = cost + neighbors[head]
#new_cost = 2 + 3 -> 5
#このコストは現状の6よりも小さい

従ってコストを更新する

ノード名	距離(コスト)
A	5
B	2
fin	infinity

さらに親ノードの情報も更新する
更新前

ノード名	距離(コスト)
A	start
B	start
fin	infinity

更新後

ノード名	距離(コスト)
A	B
B	start
fin	nil

creater
この関数についてはオマケなのであまり深く語る部分はない
dijkstraの戻り値の第2要素を使ってresからrootを生成しているだけ

res = %{a: :b, b: :start, fin: :a}
root = Algo.creater(res)

iex> root
[:start, :b, :a, :fin] #道順になっている

_search_minimize_cost_in_graph

defp _search_minimize_cost_in_graph(costs, processed) do
  #探索済みのノードを破棄
  rest_node = Map.keys(costs) |> Enum.filter(fn x -> x not in processed end)
  case rest_node == [] do
    true -> :empty
    #[:a, :b, :fin]から最小コストを持つノードを探索
    false -> Enum.reduce(rest_node, :infinity, fn x, accum ->
      if accum > costs[x] do
        x
      else
        accum
      end
    end)
  end
end

長くなってしまいましたが、おそらくコード自体はもっと短くできるかと思います
とりあえずは実装してみるを原動力に書いているのでその点はご了承ください。リファクタリングはElixir力が高まってからチャレンジしてみようと思います