Gemmaの日記 このページをアンテナに追加 RSSフィード

2010-06-22

ICFPc2010参戦記 00:31  ICFPc2010参戦記 - Gemmaの日記 を含むブックマーク  ICFPc2010参戦記 - Gemmaの日記 のブックマークコメント

  • 会社の先輩に誘われて参加。
  • Common Lisp と英語が共通言語のチーム。コミュニケーションはIRCとgitのコミットログ。
  • 私は、Common Lisp書けない、ICFPc 初参加、月曜は会社で新人研修、なので、見学者扱い。
  • 記録: 0点
  • 任意の燃料を生成するための工場の生成プログラムを書く段階で断念。(大会の2合目といったところ)
  • 大会開始
  • 仲間が問題読む。
  • 仲間が回路の文法の解析。
  • 7時間目 仲間がゲートの入出力を同定。左 L-R(mod 3),右 L*R - 1(mod 3)。
  • 12時間目 私 参加。IRCログで以上の経緯を知る。問題を読む。回路シミュレータがもう半分できかけてるし、私の出番はなさそうだ。
  • 17時間目 仲間がサーバの入力列同定。
  • 20時間目 仲間が backward wire の意味を同定。backward か forward かはゲートの行番号で決まる。入力の初期値は 0 。回路シミュレータが完成に向かう。
  • 21時間目 仲間が回路シミュレータ完成。鍵prefix同定。
  • 次の問題は、サーバの入力列から鍵prefixを出力するような回路の生成だが、誰も解決できず。

http://eva-lu-ator.net/~gemma/hatena/icfp2010/keycircuit.gif

  • 簡単な回路1

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple01.gif

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple01detail.gif

  • 簡単な回路2

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple02.gif

  • 簡単な回路3

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple03.gif

  • 簡単な回路4

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple04.gif

  • 簡単な回路5

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple05.gif

  • 簡単な回路6

http://eva-lu-ator.net/~gemma/hatena/icfp2010/simple06.gif

  • 入力を出力する回路 (X:Xは気づかなかった)

http://eva-lu-ator.net/~gemma/hatena/icfp2010/identity.gif

  • ゲートのダイアグラム

http://eva-lu-ator.net/~gemma/hatena/icfp2010/diagram.gif

  • 常に 0 を出力する 定数回路

http://eva-lu-ator.net/~gemma/hatena/icfp2010/const0.gif

  • 常に 1 を出力する 定数回路

http://eva-lu-ator.net/~gemma/hatena/icfp2010/const1.gif

http://eva-lu-ator.net/~gemma/hatena/icfp2010/const1detail.gif

  • 常に 2 を出力する 定数回路

http://eva-lu-ator.net/~gemma/hatena/icfp2010/const2.gif

  • 定数回路じゃだめだ、NAND、カウンタ、シフトレジスタ
  • ゲートをとりあえず4つ以下とかで並びかえ全探索すれば手がかりになるかも…でも Common Lisp じゃないと…
  • 仲間の Common Lisp を読めず、書けず、さりとて再実装する勇気もない自分がうらめしい。
  • 日本時間 月曜は会社で新人研修。
  • 日本時間 月曜21時に大会終了。何もできなかった。情けない。
  • 男はつらいよ柴又慕情を見ながら、酒を飲み、下品なtweetをして、ふて寝した。
  • 「あんときの酒は、辛口でしたネェ」

来年は Common Lisp でチームに貢献するぞ。

   2010/07/10 16:38 こんにちわ。お忙しい中失礼します。
http://gemmat.s206.xrea.com/matome/matome.cgi

こちらのサイトで2ちゃんねるのスレッドが取得出来なくなっています。

確認した板です。
ニュース速報+
http://tsushima.2ch.net/newsplus/

ニュース速報
http://tsushima.2ch.net/news/

芸スポ速報+
http://kamome.2ch.net/mnewsplus/

対応よろしくお願い致します。

2009-10-21

2chのレスをアンカで並びかえる 00:16  2chのレスをアンカで並びかえる - Gemmaの日記 を含むブックマーク  2chのレスをアンカで並びかえる - Gemmaの日記 のブックマークコメント

アンカで並び替えて、例えばこのように7の次に11を表示するような処理を説明します。

http://eva-lu-ator.net/~gemma/geocities/sort2ch/a0.png

さて、2chの板はこのようになっています。

http://eva-lu-ator.net/~gemma/geocities/sort2ch/a1.png

アンカは、Web(網)と同様に網の目のようにリンクしています。これは有向グラフです。

http://eva-lu-ator.net/~gemma/geocities/sort2ch/data0.gif

有向グラフは難しい。

循環が困る。

http://eva-lu-ator.net/~gemma/geocities/sort2ch/circle.gif

循環は"未来へのアンカ"を無視すれば防げます。

  • このような未来へのアンカ>>100を無視する

http://eva-lu-ator.net/~gemma/geocities/sort2ch/future.png

これで問題が無閉路有向グラフになります。

燐隊長が困る。

http://eva-lu-ator.net/~gemma/geocities/sort2ch/lin.png

燐隊長は、"一番大きなアンカ"の8をとることにしましょう。

これで問題がこのような単連結無閉路有向グラフになります。

http://eva-lu-ator.net/~gemma/geocities/sort2ch/data1.gif

実装

var testdata = [
  [],                // 配列のインデックスを1から始めたいので詰め物をする
  [],                // 1:
  [1],               // 2: >>1
  [1],               // 3: >>1
  [],                // 4:
  [4],               // 5: >>4
  [5],               // 6: >>5
  [5],               // 7: >>5
  [4,100],           // 8: >>4 >>100
  [1,2,3,4,5,6,7,8], // 9: 燐隊長
  [],                //10: 
  [5]];              //11: >>5

function removeFutureAnchor(aData) {
  return aData.map(function(res, i) {
    return res.filter(function(x) {
      return x < i;
    });
  });
}

function maxAnchor(aData) {
  //配列の最大の要素を求めるmax関数。
  function max(aArray) {
    var r = -1;
    for (var i = 0; i < aArray.length; i++) {
      if (aArray[i] > r) r = aArray[i];
    };
    return r;
  }
  return aData.map(function(res) {
    return res.length ? [max(res)] : [];
  });
}

//木を作る。転置インデックスに似ている。
function makeTree(aData) {
  var table = [];
  aData.forEach(function(res, i) {
    table[i] = [i];
    res.forEach(function(x) {
      table[x].push(i);
    });
  });
  return table;
}

makeTreeは[親、子、子、子]のように木を表現します。さっきのグラフと見比べてください。([0]は詰め物なので無視してください)

makeTree(maxAnchor(removeFutureAnchor(testdata))));
->
 [[0],
 [1,2,3],
 [2],    
 [3],    
 [4,5,8],
 [5,6,7,11],
 [6],
 [7],
 [8,9],
 [9],
 [10],
 [11]]

http://eva-lu-ator.net/~gemma/geocities/sort2ch/data1.gif

この木を順番にたどって直列にするのがserialize関数です。

木の入れ子構造に、関数fの再帰が威力を発揮します。

function serialize(aData) {
  var result = [];
  var done = aData.map(function(_) {return false;});
  function f(res) {
    if (!res.length) return;
    if (!done[res[0]]) {
      done[res[0]] = true;
      result.push(res[0]);
    }
    res.slice(1).map(function(x) {
      return aData[x];
    }).forEach(f);
  }
  aData.forEach(function(res) {
    if (!done[res[0]]) f(res);
  });
  return result;
}
serialize(makeIndex(maxAnchor(removeFutureAnchor(testdata))));

-> [0,1,2,3,4,5,6,7,11,8,9,10]

これで完成です。

発展として、木を統合する複雑なコードはこちらにあります。

木の統合(SchemeをJavaScriptに移植した) - Gemmaの日記

参考文献

osiireosiire 2009/10/22 08:27 もっと抽象的なやり方なんかはocamlgraphが参考になるよー

GemmaGemma 2009/10/22 09:14 うひょー さすがOCaml。数独をグラフ彩色で解くサンプルとか面白そうですね。

2008-03-16

コード 03:43  コード - Gemmaの日記 を含むブックマーク  コード - Gemmaの日記 のブックマークコメント

Gaucheで総当たりで解きます。わかりやすく書くとこんなコード。

(use srfi-1)
(use util.combinations)

(define (same-answer? x y)
   ;;ネックレスの等価判定。
  (or (equal? x y)
      (equal? x (cons (car x) (reverse (cdr y))))))

(define (5balls-very-simple)
  (define result '())
  (define nums (iota 21 1))
  (combinations-for-each
   (lambda (x)
     (permutations-for-each
      (lambda (x)
	(receive (a b c d e) (apply values x)
	  (when (and (= 21 (+ a b c d e))
		     (lset= eq?
			    nums
			    (list (+ a b c d e)
				  a
				  (+ a b)
				  (+ a b c)
				  (+ a b c d)
				  b
				  (+ b c)
				  (+ b c d)
				  (+ b c d e)
				  c
				  (+ c d)
				  (+ c d e)
				  (+ c d e a)
				  d
				  (+ d e)
				  (+ d e a)
				  (+ d e a b)
				  e
				  (+ e a)
				  (+ e a b)
				  (+ e a b c))))
	    (push! result x))))
      x))
   nums 5)
  (delete-duplicates result same-answer?))

Gaucheのutil.combinationsが総当たりに便利です。で、マクロを使うともっと短くかける部分があるわけで。

(define-macro (math-goodbye . l)
  (let ((cp-list (cartesian-product (list (iota (length l)) (cdr (iota (length l))))))
	(necklace (apply circular-list l)))
    `(list ,@(cons `(+ ,@l)
		   (map (lambda (x)
			  `(+ ,@(take (drop necklace (car x)) (cadr x))))
			cp-list)))))

define (5balls)
  (define result '())
  (define nums (iota 21 1))
  (combinations-for-each
   (lambda (x)
     (permutations-for-each
      (lambda (x)
	(receive (a b c d e) (apply values (cons 1 x))
	  (when (and (= 21 (+ a b c d e))
		     (lset= eq? nums (math-goodbye a b c d e)))
	    (push! result (list a b c d e)))))
      (cons 2 x)))
   '(3 4 5 6 7 8 9 10 11) 3)
  (delete-duplicates result same-answer?))

(define (6balls)
  (define result '())
  (define nums (iota 31 1))
  (combinations-for-each
   (lambda (x)
     (permutations-for-each
      (lambda (x)
	(receive (a b c d e f) (apply values (cons 1 x))
	  (when (and (= 31 (+ a b c d e f))
		     (lset= eq? nums (math-goodbye a b c d e f)))
	    (push! result (list a b c d e f)))))
      (cons 2 x)))
   '(3 4 5 6 7 8 9 10 11 12 13 14 15 16) 4)
  (delete-duplicates result same-answer?))

(define (7balls)
  (define result '())
  (define nums (iota 43 1))
  (combinations-for-each
   (lambda (x)
     (permutations-for-each
      (lambda (x)
	(receive (a b c d e f g) (apply values (cons 1 x))
	  (when (and (= 43 (+ a b c d e f g))
		     (lset= eq? nums (math-goodbye a b c d e f g)))
	    (push! result (list a b c d e f g)))))
      (cons 2 x)))
   '(3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22) 5)
  (delete-duplicates result same-answer?))

ここまで来たら、8balls, 9balls ... を自動生成するマクロを書いてやるぜ。満足満足。

(use srfi-1)
(use util.combinations)

(define (same-answer? x y)
   ;;ネックレスの等価判定。
  (or (equal? x y)
      (equal? x (cons (car x) (reverse (cdr y))))))

(define-macro (math-goodbye . l)
  (let ((cp-list (cartesian-product (list (iota (length l)) (cdr (iota (length l))))))
	(necklace (apply circular-list l)))
    `(list ,@(cons `(+ ,@l)
		   (map (lambda (x)
			  `(+ ,@(take (drop necklace (car x)) (cadr x))))
			cp-list)))))

(define-syntax nballs-helper
  (syntax-rules ()
    ((nballs n a ...)
     (lambda ()
       (define result '())
       (define nums (iota (+ (* n (- n 1)) 1) 1))
       (combinations-for-each
	(lambda (x)
	  (permutations-for-each
	   (lambda (x)
	     (receive (a ...) (apply values (cons 1 x))
	       (when (and (= (+ (* n (- n 1)) 1) (+ a ...))
			  (lset= eq? nums (math-goodbye a ...)))
		 (push! result (list a ...)))))
	   (cons 2 x)))
	(iota (- (/ (* n (- n 1)) 2) 1) 3) 3)
       (delete-duplicates result same-answer?)))))

(define-macro (nballs n)
  `(nballs-helper ,n ,@(map (lambda _ (gensym)) (iota n))))

(define 8balls (nballs 8))

srtsrt 2013/01/29 23:46 ●球の数が7つの時は、解無し

●球の数が8つの時は、以下の6通り

1 2 10 19 4 7 9 5
1 3 5 11 2 12 17 6
1 3 8 2 16 7 15 5
1 4 2 10 18 3 11 8
1 4 22 7 3 6 2 12
1 6 12 4 21 3 2 8

●球の数が9つの時は、以下の4通り

1 2 4 8 16 5 18 9 10
1 4 7 6 3 28 2 8 14
1 6 4 24 13 3 2 12 8
1 11 8 6 4 3 2 22 16

●球の数が 10個の時は、以下の6通り

1 2 6 18 22 7 5 16 4 10
1 3 9 11 6 8 2 5 28 18
1 4 2 20 8 9 23 10 3 11
1 4 3 10 2 9 14 16 6 26
1 5 4 13 3 8 7 12 2 36
1 6 9 11 29 4 8 2 3 18

●球の数が 11個の時は、解無し

●球の数が 12個の時は、以下の 18 通り

1 2 9 8 14 4 43 7 6 10 5 24
1 2 12 31 25 4 9 10 7 11 16 5
1 2 14 4 37 7 8 27 5 6 13 9
1 2 14 12 32 19 6 5 4 18 13 7
1 3 8 9 5 19 23 16 13 2 28 6
1 3 12 34 21 2 8 9 5 6 7 25
1 3 23 24 6 22 10 11 18 2 5 8
1 4 7 3 16 2 6 17 20 9 13 35
1 4 16 3 15 10 12 14 17 33 2 6
1 4 19 20 27 3 6 25 7 8 2 11
1 4 20 3 40 10 9 2 15 16 6 7
1 5 12 21 29 11 3 16 4 22 2 7
1 7 13 12 3 11 5 18 4 2 48 9
1 8 10 5 7 21 4 2 11 3 26 35
1 14 3 2 4 7 21 8 25 10 12 26
1 14 10 20 7 6 3 2 17 4 8 41
1 15 5 3 25 2 7 4 6 12 14 39
1 22 14 20 5 13 8 3 4 2 10 31

●球の数が 13個の時は、解無し

●球の数が 14個の時は、以下の 20 通り

1 2 13 7 5 14 34 6 4 33 18 17 21 8
1 2 21 17 11 5 9 4 26 6 47 15 12 7
1 2 28 14 5 6 9 12 48 18 4 13 16 7
1 3 5 6 25 32 23 10 18 2 17 7 22 12
1 3 12 7 20 14 44 6 5 24 2 28 8 9
1 3 24 6 12 14 11 55 7 2 8 5 16 19
1 4 6 31 3 13 2 7 14 12 17 46 8 19
1 4 8 52 3 25 18 2 9 24 6 10 7 14
1 4 20 2 12 3 6 7 33 11 8 10 35 31
1 5 2 24 15 29 14 21 13 4 33 3 9 10
1 5 23 27 42 3 4 11 2 19 12 10 16 8
1 6 8 22 4 5 33 21 3 20 32 16 2 10
1 8 3 10 23 5 56 4 2 14 15 17 7 18
1 8 21 45 6 7 11 17 3 2 10 4 23 25
1 9 5 40 3 4 21 35 16 18 2 6 11 12
1 9 14 26 4 2 11 5 3 12 27 34 7 28
1 9 21 25 3 4 8 5 6 16 2 36 14 33
1 10 22 34 27 12 3 4 2 14 24 5 8 17
1 10 48 9 19 4 8 6 7 17 3 2 34 15
1 12 48 6 2 38 3 22 7 10 11 5 4 14

●球の数が 15個の時は、解無し

家の計算機ではこの辺が限界のようです。

以上