CodeIQの魔方陣ヌルヌル問題を解いてみた
魔方陣ヌルヌル問題を解いていたはずなのに、スパゲティグルグルになってました。(汚くて大変恐縮ですが)ワシのコードを見てくだされ~!!
解答
この内容で提出し正解でした。
n = 3 -2 8 -6 -4 0 4 6 -8 2 n = 4 -15 13 11 -9 7 -5 -3 1 -1 3 5 -7 9 -11 -13 15 n = 5 -4 10 24 -22 -8 -6 -2 12 16 -20 -18 -14 0 14 18 20 -16 -12 2 6 8 22 -24 -10 4
求め方
全探索しようとしたのですが全く終わる気配がなく・・
ウニョラー!! 期限迫ってるのでぐーぐる先生にヒントだけ頂こう… 挑戦者求む!魔方陣ヌルヌル by Short Coder @ozy4dm http://t.co/1tJBAbfvFv via @codeiq
— tmftake++ (@tmftake) May 25, 2014
Ozyさんの問題だったので、JavaScriptでショートコーディングしてみることにしました。(とは言いつつあまり短くなっていませんが・・・)
方陣に使用する数字は、和が0になるように同じ数字のプラスとマイナスを使用しました。
奇数x奇数のコード(n=3 or 5)
n=5;p=n*n;a=[];x=p+~(n/2);for(i=p;i--;){a[x]=i*2-p+1;x=a[t=(x-1+(x%n?n:2*n))%p]!=null?(x-n+p)%p:t}for(i=n;i--;)print(a.slice(i*n,i*n+n).join(" "))
「ヒンズーの連続方式」で解きました。
4x4のコード
a=[];for(i=16;i--;)a[38505>>i&1?i:15-i]=i*2-15;for(i=4;i--;)print(a.slice(i*4,i*4+4).join(" "))
解き方の参考:4の倍数×4の倍数の魔方陣の作り方
38505=1001 0110 0110 1001(2進数)で、
1001
0110
0110
1001
1の場所→インデックス順(左上から)
0の場所→インデックス逆順(右下から)
値を埋めていくよう作りました。
感想
自力では3x3(手計算)しか求めることができませんでしたが、勉強するいいきっかけとなりました。
フィードバックコメントを出題者のOzyさんよりいただきました。
まさかのショートコーディング!
笑わせていただきました、ありがとうございます!
(2014/06/13追記)
解説記事来てました。
タテ・ヨコ・ナナメ、すべての合計が0(null)になる「魔方陣ヌルヌル」解説記事|CodeIQ MAGAZINE
「ショートコード書いちゃった賞」頂いちゃいました。ありがとうございます。
CodeIQのチケットゴブル問題を解いてみた
スペーストーキー問題のリベンジ。
頭の中で考えたアルゴリズムをコードに落としました。
コード
可読性ってナンデスカ…。
思いついた解法
あまりにもコードだと分かりにくすぎるので、以下でかるーくコメントしていきます。
チケットを読み込み
データをパッと見でうるう日があったりと、どんな罠があるか分からなかったので出国日も帰国日も文字列にしちゃいました。
a=[] b=[] tickets.split(/\n/).each {|t| t = t.split(/\s|-/); if (t.length >= 3) then t[1] = t[1].split(/\//) from = t[1][0].rjust(2,"0") + t[1][1].rjust(2,"0") t[2] = t[2].split(/\//) to = t[2][0].rjust(2,"0") + t[2][1].rjust(2,"0") a.push({"name" => t[0],"from" => from,"to" => to}) end }
チケットを帰国日降順ソート
a = a.sort {|x, y| y["to"] <=> x["to"] }
チケットを先頭から順に、対象チケットとチケット数最大となる組み合わせを保持(b)
def getMaxTickets(target, tickets) max = [] tickets.each {|t| if (nodup(t[0], target) && max.length < t.length) then max = t end } return max end a.each{|t| c=[] c.push(t) c += getMaxTickets(t,b) b.push(c) }
チケット数で降順ソート、最大チケット数とチケット(国名アルファベット順)を出力
b = b.sort {|x, y| y.size <=> x.size } d = b[0].sort {|x, y| x['name'] <=> y['name'] } print d.size d.each{|s| print " " + s['name']}
解を出したあとに悩んだこと
出国日昇順ソートで検算したら別解が出てきた
→目で見てもプランの中で交換できそうなチケットがあるのを確認。問題文に条件が書かれていたので安心しました。
あなた 「 もしも 、 枚数が同じ複数のプランがあった場合にはどうしましょうか 」
依頼者 「 プランはひとつだけ作っていただければ結構です 」
また、このタイミングで「国名アルファベット順」に気づいて慌てて直しました。
感想
徐々に頭にアルゴリズムの基礎を擦り込めている気がします。問題の難易度のせいもあるかもしれませんが試行錯誤の回数が減ってきました。
最適な解法の選択とコードへの落とし込みを徐々に早く出来るよう引き続き問題を解いていこうと思います。
CodeIQのスペーストーキー問題を解いてみた
ワナも、引っ掛けも、あるんだよ。
というわけで、仕事終わりの午前零時半にコード書いてさっさと提出したら見落としがありました。検算大事。
解答
連長圧縮。2文字ごとに英字とその連続回数を英小文字で示す。文字数が奇数のコマンドは生成できない。
・・・まではすぐにわかったのですが。
いつもは気にする境界値をすっかり忘れてました。
例えば1,3文字目などに同一文字が連続で来た場合、2文字は'z'以外は変換できない。
私の理解が正しければ、スペーストーキーのコーナーケースはexerciseとsqueezedの2つ。前者のみがXになります。#codeiq
— しえる (@cielavenir) April 28, 2014
そして訂正したコードがこちらになります。
デコード部分
def decode(s) r="" if (s.length % 2 == 1) then return "X" end p = "" s.scan(/.{2}/).each {|c| if (p[0] == c[0] && p[1] != "z") then return "X" end r += c[0] * (c[1].ord-0x60) p = c } return r end
全ソース
感想
提出は 一晩寝かせて 再チェック。
CodeIQのクリプタン帝国の暗号文2をPowerShellで解いてみた
PowerShellのお勉強がてら。
SHA1ハッシュ化
$data = [system.Text.Encoding]::UTF8.GetBytes("test") $alg = New-Object System.Security.Cryptography.SHA1CryptoServiceProvider $HashBuilder = New-Object System.Text.StringBuilder $alg.ComputeHash($data) | %{[void] $HashBuilder.Append($_.ToString("x2"))} $HashBuilder.ToString()
暗号文2を解いてみる
解答PDFのロジックを忠実にPowerShellで再現したつもりです。
というわけで、解説は解答PDFをご参照ください。
# 暗号文を平文に変換する function ConvertTo-OriginalString($crypted, $seed) { # 各変数初期化 $data = @($seed) $strs = "" $alg = new-object System.Security.Cryptography.SHA1CryptoServiceProvider $HashBuilder = New-Object System.Text.StringBuilder ($crypted -replace "`n"," ").split(" ") | ForEach-Object{ $code = [System.Convert]::ToInt32($_.Trim(), 16) # バーナム暗号の復号 # ⇒SHA-1ハッシュとのビットXORをとり平文文字列に追加 $chr = [char]($code -bxor $seed) $strs += $chr # SHA-1ハッシュ化、取得した16進文字列を数値変換して剰余をとる # ⇒桁数のせいか数値変換できなかったので下2桁のみ取得に変更 #$seed = ([System.Convert]::ToInt64($HashBuilder.ToString(), 16)) % 256 $seed = $alg.ComputeHash($data) | select -last 1 $data += $seed } return $strs } $crypted = @' C8 EE A8 0F 80 FD 60 E9 00 3F C4 B0 10 2C E7 33 DC 82 1E 6B D3 5B BB FA 8A 48 C2 F0 97 7F A6 C0 9C 32 15 89 37 51 AA C9 D8 93 9D 86 DA 28 BB 58 A2 6D E2 7F 3A 3B A5 F1 A5 31 89 6C D8 B5 E6 15 BC A4 BC 59 93 CD 68 85 52 48 93 36 B1 F4 5E FA D1 62 7C 4B C1 A2 E4 98 7F 17 D5 21 37 7F C5 A0 2C BE 67 4D DC 5A 0B 66 D9 D4 5B 09 58 2F 72 ED 4F 45 81 36 73 AB 18 DF 51 5C 1A D3 7F 2E EF B8 D8 C8 C0 8A 4C BA 87 23 01 44 46 E7 03 42 EF 44 EA 05 36 11 3C 03 67 24 A4 BC 53 EF 6E 2D C3 66 B9 CF 9C C2 55 04 9C F8 F4 99 B8 AF FF EA 16 7D AA EC FF 7D E2 52 8B B7 65 EE 2C 69 07 1D D9 14 C5 5A 6B 5A BC EF 34 12 C4 0D 7D 4E AA DD 19 0A 2B 5F 8B CE 06 2D A0 6C 76 49 E2 62 AC 4B 04 46 FA E6 58 3E D0 7B 58 F0 8A 9E 67 1B 96 3C B3 93 94 66 8A 44 50 D5 4F F8 49 33 4E BA CA E1 95 24 92 43 85 FC A8 B1 66 6F 46 57 BD A5 B3 1E 1B 47 5B 95 EB E7 8C 41 25 DC 88 9D 66 72 36 6B C1 D8 E8 60 59 BA 1F BD 66 A7 3C A3 1D 08 DE CF EB 02 10 90 FD 9A F9 51 83 6C 22 79 6F 79 D7 98 52 43 DD 1E 66 AB E1 F0 E2 E4 85 0D 5F E5 B9 83 07 E0 84 9C B8 3A 60 1E 00 31 8B E9 7B 9B 6E 56 F0 84 81 A7 AE AE BE B2 56 0A C3 B8 DE B8 5C 8A 09 83 4C 9F 12 D3 DE C2 08 F2 79 CF 71 51 B3 E5 F0 D2 47 12 0E DF 98 B2 5C 02 E7 E3 4D B3 6B 20 91 0D 7C 0E E2 95 2E 7A 29 E2 7C C0 A8 9A B6 25 C1 FB E5 EB A5 A0 F6 E2 E6 A0 70 4E E5 8F DE 1E 9C 33 29 2F DA 85 E0 9A C2 F6 6F 71 A9 84 E7 F9 61 29 50 3A 0A 65 C3 BD 91 CC 7E 52 69 84 12 27 6C 97 0C 9C FC 60 32 58 7D BD 2E 4F 5A 36 97 ED 34 5A 35 2F A8 ED DC A0 67 F0 FE 17 C9 E0 6E D6 D1 9D 58 C2 E0 81 6F C1 7F E9 38 5C EC 5A 30 08 00 CB C3 65 2F A9 78 6D F5 C0 D1 34 8E 99 C8 52 85 E4 F7 06 FD E7 1B 14 9F 97 BD D9 97 29 18 8A 2A E4 76 AA 36 2D CE 4E E4 D0 84 69 65 22 0C 9B A4 42 '@ # 変換呼出 # 総当たり最初のコード判定 #127..255 | %{ $_; ConvertTo-OriginalString $crypted ([byte]$_) } $org = ConvertTo-OriginalString $crypted ([byte]0xEA) Write-Host $org
CodeIQのクリプタン帝国の暗号を解いてみた
粘り強く挑戦したら解けて大満足。
問題
あなたはクリプタン帝国にプログラマとして雇われました。
あなたは、依頼に基づき「暗号文」二つを解読しなければなりません。
それぞれの「暗号文」にはクリプタン帝国の諜報員が入手した
《暗号プログラムの構成図》が付随していますが、十分な情報はありません。
「暗号文」二つを解読して、
暗号化する前の文章を復元することがあなたのミッションなのです!
暗号文1
問題の構成図に着目。
E[i] := SBOX(T[i])
一文字ずつ暗号化しているのを見て、頭の片隅に残っていた「頻度分析」というキーワードを引っ張り出して調べてみました。暗号文に使われているコードの種類が34種類であることを調べて、これで解けると確信しました。
アルファベットの文字頻度表を参考にして、コードを文字に置換していきました。
文字頻度表
例えば、
CB:115回→空白 9C:67回→e BA:49回→t …
と言った形で。
大体の文字が埋まったところで、あとは英単語の穴埋めパズルの要領で原文を推測して埋めていきました。ここが一番楽しかった。
回答チェックに使ったコードがこちらです。
実行結果
暗号文2
先日のhello world問題で興味を持ったRubyでSHA-1ハッシュ化&暗号コードとのXORを試行。
最初はDigest::SHA1.hexdigestを使って一文字ずつハッシュ化してたのですがうまく行かず。
Rubyのドキュメントを漁ったところ、updateメソッドで一文字ずつ対象文字を追加することができることを知り、試したらビンゴでした。
class Digest::Base
復号に使ったコードはこちら。
実行結果
感想とか
暗号解読は初めてながら、一週間かけてなんとか解けました。しかし、出題者の結城さんのツイートにもある通り、分かる人にはきっと簡単な問題なんだろうなーと。
どちらも、勉強しなおす良いきっかけになりました。
CodeIQの「5乗のダンジョン」を解いてみた
最短コードへの道のりは遠く・・・
問題
「1, 2, 3, 4, 5, 6, 7, 8, 9」の9つの数字から、被らないように3つずつ選んだ、2つの「3桁の数字」があります。これは、たとえば「123, 456」「951, 372」などです(「123, 345」のように、同じ数字が2回出てくることはありません)。
この2つの数字のうち、1つ目の数値を「a」、2つ目の数値を「b」とします。「c」の値が、「a」を5乗した値ならば「0」を、「b」を5乗した値ならば「1」を戻すプログラムを書いてください。
LV1
3回挑戦しました。
1回目:16文字
問題文そのままに、安直に5乗したコードがこちら。
(b*b*b*b*b==c)+0
2回目:12文字
規則性に気づいてまず書いたコードがこちら。
+!((c-b)%10)
3回目:11文字
最短コードになりました。
(c-a)%10&&1
LV2
30文字
-(c-a).toFixed().substr(-1)&&1
数値⇒文字列変換はtoFixed、末尾はsubstr(-1)を使いました、というかそれ以外わかりませんでした。
解説記事を見ると、escape(n)とか他にもいろいろあったんですね。
そして新たなダンジョンへ続く…。
挑戦者求む!【JavaScript】あべこべのダンジョン - LV1 by クロノス・クラウン合同会社 柳井 政和│CodeIQ
CodeIQの「hello, world × 3」に挑戦してみた
3/17現在、フィードバックはまだですが記事にしてみます。
最高評価は難しい、と思ったらやっぱり難しかった。
問題
挑戦者求む!【コーディングパズル】hello, world × 3 by @Nabetani 鍋谷 武典│CodeIQ
hello, world
という文字列を出力するプログラムを、3つのプログラミング言語で1つずつ書いてください。
ただし、どのプログラムも、他の2つのプログラムで使った文字をできるだけ使わないようにしてください。
複数の実装で使われている文字の種類が少ないほうが高評価となります。
複数の実装で使われている文字の種類がひとつもない場合に最高評価になります。
どうやって解いたか
「大文字」「小文字」「ASCIIコード」と大枠を決めて、与えられた言語の中でそれぞれ組めそうなものを抽出しました。
他にも以下のもので試しに作ってみましたが、どれも重複有りでボツにしました。特に記号の重複には苦労しました。
「大文字」COBOL
ドットや丸括弧、空白など、他の言語と重複してしまうためNG。(COBOL、初めて書きました・・・。)
IDENTIFICATION DIVISION. PROGRAM-ID. IDEONE. DATA DIVISION. WORKING-STORAGE SECTION. 01 HELLO PIC XXXXXXXXXXXXXX VALUE 'HELLO, WORLD'. PROCEDURE DIVISION. MOVE FUNCTION LOWER-CASE(HELLO) TO HELLO. DISPLAY HELLO STOP RUN.
「ASCIIコード」Ruby
カンマやドットが他と重複、eachやchrの文字の種類が"hello, world"小文字表記や他言語のecho、print、sayなどの命令とかぶるためNG
[104,101,108,108,111,44,32,119,111,114,108,100].each{|e|$><<e.chr}
3/24追記
出題者の鍋谷さん(id:nabetani)の解説記事に載りました。
CodeIQ に出した「hello, world × 3」の解説・解題 - Codeへの愛とCuriosity
△文字列を回避するためのトリックの量が最低限に抑えられていて、おそらく今回もっとも可読性が高いコードになっています。
○トリックなんてほとんど知らないので記号重複を回避しつつ簡単に書かざるを得なかった
— tmftake.local (@tmftake) 2014, 3月 21