DouKaku? Language detail: diff

バグってました orz. 正しくは1秒以内で350語前後でした。

なお、グラフ理論でいうと、任意のグラフから最大の準オイラーグラフとなる部分グラフを抽出するという問題になると思います。

--- Shiritori_old.java  2009-07-27 14:44:42.167161400 +0900
+++ Shiritori_new.java  2009-07-27 14:59:44.602959300 +0900
@@ -46,2 +46,7 @@

+            if(!head.hasCapacity()) {
+                flows.remove(head);
+                break;
+            }
+
             LinkedList<String> path = new LinkedList<String>();
@@ -50,3 +55,3 @@
             while (head.hasCapacity() || tail.hasCapacity()) {
-                if (!head.inEdges.isEmpty()) {
+                if (head.hasCapacity()) {
                     String newHead = popInEdge(head);
@@ -55,5 +60,6 @@
                     head = nodes.get(headChar(newHead));
+                    head.outEdges.remove(newHead);
                 }

-                if (!tail.outEdges.isEmpty()) {
+                if (tail.hasCapacity()) {
                     String newTail = popOutEdge(tail);
@@ -62,2 +68,3 @@
                     tail = nodes.get(tailChar(newTail));
+                    tail.inEdges.remove(newTail);
                 }

ケブンッリジ関数 (Nested Flatten)

文字が1文字の場合のバグを修正。

    foreach($problem as $word){
+        if (mb_strlen($word) > 1){
            $start = mb_substr($word, 0, 1);
            $end = mb_substr($word, mb_strlen($word) - 1, 1);
            $mid = mb_str_split(mb_substr($word, 1, mb_strlen($word) - 2));
            shuffle($mid);
            print $start.join("",$mid).$end." ";
+        }
+        else {
+            print $word;
+        }
    }

ソートするコードの生成 (Nested Flatten)

次の改造を行いました。

type_str_tにムーブコンストラクタ・代入演算子の導入
vectorをconst参照渡しにした（Ovenでエラーになるので元のコードでは値渡しにしていたが、const_singleの導入で回避できることが判明）

元の投稿はVC++9でしたが、1番目の修正の結果、今度はVC++ 10 βを使っています。gensort 9の結果が3回の平均で23.756秒、gensort 10の結果が256.315秒（1回だけ）となりました。アルゴリズム自体が指数的に増加するので焼け石に水だとは思いますが一応。なお、gensortが生成するコードも変化ありません。

*** go.cpp    Sat Jun 27 01:23:14 2009
--- g.cpp    Sat Jun 27 01:25:16 2009
***************
*** 55,60 ****
--- 55,77 ----
              os << '\n' << indent(n) << tail;
          }
      }
+ 
+     type_str_t() {}
+     type_str_t(const type_str_t& y)
+         : head(y.head), tail(y.tail), child(y.child) {}
+     type_str_t(type_str_t&& y)
+         : head(std::move(y.head)), tail(std::move(y.tail)), child(std::move(y.child)) {}
+     type_str_t& operator =(const type_str_t& y)
+     {
+         return operator =(std::move(type_str_t(y)));
+     }
+     type_str_t& operator =(type_str_t&& y)
+     {
+         head = std::move(y.head);
+         tail = std::move(y.tail);
+         child = std::move(y.child);
+         return *this;
+     }
  };
  
  type_str_t vecr(const std::vector<char>& c)
***************
*** 71,83 ****
      return t;
  }
  
! type_str_t gensort_impl2(std::vector<char> xs, std::vector<char> ss);
! type_str_t gensort_impl2_rec(char x, std::vector<char> xs, std::vector<char> ss, std::vector<char> rs)
  {
      if (ss.empty())
      {
          return gensort_impl2(xs,
!             ov::single(x)
               | ov::jointed(rs)
               | ov::copied);
      }
--- 88,107 ----
      return t;
  }
  
! template<typename T>
! inline boost::iterator_range<T const*>
! const_single(T const& x)
! {
!     return boost::iterator_range<T const*>(&x, &x + 1);
! }
! 
! type_str_t gensort_impl2(std::vector<char> const& xs, std::vector<char> const& ss);
! type_str_t gensort_impl2_rec(char x, std::vector<char> const& xs, std::vector<char> const& ss, std::vector<char> const& rs)
  {
      if (ss.empty())
      {
          return gensort_impl2(xs,
!             const_single(x)
               | ov::jointed(rs)
               | ov::copied);
      }
***************
*** 100,113 ****
              ss
              | ov::taken(ss.size() - 1)
              | ov::copied,
!             ov::single(y)
              | ov::jointed(rs)
              | ov::copied));
          return ts;
      }
  }
  
! type_str_t gensort_impl2(std::vector<char> xs, std::vector<char> ss)
  {
      if (xs.empty())
      {
--- 124,137 ----
              ss
              | ov::taken(ss.size() - 1)
              | ov::copied,
!             const_single(y)
              | ov::jointed(rs)
              | ov::copied));
          return ts;
      }
  }
  
! type_str_t gensort_impl2(std::vector<char> const& xs, std::vector<char> const& ss)
  {
      if (xs.empty())
      {

ケブンッリジ関数 (Nested Flatten)

alphanumericp な文字が一つもない文字列を渡したときにエラーになってました。

@@ -6,7 +6,7 @@
                  (char text (+ from (random d))))))))
 
 (defun cambridge (text)
-  (loop for from = (position-if #'alphanumericp text)
+  (loop for from = (or (position-if #'alphanumericp text) (return))
                  then (or (position-if #'alphanumericp text :start to)
                           (length text))
     for to = (or (position-if-not #'alphanumericp text :start from)

テキスト行の正規化 (Nested Flatten)

>元の文字列の最後は改行です。
これを忘れてた。

#coding: utf-8

def padding(inputStr, paddingChar = " "):
    maxNum = len(max(inputStr.split("\n"), key=(lambda(x):len(x))))
    outputStr = ""
-   for linedata in inputStr.split("\n"):
+   for linedata in inputStr.split("\n")[:-1]:
        outputStr += linedata + paddingChar * (maxNum - len(linedata)) + "\n"
    return outputStr

すみません。 ↓のようなつもりでした。

(define (pad lines ch)
  (let iter ((ls (string-split lines "\n"))
             (maxlen 0)
-            (acc 0))
+            (acc '()))

tailの実装 (Nested Flatten)

ちょうど気を抜いたところでバグってました．うーん．

--- tail.c.orig 2008-12-15 21:28:50.000000000 +0900
+++ tail.c      2008-12-16 00:39:44.000000000 +0900
@@ -37,7 +37,7 @@
         if ((len_r = read(fd, buf, sizeof(buf))) == -1)
             handle_error("read");
         for (buf_p = buf; (buf_p - buf) < len_r; buf_p += len_w)
-            if ((len_w = write(1, buf, len_r)) == -1)
+            if ((len_w = write(1, buf_p, len_r - (buf_p - buf))) == -1)
                 handle_error("write");
     }
 }

正しい文(クイズ) (Nested Flatten)

やっぱりループを無駄に回しすぎていた。
しかし、それでも時間がかかる。

4c4
< #define TRY_MAX  (128 + 16)
---
> #define TRY_MAX   32

日本語メールのエンコード (Nested Flatten)

投稿された内容を後から見て、エンコードされていないことに気づきました。

60c60
< { header; body; } < $templ | nkf -Lw
---
> { header; body; } < $templ | nkf -Lw -m0

'('と')'の対応 (Nested Flatten)

なるほど。修正。

8c8
<     while LPAR *p RPAR {
---
>     while LPAR *p && cnt >= 0 RPAR {

起動オプションの解析 (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)

DouKaku?

Language detail: diff

Unsolved challenges

codes

Index

Feed

Other

Link

Pathtraq