Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2007-05-04 knight move

yaneurao2007-05-04

[] knight move  knight moveを含むブックマーク  knight moveのブックマークコメント

PKU1915にて挑戦者受付中である!(`ω´)


俺様は誰の挑戦でも受ける!おんどれら、かかってこやんかい!!(` ω ´)

emtemt 2007/05/04 00:12 はたしてrank no1 user yaneurao Code Length 239Bをこえることができる人がいるのか!ですね・・・。ぼくは無理です。m(_)m

yaneuraoyaneurao 2007/05/04 00:36 いや、超えられる人はいっぱいいると思う。

ショートコードの世界をみんなに知ってもらおうかと思ってちょっと煽ってみただけ。

yaneuraoyaneurao 2007/05/04 14:15 さっそくOzyさんに追い抜かされた。さすがや…。

yaneuraoyaneurao 2007/05/04 17:34 funnythingさん追い上げてきたなぁ…。私のほうは、現在181B。Ozyさんが166B。私のほうは、もうちょっと縮みそうだけど、ちょっとやそっとでは簡略化できそうにないのでこのへんでリタイア。(´ω`)

funnythingfunnything 2007/05/04 18:15 お初です。
僕は、なんかこう縮められそうなとこはあるんだけど縮まない、、、アイデア枯れてきたのでちょっと休憩かな、、

yaneuraoyaneurao 2007/05/04 22:49 私からのヒント
http://d.hatena.ne.jp/Ozy/20070420#p1

上記コードで、n>=6のとき
a = dx + dy;
dy = (dy+1)/2,
dx = (a+2)/3,
dx = MAX(dx,dy);
return dx+(a^dx)%2
と短縮できる。これでコード縮めていけば181B。
Ozyさんのほうは別のアルゴリズムではないかと思う。

黒龍黒龍 2007/05/05 00:10 面白そうですね。英語が苦手なので思いっきり勘違いしてるかもですがKnightの巡回問題はメンタルマジックでは割と有名な問題ですがテーブル化&テーブルの圧縮みたいな方法では逆効果かな??

yaneuraoyaneurao 2007/05/05 00:33 ↑この問題は(テーブル化するまでもなく)簡単な算術演算で求まることが知られています。詳しくは↑*2のOzyさんのページをご覧を。

Knightを用いた問題としては、Knight Tourという、Knightがチェスボードすべての地点を1回ずつ通るように逡巡させる問題があり、こちらは数学的にもプログラム的にも大変興味深いです。

funnythingfunnything 2007/05/05 06:40 アドバイスを参考に書いたら160Bが通ったんですが、、、自分のコードにこれほど自信が持てないのは初めてです(w
というわけでなんでそう短縮できるかの説明希望!

OzyOzy 2007/05/05 11:29 私も同じアルゴリズムですよー。
インチキすればたぶん140B位で通りますが・・・。

OzyOzy 2007/05/05 12:09 最大値と最小値を使うので、GNU C++の拡張演算子が使えるG++の方が短く出来るような気がします。funnythingさんのコードならきっと160Bは切れますよ。

funnythingfunnything 2007/05/05 12:56 あら、G++は最初に試したっきりでした、、、
そしてインチキの領域へ。

yaneuraoyaneurao 2007/05/05 15:31 一晩経過で、funnythingさんが153Bに!!(゜Д゜)

yamatsyamats 2007/05/05 17:41 Nous avons tout notre temps,Quelle surprise!!<En un mot 一晩 de 153B!(・Д・)!

yaneuraoyaneurao 2007/05/05 18:01 日本語でおk

AmaiSaetaAmaiSaeta 2007/05/06 18:38 ファミコンのKnight Moveかとオモタ(´・ω・`)

トラックバック - http://d.hatena.ne.jp/yaneurao/20070504
 | 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06