H-99: Ninety-Nine Haskell ProblemsというHaskellの問題集があります。
元はPrologの問題集だったそうです。
二番煎じかもしれませんがこの問題集を少し改変して、JavaScriptで解いていくことにします。
ほぼ自分の腕試し用です。
- テストを書く
- 最適化
Node.jsを使いますので、インストールしてください。
インストール後にコンソールを開いて以下のコマンドを実行し、バージョンが表示されればPATHが通っています。
執筆時点では、Node.jsはv11.0.0、npmは6.4.1を使用しています。
$ node -v
$ npm -vYarnもインストールします。
Yarnはnpmよりも高速なパッケージマネージャです。
$ npm i -g yarn問題を解いていくためのパッケージを作成しましょう。
以下のコマンドを実行します。
$ mkdir js-99
$ cd js-99
$ yarn init -yjs-99ディレクトリにpackage.jsonが生成されます。
問題の解答をライブラリとしてビルドできるようにしましょう。
たくさん解けば、最終的にはlodashみたいな感じになりそうですね！
Webpackは分割したモジュールを一つのファイルにまとめてくれるバンドラです。
最新のJavaScriptの構文をIE11などの古いブラウザでも使えるように変換(トランスパイル)してくれるBabelもインストールします。
以下のコマンドを実行しましょう。これらのモジュールはnode_modulesディレクトリが作成されて、そこに格納されます。
$ yarn add -D @babel/core @babel/preset-env @babel/register babel-loader webpack@4.x webpack-cliプロジェクト直下に.babelrcを作成し、以下のように設定します。
{
"presets": ["@babel/preset-env"]
}webpack.config.babel.jsを作成し、webpackの設定を書いていきます。
outputはバンドルしたJSファイルをライブラリとして使えるようにするための設定です。
import path from 'path'
export default {
mode: 'production',
entry: path.join(__dirname, 'src', 'index.js'),
output: {
library: 'js99',
libraryTarget: 'umd',
globalObject: 'this',
filename: 'js-99.js',
path: path.join(__dirname, 'dist')
}
}package.jsonにscriptsを追記します。
これはnpm-scriptsというもので、スクリプトを書いておくとyarn <script名>で実行できるようになります。
{
...
"scripts": {
"build": "webpack"
},
...
}srcディレクトリを作成し、index.jsを以下のような内容で作成してみましょう。
export default { hoge: 'fuga' }次のコマンドを実行してdist/js-99.jsが出力されれば成功です。
REPLでrequireして確かめることもできます。
$ yarn build$ node
> require('./dist/js-99')
{ default: { hoge: 'fuga' } }問題が解けたかどうか確かめるために、ユニットテストができる環境を作りましょう。
ユニットテストをするためにJestを導入します。
$ yarn add -D jest babel-jest babel-core@^7.0.0-bridge.0 regenerator-runtimepackage.jsonのscriptsにtestを追記します。
{
...
"scripts": {
"build": "webpack",
"test": "jest"
},
...
}動作確認してみましょう。
testディレクトリを作成し、hoge.test.jsにユニットテストを書いていきます。
import hoge from '../src'
test('動作確認', () => {
expect(hoge.hoge).toBe('fuga')
})以下のコマンドでユニットテストを実行できます。
$ yarn test次のような出力になれば成功です。
[PASS] test/hoge.test.js
√ 動作確認 (3ms)
Test Suites: 1 passed, 1 total
Tests: 1 passed, 1 total
Snapshots: 0 total
Time: 1.425s
Ran all test suites.
Done in 2.16s.
H-99の22問目の「指定された範囲内のすべての整数を含む配列を生成する関数rangeを実装する」という問題を試しに解いてみます。
Haskellには[4..9]のように書くと[4,5,6,7,8,9]が生成される構文があるため、それと同様の結果を返すrangeは面白そうだと思ったからです。
初回なので、とりあえずそれなりにテストも書いてみます。
range関数は以下のような動作になるはずです。
range(4, 9) // [4,5,6,7,8,9]まずはテストから書いてみます。range(5, 1)のような引数を渡すと空の配列が返ってくることを想定します。
test/index.test.jsを次のように編集します。
import { range } from '../src'
describe('問22: 指定された範囲内のすべての整数を含む配列を生成する', () => {
test('4から9までの整数の配列', () => {
expect(range(4, 9)).toEqual([4, 5, 6, 7, 8, 9])
})
test('5から1までの整数の配列（空の配列）', () => {
expect(range(5, 1)).toEqual([])
})
})まだ未実装なのでyarn testをすると失敗します。
このテストをパスできるようにsrc/index.jsに実装していきましょう。
for文を使えばすぐに実装できます。
/**
* 指定された範囲内のすべての整数を含む配列を生成する
* @param {number} start 開始
* @param {number} end 終了
* @returns {number[]} 範囲内のすべての整数を含む配列
*/
export const range = (start, end) => {
const list = []
for (let i = start; i <= end; i++) {
list.push(i)
}
return list
}これでyarn testをパスできるようになりました！書いたテストが全て緑色になるのは気持ちいいですね。
ついでに、「指定された範囲内のすべての文字を含む配列」もrange関数で返すようにしてみます。
Haskellでは['a'..'z']で小文字のアルファベットの配列を表現できるからです。
関数に変更を加えても先ほど書いたテストは当然通るようにしなければなりません。
逆に、変更によってバグが生じた場合は、ユニットテストをパスしなくなってすぐに分かるわけです。
test/index.test.jsにテストを追加しましょう。
describe('問22: 指定された範囲内のすべての整数または文字を含む配列を生成する', () => {
/* 省略 */
test('aからzまでの文字の配列', () => {
expect(range('a', 'z')).toEqual(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'])
})
test('引数の型が異なる（エラー）', () => {
expect(() => range(1, 'a')).toThrowError()
})
test('引数が文字列のとき、長さが2以上ある（エラー）', () => {
expect(() => range('aa', 'b')).toThrowError()
})
})src/index.jsのrange関数に機能を追加しましょう。
引数がstringだった場合、文字をUnicode値に変換してからループさせ、結果を格納するときはUnicode値を文字に変換するようにします。
/**
* 指定された範囲内のすべての整数または文字を含む配列を生成する
* @param {number|string} start 開始位置の要素
* @param {number|string} end 終了位置の要素
* @returns {number[]|string[]} 範囲内のすべての要素を含む配列
*/
export const range = (start, end) => {
if (typeof(start) !== typeof(end)) {
throw new Error('引数は同じ型にしてください')
}
const isStr = typeof(start) === 'string'
if (isStr && (start.length !== 1 || end.length !== 1)) {
throw new Error('引数にする文字列の長さは1にしてください')
}
const list = []
if (isStr) {
start = start.charCodeAt(0)
end = end.charCodeAt(0)
}
for (let i = start; i <= end; i++) {
list.push(isStr ? String.fromCharCode(i) : i)
}
return list
}少し長くなってしまいました。yarn testで全てパスされていれば成功です。
問題をJavaScript用に改変しているところがあります。
これによって難易度にバラつきが出ていますが、ご了承ください。
一部の問題は統合しているため、本当に99問あるわけではありません。
配列や文字列の最後の要素を取り出す
last関数を実装せよ。
last([1, 2, 3, 4]) // 4
last('xyz') // z配列や文字列の最後の一つ前の要素を取り出す
butLast関数を実装せよ。
butLast([1, 2, 3, 4]) // 3
butLast('abcdefghijklmnopqrstuvwxyz') // y配列や文字列のn番目の要素を取り出す
elementAt関数を実装せよ。
ただし、最初の要素は0番目ではなく、1番目と数える。
elementAt([1, 2, 3], 2) // 2
elementAt('JavaScript', 5) // S配列や文字列の長さを返す
length関数を実装せよ。
ただし、Array.lengthやString.lengthは使用しないこと。
また、絵文字の長さは1と数えるようにすること。
length([123, 456, 789]) // 3
length('💃Hello, World!💃') // 15配列や文字列を逆順にして返す
reverse関数を実装せよ。
ただし、Array.reverseは使用しないこと。
また、絵文字の長さは1と数えるようにすること。
reverse('A man, a plan, a canal, panama!💃') // 💃!amanap ,lanac a ,nalp a ,nam A
reverse([1, 2, 3, 4]) // [4, 3, 2, 1]配列や文字列が回文かどうかを返す
isPalindrome関数を実装せよ。
isPalindrome([1, 2, 3]) // false
isPalindrome('たけやぶやけた') // true
isPalindrome([1, 2, 4, 8, 16, 8, 4, 2, 1]) // trueネストしている配列を平坦（一次元配列）にして返す
flatten関数を実装せよ。
ただし、Array.flatは使用しないこと。
flatten([1, [2, [3, 4], 5]]) // [1, 2, 3, 4, 5]配列や文字列から同じ要素の繰り返しを排除して返す
compress関数を実装せよ。
compress([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [ 1, 2, 1, 2, 3 ]
compress('aaaabccaadeeee') // abcade配列や文字列の同じ要素の繰り返しを配列としてまとめて返す
pack関数を実装せよ。
pack([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[1, 1], [2], [1], [2, 2], [3, 3, 3, 3]]
pack('aaaabccaadeeee') // ['aaaa', 'b', 'cc', 'aa', 'd', 'eeee']
pack関数を用いて、配列や文字列をランレングス圧縮するencode関数を実装せよ。
encode([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[2, 1], [1, 2], [1, 1], [2, 2], [4, 3]]
encode('aaaabccaadeeee')
// [[4, 'a'], [1, 'b'], [2, 'c'], [2, 'a'], [1, 'd'], [4, 'e']]問10の結果を変更し、重複が無ければランレングス圧縮せずに要素を格納する
encodeModified関数を実装せよ。
encodeModified([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[2, 1], 2, 1, [2, 2], [4, 3]]
encodeModified('aaaabccaadeeee')
// [[4, 'a'], 'b', [2, 'c'], [2, 'a'], 'd', [4, 'e']]ランレングス圧縮した配列をデコードする
decodeModified関数を実装せよ。
decodeModified([[2, 1], 2, 1, [2, 2], [4, 3]]) // [1, 1, 2, 1, 2, 2, 3, 3, 3, 3]
decodeModified([[4, 'a'], 'b', [2, 'c'], [2, 'a'], 'd', [4, 'e']]) // aaaabccaadeeee
pack関数のように重複を含む配列を作らずに、直接ランレングス圧縮するencodeDirect関数を実装せよ。
encodeDirect([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[2, 1], 2, 1, [2, 2], [4, 3]]
encodeDirect('aaaabccaadeeee')
// [[4, 'a'], 'b', [2, 'c'], [2, 'a'], 'd', [4, 'e']]配列や文字列の要素を複製する
dupli関数を実装せよ。
dupli([1, 2, 3]) // [1, 1, 2, 2, 3, 3]
dupli('abc') // aabbcc指定された回数だけ配列や文字列の要素を複製する
repli関数を実装せよ。
repli([1, 2, 3], 3) // [1, 1, 1, 2, 2, 2, 3, 3, 3]
repli('abc', 3) // aaabbbcccnの倍数の位置の要素を配列や文字列から削除する
drop関数を実装せよ。
drop([1, 2, 3, 4], 2) // [1, 3]
drop('abcdefghik', 3) // 'abdeghk'配列や文字列を指定した位置で分ける
split関数を実装せよ。
split([1, 2, 3, 4], 2) // [[1, 2], [3, 4]]
split('abcdefghik', 3) // ['abc', 'defghik']選択した範囲を配列や文字列から取り出す
slice関数を実装せよ。
ただし、Array.slice、Array.spliceは使用しないこと。
slice([1, 2, 3, 4], 2, 4) // [2, 3, 4]
slice('abcdefghik', 3, 7) // cdefg配列や文字列の要素を左にn個ずらす
rotate関数を実装せよ。
負の数を渡したときは右にずらすようにすること。
rotate([1, 2, 3], 1) // [2, 3, 1]
rotate('abcdefgh', 3) // defghabc
rotate('abcdefgh', -2) // ghabcdef配列や文字列のn番目の要素を削除する
removeAt関数を実装せよ。
削除した要素と処理後の配列を配列に格納し、呼び出した結果として返しなさい。
removeAt(3, [1, 2, 3]) // [3, [1, 2]]
removeAt(2, 'abcd') // ['b', 'acd']配列や文字列の指定した位置に要素を挿入する
insertAt関数を実装せよ。
insertAt(5, [1, 2, 3, 4], 3) // [1, 2, 5, 3, 4]
insertAt('X', 'abcd', 2) // aXbcd指定された範囲内のすべての整数または文字を含む配列を生成する
range関数を実装せよ。
range(4, 9) // [4, 5 ,6, 7, 8, 9]
range('a', 'z') // ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']配列や文字列から指定された数ぶんだけランダムに要素を取り出す
rndSelect関数を実装せよ。
rndSelect('abcdefgh', 3) // eda など長さnの1以上m以下の乱数列を生成する
diffSelect関数を実装せよ。
diffSelect(6, 49) // [23, 1, 17, 33, 21, 37] など配列や文字列をランダムに並び替える
rndPermu関数を実装せよ。
rndPermu('abcdef') // badcef などm個の要素からn個を選んだ組み合わせを返す
combinations関数を実装せよ。
combinations('abcdef', 2) // ['ab', 'ac', 'ad', 'ae', 'af', 'bc', 'bd', 'be', 'bf', 'cd', 'ce', 'cf', 'de', 'df', 'ef']配列の要素を互いに素な配列にグループ化して返す
group関数を実装せよ。
group(["aldo","beat","carla","david","evi","flip","gary","hugo","ida"], 2, 3, 4)
// [[["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]],...] 1260個の解
group(["aldo","beat","carla","david","evi","flip","gary","hugo","ida"], 2, 2, 5)
// [[["aldo","beat"],["carla","david"],["evi","flip","gary","hugo","ida"]],...] 756個の解配列の配列を、要素の長さでソートする
lsort関数を実装せよ。
また、要素の長さの頻度順にソートするlfsort関数を実装せよ。
lsort(["abc","de","fgh","de","ijkl","mn","o"]) // ["o","de","de","mn","abc","fgh","ijkl"]
lfsort(["abc", "de", "fgh", "de", "ijkl", "mn", "o"]) // ["ijkl","o","abc","fgh","de","de","mn"]引数が素数かどうかを返す
isPrime関数を実装せよ。
isPrime(7) // trueユークリッドの互除法を使って最大公約数を求める
gcd関数を実装せよ。
gcd(36, 63) // 9渡した2つの整数が互いに素かどうかを返す
coprime関数を実装せよ。
coprime(35, 64) // trueオイラーのφ関数
totientを実装せよ。
totient(10) // 4引数を素因数分解する
primeFactors関数を実装せよ。
結果は昇順にソートすること。
primeFactors(315) // [3, 3, 5, 7]問35の結果を累乗で表現する
primeFactorsMult関数を実装せよ。
3 ** 2なら[3, 2]と表現します。
primeFactorsMult(315) // [[3, 2], [5, 1], [7, 1]]オイラーのφ関数を改良した
phi関数を実装せよ。
問36の結果を[[p1, m1], [p2, m2], [p3, m3], ...]としたとき、オイラーのφ関数は次のようにして計算できます。
phi(m) = (p1 - 1) * p1 ** (m1 - 1) *
(p2 - 1) * p2 ** (m2 - 1) *
(p3 - 1) * p3 ** (m3 - 1) * ...
phi(10) // 4問34と問37の実行時間を比較せよ。
totient(10090)とphi(10090)を実行して、phi関数のほうが効率的であることを確かめてください。
せっかくなので、関数の実行時間を計測するtime関数を実装して調べましょう。
time(totient, 10090) < time(phi, 10090) // true与えられた範囲内の素数の配列を返す
primesR関数を実装せよ。
primesR(10, 20) // [11, 13, 17, 19]ゴールドバッハの予想を確かめる
goldbach関数を実装せよ。
ゴールドバッハの予想は「全ての2よりも大きな偶数は2つの素数の和として表すことができる」という予想です。
goldbach(28) // [5, 23]与えられた範囲内の
goldbachの結果を出力するgoldbachList関数を実装せよ。
第三引数を与えた場合、2つの素数がその値より大きいもののみを出力するようにすること。
goldbachList(9, 20) // [[3, 7], [5, 7], [3, 11], [3, 13], [5, 13], [3,17]]
goldbachList(4, 2000, 50) // [[73, 919], [61, 1321], [67, 1789], [61, 1867]]真理値表を作成する
table関数を実装せよ。
table((a, b, c) => a && (b || c))のように、引数が増えても真理値表を出力できるようにすること。
table((a, b) => a && (a || b))
/*
[
[[true, true], true],
[[true, false], true],
[[false, true], false],
[[false, false], false]
]
*/与えられたbit数のグレイコードの配列を求める
gray関数を実装せよ。
gray(3) // ["000","001","011","010","110","111","101","100"]ハフマン符号化をする
huffman関数を実装せよ。
符号化する要素は[記号, 出現頻度]で表されます。ついでに、文字列も変換できるようにしましょう。
huffman([['a', 45], ['b', 13], ['c', 12], ['d', 16], ['e', 9], ['f', 5]])
// [['a', '0'], ['b', '101'], ['c', '100'], ['d', '111'], ['e', '1101'], ['f', '1100']]
huffman('DAEBCBACBBBC') // [['A', '111'], ['B', '0'], ['C', '10'], ['D', '1100'], ['E', '1101'] ]二分木クラス
BinaryTreeを実装せよ。
二分木は、あるノードが持つ子の数が2個以下の木構造です。
以下のようにコンストラクタに二分木にしたい配列を渡すと、二分木として表現できるようにします。
引数とする配列は、[値, 左部分木, 右部分木]で表現することにします。
const tree = new BinaryTree(['a', ['b', 'd', 'e'], ['c', null, ['f', 'g', null]]])
console.log(tree.toString())
/*
{
"value": "a",
"left": {
"value": "b",
"left": {
"value": "d",
"left": null,
"right": null
},
"right": {
"value": "e",
"left": null,
"right": null
}
},
"right": {
"value": "c",
"left": null,
"right": {
"value": "f",
"left": {
"value": "g",
"left": null,
"right": null
},
"right": null
}
}
}
*/左部分木と右部分木のノードの数の差が1以下である二分木を全て生成する
cbalTree関数を実装せよ。
下記の省略されている[BinaryTree]の部分は、BinaryTree { value: 'x', left: null, right: null }のようになっています。
BinaryTree.cbalTree(4)
/*
[ BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right: BinaryTree { value: 'x', left: null, right: [BinaryTree] } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: [BinaryTree] },
right: BinaryTree { value: 'x', left: null, right: null } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right: BinaryTree { value: 'x', left: [BinaryTree], right: null } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: [BinaryTree], right: null },
right: BinaryTree { value: 'x', left: null, right: null } } ]
*/二分木が対称かどうかを返す
isSymmetric関数を実装せよ。
ノードの値は比較しません。あくまで、構造が対称かどうかを調べます。
const x = new BinaryTree(['x', 'x', null])
const y = new BinaryTree(['x', 'x', 'x'])
x.isSymmetric // false
y.isSymmetric // true二分探索木を生成する
searchTree関数を実装せよ。
引数は一次元配列とします。
BinaryTree.searchTree([3, 2, 5, 7, 1])
/*
BinaryTree {
value: 3,
left:
BinaryTree {
value: 2,
left: BinaryTree { value: 1, left: null, right: null },
right: null },
right:
BinaryTree {
value: 5,
left: null,
right: BinaryTree { value: 7, left: null, right: null } } }
*/
BinaryTree.searchTree([5, 3, 18, 1, 4, 12, 21]).isSymmetric // true
BinaryTree.searchTree([3, 2, 5, 7, 4]).isSymmetric // false問55のように平衡で、かつ対称な二分木があれば返す
symCbalTrees関数を実装せよ。
引数はノード数で、そのような二分木が見つからなければ[]を返します。
BinaryTree.symCbalTrees(5)
/*
[ BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: [BinaryTree] },
right: BinaryTree { value: 'x', left: [BinaryTree], right: null } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: [BinaryTree], right: null },
right: BinaryTree { value: 'x', left: null, right: [BinaryTree] } } ]
*/左部分木と右部分木の高さの差が1以下である二分木を全て生成する
hbalTree関数を実装せよ。
引数は生成する木構造の高さ（根ノードの高さ）とします。
BinaryTree.hbalTree(3)[0]
/*
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right:
BinaryTree {
value: 'x',
left: null,
right: BinaryTree { value: 'x', left: null, right: null } } }
*/
BinaryTree.hbalTree(4).length // 315与えられた数のノードを持つ問59のような二分木を全て生成する
hbalTreeNodes関数を実装せよ。
ヒント
まず、左部分木と右部分木の高さの差が1以下である二分木の高さhを実現するために必要な最小ノード数を計算するminNodes関数を定義します。
少し数式を考えてみれば、最小ノード数はフィボナッチ数列に近いものになるはずです。
次に、minNodes関数を用いて、問題の木構造の最大の高さを求めるmaxHeight関数を定義します。
その後、最小から最大までの高さについて、与えられたノード数を持つ二分木があるかどうか調べます。
BinaryTree.hbalTreeNodes(15).length // 1553
[0, 1, 2, 3].map(BinaryTree.hbalTreeNodes)
/*
[ [ null ],
[ BinaryTree { value: 'x', left: null, right: null } ],
[ BinaryTree { value: 'x', left: null, right: [BinaryTree] },
BinaryTree { value: 'x', left: [BinaryTree], right: null } ],
[ BinaryTree { value: 'x', left: [BinaryTree], right: [BinaryTree] } ] ]
*/二分木の葉の数を数える
countLeaves関数を実装せよ。
(new BinaryTree([1, [2, null, 4], 2])).countLeaves // 2二分木の葉のリストを返す
leaves関数を実装せよ。
(new BinaryTree([1, [2, null, 4], 2])).leaves // [ 4, 2 ]二分木の内部ノード（葉以外の節）を返す
internals関数を実装せよ。
(new BinaryTree([1, [2, null, 4], 2])).internals // [ 1, 2 ]指定された深さのノードのリストを返す
atLevel関数を実装せよ。
(new BinaryTree([1, [2, null, 4], 2])).atLevel(2) // [ 2, 2 ]完全二分木を生成する
completeBinaryTree関数と、完全二分木かどうかを返すisCompleteBinaryTree関数を実装せよ。
完全二分木は、根からすべての葉までの深さの差が1以下で、葉が左詰めになっている二分木です。
引数はノード数とします。
BinaryTree.completeBinaryTree(4)
/*
BinaryTree {
value: 'x',
left:
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right: null },
right: BinaryTree { value: 'x', left: null, right: null } }
*/
(new BinaryTree(['x', ['x', 'x', null], ['x', null, null]])).isCompleteBinaryTree // true
(new BinaryTree(['x', ['x', 'x', null], ['x', null, 'x']])).isCompleteBinaryTree // false次の図のように、各ノードに座標を付与する
layout関数を実装せよ。
次のようにノードに座標を割り振ります。
- x座標は、中順に走査したときの順番
- y座標は、そのノードがある深さ
結果が見づらくなるので、各ノードの座標を分かりやすく取得できるpositions関数もついでに定義しましょう。
const result = (new BinaryTree(['n', ['k', ['c', 'a', ['h', ['g', 'e', null], null]], 'm'], ['u', ['p', null, ['s', 'q', null]], null]])).layout()
result.positions
/*
[ { value: 'n', x: 8, y: 1 },
{ value: 'k', x: 6, y: 2 },
{ value: 'c', x: 2, y: 3 },
{ value: 'a', x: 1, y: 4 },
{ value: 'h', x: 5, y: 4 },
{ value: 'g', x: 4, y: 5 },
{ value: 'e', x: 3, y: 6 },
{ value: 'm', x: 7, y: 3 },
{ value: 'u', x: 12, y: 2 },
{ value: 'p', x: 9, y: 3 },
{ value: 's', x: 11, y: 4 },
{ value: 'q', x: 10, y: 5 } ]
*/次の図のように、各ノードに座標を付与する
wideLayout関数を実装せよ。
配置ルールは図を見て考えてください。
ヒント
ある深さの隣接するノードの水平距離が一定なことに着目しましょう。
const result = (new BinaryTree(['n', ['k', ['c', 'a', ['e', 'd', 'g']], 'm'], ['u', ['p', null, 'q'], null]])).wideLayout()
result.positions
/*
[ { value: 'n', x: 15, y: 1 },
{ value: 'k', x: 7, y: 2 },
{ value: 'c', x: 3, y: 3 },
{ value: 'a', x: 1, y: 4 },
{ value: 'e', x: 5, y: 4 },
{ value: 'd', x: 4, y: 5 },
{ value: 'g', x: 6, y: 5 },
{ value: 'm', x: 11, y: 3 },
{ value: 'u', x: 23, y: 2 },
{ value: 'p', x: 19, y: 3 },
{ value: 'q', x: 21, y: 4 } ]
*/次の図のように、各ノードに座標を付与する
compactLayout関数を実装せよ。
このレイアウトを用いると、全てのノードにおいて一定の対称性を保ちつつ、コンパクトに二分木を表現できます。
配置ルールは図を見て考えてください。
ヒント
ノードと後継ノード間の水平距離に着目しましょう。
const result = (new BinaryTree(['n', ['k', ['c', 'a', ['e', 'd', 'g']], 'm'], ['u', ['p', null, 'q'], null]])).compactLayout()
result.positions
/*
[ { value: 'n', x: 5, y: 1 },
{ value: 'k', x: 3, y: 2 },
{ value: 'c', x: 2, y: 3 },
{ value: 'a', x: 1, y: 4 },
{ value: 'e', x: 3, y: 4 },
{ value: 'd', x: 2, y: 5 },
{ value: 'g', x: 4, y: 5 },
{ value: 'm', x: 4, y: 3 },
{ value: 'u', x: 7, y: 2 },
{ value: 'p', x: 6, y: 3 },
{ value: 'q', x: 7, y: 4 } ]
*/文字列をパースして二分木にする
fromString関数を実装せよ。
二分木の文字列表現はx(y,a(,b))のようにして与えられる。
BinaryTree.stringToTree('x(y,a(,b))')
/*
BinaryTree {
value: 'x',
left: BinaryTree { value: 'y', left: null, right: null },
right:
BinaryTree {
value: 'a',
left: null,
right: BinaryTree { value: 'b', left: null, right: null } } }
*/二分木を前順に走査する
preorder関数と、中順に走査するinorder関数を実装せよ。
また、前順と中順に走査した結果を用いて二分木を生成するpreInTree関数を実装せよ。
前順と中順で走査した結果があれば、二分木の木構造は一通りに定められます。
const tree = BinaryTree.stringToTree('a(b(d,e),c(,f(g,)))')
tree.preorder // [ 'a', 'b', 'd', 'e', 'c', 'f', 'g' ]
tree.inorder // [ 'd', 'b', 'e', 'a', 'c', 'g', 'f' ]
BinaryTree.preInTree(tree.preorder, tree.inorder)
/*
BinaryTree {
value: 'a',
left:
BinaryTree {
value: 'b',
left: BinaryTree { value: 'd', left: null, right: null },
right: BinaryTree { value: 'e', left: null, right: null } },
right:
BinaryTree {
value: 'c',
left: null,
right:
BinaryTree {
value: 'f',
left: BinaryTree { value: 'g', left: null, right: null },
right: null } } }
*/文字列を二分木に変換する
dotstrToTree関数と、逆変換するtoDotstr関数を実装せよ。
二分木は'abd..e..c.fg...'のような文字列表現で渡される。
.はnullとし、各ノードには1文字のみ入る。
const tree = BinaryTree.dotstrToTree('abd..e..c.fg...') // 問68の二分木と同じ
tree.toDotstr // abd..e..c.fg...二分木と違って比較的簡単な問題しかないので、こちらから先に着手するのも手です。
多分木クラス
MultiwayTreeを実装せよ。
また、ノードの数を返すcount関数を実装せよ。
二分木と同様に、配列から変換できるようにしておきます。
const tree = new MultiwayTree(['a', ['f', 'g'], 'c', ['b', 'd', 'e']])
console.log(tree)
/*
MultiwayTree {
'0':
MultiwayTree { '0': MultiwayTree { value: 'g' }, value: 'f' },
'1': MultiwayTree { value: 'c' },
'2':
MultiwayTree {
'0': MultiwayTree { value: 'd' },
'1': MultiwayTree { value: 'e' },
value: 'b' },
value: 'a' }
*/
tree.count // 7文字列表現を多分木に変換する
stringToTree関数と、逆変換するtoString関数を実装せよ。
問70の多分木は'afg^^c^bd^e^^^'のように表現される。
^は前の深さに戻るという意味で、根より前に戻った場合、そこで木構造が確定する。
const tree = MultiwayTree.stringToTree('afg^^c^bd^e^^^')
console.log(tree) // 問70の多分木と同じ
tree.toString() // afg^^c^bd^e^^^根から全ノードまでの経路長の総和を求める
internalPathLength関数を実装せよ。
MultiwayTree.stringToTree('afg^^c^bd^e^^^').internalPathLength // 9多分木を後順に走査する
postorder関数を実装せよ。
MultiwayTree.stringToTree('afg^^c^bd^e^^^').postorder
// [ 'g', 'f', 'c', 'd', 'e', 'b', 'a' ]Lispのような木構造の配列表現を返す
lisp関数を実装せよ。
配列から多分木に変換できるようにしていましたが、lisp関数で逆変換もできるようにします。
関数名がlispなのは、この木構造の配列での表現がLispライクだからです。
（元々の問題では、['a', ['b', 'c']]が(a (b c))のような表現になっています）
new MultiwayTree('a').lisp
new MultiwayTree(['a', 'b']).lisp
new MultiwayTree(['a', ['b', 'c']]).lisp
new MultiwayTree(['b', 'd', 'e']).lisp
new MultiwayTree(['a', ['f', 'g'], 'c', ['b', 'd', 'e']]).lisp
// 結果は全て引数と同じになるグラフを表現する
Graphクラスを実装せよ。
頂点のリストと、辺（[from, to, cost]）のリストを渡すと、図のようなラベル付きグラフを構築できるようにします。
また、辺のリストのみ渡された場合でもグラフを構築できるようにします。
各辺はコストを持ちます。costが渡されなかった場合は1にします。
クラスの設計は今後の問題が解きやすいようにしてください。
この結果通りのインスタンスが生成されなくても構いません。
new Graph(['b', 'c', 'd', 'f', 'g', 'h', 'k'], [['b', 'c', 1], ['b', 'f', 2], ['c', 'f', 5], ['f', 'k', 3], ['g', 'h']])
// new Graph([['b', 'c', 1], ['b', 'f', 2], ['c', 'f', 5], ['f', 'k', 3], ['g', 'h'], 'd'])
/*
Graph {
b: { from: {}, to: { c: 1, f: 2 } },
c: { from: { b: 1 }, to: { f: 5 } },
d: { from: {}, to: {} },
f: { from: { b: 2, c: 5 }, to: { k: 3 } },
g: { from: {}, to: { h: 1 } },
h: { from: { g: 1 }, to: {} },
k: { from: { f: 3 }, to: {} } }
*/ある頂点から別の頂点までの経路を返す
paths関数を実装せよ。
new Graph([[1, 2], [2, 3], [1, 3], [3, 4], [4, 2], [5, 6]]).paths('1', '4')
/*
[ [ [ '1', '2', 1 ], [ '2', '3', 1 ], [ '3', '4', 1 ] ],
[ [ '1', '3', 1 ], [ '3', '4', 1 ] ] ]
*/閉路（ある頂点から始まってある頂点へ帰るまでの経路）を見つける
cycle関数を実装せよ。
new Graph([[1, 2], [2, 3], [1, 3], [3, 4], [4, 2], [5, 6]]).cycle('2')
// [ [ [ '2', '3', 1 ], [ '3', '4', 1 ], [ '4', '2', 1 ] ] ]グラフからスパニングツリーを全て探す
spanningTrees関数を実装せよ。
const trees = new Graph([['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'a'], ['a', 'c'], ['b', 'd']]).spanningTrees
trees[0]
/*
Graph {
a: { from: {}, to: { b: 1, c: 1 } },
b: { from: { a: 1 }, to: { d: 1 } },
c: { from: { a: 1 }, to: {} },
d: { from: { b: 1 }, to: {} } }
*/
trees.length // 16最小スパニングツリー(MST)をPrim法で全て探す
prim関数を実装せよ。
new Graph([[1, 2, 12], [1, 3, 34], [1, 5, 78], [2, 4, 55], [2, 5, 32], [3, 4, 61], [3, 5, 44], [4, 5, 93]]).prim
/*
[ Graph {
'1': { from: {}, to: { '2': 12, '3': 34 } },
'2': { from: { '1': 12 }, to: { '4': 55, '5': 32 } },
'3': { from: { '1': 34 }, to: {} },
'4': { from: { '2': 55 }, to: {} },
'5': { from: { '2': 32 }, to: {} } } ]
*/二つのグラフがグラフ同型であるかを返す
isomorphism関数を実装せよ。
折角なので、グラフ同型だった場合は頂点の対応表を返すと、結果が正しいか検証しやすくなって良いと思います。
const graph1 = new Graph([1, 2, 3, 4, 5, 6, 7, 8], [[1, 5], [1, 6], [1, 7], [2, 5], [2, 6], [2, 8], [3, 5], [3, 7], [3, 8], [4, 6], [4, 7], [4, 8]])
const graph2 = new Graph([1, 2, 3, 4, 5, 6, 7, 8], [[1, 2], [1, 4], [1, 5], [6, 2], [6, 5], [6, 7], [8, 4], [8, 5], [8, 7], [3, 2], [3, 4], [3, 7]])
graph1.isomorphism(graph2)
/*
{ '1': '1',
'2': '3',
'3': '6',
'4': '8',
'5': '2',
'6': '4',
'7': '5',
'8': '7' }
*/Welsh-Powellの頂点彩色アルゴリズムを使用して、隣接ノードが異なる色になるように彩色する
paint関数を実装せよ。
頂点を次数が小さくなる順序でソートした後、貪欲彩色を行います。
const graph = new Graph(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], [['a', 'b'], ['a', 'e'], ['a', 'f'], ['b', 'c'], ['b', 'g'], ['c', 'd'], ['c', 'h'], ['d', 'e'], ['d', 'i'], ['e', 'j'], ['f', 'h'], ['f', 'i'], ['g', 'i'], ['g', 'j'], ['h', 'j']])
graph.paint()
// { a: 1, b: 2, c: 1, d: 2, e: 3, f: 2, g: 1, h: 3, i: 3, j: 2 }深さを優先してグラフを探索する
depthFirst関数を実装せよ。
const graph = new Graph([1, 2, 3, 4, 5, 6, 7], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4], [6, 7]])
graph.depthFirst('1')
// [ '1', '2', '3', '4', '5' ]グラフを連結している頂点で分離する
connectedComponents関数を実装せよ。
const graph = new Graph([1, 2, 3, 4, 5, 6, 7], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4], [6, 7]])
graph.connectedComponents
// [ [ '1', '2', '3', '4', '5' ], [ '6', '7' ] ]グラフが2部グラフかどうかを返す
bipartite関数を実装せよ。
2部グラフだった場合、頂点を二つのグループに分けてみましょう。
const graph1 = new Graph([1, 2, 3, 4, 5], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4]])
const graph2 = new Graph([1, 2, 3, 4, 5], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4], [1, 3]])
graph1.bipartite // [ [ '1', '3', '5' ], [ '2', '4' ] ]
graph2.bipartite // nullN-クイーン問題を解く
queens関数を実装せよ。
const result = [...queen(8)]
result.length // 92
result[0] // [ 1, 5, 8, 6, 3, 7, 2, 4 ] などナイト・ツアー問題を解く
knightsTour関数を実装せよ。
m * nのチェス盤の上を指定したマスに置かれたナイトが全てのマスを巡回し、その辿った経路を配列として返します。
余裕があれば、最初の座標にナイトが戻ってくる結果のみを収集できるようにもしてみましょう。
knightsTour([1, 1], [8, 8]).next().value // 例では初期座標と盤面サイズを渡している
/*
[ [ 1, 1 ], [ 3, 2 ], [ 5, 1 ], [ 7, 2 ], [ 8, 4 ], [ 7, 6 ], [ 8, 8 ], [ 6, 7 ], [ 8, 6 ], [ 7, 8 ], [ 5, 7 ], [ 3, 8 ], [ 1, 7 ], [ 2, 5 ], [ 1, 3 ], [ 2, 1 ], [ 4, 2 ], [ 6, 1 ], [ 8, 2 ], [ 6, 3 ], [ 7, 1 ], [ 8, 3 ], [ 7, 5 ], [ 8, 7 ], [ 6, 8 ], [ 4, 7 ], [ 2, 8 ], [ 1, 6 ], [ 2, 4 ], [ 1, 2 ], [ 3, 1 ], [ 2, 3 ], [ 1, 5 ], [ 3, 6 ], [ 4, 8 ], [ 2, 7 ], [ 3, 5 ], [ 1, 4 ], [ 2, 2 ], [ 4, 1 ], [ 3, 3 ], [ 5, 2 ], [ 4, 4 ], [ 5, 6 ], [ 6, 4 ], [ 4, 3 ], [ 5, 5 ], [ 3, 4 ], [ 2, 6 ], [ 1, 8 ], [ 3, 7 ], [ 4, 5 ], [ 5, 3 ], [ 7, 4 ], [ 6, 2 ], [ 8, 1 ], [ 7, 3 ], [ 5, 4 ], [ 4, 6 ], [ 6, 5 ], [ 7, 7 ], [ 8, 5 ], [ 6, 6 ], [ 5, 8 ] ]
など
*/コッホ予想を解く
vonKoch関数を実装せよ。
ヘルゲ・フォン・コッホの予想によると、n個の頂点とn - 1個の辺があるグラフ（木構造）の場合、Graceful Labelingができます。
グラフの各頂点が固有のラベル（数値）を持ち、各辺が繋がる頂点のラベルの差の絶対値の固有のラベルを持っているパターンを探します。
結果は変換後の各頂点のラベルや、引数として与えられた各辺に付与されたラベルなどを返しましょう。
[...vonKoch([[4, 1], [1, 2], [1, 7], [2, 3], [2, 5], [5, 6]])]
// [ [ 7, 3, 6, 1, 5, 4, 2 ], [ 6, 4, 5, 3, 2, 1 ] ] など四則演算と等号と括弧を使って与えられた数列内で等式が成り立つものを見つける
puzzle関数を実装せよ。
配列の順番は変更しないものとします。
[...puzzle([2, 3, 5, 7, 11])]
/*
[ '2 = 3 - (5 + 7 - 11)',
'2 = 3 - 5 - (7 - 11)',
'2 = 3 - (5 + 7) + 11',
'2 = 3 - 5 - 7 + 11',
'2 = (3 * 5 + 7) / 11',
'2 * (3 - 5) = 7 - 11',
'2 - (3 - (5 + 7)) = 11',
'2 - (3 - 5 - 7) = 11',
'2 - (3 - 5) + 7 = 11',
'2 - 3 + 5 + 7 = 11' ]
*/k-正則単純グラフを生成する
regular関数を実装せよ。
k-正則グラフは全ての頂点の次数がkのグラフです。つまり、各頂点はk本の辺を持っています。
単純グラフは自己ループが無く、頂点間に複数の辺も無いグラフです。
余裕があれば、結果にグラフ同型なものを含まないようにします。
[...regular(6, 3)]
/*
[ Graph {
'1': { from: {}, to: { '2': 1, '3': 1, '4': 1 } },
'2': { from: { '1': 1 }, to: { '3': 1, '5': 1 } },
'3': { from: { '1': 1, '2': 1 }, to: { '6': 1 } },
'4': { from: { '1': 1 }, to: { '5': 1, '6': 1 } },
'5': { from: { '2': 1, '4': 1 }, to: { '6': 1 } },
'6': { from: { '3': 1, '4': 1, '5': 1 }, to: {} } },
Graph {
'1': { from: {}, to: { '2': 1, '3': 1, '4': 1 } },
'2': { from: { '1': 1 }, to: { '5': 1, '6': 1 } },
'3': { from: { '1': 1 }, to: { '4': 1, '5': 1 } },
'4': { from: { '1': 1, '3': 1 }, to: { '6': 1 } },
'5': { from: { '2': 1, '3': 1 }, to: { '6': 1 } },
'6': { from: { '2': 1, '4': 1, '5': 1 }, to: {} } } ]
*/数字を英単語に変換する
fullWords関数を実装せよ。
0以上の整数のみ引数として渡されます。
fullWords(175) // one-seven-five文字列がAdaの識別子かどうかを返す
identifier関数を実装せよ。
プログラミング言語Adaの識別子はBNFで次のように表されます。
identifier ::= letter { [ underscore ] letter | digit }
letter ::= A | ... | Z | a | ... | z
digit ::= 0 | ... | 9
underscore ::= _
identifier('Time_Of_Day') // true
identifier('2nd_turn') // false
identifier('General__Alarm') // false数独を実装せよ。
未着手。Vue.jsで実装すると面白そうです。問題生成もできるようにするといいかもしれません。
お絵描きロジックを実装せよ。
未着手。64*64程度のドット絵からパズルを生成して解けるようにすると面白いかもしれません。
クロスワードパズルを解く
crossword関数を実装せよ。
以下のように単語（キー）とクロスワードパズルが与えられたとき、マス目（ピリオド）を全て埋めたものを出力します。
解答が無い場合はnullを返すようにします。
LINUX
PROLOG
PERL
ONLINE
GNU
XML
NFS
SQL
EMACS
WEB
MAC
...... .
. . . .
. ..... .
. . . ...
. ... .
...
import fs from 'fs'
crossword(fs.readFileSync('./test/crossword/1.dat', 'utf8'))PROLOG E
E N N M
R LINUX A
L I F MAC
N SQL S
WEB
解答例の解き方は短く書こうとしていたり、丁寧に書こうとしていたりで、その時の気分によってまちまちです。
パフォーマンスも考慮していません。
知識不足で冗長になっている部分もあります。
実際に解くときは無理して短く書くよりも、読み手が分かりやすいコードを書くようにしましょう。
配列や文字列の最後の要素を取り出す
last関数を実装せよ。
const last = list => list[list.length - 1]
last([1, 2, 3, 4]) // 4
last('xyz') // z配列のindexは0から開始するため、配列の長さ - 1で最後の要素が取れます。
JavaScriptの場合は定義していないプロパティを参照するとundefinedが返ってくるので、空文字や空の配列を扱うことがあるときは注意します。
配列や文字列の最後の一つ前の要素を取り出す
butLast関数を実装せよ。
const butLast = list => list[list.length - 2]
butLast([1, 2, 3, 4]) // 3
butLast('abcdefghijklmnopqrstuvwxyz') // y問1と同様です。
配列や文字列のn番目の要素を取り出す
elementAt関数を実装せよ。
ただし、最初の要素は0番目ではなく、1番目と数える。
const elementAt = (list, index) => list[index - 1]
elementAt([1, 2, 3], 2) // 2
elementAt('JavaScript', 5) // SelementAt関数を作る意味は無いですが、たぶんこれは複数の引数を扱う練習でしょう。
配列や文字列の長さを返す
length関数を実装せよ。
ただし、Array.lengthやString.lengthは使用しないこと。
また、絵文字の長さは1と数えるようにすること。
const length = list => [...list].reduce(a => a + 1, 0)
length([123, 456, 789]) // 3
length('💃Hello, World!💃') // 15文字列の方には絵文字が混ざっています。
絵文字はサロゲートペアで表現されているため、lengthで2文字扱いになります。
スプレッド演算子を用いると、[...'💃Hello!💃']で[ '💃', 'H', 'e', 'l', 'l', 'o', '!', '💃' ]に変換できるため、lengthで正しい長さを返すことができます。
さて、lengthの使用が禁止されているため、その代わりとなる方法を考えなければなりません。
reduceは配列の要素を左から右に読んでいき、何か処理をすることができます。
引数のaはアキュムレータと呼ばれ、繰り返しの中で前の戻り値が保存されています。
つまり、aの初期値を0にし、1を足していけば長さが求められます。
配列や文字列を逆順にして返す
reverse関数を実装せよ。
ただし、Array.reverseは使用しないこと。
また、絵文字の長さは1と数えるようにすること。
const reverse = list => [...list].reduceRight(
(a, c) => a.concat(c), Array.isArray(list) ? [] : '')
reverse('A man, a plan, a canal, panama!💃') // 💃!amanap ,lanac a ,nalp a ,nam A
reverse([1, 2, 3, 4]) // [4, 3, 2, 1]絵文字の処理は問4と同様です。
配列の要素を右から左に結合していけば逆になるため、reduceRightを用います。
引数が配列のときと文字列のときで結果を変えたいので、初期値をArray.isArray(list) ? [] : ''で分岐させ、Array.concatまたはString.concatで結合させています。
配列や文字列が回文かどうかを返す
isPalindrome関数を実装せよ。
const isPalindrome = list => list.toString() === reverse(list).toString()
isPalindrome([1, 2, 3]) // false
isPalindrome('たけやぶやけた') // true
isPalindrome([1, 2, 4, 8, 16, 8, 4, 2, 1]) // true問5のreverseを使うと楽に書けます。
配列の厳密な比較は面倒なので、toStringして同じ文字列になればよしとします。
ネストしている配列を平坦（一次元配列）にして返す
flatten関数を実装せよ。
ただし、Array.flatは使用しないこと。
const flatten = list => list.reduce(
(a, c) => a.concat(Array.isArray(c) ? flatten(c) : c), [])
flatten([1, [2, [3, 4], 5]]) // [1, 2, 3, 4, 5]reduceを使います。要素が配列なら再帰的にflattenを呼んで一次元配列を返し、concatで結合します。
配列や文字列から同じ要素の繰り返しを排除して返す
compress関数を実装せよ。
const compress = list => [...list].reduce(
(a, c) => a.concat(a[a.length - 1] !== c ? c : []),
Array.isArray(list) ? [] : '')
compress([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [ 1, 2, 1, 2, 3 ]
compress('aaaabccaadeeee') // abcadereduceを使います。
アキュムレータaの最後の要素が現在値cと等しくなければcを結合し、等しければ何も結合しないようにします。
配列や文字列の同じ要素の繰り返しを配列としてまとめて返す
pack関数を実装せよ。
const pack = list => {
const isArray = Array.isArray(list)
list = [...list]
const result = []
let element = null
let current = null
list.forEach((e, i) => {
if (current === e) {
element = element.concat(e)
} else {
if (element) { result.push(element) }
current = e
element = isArray ? [e] : e
}
if (i === (list.length - 1)) {
result.push(element)
}
})
return result
}
pack([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[1, 1], [2], [1], [2, 2], [3, 3, 3, 3]]
pack('aaaabccaadeeee') // ['aaaa', 'b', 'cc', 'aa', 'd', 'eeee']結果の配列resultに格納したい要素elementと、現在対象としている値currentを宣言します。
forEachでループさせ、currentと要素が等しければelementと結合させ、等しくなければcurrentとelementに新しい値をセットします。
ループが末尾のときは、elementをresultに格納するのを忘れないようにします。
pack関数を用いて、配列や文字列をランレングス圧縮するencode関数を実装せよ。
const encode = list => pack(list).map(e => [e.length, e[0]])
encode([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[2, 1], [1, 2], [1, 1], [2, 2], [4, 3]]
encode('aaaabccaadeeee')
// [[4, 'a'], [1, 'b'], [2, 'c'], [2, 'a'], [1, 'd'], [4, 'e']]mapで各要素の長さと最初の要素を格納した配列に変換します。
問10の結果を変更し、重複が無ければランレングス圧縮せずに要素を格納する
encodeModified関数を実装せよ。
const encodeModified = list => encode(list).map(e => e[0] === 1 ? e[1] : e)
encodeModified([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[2, 1], 2, 1, [2, 2], [4, 3]]
encodeModified('aaaabccaadeeee')
// [[4, 'a'], 'b', [2, 'c'], [2, 'a'], 'd', [4, 'e']]encodeの最初の要素が1になっているペアのみをmapで展開します。
ランレングス圧縮した配列をデコードする
decodeModified関数を実装せよ。
const decodeModified = list => {
const result = []
list.forEach(e => {
if (Array.isArray(e)) for (let i = 0; i < e[0]; i++) {
result.push(e[1])
} else {
result.push(e)
}
})
return typeof(result[0]) === 'string' ? result.join('') : result
}
decodeModified([[2, 1], 2, 1, [2, 2], [4, 3]]) // [1, 1, 2, 1, 2, 2, 3, 3, 3, 3]
decodeModified([[4, 'a'], 'b', [2, 'c'], [2, 'a'], 'd', [4, 'e']]) // aaaabccaadeeee配列なら1番目の要素を長さの分だけ格納し、そうでないなら要素をそのまま配列に格納します。
文字の配列だった場合は、最後にjoinで文字列にします。文字と数値の混在には対応していません。
文字列かどうかの判定はtypeofを使っています。
typeofは、引数の型を文字列で返してくれます。
pack関数のように重複を含む配列を作らずに、直接ランレングス圧縮するencodeDirect関数を実装せよ。
const encodeDirect = list => {
list = [...list]
const result = []
let count = 1
let current = null
const push = () => result.push(count > 1 ? [count, current] : current)
list.forEach((e, i) => {
if (current === e) {
count++
} else {
if (current) { push() }
count = 1
current = e
}
if (i === (list.length - 1)) { push() }
})
return result
}
encodeDirect([1, 1, 2, 1, 2, 2, 3, 3, 3, 3]) // [[2, 1], 2, 1, [2, 2], [4, 3]]
encodeDirect('aaaabccaadeeee')
// [[4, 'a'], 'b', [2, 'c'], [2, 'a'], 'd', [4, 'e']]pack関数を改造して直接エンコードできるようにします。
要素の数をカウントして、1個しかないならその要素自体を、2個以上あるならランレングス圧縮した結果を格納します。
配列や文字列の要素を複製する
dupli関数を実装せよ。
dupli([1, 2, 3]) // [1, 1, 2, 2, 3, 3]
dupli('abc') // aabbccrepli関数のデフォルトをdupli関数の動作にするのでスキップします。
指定された回数だけ配列や文字列の要素を複製する
repli関数を実装せよ。
const repli = (list, n = 2) => {
const isStr = typeof(list) === 'string'
list = [...list]
const result = []
list.forEach(e => { for (let i = 0; i < n; i++) result.push(e) })
return isStr ? result.join('') : result
}
repli([1, 2, 3], 3) // [1, 1, 1, 2, 2, 2, 3, 3, 3]
repli('abc', 3) // aaabbbcccfor文で指定された回数分だけ配列に要素を繰り返しpushします。
デフォルト引数を与えているため、第二引数を渡さなければdupliの動作になります。
nの倍数の位置の要素を配列や文字列から削除する
drop関数を実装せよ。
const drop = (list, n) => ((ret = [...list].filter((_, i) => (i + 1) % n !== 0)) =>
typeof(list) === 'string' ? ret.join('') : ret)()
drop([1, 2, 3, 4], 2) // [1, 3]
drop('abcdefghik', 3) // 'abdeghk'1行で書く必要は全くありませんが、デフォルト引数とアロー関数を利用すれば1行で色々な処理をさせることができます。
filterでindex + 1がnで割り切れるなら除外するようにしています。
配列や文字列を指定した位置で分ける
split関数を実装せよ。
const split = (list, n) => ((x = [...list], ret = [x, x.splice(n)]) =>
typeof(list) === 'string' ? ret.map(e => e.join('')) : ret)()
split([1, 2, 3, 4], 2) // [[1, 2], [3, 4]]
split('abcdefghik', 3) // ['abc', 'defghik']spliceを使えば簡単に二つに分けることができます。
元の配列にも変更を加えてしまうので、使う際はスプレッド演算子などで配列をコピーしておいたほうが安全です。
その性質を利用して、[x, x.splice(n)]で二つに分けています。
選択した範囲を配列や文字列から取り出す
slice関数を実装せよ。
ただし、Array.slice、Array.spliceは使用しないこと。
const slice = (list, start, end = list.length) => {
let result = Array.isArray(list) ? [] : ''
for (let i = start - 1; i < end; i++) {
result = result.concat(list[i])
}
return result
}
slice([1, 2, 3, 4], 2, 4) // [2, 3, 4]
slice('abcdefghik', 3, 7) // cdefg指定した範囲内の要素をfor文でそれぞれ参照して、要素を結合して返します。
配列や文字列の要素を左にn個ずらす
rotate関数を実装せよ。
負の数を渡したときは右にずらすようにすること。
const rotate = (list, n) => ((x = [...list], _ = x.unshift(...x.splice(n))) =>
typeof(list) === 'string' ? x.join('') : x)()
rotate([1, 2, 3], 1) // [2, 3, 1]
rotate('abcdefgh', 3) // defghabc
rotate('abcdefgh', -2) // ghabcdef先頭に要素を追加するunshiftと、配列から要素を取り除くspliceを組み合わせれば簡単に実装できます。
配列や文字列のn番目の要素を削除する
removeAt関数を実装せよ。
削除した要素と処理後の配列を配列に格納し、呼び出した結果として返しなさい。
const removeAt = (n, list) => ((x = [...list], removed = x.splice(n - 1, 1)[0]) =>
[removed, typeof(list) === 'string' ? x.join('') : x])()
removeAt(3, [1, 2, 3]) // [3, [1, 2]]
removeAt(2, 'abcd') // ['b', 'acd']spliceの第二引数に数値を渡すと、その数だけ開始位置から取り除かれます。
配列や文字列の指定した位置に要素を挿入する
insertAt関数を実装せよ。
const insertAt = (element, list, n) => ((x = [...list], ret = x.concat(element, x.splice(n - 1))) =>
typeof(list) === 'string' ? ret.join('') : ret)()
insertAt(5, [1, 2, 3, 4], 3) // [1, 2, 5, 3, 4]
insertAt('X', 'abcd', 2) // aXbcdconcatとspliceを組み合わせて、指定位置にelementを挿入します。
指定された範囲内のすべての整数または文字を含む配列を生成する
range関数を実装せよ。
const range = (start, end) => {
if (typeof(start) !== typeof(end)) {
throw new Error('引数は同じ型にしてください')
}
const isStr = typeof(start) === 'string'
if (isStr && (start.length !== 1 || end.length !== 1)) {
throw new Error('引数にする文字列の長さは1にしてください')
}
const list = []
if (isStr) {
start = start.charCodeAt(0)
end = end.charCodeAt(0)
}
for (let i = start; i <= end; i++) {
list.push(isStr ? String.fromCharCode(i) : i)
}
return list
}
range(4, 9) // [4, 5 ,6, 7, 8, 9]
range('a', 'z') // ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']試しに1問解いてみるで解答済みです。
文字列の場合はString.charCodeAtで数値化し、startとendの範囲内の文字を配列に格納します。
配列や文字列から指定された数ぶんだけランダムに要素を取り出す
rndSelect関数を実装せよ。
const rndSelect = (list, n) => {
const isStr = typeof(list) === 'string'
list = [...list]
const result = []
for (let i = 0; i < n && list.length > 0; i++) {
const target = Math.floor(Math.random() * list.length)
const removed = list.splice(target, 1)[0]
result.push(removed)
}
return isStr ? result.join('') : result
}
rndSelect('abcdefgh', 3) // eda などMath.floor(Math.random() * n)で、0以上n未満の乱数を生成することができます。
あとはspliceで除去しながら結果の配列に格納していきます。
この場合、条件文にlist.length > 0を加えないと、rndSelect([1, 2, 3], 10)などの場合にundefinedを含む長さ10の配列が返ってきてしまいます。
長さnの1以上m以下の乱数列を生成する
diffSelect関数を実装せよ。
const diffSelect = (length, max) => {
if (max < 1) { throw new Error('最大値は1以上の値を指定してください') }
const result = []
for (let i = 0; i < length; i++) {
result.push(Math.floor(Math.random() * max) + 1)
}
return result
}
diffSelect(6, 49) // [23, 1, 17, 33, 21, 37] など問題23で扱ったMath.floor(Math.random() * max)に1を足すと1以上max以下の乱数になります。
配列や文字列をランダムに並び替える
rndPermu関数を実装せよ。
const rndPermu = list => rndSelect(list, list.length)
rndPermu('abcdef') // badcef など定義済みのrndSelectを使えばすぐに定義できます。
m個の要素からn個を選んだ組み合わせを返す
combinations関数を実装せよ。
const combinations = (list, n) => {
if (n < 0 || list.length < n) throw new Error('不正な引数です')
if (n === 0) return [null]
const isStr = typeof(list) === 'string'
if (n === 1) return isStr ? [...list] : [...list].map(e => [e])
const result = []
n--
for (let i = 0; i < list.length - n; i++) {
const combi = combinations(list.slice(i + 1), n)
for (let j = 0; j < combi.length; j++){
const concatenated = [list[i]].concat(combi[j])
result.push(isStr ? concatenated.join('') : concatenated)
}
}
return result
}
combinations('abcdef', 3)
// ['abc', 'abd', 'abe', 'abf', 'acd', 'ace', 'acf', 'ade', 'adf', 'aef', 'bcd', 'bce', 'bcf', 'bde', 'bdf', 'bef', 'cde', 'cdf', 'cef', 'def']高校一年生くらいで習う組み合わせです。
0の場合は、何も選ばないのでnullを入れた配列を返します。
1の場合は各要素を選ぶので、スプレッド演算子でバラします。
2以上の場合は再帰的にcombinationsを適用しましょう。
例えばabcdで2のとき、aにb, c, d、bにc, d、cにdを結合すれば組み合わせ['ab', 'ac', 'ad', 'bc', 'bd', 'cd']が出ます。
3のとき、aにb, c, dから2個選んだ組み合わせbc, bd, cdと、bにc, dから2個選んだ組み合わせcdを結合すれば['abc', 'abd', 'acd', 'bcd']が出ます。
つまり、i番目の要素に後続(i + 1以降)の要素をn - 1個選んだ組み合わせを結合すれば、組み合わせを導出できます。
配列の要素を互いに素な配列にグループ化して返す
group関数を実装せよ。
const exCombinations = (list, n) => {
const isStr = typeof(list) === 'string'
if (n === 0) return [isStr ? '' : [], list]
if (list.length === 0) return []
if (n === 1) return [...list].map((_, i) => {
let r = [...list]
r = [r.splice(i, 1), r]
return isStr ? r.map(e => e.join('')) : r
})
const result = []
const [x, ...xs] = list
exCombinations(isStr ? xs.join('') : xs, n - 1).forEach(
([ys, zs]) => result.push([isStr ? x + ys : [x].concat(ys), zs]))
exCombinations(isStr ? xs.join('') : xs, n).forEach(
([ys, zs]) => result.push([ys, isStr ? x + zs : [x].concat(zs)]))
return result
}
const group = (list, ...numbers) => {
if (list.length === 0) return [[]]
const [n, ...ns] = numbers
const result = []
exCombinations(list, n).forEach(([g, rs]) =>
group(rs, ...ns).forEach(e => result.push([g].concat(e))))
return result
}
group(["aldo","beat","carla","david","evi","flip","gary","hugo","ida"], 2, 3, 4)
// [[["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]],...] 1260個の解
group(["aldo","beat","carla","david","evi","flip","gary","hugo","ida"], 2, 2, 5)
// [[["aldo","beat"],["carla","david"],["evi","flip","gary","hugo","ida"]],...] 756個の解まず、選択されなかった要素も一緒に返すexCombinations関数を定義します。
結果は[選んだものの配列, 選ばなかったものの配列]の構造にします。
再帰させるので、再帰を抜けるための条件文は最初に書いておきましょう。
n === 1のときは、配列の全ての要素が選択されるようにします。
exCombinationsは、最初の要素を選ぶ場合と、選ばない場合を考慮して再帰させます。
exCombinationsがどう呼ばれるのか例を見てみましょう。
exCombinations([1,2,3,4], 2)
exCombinations([2,3,4], 1) // [ [ [ 2 ], [ 3, 4 ] ], [ [ 3 ], [ 2, 4 ] ], [ [ 4 ], [ 2, 3 ] ] ]
exCombinations([2,3,4], 2) // [ [ [ 2, 3 ], [ 4 ] ], [ [ 2, 4 ], [ 3 ] ], [ [ 3, 4 ], [ 2 ] ] ]最初の要素をx、後続する要素をxsとします。
最初の要素xを選んだ場合、xsから残りのn - 1個の要素を選択すればn個選んだことになります。
結果は[選んだものの配列, 選ばなかったものの配列]になっているため、結果の0番目にxを結合させます。
xを選ばなかった場合、xsから残りのn個の要素を選択すればn個選んだことになります。
xは結果の配列の1番目に結合させます。
これを再帰的に呼ぶと、配列からn個選んだ組み合わせと選ばなかった組み合わせを取得できます。
肝心のgroupですが、選んだ組み合わせに、選ばなかった組み合わせのグループを結合していけば生成できます。
配列の配列を、要素の長さでソートする
lsort関数を実装せよ。
また、要素の長さの頻度順にソートするlfsort関数を実装せよ。
const lsort = list => list.sort((a, b) => a.length - b.length)
lsort(["abc","de","fgh","de","ijkl","mn","o"]) // ["o","de","de","mn","abc","fgh","ijkl"]const lfsort = list => {
const map = new Map(encode(list.map(e => e.length).sort()).map(([value, key]) => [key, value]))
return list.sort((a, b) => map.get(a.length) - map.get(b.length))
}
lfsort(["abc", "de", "fgh", "de", "ijkl", "mn", "o"]) // ["ijkl","o","abc","fgh","de","de","mn"]sortを使えば簡単に長さの昇順にソートできます。
sortには比較関数を渡すのですが、この関数の戻り値が0未満ならaをbより前に、0なら変更なし、0より大きいならbをaより前に移動します。
つまり、前の要素の長さから次の要素の長さを引けば、どちらが長いか分かります。
頻度順にソートするには、前に作ったランレングス圧縮するencode関数を使うと楽にできます。長さの配列を昇順ソートしたものをランレングス圧縮しましょう。
長さをkey、頻度をvalueにしてMapに格納したいので、そのように入れ替えておきます。
あとは生成したMapから、長さをkeyにして頻度を参照しながらソートすればよいでしょう。
引数が素数かどうかを返す
isPrime関数を実装せよ。
const isPrime = (n, loop = 100) => {
if (n === 2) return true
if (n <= 1 || n % 2 === 0) return false
let d = (n - 1) >> 1
while (d % 2 === 0) { d >>= 1 }
const pow = (base, power, mod) => {
let result = 1
while (power > 0) {
if (power % 2 === 1) { result = (result * base) % mod }
base = (base ** 2) % mod
power >>= 1
}
return result
}
for (let i = 0; i < loop; i++) {
const rand = Math.floor(Math.random() * (n - 1) + 1)
let t = d
let y = pow(rand, t, n)
while ((t !== (n - 1)) && (y !== 1) && (y !== (n - 1))) {
y = (y ** 2) % n
t <<= 1
}
if ((y !== (n - 1)) && (t % 2 === 0)) return false
}
return true
}
isPrime(7) // true素数判定はエラトステネスの篩が単純で実装しやすいです。
今回はミラー–ラビン素数判定法で実装しました。
解答のコードは、Wikipediaの記事のRubyのコードをJavaScriptに翻訳したものになっています。
アルゴリズムに関しては、アルゴリズムと実行時間を参照してください。
ただし、確率的素数判定法なので、極々低確率で素数でないものを素数と判定してしまうことがあります。
補足ですが、(d & 1) === 0はd % 2 === 0と同じです。奇数は2n + 1なので、二進表現の1桁目が0なら偶数、1なら奇数となります。
例えば、0b1011 & 1は1で奇数、0b1010 & 1は0で偶数となります。
JavaScriptでは&演算子の優先度が===より低いので、使用する際は注意しましょう。
ユークリッドの互除法を使って最大公約数を求める
gcd関数を実装せよ。
const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b)
gcd(36, 63) // 9例えばaとbの最大公約数を求めるときgcd(a, b)は、
b === 0ならaの絶対値を返す- そうでないなら次の処理を行う
bを新しいaとするaをbで割った余りを新しいbとするgcd(a, b)を呼ぶ
のように実装すればユークリッドの互除法によって最大公約数を求めることができます。
a >= bである必要がありますが、a < bのときはaをbで割った余りを算出するとaになるので、結果的にaとbを入れ替えて再帰呼び出しすることになります。
渡した2つの整数が互いに素かどうかを返す
coprime関数を実装せよ。
const coprime = (a, b) => gcd(a, b) === 1
coprime(35, 64) // trueaとbを共に割り切る整数が1のみ、つまり最大公約数が1の場合はaとbが互いに素となっています。
問32のgcd関数を利用して、戻り値が1なら互いに素であると判別します。
オイラーのφ関数
totientを実装せよ。
const totient = n => n === 1 ? 1 : [...Array(n - 1)].map((_, i) => i + 1).filter(e => coprime(n, e)).length
totient(10) // 41からnまでの自然数のうち、nと互いに素なものの個数がφ関数の戻り値になります。
[...Array(n - 1)].map((_, i) => i + 1)をすると1..(n - 1)の配列が生成できるので、それをcoprime関数でフィルタしてから要素の個数を取得しています。
引数を素因数分解する
primeFactors関数を実装せよ。
結果は昇順にソートすること。
const primeFactors = n => ((f = ((a, b = 2) =>
(a < b ** 2) ? [a]
: (a % b === 0) ? [b].concat(f(a / b, b))
: f(a, b + 1)
)) => f(n))()
primeFactors(315) // [3, 3, 5, 7]与えられた自然数nを2から順に割っていき、割り切れなくなるまで計算します。
処理している値aと、割るのに用いる現在値bを引数にとるfを定義します。
aはsqrt(a)より大きい数では割り切れないため、その場合はaを配列に詰めて返します。
aがbで割り切れるなら、bとf(a / b, b)を結合します。
それ以外の場合は、割るのに用いる数値を1進めて再帰します。
4や10などもbに入りますが、事前にその自然数までの素数で割っている場合は割り切れないため、素数しか結果の配列には入りません。
問35の結果を累乗で表現する
primeFactorsMult関数を実装せよ。
3 ** 2なら[3, 2]と表現します。
const primeFactorsMult = n => ((factors = primeFactors(n)) =>
factors.filter((e, i, self) => self.indexOf(e) === i)
.map(e => [e, factors.filter(v => e === v).length])
)()
primeFactorsMult(315) // [[3, 2], [5, 1], [7, 1]]先ほど定義したprimeFactors関数を利用します。
まず、重複なしの配列をfilter((e, i, self) => self.indexOf(e) === i)で作ります。
これは、要素の位置と要素の検索位置が一致していない要素（重複要素）があれば排除する処理になっています。
その後、map(e => [e, factors.filter(v => e === v).length])で要素と個数をペアにした配列を作成します。
これで、primeFactorsの結果を[[底, 指数], ...]の形に変換することができます。
オイラーのφ関数を改良した
phi関数を実装せよ。
問36の結果を[[p1, m1], [p2, m2], [p3, m3], ...]としたとき、オイラーのφ関数は次のようにして計算できます。
phi(m) = (p1 - 1) * p1 ** (m1 - 1) *
(p2 - 1) * p2 ** (m2 - 1) *
(p3 - 1) * p3 ** (m3 - 1) * ...
const phi = n => primeFactorsMult(n).map(([p, m]) => (p - 1) * p ** (m - 1)).reduce((a, c) => a * c)
phi(10) // 4先ほど定義したprimeFactorsMult関数を利用します。
mapで数式の形に合わせてreduceで掛け合わせるだけで計算できます。
問34と問37の実行時間を比較せよ。
totient(10090)とphi(10090)を実行して、phi関数のほうが効率的であることを確かめてください。
せっかくなので、関数の実行時間を計測するtime関数を実装して調べましょう。
const time = (f, ...args) => {
const perf = typeof(performance) === 'undefined' ? require('perf_hooks').performance : performance
const t0 = perf.now()
f(...args)
const t1 = perf.now()
return t1 - t0
}
time(totient, 10090) < time(phi, 10090) // trueパフォーマンスを計測するにはperformance.nowを使用します。
Node.jsで実行する際はグローバルに定義されていないので、perf_hooksからrequireもしくはimportしましょう。
与えられた範囲内の素数の配列を返す
primesR関数を実装せよ。
const primesR = (min, max) => [...Array(max - min + 1)].map((_, i) => i + min).filter(e => isPrime(e))
primesR(10, 20) // [11, 13, 17, 19]isPrime関数を利用します。
下限と上限を含めた整数の配列は[...Array(max - min + 1)].map((_, i) => i + min)で作成できるので、これをisPrimeでフィルタしましょう。
ゴールドバッハの予想を確かめる
goldbach関数を実装せよ。
ゴールドバッハの予想は「全ての2よりも大きな偶数は2つの素数の和として表すことができる」という予想です。
const goldbach = n => {
if (n < 4 || n % 2 === 1) return []
if (n === 4) return [2, 2]
return [...Array(Math.floor(n / 2))]
.map((_, i) => i + 1)
.filter(e => e % 2 === 1)
.map(e => [e, n - e])
.find(([x, y]) => isPrime(x) && isPrime(y))
}
goldbach(28) // [5, 23]4未満や奇数が渡された場合は空配列を返すことにします。
4の場合は、[2, 2]を返すようにします。
引数を2で割った結果までの奇数の配列を作成します。
次に、mapでその奇数との和でnになるような整数のペアに変換します。
最後に、両方とも素数の組をfindの中でisPrimeを使って見つけます。
与えられた範囲内の
goldbachの結果を出力するgoldbachList関数を実装せよ。
第三引数を与えた場合、2つの素数がその値より大きいもののみを出力するようにすること。
const goldbachList = (min, max, gt) => {
const result = [...Array(max - min + 1)]
.map((_, i) => i + min)
.filter(e => e % 2 === 0)
.map(e => goldbach(e))
return gt ? result.filter(([x, y]) => x > gt && y > gt) : result
}
goldbachList(9, 20) // [[3, 7], [5, 7], [3, 11], [3, 13], [5, 13], [3,17]]
goldbachList(4, 2000, 50) // [[73, 919], [61, 1321], [67, 1789], [61, 1867]]偶数の配列を作成し、mapでgoldbach関数を適用するだけです。
第三引数が与えられている場合は、ペアがその値より大きいかどうかでフィルタします。
真理値表を作成する
table関数を実装せよ。
table((a, b, c) => a && (b || c))のように、引数が増えても真理値表を出力できるようにすること。
const truth = n => {
if (n < 1) return []
if (n === 1) return [[true], [false]]
const result = []
truth(n - 1).forEach(e => {
result.push(e.concat(true))
result.push(e.concat(false))
})
return result
}
const table = f => truth(f.length).map(e => [e, f(...e)])
table((a, b) => a && (a || b))
/*
[
[[true, true], true],
[[true, false], true],
[[false, true], false],
[[false, false], false]
]
*/truth関数を定義して、真理値表で使う真理値の組み合わせを生成するようにします。
これは再帰で解けば、全てのパターンを簡単に生成できます。
table関数では、渡された関数の引数の長さをFunction.lengthで取得して、truth関数に渡しています。
後はmap内で渡された関数を呼び出してその結果を配列に格納します。
与えられたbit数のグレイコードの配列を求める
gray関数を実装せよ。
const gray = n => [...Array(2 ** n)].map((_, i) => Number(i ^ (i >> 1)).toString(2).padStart(n, '0'))
gray(3) // ["000","001","011","010","110","111","101","100"]グレイコードは、対象の二進表現と、それを1bit右シフトしたもののXORをとれば生成できます。
数値を二進表現の文字列として出力するのは、Number.toStringに基数を渡せば変換することができます。
その際、頭の0は揃わないので、padStartを用いて長さを合わせます。
ハフマン符号化をする
huffman関数を実装せよ。
符号化する要素は[記号, 出現頻度]で表されます。ついでに、文字列も変換できるようにしましょう。
const huffman = raws => {
if (typeof(raws) === 'string') {
const characters = [...raws]
raws = characters.filter((e, i, self) => self.indexOf(e) === i).map(e => [e, characters.filter(v => e === v).length])
}
if (raws.length < 2) throw new Error('この配列はハフマン符号化できません')
const sort = list => list.sort(([, a], [, b]) => a - b)
while (raws.length >= 2) {
raws = sort(raws)
const [xValues, xFreq] = raws.shift()
const [yValues, yFreq] = raws.shift()
raws.unshift([[xValues, yValues], xFreq + yFreq])
}
const result = []
const encode = ([left, right], prefix = '') => {
if (Array.isArray(left)) { encode(left, `${prefix}0`) } else { result.push([left, `${prefix}0`]) }
if (Array.isArray(right)) { encode(right, `${prefix}1`) } else { result.push([right, `${prefix}1`]) }
}
encode(raws[0][0])
return result.sort(([a,], [b,]) => a.codePointAt() - b.codePointAt())
}
huffman([['a', 45], ['b', 13], ['c', 12], ['d', 16], ['e', 9], ['f', 5]])
// [['a', '0'], ['b', '101'], ['c', '100'], ['d', '111'], ['e', '1101'], ['f', '1100']]
huffman('DAEBCBACBBBC') // [['A', '111'], ['B', '0'], ['C', '10'], ['D', '1100'], ['E', '1101'] ]引数に文字列が与えられた場合は、重複を排除にしてからmapで出現頻度とペアにします。
配列として渡すときと同じ表現になれば問題ありません。
ハフマン符号化するには、ハフマンツリーと呼ばれる二分木を構築する必要があります。
ハフマンツリーは次のようにして生成します（Wikipediaより引用）。
- まず、葉を含むすべての節点のうち、親を持たないものを集める。
- その中から、最小の値を持つものと2番目に小さい値を持つものを取り出す。
- それらを子供に持つ新しい節点を作る。このとき、新しい節点の値は、両方の子供の値の和とする。
つまり、今回の場合、次のように言い換えられます。
- 頻度で昇順ソートする
- 先頭から要素を2つ取り出し、0番目の要素を左、1番目の要素を右とする
- 先頭に
[[左, 右], 頻度の和]を格納する - 1～3を配列の長さが1になるまで繰り返す
これで、結果の配列の先頭にはハフマンツリーが格納されることになります。
次に、ハフマンツリーを用いてハフマン符号化します。
左なら0、右なら1を文字列の後ろに付け加えていくことにします。
子が配列の場合は、再帰で子の左右を見て、葉に突き当たるまで処理を繰り返しましょう。
子が葉の場合は、結果の配列に[子, 子をハフマン符号化したもの]を格納します。
ハフマン符号化の結果は実装や引数によって異なります。
復号するには、どの文字がどの符号に対応しているかの対応表（huffman関数の結果）が必要になります。
二分木クラス
BinaryTreeを実装せよ。
二分木は、あるノードが持つ子の数が2個以下の木構造です。
以下のようにコンストラクタに二分木にしたい配列を渡すと、二分木として表現できるようにします。
引数とする配列は、[値, 左部分木, 右部分木]で表現することにします。
class BinaryTree {
constructor(value, left = null, right = null) {
if (Array.isArray(value)) { [value, left, right] = value }
else if (value instanceof BinaryTree) { ({value, left, right} = value) }
this.value = value
this.left = left !== null ? new BinaryTree(left) : left
this.right = right !== null ? new BinaryTree(right) : right
}
toString() {
return JSON.stringify(this, null, 2)
}
}
const tree = new BinaryTree(['a', ['b', 'd', 'e'], ['c', null, ['f', 'g', null]]])
console.log(tree.toString())
/*
{
"value": "a",
"left": {
"value": "b",
"left": {
"value": "d",
"left": null,
"right": null
},
"right": {
"value": "e",
"left": null,
"right": null
}
},
"right": {
"value": "c",
"left": null,
"right": {
"value": "f",
"left": {
"value": "g",
"left": null,
"right": null
},
"right": null
}
}
}
*/二分木を表現した配列が渡されたら、コンストラクタの引数のvalue、left、rightに分割代入します。
また、valueに二分木が渡されたときは、その二分木のコピーを作成できるようにしておきます。
JavaScriptではコンストラクタを複数定義することができないので、擬似的に定義したい場合は引数の数や型などで条件を分岐する必要があります。
結果を見たいとき、今回の場合はtoStringでJSONにシリアライズできるようにしておくと木構造が把握しやすくなるかもしれません（ので、問題に追加しました）。
左部分木と右部分木のノードの数の差が1以下である二分木を全て生成する
cbalTree関数を実装せよ。
下記の省略されている[BinaryTree]の部分は、BinaryTree { value: 'x', left: null, right: null }のようになっています。
BinaryTree.cbalTree = n => {
n = Math.floor(n)
if (n <= 0) return [null]
if (n === 1) return [new BinaryTree('x')]
const result = []
if (n % 2 === 1) {
const trees = BinaryTree.cbalTree((n - 1) / 2)
trees.forEach(left => trees.forEach(right => result.push(new BinaryTree('x', left, right))))
} else {
const left = BinaryTree.cbalTree(n / 2 - 1)
const right = BinaryTree.cbalTree(n / 2)
left.forEach(l => right.forEach(r => result.push(...[new BinaryTree('x', l, r), new BinaryTree('x', r, l)])))
}
return result
}
BinaryTree.cbalTree(4)
/*
[ BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right: BinaryTree { value: 'x', left: null, right: [BinaryTree] } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: [BinaryTree] },
right: BinaryTree { value: 'x', left: null, right: null } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right: BinaryTree { value: 'x', left: [BinaryTree], right: null } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: [BinaryTree], right: null },
right: BinaryTree { value: 'x', left: null, right: null } } ]
*/再帰させたいので、終了する条件から先に考えてしまいましょう。
0以下ならそもそも木構造が無いのでnullで、1ならxのノードがあるだけの木です。
左右の部分木のノード数の合計は根を取り除いた数なのでn - 1になります。
nが奇数のとき、左部分木と右部分木のノードの数の差は0です。
なのでcbalTree((n - 1) / 2)の結果を二重ループさせて、全ての二分木のパターンを生成します。
nが偶数のとき、左部分木と右部分木のノードの数の差は1です。
2の場合を考えてみると、左右のどちらかがnullになることが分かると思います。
つまり、左右の部分木がcbalTree(n / 2 - 1)とcbalTree(n / 2)の結果を組み合わせたパターンになります。
二分木が対称かどうかを返す
isSymmetric関数を実装せよ。
ノードの値は比較しません。あくまで、構造が対称かどうかを調べます。
class BinaryTree {
/* 省略 */
get isSymmetric() {
const mirror = (x, y) => {
if (x === null && y === null) return true
if (x !== null && y !== null) return mirror(x.left, y.right) && mirror(x.right, y.left)
return false
}
return mirror(this, this)
}
}
const x = new BinaryTree(['x', 'x', null])
const y = new BinaryTree(['x', 'x', 'x'])
x.isSymmetric // false
y.isSymmetric // truemirror関数は二つの木を比較して対称かどうかを調べてくれる関数です。
左の要素と右の要素がnullの場合はtrueにします。
木構造が入っている場合は、左右の要素をmirror関数を再帰呼び出しすることで比較します。
mirror関数の最初の呼び出しは、この二分木自身(this)を渡しましょう。
二分探索木を生成する
searchTree関数を実装せよ。
引数は一次元配列とします。
BinaryTree.searchTree = numbers => {
if (numbers.length === 0) return null
const [x, ...xs] = numbers
const tree = new BinaryTree(x)
let target = tree
const insert = n => {
const property = n < target.value ? 'left' : 'right'
if (target[property] !== null) {
target = target[property]
insert(n)
} else {
target[property] = new BinaryTree(n)
target = tree
}
}
xs.forEach(insert)
return tree
}
BinaryTree.searchTree([3, 2, 5, 7, 1])
/*
BinaryTree {
value: 3,
left:
BinaryTree {
value: 2,
left: BinaryTree { value: 1, left: null, right: null },
right: null },
right:
BinaryTree {
value: 5,
left: null,
right: BinaryTree { value: 7, left: null, right: null } } }
*/
BinaryTree.searchTree([5, 3, 18, 1, 4, 12, 21]).isSymmetric // true
BinaryTree.searchTree([3, 2, 5, 7, 4]).isSymmetric // false二分探索木では、挿入しようとしている値が着目しているノードの値より小さければ左に、それ以上なら右に挿入を試みます。
挿入先にもノードがあるなら同様の操作を繰り返していき、何もなければ（nullの場合）挿入します。
解答例では、insert関数を再帰呼び出しすることで、挿入位置を決定して挿入しています。
JavaScriptのオブジェクトは連想配列のようになっているので、添字にプロパティ名を渡せば参照できます。
今回のように左や右を見るだけであれば便利かもしれません。
問55のように平衡で、かつ対称な二分木があれば返す
symCbalTrees関数を実装せよ。
引数はノード数で、そのような二分木が見つからなければ[]を返します。
BinaryTree.symCbalTrees = n => BinaryTree.cbalTree(n).filter(e => e.isSymmetric)
BinaryTree.symCbalTrees(5)
/*
[ BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: [BinaryTree] },
right: BinaryTree { value: 'x', left: [BinaryTree], right: null } },
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: [BinaryTree], right: null },
right: BinaryTree { value: 'x', left: null, right: [BinaryTree] } } ]
*/cbalTreeの結果をisSymmetricでフィルタするだけです。
既に単体テスト済みなら、今まで作った関数を組み合わせるのが安全でしょう。
左部分木と右部分木の高さの差が1以下である二分木を全て生成する
hbalTree関数を実装せよ。
引数は生成する木構造の高さ（根ノードの高さ）とします。
BinaryTree.hbalTree = maxHeight => {
if (maxHeight <= 0) return [null]
if (maxHeight === 1) return [new BinaryTree('x')]
const highers = BinaryTree.hbalTree(maxHeight - 1)
const lowers = BinaryTree.hbalTree(maxHeight - 2)
const result = []
lowers.forEach(lower => highers.forEach(higher => result.push(new BinaryTree('x', lower, higher))))
highers.forEach(x => highers.forEach(y => result.push(new BinaryTree('x', x, y))))
highers.forEach(higher => lowers.forEach(lower => result.push(new BinaryTree('x', higher, lower))))
return result
}
BinaryTree.hbalTree(3)[0]
/*
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right:
BinaryTree {
value: 'x',
left: null,
right: BinaryTree { value: 'x', left: null, right: null } } }
*/
BinaryTree.hbalTree(4).length // 315このような二分木をAVL木といいます。
AVL木はどの左部分木と右部分木を見ても高さの差が1以下です。つまり、
- 左部分木が低くて右部分木が高い二分木
- 左部分木と右部分木の高さが同じ二分木
- 左部分木が高くて右部分木が低い二分木
をそれぞれ生成して格納すればいいことになります。
与えられた数のノードを持つ問59のような二分木を全て生成する
hbalTreeNodes関数を実装せよ。
ヒント
まず、左部分木と右部分木の高さの差が1以下である二分木の高さhを実現するために必要な最小ノード数を計算するminNodes関数を定義します。
少し数式を考えてみれば、最小ノード数はフィボナッチ数列に近いものになるはずです。
次に、minNodes関数を用いて、問題の木構造の最大の高さを求めるmaxHeight関数を定義します。
その後、最小から最大までの高さについて、与えられたノード数を持つ二分木があるかどうか調べます。
class BinaryTree {
/* 省略 */
get countNodes() {
const count = tree => tree === null ? 0 : count(tree.left) + count(tree.right) + 1
return count(this)
}
}
const hbalTreeMaxHeight = (n, prev = 0, ac = 1, height = 1) => {
if (n < 1) return 0
const value = prev + ac + 1
return n < value ? height : hbalTreeMaxHeight(n, ac, value, height + 1)
}
BinaryTree.hbalTreeNodes = n => {
if (n <= 0) return [null]
const minHeight = Math.ceil(Math.log2(n + 1))
const maxHeight = hbalTreeMaxHeight(n)
const result = []
for (let i = minHeight; i <= maxHeight; i++) {
const trees = BinaryTree.hbalTree(i).filter(e => e.countNodes === n)
result.push(...trees)
}
return result
}
BinaryTree.hbalTreeNodes(15).length // 1553
[0, 1, 2, 3].map(BinaryTree.hbalTreeNodes)
/*
[ [ null ],
[ BinaryTree { value: 'x', left: null, right: null } ],
[ BinaryTree { value: 'x', left: null, right: [BinaryTree] },
BinaryTree { value: 'x', left: [BinaryTree], right: null } ],
[ BinaryTree { value: 'x', left: [BinaryTree], right: [BinaryTree] } ] ]
*/先に、BinaryTreeクラスに合計ノード数を計算するcountNodesを定義しておきます。
高さhのAVL木の最小ノード数を求める関数a(h)について考えましょう。
高さ1のときは最小ノード数は1です。高さ2のときは2で、高さ3のときは4ですね。
また、高さhを実現するためにノード数を最小にする場合、左部分木と右部分木の高さが異なります。
つまり、一方の部分木の最小ノード数はa(h - 1)で、もう一方の部分木の最小ノード数はa(h - 2)となります。
根も含めるので、a(h) = a(h - 1) + a(h - 2) + 1となります。
（n番目のフィボナッチ数はa(n) = a(n - 1) + a(n - 2)なので、この漸化式にかなり似ていますね）
求めたa(h)により、高さhのAVL木の最小ノード数は[1, 2, 4, 7, 12, 20, 33, 54, 88, 143, ...]のようになることが分かりました。
この配列のindex + 1が最大の高さと一致しているため、ノード数と数列を比較しながら最大の高さを求めるhbalTreeMaxHeight関数を定義します。
また、最小の高さはノードを順に詰めていくため、Math.ceil(Math.log2(n + 1))になります。
あとは最小から最大の高さまでhbalTreeでAVL木を全て生成してcountNodesでフィルタします。
二分木の葉の数を数える
countLeaves関数を実装せよ。
class BinaryTree {
/* 省略 */
get countLeaves() {
const count = tree => {
if (tree === null) return 0
const { left, right } = tree
return left === null && right === null ? 1 : count(left) + count(right)
}
return count(this)
}
}
(new BinaryTree([1, [2, null, 4], 2])).countLeaves // 2葉以外のノードは無視するようにして、count関数を再帰させて数えます。
二分木の葉のリストを返す
leaves関数を実装せよ。
class BinaryTree {
/* 省略 */
get leaves() {
const take = tree => {
if (tree === null) return []
const { value, left, right } = tree
return left === null && right === null ? [value] : [...take(left), ...take(right)]
}
return take(this)
}
}
(new BinaryTree([1, [2, null, 4], 2])).leaves // [ 4, 2 ]countLeavesの結果を少し変えれば実装できます。
葉ならvalueのみ格納された配列を返し、それ以外なら再帰します。
二分木の内部ノード（葉以外の節）を返す
internals関数を実装せよ。
class BinaryTree {
/* 省略 */
get internals() {
const take = tree => {
if (tree === null) return []
const { value, left, right } = tree
return left === null && right === null ? [] : [value, ...take(left), ...take(right)]
}
return take(this)
}
}
(new BinaryTree([1, [2, null, 4], 2])).internals // [ 1, 2 ]これもleavesを少し変えれば実装できます。
葉なら空配列を返すようにして、それ以外ならvalue（内部ノード）と、leftとrightの内部ノードの配列を結合したものを返します。
指定された深さのノードのリストを返す
atLevel関数を実装せよ。
class BinaryTree {
/* 省略 */
atLevel(level) {
if (level === 1) return [this.value]
if (level > 1) {
const left = this.left === null ? [] : this.left.atLevel(level - 1)
const right = this.right === null ? [] : this.right.atLevel(level - 1)
return [...left, ...right]
}
return []
}
}
(new BinaryTree([1, [2, null, 4], 2])).atLevel(2) // [ 2, 2 ]levelが1なら、その深さのノードの値のみを返します。
levelが1より大きい場合、左右の部分木がnullでないなら、それぞれatLevel(level - 1)を呼びます。
得られた配列を結合すると、結果的に同じ深さのノードを集めることができます。
完全二分木を生成する
completeBinaryTree関数と、完全二分木かどうかを返すisCompleteBinaryTree関数を実装せよ。
完全二分木は、根からすべての葉までの深さの差が1以下で、葉が左詰めになっている二分木です。
引数はノード数とします。
class BinaryTree {
/* 省略 */
get isCompleteBinaryTree() {
const equals = (x, y) => {
if (x === null && y === null) return true
if (x !== null && y !== null) return equals(x.left, y.left) && equals(x.right, y.right)
return false
}
return equals(this, BinaryTree.completeBinaryTree(this.countNodes))
}
}
BinaryTree.completeBinaryTree = n => ((f = x => x > n ? null : new BinaryTree('x', f(x * 2), f(x * 2 + 1))) => f(1))()
BinaryTree.completeBinaryTree(4)
/*
BinaryTree {
value: 'x',
left:
BinaryTree {
value: 'x',
left: BinaryTree { value: 'x', left: null, right: null },
right: null },
right: BinaryTree { value: 'x', left: null, right: null } }
*/
(new BinaryTree(['x', ['x', 'x', null], ['x', null, null]])).isCompleteBinaryTree // true
(new BinaryTree(['x', ['x', 'x', null], ['x', null, 'x']])).isCompleteBinaryTree // false完全二分木の幅優先探索について、任意の部分木の根ノードをn番目とするとき、子ノードは左が2n番目、右が2n + 1番目になります。
これを利用するとcompleteBinaryTree関数を定義できます。指定したノード数を超えてしまった場合はnullを返します。
二分木が完全二分木かどうかを調べるには、調べたい二分木のノード数から完全二分木を生成して、これらの構造が等しいかどうかを確かめましょう。
次の図のように、各ノードに座標を付与する
layout関数を実装せよ。
次のようにノードに座標を割り振ります。
- x座標は、中順に走査したときの順番
- y座標は、そのノードがある深さ
結果が見づらくなるので、各ノードの座標を分かりやすく取得できるpositions関数もついでに定義しましょう。
class BinaryTree {
/* 省略 */
get positions() {
const f = tree => {
if (tree === null) return []
const { value, x, y } = tree
return [{ value, x, y }, ...f(tree.left), ...f(tree.right)]
}
return f(this)
}
layout() {
const f = (x, y, tree) => {
if (tree === null) return x
const lx = f(x, y + 1, tree.left)
tree.x = lx
tree.y = y
return f(lx + 1, y + 1, tree.right)
}
f(1, 1, this)
return this
}
}
const result = (new BinaryTree(['n', ['k', ['c', 'a', ['h', ['g', 'e', null], null]], 'm'], ['u', ['p', null, ['s', 'q', null]], null]])).layout()
result.positions
/*
[ { value: 'n', x: 8, y: 1 },
{ value: 'k', x: 6, y: 2 },
{ value: 'c', x: 2, y: 3 },
{ value: 'a', x: 1, y: 4 },
{ value: 'h', x: 5, y: 4 },
{ value: 'g', x: 4, y: 5 },
{ value: 'e', x: 3, y: 6 },
{ value: 'm', x: 7, y: 3 },
{ value: 'u', x: 12, y: 2 },
{ value: 'p', x: 9, y: 3 },
{ value: 's', x: 11, y: 4 },
{ value: 'q', x: 10, y: 5 } ]
*/positionsは、各ノードのvalueとxとyプロパティを入れたオブジェクトをまとめた配列を返すようにします。
中順の走査では、一度左側の子を再帰で見てから、今見ているノードのx座標を決定します。
その後、右側の子のx座標を決定されたx座標 + 1として再帰呼び出しし、これを戻り値とします。
次の図のように、各ノードに座標を付与する
wideLayout関数を実装せよ。
配置ルールは図を見て考えてください。
ヒント
ある深さの隣接するノードの水平距離が一定なことに着目しましょう。
class BinaryTree {
/* 省略 */
get height() {
const f = tree => tree === null ? 0 : Math.max(f(tree.left), f(tree.right)) + 1
return f(this)
}
get leftHeight() {
const f = tree => tree === null ? 0 : f(tree.left) + 1
return f(this)
}
wideLayout() {
const f = (x, y, sep, tree) => {
if (tree === null) return
tree.x = x
tree.y = y
f(x - sep, y + 1, sep / 2, tree.left)
f(x + sep, y + 1, sep / 2, tree.right)
}
const h = this.height
const lh = this.leftHeight
const x = 2 ** (h - 1) - 2 ** (h - lh) + 1
const sep = 2 ** (h - 2)
f(x, 1, sep, this)
return this
}
}
const result = (new BinaryTree(['n', ['k', ['c', 'a', ['e', 'd', 'g']], 'm'], ['u', ['p', null, 'q'], null]])).wideLayout()
result.positions
/*
[ { value: 'n', x: 15, y: 1 },
{ value: 'k', x: 7, y: 2 },
{ value: 'c', x: 3, y: 3 },
{ value: 'a', x: 1, y: 4 },
{ value: 'e', x: 5, y: 4 },
{ value: 'd', x: 4, y: 5 },
{ value: 'g', x: 6, y: 5 },
{ value: 'm', x: 11, y: 3 },
{ value: 'u', x: 23, y: 2 },
{ value: 'p', x: 19, y: 3 },
{ value: 'q', x: 21, y: 4 } ]
*/図を見ると、一番深いところの二分木は、左右の子ノードと親ノード間のx座標の距離が1です。
また、それより一つ浅いところは距離が2になっていて、さらに一つ浅いところは4になっています。
つまり、深さによって[1, 2, 4, 8, ...]のように間隔が大きくなります。
左右にノードがあるだけの二分木の高さは2なので、間隔は2 ** (高さ - 2)で求められそうです。
間隔は一つ深いところになると半分になります。
x座標は、左が現在のx座標 - 間隔、右が現在のx座標 + 間隔になるので、これを引数にして再帰しましょう。
最初の関数呼び出しの引数ですが、根ノードのx座標は2 ** (高さ - 1) - 2 ** (高さ - 左端の子までの高さ) + 1で求められます。
後述していますが、x座標を0から始めて左端のノードのx座標を見てからもう一度振りなおす手法でも、各ノードのx座標を求められるかと思います。
次の図のように、各ノードに座標を付与する
compactLayout関数を実装せよ。
このレイアウトを用いると、全てのノードにおいて一定の対称性を保ちつつ、コンパクトに二分木を表現できます。
配置ルールは図を見て考えてください。
ヒント
ノードと後継ノード間の水平距離に着目しましょう。
class BinaryTree {
/* 省略 */
compactLayout() {
const margin = (left, right) => {
if (left === null || right === null) return 1
if (left.right === null || right.left === null) return 1
return margin(left.right, right.left) + 1
}
const layout = (x, y, tree) => {
if (tree === null) return
tree.x = x
tree.y = y
const m = margin(tree.left, tree.right)
layout(x - m, y + 1, tree.left)
layout(x + m, y + 1, tree.right)
}
const leftX = tree => tree.positions.sort(({x: a}, {x: b}) => a - b)[0].x
layout(0, 1, this)
const x = Math.abs(leftX(this)) + 1
layout(x, 1, this)
return this
}
}
const result = (new BinaryTree(['n', ['k', ['c', 'a', ['e', 'd', 'g']], 'm'], ['u', ['p', null, 'q'], null]])).compactLayout()
result.positions
/*
[ { value: 'n', x: 5, y: 1 },
{ value: 'k', x: 3, y: 2 },
{ value: 'c', x: 2, y: 3 },
{ value: 'a', x: 1, y: 4 },
{ value: 'e', x: 3, y: 4 },
{ value: 'd', x: 2, y: 5 },
{ value: 'g', x: 4, y: 5 },
{ value: 'm', x: 4, y: 3 },
{ value: 'u', x: 7, y: 2 },
{ value: 'p', x: 6, y: 3 },
{ value: 'q', x: 7, y: 4 } ]
*/間隔は1が標準で、左の子ノードの右、右の子ノードの左があると2になるようです。
また、左右右、右左左が両方とも存在すると3になることが分かります。
margin関数はこの比較を再帰呼び出しですることで、間隔を算出しています。
この間隔を引けば左側のx座標、足せば右側のx座標が求められます。
根ノードのx座標が不明なので、0として座標を計算します。
その後、左端のノードのx座標の絶対値 + 1を初期のx座標とし、再び座標を計算します。
文字列をパースして二分木にする
fromString関数を実装せよ。
二分木の文字列表現はx(y,a(,b))のようにして与えられる。
BinaryTree.stringToTree = str => {
if (str === null) return null
const regex = /^([^\(\,]+)\((.+)\)$/
const groups = regex.exec(str)
if (groups === null) {
if (str.indexOf('(') !== -1 || str.indexOf(')') !== -1 || str.indexOf(',') !== -1) throw new Error('parse error')
return new BinaryTree(str)
}
const [, id, arg] = groups
const args = []
let value = null
let brace = 0
for (let i = 0; i < arg.length; i++) {
const current = arg[i]
if (current === ',' && brace === 0) {
args.push(value)
value = null
} else {
value = (value || '') + current
brace = current === '(' ? brace + 1
: current === ')' ? brace - 1
: brace
}
if (i === arg.length - 1) { args.push(value) }
}
if (args.length !== 2) throw new Error('parse error')
const [left, right] = args
return new BinaryTree(id, BinaryTree.stringToTree(left), BinaryTree.stringToTree(right))
}
BinaryTree.stringToTree('x(y,a(,b))')
/*
BinaryTree {
value: 'x',
left: BinaryTree { value: 'y', left: null, right: null },
right:
BinaryTree {
value: 'a',
left: null,
right: BinaryTree { value: 'b', left: null, right: null } } }
*/正規表現^([^\(\,]+)\((.+)\)$でノードの値と括弧の中の文字列を抜き出します。
一致しなかった場合はノードの値だけなので、括弧やカンマが含まれていないか確認してから二分木インスタンスを生成して返します。
一致した場合、括弧の中の文字列を調べなければなりません。
括弧に囲われていないカンマで左右を区切りたいので、変数braceで括弧で囲われているかどうかを判別します。
文字列を二つに分けられたらstringToTree関数を再帰して左部分木と右部分木も構築します。
二分木を前順に走査する
preorder関数と、中順に走査するinorder関数を実装せよ。
また、前順と中順に走査した結果を用いて二分木を生成するpreInTree関数を実装せよ。
class BinaryTree {
/* 省略 */
get preorder() {
const f = tree => tree === null ? [] : [tree.value, ...f(tree.left), ...f(tree.right)]
return f(this)
}
get inorder() {
const f = tree => tree === null ? [] : [...f(tree.left), tree.value, ...f(tree.right)]
return f(this)
}
}
BinaryTree.preInTree = (preorder, inorder) => {
if (preorder.length === 0 || inorder.length === 0) return null
if (inorder.length === 1) return new BinaryTree(inorder[0])
const [x, ...xs] = preorder
const index = inorder.indexOf(x)
if (index === -1) return BinaryTree.preInTree(xs, inorder)
const left = inorder.slice(0, index)
const right = inorder.slice(index + 1, inorder.length)
return new BinaryTree(x, BinaryTree.preInTree(xs, left), BinaryTree.preInTree(xs, right))
}
const tree = BinaryTree.stringToTree('a(b(d,e),c(,f(g,)))')
tree.preorder // [ 'a', 'b', 'd', 'e', 'c', 'f', 'g' ]
tree.inorder // [ 'd', 'b', 'e', 'a', 'c', 'g', 'f' ]
BinaryTree.preInTree(tree.preorder, tree.inorder)
/*
BinaryTree {
value: 'a',
left:
BinaryTree {
value: 'b',
left: BinaryTree { value: 'd', left: null, right: null },
right: BinaryTree { value: 'e', left: null, right: null } },
right:
BinaryTree {
value: 'c',
left: null,
right:
BinaryTree {
value: 'f',
left: BinaryTree { value: 'g', left: null, right: null },
right: null } } }
*/前順、中順で走査をするときは、その名の通り再帰すればノードを順番に集められます。
preInTree関数ですが、まずinorderの長さが1ならその要素で二分木を作って返します。
preorderの先頭の要素がinorderに無い場合、preorderの残りの要素から探します。
inorderに含まれる場合は、inorderを左部分木に含まれる要素の配列leftと右部分木に含まれる要素の配列rightに分けます。
それぞれの配列をpreInTree関数のinorderとして渡して再帰させれば、目的の二分木を構築できます。
文字列を二分木に変換する
dotstrToTree関数と、逆変換するtoDotstr関数を実装せよ。
二分木は'abd..e..c.fg...'のような文字列表現で渡される。
.はnullとし、各ノードには1文字のみ入る。
class BinaryTree {
/* 省略 */
toDotstr() {
const f = tree => tree === null ? '.' : tree.value + f(tree.left) + f(tree.right)
return f(this)
}
}
BinaryTree.dotstrToTree = ds => {
const f = str => {
if (str.length === 0) return [null, '']
let [x, ...xs] = [...str]
xs = xs.join('')
if (x === '.') return [null, xs]
const [left, ys] = f(xs)
const [right, rest] = f(ys)
return [new BinaryTree(x, left, right), rest]
}
return f(ds)[0]
}
const tree = BinaryTree.dotstrToTree('abd..e..c.fg...') // 問68の二分木と同じ
tree.toDotstr() // abd..e..c.fg...戻り値は[二分木, 残りの文字列]とします。
dotstrToTree関数では、渡した文字列を先頭から順番に見ていきます。
見ている文字が.なら、[null, 残りの文字列]を返します。
それ以外のときは、まず左部分木を構築しつつ残りの文字列を取得し、右部分木をその残りの文字列から構築します。
そして、今見ている文字を根とした二分木と残りの文字列のペアを返します。
toDotstr関数は前順で走査するだけです。
ノードの値が一文字でない場合は正しく変換されないため、この文字列表現は一文字の場合にしか使えません。
多分木クラス
MultiwayTreeを実装せよ。
また、ノードの数を返すcount関数を実装せよ。
二分木と同様に、配列から変換できるようにしておきます。
class MultiwayTree {
constructor(value, ...args) {
if (Array.isArray(value)) { [value, ...args] = value }
else if (value instanceof MultiwayTree) { args = [...value]; ({ value } = value) }
this.value = value
args.forEach((e, i) => this[i] = e !== null ? new MultiwayTree(e) : e)
}
* [Symbol.iterator]() {
for (let i = 0; typeof(this[i]) !== 'undefined'; i++) {
yield this[i]
}
}
get count() {
const f = x => [...x].map(f).reduce((a, c) => a + c, 1)
return f(this)
}
}
const tree = new MultiwayTree(['a', ['f', 'g'], 'c', ['b', 'd', 'e']])
console.log(tree)
/*
MultiwayTree {
'0':
MultiwayTree { '0': MultiwayTree { value: 'g' }, value: 'f' },
'1': MultiwayTree { value: 'c' },
'2':
MultiwayTree {
'0': MultiwayTree { value: 'd' },
'1': MultiwayTree { value: 'e' },
value: 'b' },
value: 'a' }
*/
tree.count // 7多分木は配列と似た構造になっています。こう表現することで子が増えても挿入することができるようになります。
MultiwayTreeはIterableにすると子が参照しやすくなって便利でしょう。
[Symbol.iterator]()メソッドを実装する必要がありますが、ジェネレータ関数にすると楽なので*を頭につけておきます。
this[i]がundefinedになるまでループします。ループ内ではyieldでthis[i]を戻しましょう。
これだけでスプレッド演算子...やfor...ofが使えるようになります。
コンストラクタは二分木のときとさほど変わりません。
引数が複数あるときはループして該当するindexに部分木を入れます。
countでは、子に関数を適用した後、reduceで合計を求めます。
根が含まれるので初期値は1にしておきます。
文字列表現を多分木に変換する
stringToTree関数と、逆変換するtoString関数を実装せよ。
問70の多分木は'afg^^c^bd^e^^^'のように表現される。
^は前の深さに戻るという意味で、根より前に戻った場合、そこで木構造が確定する。
class MultiwayTree {
/* 省略 */
push(child) {
let i = 0
while (true) if (this[i]) { i++ } else {
this[i] = new MultiwayTree(child)
return i + 1
}
}
toString() {
return `${ this.value }${ [...this].join('') }^`
}
}
MultiwayTree.stringToTree = str => {
if (str.length === 0) return null
const trees = []
for (const s of str) if (s === '^') {
const parent = trees[trees.length - 2]
if (parent) { parent.push(trees.pop()) } else break
} else {
trees.push(new MultiwayTree(s))
}
return trees[0]
}
const tree = MultiwayTree.stringToTree('afg^^c^bd^e^^^')
console.log(tree) // 問70の多分木と同じ
tree.toString() // afg^^c^bd^e^^^toStringはノードの値、子の文字列表現、^を結合したものを返します。
オブジェクトを文字列にしようとしたときに自動的にtoStringが呼ばれるのを利用しています。
stringToTree関数は文字列を先頭から順番に見て、^と等しければ親の多分木に子を挿入します。
（親となる多分木はtreesの最後尾の一つ前、その子となる多分木は最後尾に格納されています）
push関数で何も入っていないindexに多分木を挿入できるようにしておきます。
^以外の文字のときは、新しい多分木を生成してtreesに保持しておきます。
trees[0]には構築された多分木が入っていることになるので、最後にそれを返します。
根から全ノードまでの経路長の総和を求める
internalPathLength関数を実装せよ。
class MultiwayTree {
/* 省略 */
get internalPathLength() {
const f = (tree, depth = 0) => [...tree].map(e => f(e, depth + 1)).reduce((a, c) => a + c, depth)
return f(this)
}
}
MultiwayTree.stringToTree('afg^^c^bd^e^^^').internalPathLength // 9根から各ノードまでの経路長は、根から見た深さと等しくなります。
自身の深さと子の深さを足していけば、根から全ノードまでの経路長の総和を求められます。
多分木を後順に走査する
postorder関数を実装せよ。
class MultiwayTree {
/* 省略 */
get postorder() {
const f = tree => [...[...tree].map(f).reduce((a, c) => a.concat(c), []), tree.value]
return f(this)
}
}
MultiwayTree.stringToTree('afg^^c^bd^e^^^').postorder
// [ 'g', 'f', 'c', 'd', 'e', 'b', 'a' ]後順に走査するので、tree.valueは配列の後ろ側に入れます。
子に対しては関数を適用した後、戻り値の配列を結合して展開するようにします。
Lispのような木構造の配列表現を返す
lisp関数を実装せよ。
配列から多分木に変換できるようにしていましたが、lisp関数で逆変換もできるようにします。
関数名がlispなのは、この木構造の配列での表現がLispライクだからです。
（元々の問題では、['a', ['b', 'c']]が(a (b c))のような表現になっています）
class MultiwayTree {
/* 省略 */
get lisp() {
const f = tree => tree[0] ? [tree.value, ...[...tree].map(f)] : tree.value
return f(this)
}
}
new MultiwayTree('a').lisp
new MultiwayTree(['a', 'b']).lisp
new MultiwayTree(['a', ['b', 'c']]).lisp
new MultiwayTree(['b', 'd', 'e']).lisp
new MultiwayTree(['a', ['f', 'g'], 'c', ['b', 'd', 'e']]).lisp
// 結果は全てコンストラクタの引数と同じになる子を持たなければ、tree.valueをそのまま返します。
子を持つ場合、配列にtree.valueと子に関数を適用したものを格納して返します。
グラフを表現する
Graphクラスを実装せよ。
頂点のリストと、辺（[from, to, cost]）のリストを渡すと、図のようなラベル付きグラフを構築できるようにします。
また、辺のリストのみ渡された場合でもグラフを構築できるようにします。
各辺はコストを持ちます。costが渡されなかった場合は1などのデフォルト値にします。
クラスの設計は今後の問題が解きやすいようにしてください。
この結果通りのインスタンスが生成されなくても構いません。
class Graph {
constructor(nodes = [], edges = null) {
if (edges) {
nodes.forEach(label => this[label] = { from: {}, to: {} })
edges.forEach(edge => this.connect(...edge))
} else nodes.forEach(e => {
if (!Array.isArray(e)) {
this[e] = { from: {}, to: {} }
} else {
let [from, to, cost] = e
cost = cost || 1
this.connect(from, to, cost, true)
}
})
}
connect(from, to, cost = 1, isInsert = false) {
if (!isInsert && (!this[from] || !this[to])) throw new Error('missing node')
if (!this[from]) { this[from] = { from: {}, to: {} } }
if (!this[to]) { this[to] = { from: {}, to: {} } }
this[from].to[to] = cost
this[to].from[from] = cost
}
}
new Graph(['b', 'c', 'd', 'f', 'g', 'h', 'k'], [['b', 'c', 1], ['b', 'f', 2], ['c', 'f', 5], ['f', 'k', 3], ['g', 'h']])
// new Graph([['b', 'c', 1], ['b', 'f', 2], ['c', 'f', 5], ['f', 'k', 3], ['g', 'h'], 'd'])
/*
Graph {
b: { from: {}, to: { c: 1, f: 2 } },
c: { from: { b: 1 }, to: { f: 5 } },
d: { from: {}, to: {} },
f: { from: { b: 2, c: 5 }, to: { k: 3 } },
g: { from: {}, to: { h: 1 } },
h: { from: { g: 1 }, to: {} },
k: { from: { f: 3 }, to: {} } }
*/頂点のラベルをプロパティ名にします。プロパティを持っていない場合は、{ from: {}, to: {} }を持たせます。
このfromとtoにはラベル: コストのプロパティが格納され、行きと帰りの経路をコストを見て選択して辿ることができるようになっています。
コンストラクタは引数が二つある場合と一つのみの場合で分岐させます。
頂点のリストがある場合は、辺は既に存在する頂点同士を結ばなければなりません。
そのためconnect関数を定義し、頂点が存在していない場合はエラーを投げるようにしています。
辺のリストのみ渡された場合は、最初の一回目の参照時はプロパティが定義されていないため定義します。
console.logなどで中身を見たときの結果を気にしないのであれば、辺のリストをインスタンス生成時に保持しておくと色々楽かもしれません。
ある頂点から別の頂点までの経路を返す
paths関数を実装せよ。
class Graph {
/* 省略 */
paths(from, to, already = new Set()) {
const target = this[from].to
const keys = Object.keys(target)
if (keys.length === 0 || already.has(from)) return []
if (target[to]) return [[[from, to, target[to]]]]
return keys.flatMap(key => this.paths(key, to, new Set([...already, from])).map(e => [[from, key, target[key]], ...e]))
}
}
new Graph([[1, 2], [2, 3], [1, 3], [3, 4], [4, 2], [5, 6]]).paths('1', '4')
/*
[ [ [ '1', '2', 1 ], [ '2', '3', 1 ], [ '3', '4', 1 ] ],
[ [ '1', '3', 1 ], [ '3', '4', 1 ] ] ]
*/何も見つからなかった場合は空の配列を返します。
また、既に辿った頂点のラベルをalreadyに格納して毎回引数として渡します。
alreadyにfromが含まれているなら辿ったことがあるため空の配列を返します。これで閉路による無限ループを防げます。
this[from].toには今見ている頂点と、行先の別の頂点間の経路が格納されています。
つまり、このオブジェクトが目的の頂点のラベルtoをプロパティ名とするプロパティを持つなら、[[from, to, cost]]を返してもよいことになります。
含まれていない場合、this[from].toが持つラベル全てにpaths関数を適用しましょう。
fromには、移動先の頂点のラベルを渡します。toは変わらないのでそのまま渡します。
alreadyには、alreadyとfromを結合して渡します。
経路が見つからなかった場合は空の配列が返ってきているため、最後にフィルタして返します。
閉路（ある頂点から始まってある頂点へ帰るまでの経路）を見つける
cycle関数を実装せよ。
class Graph {
/* 省略 */
cycle(target) {
return this.paths(target, target)
}
}
new Graph([[1, 2], [2, 3], [1, 3], [3, 4], [4, 2], [5, 6]]).cycle('2')
// [ [ [ '2', '3', 1 ], [ '3', '4', 1 ], [ '4', '2', 1 ] ] ]paths関数のfromとtoを同じ頂点のラベルにして呼び出します。
グラフからスパニングツリーを全て探す
spanningTrees関数を実装せよ。
import { combinations } from './array' // 問26で実装した組み合わせ関数
class Graph {
/* 省略 */
get edges() {
return Object.keys(this).flatMap(from => {
const target = this[from].to
const edges = []
for (const to in target) {
edges.push([from, to, target[to]])
}
return edges
})
}
get spanningTrees() {
const keys = Object.keys(this)
const { edges } = this
if (!keys.length || edges.length < keys.length - 1) return []
return combinations(edges, keys.length - 1)
.filter(x => {
for (const key of keys) {
let find = false
for (const [from, to,] of x) if (key === from || key === to) {
find = true
break
}
if (!find) return false
}
return true
})
.map(e => new Graph(e))
}
const trees = new Graph([['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'a'], ['a', 'c'], ['b', 'd']]).spanningTrees
trees[0]
/*
Graph {
a: { from: {}, to: { b: 1, c: 1 } },
b: { from: { a: 1 }, to: { d: 1 } },
c: { from: { a: 1 }, to: {} },
d: { from: { b: 1 }, to: {} } }
*/
trees.length // 16全ての辺のリストを返すedgesを定義しておきます。
辺は各プロパティのtoとプロパティ名を結合すれば得られます。
スパニングツリーのリストは、グラフの全ての辺の中から頂点の数 - 1本を選んだ組み合わせから、全ての頂点を含む組み合わせのみを抽出すれば得られます。
combinations関数で組み合わせを得た後に、全ての頂点を含まない辺のリストをフィルタで除外しています。
孤立している頂点があったり、頂点が分断されていたりすれば全域木は無いので、それを判別できれば無駄な処理をせずに済むかもしれません。
最小スパニングツリー(MST)をPrim法で全て探す
prim関数を実装せよ。
import { uniqWith, isEqual } from 'lodash'
class Graph {
/* 省略 */
copy(edge = null) {
const graph = new Graph(Object.keys(this), this.edges)
if (edge) { graph.connect(...edge, true) }
return graph
}
get prim() {
const keys = Object.keys(this)
const { edges } = this
if (!keys.length || edges.length < keys.length - 1) return []
/**
* 次の頂点へ行くために最小コストの辺を探す
* @param {Graph} graph 調べるグラフ
* @returns {[string, string, number][]} 最小コストの辺のリスト
*/
const min = (graph) => {
const labels = Object.keys(graph)
const result = []
labels.forEach(e => {
const { from, to } = this[e]
const fromEdges = Object.keys(from).filter(k => !labels.includes(k)).map(k => [k, e, from[k]])
if (fromEdges.length) { result.push(...fromEdges) }
const toEdges = Object.keys(to).filter(k => !labels.includes(k)).map(k => [e, k, to[k]])
if (toEdges.length) { result.push(...toEdges) }
})
return result.sort(([,,a], [,,b]) => a - b).filter(([,,cost], _, self) => cost <= self[0][2])
}
/**
* MSTを探す
* @param {Graph} graph 調べるグラフ
* @returns {Graph[]} MSTのリスト
*/
const search = (graph) => {
const edges = min(graph)
return edges.length ? edges.flatMap(e => search(graph.copy(e))) : [graph]
}
// 探した後、全ての頂点が含まれているかどうか調べる
const result = search(new Graph([keys[0]]))
.filter(x => {
for (const key of keys) if (!x[key]) return false
return true
})
return uniqWith(result, isEqual)
}
}
new Graph([[1, 2, 12], [1, 3, 34], [1, 5, 78], [2, 4, 55], [2, 5, 32], [3, 4, 61], [3, 5, 44], [4, 5, 93]]).prim
/*
[ Graph {
'1': { from: {}, to: { '2': 12, '3': 34 } },
'2': { from: { '1': 12 }, to: { '4': 55, '5': 32 } },
'3': { from: { '1': 34 }, to: {} },
'4': { from: { '2': 55 }, to: {} },
'5': { from: { '2': 32 }, to: {} } } ]
*/えいニャ！えいニャ！渚の小悪魔☆
グラフを複製するcopy関数を作っておきます。複製に辺も追加したいので、引数で渡せるようにしておきます。
Prim法は以下のようにして最小スパニングツリー(以下MST)を探し出します。
- グラフの全ての頂点から任意の1点を選び、グラフGを生成する
- Gから最小コストで辿ることができる、まだ追加していない頂点をGに追加する
- 全ての頂点を追加するまで2を繰り返す
最小のコストを持つ辺は、持っている頂点のfromとtoから探し出します。
この辺が2本以上見つかった場合、MSTを1個探すだけなら任意に選択してもよいのですが、今回は全て見つけ出したいためループします。
このループによって重複するMSTが何個か生成されてしまいます。
頂点が分断されている場合、走査を行った後に全ての頂点が含まれているとは限らないため、グラフが全ての頂点を持っているかどうかを確かめておきます。
無駄な計算を抑えるためには最初に判別しておいたほうがいいかもしれません。
最後に、重複するMSTが格納されていることがあるため、lodashのuniqWithとisEqualを組み合わせて重複排除します。
なお、全ての辺のコストが等しいなら、問83のspanningTreesと同じ実行結果となります。
二つのグラフがグラフ同型であるかを返す
isomorphism関数を実装せよ。
折角なので、グラフ同型だった場合は頂点の対応表を返すと、結果が正しいか検証しやすくなって良いと思います。
function* permutations(list, n = list.length) {
if (n <= 1) yield list.slice()
else for (let i = 0; i < n; i++) {
yield* permutations(list, n - 1)
const j = n % 2 ? 0 : i;
[list[n - 1], list[j]] = [list[j], list[n - 1]]
}
}
class Graph {
/* 省略 */
isomorphism(graph) {
const xKeys = Object.keys(this)
const { edges: xEdges } = this
const yKeys = Object.keys(graph)
const yEdges = graph.edges.map(([from, to,]) => [from, to])
if (xKeys.length !== yKeys.length) return null
if (xEdges.length !== yEdges.length) return null
for (const perm of permutations(yKeys)) {
const table = {}
perm.forEach((e, i) => table[xKeys[i]] = e)
const edges = xEdges.map(([from, to,]) => [table[from], table[to]])
const result = yEdges.every(x => edges.some(y => isEqual(x, y)))
if (result) return table
}
return null
}
}
const graph1 = new Graph([1, 2, 3, 4, 5, 6, 7, 8], [[1, 5], [1, 6], [1, 7], [2, 5], [2, 6], [2, 8], [3, 5], [3, 7], [3, 8], [4, 6], [4, 7], [4, 8]])
const graph2 = new Graph([1, 2, 3, 4, 5, 6, 7, 8], [[1, 2], [1, 4], [1, 5], [6, 2], [6, 5], [6, 7], [8, 4], [8, 5], [8, 7], [3, 2], [3, 4], [3, 7]])
graph1.isomorphism(graph2)
/*
{ '1': '1',
'2': '3',
'3': '6',
'4': '8',
'5': '2',
'6': '4',
'7': '5',
'8': '7' }
*/配列から全ての要素を選んで並べ替える順列を求めるpermutations関数をあらかじめ定義しておきます。
総当たりでグラフ同型かを判別するには、頂点を並べ替えたリストが必要になるからです。
頂点の数や辺の数が異なる場合、グラフ同型になり得ないのでnullを返します。
頂点の数と辺の数が一致するなら、渡したグラフの頂点を並び替えたリストを生成します。
その後、このパターン一つ一つを用いて頂点と頂点のラベルの対応表を作成し、グラフが持つ辺のリストの頂点のラベルを変更します。
渡したグラフの辺のリストがこの辺のリストの全要素を含むならグラフ同型であるため、ラベルの対応表を返します。
見つからなかった場合はnullを返します。
このisomorphism関数のオーダーは頂点数をnとするとO(n!)です。
これは巡回セールスマン問題の全探索による解法と同程度遅いアルゴリズムであることを意味しています。
グラフ同型問題は準多項式時間で解けるらしいので、そのアルゴリズムで実装できればかなり高速化することができます。
Welsh-Powellの頂点彩色アルゴリズムを使用して、隣接ノードが異なる色になるように彩色する
paint関数を実装せよ。
頂点を次数が小さくなる順序でソートした後、貪欲彩色を行います。
class Graph {
/* 省略 */
degree(label) {
const { from, to } = this[label]
return Object.keys(from).length + Object.keys(to).length
}
paint() {
const result = {}
const keys = Object.keys(this).sort((a, b) => this.degree(a) - this.degree(b))
keys.forEach(key => {
const { from, to } = this[key]
let color = 1
const neighbors = [...Object.keys(from), ...Object.keys(to)]
.filter((e, i, self) => self.indexOf(e) === i)
.map(e => result[e])
while (neighbors.includes(color)) { color++ }
result[key] = color
})
return result
}
}
const graph = new Graph(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], [['a', 'b'], ['a', 'e'], ['a', 'f'], ['b', 'c'], ['b', 'g'], ['c', 'd'], ['c', 'h'], ['d', 'e'], ['d', 'i'], ['e', 'j'], ['f', 'h'], ['f', 'i'], ['g', 'i'], ['g', 'j'], ['h', 'j']])
graph.paint()
// { a: 1, b: 2, c: 1, d: 2, e: 3, f: 2, g: 1, h: 3, i: 3, j: 2 }次数はfromとtoが持つプロパティの数と等しいことになります。
グラフが持つ頂点のラベルを次数の昇順でソートします。
着色する際は近隣の頂点と同じ色になってはいけないので、近隣の着色済みの頂点の色と同じだったらインクリメントすることでズラします。
深さを優先してグラフを探索する
depthFirst関数を実装せよ。
class Graph {
/* 省略 */
depthFirst(start) {
const visited = []
const f = label => {
visited.push(label)
const { from, to } = this[label]
const keysForEach = obj => Object.keys(obj).forEach(key => {
if (!visited.includes(key)) { f(key) }
})
keysForEach(to)
keysForEach(from)
}
f(start)
return visited
}
}
const graph = new Graph([1, 2, 3, 4, 5, 6, 7], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4], [6, 7]])
console.log(graph.depthFirst('1'))
// [ '1', '2', '3', '4', '5' ]探索し終わった頂点については配列に格納します。
指定された頂点についてto、fromの順に繋がっている未探索の頂点を探索していきます。
グラフを連結している頂点で分離する
connectedComponents関数を実装せよ。
class Graph {
/* 省略 */
get connectedComponents() {
const keys = Object.keys(this)
const set = new Set()
const result = []
keys.forEach(key => {
if (set.has(key)) return
const connected = this.depthFirst(key)
connected.forEach(e => set.add(e))
result.push(connected)
})
return result
}
}
const graph = new Graph([1, 2, 3, 4, 5, 6, 7], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4], [6, 7]])
console.log(graph.connectedComponents)
// [ [ '1', '2', '3', '4', '5' ], [ '6', '7' ] ]depthFirst関数を実装したことで、ある頂点から繋がっている頂点を辿ることができるようになりました。
connectedComponents関数は辿ったことがない頂点に対してdepthFirst関数を適用することで、グラフの頂点を繋がっているもの同士で分離します。
グラフが2部グラフかどうかを返す
bipartite関数を実装せよ。
2部グラフだった場合、頂点を二つのグループに分けてみましょう。
class Graph {
/* 省略 */
get bipartite() {
const keys = Object.keys(this)
if (keys.length < 2) return null
const colors = {}
const paint = (key, color) => {
colors[key] = color
const { from, to } = this[key]
for (const k of Object.keys(to)) {
if (colors[k] === color) return false
if (!colors[k] && !paint(k, -color)) return false
}
for (const k of Object.keys(from)) {
if (colors[k] === color) return false
if (!colors[k] && !paint(k, -color)) return false
}
return true
}
const key = keys[0]
if (!paint(key, 1)) return null
const painted = Object.keys(colors)
if (keys.length !== painted.length) return null
const result = [[], []]
painted.forEach(k => result[colors[k] === 1 ? 0 : 1].push(k))
return result
}
}
const graph1 = new Graph([1, 2, 3, 4, 5], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4]])
const graph2 = new Graph([1, 2, 3, 4, 5], [[1, 2], [2, 3], [1, 4], [3, 4], [5, 2], [5, 4], [1, 3]])
graph1.bipartite // [ [ '1', '3', '5' ], [ '2', '4' ] ]
graph2.bipartite // null2部グラフは2色で彩色することが可能です。
つまり、各頂点を2色を切り替えながら塗り、隣接する頂点の色と被らなければ2部グラフだと言えます。
色が被っていたり、頂点同士が繋がっていない場合はnullを返すようにします。
解答例ではpaint関数を呼ぶと頂点と色の対応表が生成されるので、それを基に結果の配列を生成しています。
N-クイーン問題を解く
queens関数を実装せよ。
function* queens(size = 8) {
const board = []
for (let i = 0; i < size; i++) {
board.push(Array(size).fill(0))
}
/**
* 盤面にクイーンを置き、配置できない場所を塞ぐ
* 取り除く場合は逆の操作を行う
* @param {number[][]} board 盤面
* @param {number} row 行
* @param {number} column 列
* @param {boolean} isRemove trueならクイーンを取り除く
*/
const block = (row, column, isRemove = false) => {
const n = isRemove ? -1 : 1
// 横と縦
for (let i = 0; i < size; i++) {
board[row][i] += n
board[i][column] += n
}
// 右斜め下
if (row > column) {
for (let i = 0; i < size - (row - column); i++) {
board[i + row - column][i] += n
}
} else {
for (let i = 0; i < size - (column - row); i++) {
board[i][i + column - row] += n
}
}
// 左斜め下
const condition = row + column < size
const start = condition ? 0 : row + column - size + 1
const max = condition ? row + column + 1 : size
for (let i = start; i < max; i++) {
board[row + column - i][i] += n
}
}
/**
* クイーンを配置・検査していき、最後の行まで達したら結果を格納する
* @param {number} row 行
* @param {number[]} queens 現在までのクイーンの位置
* @param {number[][]} board 盤面
* @returns {IterableIterator<number[]>} 確定したクイーンの位置
*/
function* generate(row = 0, queens = []) {
if (row === size) return yield queens.map(e => e + 1)
for (let column = 0; column < size; column++) if (board[row][column] === 0) {
queens[row] = column
block(row, column)
yield* generate(row + 1, queens, board)
block(row, column, true)
}
}
yield* generate()
}
const result = [...queen(8)]
result.length // 92
result[0] // [ 1, 5, 8, 6, 3, 7, 2, 4 ] などまず、クイーンが移動可能なマスに駒を置けないようにしたり逆に置けるようにするblock関数を定義します。
バックトラック法で解を探し出していきます。
generate関数は、最後の行まで辿り着いたなら盤面のクイーンの位置をyieldします。
それ以外のときはその行の各マスにクイーンが置けるかどうかを検査し、置ける場合はクイーンを設置してから次の行を検査し、最後にクイーンを取り除きます。
- データを変更する
- 次を試す（一手進める）
- データを元に戻す（一手戻す）
を繰り返すことで、全てのパターンを高速に網羅する手法がバックトラック法です。
ナイト・ツアー問題を解く
knightsTour関数を実装せよ。
m * nのチェス盤の上を指定したマスに置かれたナイトが全てのマスを巡回し、その辿った経路を配列として返します。
余裕があれば、最初の座標にナイトが戻ってくる結果のみを収集できるようにもしてみましょう。
function* knightsTour([x, y] = [1, 1], [width, height] = [8, 8], {isClosed, isWarnsdorf} = {isClosed: false, isWarnsdorf: true}) {
if (width < 1 || height < 1) throw new Error('不正な盤面のサイズです')
if (!(x >= 1 && y >= 1 && x <= width && y <= height)) throw new Error('ナイトの初期位置が盤外です')
x -= 1
y -= 1
const board = []
for (let i = 0; i < height + 4; i++) {
board.push(Array(width + 4).fill(1))
}
/**
* 次のナイトの行先を列挙する
* @param {number} i y座標
* @param {number} j x座標
*/
const destinations = (i, j) => [
[i - 2, j - 1], [i - 2, j + 1], [i - 1, j - 2], [i - 1, j + 2],
[i + 1, j - 2], [i + 1, j + 2], [i + 2, j - 1], [i + 2, j + 1]
]
/**
* 次のナイトの行先を決定する
* @param {number} i y座標
* @param {number} j x座標
*/
const next = (i, j) => destinations(i, j)
.filter(([y, x]) => x >= 0 && x < width && y >= 0 && y < height && board[y][x] >= 0)
/** 現在までにナイトが辿った経路 */
const route = []
/**
* ナイトを巡歴させる
* @param {number} i y座標
* @param {number} j x座標
* @param {number} count 何巡目か
* @returns {IterableIterator<number[][]>} ナイトの辿った経路
*/
function* generate(i = y, j = x, count = 0) {
route[count++] = [j, i]
if (!isClosed && count === width * height) {
return yield route.map(([x, y]) => [x + 1, y + 1])
}
board[i][j] = -1
const dests = destinations(i, j)
let nextRoutes = next(i, j)
if (isWarnsdorf) {
nextRoutes = nextRoutes.map(([y, x]) => [[y, x], next(y, x).length])
.sort(([,a], [,b]) => a - b)
.map(([e,]) => e)
}
if (isClosed && count === width * height && nextRoutes.length === 0) {
const found = dests.some(([i, j]) => i === y && j === x)
if (found) yield route.map(([x, y]) => [x + 1, y + 1])
}
else for (const [nextY, nextX] of nextRoutes) {
yield* generate(nextY, nextX, count)
}
board[i][j] = 1
}
yield* generate()
}
knightsTour([1, 1], [8, 8]).next().value
/*
[ [ 1, 1 ], [ 3, 2 ], [ 5, 1 ], [ 7, 2 ], [ 8, 4 ], [ 7, 6 ], [ 8, 8 ], [ 6, 7 ], [ 8, 6 ], [ 7, 8 ], [ 5, 7 ], [ 3, 8 ], [ 1, 7 ], [ 2, 5 ], [ 1, 3 ], [ 2, 1 ], [ 4, 2 ], [ 6, 1 ], [ 8, 2 ], [ 6, 3 ], [ 7, 1 ], [ 8, 3 ], [ 7, 5 ], [ 8, 7 ], [ 6, 8 ], [ 4, 7 ], [ 2, 8 ], [ 1, 6 ], [ 2, 4 ], [ 1, 2 ], [ 3, 1 ], [ 2, 3 ], [ 1, 5 ], [ 3, 6 ], [ 4, 8 ], [ 2, 7 ], [ 3, 5 ], [ 1, 4 ], [ 2, 2 ], [ 4, 1 ], [ 3, 3 ], [ 5, 2 ], [ 4, 4 ], [ 5, 6 ], [ 6, 4 ], [ 4, 3 ], [ 5, 5 ], [ 3, 4 ], [ 2, 6 ], [ 1, 8 ], [ 3, 7 ], [ 4, 5 ], [ 5, 3 ], [ 7, 4 ], [ 6, 2 ], [ 8, 1 ], [ 7, 3 ], [ 5, 4 ], [ 4, 6 ], [ 6, 5 ], [ 7, 7 ], [ 8, 5 ], [ 6, 6 ], [ 5, 8 ] ]
など
*/ナイトの駒の動きを再現したdestinations関数と、盤内にあるマス（次の行先）のみを抽出するnext関数を定義しておきます。
バックトラック法で結果を求めます。
基本的には現在ナイトがいるマスの座標を格納し、最後のマスまで辿れたなら辿ったルートをyieldし、そうでないなら次の行先にナイトを移動させてみます。
周遊ルートを求める場合は、最初のマスに戻ってこれたかどうかをチェックする必要があります。
最後のマスに辿り着いたとき、次の行先に最初のマスがあるかどうかをチェックし、あれば辿ったルートをyieldします。
なお、このコードだと実行時間が長すぎるため8 * 8の周遊ルートを求められません。
Warnsdorfの法則によって、最初の巡歴ルートを発見するのを高速化することができます。
引数でオプションとしてisWarnsdorfを渡せるようにし、trueのときだけ次のマスからのナイトの移動先が少ない順にソートするようにします。
コッホ予想を解く
vonKoch関数を実装せよ。
ヘルゲ・フォン・コッホの予想によると、n個の頂点とn - 1個の辺があるグラフ（木構造）の場合、Graceful Labelingができます。
グラフの各頂点が固有のラベル（数値）を持ち、各辺が繋がる頂点のラベルの差の絶対値の固有のラベルを持っているパターンを探します。
結果は変換後の各頂点のラベルや、引数として与えられた各辺に付与されたラベルなどを返しましょう。
import { permutations } from './array'
function* vonKoch(edges) {
const numbers = [...Array(edges.length + 1)].map((_, i) => i + 1)
for (const nodes of permutations(numbers)) {
const costs = edges.map(([from, to]) => Math.abs(nodes[from - 1] - nodes[to - 1]))
const isFound = costs.filter((e, i, self) => self.indexOf(e) === i).length === edges.length
if (isFound) yield [nodes, costs]
}
}
[...vonKoch([[4, 1], [1, 2], [1, 7], [2, 3], [2, 5], [5, 6]])]
// [ [ 7, 3, 6, 1, 5, 4, 2 ], [ 6, 4, 5, 3, 2, 1 ] ] などn個からn個を選んで得られる順列から、各辺のラベルがユニークになるものを探します。
各辺のラベルは頂点のラベルの差の絶対値なので、edges.map(([from, to]) => Math.abs(nodes[from - 1] - nodes[to - 1]))となります。
あとは各辺のラベルが重複するものを含まなければGraceful Labelingが成立します。
このコードだと、小さい木の場合しか解を求められません。
四則演算と等号と括弧を使って与えられた数列内で等式が成り立つものを見つける
puzzle関数を実装せよ。
配列の順番は変更しないものとします。
function* puzzle(numbers) {
const add = (a, b) => a + b
const sub = (a, b) => a - b
const mul = (a, b) => a * b
const div = (a, b) => a / b
/**
* 配列を指定位置で分ける
* @param {number[]} list 配列
* @param {number} n 添え字
*/
const splitAt = (list, n) => {
list = [...list]
return [list, list.splice(n)]
}
/**
* 四則演算のパターンを生成する
* @param {number[]} numbers 数列
* @returns {IterableIterator<[string, number, string]>} [数式, 数値, 演算子]
*/
function* generate(numbers) {
if (numbers.length === 1) return yield [numbers[0] + '', numbers[0], '_']
for (let i = 1; i < numbers.length; i++) {
const [left, right] = splitAt(numbers, i).map(e => [...generate(e)])
const operators = [['+', add], ['-', sub], ['*', mul], ['/', div]]
for (const [sl, vl, opsl] of left) for (const [sr, vr, opsr] of right) for (const [ops, op] of operators) {
if ((ops === '/' && vr === 0) ||
(ops === '+' && (opsr === '+' || opsr === '-')) ||
(ops === '*' && (opsr === '*' || opsr === '/'))) continue
const expression = `${
(opsl !== '_' &&
(ops === '*' || ops === '/') &&
(opsl === '+' || opsl === '-')) ? `(${sl})` : sl
} ${ ops } ${
(opsr !== '_' &&
((ops === '-' && opsr !== '*' && opsr !== '/')
|| (ops === '*' && (opsr === '+' || opsr === '-'))
|| ops === '/')) ? `(${sr})` : sr
}`
yield [expression, op(vl, vr), ops]
}
}
}
for (let i = 1; i < numbers.length; i++) {
const [left, right] = splitAt(numbers, i).map(e => [...generate(e)])
for (const [sl, vl,] of left) for (const [sr, vr,] of right) {
if (vl === vr) yield `${sl} = ${sr}`
}
}
}
[...puzzle([2, 3, 5, 7, 11])]
/*
[ '2 = 3 - (5 + 7 - 11)',
'2 = 3 - 5 - (7 - 11)',
'2 = 3 - (5 + 7) + 11',
'2 = 3 - 5 - 7 + 11',
'2 = (3 * 5 + 7) / 11',
'2 * (3 - 5) = 7 - 11',
'2 - (3 - (5 + 7)) = 11',
'2 - (3 - 5 - 7) = 11',
'2 - (3 - 5) + 7 = 11',
'2 - 3 + 5 + 7 = 11' ]
*/四則演算ができるように各演算子を関数化します。
また、配列を指定位置で分けられるsplitAt関数を定義します。
配列を各位置で左辺と右辺に切り分け、左辺と右辺で四則演算の全てのパターンを生成し、両辺が等しいかどうかを判別すれば解が求められそうです。
パターン生成用のgenerate関数は、[数式, 数値, 演算子]を返すようにします。
数値のみ返ってくる場合の演算子は_にしておきます。
配列を各位置で切り分けられるように1 <= i && i < numbers.lengthの範囲でforループし、最初にsplitAtで分けて各要素にgenerateを適用します。
次に全ての四則演算のパターンを生成することを考えます。
まず、各演算子を後から適用できるように、operatorsを宣言・初期化しておきます。
ループは左辺の各パターン、右辺の各パターン、各演算子で三重ループになります。
分割代入でそれぞれ[数式(s), 数値(v), 適用した演算子(ops)]に分けておきます。
弾くパターンについて考えます。
演算子が/のとき、右辺値は0以外でなければなりません。
また、同様のパターンが何個も生成されないよう、鏡合わせになるものは除外します。
数式の生成部ですが、適用する演算子が*か/で左辺の演算子が+か-のとき、左辺を小括弧で括る必要があります。
右辺は、適用する演算子が-か*で右辺の演算子が+か-のとき、もしくは適用する演算子が/で右辺が数式のとき、右辺を小括弧で括る必要があります。
最後に、[生成した数式, 演算子を適用した結果, 演算子]をyieldします。
k-正則単純グラフを生成する
regular関数を実装せよ。
k-正則グラフは全ての頂点の次数がkのグラフです。つまり、各頂点はk本の辺を持っています。
単純グラフは自己ループが無く、頂点間に複数の辺も無いグラフです。
余裕があれば、結果にグラフ同型なものを含まないようにします。
import { isEqual } from 'lodash'
function* regular(n, k) {
// n * kが2で割り切れないと辺が余るのでk-正則になり得ない
if (n * k % 2 === 1 || n <= k || n < 0 || k < 0) return
/**
* k-正則グラフを探す
* @param {Graph} graph 操作中のグラフ
* @param {number} target 頂点のラベル
* @param {number[]} rest 残りの頂点のラベル
* @returns {IterableIterator<Graph>} k-正則グラフ
*/
function* generate(graph, rest) {
const [target, ...rs] = rest
const degree = graph.degree(target)
const done = degree === k
if (!rs.length) {
if (done) yield graph
return
}
if (done) { return yield* generate(graph, rs) }
if (k - degree > rs.length) return
const combi = combinations(rs, k - degree)
.map(x => [x, x.map(y => graph.degree(y))])
.filter(([,x], i, self) => self.findIndex(([,y]) => isEqual(x, y)) === i)
.map(([e,]) => e)
for (const selections of combi) {
const g = graph.copy()
selections.forEach(selection => g.connect(target, selection))
yield* generate(g, rs)
}
}
const labels = [...Array(n)].map((_, i) => i + 1)
const graph = new Graph(labels)
for (let i = 2; i < k + 2; i++) { graph.connect(1, i) }
const [, ...rest] = labels
yield* generate(graph, rest)
}
[...regular(6, 3)]
/*
[ Graph {
'1': { from: {}, to: { '2': 1, '3': 1, '4': 1 } },
'2': { from: { '1': 1 }, to: { '3': 1, '5': 1 } },
'3': { from: { '1': 1, '2': 1 }, to: { '6': 1 } },
'4': { from: { '1': 1 }, to: { '5': 1, '6': 1 } },
'5': { from: { '2': 1, '4': 1 }, to: { '6': 1 } },
'6': { from: { '3': 1, '4': 1, '5': 1 }, to: {} } },
Graph {
'1': { from: {}, to: { '2': 1, '3': 1, '4': 1 } },
'2': { from: { '1': 1 }, to: { '5': 1, '6': 1 } },
'3': { from: { '1': 1 }, to: { '4': 1, '5': 1 } },
'4': { from: { '1': 1, '3': 1 }, to: { '6': 1 } },
'5': { from: { '2': 1, '3': 1 }, to: { '6': 1 } },
'6': { from: { '2': 1, '4': 1, '5': 1 }, to: {} } } ]
*/辺が余ったり、頂点数が次数以下だった場合は解が無いのでreturnします。
グラフを生成し、あらかじめ1の頂点に指定した次数分だけ他の頂点を繋げておきます。
k-正則グラフを探して生成するgenerate関数を考えてみます。
引数は操作中のグラフと残りの頂点のラベルにします。
残りの頂点のラベルを[対象とする頂点, 残りの頂点]として分割します。
対象とする頂点の現在の次数を求め、regularの引数として与えられた次数kと等しいかどうかも判別します。
各頂点の次数は前に定義したGraph.degreeを使って求めます。
ここで残りの頂点が無い場合は終端なので、次数がkと等しければyieldし、その後はreturnします。
終端でないとき、次数がkと等しければ再帰します。
また、kと次数の差は残りの頂点の数以下でなければ組み合わせが求められないため、超えている場合はreturnします。
次の手順で頂点同士を辺で繋いでいきます。
- 残りの頂点から
kと現在の次数の差の個数だけ頂点を選ぶ - 選んだ頂点のリストをそれぞれ現在の次数に変換したリストとのペアに変換する
- 頂点のリストを次数の重複が無いようにフィルタする
- 頂点のリストのみに戻す
- 組み合わせ分だけループする
- グラフをコピーする
- 対象の頂点と頂点のリストにある頂点間を辺で繋ぐ
- このグラフと残りの頂点のリストを渡して再帰する
ただ、このコードだとフィルタが完璧でないようで、結果にグラフ同型なグラフを含むことがあります。
数字を英単語に変換する
fullWords関数を実装せよ。
0以上の整数のみ引数として渡されます。
const numberNames = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
const fullWords = number => [...(number + '')].map(e => numberNames[e]).join('-')
fullWords(175) // one-seven-five添え字と数字の英単語を一致させるようにして配列を定義します。
fullWords関数では、数値を受け取ったら文字列に変換し、各桁の数字を添え字にして先ほどの配列の要素を参照するようにします。
最後にjoin('-')をすれば要素同士が-で繋がって文字列になります。
文字列がAdaの識別子かどうかを返す
identifier関数を実装せよ。
プログラミング言語Adaの識別子はBNFで次のように表されます。
identifier ::= letter { [ underscore ] letter | digit }
letter ::= A | ... | Z | a | ... | z
digit ::= 0 | ... | 9
underscore ::= _
const identifier = str => /^[a-zA-Z](_?[a-zA-Z0-9])*$/.test(str)
identifier('Time_Of_Day') // true
identifier('2nd_turn') // false
identifier('General__Alarm') // false正規表現を使うと簡単に解けます。
letterが必ず先頭に来るので^[a-zA-Z]としましょう。
その後ろに0個以上のアンダースコア（省略可能）と英数字が末尾まで連続するので(_?[a-zA-Z0-9])*$となります。
クロスワードパズルを解く
crossword関数を実装せよ。
以下のように単語（キー）とクロスワードパズルが与えられたとき、マス目（ピリオド）を全て埋めたものを出力します。
解答が無い場合はnullを返すようにします。
LINUX
PROLOG
PERL
ONLINE
GNU
XML
NFS
SQL
EMACS
WEB
MAC
...... .
. . . .
. ..... .
. . . ...
. ... .
...
import fs from 'fs'
import { cloneDeep, findIndex } from 'lodash'
import { lfsort } from './array'
const crossword = file => {
const [words, puzzle] = file.split('\n\n').filter(e => e).map(e => e.split('\n').filter(e => e))
lfsort(words)
const lines = []
for (let i = 0; i < puzzle.length; i++) {
const row = puzzle[i]
for (let j = 0; j < row.length; j++) {
const char = row[j]
if (char !== '.') continue
// 横に繋がっているマスを探す
if (row[j - 1] !== '.' && row[j + 1] === '.') {
let count = 0
for (; row[j + count] === '.'; count++) {}
lines.push({ direction: 0, x: j, y: i, count })
}
// 縦に繋がっているマスを探す
if ((!puzzle[i - 1] || puzzle[i - 1][j] !== '.') && (puzzle[i + 1] && puzzle[i + 1][j] === '.')) {
let count = 0
for (; puzzle[i + count] && puzzle[i + count][j] === '.'; count++) {}
lines.push({ direction: 1, x: j, y: i, count })
}
}
}
if (words.length !== lines.length) return null
/**
* クロスワードパズルを解く
* @param {string[]} restWords 残りの単語
* @param {{ direction: number, x: number, y: number, count: number }[]} restLines 残りのマス
* @param {string[][]} result 結果が格納される
* @return {string[][]} 結果
*/
const solve = (restWords = words, restLines = lines, result = [...Array(puzzle.length)].map(() => Array(puzzle[0].length).fill(' '))) => {
if (!restWords.length) return result
const [w, ...ws] = restWords
let index = -1
outer: while ((index = findIndex(restLines, ({ count }) => w.length === count, index + 1)) !== -1) {
const { direction, x, y, count } = restLines[index]
const board = cloneDeep(result)
if (direction === 0) for (let i = 0; i < count; i++) {
if (board[y][x + i] !== ' ' && w[i] !== board[y][x + i]) { continue outer }
board[y][x + i] = w[i]
}
else for (let i = 0; i < count; i++) {
if (board[y + i][x] !== ' ' && w[i] !== board[y + i][x]) { continue outer }
board[y + i][x] = w[i]
}
const found = solve(ws, restLines.filter((_, i) => i !== index), board)
if (found) return found
}
return null
}
const result = solve()
return result ? result.map(e => e.join('')).join('\n') : null
}
crossword(fs.readFileSync('./test/crossword/1.dat', 'utf8'))PROLOG E
E N N M
R LINUX A
L I F MAC
N SQL S
WEB
英単語リストとクロスワードパズルの間には\n\nがあるのでそこでsplitし、さらにそれぞれ\nでsplitすると扱いやすい配列になります。
改行の関係で空文字が含まれることがあるので、filter(e => e)しておくと空文字の要素が取り除かれます。
パズルが.で表現されたままだと扱いづらい気がするのでどうにかします。
どこの座標から始まって、行なら右に、列なら下に何マス繋がっているかを表現できるオブジェクトがあれば便利な気がしたため変換します。
型は{ direction: number, x: number, y: number, count: number }とし、directionが0のときは行、1のときは列としました。
.から始まって下か右に.が続く座標があれば、.がいくつ繋がっているかカウントしてオブジェクトに変換して配列（lines）に格納します。
前準備ができたので、このクロスワードパズルを解く戦略を考えてみましょう。
例えば、PERLは英単語リストの中で唯一の4文字で、クロスワードパズルにも4マスの行もしくは列は1本しかないため、当てはめる位置をすぐに固定できます。
文字列の長さの頻度順にソートして順次当てはめるのを試みていけば、手戻りが少なくなって計算量を抑えることができそうです。
英単語のリストは以前定義したlfsort関数でソートしておくことにします。
この英単語のリストの先頭から1つ取り出して、同じ長さのマスに当てはまるかどうか試していけば解くことができそうです。
既にマスに文字が入っている場合は、その文字とマスに入れようとした文字を比較して等しければ続行し、等しくなければ別のマスを検査します。
処理の流れは次のようになります。
- 残りの英単語（もしくは行・列）が無ければ、完成したクロスワードパズルを返す
- 残りの英単語から先頭の英単語を取り出す
- この英単語の長さと等しい行・列を探す
- 探した行・列に対して英単語を当てはめることを試みる
- いずれかの行・列に当てはまれば、再帰して残りの英単語と行列に対しても試し、解答が返ってくればそのまま返す
- 当てはまらなければ、違う行・列に当てはめることを試みる
- どの行・列にも当てはまらなければ
nullを返す
この流れに沿ってsolve関数を実装しました。
結果を格納するresultは、クロスワードパズルを表す二次元配列にし、最終的にjoinで結合して文字列にします。
この方法だとresultをディープコピーしないと想定しない文字が入ることがあるため、LodashのcloneDeepで試行の度にコピーを生成しています。
ラベル付きcontinueは見たことが無い人がいるかもしれません。
これを使うと、ラベルがついた文をbreakやcontinueの対象にすることができます。
solve関数に残りの英単語、残りの行列、現在のパズルを渡して再帰させれば、解答もしくはnullが返ってきます。
解答が返ってきた場合はそれをそのまま返すようにしましょう。
nullの場合は当てはめる行・列が間違っていた（または解答が無い）ということなので、別の行・列に当てはめることを試みます。
Node.js上ではfsでローカルファイルを読み込むことができるため、fs.readFileSyncでファイルの中の文字列をcrossword関数に渡しています。
便利ですが当然フロントエンドでは使えないため、代わりにFile APIを使いましょう。