1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に
...という日本で話題になっているか不明な問題をSwiftで解いてみましたので、合っているかは解りませんがソースを晒しておきます（ネタバレ要注意です）。
５問ありますが、私はおおよそ80分ぐらい掛かったので失格でした＼(^o^)／
問題4が一番時間掛かったと思います。
- Xcode6.3.1 + Playground
問題1
forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。
func sumFor(values: [Int]) -> Int {
var sum = 0
for v in values {
sum += v
}
return sum
}
func sumWhlie(values: [Int]) -> Int {
var sum = 0
var i = 0
while i < values.count {
sum += values[i]
i++
}
return sum
}
func sumRecursive(values: [Int], index: Int) -> Int {
if index == values.count - 1 {
return values[index]
} else {
return values[index] + sumRecursive(values, index + 1)
}
}
let values = [4, 5, 10, 34, 155]
values.reduce(0, combine: +) // 208
sumFor(values) // 208
sumWhlie(values) // 208
sumRecursive(values, 0) // 208
再帰の所はC言語なら配列の先頭ポインタと残りの要素数でも渡していると思いますが、Swiftでそれをやるのも危険かなーと思い、単純なインデックスで処理することにしました。
問題2
交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。
func myCat(a: [Any], b: [Any]) -> [Any] {
var c = [Any]()
for i in 0..<max(a.count, b.count) {
if i < a.count {
c.append(a[i])
}
if i < b.count {
c.append(b[i])
}
}
return c
}
myCat(["a", "b", "c"], [1, 2, 3, 4]) // ["a", 1, "b", 2, "c", 3, 4]
要素数が違った場合の記述が無かったのですが、違ってもクラッシュしない感じにしてあります。
問題3
最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。
func fibonacci() -> [Double] {
var a: [Double] = [0, 1]
while a.count < 100 {
a.append(a[a.count - 2] + a[a.count - 1])
}
return a
}
println(fibonacci().last) // Optional(2.18922995834555e+20)
UInt64でもオーバーフローしてしまうので、仕方なくDoubleで計算しました。
UInt128が欲しい！（キリがない）
問題4
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。
import UIKit
func hoge(values: [Int64]) -> Int64 {
var result: Int64 = 0
var indexes = (0..<values.count).map { [$0] }
while indexes.count > 0 {
let cur = indexes.removeLast()
if cur.count == values.count {
let str: NSString = cur.map { values[$0].description }.reduce("", combine: +)
result = max(result, str.longLongValue)
} else {
for i in 0..<values.count {
if find(cur, i) == nil {
indexes.append(cur + [i])
}
}
}
}
return result
}
hoge([50, 2, 1, 9]) // 95021
hoge([420, 42, 423]) // 42423420
配列インデックスの順列を生成して、数値を文字列として合成し、文字列をInt64へ変換、その最大値を求める感じです。
順列生成方法の書き方に時間が掛かりました。
(Stringにfunc toUInt64() -> UInt64?とかなんで無いのよ...)
追記
答え見たら、もっと単純な方法で良かったみたいです。
import UIKit
func hoge(values: [Int64]) -> Int64 {
let str: NSString = values.sorted { "\($0)\($1)" > "\($1)\($0)" }.map { $0.description }.reduce("", combine: +)
return str.longLongValue
}
hoge([50, 2, 1, 9]) // 95021
hoge([420, 42, 423]) // 42423420
ソート時、単純な文字列で比較するのではなく、結合した結果で比較するのがミソなもよう。
（50と2を比較する際、"50"と"2"ではなく、"502"と"250"で比較する。）
言われてみれば確かにそうなのですが、そこに気がつくかどうかが難所ですね。
問題5
1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる
import UIKit
struct Item {
var text: String
var number: Int
}
var items = [Item(text: "1", number: 1)]
while items.count > 0 {
let cur = items.removeLast()
if cur.number == 9 {
if NSExpression(format: cur.text).expressionValueWithObject(nil, context: nil) as? Int == 100 {
println("\(cur.text)=100")
}
} else {
items += ["", "+", "-"].map {
Item(text: cur.text + "\($0)\(cur.number + 1)", number: cur.number + 1)
}
}
}
1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12-3-4+5-6+7+89=100
12+3-4+5+67+8+9=100
12+3+4+5-6-7+89=100
123-4-5-6-7+8-9=100
123-45-67+89=100
123+4-5+67-89=100
123+45-67+8-9=100
総当たりで計算式（文字列）を作り、NSExpressionで計算させて、その結果が100だったものだけ出力している感じです。
NSExpressionを使っている分、楽した感はあります。
感想
問４・５辺りのような問題は昔からコンテスト系で出題されたり、Cマガジンで連載していたり、最近ではCodeIQさん辺りで頻繁に出題されているかなと思います。
が、私は仕事柄この類のコードを書くことは無いに等しいのでチラ見して終わりなのですが、たまに解いてみるといろんな発見があって面白いです。
是非皆さんも挑戦してみてください。