Instantly share code, notes, and snippets.

# touyou/GreedyMaze.swift

Created November 12, 2017 04:05
Show Gist options
• Save touyou/062592225d8ba66617de84f2ee1cb882 to your computer and use it in GitHub Desktop.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // A*探索で5パズル（スライドパズルの簡易版） use std::cmp::Ordering; use std::collections::BinaryHeap; use std::collections::HashMap; use std::vec::Vec; use std::usize; // Utility // print board // 6 is empty fn print_board(board: &mut [usize; 6]) { println!("{0} | {1} | {2}", board[0]+1, board[1]+1, board[2]+1); println!("{0} | {1} | {2}\n", board[3]+1, board[4]+1, board[5]+1); } // Heuristic Method fn h(board: &mut [usize; 6]) -> usize { let mut ret = 0; for i in 0..6 { if board[i] != i { ret += 1; } } ret } // Priority Queue // Including puzzle state as hash value const FACTOR: [usize; 6] = [1, 1, 2, 6, 24, 120]; fn gen_hash(board: &mut [usize; 6]) -> usize { let value = board; for i in 0..6 { for j in (i+1)..6 { if value[j] > value[i] { value[j] -= 1; } } } let mut hash = 0; for i in 0..6 { hash += value[i] * FACTOR[5-i]; } for i in (0..6).rev() { for j in (i+1)..6 { if value[i] <= value[j] { value[j] += 1; } } } hash } fn dehash(key: usize) -> [usize; 6] { let mut board = [0; 6]; let mut mkey = key; for i in 0..6 { board[i] = mkey / FACTOR[5-i]; mkey %= FACTOR[5-i]; } for i in (0..6).rev() { for j in (i+1)..6 { if board[i] <= board[j] { board[j] += 1; } } } board } #[derive(Copy, Clone, Eq, PartialEq)] struct State { cost: usize, position: usize, } impl Ord for State { fn cmp(&self, other: &State) -> Ordering { let other_cost = other.cost + h(&mut dehash(other.position)); let self_cost = self.cost + h(&mut dehash(self.position)); other_cost.cmp(&self_cost) .then_with(|| self.position.cmp(&other.position)) } } impl PartialOrd for State { fn partial_cmp(&self, other: &State) -> Option { Some(self.cmp(other)) } } // A* Search fn aster_search(start: usize, goal: usize) -> Option { let mut dist = HashMap::new(); let mut heap = BinaryHeap::new(); let movable: [Vec; 6] = [vec![1, 3], vec![0, 2, 4], vec![1, 5], vec![0, 4], vec![1, 3, 5], vec![2, 4]]; dist.insert(start, 0 as usize); heap.push(State { cost: 0, position: start }); while let Some(State { cost, position }) = heap.pop() { if position == goal { return Some(cost) } if let Some(&dcost) = dist.get(&position) { if cost > dcost { continue; } } let mut current_board = &mut dehash(position); let mut empty_pos = 9; for i in 0..6 { if current_board[i] == 5 { empty_pos = i; break; } } println!("cost: {}---", cost); print_board(&mut *current_board); for &adj in &movable[empty_pos] { current_board.swap(adj, empty_pos); let next = State { cost: cost + 1, position: gen_hash(&mut current_board) }; if let Some(&dcost) = dist.get(&next.position) { if next.cost < dcost { heap.push(next); dist.insert(next.position, next.cost); } } else { heap.push(next); dist.insert(next.position, next.cost); } current_board.swap(adj, empty_pos); } } None } fn main() { let mut start: [usize; 6] = [3, 2, 4, 1, 0, 5]; let mut goal: [usize; 6] = [0, 1, 2, 3, 4, 5]; if let Some(ret) = aster_search(gen_hash(&mut start), gen_hash(&mut goal)) { println!("result is {}", ret); } else { println!("not found valid solution"); } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // Dijkstraで迷路探索 package main import ( "container/heap" "fmt" ) type Node struct { dist int name int index int } type Edge struct { cost int to int } // Priority Queue type PriorityQueue []*Node func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[i].dist } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) node := x.(*Node) node.index = n *pq = append(*pq, node) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] item.index = -1 *pq = old[0 : n-1] return item } func (pq *PriorityQueue) update(node *Node, dist int, name int) { node.dist = dist node.name = name heap.Fix(pq, node.index) } // Dijkstra var names = [10]string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"} var dist [10]int var G [10][]Edge func makeMap() { G[0] = []Edge{Edge{cost: 1, to: 1}, Edge{cost: 2, to: 3}} G[1] = []Edge{Edge{cost: 1, to: 0}, Edge{cost: 2, to: 2}} G[2] = []Edge{Edge{cost: 2, to: 1}, Edge{cost: 1, to: 6}} G[3] = []Edge{Edge{cost: 2, to: 0}, Edge{cost: 1, to: 4}} G[4] = []Edge{Edge{cost: 1, to: 3}, Edge{cost: 2, to: 5}} G[5] = []Edge{Edge{cost: 2, to: 4}, Edge{cost: 1, to: 6}} G[6] = []Edge{Edge{cost: 1, to: 5}, Edge{cost: 1, to: 2}, Edge{cost: 1, to: 7}} G[7] = []Edge{Edge{cost: 1, to: 6}, Edge{cost: 1, to: 8}, Edge{cost: 2, to: 9}} G[8] = []Edge{Edge{cost: 1, to: 7}} G[9] = []Edge{Edge{cost: 2, to: 7}} } func dijkstra(s int) { for i := 0; i < 10; i++ { dist[i] = 10000000000000 } dist[s] = 0 pq := make(PriorityQueue, 0) heap.Init(&pq) heap.Push(&pq, &Node{dist: 0, name: s}) for pq.Len() > 0 { node := heap.Pop(&pq).(*Node) v := node.name d := node.dist if dist[v] < d { continue } fmt.Printf("%s: %d\nnext is ", names[v], d) for i := 0; i < len(G[v]); i++ { e := G[v][i] fmt.Printf("%s ", names[e.to]) if dist[e.to] > dist[v]+e.cost { dist[e.to] = dist[v] + e.cost heap.Push(&pq, &Node{dist: dist[e.to], name: e.to}) } } fmt.Printf("\n") } } func main() { makeMap() dijkstra(0) for i := 0; i < len(names); i++ { fmt.Printf("%s: %d\n", names[i], dist[i]) } fmt.Printf("\nresult is %d\n", dist[9]) }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 貪欲最適探索で迷路探索 import Foundation class Maze { struct Point: Comparable, Equatable { let x: Int let y: Int let label: String let connectedLabel: [String] var manhattan: Int { get { return abs(self.x - 3) + abs(self.y - 3) } } init(x: Int, y: Int, label: String, connectedLabel: [String]) { self.x = x self.y = y self.label = label self.connectedLabel = connectedLabel } func connectedPoints(_ points: [Point]) -> [Point] { return connectedLabel.map { label in points.filter({ \$0.label == label }).first! } } static func < (lhs: Point, rhs: Point) -> Bool { return lhs.manhattan < rhs.manhattan } static func == (lhs: Point, rhs: Point) -> Bool { return lhs.manhattan == rhs.manhattan } } var mazeMap: [Point]! var closedList: [Point]! var openList: [Point]! func makeMap() { mazeMap = [] mazeMap.append(Point(x: 1, y: 0, label: "A", connectedLabel: ["B", "D"])) mazeMap.append(Point(x: 0, y: 0, label: "B", connectedLabel: ["A", "C"])) mazeMap.append(Point(x: 0, y: 2, label: "C", connectedLabel: ["B", "G"])) mazeMap.append(Point(x: 3, y: 0, label: "D", connectedLabel: ["A", "E"])) mazeMap.append(Point(x: 3, y: 1, label: "E", connectedLabel: ["D", "F"])) mazeMap.append(Point(x: 1, y: 1, label: "F", connectedLabel: ["E", "G"])) mazeMap.append(Point(x: 1, y: 2, label: "G", connectedLabel: ["C", "H"])) mazeMap.append(Point(x: 1, y: 3, label: "H", connectedLabel: ["I", "J"])) mazeMap.append(Point(x: 0, y: 3, label: "I", connectedLabel: ["H"])) mazeMap.append(Point(x: 3, y: 3, label: "J", connectedLabel: ["H"])) } func search(_ cur: Point, cost: Int) -> Int { print("\(cur.label): \(cur.manhattan)") print("searching...") let nextList = cur.connectedPoints(mazeMap).filter({ point in !self.closedList.contains(where: { \$0.label == point.label }) }) openList = (nextList + openList).unique print("openList \(openList ?? [])") let next = openList.min()! closedList.append(next) openList = openList.filter { \$0.label != next.label } if next.label == "J" { return cost + abs(cur.x - next.x) + abs(cur.y - next.y) } return search(next, cost: cost + abs(cur.x - next.x) + abs(cur.y - next.y)) } } extension Array where Element == Maze.Point { var unique: [Element] { var r = [Element]() for i in self { r += !r.contains(where: { \$0.label == i.label }) ? [i] : [] } return r } } func main() { let maze = Maze() maze.makeMap() maze.closedList = [maze.mazeMap[0]] maze.openList = [] let result = maze.search(maze.mazeMap[0], cost: 0) print("result: \(result)") } main()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # モンテカルロ法での円周率 #! /usr/bin/env python # -*- coding: utf-8 -*- import numpy as np import numpy.random as random def monte_carlo(n): # random number rx = random.rand(n) * 2.0 - 1.0 ry = random.rand(n) * 2.0 - 1.0 cnt = 0 for (x, y) in zip(rx, ry): if x ** 2.0 + y ** 2.0 <= 1.0: cnt += 1 return cnt * 4.0 / n for n in [100, 1000, 10000, 100000, 1000000, 10000000]: print(n,monte_carlo(n),sep=': ')