JavaScript基礎概念勉強ノート5 実践編

初めに

今回は自分がJS基礎の練習時に遭遇した難問、もしくは面白い問題を少し紹介したいと思います。ここで書いたのは自分のコードへの振り返りですので、模範解答的なものではありません。アウトプットテストの検証を一応通っています。

Fibonacci numbers（フィボナッチ数列）

// fib(0), fib(1) are special cases
// solution1
let arr = [0, 1]

function fibonacci(n) {
  let sum = 0
  if (n === 0) return arr[0]
  if (n === 1) return arr[1]
  if (n >= 2) {
    for (let i = 2; i <= n; i++) {
      sum = arr[i - 1] + arr[i - 2]
      arr.push(sum)
    }
  }
  // console.log(arr)
  return arr[n]
}

// console.log(fibonacci(1)) // 1
// console.log(fibonacci(2)) // 1
console.log(fibonacci(8)) // 21

フィボナッチ数列の問題です。最初問題を目にしたとき、え？聞いたことがないんです...（文系出身かつ数学が苦手です...）。ウェキペディアで調べたら、ひとつ前と二つ前の数字を合わせて、次の数字になるような感覚でした。arrayを作っていけばいいじゃないかと。フィボナッチの数列を見たら、indexが0からしても問題なさそうなので、arrayの最初に0と1だけ入れてスペシャルケースとして使ってもいいし、ループで加算して入れていけばいいんじゃないかと。
簡単に解けた感覚でした。が、資料を調べながらほかの解き方を見てまた思わずに、え？って。

// solution takes a cue from other people
function fib(n) {
  var fib = [0, 1]
  for (var i = 2; i <= 8; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]
    // it doesn't have to use push()...
  }
  return fib[n]
}

console.log(fib(8))

この書き方すごい簡潔！（初めてRecusionに出会ったのはフィボナッチ数列のおかげです。）
Recusion（再帰） は、functionの中でダメになるまで自分を何度も呼び出して、その値を前一個のfunctionに渡し、今のfunctionまで連続的に値を返し続ける過程です。（←自分の感覚で書いた解釈なんですが、すごく変な言い方かもしれません...。）
しかしプログラミングを勉強していくなか、パフォーマンスに気にしなきゃいけないということ何度も目にした覚えがあります。Time complexity（時間計算量／複雑さ）とSpace complexity（空間計算量／複雑さ）の関連性にとても気になっていて、そこから調べたらループの時間複雑さは要素と関連しているとか、数列にして空間で記憶させて時間の複雑さを低くするとか、一応認識しています。
なのでRecusionのやり方でfib(1000)で実行させたら、何度も自分を呼び出していくというのは、fib(1000)⇒fib(1)+fib(0)に至るまで、これまで呼び出されたfunctionを一時記憶体の中に保存しないといけないし、時間や空間を消耗してしまうことになる。
またfib(0)⇒fib(1000)まで記憶空間をリリースするのも一工夫しなければいけない...等々と分かってだんだんこの書き方を遠ざかってしまいました。せめてほかの方のコードを読むとき、何をしているかが理解できるつもりでいろいろ調べて覚えておきました。

flatten multidimensional array（多次元配列の一次元化）

let newArr = []

function flatArr(arr) {
  // if it's an array, callback & return
  // if arr is not an array, push into newArr
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'object') {
      flatArr(arr[i])
    } else {
      newArr.push(arr[i])
    }
  }
  return newArr
}

// flatArr([1, 2, 3])
// flatArr([1, 2, [1, 2], [1, 3], 6])
console.log(flatArr([1, [2, [3, [4]], 5], 6]))

上でRecusionの悪口を散々言ったくせに、この問題にあうとき、まっさきにRecusionのこと思い出しました。
単に二次元配列なら、二重ループとif条件で要素を走査するか、Spread syntax（スプレット構文）ですべての要素をconcat()の引数として渡せばいいと。

const arr = [1, 2, [1, 2], [1, 3], 6]
let newArr = [].concat(...arr)
console.log(newArr)

でも多次元になるとこのやり方には絶対無理だと思いました...。
しかしRecusionで書くと言っても、どこで呼び出すのか戸惑っていました。要素を走査してほしいのでforが必要ですし、配列じゃないならpush()、配列にあったら平坦化させたいので、とりあえずfunction名だけ残しておいて、最終的にnewArrを返してほしいので、このように残りの条件を書きました。
その下に平坦化のfunctionを書き始めて、[].concat(...arr)で平坦化する？でもこれじゃ二次元とは変わらない、この部分を外に移すだけじゃない...。
それに外で一回 flatArr() を呼び出しただけで、どうやって平坦化のfunctionの再帰を行うのかな？（最初は flatArr() の中で別のfunctionの再帰を呼び出すつもりだった）
結構悩んでいたら突然気づきました。本当に何度も実行させたいのは flatArr() だよね？ flatArr() ですべての要素を走査し条件判断を行うべきだった、なら本当に何度も呼び出されるのは flatArr() 、つまり自分なのか！
ということで実行させてみたら無事に終わり、一応完成したんです。
今でも再帰の書き方に苦手です。でも何を何度も使いたいというのを見極めれば、徐々に慣れるかもしれないと思います。

// solution takes a cue from other people

function flatten(arr) {
  let result = [];
  recursive(result, arr);
  return result;
}

function recursive(result, arr) {
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] !== "object") {
      result.push(arr[i]);
    } else {
      recursive(result, arr[i]);
    }
  }
}
console.log(flatten([1, 2, 3]));
console.log(flatten([1, 2, [1, 2], [1, 3], 6]));
console.log(flatten([1, [2, [3, [4]], 5], 6]))

↑は書き終わって資料を調べるときほかの方が書いたものです。
resultの宣言は関数の中にしたので、パラメータの引数として入れられたんですね。最終的にresultを返す。
自分の書き方では何度も使われると思ってglobalで宣言したんですが、この書き方なら関数内でやることを済ませて値として返し、closure（関数閉包） を避けるのではないかと思いました。（closureについては浅はかな認識しかないけれど、自分の書き方とはどこが違うか、一応自分の考えを残す）

Christmas tree（クリスマスツリー）

function stars(n) {
  let stars = ''
  stars += '*' + '*'.repeat(n * 2) + '\n'
  return stars
}
// console.log(stars(5))

function spaceWithStar(n) {
  let space = ''
  for (let i = n; i >= 1; i--) {
    // space: 5, 4, 3, 2, 1
    // stars: 0, 1, 2, 3, 4
    space += '_'.repeat(i - 1)
    space += stars(n - i)
    // console.log(space)
    // console.log('n:', n)
    // console.log('i', i)
  }
  return space
}
// console.log(spaceWithStar(5))

function trunk(n) {
  let trunk = ''
  for (let i = 0; i < n; i++) {
    trunk += '_'.repeat(n - 1)
    if (n > 1) {
      for (let j = 0; j < 1; j++) {
        trunk += '*'
      }
      trunk += '\n'
    }
  }
  return trunk
}
// console.log(trunk(1))

function tree(n) {
  let result = ''
  result += spaceWithStar(n)
  result += trunk(n)
  console.log(result)
}

// tree(1)
// tree(2)
tree(5)
// problem: over a '\n'

____*
___***
__*****
_*******
*********
____*
____*
____*
____*
____*

クリスマスツリーの練習結構好きです。最初はspaceWithStar()の法則を見つけ出すだめのメモも取りました（スペースはCLIで読みづらいので"_"に変えた）。今振り返ると、ツッコミのとろこありすぎて、自分の未熟さを感じました。例えば、stars()のところ、
stars += '*'.repeat(2n - 1) + '\n' ←こっちはもっと簡潔に、無理やり作らせる感覚もない。
そして全体としてreturnではなくconsole.log()にすればtrunk()から余った'\n'も無くなります。
ただ気になるのは、アウトプットが同じでもreturnとconsole.log()はやっぱり違うものだと思います。ならreturnのやり方では、trunk()の余った改行はどうやって解決できるのかな。
return trunk - '\n' にしてみますと NaN と返され、勝手にnumberに変換されました。
（今後の課題として記録を残します。）

Tic-tac-toe（三目並べ）

// arr[0], [3], [6]
// arrOne
function addOne(arr, n) {
  // x = 1, check 0, 1, 2 | 3, 4, 5 | 6, 7, 8 |
  let counter = 0
  for (let i = 0; i < 2; i++) {
    if (arr[n] === arr[n + 1]) {
      counter++
      n += 1
    }
  }
  return counter
}

// arr[0], [1], [2]
// addThree
function addThree(arr, n) {
  // y = 3, check 0, 3, 6 | 1, 4, 7 | 2, 5, 8 |
  let counter = 0
  for (let i = 0; i < 2; i++) {
    if (arr[n] === arr[n + 3]) {
      counter++
      n += 3
    }
  }
  return counter
}

// arr[2]
// addTwo
function addTwo(arr, n) {
  let counter = 0
  for (let i = 0; i < 2; i++) {
    if (arr[n] === arr[n + 2]) {
      counter++
      n += 2
    }
  }
  return counter
}

// arr[0]
// addFour
function addFour(arr, n) {
  // z = 4, check 0, 4, 7
  let counter = 0
  for (let i = 0; i < 2; i++) {
    if (arr[n] === arr[n + 4]) {
      counter++
      n += 4
    }
  }
  return counter
}

function indexZero(arr) {
  if (arr[0] === 'O') {
    if (addOne(arr, index[0]) >= 2 ||
      addThree(arr, index[0]) >= 2 ||
      addFour(arr, index[0]) >= 2) {
      return 'winner is O'
    }
  } else if (arr[0] === 'X') {
    if (addOne(arr, index[0]) >= 2 ||
      addThree(arr, index[0]) >= 2 ||
      addFour(arr, index[0]) >= 2) {
      return 'winner is X'
    }
  }
}

function indexOne(arr) {
  if (arr[1] === 'O') {
    if (addThree(arr, index[1]) >= 2) {
      return 'winner is O'
    }
  } else if (arr[1] === 'X') {
    if (addThree(arr, index[1]) >= 2) {
      return 'winner is X'
    }
  }
}

function indexTwo(arr) {
  if (arr[2] === 'O') {
    if (addTwo(arr, index[2]) >= 2 ||
      addThree(arr, index[2]) >= 2) {
      return 'winner is O'
    }
  } else if (arr[2] === 'X') {
    if (addTwo(arr, index[2]) >= 2 ||
      addThree(arr, index[2]) >= 2) {
      return 'winner is X'
    }
  }
}

function indexThree(arr) {
  if (arr[3] === 'O') {
    if (addOne(arr, index[3]) >= 2) {
      return 'winner is O'
    }
  } else if (arr[3] === 'X') {
    if (addOne(arr, index[3]) >= 2) {
      return 'winner is X'
    }
  }
}

function indexSix(arr) {
  if (arr[6] === 'O') {
    if (addOne(arr, index[6]) >= 2) {
      return 'winner is O'
    }
  } else if (arr[6] === 'X') {
    if (addOne(arr, index[6]) >= 2) {
      return 'winner is X'
    }
  }
}

let index = [
  0, 1, 2,
  3, 4, 5,
  6, 7, 8
]

function winner(arr) {
  let newArr = [].concat(...arr)
  console.log(newArr)

  if (newArr.length > 0) {
    if ((indexZero(newArr) || indexOne(newArr) ||
      indexTwo(newArr) || indexThree(newArr) ||
      indexSix(newArr)) === undefined) {
      return 'draw'
    } else {
      return indexZero(newArr) || indexOne(newArr) ||
        indexTwo(newArr) || indexThree(newArr) ||
        indexSix(newArr)
    }
  } else {
    return 'draw'
  }
}

//
console.log(winner([
  ['O', 'X', 'O']
])) // draw
console.log(winner([
  ['O', 'O', ''],
  ['X', 'X', 'X']
])) // winner is X
console.log(winner([
  ['O', 'O', 'X'],
  ['O', 'X', '']
])) // draw
//
console.log(winner([
  ['O', 'O', 'X'],
  ['O', 'X', 'X'],
  ['O', 'X', 'O']
])) // winner is O
console.log(winner([
  ['O', 'O', 'X'],
  ['O', 'X', 'X'],
  ['X', 'X', 'O']
])) // winner is X
console.log(winner([
  ['O', 'O', 'X'],
  ['O', 'O', 'X'],
  ['X', 'X', '']
])) // draw

一番時間をかけた問題でした。この問題も結構すきです。最初のアウトプットテストは、一番下の三つのようにどっちが勝ったのか正しい判断を示せばいいのですが、しかし途中で勝つ可能性もあるし、それに好きな場所にOとX入れるのがこのゲームなんじゃないかな？って思って、いろんなケースを考えて完成しました。最適化にするつもりはあるけれど、どうすればいいのかはまだ...。
addのところではみんなループが同じ回数、counter++も何度も繰り返しているんですが、検査のインデックスは違うのでnの計算も違う。最適化するならいっそうif条件式を入れて、同じインデックスからでも検査相手のインデックスの違いでnの計算を別々にする、と、一回目はいいかもしれないけど、OXゲームはOを取ったほうとXを取ったほうに一回ずつ場所を占めていくので、counterの計算は問題にならないはずですが、nは相互に利用しあうようになって検査条件がおかしくなると思ってとりあえず一旦放置。
きっともっといい書き方があると、今の自分はまだまだ弱いから解決できない...。これも今後の課題にしておきます。

感想

振り返えれば課題がたくさん残っています。この積み重ねてきたものがストレスであり自分の成長につれて解決していく達成感でもあると時々思います。余裕があってもなくても今の自分に直面して、これからも頑張っていきたいと思います。