エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

Redis Pub/Sub in Elixir 覚書

Elixir Redis めも

Exredis を使っています。

defmodule Subscribe do
  def sub(channel) do
    {:ok ,client_sub} = Exredis.Sub.start_link
    pid = Kernel.self

    Exredis.Sub.subscribe(client_sub, channel, fn msg ->
      send(pid, msg)
    end)

    receive do
      {:subscribed, ^channel, _pid} ->
        IO.puts "OK"
    end

    loop(channel)
  end

  def loop(channel) do
    receive do
      {:message, ^channel, message, _pid} ->
        IO.puts message
        loop(channel)
    end
  end
end

どこかで起動しておく。Redis も起動しておく。

> Subscribe.sub("test")
OK


Pub 。

> import Exredis
> Exredis.Api.publish(client, "test", "Hello")


こんな風に表示されます。

> Subscribe.sub("test")
OK
Hello


Ruby でも。

require 'redis'

r = Redis.new
r.publish('test', 'Hello')

> Subscribe.sub("test")
OK
Hello
Hello

RPN in Elixir

Elixir めも 
# Rpn.eval "3 1 - 2.1 +"
# => 4.1

defmodule Rpn do
  def eval(expression) do
    eval(tokenize(expression), [])
  end

  defp eval([], [result]), do: result
  defp eval(["+"|tokens], [rhs, lhs|stack]), do: eval(tokens, [lhs + rhs | stack])
  defp eval(["-"|tokens], [rhs, lhs|stack]), do: eval(tokens, [lhs - rhs | stack])
  defp eval(["*"|tokens], [rhs, lhs|stack]), do: eval(tokens, [lhs * rhs | stack])
  defp eval(["/"|tokens], [rhs, lhs|stack]), do: eval(tokens, [lhs / rhs | stack])
  defp eval([value|tokens], stack), do: eval(tokens, [value | stack])

  defp tokenize(expression) do
    tokens = Regex.scan( ~r/(?<op>[\+\-\*\/])|(?<float>\d+\.\d+)|(?<int>\d+)/, expression, capture: ["op", "int", "float"])
    Enum.map(
      tokens,
      fn
        ([op, "", ""]) -> op
        (["", int, ""]) -> String.to_integer(int)
        (["", "", float]) -> String.to_float(float)
      end
    )
  end
end


Regex.scan/3 がいささかトリッキー。使い方が合っているのか判断がつかない。

span

Prolog めも

練習。

% span.pro

:- module(span, [span/2]).

span(From, From, [From]) :- !.
span(From, To, [From|Span]) :-
  From < To,
  From1 is From + 1,
  span(From1, To, Span),
  !.

% span-test.pro

:- include(span).

main :-
  span(1, 10, S),
  format("~p~n", [S]),
  halt.


実行。

$ gprolog --consult-file span-test.pro --entry-goal main
[1,2,3,4,5,6,7,8,9,10]


通常使うには between で充分なのだけれど。

$ gprolog
| ?- findall(N, between(1, 10, N), NS).
NS = [1,2,3,4,5,6,7,8,9,10]
yes

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

oblove

やがて1月も終わろうという時期ですが。
2017 年版オブラブカレンダーができました。


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

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

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

ご挨拶の会でも話をしたのですが、今の仕事をするきっかけは 10 年ほど前に参加したオブラブイベントがきっかけでした。
巡り巡って今の会社に移り今の仕事が始まったわけですが、たびたびイベントに参加していたとはいえ外から見える景色と中から見える景色はかなり違います。
そんな中で、刷り上がって納品されたオブラブカレンダーの束を見たとき、ようやく「中の人」の実感が湧いてきたのを覚えています。外から見えていたものをようやく内側から見えた、そんな感じです。

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

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

Prolog めも

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

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-1 は 1 とはマッチしません。

| ?- 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文庫は読んだことはないのですが、こうして復刊されたものを読むと良書ぞろいだったのだろうなぁと思わずにはいられません。

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

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

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

Ruby どう書く

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

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

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

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

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

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


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


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

私のマシンで 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 ヘ)

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

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