added algorithms

brice-allen · Oct 10, 2021 · 99bd6a4 · 99bd6a4
1 parent 806b6a9
commit 99bd6a4
Show file tree

Hide file tree

Showing 6 changed files with 439 additions and 0 deletions.
diff --git a/astar/astar.go b/astar/astar.go
@@ -0,0 +1,42 @@
+package astar
+
+import (
+	"container/heap"
+	_ "fmt"
+	"github.com/brice-allen/csci4202/priorityQueue"
+	"github.com//brice-allen/csci4202/search"
+	"github.com/brice-allen/csci4202/utils"
+	//"time"
+)
+
+func Solve(start search.State, goal [][]int) (*search.State, int, int) {
+	var frontier, expanded int
+	states := make(map[string]search.State)
+	pq := make(priorityQueue.PriorityQueue, 0)
+	key := utils.BoardStringer(start.Board)
+	states[key] = start
+	heap.Push(&pq, &priorityQueue.Item{Value: key, Priority: 0, Index: 0})
+
+	for pq.Len() != 0 {
+		//time.Sleep(100 * time.Millisecond)
+		currentItem := heap.Pop(&pq).(*priorityQueue.Item)
+		current := states[currentItem.Value]
+		expanded++
+		//utils.StatePrinter(current.Board)
+		//fmt.Println(current.Distance)
+		if current.IsGoal(goal) {
+			//solved
+			return &current, frontier, expanded
+		}
+		for _, next := range current.PossibleMoves() {
+			//implement key of state to keep in heap
+			key := utils.BoardStringer(next.Board)
+			if old, exists := states[key]; !exists || next.Distance < old.Distance {
+				states[key] = next
+				heap.Push(&pq, &priorityQueue.Item{Value: key, Priority: next.Distance + next.NumMoves, Index: 0})
+				frontier++
+			}
+		}
+	}
+	return nil, frontier, expanded
+}
diff --git a/bfs/bfs.go b/bfs/bfs.go
@@ -0,0 +1,41 @@
+package bfs
+
+import (
+	_ "fmt"
+	"github.com/brice-allen/csci4202/search"
+	"github.com/brice-allen/csci4202/utils"
+	//"time"
+)
+
+func Solve(start search.State, goal [][]int) (*search.State, int, int) {
+	var frontier, expanded int
+	states := make(map[string]search.State)
+	var stack []string
+	key := utils.BoardStringer(start.Board)
+	states[key] = start
+	stack = append(stack, key)
+	for len(stack) != 0 {
+		//time.Sleep(100 * time.Millisecond)
+		currentItem := stack[0]
+		stack[0] = ""
+		stack = stack[1:]
+		current := states[currentItem]
+		expanded++
+		//utils.StatePrinter(current.Board)
+		//fmt.Println(current.Distance)
+		if current.IsGoal(goal) {
+			//solved
+			return &current, frontier, expanded
+		}
+		for _, next := range current.PossibleMoves() {
+			//implement key of state to keep in heap
+			key := utils.BoardStringer(next.Board)
+			if _, exists := states[key]; !exists {
+				states[key] = next
+				stack = append(stack, key)
+				frontier++
+			}
+		}
+	}
+	return nil, frontier, expanded
+}
diff --git a/input.txt b/input.txt
@@ -0,0 +1,3 @@
+7 2 4
+5 0 6
+8 3 1
diff --git a/priorityQueue/priorityQueue.go b/priorityQueue/priorityQueue.go
@@ -0,0 +1,52 @@
+package priorityQueue
+
+import (
+	"container/heap"
+)
+
+// An Item is something we manage in a priority queue.
+type Item struct {
+	Value    string // The value of the item; arbitrary.
+	Priority int    // The priority of the item in the queue.
+	// The index is needed by update and is maintained by the heap.Interface methods.
+	Index int // The index of the item in the heap.
+}
+
+// A PriorityQueue implements heap.Interface and holds Items.
+type PriorityQueue []*Item
+
+func (pq PriorityQueue) Len() int { return len(pq) }
+
+func (pq PriorityQueue) Less(i, j int) bool {
+	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
+	return pq[i].Priority < pq[j].Priority
+}
+
+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)
+	item := x.(*Item)
+	item.Index = n
+	*pq = append(*pq, item)
+}
+
+func (pq *PriorityQueue) Pop() interface{} {
+	old := *pq
+	n := len(old)
+	item := old[n-1]
+	item.Index = -1 // for safety
+	*pq = old[0 : n-1]
+	return item
+}
+
+// update modifies the priority and value of an Item in the queue.
+func (pq *PriorityQueue) update(item *Item, value string, priority int) {
+	item.Value = value
+	item.Priority = priority
+	heap.Fix(pq, item.Index)
+}
diff --git a/search/search.go b/search/search.go
@@ -0,0 +1,164 @@
+package search
+
+import (
+	"math"
+
+	"github.com/brice-allen/csci4202/utils"
+)
+
+/////////END STACK DEFs
+type State struct {
+	Board    [][]int
+	NumMoves int
+	Parent   *State
+	LastMove Direction
+	Distance int
+}
+
+type Direction int
+
+const (
+	None  Direction = 0
+	Up    Direction = 1
+	Down  Direction = 2
+	Left  Direction = 3
+	Right Direction = 4
+)
+
+const SizeX = 3
+const SizeY = 3
+
+//////COMPARES
+
+func FindEmptyTile(board [][]int) (int, int) {
+	for y0 := 0; y0 < 3; y0++ {
+		for x0 := 0; x0 < 3; x0++ {
+			if board[y0][x0] == 0 {
+				return x0, y0
+			}
+		}
+	}
+	return -1, -1
+}
+
+////////ACTIONS
+func MoveUp(board [][]int, emptyX int, emptyY int) ([][]int, int, int) {
+	newBoard := make([][]int, 3)
+	for i := 0; i < 3; i++ {
+		newBoard[i] = make([]int, 3)
+	}
+	utils.CopySlice(newBoard, board)
+	if emptyY > 0 {
+		newBoard[emptyY-1][emptyX], newBoard[emptyY][emptyX] = newBoard[emptyY][emptyX], newBoard[emptyY-1][emptyX]
+		return newBoard, emptyX, emptyY - 1
+	}
+	return board, emptyX, emptyY
+}
+
+func MoveDown(board [][]int, emptyX int, emptyY int) ([][]int, int, int) {
+	newBoard := make([][]int, 3)
+	for i := 0; i < 3; i++ {
+		newBoard[i] = make([]int, 3)
+	}
+	utils.CopySlice(newBoard, board)
+	if emptyY < 2 {
+		newBoard[emptyY+1][emptyX], newBoard[emptyY][emptyX] = newBoard[emptyY][emptyX], newBoard[emptyY+1][emptyX]
+		return newBoard, emptyX, emptyY + 1
+	}
+	return board, emptyX, emptyY
+
+}
+
+func MoveLeft(board [][]int, emptyX int, emptyY int) ([][]int, int, int) {
+	newBoard := make([][]int, 3)
+	for i := 0; i < 3; i++ {
+		newBoard[i] = make([]int, 3)
+	}
+	utils.CopySlice(newBoard, board)
+	if emptyX > 0 {
+		newBoard[emptyY][emptyX-1], newBoard[emptyY][emptyX] = newBoard[emptyY][emptyX], newBoard[emptyY][emptyX-1]
+		return newBoard, emptyX - 1, emptyY
+	}
+	return board, emptyX, emptyY
+
+}
+
+func MoveRight(board [][]int, emptyX int, emptyY int) ([][]int, int, int) {
+	newBoard := make([][]int, 3)
+	for i := 0; i < 3; i++ {
+		newBoard[i] = make([]int, 3)
+	}
+	utils.CopySlice(newBoard, board)
+	if emptyX < 2 {
+		newBoard[emptyY][emptyX+1], newBoard[emptyY][emptyX] = newBoard[emptyY][emptyX], newBoard[emptyY][emptyX+1]
+		return newBoard, emptyX + 1, emptyY
+	}
+	return board, emptyX, emptyY
+
+}
+
+//check possible moves to create children
+func (s State) PossibleMoves() []State {
+	x, y := FindEmptyTile(s.Board)
+	goal := utils.FillGoal()
+	moves := make([]State, 0, 4)
+
+	if y > 0 {
+		newBoard, _, _ := MoveUp(s.Board, x, y)
+		moves = append(moves, State{Board: newBoard, NumMoves: s.NumMoves + 1, Parent: &s, LastMove: Up, Distance: ManhattanDistance(newBoard, goal)})
+	}
+	if y < 2 {
+		newBoard, _, _ := MoveDown(s.Board, x, y)
+		moves = append(moves, State{Board: newBoard, NumMoves: s.NumMoves + 1, Parent: &s, LastMove: Down, Distance: ManhattanDistance(newBoard, goal)})
+	}
+	if x > 0 {
+		newBoard, _, _ := MoveLeft(s.Board, x, y)
+		moves = append(moves, State{Board: newBoard, NumMoves: s.NumMoves + 1, Parent: &s, LastMove: Left, Distance: ManhattanDistance(newBoard, goal)})
+	}
+	if x < 2 {
+		newBoard, _, _ := MoveRight(s.Board, x, y)
+		moves = append(moves, State{Board: newBoard, NumMoves: s.NumMoves + 1, Parent: &s, LastMove: Right, Distance: ManhattanDistance(newBoard, goal)})
+	}
+	return moves
+
+}
+
+////BEGINING & END
+func NewState(board [][]int, goal [][]int) State {
+	return State{Board: board, Distance: ManhattanDistance(board, goal)}
+}
+
+func (s State) IsGoal(goal [][]int) bool {
+	for y0 := 0; y0 < 3; y0++ {
+		for x0 := 0; x0 < 3; x0++ {
+			if s.Board[y0][x0] != goal[y0][x0] {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+/////HEURISTIC METHODS
+func ManhattanDistance(board [][]int, goal [][]int) int {
+	var dx, dy int
+	var sum int
+	sum = 0
+	for y0 := 0; y0 < 3; y0++ {
+		for x0 := 0; x0 < 3; x0++ {
+			for y1 := 0; y1 < 3; y1++ {
+				for x1 := 0; x1 < 3; x1++ {
+					if board[y0][x0] == goal[y1][x1] && board[y0][x0] != 0 {
+						dx = int(math.Abs(float64(x0 - x1)))
+						dy = int(math.Abs(float64(y0 - y1)))
+						sum = sum + dx + dy
+						//fmt.Printf("x0: %d, y0:%d, sta: %d,,y0:%d,x0:%d,goa:%d\n", x0, y0, board[y0][x0], x1, y1, goal[y1][x1])
+						//fmt.Printf("dx:%d,dy:%d,sum:%d\n", dx, dy, sum)
+					}
+				}
+			}
+
+		}
+	}
+	return sum
+}
-Original file line number
+Diff line change
@@ -0,0 +1,3 @@
+2 4
+0 6
+3 1