notebook

都内でWEB系エンジニアやってます。

1時間以内に解けなければプログラマ失格となってしまう5つの問題をscalaで

1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に

今更ながらscalaの勉強を兼ねて実際に解いてみました

intellijscala worksheetを使いましたがとても便利ですね

問題1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

問題2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

最初zipとか使っていけるかと色々試したものの要素数が違う場合にうまく処理できなかったので断念

matchを使って処理を分岐させました

多分もっといい書き方はありそう

問題3

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

リストの連結で値 + リストの場合(::)とリスト + リストの場合(:::)で結構詰まりました

一つ目の方法だと100個のリスト取得にとても時間が掛かるため実用性は。。。

そこで二つ目、末尾再帰を用いる方法があるようです

途中の計算結果を引数として渡してあげることで実現できます

最後一つはStreamを使う方法

これはまだちょっと理解が追いついていない感がありますが、無限のリストを定義することができ、遅延評価を使うので計算する時に処理が走るというものらしい

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる

最初文字列で比較してソートすれば1行でいけるかと思いましたが、桁が違う時の比較がうまくいかなかったため断念

3,34,32 のリストをソートした場合 期待される並び方は34332だが34323のならびになってしまう

数値を足したもの同士を比較すればいける模様

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる

  • 数値のリストに対して+か-か結合させるかの組み合わせを出す
  • 出したリストを順次計算し100になるものを返す

というやり方でやりました。

perlではevalが使えるのでリスト出してeval,grepで簡単でしたがscalaでevalを使うにはライブラリを入れる必要がありそうだったので正規表現でパターンを分けて計算させました。

末尾再帰にはなってないのでリストの数が増えたら重くなってしまいます。

list.tail.headとかlist.tail.tailとかパターン全て列挙する関数に渡す値が綺麗に渡せなかったけどかなり時間かけてしまったのでここで終了。

最初と比べると処理の流れとか大分イメージがわくようになったので勉強になりました。

まだまだ全然慣れないですが。。。