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

RubyGem 'oekaki' でアナログ時計を作ってみた

　
グラフィック機能のデモの定番である時計です。Gem 'oekaki' についてはこちら。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura
　
oekaki_sample16.rb

require 'oekaki'

Oekaki.app title: :clock do
  Oekaki::W.move(100, 100)
  
  palegreen = color(0x98 * 256, 0xfb * 256, 0x98 * 256)
  draw {clear(palegreen)}
  
  hand = proc do |r, θ, f = true|
    θ1 = PI * θ / 180
    a = Vector[sin(θ1), cos(θ1)]
    if f
      a1 = Vector[cos(θ1), -sin(θ1)]
      v1 = -a * 6 + a1 * 3
      v2 = -a * 6 - a1 * 3
      ar = []
      ar << [150 + r * a[0], 150 - r * a[1]]
      ar << [150 + v1[0], 150 - v1[1]]
      ar << [150 + v2[0], 150 - v2[1]]
      polygon(true, ar)
    else
      line(150, 150, 150 + r * a[0], 150 - r * a[1])
    end
  end
  
  timer(1000) do
    clear(palegreen)
    
    #日付と曜日の窓
    l, r = 120, 0.8
    color(0x98ff * r, 0xfbff * r, 0x98ff * r)
    rectangle(true, 150 - l / 2, 190, l, 20)
    
    d = Date.today
    color(0xffff, 0xffff, 0xffff)
    week = %w(日 月 火 水 木 金 土)
    text("%02d月%02d日 %s" % [d.month, d.day, week[d.wday]], 150 - 46, 190, 13 * 1000)
    
    #一時間を表す小さな円
    12.times do |i|
      color(0xcd * 256, 0x85 * 256, 0x3f * 256)   #peru
      θ = PI * i * 30 / 180
      circle(true, 150 + 130 * cos(θ), 150 - 130 * sin(θ), 4)
    end
    
    #針
    t = Time.now
    color(65535, 0, 0)
    hand.(100, t.sec * 6, false)    #秒針
    
    color(0, 0, 0)
    hand.(110, t.min * 6)           #長針
    hand.(90, (t.hour % 12 * 60 + t.min) * 0.5)    #短針
  end
end

　
　
※追記（2018/2/16）
日にちと曜日を表示するようにしました。

paiza オンラインハッカソン vol.1 をやってみた

前回のエントリでやったのがおもしろかったので、最初からやってみた。いつもながら Ruby です。
　
結果。

まあ悪くないのだけれど…。

いや、これは苦しみました。最初はソートしてバイナリサーチというアルゴリズムを考えていたのだけれど、バグに悩まされて挫折。もうこの方法は自分の力ではできないと諦めて、バケットソートの応用で解く攻め方に替えました。なんとかそれが上手くいったという次第。実行時間はまあまあというところらしい。コードは全然複雑でないですよね。でも、富豪プログラミング…。配列の大きさが 100万くらいなので、まあ許されるかなあ…。

コード。

n, d = gets.split.map(&:to_i)
price, target = [], []
n.times {price  << gets.to_i}
d.times {target << gets.to_i}

field = Array.new(100_0001, 0)
price.each_with_index do |x, i|
  if field[x].zero?
    field[x] = i
  elsif field[x] > 0
    field[x] = -1
  end
end

target.each do |t|
  min = Float::INFINITY
  price.size.times do |i|
    a = t - price[i]
    co = 0
    loop do
      break if co >= min
      if not field[a - co].zero? and i != field[a - co]
        min = co if min > co
        break
      else
        co += 1
        break if a - co < 0
      end
    end
    break if min.zero?    #高速化のためにあとで加えた（追記参照）
  end
  min = t if min == Float::INFINITY
  puts t - min
end

同じ値段の別商品があるというのが面倒ですよね。それなのに、同じ商品を二つ買ってはいけないという。

あ、これ、課題は通ったけれども、おかしいところがありますね。if文のところは

      if (field[a - co] > 0 and i != field[a - co]) or field[a - co] < 0

であるべきしょうね。たまたま誤った答えが出る条件ではなかったのだな。

※追記
ふと思いついて 1行付け加えたら、だいぶ高速化しました。こちらが以前で、こちらが 1行加えたあとの結果です。

paiza Online Hackathon をやってみた

もうとっくに応募は締め切られているけれど、とにかく Ruby でやってみました。
　
結果。

やったね！

コードです。

need = gets.to_i
company = gets.to_i
number, cost = [], []
company.times {|i| number[i], cost[i] = gets.split.map(&:to_i)}

h = {}
company.times do |i|
  h1 = h.dup
  h.each do |n, c|
    num = n + number[i]
    ct  = c + cost[i]
    h1[num] = ct if not h1[num] or h1[num] > ct
  end
  h1[number[i]] = cost[i]
  h = h1
end
puts h.select {|n, c| n >= need}.min {|a, b| a[1] <=> b[1]}.last

典型的な動的計画法かと思ったので、それでコーディングしました。

※追記（2017/10/18）
コードの可読性を上げました。それにともないパフォーマンスが微妙に落ちたようです（結果）。
それから下から 4行目は正しくは

  h1[number[i]] = cost[i] if not h1[number[i]] or h1[number[i]] > cost[i]

であるべきですね（結果）。コードの可読性を上げたので気がつきました。読みやすく書くというのはやはり大切ということですね。