codewars.com の問題を解いていて、ほぇえええ（感嘆）なコードを見たので、理解するまでの流れを復習の意味でまとめています。
書いてる人
- 数学知識は皆無（高校でやったはずですがほとんど覚えていません、、算数ができる程度です）
- 主にJSを利用（以下の問題もJSで解いています）
- JSに関して初学者ではないが、リファレンスに載ってる関数を全部把握してるかと言われると微妙
- アルゴリズムってねーあれだよねー
という感じですので、同じような人におすすめです。
codewars.com や projecteuler.net を解きながら初歩の初歩から数学やアルゴリズムの勉強をしている最中です。
codewars
codewars.com はサイト上でプログラミングの問題を解いていくサービスです。
以下が詳しいです。
https://qiita.com/javacommons/items/7c473cda7825ab99e08c
今回の問題
ざっくり説明すると、与えられた配列の中から奇数回出現する数字を求めなさい。
奇数回出現する数字は必ず一つだけです。
という問題です。例えば
[5,4,3,2,1,5,4,3,2,10,10]
上の配列では1だけが奇数回の出現、他はすべて偶数回出現します。
正解は１になります。
まず愚直な回答
自分が何も考えすに書いたコードです。
function findOdd(researchArray) {
let counts = {}
researchArray.map(key=>{
counts[key] = counts[key] ? counts[key] + 1 : 1;
});
let keyNumber = Object.keys(counts).find(function (key) {
return counts[key] % 2 == 1;
});
return Number(keyNumber);
}
ハッシュに追加しながら、既存のkeyの場合はvalueに1を足していき、最後にハッシュから奇数のセットを探しています。
我ながら誰でも思い付く何のひねりもないすごく普通の回答に見えます。
感動したコード
上記のコードを提出した後、他の方の回答を見たのですが簡単に奇数を探し出してるコードがありました。
（元のコードはワンライナーなのですが見やすいように少し書き換えています）
function findOdd(researchArray) {
return researchArray.reduce((a, b) => {
return a ^ b;
});
}
すっごい！意味わからない！
なにこれ！？？
まずこの謎コードの要素を分解します
reduce関数
便利です、自分も最近知りました。
配列の左から順にループしながら処理を行っていく関数なのですが
上のコードの場合、まず1ステップ目では
a = researchArray[0]
b = researchArray[1]
2ステップ目は
a = コールバック関数内でreturnした値
b = researchArray[2]
となり、これが配列の最後まで繰り返されます。
例えば配列を左から順に全部掛け算したい時は
[1,2,5,6,8,34].reduce((a, b) => {
retuen a * b;
});
と書くことが出来ます。
a ^ b
XOR(排他的論理和）ってやつですね、普段使う事はないけど何となく知っている程度です。
2つのビットが同じなら0,違ったら1を返します。
以下の4パターンです。
1 ^ 1 = 0;
1 ^ 0 = 1;
0 ^ 1 = 1;
0 ^ 0 = 0;
要するに
reduce関数を使って配列を左から順にXORを求めているという状態です。
なんですが、なんで奇数の数字が返ってくるのか意味不明です。
何が起きてるのか確認してみる
問題を単純化して実際の数字を見ながら確認していきます
2進数で考えてみる
まず与えられた配列が2進数だった場合で考えてみました。
[1,0,0,1,1]
奇数個の数字は1になります。
処理をステップ毎に確認
この配列を順番にxorしてみます。
[ 1 ] a = 1
b = 0
[ 2 ] a = 1
b = 0
[ 3 ] a = 1
b = 1
[ 4 ] a = 0
b = 1
return 1
確かに1になりました。
10進数でも考えてみる
次は10進数の配列で考えてみます、ビット桁が大きくならない様にMAXを３で確認しました。
[3, 1, 0, 0 ,1]
処理をステップ毎に確認
そもそも10進数をXORした時にどうなるのか分かっていなかったのですが、2進数に変換して各桁のビットに対してXORが走るそうです。
元の10進数と2進数を並べるとこんな流れになります。
[ 1 ] a = 3: 11
b = 1: 01
[ 2 ] a = 2: 10
b = 0: 00
[ 3 ] a = 2: 10
b = 0: 00
[ 4 ] a = 2: 10
b = 1: 01
return 3: 11
正しい答えが出ています。なんで、、
XOR交換アルゴリズム
さっぱり分からないのでXORについて調べているとXOR交換アルゴリズムというものに出くわしました。
以下が詳しいです。
https://qiita.com/Riliumph/items/9f3719b2db39cf111208
XORを繰り返す事でAとBの値が入れ替わります。
a = 2;
b = 5;
a = a ^ b;
b = a ^ b;
a = a ^ b;
// a == 5, b == 2
これも不思議なのですが、以下の4条件が成り立つことで交換が動作するとのこと。
- 左右交換可能:
a ^ b = b ^ a - 順番入れ替えても答え一緒:
(a ^ b) ^ c = a ^ (b ^ c) - ０でXORすると元の値:
a ^ 0 = a - 自身でXORすると0:
a ^ a = 0
うん、、、、という感じですが、上に貼った@Riliumphさんの記事の証明部分を見ると確かに動きそうな事が理解できます。
同じ条件を奇数検知に当てはめる
XORの性質を奇数検知に当てはめてみます。
- 条件2により配列の順番は関係なく同じ計算結果になる
- 条件4により自身同士（偶数回）のXORの場合０になるので消えていき、奇数回の数字だけが残る
- 条件3により値が0の場合は結果に反映されないので、０が奇数で他の数字が偶数場合は０以外の数字もXORの結果０になり最終的に正解の0を返す
おお、動く。こっちの方が簡単ですね。
そして必ず奇数個出現する数字は１つという条件がないと成立しないコードだという事も分かりました。
ってことは、XOR使う回答を想定した出題って事ですね。みんなすごい。
まとめ
問題を解いて知ったこと
- XORの特性
- 特性を理解して道具を使いこなすと想像出来なかった成果が生まれる
- ビットに変換するというのは数字の構造分析みたいな感じなのかなという気がした
今後もアルゴリズムや数学の勉強をしがてらQiitaに書き残していこうと思います