Hatena::ブログ(Diary)

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

2017-02-21

Prolog で特殊文字をリテラルに書く

\x で始まり \ で終えます。末尾があることに注意。

例:バックスペース(0x08)を出力しています。

$ gprolog
| ?- format("~s\x08\~s~n", ["ABc", "CDE"]).
ABCDE

2017-01-29

オブラブカレンダーができました

やがて1月も終わろうという時期ですが。

2017 年版オブラブカレンダーができました。

f:id:E_Mattsan:20170124091829j:image


去る 1 月 11 日 には事業部のご挨拶とともにできあがったカレンダーをお渡しする会を開きました。

まだ若干数ありますので、ご興味のある方はオフィスにお立ち寄りいただけたらと思います。


ところで。私とオブラブカレンダーについて

f:id:E_Mattsan:20170124091717j:image:left

ご挨拶の会でも話をしたのですが、今の仕事をするきっかけは 10 年ほど前に参加したオブラブイベントがきっかけでした。

巡り巡って今の会社に移り今の仕事が始まったわけですが、たびたびイベントに参加していたとはいえ外から見える景色と中から見える景色はかなり違います。

そんな中で、刷り上がって納品されたオブラブカレンダーの束を見たとき、ようやく「中の人」の実感が湧いてきたのを覚えています。外から見えていたものをようやく内側から見えた、そんな感じです。

これは、手元に残っているおそらく最古のオブラブカレンダー。見ると 2007 年版。図らずしもちょうど 10 年前のオブラブカレンダー。

2017-01-09

Prolog だって Key-Value を扱いたい

不思議な記述を見つけました。

An object in JSON is presented as a bunch of keys and values within curly braces, in Prolog I have used a function and a KV list like so:

obj([key1-value1, key2-value2, ...]).

Present your terms like that and everything should be fine. See the source file json_encode.pl for a full explanation and some examples that should hopefully explain it all.

https://github.com/emacstheviking/gnuprolog-json


Prolog に “key-value” といった記法があったけ? と数日考え込んだのですが、Prolog では明示的に評価するまで記述した内容がそのまま値として扱われるということを利用しているということに思い至りました。


$ gprolog
| ?- A = 2 - 1.
A = 2-1

変数 A の値は 1 ではなく 2-1 であることがわかります。

2-11 とはマッチしません。

| ?- 1 = 2 - 1.
no

2-1 を明示的に評価することで値として 1 がえられます。

| ?- A is 2 - 1.
A = 1
yes
| ?- A is 2 - 1, 1 = A.
A = 1
yes


と、いうことは。評価前であれば演算子 - も含めた形で変数にマッチさせることができます。

| ?- A - B = 2 - 1.
A = 2
B = 1
yes

-演算は評価されないので、数値でなくても構いません。

| ?- A - B = abc - def. 
A = abc
B = def
yes

評価すると当然のようにエラーになります。

| ?- A is abc - def.   
uncaught exception: error(type_error(evaluable,abc/0),(is)/2)

これが “key-value” の正体だったようです。


これらを踏まえて。

key_value.pro を用意。

find(_, [], not_found) :- !.
find(K, [K-V|_], V) :- !.
find(K, [_|KVs], V) :- find(K, KVs, V).

GNU-Prolog で実行。

$ gprolog
| ?- ['key_value.pro'].
yes
| ?- find(a, [a-1, b-2, c-3], V).
V = 1
yes
| ?- find(b, [a-1, b-2, c-3], V).
V = 2
yes
| ?- find(c, [a-1, b-2, c-3], V).
V = 3
yes
| ?- find(d, [a-1, b-2, c-3], V).
V = not_found
yes

ペアが作れればよいので [ [a, 1], [b, 2], [c, 3] ] でもよいのですが、見やすさ書きやすさ誤った形式の排除という点で key-value という記述のメリットはありそうです。

ちなみに。

評価されなければよいので演算子- でなくても構いません。

| ?- A + B = abc + def.
A = abc
B = def
yes
| ?- A / B = abc / def.
A = abc
B = def
yes
| ?- A : B = abc : def.
A = abc
B = def
yes

いつか読むはずっと読まない:青春ものだった

私はサンリオSF文庫は読んだことはないのですが、こうして復刊されたものを読むと良書ぞろいだったのだろうなぁと思わずにはいられません。

ハローサマー、グッドバイ (河出文庫)

ハローサマー、グッドバイ (河出文庫)

2016-12-23

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

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

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

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

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

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

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

f:id:E_Mattsan:20161223124708j:image


この方法を単純に適用するだけでは、たとえば上の方では別の領域だったけれども下までたどったら繋がっていた、という場合にうまくいきません。そこで繋がっていた場合は一方はもう一方の別名だった、ということを記録するようにします。

番号は 1 から順番に大きくなる、先にふられた番号の方を有効とする、というルールに決めておくと、小さい方を実際の値、大きい方を別名と定義できます。すべてのセルに番号がついたら、記録しておいた別名を実際の番号にふりなおすことで繋がったセルには同じ番号がふられた状態になります。

f:id:E_Mattsan:20161223124702j:image


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

私のマシンで 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”)ですが、これもまた物の見事に内容を思い出せない。

そのうち読み返そうと思うのですが、書籍の山から本書を探し出して引っ張り出すのが、過去の記憶を引っ張り出すのと同じぐらい大変そうというのが目下の課題。

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;
}

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

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

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

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

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