ソフトウェアエンジニアが1時間以内に解決できてしかるべき5つの問題をやってみた
2015-05-11-1
[Programming][Perl]
これ、やってみた。
- 1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に
http://www.softantenna.com/wp/software/5-programming-problems/
(元記事: Five programming problems every Software Engineer should be able to solve in less than 1 hour)
問題1、問題2、問題3は簡単すぎなので飛ばして問題4と問題5に挑戦。
問題4:
最初は単純に数値を文字列として降順にソートするだけと思ってシンプルなワンライナーを書いてみた。
しかし、"10 1 15" が "15101" となってしまう。正しくは "15110" なのに。"10" と "1" の場合、つまり桁が異なるときの比較が問題。そこで、"10" と "1" の比較は先頭の数字を末尾にくっつけた "10111111..." と "11111111..." で比較することにした。直してみたのがこれ。
正解をみてみたらもっとシンプルで、"10" と "1" の比較はを "101" ("10"+"1") と "110" ("1"+"10") の比較で解決してた。なるほどなあ。合理的でエレガントだ。
問題5:
こちらは総当たりしただけ。
"123456789" の各数字の間に入るのは、"+" か "-" か "" (なにもなし) の3種類。
なので3の8乗 (6561) 個のパターンがあるだけ。
再帰とかじゃなく、単に0から6560までの6561個の数を3進数に変換する処理で実装。
というか、問題4と問題5は問題1,2,3の結果を踏まえてプログラムを書くのが正しい流れだったのかも。
- 1時間以内に解けなければプログラマ失格となってしまう5つの問題が話題に
http://www.softantenna.com/wp/software/5-programming-problems/
(元記事: Five programming problems every Software Engineer should be able to solve in less than 1 hour)
問題1、問題2、問題3は簡単すぎなので飛ばして問題4と問題5に挑戦。
問題4:
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる
最初は単純に数値を文字列として降順にソートするだけと思ってシンプルなワンライナーを書いてみた。
perl -le 'print join "", reverse sort @ARGV' 50 2 1 9
しかし、"10 1 15" が "15101" となってしまう。正しくは "15110" なのに。"10" と "1" の場合、つまり桁が異なるときの比較が問題。そこで、"10" と "1" の比較は先頭の数字を末尾にくっつけた "10111111..." と "11111111..." で比較することにした。直してみたのがこれ。
perl -le ' print join "", reverse sort { my $t=substr($a, 0, 1); $t != substr($b, 0, 1) ? ($a cmp $b) : ($a.($t x length($b)) cmp $b.($t x length($a))) } @ARGV' 50 5 55 1 10 11 9
正解をみてみたらもっとシンプルで、"10" と "1" の比較はを "101" ("10"+"1") と "110" ("1"+"10") の比較で解決してた。なるほどなあ。合理的でエレガントだ。
問題5:
1,2,...,9の数をこの順序で、"+"、"-"、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 - 5 + 67 - 8 + 9 = 100となる
こちらは総当たりしただけ。
"123456789" の各数字の間に入るのは、"+" か "-" か "" (なにもなし) の3種類。
なので3の8乗 (6561) 個のパターンがあるだけ。
再帰とかじゃなく、単に0から6560までの6561個の数を3進数に変換する処理で実装。
ワンライナー:perl -le ' for (0..3**8) { my $s = 1; my $n = $_; for (2..9) { $s .= ("+", "-", "")[$n % 3].$_; $n /= 3; } print $s if eval($s) == 100; }'
perl -le 'for(0..3**8){$s=1;$n=$_;for(2..9){$s.=("+","-","")[$n%3].$_;$n/=3}print $s if eval($s)==100}'
というか、問題4と問題5は問題1,2,3の結果を踏まえてプログラムを書くのが正しい流れだったのかも。