CodeIQ感謝祭「ドワンゴからの挑戦状」についての解説:dwango エンジニアブロマガ: ドワンゴ研究開発チャンネル(ドワンゴエンジニア)

ドワンゴ技術コミュニケーション室の塩谷( @kwappa / @kwappa@friends.nico )です。

9/16に開催された「学びの秋！エンジニア最先端に触れて学ぶITフェス」というイベントにドワンゴも企業として出展し、私も職務経歴書についての講演を行ってきました。ご清聴いただいた皆様、ありがとうございました！

さて、企業ブースでは「ドワンゴからの挑戦状」と題したプログラミング課題を用意し、正解者には先着順でアスキードワンゴの技術書をプレゼントする企画を実施しました。「ヒントが欲しい」「解き方を教えてください」という要望も多かったので、解法をJavaScriptによるサンプルコードを添えて紹介します。
fdc86074325d0845df1fcb641327b7596e9950bf

fdc86074325d0845df1fcb641327b7596e9950bf

解答と解説

Q1 : 101

力技で解くなら、2525から1までのループを回し、その数と2525および5252の剰余を求め、いずれも0になる最初の数、ということになります。

let a0
for (let i = 2525 ; i > 0 ; i --) {
  if (2525 % i === 0 && 5252 % i === 0) {
    a0 = i
    break
  }
}

最大公約数を求める有名な方法に「ユークリッドの互除法」があり、そちらを使えばより計算量少なく求めることができます。

x <= y , x > 0 , y > 0 の場合、以下のコードで最大公約数が求められます。互いに素な場合は1が返ります。

function gcd(x, y) {

let r

while (y > 0) {

r = x % y

x = y

y = r

}

return x

}

const a1 = gcd(2525, 5252)

Q2 : 2859870693

漸化式なので、設問通りの演算をする関数を再帰的に呼び出せばn項めを求めることができます。ですが、Q3とQ4が同様の数列を利用する問題になっているため、ここで全要素を演算した配列を生成した方が楽でしょう。

2 ^ 32 はこのあとも使うので、ここで定義してしまいましょう。ES2016からは「2 ** 32」と書くこともできます。

const TWO_POW_32 = Math.pow(2, 32)

let arr = [a1]

for (let i = 1 ; i <= 1000 ; i ++) {

arr[i] = (arr[i - 1] * 2525 + 5252) % TWO_POW_32

}

const a2 = arr[1000]

Q3 : [2355222565, 3890716245, 434637493, 1285940997, 3265016661, 5746901]

文字コードをindexとして先ほどの配列から取り出し答えとなる配列にpushしていく、という戦略が考えられます。

文字列を配列に分解するにはスプレッド演算子が使えます。以前は `'dwango'.split('')` という書き方をすることが多かったようです。

const a3 = [...'dwango'].map(v => arr[v.charCodeAt(0)])

Q4 : 2110379477

ソートして取り出すだけの問題です。500番目はちょうど真ん中なので、昇順 / 降順を間違えても解答は変わらないというボーナス問題です。

JavaScriptの場合は単純に `Array#sort` でソートすると文字列として辞書順でソートされてしまうので、比較関数を書いて数値でソートする必要があります。

const sortedArr = arr.sort((a, b) => a - b)

const a4 = sortedArr[500]

問題 : 3322

JavaScriptではreduceというメソッドで畳み込み演算を行うことができます。Q3で作った配列に残りの値を連結した配列を作り、すべての値を合計し、2 ^ 32との剰余を求め、先頭4文字を取り出してみましょう。

const answerArr = a3.concat([a1, a2, a4])

const answer = ((answerArr.reduce((a, x) => a + x))% TWO_POW_32).toString().slice(0, 4)

蛇足

筆者の趣味でRubyによる解答例も掲載しておきます。 Integer#gcd とか Array#sum （2.4から）など便利メソッドがあることをコードレビューで教えてもらいました。

a1 = 2525.gcd(5252)

puts "Q1 : #{a1}"

arr = [a1]

1.upto(1000) { |idx| arr[idx] = (arr[idx - 1] * 2525 + 5252) % 2 ** 32 }

a2 = arr[1000]

puts "Q2 : #{a2}"

a3 = "dwango".each_byte.map { |idx| arr[idx] }

puts "Q3 : #{a3}"

a4 = arr.sort[500]

puts "Q4 : #{a4}"

answer = (a3.concat([a1, a2, a4]).sum % 2 ** 32).to_s[0..3]

puts "Answer : #{answer}"