鍋あり谷あり このページをアンテナに追加 RSSフィード

1904 | 06 | 07 | 09 | 10 |
1906 | 08 |
2004 | 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 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 03 | 05 | 06 | 08 | 09 | 11 | 12 |
2009 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 12 |
2010 | 01 | 09 | 10 |
2011 | 01 | 02 | 03 | 05 | 08 | 12 |
2012 | 12 |
2013 | 03 | 04 | 05 | 07 | 08 | 09 |
2014 | 01 | 02 | 05 | 08 |
2015 | 05 |
2016 | 05 |
<< 2016/06 >>
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30


2016年 5月 1日 用もないのに原ノ町駅近辺に行ってきた このエントリーを含むブックマーク このエントリーのブックマークコメント

常磐線の果てに行ってみたかった。

切符を買ってから気づいたんだけど、私が行きたかった場所はどちらかと言うと 竜田駅 の方で、原ノ町駅は反対側だった。そんな日もある。

気にせず原ノ町駅 https://goo.gl/maps/Qmxyfd4fvMn

f:id:Nabetani:20160501110535j:image

へ。新幹線福島バス

何かがあることを期待していたわけでもなく、そこで人が普通に暮らしていることを自分の目で見たかったという感じ。

案の定、そこは普通田舎町だった。

f:id:Nabetani:20160501110713j:image

震災から5年もたっているので当たり前かもしれないけど、まだ普通田舎町になっていない地域もあるので実は当たり前ではない。

海に向かって歩いた。

バスで行きたかったんだけど、バスはなかった。

途中までは普通田舎町なんだけど、ある地点を超えると様子が変わった。

f:id:Nabetani:20160501110101j:image

右は田んぼなのかもしれないけど、左は整地中という感じ。

海まであと一歩のところまで歩いたけど、堤防工事中とのことで、

f:id:Nabetani:20160501104524j:image

海までは辿りつけなかった。残念。

駅に戻る途中、tonbo というケーキ屋さんでレアチーズケーキを頂いた。おいしかった。

通りすがりの雀。

f:id:Nabetani:20160501104525j:image

2015年 5月 5日

マイルの話

ふとマイルという長さについて知ろうと思い、 wikipedia( http://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%A4%E3%83%AB ) を見てみた。

すると。

イタリアマイル(ミリオ miglio)
古代は2.226キロメートル、伝統的には1.489キロメートル、現在は1キロメートル。

という驚くべき記載が。

潔い。

アメリカ・イギリスもこれぐらいの荒療治をしてくれたらいいのにと思ったり。

じゃあその、1マイル=1キロメートル世界での ヤード フィート インチ はどうなってるんだろうと思い、イタリア語版の wikipedia( http://it.wikipedia.org/wiki/Miglio_(unit%C3%A0_di_misura) )を見てみた。

ら。

現在のイタリアマイルについての記載は一切ない。

代わりに

Miglio nuovo nederlandese = 1 000 m

拙訳「新オランダマイル = 1000メートル

という記載がある。

なんだこれ。と思い、オランダ語wikipedia( http://nl.wikipedia.org/wiki/Mijl )に行ってみると、1000m であるマイルについての記載は一切ない。

どうなってんだこれ。

英語スペイン語フランス語wikipedia も見てみたけど、情報はなかった。

なんだろうなぁ。

2014年 8月 16日

[] 遅いソート

http://bugrammer.hateblo.jp/entry/2014/08/16/014212 ( バブルソートよりも非効率ソートアルゴリズムを探して ―― ストゥージソートスローソート ) を読んで。

ちゃんと終わるけどもっと遅いソートがあるので書いてみた。

たぶん名前がついていると思うんだけど、調べてないので名称不明。

こういう奴。

def try_all_sort(s)
  s.permutation(s.size){ |x|
    return x if x.each_cons(2).all?{ |a,b| a<=b }
  }
end

typical case では bogo sort と同じオーダー。

bogo sort と違って、worst case は有限。O((N+1)!)だと思う。

で。ベンチマーク

100要素を1000回なんて宇宙が消滅するまでに終わらないので、試したのはシャッフル済み10要素を10回。

手元で測って、30秒ぐらい。

一方、slowsort だと速すぎて測定不能。

bogo sort だと 54秒だった。まあ運次第だけど。

10要素で30秒なので、15要素なら4ヶ月、20要素なら60万年ぐらいかかる。

コンピュータがやる計算なのに、人間が紙に書いてソートするよりずっと遅い。

■ 8/17 追記

メモリ消費は、上記のソースでは O(N)。だと思う。

100要素1000回に要する時間は、普通の人がパッと読んで分かるような表現ができないぐらい長い。

10の148乗年ぐらい。

概ね、千無量大数高速化すると、千無量大数年かかるぐらい。百万倍ぐらいサバ読んでるけどいいでしょ?

メモリ消費は、数キロバイト〜数十キロバイト だと思う。

無量大数高速化というと無理難題のように思うかもしれないけど、普通の sort に書き換えれば、それ以上の高速化を実現できる。

2014年 5月 18日

どう書くの問題を作るときに考えること

塚さんの記事

http://d.hatena.ne.jp/torazuka/20140512/doukaku

を受けて。

正確なテストデータ / データの数

深く考えずに、40個ぐらいにしていることが多いんだけど、

コーナーケースが多そうなら多めに、コーナーケースが少なそうなら少なめにしてる。

仕様を網羅したいという希望はありつつも、べつに網羅できなくてもいいよね、とも思っている。

正確なテストデータ / データ作成方法

だいたい以下の順序で

  1. 典型的なケース。問題文中に例として挙げます。
  2. 典型的例外ケース。該当するものがなかったらとかそういうの。
  3. 典型的なケースをいくつか。
  4. コーナーケースを思いつく限り。
  5. 乱数

乱数」と、さらっと書いたけど、一様乱数でうまくいくわけではない。

たとえば「ポーカーの残り+」( http://nabetani.sakura.ne.jp/hena/ord10pokarest/ )。

この問題の場合は(あんまりおぼえてないけど)全部の手についてのデータをまあまあ均等に出している。

解き方が複数ある問題にする

この要件が大問題で、ここに注力するとすぐに難易度が上がってしまう。

で。

『「自分では思いつかないけれど、誰かが別の方法で解いてくれるかもしれない」などと勝手に期待』することは結構あって、解き方がひとつしか思いついていない場合でも、いやこれはこの経路以外にありそうだという感触があればそれでよしとする場合もある。

もちろん複数の経路を実装しておきたいとは思うんだけど。

特定プログラミング言語配慮する

だいたい ruby に対する嫌がらせをしたいんだけど、いくら考えても他の言語に対する嫌がらせしかならない。

C と Java特に C を優遇したいと考えていて、入力データを固定長にしたりしている。

視覚的な演出になる図表を入れる

どちらかというと、できれば図を入れたくないと思ってる。

図を書くコードを書くのが面倒なので。

図が入っているのは、図を入れないと仕様が明確にならないと思ったときだと思う。

過去に出した図で一番気に入ってるのはやっぱり

折って切る( http://nabetani.sakura.ne.jp/hena/ord17foldcut/ )のアニメーション。

問題としてもすごく気に入ってる。

未見の方は是非解くことをおすすめする。

それ以外

どれ以外だと

あたりのことを考えてるって、前にどっかに書いたような。

参加者想像して問題を作る

これはあんまり具体的にどう問題を作るかという話ではなく。

文字通り、参加者想像する。

☓☓さんはこの問題を見たらどういう表情をするだろうか。

◯◯さんはこの問題にどう取り組むだろうか。

とか、そういうこと。

CodeIQ と違って、問題を解く人々の集う場があるので(問題だけではなく)その場を面白くしたいと思ってる。

どうしたら面白くなるのか全然からないんだけど、たぶん面白くするための手段として、想像しながら問題を作っている。

2014年 2月 23日

[]久々に 剰余なしで FizzBuzz

はるか昔に書いた

http://d.hatena.ne.jp/Nabetani/20070510/p1

が、ruby 2.1.0 では動かないようなので、書きなおした。

def f(name,n)
  Fiber.new do
    loop do
      (n-1).times{ Fiber.yield "" }
      Fiber.yield name
    end
  end
end

def fb(sup, *x)
  s=x.map{|name,n| f(name,n)}
  1.upto(sup) do |n|
    yield( (r=s.map{|x|x.resume}.join).empty? ? n : r )
  end
end

fb( 100, [ 'Fizz', 3], [ 'Buzz', 5 ] ) do |s|
  puts s
end

Generator がなくなって Fiber になったらしいので、それに関する対応

ほかにも多少変更したけど。

527369