塗らずに蹂躙する〜どう書くE10の問題から

今月の初めの土曜日、秋葉原/神田開催どう書くの第10回が開催されました。

• オフラインリアルタイムどう書くE10 - 横浜へなちょこプログラミング勉強会 | Doorkeeper

問題とみなさんの回答へのリンクはこちらから。

• mtsmfm blog - オフラインリアルタイムどう書く E10 の問題 - 塗って繋ぐ
• オフラインリアルタイムどう書くE10 の問題 - Qiita

当日の時間内にテストにパスするコードを書けなかっただけでなく、理屈の上ではパスするものの到底時間内に実行が終わらないアイディアしか思い浮かばず。惨敗しました。

セルを塗り分けるには隣接したセルを調べて同じ色であれば同じ番号をふるということが必要になります、素朴なアイディアでは。しかしここが落とし穴。セルの数は 3^{入力の文字列のながさ×2} になるため、もっとも長い文字列の入力ではセルの数が 4,782,969 になり、隣の隣の隣の…と調べに行ったままなかなか帰ってこないというありさまでした。加えて、再帰を使うと簡単に書けるのですが帰ってくる前にメモリが尽きるという様相に。

で。作戦変更。端からセルを一つ一つ走査する方法を 3 日ぐらいかけて考えていました。

基本的な考え方は、左から右へ上から下へセルを一つ一つ調べ、左か上にすでに番号のふられたセルがあればその番号と同じ番号をふり、そのようなセルがなければ新しい番号をふる、すべてのセルに番号がついたら、番号の数が塗り分けの数になる、というもの。

この方法を単純に適用するだけでは、たとえば上の方では別の領域だったけれども下までたどったら繋がっていた、という場合にうまくいきません。そこで繋がっていた場合は一方はもう一方の別名だった、ということを記録するようにします。
番号は 1 から順番に大きくなる、先にふられた番号の方を有効とする、というルールに決めておくと、小さい方を実際の値、大きい方を別名と定義できます。すべてのセルに番号がついたら、記録しておいた別名を実際の番号にふりなおすことで繋がったセルには同じ番号がふられた状態になります。

そうやって解いたのがこちら。

• オフラインリアルタイムどう書く E10 「塗って繋ぐ」をRubyで塗る - Qiita

私のマシンで 10 秒程度ですべてのテストにパスするようになりました。

しかし実は領域の数だけを知りたいのであれば番号をふりなおす必要なくて、ふられた番号の中から別名として登録されている番号を引いて残る番号の、その個数が領域の数と同じになります。さらに記憶している番号に重複がなければ、全体の番号の個数から別名の個数を引いても答えがえられます。すると別名と実際の値の表を用意する必要もなく、単に別名だった番号を記録しておけばよいことになります。

そのアイディアにもとづいて書き直したのがこちら。実行時間はさらに 3 分の 1 の 3〜4 秒まで短縮することができました。

require 'benchmark'
require 'set'

PATTERNS = {
  'X' => [[1, 0], [0, 1], [2, 1], [1, 2]],
  'O' => [[0, 0], [2, 0], [1, 1], [0, 2], [2, 2]]
}

def filled_area_count(size, blocks)
  sentinel_index = size ** 2
  board = Array.new(sentinel_index)
  blocks.each {|x, y| board[y * size + x] = sentinel_index }

  alias_table = Set.new

  next_index = 0
  sentinel_index.times do |i|
    next if board[i]
    left_index  = (i % size == 0) ? sentinel_index : board[i - 1]
    upper_index = (i < size) ? sentinel_index : board[i - size]

    if (left_index == sentinel_index) && (upper_index == sentinel_index)
      board[i] = next_index
      next_index += 1
    elsif left_index == upper_index
      board[i] = left_index
    else
      actual_index, alias_index = (left_index < upper_index) ? [left_index, upper_index] : [upper_index, left_index]
      alias_table << alias_index
      board[i] = actual_index
    end
  end

  alias_table.delete(sentinel_index)
  next_index - alias_table.size
end

def solve(input)
  blacks = input.chars.reduce([[0, 0]]) {|blacks, c|
    blacks.map {|cell|
      PATTERNS[c].map {|x, y| [cell[0] * 3 + x, cell[1] * 3 + y] }
    }.flatten(1)
  }

  filled_area_count(3 ** input.length, blacks).to_s
end

def test(input, expected)
  actual = solve(input)
  if actual == expected
    print "\x1b[1m\x1b[32m.\x1b[0m"
  else
    puts(<<~EOS)
      \x1b[1m\x1b[31m
      input:    #{input}
      expected: #{expected}
      actual:   #{actual}\x1b[0m
    EOS
  end
end

def test_all(data)
  data.each do |line|
    input, expected = line.split
    test(input, expected)
  end

  puts
end

time = Benchmark.realtime { test_all(DATA) }

puts format('%8.3f sec', time)

__END__
X 5
O 4
XX 5
OX 10
XO 9
XOO 17
OXX 21
OXO 18
OOOX 130
OXXO 29
XXOX 81
XOXXO 89
OOOOX 630
OXOOO 66
OXOXOX 2001
OXOXXO 417
OXXOXX 1601
XXXOXOO 345
OOOOOXO 3258
OXXOXXX 6401

いつか読むはずっと読まない：神・銃

短編 “The God-Gun” の翻訳「神・銃」を「ゴッド・ガン」と改め、それを表題作とした短編集。

ベイリーの本は何冊か読んでいるはずなのですが、からっきし内容を覚えていないという体たらく。新訳版となった「カエアンの聖衣」を新鮮な気持ちで読めたのでありがたいということもできなくはないのですが。

「神・銃」「ゴッド・ガン」という字面を見たときに思い出すのが「禅〈ゼン・ガン〉銃」（原題 “The Zen Gun”）ですが、これもまた物の見事に内容を思い出せない。
そのうち読み返そうと思うのですが、書籍の山から本書を探し出して引っ張り出すのが、過去の記憶を引っ張り出すのと同じぐらい大変そうというのが目下の課題。

ゴッド・ガン (ハヤカワ文庫 SF ヘ)

禅銃(ゼンガン) (ハヤカワ文庫SF ヘ 3-1) (ハヤカワ文庫 SF (579))

FizzBuzzを宣言的に書く、宣言できない場合は宣言っぽく書く

プログラミング Elixir を読んでいます。

プログラミングElixir

Elixir

プログラミング Elixir の第5章で FizzBuzz を書く練習問題が出てきます。

# $ elixir fizz_buzz.exs

fizzBuzz3 = fn
  0, 0, _ -> "FizzBuzz"
  0, _, _ -> "Fizz"
  _, 0, _ -> "Buzz"
  _, _, n -> "#{n}"
end

fizzBuzz = fn n -> fizzBuzz3.(rem(n, 3), rem(n, 5), n) end

fizzBuzzSeries = fn first, last -> first..last |> Enum.map(fizzBuzz) end

fizzBuzzSeries.(1, 20) |> Enum.join("\n") |> IO.puts

Erlang

VM は同じでもシンタクスが違うので見た目が結構違って見えます。

% $ erlc fizz_buzz.erl
% $ erl -run fizz_buzz main

-module(fizz_buzz).
-export([main/0]).

fizz_buzz(0, 0, _) -> "FizzBuzz";
fizz_buzz(0, _, _) -> "Fizz";
fizz_buzz(_, 0, _) -> "Buzz";
fizz_buzz(_, _, N) -> integer_to_list(N).

fizz_buzz(N) -> fizz_buzz(N rem 3, N rem 5, N).

fizz_buzz_series(First, Last) -> [fizz_buzz(N) || N <- lists:seq(First, Last)].

main() ->
  lists:map(fun(S) -> io:format("~s~n", [S]) end, fizz_buzz_series(1, 20)),
  erlang:halt(0).

Haskell

Haskell で書いてもほぼ同じ。

-- $ ghc --make fizz_buzz
-- $ ./fizz_buzz

fizzBuzz3 0 0 _ = "FizzBuzz"
fizzBuzz3 0 _ _ = "Fizz"
fizzBuzz3 _ 0 _ = "Buzz"
fizzBuzz3 _ _ n = show n

fizzBuzz n = fizzBuzz3 (n `mod` 3) (n `mod` 5) n

fizzBuzzeSeries = [ fizzBuzz n | n <- [1..20]]

main = putStrLn $ unlines fizzBuzzeSeries

Prolog

関数でなく述語で表現するのでまた違った印象。

% $ gprolog --consult-file fizz_buzz.pro --entry-goal main

fizz_buzz(0, 0, _, "FizzBuzz") :- !.
fizz_buzz(0, _, _, "Fizz") :- !.
fizz_buzz(_, 0, _, "Buzz") :- !.
fizz_buzz(_, _, N, S) :- number_codes(N, S), !.

fizz_buzz(N, S) :- N3 is N rem 3, N5 is N rem 5, fizz_buzz(N3, N5, N, S).

fizz_buzz_series(First, Last, FBS) :- findall(FB, (between(First, Last, N), fizz_buzz(N, FB)), FBS).

puts(S) :- format("~s~n", [S]).

main :- fizz_buzz_series(1, 20, FBS), maplist(puts, FBS), halt.

Ruby

Ruby はメソッドのレベルでのパタンマッチの機能が今はないので、case を使ってそれっぽく書いてみる。

# $ ruby fizz_buzz.rb

def fizz_buzz3(n3, n5, n)
  case [n3, n5, n]
  when [0,  0,  n] then 'FizzBuzz'
  when [0,  n5, n] then 'Fizz'
  when [n3, 0,  n] then 'Buzz'
  else                "#{n}"
  end
end

def fizz_buzz(n)
  fizz_buzz3(n % 3, n % 5, n)
end

def fizz_buzz_series(first, last)
  (first..last).map {|n| fizz_buzz(n) }
end

puts fizz_buzz_series(1, 20).join("\n")

C++ Template Metaprograming

パタンマッチングは、C++ にはないけれども C++ Template では使える。コード量が多いのが難点。

// $ g++ --std=c++11 -o fizz_buzz fizz_buzz.cpp
// $ ./fizz_buzz

#include <string>
#include <iostream>
#include <algorithm>

template<int N1, int N2, int N3> struct FizzBuzz3 { static const std::string value; };
template<int N3>                 struct FizzBuzz3<0, 0, N3> { static const std::string value; };
template<int N2, int N3>         struct FizzBuzz3<0, N2, N3> { static const std::string value; };
template<int N1, int N3>         struct FizzBuzz3<N1, 0, N3> { static const std::string value; };

template<int N1, int N2, int N3> const std::string FizzBuzz3<N1, N2, N3>::value = std::to_string(N3);
template<int N3>                 const std::string FizzBuzz3<0, 0, N3>::value = "FizzBuzz";
template<int N2, int N3>         const std::string FizzBuzz3<0, N2, N3>::value = "Fizz";
template<int N1, int N3>         const std::string FizzBuzz3<N1, 0, N3>::value = "Buzz";

template<int N> struct FizzBuzz { static const std::string value; };

template<int N> const std::string FizzBuzz<N>::value = FizzBuzz3<N % 3, N % 5, N>::value;

struct Nil;

template<template<int> class T, int First, int Last>
struct Range
{
    typedef T<First>                  Head;
    typedef Range<T, First + 1, Last> Tail;
};

template<template<int> class T, int Last>
struct Range<T, Last, Last>
{
    typedef T<Last> Head;
    typedef Nil     Tail;
};

template<int First, int Last>
using FizzBuzzSeries = Range<FizzBuzz, First, Last>;

template<typename R>
void puts_range()
{
    std::cout << R::Head::value << std::endl;
    puts_range<typename R::Tail>();
}

template<> void puts_range<Nil>() {};

int main(int, char* [])
{
    puts_range<FizzBuzzSeries<1, 20> >();

    return 0;
}

いつか読むはずっと読まない：バイク乗りがバイクになる（なりません）

一年半ほど前からクロスバイクに乗るようになりました。十ン年まともに運動などしたことがなかった人間が面白いぐらいにのめり込んでいます。

以前だったらアンテナにさえかからなかっただろう本書、今は描写の一つ一つに反応してしまっています。

追い風ライダー (徳間文庫)

Prolog が解くに適した問題がある

Prolog でコードをたびたび書いてはいますが、実用的なプログラムを Prolog で書けたためしがないというのが正直なところです。使い所がつかめていないのがその原因。

今もまだつかめているわけではないのですが、Prolog ならば自然に表現できて簡単に解ける例に遭遇して、そのような問題に適用すればよいのだということに気づかされました。残る課題はそのような問題であることを見極める自身の技量なわけですが。

矩形を見つける問題

実例として見つけた問題というのが、「どう書く」で出題された中にある矩形を求める部分。

• mtsmfm blog - オフラインリアルタイムどう書く E08 の問題 - 白黒陣取りゲーム

XY平面上にある複数の点のうち、矩形の頂点の位置なる 4 点 {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} を見つけるというもの。

Prolog で愚直に書いた

実際に矩形探しをさせてみます。x, y とも 10〜40 の値からなり重複しない点 200 個を用意して実験。

points([
  [18, 34], [32, 14], [21, 23], [24, 29], [37, 20],   [40, 28], [16, 30], [13, 33], [40, 37], [28, 23],
  [30, 38], [23, 37], [29, 20], [34, 14], [25, 26],   [12, 27], [10, 19], [30, 18], [13, 26], [18, 13],
  [10, 32], [13, 16], [15, 19], [17, 14], [38, 30],   [36, 22], [22, 38], [18, 22], [29, 12], [17, 36],
  [20, 25], [27, 21], [21, 37], [33, 14], [28, 15],   [15, 20], [37, 31], [37, 27], [20, 27], [24, 12],
  [18, 21], [32, 19], [33, 19], [27, 18], [32, 39],   [10, 36], [37, 19], [28, 16], [32, 32], [31, 12],
  [36, 14], [19, 33], [15, 28], [35, 23], [27, 17],   [26, 27], [22, 34], [24, 18], [13, 12], [31, 30],
  [28, 14], [24, 31], [31, 25], [33, 23], [29, 16],   [20, 35], [13, 35], [30, 40], [36, 25], [35, 25],
  [11, 19], [26, 17], [37, 28], [10, 25], [20, 22],   [35, 31], [20, 17], [31, 32], [33, 33], [35, 40],
  [37, 22], [39, 40], [31, 21], [38, 29], [17, 34],   [38, 13], [35, 24], [21, 38], [24, 39], [29, 30],
  [35, 22], [25, 37], [14, 15], [13, 18], [17, 30],   [24, 30], [12, 23], [10, 21], [33, 21], [13, 21],
  [32, 28], [26, 31], [27, 31], [23, 11], [14, 21],   [33, 34], [12, 28], [30, 16], [12, 18], [28, 25],
  [23, 36], [10, 35], [27, 36], [15, 17], [37, 10],   [37, 15], [24, 36], [26, 10], [11, 11], [23, 23],
  [24, 14], [13, 10], [37, 24], [32, 30], [14, 26],   [24, 25], [29, 39], [26, 18], [13, 20], [24, 28],
  [11, 22], [16, 16], [27, 35], [16, 14], [15, 12],   [17, 28], [25, 19], [33, 16], [24, 27], [32, 20],
  [16, 18], [19, 17], [39, 12], [18, 27], [27, 15],   [15, 27], [20, 15], [12, 20], [15, 16], [37, 33],
  [33, 20], [12, 33], [16, 10], [22, 37], [24, 15],   [13, 38], [37, 25], [17, 12], [18, 35], [29, 27],
  [29, 24], [32, 13], [13, 31], [16, 39], [20, 14],   [32, 38], [25, 17], [35, 15], [28, 21], [23, 39],
  [34, 24], [17, 26], [32, 10], [33, 28], [13, 24],   [29, 29], [28, 17], [14, 39], [20, 18], [13, 27],
  [40, 20], [11, 14], [22, 18], [28, 13], [32, 12],   [37, 40], [11, 37], [25, 35], [11, 31], [18, 16],
  [19, 24], [29, 37], [34, 31], [26, 19], [34, 11],   [37, 29], [20, 37], [24, 38], [35, 32], [30, 26]
]).

rect(X1, Y1, X2, Y2) :-
  points(PS),
  member([X1, Y1], PS),
  member([X1, Y2], PS),
  member([X2, Y1], PS),
  member([X2, Y2], PS),
  X1 < X2,
  Y1 < Y2.

rects(RS) :-
  findall([[X1, Y1], [X1, Y2], [X2, Y1], [X2, Y2]], rect(X1, Y1, X2, Y2), RS).

main :-
  rects(RS),
  length(RS, L),
  format("~p~n~d~n", [RS, L]).

実行。

$ time gprolog --consult-file rect.pro --entry-goal 'main, halt'
[[[32,14],[32,19],[33,14],[33,19]], ... (略)  ... ,[[24,38],[24,39],[32,38],[32,39]]]
450

real    0m0.351s
user    0m0.322s
sys     0m0.023s

すぐに答えが表示されたのには、正直驚きました。

Ruby で愚直に書く

任意の 4 点を取得して、矩形の頂点になるものを選べばよいというのなら、combination で 4 点を選び条件に合うものを選べばよいだろうと、愚直に書き直したものです。
200 個の点は同じ値です。

def points
  [
    [18, 34], [32, 14], [21, 23], [24, 29], [37, 20],   [40, 28], [16, 30], [13, 33], [40, 37], [28, 23],
    [30, 38], [23, 37], [29, 20], [34, 14], [25, 26],   [12, 27], [10, 19], [30, 18], [13, 26], [18, 13],
    [10, 32], [13, 16], [15, 19], [17, 14], [38, 30],   [36, 22], [22, 38], [18, 22], [29, 12], [17, 36],
    [20, 25], [27, 21], [21, 37], [33, 14], [28, 15],   [15, 20], [37, 31], [37, 27], [20, 27], [24, 12],
    [18, 21], [32, 19], [33, 19], [27, 18], [32, 39],   [10, 36], [37, 19], [28, 16], [32, 32], [31, 12],
    [36, 14], [19, 33], [15, 28], [35, 23], [27, 17],   [26, 27], [22, 34], [24, 18], [13, 12], [31, 30],
    [28, 14], [24, 31], [31, 25], [33, 23], [29, 16],   [20, 35], [13, 35], [30, 40], [36, 25], [35, 25],
    [11, 19], [26, 17], [37, 28], [10, 25], [20, 22],   [35, 31], [20, 17], [31, 32], [33, 33], [35, 40],
    [37, 22], [39, 40], [31, 21], [38, 29], [17, 34],   [38, 13], [35, 24], [21, 38], [24, 39], [29, 30],
    [35, 22], [25, 37], [14, 15], [13, 18], [17, 30],   [24, 30], [12, 23], [10, 21], [33, 21], [13, 21],
    [32, 28], [26, 31], [27, 31], [23, 11], [14, 21],   [33, 34], [12, 28], [30, 16], [12, 18], [28, 25],
    [23, 36], [10, 35], [27, 36], [15, 17], [37, 10],   [37, 15], [24, 36], [26, 10], [11, 11], [23, 23],
    [24, 14], [13, 10], [37, 24], [32, 30], [14, 26],   [24, 25], [29, 39], [26, 18], [13, 20], [24, 28],
    [11, 22], [16, 16], [27, 35], [16, 14], [15, 12],   [17, 28], [25, 19], [33, 16], [24, 27], [32, 20],
    [16, 18], [19, 17], [39, 12], [18, 27], [27, 15],   [15, 27], [20, 15], [12, 20], [15, 16], [37, 33],
    [33, 20], [12, 33], [16, 10], [22, 37], [24, 15],   [13, 38], [37, 25], [17, 12], [18, 35], [29, 27],
    [29, 24], [32, 13], [13, 31], [16, 39], [20, 14],   [32, 38], [25, 17], [35, 15], [28, 21], [23, 39],
    [34, 24], [17, 26], [32, 10], [33, 28], [13, 24],   [29, 29], [28, 17], [14, 39], [20, 18], [13, 27],
    [40, 20], [11, 14], [22, 18], [28, 13], [32, 12],   [37, 40], [11, 37], [25, 35], [11, 31], [18, 16],
    [19, 24], [29, 37], [34, 31], [26, 19], [34, 11],   [37, 29], [20, 37], [24, 38], [35, 32], [30, 26]
  ]
end

def rects
  points.sort.combination(4).select {|p1, p2, p3, p4|
    p1[0] == p2[0] && p1[1] == p3[1] && p3[0] == p4[0] && p2[1] == p4[1]
  }
end

rs = rects
puts rs.to_s
puts rs.size

実行。

$ time ruby rect1.rb
[[[10, 19], [10, 21], [33, 19], [33, 21]], ... (略) ... , [[37, 20], [37, 28], [40, 20], [40, 28]]]
450

real    0m22.360s
user    0m21.820s
sys     0m0.187s

それほど速くはないだろうと思いつつも、これほど数字になるとは思っていなかったので結構驚きでした。

Ruby で工夫して書く

当然、工夫すれば速くなります。

def points
  [
    # 上記と同じなので省略
  ]
end

def rects
  points.group_by {|_, y| y }
        .map {|y, ps| [y, ps.map(&:first).sort] }
        .combination(2)
        .map {|(y1, xs1), (y2, xs2)|
    (xs1 & xs2).combination(2).map {|x1, x2|
      [[x1, y1], [x1, y2], [x2, y1], [x2, y2]]
    }
  }.reject(&:empty?).flatten(1)
end

rs = rects
puts rs.to_s
puts rs.size

実行。

$ time ruby rect2.rb 
[[[17, 34], [17, 14], [33, 34], [33, 14]], ... (略) ... , [[13, 24], [13, 10], [37, 24], [37, 10]]]
450

real	0m0.121s
user	0m0.074s
sys	0m0.041s

ずいぶん速くなります。しかし Prolog で愚直に書いた場合もこれの数倍程度の時間しかかからないということは、やはり驚きです。

いつか読むはずっと読まない：付き従う正義、付き従う剣、付き従う慈

2冊目の中間、ちょっど真ん中あたりを読んでいます。半分まで読み進めてみても「異質な感じ」が終わりません。
正直最初のうちは得体の知れない感じが苦痛に感じる時もありましたが、進むにつれその感じにのめり込んでいることに気がつかされます。

叛逆航路 (創元SF文庫)

亡霊星域 (創元SF文庫)

星群艦隊 (創元SF文庫)

Fiddle を掻き鳴らしてみる

• library fiddle (Ruby 2.3.0)

*.dllや*.soなど、ダイナミックリンクライブラリを扱うためのライブラリです。

Ruby は痒い所に手が届く便利な言語だと知ってはいましたが、こんなに便利になっているとは思いませんでした。

と、いうわけで。

Fibonacci Number

まず。適当な .so ファイルを用意します。

// libfib.cpp

#include <map>

namespace
{

std::map<int, int> memo;

}

extern "C"
{

int fibonacci_number(int n)
{
    if(n < 1)
    {
        return 0;
    }
    else if(n <= 2)
    {
        return 1;
    }
    else
    {
        if(memo.find(n) == memo.end())
        {
            memo[n] = fibonacci_number(n - 1) + fibonacci_number(n - 2);
        }
        return memo[n];
    }
}

}

.so ファイルの生成。オプションは環境に合わせて指定してください。私は El Capitan 。

$ g++ --std=c++11 -dynamiclib -o libfib.so libfib.cpp

次に。ライブラリを呼び出すモジュールを作成。extern に続いて文字列で C 言語の関数の定義をそのまま書けば済んでしまうとか、予想外の簡単さ。

# fibonacci.rb

require 'fiddle/import'

module Fibonacci
  extend Fiddle::Importer
  dlload './libfib.so'

  extern 'int fibonacci_number(int n)'
end

サンプル用意。

# sample.rb

require './fibonacci'

puts Fibonacci.fibonacci_number(10)
puts Fibonacci.fibonacci_number(20)
puts Fibonacci.fibonacci_number(30)
puts Fibonacci.fibonacci_number(40)

実行。

$ ruby sample.rb 
55
6765
832040
102334155

簡単すぎる。

Fibonacci Series

配列を扱うときは Array#pack, Array#unpack を使って文字列（バイト列）を経由して扱う模様。

配列を扱う関数を追加。

// $ g++ --std=c++11 -dynamiclib -o libfib.so libfib.cpp

#include <map>

namespace
{

std::map<int, int> memo;

}

extern "C"
{

int fibonacci_number(int n)
{
    // 省略
}

void fibonacci_series(int n, int* s)
{
    for(int i = 1; i <= n; ++i)
    {
        s[i - 1] = fibonacci_number(i);
    }
}

}

同じ要領で .so ファイルを作成。

定義を追加。

# fibonacci.rb

require 'fiddle/import'

module Fibonacci
  extend Fiddle::Importer
  dlload './libfib.so'

  extern 'int fibonacci_number(int n)'
  extern 'void fibonacci_series(int n, int* s)'
end

呼び出し。

# sample2.rb

require './fibonacci'

s = [0].pack('i') * 10            # int 型のサイズのバイト列を 10 並べたものを用意
Fibonacci.fibonacci_series(10, s) # 関数呼び出し
puts s.unpack('i' * 10)           # int 型の値 10 個に戻す

実行。

$ ruby sample2.rb 
1
1
2
3
5
8
13
21
34
55

簡単すぎる。

いつか聴くはずっと聴かない：古楽器楽団「タブラトゥーラ」

フィドルといえば、思い出すのはタブラトゥーラ。

（ダウランドアンドカンパニイ 公式サイトより）

これがフィドル。

（同サイトより）

CD 購入は こちら から。サンプルも聴けます。

Retriable gem の使い方のめも

• GitHub - kamui/retriable: Retriable is an simple DSL to retry failed code blocks with randomized exponential backoff.

インストール

$ gem install retriable

実装例

require 'retriable'

class SampleError < RuntimeError
end

puts <<~EOS
  | exception       | try | elapsed_time | time         |
  |-----------------|-----|--------------|--------------|
EOS

Retriable.configure do |c|
  c.tries = 5
  c.base_interval = 1
  c.rand_factor = 0
  c.on = SampleError
  c.on_retry = -> (exception, try, elapsed_time, next_interval) {
    puts format('| %-15s | %3d | %12f | %-12s |', exception, try, elapsed_time, Time.now.strftime('%H:%M:%S.%L'))
  }
end

begin
  Retriable.retriable do |try|
    raise SampleError if try < 5
  end
  puts format('| %-15s | --- | ------------ | %-12s |', 'done', Time.now.strftime('%H:%M:%S.%L'))
rescue SampleError => e
  puts format('| %-15s | --- | ------------ | %-12s |', e, Time.now.strftime('%H:%M:%S.%L'))
end

実行。

$ ruby samle.rb
| exception       | try | elapsed_time | time         |
|-----------------|-----|--------------|--------------|
| SampleError     |   1 |     0.000040 | 13:29:53.806 |
| SampleError     |   2 |     1.005182 | 13:29:54.811 |
| SampleError     |   3 |     2.508871 | 13:29:56.315 |
| SampleError     |   4 |     4.764138 | 13:29:58.570 |
| done            | --- | ------------ | 13:30:01.948 |

リトライ回数を 3 回にしてみます。

# 略

Retriable.configure do |c|
  c.tries = 3
  # 略
end

# 略

実行。

$ ruby sample.rb 
| exception       | try | elapsed_time | time         |
|-----------------|-----|--------------|--------------|
| SampleError     |   1 |     0.000041 | 13:35:22.001 |
| SampleError     |   2 |     1.000827 | 13:35:23.002 |
| SampleError     |   3 |     2.501092 | 13:35:24.502 |
| SampleError     | --- | ------------ | 13:35:24.502 |

抵抗器のカラーコードは虹の色

会社で「抵抗器のカラーコードは虹の順番だよ」という話をしたら。
「いや、そもそも虹の色の順番覚えてないから」と返されてしまいました。

そんなわけなので、Ruby の gem にしてみました。
gem は書き慣れていないので、雑です。

• GitHub - mattsan/color_code: Resister Color Code

虹の色

「せき とう おう りょく せい らん し」と覚えます。「赤 橙 黄 緑 青 藍 紫」。
ただしカラーコードには「藍」は使われず「赤 橙 黄 緑 青 紫」の 6 つを使います。
前に「黒 茶」、後ろに「灰 白」を加えた「黒 茶 赤 橙 黄 緑 青 紫 灰 白」を 0 から 9 に割り当てます。

gem にしてみた

まず。Gemfile を書きます。

source "https://rubygems.org"

gem 'color_code', github: 'mattsan/color_code'

インストールします。

$ bundle install

irb で動作確認。

color_code_sample $ bundle exec irb
irb(main):001:0> require 'color_code'
=> true
irb(main):002:0> resister = '青緑赤金'.to_resister
=> 65 * 10**2 ± 5.0%
irb(main):003:0> resister.to_f
=> 6500.0
irb(main):004:0> resister.significant_digits
=> 65
irb(main):005:0> resister.multiplier
=> 2
irb(main):006:0> resister.tolerance
=> 0.05
irb(main):007:0> resister.lower_bound
=> 6175.0
irb(main):008:0> resister.upper_bound
=> 6825.0

誤差の範囲の上限下限も計算します。

いつか読むはずっと読まない：半世紀前の作品

原著 “ Way Station” が著されたのが 1963 年。サイエンス・フィクションというカテゴリにあると、科学や技術の発展に伴って陳腐化するのではないか、古くさくなるのではないか、という感覚を抱いてしまいますが。物語の面白さはそんなこととは無縁でした。

中継ステーション〔新訳版〕 (ハヤカワ文庫 SF シ 1-5) (ハヤカワ文庫SF)

どう書くのたのしみ

横浜へなちょこプログラミング勉強会 オフラインリアルタイムどう書く が神田に移ってきてやがて半年になります。
場所が住んでいるところから近くに移ったということもあって、ようやくオフラインで参加できるようになりました。

ふりかえってみるとオンラインながら どう書く のコードを書き始めたのが4年前。

• 「どう書く？」とつねに問う姿勢が大事、だと、思う。 - エンジニアのソフトウェア的愛情

気がつくと長いおつきあいになっていました。

ようやくオフラインで参加できるようになって、感じたことを少し。

当日

頭が真っ白になる、あの感じ

制限時間内にコードを書き上げなければならないのに、問題を見た瞬間に一行も書けないんじゃないか、という気がするあの感じ。
学生の頃はよく経験したこの感覚ですが（ォィ）、それが懐かしくもあり新鮮でもあり。

その状態から解法を閃いて書ける！ と感じた時のあの安堵感もなんとも言えません。

脇目も振らずコードを書く、あの感じ

仕事で書くコードは、慎重に書くようにしています。何かと早とちりする性格なので、小さく手を進めるようにしています。
そいうのをかなぐり捨てて、閃いた解法をコードに変換する行為に没頭する、あの感じ。
入力データがどのように流れて出力データになるのか見えていて、途中の動作確認もそこそこにコードを書く。コードの最終形態に頭から突っ込む。

…そしてだいたいはテストが通らず焦りながらデバッグする後半になるのですが、それはまた別のお話。

他の参加者のアイディアを知る、書き方を知る

当日参加された方の多くは、書いたコードをネット上に公開してくださっていますが、そこに至った経緯の解説はどうしても少なくなります。また解けたアイディアの解説はあっても、失敗したアイディアや、つまずいたところは、あまり表に出てきません。
当日は、その人が、その場所で、その問題を考えた、生のアイディアを伺う機会がえられます。勘違いだったり、遠回りだったり、明後日の方向を向いていたりすることもありますが、それを思いついた背景を聴ける機会はとても貴重。
加えてコーディングの技法もいろいろと知ることができます。

「join を *"" と書くのはゴルファだけです」 #yhpg

— MATSUMOTO Eiji (@emattsan) 2016年6月4日

飲む

コードを書いて、互いにコードを読んで、そのあとは懇親会です。

お酒の失敗してる人が多い会だ #yhpg

— 謎の音 (@onigra_) 2016年2月6日

#yhpg 皆でさいきんの失敗談を添えて自己紹介をしあった結果、E和さんに飲まれてる人が多いイメージが強化された

— torazuka (@torazuka) 2016年2月6日

…。

そんなことも、あります。

後日

深く深く考える

気になる問題に遭遇すると、何日も考える癖があります。二日も三日も考え続けると、ふと新しいアイディアが降りてくる瞬間があります。
そんなアイディアが降りてきたときは、言葉で定義し文章に書き出すことをしています。そうすると一段高いところから問題が見えるようになった気がします。

• ビット演算で解く Tick-Tack-Toe 〜「第一回 オフラインリアルタイムどう書く」より〜 - エンジニアのソフトウェア的愛情
• どう書くE04「ドキドキ登山〜怒りのデスルート」を解いたアイディアの解説 - Qiita

こうすることでコードを書くときの視野が高く遠く広くなってゆく感じがしています。

次回

そして次回は。今週末の開催です。

• オフラインリアルタイムどう書くE05 - 横浜へなちょこプログラミング勉強会 | Doorkeeper

いつか読むはずっと読まない：ハッカーのたのしみ

すでに何回も紹介していますが。良書です。現在入手は困難なようですが、見つけたらぜひ手にとって読んでみてください。

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか