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]

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

GTK+ で落書き 13（Ruby）

自作の Gem 'oekaki' を使っています。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura
　

require 'oekaki'

Width, Height = 500, 400
ColorMax = 65536
R = 20

class Star
  def initialize(ob)
    @x, @y = rand(Width), rand(Height)
    @v = Vector[rand - 0.5, rand - 0.5] * (rand + 2) * 4
    @θ = 0
    @f = (rand < 0.5) ? 1 : -1
    @slot = ob
    @color = @slot.color(rand(ColorMax), rand(ColorMax), rand(ColorMax))
  end
  
  def draw
    x1 = @x + R * cos(@θ)
    y1 = @y - R * sin(@θ)
    @slot.star(true, @x, @y, x1, y1, @color)
    
    @x += @v[0]
    @y += @v[1]
    @x = Width  + R if @x < -R
    @y = Height + R if @y < -R
    @x = -R if @x > Width  + R
    @y = -R if @y > Height + R
    
    @θ += @f * PI * 10 / 180
  end
end


Oekaki.app width: Width, height: Height do
  draw {clear}
  
  stars = []
  timer(50) do
    clear

    stars << Star.new(self) if stars.size <= 40 and rand < 0.1
    stars.each(&:draw)
  end
end

星形を描くメソッド star を使っています。

斜方投射の数値計算と描画（Ruby）

4次のルンゲ−クッタ法の練習としてやってみました。斜方投射（斜め上にものを投げるということです）じゃ全然威力を発揮しないのですが、とりあえず動くかどうかだけ確かめました。描画は gnuplot でやっています。
　

　
runge_kutta_sample1.rb

require 'numo/gnuplot'
require 'matrix'

def runge_kutta(f, dt, x, v, t, m)    #x, v は Vector, f[x, v, t] は Vector を返す
  k1 = v * dt
  l1 = f[x, v, t] * dt / m
  k2 = (v + l1 / 2) * dt
  l2 = f[x + k1 / 2, v + l1 / 2, t + dt / 2] * dt / m
  k3 = (v + l2 / 2) * dt
  l3 = f[x + k2 / 2, v + l2 / 2, t + dt / 2] * dt / m
  k4 = (v + l3) * dt
  l4 = f[x + k3, v + l3, t + dt] * dt / m
  
  nx = x + (k1 + 2 * k2 + 2 * k3 + k4) / 6
  nv = v + (l1 + 2 * l2 + 2 * l3 + l4) / 6
  
  [nx, nv]
end

g = 9.80665
m = 1.0
x = Vector[0.0, 0.0]
v = Vector[1.0, 1.0]
f = lambda {|x, v, t| Vector[0, -m * g]}
dt = 0.001

t = 0
ax, ay = [], []
while x[1] >= 0
  nx, nv = runge_kutta(f, dt, x, v, t, m)
  ax << x[0]
  ay << x[1]
  x, v = nx, nv
  t += dt
end

Numo.gnuplot do
  unset :key
  plot ax, ay, w: :l
end
gets    #終了待ち

初期値はいい加減に設定したのですが、グラフを見ると 5cm くらいの高さまでしか上がらないですね（笑）。初速はだいたい 1.5m/s くらいなのですが、これは時速 5km くらい（おおよそ人の歩く速さ）で、これが小さすぎるのですね。高校生で速い球を投げる人だと時速 100km 以上出るので、それくらいにしてみると（斜めに投げ上げても）高さ 20m くらいまで上がります。また、80m くらい先まで飛びます。なお、物理を知っている人には自明ですが、これらは球の質量には関係しません。重い球だろうが軽い球だろうが関係ないのですね。不思議ですか？　このプログラムで実際に質量 m の値を変えてやれば、はっきりとわかります。
　
空気抵抗を入れてみます。はっきりとグラフに出るよう、非常に強く効かせています。力を次の関数で与えます。

f = lambda {|x, v, t| Vector[0, -m * g] - v * 10}

グラフはこんな風になります。なかなか飛ばない感じが出ているでしょうか。

　
Ruby の Vector クラスはじつに手軽ですね。こういうことに使うにはすばらしいと思います。以上は 2次元でやっていますが、このまま 1次元でも 3次元でも動きます。
　

※参考
運動方程式の数値計算法（pdf）