最長共通部分列（Ruby）

文字列の「部分列」とは、文字列から任意の文字を取り除いたものをいう。文字列 X と Y があって、文字列 Z が X と Y 両方の部分列になっている場合、Z を X, Y の「共通部分列」という。共通部分列の最長のものが、「最長共通部分列」である。たとえば文字列 CATCGA と GTACCGTCA の最長共通部分列は CTCA である。

これを Ruby で求めるプログラムを書きました。
LCS.rb

def compute_LCS_table(x, y)
  l = Array.new(x.length + 1) {Array.new(y.length + 1, 0)}
  1.upto(x.length) do |i|
    1.upto(y.length) do |j|
      l[i][j] = if x[i - 1] == y[j - 1]
        l[i - 1][j - 1] + 1
      else
        a, b = l[i][j - 1], l[i - 1][j]
        (a > b) ? a : b
      end
    end
  end
  l
end

def assemble_LCS(x, y, l, i, j)
  return "" if l[i][j].zero?
  if x[i - 1] == y[j - 1]
    assemble_LCS(x, y, l, i - 1, j - 1) + x[i - 1]
  elsif l[i][j - 1] > l[i - 1][j]
    assemble_LCS(x, y, l, i, j - 1)
  else
    assemble_LCS(x, y, l, i - 1, j)
  end
end


x, y = "CATCGA", "GTACCGTCA"
l = compute_LCS_table(x, y)
puts assemble_LCS(x, y, l, x.length, y.length)    #=>CTCA

ここで最初に compute_LCS_table で求めている l[i][j] は、文字列 x[0..(i - 1)], y[0..(j - 1)] の最長共通部分列の長さです。これは動的計画法で求めています。それから assemble_LCS で実際の最長共通部分列を求め直しています。
　

アルゴリズムの基本

Ruby で迷路作成（コンソール版）

ここでグラフィカルな迷路を生成してみたのですが、やっぱりコンソール版も欲しいよねということで作りました。
　
こんな感じ。

*****************************************
*           *   *   *   *   * *         *
*** * * * ***** * ***** * *** ******* ***
*   * * * *       * * *       *   *     *
******* * * ******* * *** *** * *** *** *
*   *   *               * * * *   * *   *
*** ******* * * ***** ***** * * ***** ***
*     *   * * * *         * *     *   * *
* ******* *** *** ******* * *** * *** * *
*             *     *         * * *     *
* ***** * *** ******* * * *** * ***** ***
*   * * * * *     * * * *   *           *
*** * * * * * ***** * *** * ***** *** ***
*     * * *   *       *   *     * *     *
*****************************************

どうですかね。

コード。
maze_another.rb

class Maze
  def initialize(x, y)
    raise "maze size error" unless x.odd? and y.odd? and x >= 5 and y >= 5
    @x, @y = x, y
    
    @field = Array.new(y) {Array.new(x, 0)}
    co = 1
    1.step(y - 2, 2) do |j|
      1.step(x - 2, 2) {|i| @field[j][i] = co; co += 1}
    end
    
    @a, @b = (x - 3) / 2, (y - 3) / 2
    @lx, @ly = @a * (@b + 1), (@a + 1) * @b
    @remain_wall = (0...(@lx + @ly)).to_a
  end
  
  def generate
    break_wall until finish
    @field
  end
  
  def break_wall
    wall = @remain_wall[rand(@remain_wall.size)]
    @remain_wall.delete(wall)
    if wall < @lx
      x, y = wall % @a * 2 + 2, wall / @a * 2 + 1
      return if (m = @field[y][x - 1]) == (n = @field[y][x + 1])
    else
      wall -= @lx
      x, y = wall % (@a + 1) * 2 + 1, wall / (@a + 1) * 2 + 2
      return if (m = @field[y - 1][x]) == (n = @field[y + 1][x])
    end
    @field[y][x] = m
    m, n = n, m if m > n
    replace(m, n)
  end
  
  def replace(m, n)
    1.upto(@y - 2) do |y|
      1.upto(@x - 2) {|x| @field[y][x] = m if @field[y][x] == n}
    end
  end
  
  def finish
    a = @field[1][1]
    1.step(@y - 2, 2) do |j|
      1.step(@x - 2, 2) {|i| return false if @field[j][i] != a}
    end
    true
  end
end

def show_maze(field)
  field.each do |line|
    puts line.map {|x| x.zero? ? "*" : " "}.join
  end
end


field = Maze.new(41, 15).generate
show_maze(field)

迷路の生成と表示は分けています。アルゴリズムは前回と同じで、ここのそれを使わせていただきました。なお、迷路の大きさ（Maze.new(x, y) の x, y）は 5 以上の奇数にして下さい。

Swift のクロージャと Ruby の lambda

ここで Swift におけるクロージャの使い方が説明されています。

こちらで同じ内容のコードを再掲するとこんな感じでしょうか。Swift 4.0。

func f(_ a: Int, _ b: Int, _ closure: (Int, Int) -> Int) -> Int { 
    return closure(a, b) 
} 

print(f(1, 2, {a, b in return a + b}))    //=>3
print(f(1, 2, {$0 + $1}))    //=>3
print(f(1, 2, +))            //=>3

print(f(1, 2) {a, b in return a + b})     //=>3

func addNumber(_ number: Int) -> () -> Int {
    var sum = 0
    func add() -> Int {
        sum += number
        return sum
    }
    return add
}

let addTen = addNumber(10)
print(addTen())    //=>10
print(addTen())    //=>20

let addSeven = addNumber(7)
print(addSeven())  //=>7
print(addSeven())  //=>14
print(addTen())    //=>30

　
これらは Ruby の lambda でも基本的に同じことができます。Ruby の lambda はもちろんクロージャで、第一級関数（first class の関数）ですからね。つまり、変数に代入したり、関数の引数になったり返り値になったりできます。

f = ->(a, b, closure) {closure[a, b]}

p f[1, 2, ->(a, b) {a + b}]    #=>3


add_number = ->(number) {
  sum = 0
  -> {sum += number}
}

add_ten = add_number[10]
p add_ten[]    #=>10
p add_ten[]    #=>20

add_seven = add_number[7]
p add_seven[]  #=>7
p add_seven[]  #=>14
p add_ten[]    #=>30

Ruby の簡潔さがここでも出ているのではないでしょうか。

同じことはもちろん JavaScript でも Python でも可能です。

しかし、Swift はいい言語ですね。ここでも見られるように、 Ruby の「ブロック」と同等の機能を、Ruby と同じくらい可読性の高い形で書けるというのはすばらしい。クロージャの中に引数を書くのは、Swift の開発者の言っているとおり、Ruby のパクリですね。いや、上手くパクったと思います。それから、この記事とは関係ないですが、Swift の「オプショナル型」は Ruby にはないものですね。Ruby で nil 関連のエラーは結構よく出るので、「オプショナル型」ってのはいい考えに思えます。もちろんより安全性が高まるというのはより面倒になるということで、Swift の融通の効かなさがかなわないこともありますが、これは盾の両面で、どちらかというと Swift のこの点の面倒さは大規模開発とかに有利に効いてくるでしょう。Ruby も nil の安全性を高めるためにいわゆる「ぼっち演算子」（safe navigation operator）を導入したくらいですし。

Ruby の lambda についてはこちらも。

Swift でエラトステネスの篩

こんな感じ。
eratosthenes.swift

func eratosthenes(_ n: Int) -> [Int] {
    var ar = Array(0...n)
    for i in 2...Int(sqrt(Double(n))) {
        if ar[i] == 0 {continue}
        for j in 2...(n / i) {ar[i * j] = 0}
    }
    return ar.filter {$0 != 0}
}

print(eratosthenes(1000))

　
1000万までの素数を求めてみました（出力はしていません）。Swift 4.0, Linux Mint 18.2。

$ time ./eratosthenes

real	0m6.161s
user	0m6.108s
sys	0m0.052s

6秒もかかっていますね。Ruby版よりも遅いですよ？　Ruby版の倍も時間がかかっています。どういうこと？　アルゴリズムは Ruby と同じです。なお、インタプリタで実行しても時間はほとんど変わりません。何かおかしいですね。

ちなみに C言語だとこの 1/10 の時間しかかかりません。

※追記
遅い理由がわかりました。Swift の Array はそのままでは遅いらしいです。コンパイル時に -O オプションを付けて最適化してやる必要があります。

$ swiftc eratosthenes.swift -O
$ time ./eratosthenes

real	0m0.234s
user	0m0.196s
sys	0m0.016s

今度は C言語よりも速くなりました！　しかしあまりにも数値がちがいすぎますね。

Linux Mint（Ubuntu）で Swift 4.0 を使う

Linux ユーザーですが Swift が使いたい。これまで Swift は 3.1-dev を使っていたのですが、折角 4.0 があるので使ってみることにしました。ちょっとハマったところがあったので記しておきます。なお、面倒なので暗号鍵を使ったデジタル署名版ではありません。その方がよろしい方は本家のドキュメントを見て下さい。Linux Mint 18.2 で確認しました。たぶん Ubuntu でもそのままいけると思います。
　
ここから Swift 4.0 Ubuntu 16.10 をダウンロードします（上記のとおり、Signature でない方）。で、基本的には解凍して好きな場所に置くだけです。ただし、

$ sudo apt-get install clang libicu-dev

をしていない方はしておいて下さい。あとは、僕の環境なら

$ ~/Documents/Swift/usr/bin/swift

みたいな感じで REPL が立ち上がります。詳細はここと同じなので、よろしければ参考にして下さい。

自分がハマったのは、$ swift としても

swift: /usr/lib/x86_64-linux-gnu/libstdc++.so.6: version `GLIBCXX_3.4.22' not found (required by swift)

というエラーが出ることです。確かに、

$ strings /usr/lib/x86_64-linux-gnu/libstdc++.so.6 | grep GLIBCXX

とすると GLIBCXX_3.4.22 はありません。gcc のビルドが必要らしく、困ったなと思ったのですが、

$ sudo add-apt-repository ppa:ubuntu-toolchain-r/test

としてリポジトリを追加したあと、アップデートマネージャでシステムの更新をしたら OK でした。

まだあります。今度は $ swift -v とやっても

$ swift -v
Swift version 4.0 (swift-4.0-RELEASE)
Target: x86_64-unknown-linux-gnu
/home/***/Documents/Swift/usr/bin/lldb "--repl=-disable-objc-interop -color-diagnostics"
error: failed to stop process at REPL breakpoint

というエラーがでます。インタプリタで適当なプログラムを実行すると

<unknown>:0: error: could not load the swift standard library

と出ます。何かライブラリが足りないようです。コンパイルは出来るので実行ファイルを実行してみたところ、

$ ./qsort
./qsort: error while loading shared libraries: libicuuc.so.57: cannot open shared object file: No such file or directory

となるのがヒントになりました。libicuuc.so.57 というのが足りないのですね。では $ sudo apt-get install libicu-dev かなと思ったのですが、libicu-dev は最新バージョンのようです。

ここで、このページが役に立ちました。ここから libicu57_57.1-6_amd64.deb をダウンロードしてきます。あるいは

$ wget http://ftp.us.debian.org/debian/pool/main/i/icu/libicu57_57.1-6_amd64.deb

でも OK です。そして

$ sudo dpkg -i libicu57_57.1-6_amd64.deb

をすれば解決の筈。実際に swift のインタプリタが動けば（あるいはコンパイルして実行できれば）終了です。お疲れ様でした。

最終的に

$ swift -v
Swift version 4.0 (swift-4.0-RELEASE)
Target: x86_64-unknown-linux-gnu
/home/***/Documents/Swift/usr/bin/lldb "--repl=-disable-objc-interop -color-diagnostics"
Welcome to Swift version 4.0 (swift-4.0-RELEASE). Type :help for assistance.

となりました。OK ですね！

Swift で 8queen 問題を解く

以前 Ruby で「エイト・クイーン」問題を解きましたが、それを Swift に移植してみました。「エイト・クイーン」というのは

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3

というものです。すべての解（92個）を求めています。Linux Mint 18.2, Swift 3.1-dev。

実行するとこんな感じ。

$ time ./eight_queen
@.......
......@.
....@...
.......@
.@......
...@....
.....@..
..@.....
------------
@.......
......@.
...@....
.....@..
.......@
.@......
....@...
..@.....
------------

（省略）

------------
.......@
.@......
...@....
@.......
......@.
....@...
..@.....
.....@..
------------

92 answers.

real	0m0.056s
user	0m0.052s
sys	0m0.000s

　
コード。

import Glibc

let N = 8

class Step {
    var x: Int, y: Int
    var parent: Step?
    var depth: Int
    
    init(_ x1: Int, _ y1: Int) {
        (x, y) = (x1, y1)
        parent = nil
        depth = 0
    }
}

func solve(x: Int, y: Int) {
    var stack = Array(arrayLiteral: Step(x, y))
    while !stack.isEmpty {
        let a = stack.removeLast()
        let y = a.y + 1
        let board = get_board(a)
        for x in 0..<N {
            if board[y][x] == 1 {continue}
            let next = Step(x, y)
            next.parent = a
            next.depth  = a.depth + 1
            if next.depth == N - 1 {
                answer(next)
            } else {
                stack.append(next)
            }
        }
    }
}

func get_board(_ a1: Step) -> [[Int]] {
    var board = [[Int]](repeating: [Int](repeating: 0, count: N), count: N)
    var a: Optional = a1
    while a != nil {
        for i in 0..<N {
            board[i][a!.x] = 1
            if i == a!.y {board[i] = [Int](repeating: N, count: N)}
            let d = abs(i - a!.y)
            let x1 = a!.x - d
            let x2 = a!.x + d
            if x1 >= 0 {board[i][x1] = 1}
            if x2 <  N {board[i][x2] = 1}
        }
        a = a!.parent
    }
    return board
}

func answer(_ a1: Step) {
    var bd = [String](repeating: "........", count: N)
    var a: Optional = a1
    while a != nil {
        var st = "......."
        st.insert("@", at: st.index(st.startIndex, offsetBy: a!.x))
        bd[a!.y] = st
        a = a!.parent
    }
    bd.forEach {print("\($0)")}
    print("------------")
    num += 1
}

var num = 0
for i in 0..<N {solve(x: i, y: 0)}
print("\n\(num) answers.")

Swift はまだ全然慣れていないので、移植するだけなのに時間がかかってしまいました。普段は Ruby を使っているので、Swift の文字列処理の貧弱さには悩みました。それから、Optional型は Ruby にはないのでだいぶハマりました。深さ優先探索も最初どうやってコーディングしたらいいかわからなかったです。ただ、コンパイルが通ればおおよそ OK というのはさすがに静的型付け言語ですね。自分は Ruby で軽く実装してみて Swift に移植というのがよさそうです。

ちなみに、ベンチマークをとってみると Ruby よりべら棒に速いというほどでもないですね。このコードではせいぜい Ruby の二倍の速さくらいです。Swift らしく書けばまたちがうのかも知れません。
（追記：最適化オプションをつけてコンパイルすると、もう少し速くなります。Ruby版の三倍くらい。）
　
　
※参考
どこよりも分かりやすいSwiftの"?"と"!" - Qiita
Swift 2.0 で追加された guard のいいところ - Qiita
String - Swift Standard Library | Apple Developer Documentation

Swift でクイックソート

extension Array where Element == Int {
    func qsort() -> [Int] {
        if self.isEmpty {return []}
        var xs = self
        let pivot = xs.removeFirst()
        let left  = xs.filter({$0 < pivot})
        let right = xs.filter({$0 > pivot})
        return left.qsort() + Array(arrayLiteral: pivot) + right.qsort()
    }
}

print([5, 1, 3, 9, 8, 7].qsort())    //=>[1, 3, 5, 7, 8, 9]

Swift 3.1-dev.
　
※参考
Swift 練習 - Marginalia