Hatena::ブログ(Diary)

エンジニアのソフトウェア的愛情 このページをアンテナに追加 RSSフィード Twitter

2016-11-23

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

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

プログラミング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;
}

いつか読むはずっと読まない:バイク乗りがバイクになる(なりません)

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

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

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

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

2016-10-26

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

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

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


矩形を見つける問題

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


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冊目の中間、ちょっど真ん中あたりを読んでいます。半分まで読み進めてみても「異質な感じ」が終わりません。

正直最初のうちは得体の知れない感じが苦痛に感じる時もありましたが、進むにつれその感じにのめり込んでいることに気がつかされます。

2016-09-20

Fiddle を掻き鳴らしてみる

*.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

簡単すぎる。


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

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

http://www.dowland.jp/tablatura/phot2/tab.jpg

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


これがフィドル。

http://www.dowland.jp/tablatura/phot2/tasaki.jpg

同サイトより)


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

2016-08-21

Retriable gem の使い方のめも

インストール

$ 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 |

2016-07-01

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

会社で「抵抗器のカラーコードは虹の順番だよ」という話をしたら。

「いや、そもそも虹の色の順番覚えてないから」と返されてしまいました。


そんなわけなので、Rubygem にしてみました。

gem は書き慣れていないので、雑です。


虹の色

「せき とう おう りょく せい らん し」と覚えます。「赤 橙 黄 緑 青 藍 紫」。

ただしカラーコードには「藍」は使われず「赤 橙 黄 緑 青 紫」の 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 年。サイエンス・フィクションというカテゴリにあると、科学や技術の発展に伴って陳腐化するのではないか、古くさくなるのではないか、という感覚を抱いてしまいますが。物語の面白さはそんなこととは無縁でした。