Hatena::Groupcoders

ラシウラ出張所 このページをアンテナに追加 RSSフィード

2007/06/10

[] RunHaskell moduleデモ  RunHaskell moduleのデモ - ラシウラ出張所 を含むブックマーク はてなブックマーク -  RunHaskell moduleのデモ - ラシウラ出張所  RunHaskell moduleのデモ - ラシウラ出張所 のブックマークコメント

で書いたような

  result = RunHaskell.run do
    main!(:mfoldr, "[]", [1,2,3]).where(%q{
      mfoldr = foldr (\elem bot -> "[" ++ (show elem) ++ ", " ++ bot ++ "]")
    })
  end

という感じで使えるもの。

とりあえず版だけど、show出力はパーズしてRubyオブジェクトにしてる。

require "tempfile"

module RunHaskell

  class HsRunner
    @@command = "runhaskell"
    def run(source)
      file = Tempfile.new "runhaskell"
      fname = file.path + ".hs"
      File.rename file.path, fname
      hsfile = File.new(fname, "w")
      hsfile.puts(source)
      hsfile.close
      io = IO.popen(@@command + " " + hsfile.path)
      result = io.read()
      io.close
      File.unlink hsfile.path
      result
    end
  end

  class HsParser
    def initialize(code)
      @code = code
      @index = 0
      @tokens = []
      tokenize
    end
    def parse()
      tok = shift
      case tok[0]
      when :numeric
        return HsNumeric.new(eval(tok[1]))
      when :string
        return HsString.new(eval(tok[1]))
      when :identifier
        return HsData.new(tok[1].to_sym, parse())
      when :lparen
        elems = []
        while true
          elem = parse()
          break if elem == nil
          elems << elem
          tok = shift
          case tok[0]
          when :rparen
            break
          when :comma
            next
          else
            unshift tok
            return nil
          end
        end
        return HsTuple.new(elems)
      when :lbracket
        elems = []
        while true
          elem = parse()
          break if elem == nil
          elems << elem
          tok = shift
          case tok[0]
          when :rbracket
            break
          when :comma
            next
          else
            unshift tok
            return nil
          end
        end
        return HsList.new(elems)
      when :lbrace
        elems = {}
        while true
          tok = shift
          unless tok[0] == :identifier
            unshift tok
            break
          end
          key = tok[1]
          tok = shift
          unless tok[0] == :equal
            unshift tok
            return nil
          end
          elem = parse()
          break if elem == nil
          elems[key] = elem
          tok = shift
          case tok[0]
          when :rbracket
            break
          when :comma
            next
          else
            unshift tok
            return nil
          end
        end
        return HsRecordPart.new(elems)
      else
        unshift tok
        return nil
      end
      nil
    end

    def tokenize
      while @index < @code.size
        token =  next_token(@code[(@index)..-1])
        @index += token[1].size
        @tokens << token unless token[0] == :space
      end
    end
    def shift()
      @tokens.shift
    end
    def unshift(token)
      @tokens.unshift token
    end

    def next_token(code)
      case code
      when /^(\s+)/
        [:space, $1]
      when /^(\{)/
        [:lbrace, $1]
      when /^(\})/
        [:rbrace, $1]
      when /^(\[)/
        [:lbracket, $1]
      when /^(\])/
        [:rbracket, $1]
      when /^(\()/
        [:lparen, $1]
      when /^(\))/
        [:rparen, $1]
      when /^([,])/
        [:comma, $1]
      when /^([=])/
        [:equal, $1]
      when /^([A-Za-z_][A-Za-z0-9_]*)/
        [:identifier, $1]
      when /^([-+]?[0-9]+([.][0-9]+)?(e[0-9]+)?)/
        [:numeric, $1]
      when /^(\"(\\\"|[^"])*\")/
        [:string, $1]
      end
    end
  end

  class HsNumeric
    def initialize(str)
      @core = str
    end
    def to_hs
      @core.to_s
    end
    def to_rb
      @core
    end
  end
  class HsString
    def initialize(str)
      @core = str
    end
    def to_hs
      core = @core.to_s.sub("\\", "\\\\")
      core = core.sub("\"", "\\\"")
      core = core.sub("\n", "\\n")
      core = core.sub("\r", "\\r")
      core = core.sub("\t", "\\t")
      core = core.sub("\b", "\\b")
      result = "\"" + core + "\""
      result
    end
    def to_rb
      @core
    end
  end
  class HsList
    def initialize(array)
      @core = array
    end
    def to_hs
      result = "["
      i = 0
      @core.each do |elem|
        i += 1
        result += elem.to_hs
        result += ", " unless i == @core.size
      end
      result += "]"
      result
    end
    def to_rb
      result = []
      @core.each do |elem|
        result << elem.to_rb
      end
      result
    end
  end
  class HsTuple
    def initialize(array)
      @core = array
    end
    def to_hs
      result = "("
      i = 0
      @core.each do |elem|
        i += 1
        result += elem.to_hs
        result += ", " unless i == @core.size
      end
      result += ")"
      result
    end
    def to_rb
      result = []
      @core.each do |elem|
        result << elem.to_rb
      end
      result
    end
  end
  class HsData
    def initialize(name, child)
      @name = name
      @child = child
    end
    def to_hs
      result = @name.to_s
      result += @child.to_hs unless @child
      result
    end
    def to_rb
      @child.to_rb unless @child
    end
  end
  class HsRecordPart
    def initialize(child)
      @child = child
    end
    def to_hs
      result = "{"
      i = 0
      @core.each do |key, elem|
        i += 1
        result += key.to_s + " = " + elem.to_hs
        result += ", " unless i == @core.size
      end
      result += "}"
      result
    end
    def to_rb
      result = {}
      @core.each do |key, elem|
        result[key] = elem.to_rb
      end
      result
    end
  end

  class Source
    def initialize(source="")
      @source = source
      @main = nil
    end
    def main!(name, *args)
      @main = Decl.new(:main)
      body = "putStrLn.show $ " + name.to_s
      args.each do |arg|
        body += " " + arg.to_hs
      end
      body += "\n"
      @main.body = body
      @main
    end
    def to_s
      source = @source
      source += "\n" + @main.to_s if @main
      source
    end
  end

  class Decl
    def initialize(name, *args)
      @name = name
      @args = args
      @body = ""
      @where = nil
    end
    attr_accessor :body
    def where(source)
      @where = source
    end
    def to_s
      result = @name.to_s
      @args.each do |arg|
        result += " " + arg.to_hs
      end
      result += " = " + @body
      if @where
        result += " where \n"
        result += @where
      end
      result
    end
  end

  def self.run(code="", &block)
    src = Source.new code
    src.instance_eval(&block) if block
    runner = HsRunner.new
    result = runner.run(src.to_s)
    parser = RunHaskell::HsParser.new(result)
    parser.parse.to_rb
  end
end

class String
  def to_hs
    RunHaskell::HsString.new(self).to_hs
  end
end
class Numeric
  def to_hs
    RunHaskell::HsNumeric.new(self).to_hs
  end
end
class Array
  def to_hs
    hs_list.to_hs
  end
  def hs_list
    RunHaskell::HsList.new(self)
  end
  def hs_tuple
    RunHaskell::HsTuple.new(self)
  end
end
class Hash
  def hs_data(name)
    RunHaskell::HsData.new(name, RunHaskell::HsRecordPart.new(self))
  end
end
class Symbol
  def to_hs
    self.to_s
  end
end

2007/06/06

[] A* アルゴリズム完全版  A* アルゴリズム完全版 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  A* アルゴリズム完全版 - ラシウラ出張所  A* アルゴリズム完全版 - ラシウラ出張所 のブックマークコメント

コード片の全体です。Java 6でかいてます。

ただし、PointやFieldの具体型を作ると、キャストで警告が出るのがいやだったので、全部genericsに書き換えました。generic typeの配列はnew T[]すると警告が出るので、そのへんも全部List<T>に書き換えることになりました。余計なところで複雑になっている。計算機科学教育Javaを避けるようになったのもわかる気がします。

Point.java

// 位置
public interface Point {
    // 同値判定できる必要がある
    boolean equals(Object point);
    int hashCode();
}

これだけは変わってません。

Field.java

import java.util.*;

// マップ
public interface Field<TPoint extends Point> {
    // その位置に入れるかどうか
    boolean canWalkIn(TPoint point);
    // その位置に隣接する位置一覧
    List<TPoint> neighbors(TPoint point);
    // その位置の目標からのスコア。
    // パスが伸びればその合計スコアは増えるように、正の整数である
    int score(TPoint goal, TPoint point);
}

Listが入り、ジェネリクス化しました。でもまだまだ単純です。

Solver.java

import java.util.*;

public interface Solver<TPoint extends Point, TField extends Field<TPoint>> {
    List<TPoint> calc(TField map, TPoint start, TPoint goal);
}

GenericsGenericsで使うとクラスの型宣言は長くなります。<TField extends Field<TPoint extends Point>> って書きたいところだけど無理っぽい。

AStar.java

import java.util.*;

class AStar<TPoint extends Point, TField extends Field<TPoint>>
    implements Solver<TPoint, TField> {
    public List<TPoint> calc(TField map, TPoint start, TPoint goal) {
        // 再入、並行実行可能にするためインスタンス生成し、実行
        return new AStar<TPoint, TField>().solve(map, start, goal);
    }
    
    private List<TPoint> solve(TField map, TPoint start, TPoint goal) {
        this.map = map;
        this.goal = goal;
        visitedCache = new HashSet<TPoint>();
        pathes = new ArrayList<ScoredPath>();

        // 初期ポイント: (0, [start])
        visitedCache.add(start);
        ArrayList<TPoint> path = new ArrayList<TPoint>();
        path.add(start);
        ScoredPath spath = new ScoredPath(0, path);
        pathes.add(spath);

        return astar();
    }

    private List<TPoint> astar() {
        while (pathes.size() > 0) {
            // 一番スコアの低いパスを取り出し進める
            ScoredPath spath = pathes.remove(0);
            TPoint current = spath.path.get(spath.path.size() - 1);
            // ゴールに着いていたら終了
            if (current.equals(goal)) {
                return spath.path;
            }
            for (TPoint next: map.neighbors(current)) {
                // すでに通ってたらスルー
                if (visitedCache.contains(next)) continue;
                // 通ったことにする
                visitedCache.add(next);
                // 入れなければスルー
                if (!map.canWalkIn(next)) continue;
                // パスに追加し、そのパスのスコアを計算
                ArrayList<TPoint> path = new ArrayList<TPoint>(spath.path);
                path.add(next);
                int score = spath.score + map.score(goal, next);
                // スコア順になるよう、この新たなパスを挿入
                insert(score, path);
            }
        }
        // もう行ける場所がなく、到達不能。
        return null;
    }

    private void insert(int score, ArrayList<TPoint> path) {
        for (int i = 0; i < pathes.size(); i += 1) {
            ScoredPath spath = pathes.get(i);
            if (spath.score >= score) {
                pathes.add(i, new ScoredPath(score, path));
                return;
            }
        }
        pathes.add(new ScoredPath(score, path));
    }
    private TField map;
    private TPoint goal;
    private ArrayList<ScoredPath> pathes;
    private Set<TPoint> visitedCache;

    private class ScoredPath {
        ScoredPath(int score, ArrayList<TPoint> path) {
            this.score = score;
            this.path = path;
        }
        int score;
        ArrayList<TPoint> path;
    }
}

手続きメインなので、ほとんど変わらないけど、privateとか入れたので、地味にめんどくさくなってます。結局、警告の出ないtoArrayの使い方がわからなかったのでList化したのです。

以下は2DでのPointやFieldの実装です。

Point2D.java

座標としてxとyを持った単純なポイントです。

public class Point2D implements Point {
    public Point2D(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public boolean equals(Object o) {
        if (o instanceof Point2D) {
            Point2D p = (Point2D) o;
            return p.x == x && p.y == y;
        }
        return false;
    }
    public int hashCode() {
        return x + y;
    }
    public int x() { return x;}
    public int y() { return y;}
    private int x;
    private int y;
}

情報隠蔽はきちっとしておきました。

equalsのなかでキャストを使ってますが、この場合は警告は出ないようです。

Field2D.java

有限マップです。A*自体はスコアリングがしっかりしてれば無限境界のマップでもいけるはずですが、今回は表示の簡略化(回り込まれると面倒なので)と、壁を省略するため、境界壁の構造にしてます。

import java.util.*;

public class Field2D implements Field<Point2D> {
    public Field2D(String[] data, int width) {
        this.data = data.clone();
        this.width = width;
        this.height = data.length / width;
    }

    public boolean canWalkIn(Point2D point) {
        if (0 <= point.x() && point.x() < width &&
            0 <= point.y() && point.y() < height &&
            " ".equals(get(data, point))) return true;
        return false;
    }

    public List<Point2D> neighbors(Point2D point) {
        List<Point2D> result = new ArrayList<Point2D>(4);
        result.add(new Point2D(point.x() - 1, point.y()));
        result.add(new Point2D(point.x() + 1, point.y()));
        result.add(new Point2D(point.x(), point.y() - 1));
        result.add(new Point2D(point.x(), point.y() + 1));
        return result;
    }

    public int score(Point2D goal, Point2D point) {
        return Math.abs(point.x() - goal.x()) +
            Math.abs(point.y() - goal.y());
    }
    
    public Field2D walk(List<Point2D> path) {
        String[] newData = data.clone();
        for (Point2D point: path) {
            set(newData, point, "*");
        }
        return new Field2D(newData, width);
    }

    public void print() {
        printWall();
        for (int y = 0; y < height; y += 1) {
            System.out.print("#");
            for (int x = 0; x < width; x += 1) {
                Point2D point = new Point2D(x, y);
                System.out.print(get(data, point));
            }
            System.out.println("#");
        }
        printWall();
    }

    private void printWall() {
        for (int x = 0; x < width + 2; x += 1) {
            System.out.print("#");
        }
        System.out.println();
    }

    private void set(String[] data, Point2D point, String value) {
        data[point.y() * width + point.x()] = value;
    }

    private String get(String[] data, Point2D point) {
        return data[point.y() * width + point.x()];
    }

    private String[] data;
    private int width;
    private int height;
}

スコアはgoalからの絶対距離です。壁は無視します。

それ以降はユーティリティです。walkはパスをたどって、マークをつけたマップを返します。printマップを壁付きで標準出力に出します。

cloneで代入してもキャストが不要なのはちょっとだけいいかもしれません。

Main.java

例題実行します。

import java.util.*;

class Main {
    public static void main(String[] args) {
        String[] mapData = new String[] {
            " ", " ", " ", " ", " ",
            " ", " ", " ", " ", " ",
            "#", "#", "#", "#", " ",
            " ", " ", " ", " ", " ",
            "#", "#", " ", "#", "#",
            " ", "#", " ", " ", " ",
            " ", "#", "#", " ", " ",
            " ", " ", " ", " ", " ",
            " ", " ", " ", " ", " ",
        };
        int width = 5;
        Field2D map = new Field2D(mapData, width);
        System.out.println("[source map]");
        map.print();

        Point2D start = new Point2D(1, 1);
        Point2D goal = new Point2D(0, 5);

        AStar<Point2D, Field2D> astar = new AStar<Point2D, Field2D>();
        List<Point2D> path = astar.calc(map, start, goal);
        Field2D walked = map.walk(path);

        System.out.println("[result map]");
        walked.print();
    }
}

実行結果

$ java Main
[source map]
#######
#     #
#     #
##### #
#     #
### ###
# #   #
# ##  #
#     #
#     #
#######
[result map]
#######
#     #
# ****#
#####*#
#  ***#
###*###
#*#** #
#*##* #
#**** #
#     #
#######