CodeIQの魔方陣ヌルヌル問題を解いてみた

方陣ヌルヌル問題を解いていたはずなのに、スパゲティグルグルになってました。(汚くて大変恐縮ですが)ワシのコードを見てくだされ~!!

問題

【問題】
正方形の方陣に、縦・横・斜めすべての列の値の合計が 0 になるように、すべて異なる整数を配置してください。
方陣は、3×3・4×4・5×5の3種類のサイズで作ってください。

解答

この内容で提出し正解でした。

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 

求め方

全探索しようとしたのですが全く終わる気配がなく・・

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'以外は変換できない。

そして訂正したコードがこちらになります。

デコード部分
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問題で興味を持ったRubySHA-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つのプログラムで使った文字をできるだけ使わないようにしてください。
複数の実装で使われている文字の種類が少ないほうが高評価となります。
複数の実装で使われている文字の種類がひとつもない場合に最高評価になります。

提出内容

最終的に提出したコードはこちら。最高評価を目指して、文字の種類の重複なしを目指してがんばってみました。

実行結果 SQL
実行結果 Ruby
実行結果 Perl

どうやって解いたか

「大文字」「小文字」「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}

実行結果

「ASCIIコード」Perl6

タブを使うことで空白使用は回避したものの、「say」で"a"が他と重複するためNG。

say	"\x68\x65\x6C\x6C\x6F\x2C\x20\x77\x6F\x72\x6C\x64"

実行結果


最終回答の1.と2.を求めた後、カンマと空白が重複しないようにするために作ったプログラムがこちら。
Perlで文字列のビット演算が使えるのを別問題でちらっと見ていたので活用してみました。

3/24追記

出題者の鍋谷さん(id:nabetani)の解説記事に載りました。
CodeIQ に出した「hello, world × 3」の解説・解題 - Codeへの愛とCuriosity