DouKaku? Language detail: diff

起動オプションの解析 (Nested Flatten)

sh版作っていて-oオプションのチェックが抜けていたことに気づくorz

--- doukaku205.c        2008-09-10 22:23:39.953125000 +0900
+++ doukaku205.c.new    2008-09-10 22:43:58.656250000 +0900
@@ -61,6 +61,14 @@
     info.argv0 = argv[0];
     info.argv  = &argv[optind];
     info.num = argc - optind;
+
+    /* 必須チェック */
+    if( info.output != true )
+    {
+        printf("必須オプションがたりない\n");
+        printf("書式：cmdopt -o [-q] [-d{0|1|2}] 文字列 [文字列 ...]\n");
+        return 1;
+    }
     if( info.num < 1 )
     {
         printf("文字列がない\n");

LL Golf Hole 1 - tinyurl.comを使ってURLを短縮する (Nested Flatten)

parseに直接urlを渡すように修正。

--- a/lxml.py   Tue Sep 02 15:50:19 2008 +0900
+++ b/lxml.py   Tue Sep 02 15:57:27 2008 +0900
@@ -1,7 +1,6 @@
-from urllib2 import urlopen
 from lxml.html import parse, submit_form

-form = parse(urlopen('http://tinyurl.com/')).getroot().forms[1]
+form = parse('http://tinyurl.com/').getroot().forms[1]
 form.fields['url'] = 'http://ll.jus.or.jp/2008/info/xgihyo'
 root = parse(submit_form(form)).getroot()
 print root.xpath('//blockquote/b')[1].text

LL Golf Hole 3 - 13日の金曜日を数え上げる (Nested Flatten)

数の出力が抜けてました。

bash.exe -c "diff -u old/Count13Friday.java Count13Friday.java"
--- old/Count13Friday.java      2008-08-06 18:51:31.343750000 +0900
+++ Count13Friday.java  2008-08-06 18:49:00.625000000 +0900
@@ -22,6 +22,7 @@
             current.add(MONTH, 1);
         }
         System.out.println("Fridays = " + fridays);
+        System.out.println("Fridays count = " + fridays.size());
     }

 }

LL Golf Hole 2 - 文字列に含まれる単語の最初の文字を大文字にする (Nested Flatten)

お題の文字列すら変換できてなかった。失敗失敗。

<●止まらない問題修正版(56byte)
< b;main(a){b=getchar();~b&&main(putchar(b-a>64?b-32:b));}
---
>●止まらない問題修正版(59byte)
> b;main(a){b=getchar();~b&&main(putchar(b>96&a<33?b-32:b));}

クリップボードへの転送 (Nested Flatten)

ちょっと簡略化。

--- clipboard.py    Mon Feb 11 19:47:02 2008
+++ clipboard.py    Mon Jul  7 02:51:50 2008
@@ -37,9 +37,7 @@
         raise WindowsError("GlobalAlloc() failed")
     try:
         with _GlobalLock(h) as p:
-            p = (ctypes.c_char * (len(s) + 1)).from_address(p)
-            for i, c in enumerate(s + "\0"):
-                p[i] = c
+            (ctypes.c_char * (len(s) + 1)).from_address(p).value = s
         # clipboard
         with _Clipboard():
             user32.EmptyClipboard()

比較しないソートの作成 (Nested Flatten)

おっと。無駄が多すぎた。
以下の修正で関数に入る回数が109→15に改善しました。

3c3
<       var mid = (minVal + maxVal) / 2;
---
>       var mid = Math.floor((minVal + maxVal) / 2);

情報オリンピック2007年度国内本選問題5 (Nested Flatten)

memsetを使うようにしたところ，大幅に高速化しました。

--- 5.cpp    Wed Jun 25 16:56:20 2008
+++ 5.cpp    Sat Jun 28 20:33:02 2008
@@ -5,6 +5,7 @@
 #include <queue>
 #include <utility>
 #include <cassert>
+#include <cstring> // memset()
 
 #define REP(i, b, e) for (size_t i = b; i < e; ++i)
 
@@ -24,7 +25,7 @@
 template <typename T>
 size_t find(const std::vector<T>& v, const T& value)
 {
-    std::vector<T>::const_iterator it = std::lower_bound(v.begin(), v.end(), value);
+    typename std::vector<T>::const_iterator it = std::lower_bound(v.begin(), v.end(), value);
 
     assert(it != v.end());
 
@@ -78,7 +79,7 @@
     const size_t xn = xs.size() - 1;
     const size_t yn = ys.size() - 1;
 
-    std::vector<std::vector<int> > map(xn, std::vector<int>(yn, true));
+    std::vector<std::vector<unsigned char> > map(xn, std::vector<unsigned char>(yn, 1));
 
     for (std::vector<rect>::const_iterator it = tapes.begin(); it != tapes.end(); ++it)
     {
@@ -87,9 +88,9 @@
         const size_t lower_yi = find(ys, it->bottom);
         const size_t upper_yi = find(ys, it->top);
 
-        REP(xi, lower_xi, upper_xi) REP(yi, lower_yi, upper_yi)
+        REP(xi, lower_xi, upper_xi)
         {
-            map[xi][yi] = false;
+            std::memset(&map[xi][lower_yi], 0, (upper_yi - lower_yi) * sizeof(unsigned char));
         }
     }

正整数のゲーデル数化？ (Nested Flatten)

ちょっと付け足した部分がエラーになってた orz

24c24
<     <xsl:if test="n&lt;=0">
---
>     <xsl:if test="$n&lt;=0">

マルバツゲーム (Nested Flatten)

判定おかしかったですね。修正しました。

79c79
<         for ($i = 0; $i < 2; $i++) {
---
>         for ($i = 0; $i < 3; $i++) {
92,95c92,95
<             ($this->field[0][0] == $player &&
<              $this->field[2][2] == $player) ||
<             ($this->field[0][2] == $player &&
<              $this->field[2][0] == $player)) {
---
>             (($this->field[0][0] == $player &&
>               $this->field[2][2] == $player) ||
>              ($this->field[0][2] == $player &&
>               $this->field[2][0] == $player))) {

リストの並び (Nested Flatten)

整数しかこないつもりでいました。一般の型に修正。

1
2
3

> data Z = NegInf | Finite Integer | PosInf deriving (Eq,Ord)
---
> data N a = NegInf | Finite a | PosInf deriving (Eq,Ord)

出力の一時停止と再開 (Nested Flatten)

threadを扱うときに変数の入り方がわかりにくかったですね。

q<return>すると resの中には'common-lisp-user::q と入力さ
れていました。こんなことあるんですね。

0a1,4
> (defpackage :dokaku179
>   (:use :common-lisp :sb-thread))
> (in-package :dokaku179)
> 
8c12,14
<     (lambda()(setf ,res (read *standard-input*)))))
---
>     (lambda()(progn
>            (in-package :dokaku179)
>            (setf ,res (read *standard-input*))))))

情報オリンピック2007年度国内本選問題4 (Nested Flatten)

いっそ、こっちの方が読みやすいかも

--- 4.cpp.new    Fri May 23 15:31:57 2008
+++ 4.cpp    Fri May 23 15:41:55 2008
@@ -9,9 +9,9 @@
 #define REP(i, b, e) for (size_t i = b; i < e; ++i)
 #define REPE(i, b, e) for (size_t i = b; i <= e; ++i)
 
-void fill(std::vector<long>& v, long value)
+void zero_fill(std::vector<long>& v)
 {
-    std::fill(v.begin(), v.end(), value);
+    std::fill(v.begin(), v.end(), 0);
 }
 
 int main()
@@ -32,11 +32,11 @@
 
     std::vector<std::vector<long> > slip(n + 3, std::vector<long>(max_x, -1)); // -1 means there is no stone
 
-    fill(slip[0], 0); // start shore (0 is dummy value)
+    zero_fill(slip[0]); // start shore (0 is dummy value)
 
-    fill(slip[n + 1], 0); // goal shore (0 is dummy value)
+    zero_fill(slip[n + 1]); // goal shore (0 is dummy value)
 
-    fill(slip[n + 2], 0); // goal shore (0 is dummy value)
+    zero_fill(slip[n + 2]); // goal shore (0 is dummy value)
 
     REPE(y, 1, n)
     {
@@ -72,7 +72,7 @@
         std::vector<std::vector<long> >(max_x,
             std::vector<long>(m + 1, std::numeric_limits<long>::max())));
 
-    dp[0] = std::vector<std::vector<long> >(max_x, std::vector<long>(m + 1, 0));
+    std::for_each(dp.front().begin(), dp.front().end(), zero_fill);
 
     REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
     {

情報ありがとうございます。こっちならうまくいきました。

see: 今のところswapに一時変数は渡せない

--- 4.cpp.new    Fri May 23 15:31:57 2008
+++ 4.cpp.new2    Fri May 23 15:32:13 2008
@@ -72,7 +72,8 @@
         std::vector<std::vector<long> >(max_x,
             std::vector<long>(m + 1, std::numeric_limits<long>::max())));
 
-    dp[0] = std::vector<std::vector<long> >(max_x, std::vector<long>(m + 1, 0));
+    std::vector<std::vector<long> >(max_x,
+        std::vector<long>(m + 1, 0)).swap(dp.front());
 
     REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
     {

g++でコンパイルが通らなかったので、修正。（理由は不明）

--- 4.cpp.old    Thu May 22 16:17:00 2008
+++ 4.cpp.new    Thu May 22 16:16:47 2008
@@ -72,9 +72,7 @@
         std::vector<std::vector<long> >(max_x,
             std::vector<long>(m + 1, std::numeric_limits<long>::max())));
 
-    dp.front().swap(
-        std::vector<std::vector<long> >(max_x,
-            std::vector<long>(m + 1, 0)));
+    dp[0] = std::vector<std::vector<long> >(max_x, std::vector<long>(m + 1, 0));
 
     REPE(y1, 0, n) REP(x1, 0, max_x) if (slip[y1][x1] >= 0) // source
     {

METHINKS IT IS A WEASEL (Nested Flatten)

本当にこれで高速化するか試してませんが・・・部分ソートというのがあるみたいなので、使ってみました。

--- main.cpp.old    Wed May 21 13:00:14 2008
+++ main.cpp.new    Wed May 21 19:04:41 2008
@@ -78,7 +78,7 @@
 
     for (size_t generation = 1; ; ++generation)
     {
-        std::sort(v.begin(), v.end());
+        std::partial_sort(v.begin(), v.begin() + count, v.end());
 
         v.erase(v.begin() + count, v.end());

マルバツゲーム：賢いプレイヤー (Nested Flatten)

バグがありました。いったい何を思ってそんなふうに書いてしまったのか、それでなぜそれっぽく動いていたのかまったく不思議です(^_^;)。以下、差分です。

6c6
< 全マス目 := (中央のマス, 隅のマス群, 縁のマス群) asOrderedCollection.
---
> 全マス目 := ({中央のマス}, 隅のマス群, 縁のマス群) asOrderedCollection.
51c51,52
<                         (敵の手 includesAnyOf: {隅のマス群 first: 2. 隅のマス群 last: 2})
---
>                         (敵の手 size = 2 and: [{隅のマス群 first: 2. 隅のマス群 last: 2}
>                                 anySatisfy: [:二隅 | (敵の手 copyWithoutAll: 二隅) isEmpty]])
58c59
<                                                 総和 + (敵のマス * 候補) sum]]]
---
>                                                 総和 + ((候補 - 敵のマス) * (候補 - 敵のマス)) sum]]]
76,77c77,78
< "=> {#賢い先手->{9774->#先手勝ち. 226->#引き分け}. 
<     #賢い後手->{7962->#後手勝ち. 2038->#引き分け}. 
---
> "=>  {#賢い先手->{9607->#先手勝ち. 393->#引き分け}.
>     #賢い後手->{8544->#後手勝ち. 1456->#引き分け}.

マルバツゲーム (Nested Flatten)

終了判定にバグ発見してしまいました。
ここを直して、100万回実行した結果以下のようになりました。
これでほぼ合っていそうです。

Result:
Player1 won: 582337
Player2 won: 290884
draw game  : 126779

15c15
<                       {new Pair(2,2), new Pair(1,1), new Pair(0,0)},
---
>                       {new Pair(0,2), new Pair(1,1), new Pair(2,0)},

1行ミスってました。コピペはいけませんね･･･。あらためて

player1 won:    5826
player2 won:    2857
draw :  1317

という感じです。

@@ -4,7 +4,7 @@
   protected val field = new Array[Array[char]](size,size)
   val len = size*size
   val lines = _stline((v,v2) => (v,v2))++_stline((v,v2) => (v2,v))++
-              List(((size-1).until(-1,-1)).map(v=>(v,v))) ++
+              List(((size-1).until(-1,-1)).map(v=> (v,(size-1-v)))) ++
               List((0 until size).map(v=>(v,v)))

   def _stline(f:(int,int) => Pair[int,int]) =

exp(pi * sqrt(n))が整数に近くなるnを探す (Nested Flatten)

このバグはPython2.5.2で修正されました。というわけでパッチです。

--- a.py    Thu Feb 28 02:32:31 2008
+++ a.py    Thu Feb 28 02:32:46 2008
@@ -1,10 +1,11 @@
 from decimal import *
-import itertools
+import itertools, sys
 
-def divmod(x, y): # workaround for python2.5 decimal mod bug.
-    div = x // y
-    mod = x - div * y
-    return div, mod
+if sys.version_info[:3] <= (2, 5, 1):
+    def divmod(x, y): # workaround for python2.5 decimal mod bug.
+        div = x // y
+        mod = x - div * y
+        return div, mod
 
 def decimal_exp(x):
     div, mod = divmod(x, Decimal("2.3025850929940456840179914546844"))

自分自身のファイル名を知る方法 (Nested Flatten)

間違い訂正（Perl 5.100ってなんだ）

1c1
< use 5.10;
---
> use 5.010;

DouKaku?

Language detail: diff

Unsolved challenges

codes

Index

Feed

Other

Link

Pathtraq