2015-06-25

atomのMarkdown Previewのフォント設定

atom markdown

atomエディタのMarkdownプレビューのCSS設定がいつの間にか変わっていたのでメモ。

目的は日本語のフォントにしたい。デフォルトだと中国系だからね

検索するといくつか出てくるけど、 setting -> Open Config Folder で、 styles.less を修正する。

/*
* Your Stylesheet
*
* This stylesheet is loaded when Atom starts up and is reloaded automatically
* when it is changed.
*
* If you are unfamiliar with LESS, you can read more about it here:
* http://www.lesscss.org
*/

.tree-view {
     font-family: "Migu 1C", sans-serif;
}

// Markdown Preview
.markdown-preview {
     font-family: "Migu 1C", sans-serif;
     h1, h2, h3, h4, h5, h6 {
          font-family: "Migu 1C", sans-serif;
     }
     code, blockquote, atom-text-editor {
          font-family: "Migu 1M", "Meiryo", monospace;
     }
}

.tree-view はどこのことかわからないのでとりあえず書いただけだけど、重要なのは .markdown-preview って方。

ここに font-family で好きなフォントを指定。これで基本的には変わるんだけど、コード部分とかのバッククォート部分が変わらない。

なのでmarkdown-previewのスタイルを確認。

<a href="https://github.com/atom/markdown-preview/blob/master/styles/markdown-preview.less">atom/markdown-preview</a>github.com

code とか blockquote とかが怪しいと思い追加してみるも変わらなかった。
結果的には atom-text-editor ってのがコード部分らしい。

まあ、とりあえず全部書いておいた。

2015-05-19

Python入門のためtoolz入れてみた

python toolz

pythonは文法が単純で覚えやすいらしい。

class MyClass:
  def __init__(self, init_value):
    self.value = init_value
  def my_method(self, value):
    return self.value + value

instance = MyClass(5)
print instance.my_method(3) # => 8
print MyClass.my_method(instance, 3) # => 8

あと、なんか特別な意味を持つメソッドは全部 __???__ みたいに _ 2つで囲まれてるらしい。

ということで入門。
細かいことを気にせずtoolzというライブラリを入れる。

・・・ために準備

pyenvのインストール

pythonはシステムに食い込んでいるらしいので、別のpythonを気軽にいじれるツールを導入。

> git checkout https://github.com/yyuu/pyenv.git ~/.pyenv
> echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
> echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
> echo 'eval "$(pyenv init -)"' >> ~/.bash_profile

if文とかは適当に。

> git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
> echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile

ローカルpythonのインストール

好きなバージョンのpythonをインストールできる。今回はやむにやまれぬ事情で2系

> pyenv install 2.7.9
> pyenv virtualenv 2.7.9 my-env-name-2.7.9

上がpythonのインストールで、下が依存ライブラリが入る環境のインストール。プロジェクト毎に依存関係を分けるためのやつ。

で、あとは自分のプロジェクトフォルダを作って、バージョン指定

> mkdir /my/project/root/dir
> cd /my/project/root/dir
> pyenv local my-env-name-2.7.9

最後の指定を行うことで、このディレクトリでのpythonが自動的に指定したバージョンになる。

pythonを使ってみる。

何はともあれtoolzをインストール。

> pip install toolz
> pip freeze > freeze

これで my-env-name-2.7.9 にだけtoolzが入ったはず。 python コマンドでpython インタープリターを起動し試してみる。

>>> import toolz
>>> toolz.map(lambda x: x + 1, [1, 3, 5, 7, 9])
<itertools.imap object at 0x7f3cfdf1af90>
>>> for a in toolz.map(lambda x: x + 1, [1, 3, 5, 7, 9]):
...   print a
...
2
4
6
8
10
>>> exit()

ひとつ上のディレクトリーに移動して、同じく実行。

>>> import toolz
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ImportError: No module named toolz
>>> exit()

いい感じ。

あと、ファイルにコードを書くときのshebangはenvを使わないといけないみたいなので注意。

#! /usr/bin/env python
# coding: utf-8

toolzを使ってみる。

toolzは難しいプログラミングを簡単にしてくれるためのツールで、swiftzみたいなものらしい。

さっき使ったmapなど、遅延実行してくれるのででっかいファイルの処理するのに使用した。

>>> infile = open('inflie.txt', 'r')
>>> lines = toolz.map(some_function, infile)
>>> outfile1 = open('outfile1.txt', 'w')
>>> outfile2 = open('outfile2.txt', 'w')
>>> for line in lines:
...   if some_condition(line):
...     outfile1.write(line)
...   else:
...     outfile2.write(line)
...
>>> outfile2.close()
>>> outfile1.close()
>>> infile.close()

まあtryとかは適時使用するとして、こんな感じでやった時に、for式のlineを取り出した段階で初めて some_function が実行される。

toolz.map で帰ってくる itertools.imap object ってやつは1回しか評価できない。やっててこれでハマった。 list(map(f, [1, 2, 3])) とかすればlist化できるけど、これだと普通の組み込みのmapでいい気がするし、どうするのがベストなんだろう？

で、ここで問題はコードに出てきた some_function 。 map の第1引数は引数を1個とって戻り値も1個の関数なので、複雑な処理をしようと思うと長い複雑な関数が必要になる。

関数合成

それは困るので、toolzを使って関数の合成。

>>> a = lambda x: x + 1
>>> b = lambda x: x * 3
>>> c = lambda x: x - 2
>>> x = toolz.compose(a, b, c)
>>> x(3) # == a(b(c(3)))
4

これで複数の関数をつなげて実行できるんだけど、どうも使いづらい。だって、aから並べたらaから実行してほしいじゃない？

これに近い関数にpipeがある。

>>> toolz.pipe(2, a, b, c) # == c(b(a(2)))
7

でもこれは可変長引数の関係からか評価する値を先に書かなくちゃダメ。仕方がないので新しい関数を定義してみた。

def chainf(*f):
  from toolz import pipe
  return lambda x: pipe(x, *f)

>>> x = chainf(a, b, c)
>>> x(2) # == c(b(a(2)))
7

これ、元からあるなら誰か教えて。。。

複数の関数がつなげられるようになったので、次の問題に挑戦。

部分適用

map は引数1の戻り値1なので、二つの引数を受け取るような関数が使えない。

これを解決するためには、部分適用を使用する。そうすればテストするときは関数単位でテストできるし、合成もできるので便利なはず。

def with_contains(values, target):
  if target in values:
    return (target, True)
  else:
    return (target, False)

この例だとif文いらないけど、まあもう少し複雑な前提で。

これを toolz.map で使って各値をtupleにしたいと。まあ、lambdaとか使ってvaluesを固定してしまえばいいんだけど、toolzには便利な curry があるので使おう。

>>> w = toolz.curry(with_contains) # w(values)(target) == with_contains(values, target)
>>> x = w([1, 2, 3])
>>> x(2)
(2, True)
>>> x(4)
(4, False)

curry は複数引数の関数を1引数で1戻り値(関数が帰ってくる)の関数に変えた関数を返してくれる。

>>> uc = lambda a, b, c, d: a + b + c + d
>>> cd = curry(uc) # uc(a, b, c, d) == cd(a)(b)(c)(d)

これで1引数まで持っていければ、小さなテスト済みの関数の組み合わせで最初の map が実行できる。

もちろんoutputのファイルに書き込む部分も関数化できるんだけど、テスト方法がよくわからないからループしてログに書くだけにした。

toolz.do とかを使えば処理自体は難しくないんだけど、ファイル出力のテストってどうやるのかがわからない。

テストの書き方勉強会とかないかなぁ。

2015-04-30

ハノイの塔をScalaで解く

scala TailRec

ハノイの塔自体は再帰を使えば簡単に解けることは有名で、Googleれば大体すぐ出てくる。

def hanoi(height: Int, from: String, via: String, to: String): Unit = {
  if (height <= 0) {
    ()
  } else {
    // 1. スタート位置にある一番下以外のものをすべて関係のない場所に動かして
    hanoi(height - 1, from, to, via)
    // 2. スタート位置にある一番下を目的地に動かして
    println(s"Move disk ${height} from ${from} to ${to}.")
    // 3. `1`で関係のないところによけておいたものを全て目的地に移動させる。
    hanoi(height - 1, via, from, to)
  }
}

> hanoi(3, "left", "middle", "right")
Move disk 1 from left to right.
Move disk 2 from left to middle.
Move disk 1 from right to middle.
Move disk 3 from left to right.
Move disk 1 from middle to left.
Move disk 2 from middle to right.
Move disk 1 from left to right.

ただ、このままだと末尾再帰でないという理由でいつかはスタックが足りなくなるはず。それより前に計算量が大きすぎて帰ってこなくなりそうな気もするけど。。。

ということで末尾再帰にしたい！たぶん。

関数らしくするために、値を返そう。

case class HanoiStep(height: Int, from: String, via: String, to: String)
def hanoi1(height: Int, from: String, via: String, to: String) = (HanoiStep, String, HanoiStep) = {
  val pre = HanoiStep(height - 1, from, to, via)
  val move = s"Move disk ${height} from ${from} to ${to}."
  val post = HanoiStep(height - 1, via, from, to)
  (pre, move, post)
}

Tree構造！！

自分でprintすべきものがrootにあって、左に自分より前にprintすべきものの塊、右に自分より後のがある。

左の枝、自分自身、右の枝の順で走査していけば結果になるはず！！

・・・Treeの走査って再帰でどうやるのん？？？わからないから後で考えるとして、一番左の要素だけ展開すれば末尾再帰できるはずだからそれをやろう。

import scala.annotation.tailrec

sealed trait HanoiStep
case class MultiSteps(height: Int, from: String, via: String, to: String) extends HanoiStep
case class SingleStep(id: Int, from: String, to: String) extends HanoiStep

def expand(ms: MultiSteps): List[HanoiStep] = ms.height match {
  case n if n <= 0 => List.empty
  case 1 => List(SingleStep(1, ms.from, ms.to))
  case _ => {
    val pre = MultiSteps(ms.height - 1, ms.from, ms.to, ms.via)
    val ss = SingleStep(ms.height, ms.from, ms.to)
    val post = MultiSteps(ms.height - 1, ms.via, ms.from, ms.to)
    List(pre, ss, post)
  }
}

@tailrec
def expandHead(ss: List[HanoiStep]): List[HanoiStep] = ss match {
  case ((h: MultiSteps) :: t) => expandHead(expand(h) ++ t)
  case _ => ss
}

> val a = MultiSteps(5, "left", "middle", "right")
a: MultiSteps = MultiSteps(5,left,middle,right)

> val b = expand(a)
b: List[HanoiStep] = List(MultiSteps(4,left,right,middle), SingleStep(5,left,right), MultiSteps(4,middle,left,right))

> val c = expandHead(b)
c: List[HanoiStep] = List(SingleStep(1,left,right), SingleStep(2,left,middle), MultiSteps(1,right,left,middle), ....

これをとりあえずStreamでくるめば、それっぽくは動きそう。

def unfold[A, B](a: A)(f: A => Option[(B, A)]): Stream[B] = f(a) match {
  case Some((b, a)) => Stream.cons(b, unfold(a)(f))
  case _ => Stream.empty
}

def hanoi(height: Int, from: String, via: String, to: String): Stream[String] = {
  import scala.annotation.tailrec
  sealed trait HanoiStep
  case class MultiSteps(height: Int, from: String, via: String, to: String) extends HanoiStep
  case class SingleStep(id: Int, from: String, to: String) extends HanoiStep
  def f1(ms: MultiSteps): List[HanoiStep] = ms.height match {
    case n if n <= 0 => List.empty
    case 1 => List(SingleStep(1, ms.from, ms.to))
    case _ => {
      val pre = MultiSteps(ms.height - 1, ms.from, ms.to, ms.via)
      val ss = SingleStep(ms.height, ms.from, ms.to)
      val post = MultiSteps(ms.height - 1, ms.via, ms.from, ms.to)
      List(pre, ss, post)
    }
  }
  @tailrec
  def f2(ss: List[HanoiStep]): List[HanoiStep] = ss match {
    case ((h: MultiSteps) :: t) => f2(f1(h) ++ t)
    case _ => ss
  }
  val init = f1(MultiSteps(height, from, via, to))
  unfold(init)(a => f2(a) match {
    case (h: SingleStep) :: t => Some((s"Move disk ${h.id} from ${h.from} to ${h.to}.", t))
    case _ => None
  })
}

> val a = hanoi(3, "left", "middle", "right")
a: Stream[String] = Stream(Move disk 1 from left to right., ?)

> a.foreach(println)
Move disk 1 from left to right.
Move disk 2 from left to middle.
Move disk 1 from right to middle.
Move disk 3 from left to right.
Move disk 1 from middle to left.
Move disk 2 from middle to right.
Move disk 1 from left to right.

> val b = hanoi(4, "left", "middle", "right").zipWithIndex
b: scala.collection.immutable.Stream[(String, Int)] = Stream((Move disk 1 from left to middle.,0), ?)

> val c = b.map { case (a, b) => s"${b + 1}: ${a}" }
c: scala.collection.immutable.Stream[String] = Stream(1: Move disk 1 from left to middle., ?)

> c.foreach(println)
1: Move disk 1 from left to middle.
2: Move disk 2 from left to right.
3: Move disk 1 from middle to right.
4: Move disk 3 from left to middle.
5: Move disk 1 from right to left.
6: Move disk 2 from right to middle.
7: Move disk 1 from left to middle.
8: Move disk 4 from left to right.
9: Move disk 1 from middle to right.
10: Move disk 2 from middle to left.
11: Move disk 1 from right to left.
12: Move disk 3 from middle to right.
13: Move disk 1 from left to middle.
14: Move disk 2 from left to right.
15: Move disk 1 from middle to right.

とりあえず動いた。

ツリーを走査する簡単なやり方とか、もしくは継続？かなんかのテクニックを使えばもっとシンプルになるんだろうなぁ。

続きはまた次回。

2015-04-17

MonadTって自動でMonadにはならないの？？？

scala scalaz

Monadって難しいって話。

元ネタは xuweiさんのブログ

いやね、最近PlayでWebアプリ作ろうと頑張ってるんですよ。
そこでログ出力のために、引数で渡すものを必要に応じてWriterにできればなとか考えてたんですよ。
結果うまくはいかなかったんですが。

本編以外を極力省くため、試すコードはただの足し算。

def add(a: Int, b: Int): Int = a + b

これをブログを参考にIdでくるむ。

import scalaz._, Scalaz._

def add(a: Id[Int], b: Id[Int]): Id[Int] = for {
  x <- a
  y <- b
} yield x + y

// 実行
> val a = add(1, 2)
a: scalaz.Scalaz.Id[Int] = 3

それぞれIdに入っちゃったから取り出すためのfor書いて、中の値を使って処理。

これをさらにブログに書いてある通り、任意の入れ物から取り出せるように変更。

import scalaz._, Scalaz._
import scala.language.higherKinds

def add[F[_]](a: F[Int], b: F[Int])(implicit F: Monad[F]): F[Int] = for {
  x <- a
  y <- b
} yield x + y

// 実行
> val a = add[Id](1, 2)
a: scalaz.Scalaz.Id[Int] = 3

[Id]って書かないと実行できなくなった。。。
まあそこはIdで使うかどうかなのできっと問題無いのかな？
OptionやListで渡していれば予想通りの動き。

> val a = add(1.some, 2.some)
a: Option[Int] = Some(3)

> val b = add(List(1, 3, 5), List(7, 8))
b: List[Int] = List(8, 9, 10, 11, 12, 13)

MonadTransformer使って合成

> val a = List(1, 2, 3).liftM[OptionT]
a: scalaz.OptionT[List,Int] = OptionT(List(Some(1), Some(2), Some(3)))

> val b = List(5, 7).liftM[OptionT]
b: scalaz.OptionT[List,Int] = OptionT(List(Some(5), Some(7)))

> val c = add(a, b)
error: no type parameters for method add: (a: F[Int], b: F[Int])(implicit F: scalaz.Monad[F])F[Int] exist
so that it can be applied to arguments (scalaz.OptionT[List,Int], scalaz.OptionT[List,Int])

！？！？
OptionT[List, Int]なんてMonadじゃねぇぞ！！！って言われる。なんで？なんで？

よーしパパMonadとか実装しちゃうぞー(結婚したい)

type OptionTList[A] = OptionT[List, A]
implicit val OptionTListMonad = new Monad[OptionTList] {
  def point[A](a: => A) = List(a).liftM[OptionT]
  def bind[A, B](fa: OptionTList[A])(f: A => OptionTList[B]) = fa flatMap f
}

> val c = add(a, b)
error: no type parameters for method add: (a: F[Int], b: F[Int])(implicit F: scalaz.Monad[F])F[Int] exist
so that it can be applied to arguments (scalaz.OptionT[List,Int], scalaz.OptionT[List,Int])

通らない・・・

> val c = add[OptionTList](a, b)
c: OptionTList[Int] = OptionT(List(Some(6), Some(8), Some(7), Some(9), Some(8), Some(10)))

これなら通る。つまりこう？

> val a: OptionTList[Int] = List(1, 2, 3).liftM[OptionT]
a: OptionTList[Int] = OptionT(List(Some(1), Some(2), Some(3)))

> val b: OptionTList[Int] = List(5, 7).liftM[OptionT]
b: OptionTList[Int] = OptionT(List(Some(5), Some(7)))

> val c = add(a, b)
c: OptionTList[Int] = OptionT(List(Some(6), Some(8), Some(7), Some(9), Some(8), Some(10)))

むぅー。。。
やり方を間違っている気しかしない。。。

やっぱり元ブログみたいにTraitでくるんでコンストラクターを中で呼び出さないとダメなのかな？
それとも、Monadの代わりに何かそれっぽいのがMonad Transformer用にある？？？

2015/04/23 追記 Scala勉強会にてねこはる先生に教えてもらった。

> val a = List(2, 3, 5).liftM[OptionT]
a: scalaz.OptionT[List,Int] = OptionT(List(Some(2), Some(3), Some(5)))

> val b = List(1, 9).liftM[OptionT]
b: scalaz.OptionT[List,Int] = OptionT(List(Some(1), Some(9)))

> val c = add[({type F[A] = OptionT[List, A]})#F](a, b)
c: scalaz.OptionT[[+A]List[A],Int] = OptionT(List(Some(3), Some(11), Some(4), Some(12), Some(6), Some(14))

「Scalaの型推論はオブジェクト指向的継承のために残念な部分が多い」ってのはこういうことなのかなぁ？

2015-03-08

簡単に分かるPrologの魅力

gprolog

昨日はPlayもくもく会に行ってきました。色々と教えていただいてありがとうございます。

で、その中でたまたまprologのお話になったので、
prologの魅力が簡単に分かるような「prolog向きの」サンプルを書いてみたいと思います。

ちなみに、prologは頑張れば関数型言語向きの事もそれなりに出来たりはしますが、
向き不向きが激しい言語なので使い道は選びます。

prologは「ルールは分かるけど解き方はわからない」ものを解くプログラムが簡単に書けます。

今回はルール説明が要らないであろう、「ハノイの塔」でやりたいと思います。

prologでハノイの塔

一応簡単に説明すると、地面に刺さった3本の棒といくつかの大きさの違う円盤を使ったゲームです。

円盤は左端の棒に大きいものから順に上に行くほど小さくなるように刺さっています。
プレイヤーは1回につき1枚の円盤を他の棒に移動させることができます。
ただし、円盤の上にはその円盤より大きい円盤は乗せることができません。
全ての円盤を右端の棒に移動させればゲームクリアです。

大体こんな感じのはずです。
実装にはgplorogを使います。他はわからないので。

棒の実装

難しいのは嫌なので、棒をリスト、円盤を数値にしてしまいます。円盤がゼロの棒を[]、小さい円盤がひとつささった棒を[1]、
複数個刺さっていたら[1, 2, 3]とか[2, 3, 5, 8]とかですね。

hanoi_tower([]).           % 空の塔
hanoi_tower([_|[]]).       % 1つの円盤が入った塔
hanoi_tower([H1, H2|T]) :- % 2つ以上の円盤が入った塔
  H1 < H2,
  hanoi_tower([H2|T]).

ここでやったことは単純に1本の棒の可能性を列挙しただけです。
|が最初の要素と後続のリストをわける記号になります。
lispで言うcarとcdr、haskellのheadとtailですね。 _(アンダースコア)は何らかの値が入るけど使わないので名前を付けないってやつです。

なので、棒(=hanoi_tower)は空([])か1つの円盤([_|[]])か2つ以上の円盤です。

2つ以上の時は上の円盤は下のより小さくないといけないので、大小比較をしています。
動作確認をしてみましょう。

$ gprolog --consult-file hanoi.pl

で指定したプログラムを読み取ってREPLを開けます。

| ?- hanoi_tower([]).

yes
| ?- hanoi_tower([1]).

true ? a

no
| ?- hanoi_tower([10]).

true ? a

(3 ms) no
| ?- hanoi_tower([1, 2, 3]).

true ? a

no
| ?- hanoi_tower([1, 3, 2]).

no

作れるはずのリストにtrueが返って来て居たら成功です。

棒のセットの実装

これも簡単にリストのリストで実装します。
[[1, 2, 3], [4, 5], []]こんなのです。

hanoi_set(X) :-
  X = [L, M, R],
  hanoi_tower(L),
  hanoi_tower(M),
  hanoi_tower(R).

読み方としては、

hanoi_setであるXは要素数3のリスト[L, M, R]である。
Lはhanoi_towerである。
Mはhanoi_towerである。
Rはhanoi_towerである。

こんな感じです。

同じくREPLで確認します。

| ?- hanoi_set([[1, 2, 3], [4, 5], []]).

true ? a

no
| ?- hanoi_set([[1, 3], [2, 4, 5], []]).

true ? a

no
| ?- hanoi_set([[1, 3], [2, 4, 5], [7, 6]]).

no

多分大丈夫かと。

移動ルールを実装

ついに移動ルールを実装します。
ルール名をhanoiとしましょう。引数を3つとって、元の状態、移動ルール、異動後の状態とします。

prologに慣れていないと何を言っているの？となりますが、
普通のプログラミング言語なら最後の引数は戻り値なんだと思えば大体あってると思います。

hanoi([[1, 2, 3], [], []], left_to_middle, X).

とした時に、Xに[[2, 3], [1], []]と入っていてほしいということです。

異動の種類としてはleft_to_middle, left_to_right, middle_to_left, middle_to_right, right_to_left, right_to_middleの6種類ですね。

hanoi(X, left_to_middle, Y) :-
  hanoi_set(X),
  [XL, XM, XR] = X,
  [H|T] = XL,
  Y = [T, [H|XM], XR],
  hanoi_set(Y).

Xはhanoi_setで
Xのそれぞれの列がXL, XM, XRで
XLの一番上をH, それ以外をTとした時
Yは左からT, [H|XM], XRとなっていて
Yはhanoi_setの条件を満たしている(= ルール上可能な移動である)

| ?- hanoi([[1, 2, 3], [], []], left_to_middle, Y).

Y = [[2,3],[1],[]] ? a

no
| ?- hanoi([[2, 3], [1], []], left_to_middle, Y).

no
| ?- hanoi([[], [1], []], left_to_middle, Y).

no

他もまあ同様に実装できます。(が、省略します。)

hanoi(X, left_to_right, Y) :-
hanoi(X, middle_to_left, Y) :-
hanoi(X, middle_to_right, Y) :-
hanoi(X, right_to_left, Y) :-
hanoi(X, right_to_middle, Y) :-

複数回の移動に対応する

先ほどのhanoiは移動処理が単純な変数なので、1回の移動しか表現できません。

そこで、移動処理もリストにしてみましょう。
まず、移動0回の場合は空のリスト[]で移動前と移動後が当然同じですね。

hanoi(X, [], X) :- hanoi_set(X).

それ以外の場合は、先頭の移動をやった後次の移動を実行です。
リストのリストという場合を検証しなくてよいように、リストに入れられる値を制限します。

% handを定義
hand(left_to_middle).
hand(left_to_right).
hand(middle_to_left).
hand(middle_to_right).
hand(right_to_left).
hand(right_to_middle).

hanoi(X, M, Y) :-
  maplist(hand, M), % `M`に入るのはhandを満たす値のみ。
  [H|T] = M,
  hanoi(X, H, Z),
  hanoi(Z, T, Y).

移動方法がリストだった場合は先頭をH, 残りをTとします。
Xに対し、Hという移動を実行したものをZとします。
Yは、Zに対して残りのTの移動を全部実行したものです。

| ?- hanoi([[1, 2, 3], [], []], [left_to_middle, left_to_right], Y).

Y = [[3],[1],[2]] ? a

no
| ?- hanoi([[1, 2, 3], [], []], [left_to_middle, middle_to_right], Y).

Y = [[2,3],[],[1]] ? a

no

これで、ルールの実装は大体終わった気がします。

仕上げ

さて、ここで答えを求めたいので、prologさんの性格に合わせて少しだけ手間をかけてあげます。

prologさんはすぐに無限ループをしたがるので、回数制限を設けてあげます。
考え方が面倒ですが、N回以下なら試すとしたいのでN以下の数値のリストを作るrangeを作成しましょう。

range(Min, Max, List) :-
  integer(Min),
  integer(Max),
  Min < Max,
  List = [Min|T],
  N is Min + 1,
  range(N, Max, T).
range(X, X [X]).

isという演算子が初めて出てきましたが、まあ、意味的には予想通りです。
この場合N = Min + 1とは出来ない事に注意が必要です。

これでrange(0, 5, X).でX = [0,1,2,3,4,5]が取得できます。

hanoi(X, M, N, Y) :- % 移動回数は最大N回まで
  range(0, N, R),
  hanoi(X, M, R, Y).
hanoi(X, M, [H|_], Y) :- % H回の移動で出来る組み合わせ
  length(M, H),
  hanoi(X, M, Y).
hanoi(X, M, [_|T], Y) :- 
  hanoi(X, M, T, Y).

完了です。
試してみましょう。

| ?- hanoi([[1], [], []], M, 1, [[], [], [1]]).

M = [left_to_right] ? a

(1 ms) no
| ?- hanoi([[1, 2], [], []], M, 1, [[], [], [1, 2]]).

(1 ms) no
| ?- hanoi([[1, 2], [], []], M, 2, [[], [], [1, 2]]).

no
| ?- hanoi([[1, 2], [], []], M, 3, [[], [], [1, 2]]).

M = [left_to_middle,left_to_right,middle_to_right] ? a

(2 ms) no
| ?- hanoi([[1, 2, 3], [], []], M, 7, [[], [], [1, 2, 3]]).

M = [left_to_right,left_to_middle,right_to_middle,left_to_right,middle_to_left,middle_to_righ,left_to_right] ? a

(1591 ms) no

こういう感じで結果がでます。

解き方を気にせず答えを求められるのが素晴らしいところですね。

ちなみに

このプログラムのままだと、円盤が4つ以上あるハノイの塔にチャレンジするとものすごく時間がかかります。
チューニング方は色々あるのですが、まあ、単純に可能性が無い奴はすぐエラーにしてしまうという方法で実行速度を上げることができます。

それは今回は扱わないと言うことで。

2015-02-16

emerge app-emulation/dockerとカーネルの癒着問題

gentoo docker

Dockerのインストールを試みるよ！！！

なんでDockerかと言いますと、Haskell環境がほしい！とか、LAMP環境がほしい！！とかいろいろあるものの、環境が汚れきって手に終えなくなることを経験してきたからなのです。

しかし、このDocker、なかなかに凶悪です。
インストールしようとするだけで、カーネルのコンパイルオプション変えろとおっしゃられるのです！！！

emergeすると、以下のようなメッセージを表示してくるのです。もちろん、左端の*はエラーを表す赤色です。

 *   CONFIG_NETFILTER_XT_MATCH_ADDRTYPE:         is not set when it should be.
 *   CONFIG_AUFS_FS: is required to be set if and only if aufs-sources are used
 *   CONFIG_DM_THIN_PROVISIONING:        is not set when it should be.
 * Please check to make sure these options are set correctly.

はじめのうちのエラー文はもう残してなくて申し訳ないのですが、まあ最初は○○が足りない！系で/usr/src/linux/.configにあるコメントアウトを外して=yみたいに変えてあげるだけで消えてなくなってくれたのですが、最後に残ったのは上のようなやつばかりなわけです。

そもそもCONFIG_NETFILTER_XT_MATCH_ADDRTYPEなんてないので、近そうなCONFIG_NETFILTER_XT_MATCH_で始まるやつをコメントアウトしてみたりするんだけど、 CONFIG_AUFS_FSなんかは近い奴すらなかったり、元から

# CONFIG_DM_THIN_PROVISIONING is not set

ってなってたりして、全然どう設定していいのかわからなかったりする。

でもまあ、とりあえず言われるがままに何度か足したり消したりしていたら、赤い丸印は出たままでもなぜかインストールできたっぽい。

不思議。

まだインストールしてから起動していないけれど、今日はここまで。

一応、記念に.configファイルを残しておいた。
.config(gist)

2015-02-16

Windows 7上に入れたVirtualBoxを4.3.22にバージョンアップしたらssh接続が途切れる問題に遭遇？

VirtualBox Windows 未解決

今のところ原因不明。。。

Windows 7にVirtualBoxを入れてその中のLinuxからsshでサーバーにつなぐ使い方をしていたんだけど、今日4.3.22にアップデートできますという通知が来たので軽い気持ちで上げてしまった。

別に何の問題もなく使えていたと思っていたら、なぜかよくsshが途中で切れる。

症状としては、最初の数分は普通に使えていても、突然何の入力も受け付けなく固まった状態になる。

で、数秒後に

Write failed: Broken pipe

と表示される。

このメッセージ自体は数分放置したときの自動切断などで表示されるものらしいけど、
今回は明らかに操作中に切れている。。。

ググってみたけど見つからず。

Changelog for VirtualBox
ネットワーク自体は初期設定(NAT)だし変な設定はしていないと思うんだけどなぁ。

来世から頑張る！！

技術ブログを目指して