どう書くのたのしみとくるしみ

今もまだ、少しずつ問題を解き進めています。

github.com

第七回 参考問題 XY-Sort

第七回の参考問題は「XY-Sort」。8x8 の数の並びを行方向または列方向で並べ替えて、最後に 1 行目の数の並びを出力する問題。

• XY-Sort 〜 横へな 2013.2.2 の参考問題

数の並びを配列の配列などで表現した場合、列の並び替えならば転置して並び替え結果を転置する、という方法が思いつけば簡単に解くことができます。

Elixir で実装するとこんな感じ。 リストのリストを転置するtranspose/1 の実装ができれば、あとは難しいところはありません。

defmodule YHPGexercise do
  @table ~w"""
         4 1 4 2 1 3
         7 3 2 0 5 0
         2 3 6 0 6 7
         6 4 5 7 5 1
         3 1 6 6 2 4
         6 0 5 5 5 1
         """
         |> Enum.chunk_every(6)

  def solve(input) when is_binary(input) do
    for(<<c <- input>>, do: c)
    |> Enum.reduce(@table, fn
      c, table when c in ?A..?F ->
        table
        |> transpose()
        |> Enum.sort_by(&Enum.at(&1, c - ?A))
        |> transpose()

      c, table ->
        table
        |> Enum.sort_by(&Enum.at(&1, c - ?u))
    end)
    |> hd()
    |> Enum.join()
  end

  def transpose([[] | _]), do: []
  def transpose(table), do: [Enum.map(table, &hd/1) | transpose(Enum.map(table, &tl/1))]
end

# 以下、テストコード

ExUnit.start(trace: true, seed: 0)

defmodule YHPGexerciseTest do
  use ExUnit.Case

  [
    {"0", "AvEx", "305027"},
    {"1", "A", "112344"},
    {"2", "C", "241413"},
    {"3", "F", "134214"},
    {"4", "u", "236067"},
    {"5", "w", "732050"},
    {"6", "y", "414213"},
    {"7", "yx", "732050"},
    {"8", "ux", "236067"},
    {"9", "EF", "131424"},
    {"10", "DF", "134124"},
    {"11", "Au", "055165"},
    {"12", "uA", "023667"},
    {"13", "By", "234114"},
    {"14", "yB", "114342"},
    {"15", "yBy", "357020"},
    {"16", "yByB", "350072"},
    {"17", "AuBvCw", "131244"},
    {"18", "FAuFBvFCw", "300527"},
    {"19", "AuBv", "112344"},
    {"20", "CwDx", "515056"},
    {"21", "FzyE", "324114"},
    {"22", "uAwDyB", "114324"},
    {"23", "zExCvF", "073520"},
    {"24", "uFxEv", "002357"},
    {"25", "DyCwB", "076362"}
  ]
  |> Enum.each(fn {number, input, expected} ->
    @tag input: input, expected: expected
    test "#{number} #{input}", %{input: input, expected: expected} do
      assert expected == YHPGexercise.solve(input)
    end
  end)
end

$ elixir exercise.exs
Running ExUnit with seed: 0, max_cases: 1


YHPGexerciseTest [7/exercise.exs]
  * test 0 AvEx (0.01ms) [L#68]
（以下略）

別解が見つからない

その後、別の解法がないか一週間ほど考えてみたのですが、どうにも見つかりません。 配列の配列以外のデータの持ち方も考えてみたのですが、データを変えても操作の方法は同じものしか思いつかない。

「どう書く」の問題を解いていて、一番悔しさを感じるときです。 気の利いた解法をじぶんで見つけられなかったときもかなり悔しいですが、すぐに思いつきすぐに解ける方法以外が見つからないときは、自分の中から出てくるアイディアはそんなものでしかないのか、と悲嘆してしまいます。

わたしは趣味のプログラマから職業プログラマへ転身した身ですが、こんなとき、仕事と趣味では向き合い方がまったく違うのだなと気付かされます。

逆に、前回の記事にしたような「こじらせた」コードができたときは満足度が高い。 仕事では絶対やりませんが。

blog.emattsan.org

第六回 当日のお題 続柄

• 続柄 〜 横へな 2013.1.11

この問題は当時も Prolog で解いているのですが、そのときの自分の記事を見ずに再発見することにしました。

genealogy(0, []) :- !.
genealogy(Person, [Person | Generation]) :-
  Parent is (Person + 1) div 3,
  genealogy(Parent, Generation).

me(P, P).
mo([_ | G], G).
da(G, [_ | G]).
si([_ | G], [_ | G]).
au([_, _ | G], [_ | G]).
ni([_ | G], [_, _ | G]).
co([_, _ | G], [_, _ | G]).

relative(G1, G2, "me") :- me(G1, G2).
relative(G1, G2, "mo") :- mo(G1, G2).
relative(G1, G2, "da") :- da(G1, G2).
relative(G1, G2, "si") :- si(G1, G2).
relative(G1, G2, "au") :- au(G1, G2).
relative(G1, G2, "ni") :- ni(G1, G2).
relative(G1, G2, "co") :- co(G1, G2).
relative(_, _, "-").

solve(P1, P2, R) :-
  genealogy(P1, G1),
  genealogy(P2, G2),
  relative(G1, G2, R),
  !.

to_integer([C], I) :- I is C - 48.
to_integer([C1, C0], I) :- I is (C1 - 48) * 10 + (C0 - 48).

split(Input, P1, P2) :-
  append(S1, [45, 62 | S2], Input),
  to_integer(S1, P1),
  to_integer(S2, P2),
  !.

% 以下、テストコード

judge(Input, Expect, Expect) :- format("o passed  input: ~s, result: ~s~n", [Input, Expect]).
judge(Input, Expect, Actual) :- format("x failed  input: ~s, expected: ~s, actual: ~s~n", [Input, Expect, Actual]).

test(Input, Expect) :-
  split(Input, P1, P2),
  solve(P1, P2, R),
  judge(Input, Expect, R),
  !.

test_all :-
  test("5->2", "mo"),
  test("28->10", "au"),
  test("1->1", "me"),
  test("40->40", "me"),
  test("27->27", "me"),
  test("7->2", "mo"),
  test("40->13", "mo"),
  test("9->3", "mo"),
  test("4->1", "mo"),
  test("1->3", "da"),
  test("12->35", "da"),
  test("3->8", "da"),
  test("6->19", "da"),
  test("38->40", "si"),
  test("9->8", "si"),
  test("4->2", "si"),
  test("15->16", "si"),
  test("40->12", "au"),
  test("10->4", "au"),
  test("21->5", "au"),
  test("8->2", "au"),
  test("3->5", "ni"),
  test("11->39", "ni"),
  test("2->13", "ni"),
  test("13->32", "ni"),
  test("14->22", "co"),
  test("40->34", "co"),
  test("5->8", "co"),
  test("12->10", "co"),
  test("1->27", "-"),
  test("8->1", "-"),
  test("12->22", "-"),
  test("2->40", "-"),
  test("32->31", "-"),
  test("13->14", "-").

使った処理系は GNU Prolog です。

• The GNU Prolog web site

$ gprolog --consult-file yhpg.pl --entry-goal test_all --query-goal halt
GNU Prolog 1.5.0 (64 bits)
Compiled Oct 29 2021, 07:27:11 with clang
Copyright (C) 1999-2021 Daniel Diaz

compiling /Users/matsumotoeiji/yhpg.pl for byte code...
/Users/matsumotoeiji/yhpg.pl compiled, 86 lines read - 24634 bytes written, 8 ms
o passed  input: 5->2, result: mo
（以下略）

実のところ、si/2 以降の続柄を判定する述語の実装は正確ではありません。 例えば si/2 で自分自身同士を比較すると結果は真（ yes ）になります。

$ gprolog

| ?- ['yhpg.pl']. % コードの読み込み

| ?- si([2, 1], [2, 1]).

yes

この実装では、si/2 よりも me/2 を先に評価し、真になったら評価を打ち切る実装をしているので、結果としてこの実装でも問題を解くことができています。

アイディアがコードになるとき

この Prolog の実装では、思いついたアイディアをそのままコードで表現できました。 アイディアを正確に思い描くのに少し時間がかかったのですが、イメージが固まったあとは、実装の都合のためのコードといったものがなく、ほぼそのまま写しとれた感じがします。

こういうときは、とても気分がよい。 コードの端まで意識が届いたような、そんな感じ。

単に一過性の満足感だけでなく、何か新しいものが自分の中に増えたような、そんな気になります。気がするだけですけれども。

いつか読むはずっと読まない：みっけた

へんなものみっけ! (13) (ビッグコミックス)

Rails on Tiles をビット演算で解く

先日の記事の通り、プログラミングの筋力トレーニングのために「オフラインリアルタイムどう書く」の過去問を解いています。

14年ぶりのフカシギの通行止め in Elixir - エンジニアのソフトウェア的愛情

第 5 回の参考問題は「Rails on Tiles」。

nabetani.sakura.ne.jp

3x3 に並べたタイルに載っているレールをたどって、指定された起点からレールが途切れるまでタイルとたどるというもの。

再挑戦して最初に実装した方法は、指定されたタイルの位置からレールのパタンにそってタイルを上下左右に移動する、という素朴な方法。 C++ で書いた 14 年前の解法 でも同じ方法をとっていました。

しかし、レールがどのようにつながっているかが構造の実体で、位置関係は本質ではありません。

そこでレールの接続に注目して再考してみました。

ポイント（頂点）とレール（辺）

まず各タイルの上には、4 つの辺に対応する 4 つのポイントがあると考えました。 それらのポイント同士はレールで接続されています。

隣接するタイルのポイントは事前に接続されているので、入力によらず下図のポイントはレールで接続されていることになります。

次に、タイル内のポイントは入力にもとづいて接続されます。 例えば 0 番目の入力でポイントを接続すると次のようになります。

ここから起点となる B0 を含むグラフを取得すると次のようになります。

B0-B2-E0-E3-D1-D2-G0-G1-H3-H1-I3-I0-F2-F3-E1-F2-H0-H2

ここからタイルの列を復元すれば BEDGHIFEH になる、はずです。

ちなみに。 一般にグラフでは「頂点」と「辺」という名前を使いますが、今回はお題が「Rails on Tiles」なので、「ポイント」と「レール」という言葉を使ってみました。

ビットで表現する

ここでタイル上にあるポイントをそれぞれ異なるビットと解釈すると、9 つのタイル上のポイントはその位置に対応するビットのみ 1 になっている 36 ビットの数値として考えることができます。

ポイント	数値表現
A0	0b0000_0000_0000_0000_0000_0000_0000_0000_0001
A1	0b0000_0000_0000_0000_0000_0000_0000_0000_0010
A2	0b0000_0000_0000_0000_0000_0000_0000_0000_0100
A3	0b0000_0000_0000_0000_0000_0000_0000_0000_1000
B0	0b0000_0000_0000_0000_0000_0000_0000_0001_0000
B1	0b0000_0000_0000_0000_0000_0000_0000_0010_0000
B2	0b0000_0000_0000_0000_0000_0000_0000_0100_0000
...	...
E0	0b0000_0000_0000_0000_0001_0000_0000_0000_0000
...	...

異なるポイントは異なる位置のビットが 1 になっているので、二つのポイントを繋ぐレールは、その二つのポイントの数値表現の論理和として表現することができるようになります。

レール	数値表現
B0 - B2	0b0000_0000_0000_0000_0000_0000_0000_0101_0000

これによって、レールとそのレールで接続される一方のポイントが与えられた場合、レールからそのポイントのビットを取り除くと、もう一方のポイントを取得することができるようになります。 このビットを取り除く操作には、排他的論理和が使えます。

その結果、次の操作でレールをたどることができるようになります。

1. 起点となるポイントを指定する
2. そのポイントを含むレールを取得する
3. そのポイントと取得したレールの排他的論理和の値を次のポイントとして取得する

接続しているすべてのポイントを取得する場合は、次のポイントを新たな起点として 2 から繰り返し、次のポイントが存在しない場合は終了します。

実装

Elixir で実装してみました。 ビット演算が可能な言語であれば、どのような言語でも同じような実装になると思います。

defmodule YHPG5exercise do
  defmodule Tile do
    import Bitwise

    # タイルの名前（"A", "B", ...）と位置から 36 ビットの数値を作成する
    def to_point(<<tile>>, direction) do
      1 <<< (direction + (tile - ?A) * 4)
    end

    # 36 ビットの数値から、タイルの名前を復元する
    def from_point(point) do
      Enum.reduce_while(?A..?I, point, fn tile, n ->
        case n >>> 4 do
          0 -> {:halt, <<tile>>}
          m -> {:cont, m}
        end
      end)
    end
  end

  import Bitwise

  # タイル間のレールのリスト
  @outer_rails [
    #  0      0      0
    # 3A1 -- 3B1 -- 3C1
    #  2      2      2
    #  |      |      |
    #  0      0      0
    # 3D1 -- 3E1 -- 3F1
    #  2      2      2
    #  |      |      |
    #  0      0      0
    # 3G1 -- 3H1 -- 3I1
    #  2      2      2
    #
    #    I    H    G    F    E    D    C    B    A
    # 3210_3210_3210_3210_3210_3210_3210_3210_3210
    # A1 - B3
    0b0000_0000_0000_0000_0000_0000_0000_1000_0010,
    # A2 - D0
    0b0000_0000_0000_0000_0000_0001_0000_0000_0100,
    # B1 - C3
    0b0000_0000_0000_0000_0000_0000_1000_0010_0000,
    # B2 - E0
    0b0000_0000_0000_0000_0001_0000_0000_0100_0000,
    # C2 - F0
    0b0000_0000_0000_0001_0000_0000_0100_0000_0000,
    # D1 - E3
    0b0000_0000_0000_0000_1000_0010_0000_0000_0000,
    # D2 - G0
    0b0000_0000_0001_0000_0000_0100_0000_0000_0000,
    # E1 - F3
    0b0000_0000_0000_1000_0010_0000_0000_0000_0000,
    # E2 - H0
    0b0000_0001_0000_0000_0100_0000_0000_0000_0000,
    # F2 - I0
    0b0001_0000_0000_0100_0000_0000_0000_0000_0000,
    # G1 - H3
    0b0000_1000_0010_0000_0000_0000_0000_0000_0000,
    # H1 - I3
    0b1000_0010_0000_0000_0000_0000_0000_0000_0000
  ]

  # タイル内のレールのパタン
  @patterns %{
    "0" => [0b0101, 0b1010],
    "1" => [0b0011, 0b1100],
    "2" => [0b0110, 0b1001]
  }

  def solve(input) when is_binary(input) do
    # タイル内のレールのリスト
    inner_rails = parse_rails(input)

    # B0 を起点にしてレールをたどる
    Stream.unfold(Tile.to_point("B", 0), fn point ->
      # point を含むレールを見つけ、レールをたどって次のタイルのポイントを取得する
      # point を出力とし、取得した次のタイルのポイントを、次の point にする
      # 次のタイルのポイントが nil になる（なくなる）まで繰り返す
      case find_rail(inner_rails, point) do
        nil -> nil
        rail -> {point, next_point(point, rail)}
      end
    end)
    |> Enum.map(&Tile.from_point/1)
    |> Enum.join()
  end

  defp parse_rails(input) do
    input
    |> String.codepoints()
    |> Enum.with_index()
    |> Enum.flat_map(fn {kind, index} ->
      Enum.map(@patterns[kind], fn pattern ->
        pattern <<< (index * 4)
      end)
    end)
  end

  # ポイントを含むレールを見つける
  defp find_rail(rails, point) do
    if is_nil(point) do
      nil
    else
      Enum.find(rails, fn rail -> (rail &&& point) != 0 end)
    end
  end

  # 現在のポイントからレールをたどって、次のタイルのレールを取得する
  defp next_point(point, rail) do
    # rail の反対側のポイント
    opposite_point = bxor(rail, point)

    # タイル間のレールのリストから、rail の反対側のポイントを含むレールを見つけ、
    # そのレールで接続される次のタイルのポイントを取得する
    case find_rail(@outer_rails, opposite_point) do
      nil -> nil
      connected_point -> bxor(connected_point, opposite_point)
    end
  end
end

# 以下、テストコード
ExUnit.start(trace: true, seed: 0)

defmodule YHPG5exerciseTest do
  use ExUnit.Case

  [
    {"0", "101221102", "BEDGHIFEH"},
    {"1", "000000000", "BEH"},
    {"2", "111111111", "BCF"},
    {"3", "222222222", "BAD"},
    {"4", "000211112", "BEFIHEDGH"},
    {"5", "221011102", "BADGHIFEBCF"},
    {"6", "201100112", "BEHIFCBADEF"},
    {"7", "000111222", "BEFIH"},
    {"8", "012012012", "BC"},
    {"9", "201120111", "BEDABCFI"},
    {"10", "220111122", "BADEHGD"},
    {"11", "221011022", "BADG"},
    {"12", "111000112", "BCFIHEBA"},
    {"13", "001211001", "BEFI"},
    {"14", "111222012", "BCFEHIF"},
    {"15", "220111211", "BADEHI"},
    {"16", "211212212", "BCFEBAD"},
    {"17", "002112210", "BEFC"},
    {"18", "001010221", "BEF"},
    {"19", "100211002", "BEFIHG"},
    {"20", "201212121", "BEFCBAD"}
  ]
  |> Enum.each(fn {number, input, expected} ->
    @tag input: input, expected: expected
    test "#{number} #{input}", %{input: input, expected: expected} do
      assert expected == YHPG5exercise.solve(input)
    end
  end)
end

<<65>> = "A"

標準の関数を使っているので、個々の関数の操作は難しくないと思います。

"A", "B", ... といった文字列から 0,1, ... を作る操作、あるいはその逆の操作のみ少しトリッキーかもしれません。

?A などは、文字コードを表します。 ?A は A の文字コードなので、型は整数で値は 65 です。

<<65>> などは、1バイトのバイナリ列を表します。 Elixir の文字列はバイナリ列として扱われているので、ここでは一文字の文字列と考えてもらっても構いません。 <<65>> は文字コード 65 一つからなる文字列で、値は "A" と同じです。

これらはパタンマッチングを利用して互いに変換することができます。

<<a>> = "A"
a #=> 65

a = 65
<<a>> #=> "A"

Tile.to_point, Tile.from_point は、これらの仕組みを使って文字列と数値の変換を行なっています。

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

何度紹介したかわからないですが、何度でも紹介したいので、また紹介します。

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

現在ではオンデマンド版の方が入手しやすいようです。

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

14年ぶりのフカシギの通行止め in Elixir

最近、プログラミングの筋力が落ちてしまい、筋トレにちょうどよいと思い、オフラインリアルタイムどう書くの過去問を解いています。

github.com

第四回の参考問題が「フカシギの通行止め」。

qiita.com

当時話題になった「フカシギの数え方」から着想された問題。

www.youtube.com

自分自身も試してみた記憶があったと思いリンクをたどってみると、ちょうど 14 年前の 9 月 21 日に投稿していました。

まだ今の会社に移る前、C++ を主たる言語として利用していた時期です。

どんな技法を使っているのかと見てみると、力業で数え上げていました。

qiita.com

現在愛用している Elixir で力業で解いてみます。

defmodule YHPG4exercise do
  #  0 -- 1 -- 2 -- 3 -- 4
  #  |    |    |    |    |
  #  5 -- 6 -- 7 -- 8 -- 9
  #  |    |    |    |    |
  # 10 - 11 - 12 - 13 - 14
  #  |    |    |    |    |
  # 15 - 16 - 17 - 18 - 19
  #  |    |    |    |    |
  # 20 - 21 - 22 - 23 - 24

  @edges %{
    0 => MapSet.new([1, 5]),
    1 => MapSet.new([0, 2, 6]),
    2 => MapSet.new([1, 3, 7]),
    3 => MapSet.new([2, 4, 8]),
    4 => MapSet.new([3, 9]),
    5 => MapSet.new([0, 6, 10]),
    6 => MapSet.new([1, 5, 7, 11]),
    7 => MapSet.new([2, 6, 8, 12]),
    8 => MapSet.new([3, 7, 9, 13]),
    9 => MapSet.new([4, 8, 14]),
    10 => MapSet.new([5, 11, 15]),
    11 => MapSet.new([6, 10, 12, 16]),
    12 => MapSet.new([7, 11, 13, 17]),
    13 => MapSet.new([8, 12, 14, 18]),
    14 => MapSet.new([9, 13, 19]),
    15 => MapSet.new([10, 16, 20]),
    16 => MapSet.new([11, 15, 17, 21]),
    17 => MapSet.new([12, 16, 18, 22]),
    18 => MapSet.new([13, 17, 19, 23]),
    19 => MapSet.new([14, 18, 24]),
    20 => MapSet.new([15, 21]),
    21 => MapSet.new([16, 20, 22]),
    22 => MapSet.new([17, 21, 23]),
    23 => MapSet.new([18, 22, 24]),
    24 => MapSet.new([19, 23])
  }

  def solve(input) when is_binary(input) do
    closed_pathes = parse_closed_pathes(input)

    count_route(0, MapSet.new(1..24), closed_pathes)
  end

  defp parse_closed_pathes(input) do
    input
    |> String.split()
    |> Enum.map(&String.to_charlist/1)
    |> Enum.map(fn [a, b] -> {a - ?a, b - ?a} end)
    |> MapSet.new()
  end

  defp count_route(24, _, _), do: 1

  defp count_route(current, nodes, closed_pathes) do
    MapSet.intersection(nodes, @edges[current])
    |> Enum.reject(&closed?(closed_pathes, current, &1))
    |> Enum.map(&count_route(&1, MapSet.delete(nodes, &1), closed_pathes))
    |> Enum.sum()
  end

  defp closed?(closed_pathes, node1, node2) do
    MapSet.member?(closed_pathes, {node1, node2}) || MapSet.member?(closed_pathes, {node2, node1})
  end
end

# 以下、テストコード
ExUnit.start(trace: true, seed: 0)

defmodule YHPG4exerciseTest do
  use ExUnit.Case

  [
    {"", 8512},
    {"af", 4256},
    {"xy", 4256},
    {"pq qr rs st di in ns sx", 184},
    {"af pq qr rs st di in ns sx", 92},
    {"bg ch di ij no st", 185},
    {"bc af ch di no kp mr ns ot pu rs", 16},
    {"ab af", 0},
    {"ty xy", 0},
    {"bg ch ej gh lm lq mr ot rs sx", 11},
    {"ty ch hi mn kp mr rs sx", 18},
    {"xy ch hi mn kp mr rs sx", 32},
    {"ch hi mn kp mr rs sx", 50},
    {"ab cd uv wx", 621},
    {"gh mn st lq qr", 685},
    {"fg gl lm mr rs", 171}
  ]
  |> Enum.each(fn {input, expected} ->
    @tag input: input, expected: expected
    test "#{input}", %{input: input, expected: expected} do
      assert expected == YHPG4exercise.solve(input)
    end
  end)
end

Elixir を使い始めて 10 年になりますが、すぐに思いつくのがこの程度ということにいささか不満が募ります。

• FizzBuzzを宣言的に書く、宣言できない場合は宣言っぽく書く - エンジニアのソフトウェア的愛情

ちなみに。 その後「フカシギの通行止め」の Prolog での実装を、このブログに書いています。

blog.emattsan.org

これを参考に Elixir でもう一捻りしてみたいところ。

はてなブログで LaTexをレンダリングする方法の覚書

[$ ... $] でブロックを作る（2026年7月以降）。

例1

[$ \sum_{x = 1}^n f(x) $]

[$ \displaystyle \sum_{x = 1}^n f(x) $]

例2

[$
\begin{array}{rcl}

\boldsymbol{A} \cdot \boldsymbol{B}

& = &

\begin{bmatrix}
| & | & | \\
\boldsymbol{a_{1}} & \boldsymbol{a_{2}} & \boldsymbol{a_{3}} \\
| & | & |
\end{bmatrix}

\cdot

\begin{bmatrix}
- & \boldsymbol{b^*_{1}} & - \\
- & \boldsymbol{b^*_{2}} & - \\
- & \boldsymbol{b^*_{3}} & -
\end{bmatrix}

\\

& = &

\boldsymbol{a_1} \boldsymbol{b^*_1} +
\boldsymbol{a_2} \boldsymbol{b^*_2} +
\boldsymbol{a_3} \boldsymbol{b^*_3}

\end{array}
$]

出典

help.hatenablog.com

staff.hatenablog.com

図形で理解するということ〜線形代数と数的霊薬〜

行列の積

図解 線形代数: ストラング流直感的理解 (近代科学社Digital)

の行列同士の積を考えます。

定義に従い計算すると、1行1列の要素は左の項の1行目と右の項の1列目の各々の要素の積の和、1行2列の要素は左の項の1行目と右の項の2列目の各々の要素の積の和、…、3行3列の要素は左の項の3行目と右の項の3列目の各々の要素の積の和、となります。

この行列の和の部分を行列の外に出すと、次のように表現することができます。

これは、左の行列を列ベクトルに、右の行列を行ベクトルに分けたとき、1 番目の列ベクトルと行ベクトル、 2 番目の列ベクトルと行ベクトル、3 番目の列ベクトルと行ベクトルのそれぞれの積を足し合わせたものと同じになります。

これを計算で確かめます。

Nx - Numerical Elixir

Elixir には Numerical Elixir - Nx というプロジェクト / ライブラリがあります。

github.com

nx.hexdocs.pm

機械学習などで利用されることを想定されていますが、ここでは純粋に行列計算に利用します。

まず IEx を起動します。

$ iex
Erlang/OTP 29 [erts-17.0.5] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [jit] [dtrace]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> 

IEx が起動したら、環境に Nx をインストールします。

iex> Mix.install([:nx])

以下、プロンプトの iex> は省略します。

ここでは Nx モジュールの関数をモジュール名の装飾なしに利用したいので、すべて import します。

import Nx

行列を定義します。

a = ~MAT[
1 2 3
4 5 6
7 8 9
]

#Nx.Tensor<
  s32[3][3]
  [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
  ]
>

ここで ~MAT は Nx.Tensor の値を作成するための構文糖衣です。 あとで出てくる ~VEC も同様です。

行列をもう一つ定義します。

b = ~MAT[
1 4 7
2 5 8
3 6 9
]

#Nx.Tensor<
  s32[3][3]
  [
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
  ]
>

行列から列ベクトルを取り出します。

take(a, ~VEC[0], axis: 1)

#Nx.Tensor<
  s32[3][1]
  [
    [1],
    [4],
    [7]
  ]
>

axis には軸を指定します。 表示された Nx.Tensor の値からわかる通り、値は [[1,2,3],[4,5,6],[7,8,9]] という並びで格納されています。 Nx では添え字は 0 から始まるので、縦方向に値を拾いたい場合は axis: 1 を指定します。

同様に行ベクトルを取り出します。 axis オプションのデフォルト値は 0 のため指定を省略できますが、ここでは表記を合わせることにします。

take(b, ~VEC[0], axis: 0)

#Nx.Tensor<
  s32[1][3]
  [
    [1, 4, 7]
  ]
>

なお第 2 引数にはスカラも利用できますが、ここでスカラを与えると期待する形の値が得られないため、それぞれベクトル（ ~VEC[0] ）で指定しています。

take(b, 0, axis: 0)

#Nx.Tensor<
  s32[3]
  [1, 4, 7]
>

行列の積の値を確認します。

dot(a, b)

#Nx.Tensor<
  s32[3][3]
  [
    [14, 32, 50],
    [32, 77, 122],
    [50, 122, 194]
  ]
>

次に、各々の列ベクトルと行ベクトルの積の和の値を確認します。

a1b1 = dot(take(a, ~VEC[0], axis: 1), take(b, ~VEC[0], axis: 0))
a2b2 = dot(take(a, ~VEC[1], axis: 1), take(b, ~VEC[1], axis: 0))
a3b3 = dot(take(a, ~VEC[2], axis: 1), take(b, ~VEC[2], axis: 0))

a1b1 |> add(a2b2) |> add(a3b3)

#Nx.Tensor<
  s32[3][3]
  [
    [14, 32, 50],
    [32, 77, 122],
    [50, 122, 194]
  ]
>

一致することが確認できました。

Julia - The Julia Programming Language

同じ内容を Julia でも計算させてみます。

julialang.org

$ julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.7.3 (2022-05-06)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

以下、プロンプトの julia> 以降が入力した式で、その下に表示される値は Julia の出力です。

julia> A = [1 2 3; 4 5 6; 7 8 9]
3×3 Matrix{Int64}:
 1  2  3
 4  5  6
 7  8  9

julia> B = [1 4 7; 2 5 8; 3 6 9]
3×3 Matrix{Int64}:
 1  4  7
 2  5  8
 3  6  9

julia> A * B
3×3 Matrix{Int64}:
 14   32   50
 32   77  122
 50  122  194

Julia では、ベクトルの後に [行番号,列番号] と列番号と列番号を指定することで、指定した位置の値を取得できます。 値の代わりに : を指定すると列全体または行全体を取得できます。

なお Julia では添え字は 1 始まりなので、1 列目や 1 行目には 1 を指定します。

ただし、単純に列番号を指定すると扱いたい形式にならないため、

julia> A[1,:]
3-element Vector{Int64}:
 1
 2
 3

[[1],:] という形で指定します。

julia> A[[1],:]
1×3 Matrix{Int64}:
 1  2  3

julia> A[:,1]
3-element Vector{Int64}:
 1
 4
 7

取り出した列と行は、同じように積をとることができます。

julia> A[:,1] * B[[1],:]
3×3 Matrix{Int64}:
 1   4   7
 4  16  28
 7  28  49

各々の列ベクトルと行ベクトルの積の和の値を確認します。

julia> A[:,1] * B[[1],:] + A[:,2] * B[[2],:] + A[:,3] * B[[3],:]
3×3 Matrix{Int64}:
 14   32   50
 32   77  122
 50  122  194

一致することが確認できました。

図解線形代数

なお、ちゃんとした話はこちらにありますので、こちらを読んでいただけたらと。

anagileway.com

オブジェクトの手続きと手続きのオブジェクト

構造体のようなオブジェクトを扱う

オブジェクト指向言語使っていても、ただの値の塊としか利用されないケースに遭遇します。

class Foo
  def initialize(attr_a, attr_b, attr_c)
    @attr_a = attr_a
    @attr_b = attr_b
    @attr_c = attr_c
  end

  def do_something(info)
    info.attr_1 = info.attr_1 * @attr_a
    info.attr_2 = info.attr_2 * @attr_b
    info.attr_3 = info.attr_3 * @attr_c
  end
end

class Info
  attr_accessor :attr_1, :attr_2, :attr_3

  def initialize(attr_1, attr_2, attr_3)
    @attr_1 = attr_1
    @attr_2 = attr_2
    @attr_3 = attr_3
  end
end

foo = Foo.new(2, 3, 5)
info = Info.new(7, 11, 13)

foo.do_something(info)
pp info
#=> #<Info:0x0000000120c09c90 @attr_1=14, @attr_2=33, @attr_3=65>

ベタ書きがよくないからと手続きを分離しても、関数に分離するところまで止まってしまうことがあります。

class Foo
  # ...

  def do_something(info)
    do_something1(info)
    do_something2(info)
    do_something3(info)
  end

  private

  def do_something1(info)
    info.attr_1 = info.attr_1 * @attr_a
  end

  def do_something2(info)
    info.attr_2 = info.attr_2 * @attr_b
  end

  def do_something3(info)
    info.attr_3 = info.attr_3 * @attr_c
  end
end

構造体のようなオブジェクトを能動的なオブジェクトで包む

構造体のようなオブジェクトを定義しているのが自分たちであれば #do_something1 を Info へ移動して、info.do_something1(@attr_a) としたいところですが、Info を直接変更することができないならば、一層包んでやる必要があります。

たとえば Info を包む Attributes を用意して、Attributes に #do_something1 を移動してみます。

class Foo
  def initialize(attr_a, attr_b, attr_c)
    @attr_a = attr_a
    @attr_b = attr_b
    @attr_c = attr_c
  end

  def do_something(attributes)
    attributes.do_something1(@attr_a)
    attributes.do_something2(@attr_b)
    attributes.do_something3(@attr_c)
  end
end

class Info
  attr_accessor :attr_1, :attr_2, :attr_3

  def initialize(attr_1, attr_2, attr_3)
    @attr_1 = attr_1
    @attr_2 = attr_2
    @attr_3 = attr_3
  end
end

class Attributes
  def initialize(info)
    @info = info
  end

  def do_something1(attr)
    @info.attr_1 = @info.attr_1 * attr
  end

  def do_something2(attr)
    @info.attr_2 = @info.attr_2 * attr
  end

  def do_something3(attr)
    @info.attr_3 = @info.attr_3 * attr
  end
end

foo = Foo.new(2, 3, 5)
info = Info.new(7, 11, 13)
attributes = Attributes.new(info)

foo.do_something(attributes)

欲しい手続きを持ったオブジェクトで包む方法はよくやるのですが、今回のように操作する間だけ包み、操作後は元のオブジェクトを利用するという使い方をするばあいは、いつオブジェクトが変更されたのか隠されてしまうという難点があります。

手続きをオブジェクトにして分離する

こういったときには手続きを分離してしまうのがよいのかも知れません。 手続きを担うオブジェクトを導入します。

class Foo
  attr_reader :attr_a, :attr_b, :attr_c

  def initialize(attr_a, attr_b, attr_c)
    @attr_a = attr_a
    @attr_b = attr_b
    @attr_c = attr_c
  end

  def do_something(processor, data)
    processor.do_something1(self, data)
    processor.do_something2(self, data)
    processor.do_something3(self, data)
  end
end

class Info
  attr_accessor :attr_1, :attr_2, :attr_3

  def initialize(attr_1, attr_2, attr_3)
    @attr_1 = attr_1
    @attr_2 = attr_2
    @attr_3 = attr_3
  end
end

class Processor
  def do_something1(foo, info)
    info.attr_1 = info.attr_1 * foo.attr_a
  end

  def do_something2(foo, info)
    info.attr_2 = info.attr_2 * foo.attr_b
  end

  def do_something3(foo, info)
    info.attr_3 = info.attr_3 * foo.attr_c
  end
end

foo = Foo.new(2, 3, 5)
info = Info.new(7, 11, 13)
processor = Processor.new

foo.do_something(processor, info)

Foo#do_something は必要な操作の並びを指揮し、個々の操作の詳細は専用のオブジェクトに任せる。

手続きの集まりのオブジェクト

ここで、それぞれの手続きは固定の操作だからとハードコードしてしまうと、二つ目に書いた「関数に分離」しただけの硬直したコードに戻ってしまいます。

結局のところこのオブジェクトは二つのオブジェクトの関係を表現しているのではないかと思います。 手続きしか持たないために対応する実態がないようにも感じられますが、同じオブジェクトの間にも複数の関係があると考えれば、それらが異なるオブジェクトで表現されることも自然に感じられるようになると思います。

foo = Foo.new(2, 3, 5)
info = Info.new(7, 11, 13)
processor = AnotherProcessor.new

foo.do_something(processor, info)

状態を持たない ≠ スタティックな存在

「状態を持たない」と説明されたときに、状態を持たない = インスタンス変数を持たない = インスタンスは不要 と捉えて、すべてのメソッドをクラスメソッド、つまり関数として定義するパタンを何回か目にしました。

おそらくこれは誤解で、上で示したとおり状態がなくてもオブジェクトとして捉えることは可能です。 そもそも、状態はなくても個々のオブジェクトに固有のパラメータを持たせることで、操作の際にそれぞれ個性の違うオブジェクトとして振る舞えるようにすることも考えられるわけで、スタティックな存在とイメージするのはいささか短絡的かなという印象です。

オブジェクト指向は、十分に普及した。 そう思っていましたが、意外とそうでなかったのか。 あるいは、オブジェクト指向を踏襲する必要性がなくなり、このような技法も不要になりつつあるのか。 もう少し観察してみたいところです。

いつか読むはずっと読まない：石垣の中の県庁

福井県の県庁は、福井城址に建てられています。

福井城とは？ (PDF)

つまり、石垣の中に県庁があります。

「石垣の中の県庁」と「黒曜石の中の不死鳥」とは似てそうと思ったけれど、そんなに似てなかった。

黒曜石のなかの不死鳥 (ハヤカワ文庫 SF 531―エレコーゼ・サーガ2)

プログラミングをプログラミングする

コードを出力するコードを書く

一発で目的のコードを出力するためのコードを書く、というのが昔のジョークにあった気がしますが。

最近は。 仕事では。 「『目的のプログラミングを AI に生成させるプロンプト』を AI に生成させるプロンプト」を AI で生成しています。

「自分」の入る余地はどこ？　という気持ちにならなくもないですが、見ているとやはりプロンプトを書く人によって個性が出るようです。

思いつく解法がひとつのとき

長く仕事でプログラミングをしていると、開発する内容に対して、それを解決する方法がそれほど迷わず思い浮かぶようになります。 完成形で出てくるわけではないですが、どの種類の解法を組み合わせればどうにかなりそうか、当たりがつくようになります。

そんなときでも、ひとつしか方法が思いつかないときは、自分を疑ってかかっています。

よほど単純な問題でもない限り、解法がひとつなどということはありません。 自分がそんなに簡単に最適な解法ひとつを選べるはずがない、という自分に対する疑念がいつもつきまとっています。

ただ一方で、最初に思いついた方法に対しても、これで間違いないだろうという感覚があり、我ながらめんどくさい精神構造だと呆れたりもしています。

クリティカルシンキング

この精神構造は今の仕事でも発揮されていて。

自分が指示を出して出力させた分析結果を信じきれず、与えた情報に偏りがないか、指示にバイアスがかかっていないか、いつも気にしています。

なので生成させるものの仕上がりが近づくと、必ず「偏ってないか」「バイアスはないか」「指示していないことは何か」「出力結果に反する情報を見落としていないか」と、問いただすのは否定的なことばかり。

無限に続けられるわけでないので、及第点と判断したところで仕上がりとするのですが、「完成には程遠いな」という感覚はずっとついて回っています。

プログラミング・プログラミング

今のような状況になってしばらく経ちますが、間接的に仕事をしているようなこの感覚は、当面消えそうにありません。

AI を使わずに仕事をするという選択はすでになく、使うのが当然という理解でいるわけですが、それとこれとはまた別の話。

自分でプログラミングするかどうかという問いも、輪郭がぼんやりしていてあまり意味をなさなくなっているように思います。 が、とはいえ。 出力される何かは自分が出力できるもの以上のものでないと、納得できない気持ちでもいます。

Markdown のテキストに、自分の思考を写し取りたいのかも。

ライフボックス

自分を写し取るというと、昔々に読んだ本の中にあった「ライフボックス」を今でも思い出します。

思考の道具箱: 数学的リアリティの五つのレベル

邦訳は現在も入手できますが、原著であれば著者のサイトで読むことができます。

www.rudyrucker.com

その中の一節。

I would hazard a guess that, in the future, recording one’s own life fractal will be a very popular activity among retired people. Already it is not uncommon for an older person to write down the “story of my life,” but how much easier and how much more complete it would be if one could purchase a small computer, called, let us say, a life box. You could tell random reminiscences to your life box and it would store them all and set up a system of cross-referencing. Occasionally the life box might ask you a question to clear up certain confusing links. After a few months it would have you down in some detail, and you could pass it on to your children so that your grandchildren would be able to hear for themselves “what Grampa was like.” Who wouldn’t want to immortalize himself this way?

（Google 翻訳）

将来、退職後の人々の間で、自分自身の「人生のフラクタル」を記録することが非常に人気のある活動になるのではないかと、私は推測しています。高齢者が「私の人生の物語」を書き残すことは今でも珍しくありませんが、もし「ライフ・ボックス」とでも呼ぶべき小型のコンピュータを購入できれば、その作業はずっと簡単になり、内容もはるかに充実したものになるでしょう。思いつくままに昔の思い出をそのライフ・ボックスに語りかければ、装置はそれらすべてを記録し、相互に関連付けるシステムを構築してくれます。時には、曖昧なつながりを明確にするために、ライフ・ボックスの方から質問をしてくることもあるかもしれません。数ヶ月もすれば、あなたの人生が詳細に記録され、それを子供たちに引き継ぐことで、孫たちが「おじいちゃんはどんな人だったのか」を自分の耳で確かめられるようになるのです。このようにして自分自身を不滅のものにしたいと思わない人がいるでしょうか。

ふと、しばらくぶりに著者のサイトを開いてみると、二年半前にそのことを大きく取り上げたブログ記事がありました。

www.rudyrucker.com

（Google 翻訳）

ルーディは「ソフトウェアによる不老不死」を予言していた

コンピュータ上でプロセスを走らせることで人間をシミュレートすることに、私たちは着実に近づいています。世間では、「ソフトウェアによる不老不死」が実現するかもしれないという夢が語られています。そして私は、40年前にそれを予言していたのです。

ルーディ・ラッカーの「ソフトウェア」を読んで三十数年になりますが、いまだにこの著作の影響を受けている気がします。

ソフトウェア (ハヤカワ文庫 SF ラ 3-1)

いつか読むはずっとよまない：柔らかな死

もっと直接的にこのことを中心に据えた「柔らかな死（Soft Death）」という短編もあります。

このご時世、このことに触れた記事がないだろうか、と検索してみた結果…

blog.emattsan.org

…十五年前の自分の記事がヒットしました。

ラッカー奇想博覧会 (ハヤカワ文庫 SF ラ 3-7)