a* implementation in swift

main.swift
struct PriorityQueue<T> {
    private var elements: [T]
    private let priorityFunction: (T, T) -> Bool
    
    init(priorityFunction: @escaping (T, T) -> Bool) {
        self.elements = []
        self.priorityFunction = priorityFunction
    }
    
    var count: Int {
        return elements.count
    }
    
    mutating func push(_ element: T) {
        elements.append(element)
        elements.sort(by: priorityFunction)
    }
    
    mutating func pop() -> T {
        return elements.removeFirst()
    }
}

struct Graph {
    let nodes: Set<Node>
}

struct Node: Hashable {
    let x: Int
    let y: Int
    var neighbors: [Node] = []
    var gScore = Double.infinity
    var fScore = Double.infinity
    
    static func == (lhs: Node, rhs: Node) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }
}

func aStar(start: Node, goal: Node, graph: Graph) -> [Node] {
    var openSet = PriorityQueue<Node>(priorityFunction: { $0.fScore < $1.fScore })
    openSet.push(start)
    var cameFrom: [Node: Node] = [:]
    var gScore: [Node: Double] = [start: 0]
    var fScore: [Node: Double] = [start: heuristicCostEstimate(start, goal)]
    
    while !openSet.isEmpty {
        let current = openSet.pop()
        if current == goal {
            return reconstructPath(cameFrom, start, goal)
        }
        
        for neighbor in current.neighbors {
            let tentativeGScore = gScore[current]! + 1 // assuming a uniform grid with distance 1 between nodes
            if tentativeGScore < gScore[neighbor, default: Double.infinity] {
                cameFrom[neighbor] = current
                gScore[neighbor] = tentativeGScore
                fScore[neighbor] = gScore[neighbor]! + heuristicCostEstimate(neighbor, goal)
                
                if !openSet.elements.contains(neighbor) {
                    openSet.push(neighbor)
                }
            }
        }
    }
    
    return []
}

func reconstructPath(_ cameFrom: [Node: Node], _ start: Node, _ goal: Node) -> [Node] {
    var current = goal
    var path: [Node] = [current]
    while current != start {
        current = cameFrom[current]!
        path.append(current)
    }
    return path.reversed()
}

func heuristicCostEstimate(_ a: Node, _ b: Node) -> Double {
    return Double(abs(a.x - b.x) + abs(a.y - b.y))
}
2436 chars
88 lines

main.swift
let a = Node(x: 0, y: 0)
let b = Node(x: 1, y: 0)
let c = Node(x: 2, y: 0)
let d = Node(x: 0, y: 1)
let e = Node(x: 1, y: 1)
let f = Node(x: 2, y: 1)
let g = Node(x: 0, y: 2)
let h = Node(x: 1, y: 2)
let i = Node(x: 2, y: 2)

a.neighbors = [b, d]
b.neighbors = [a, c, e]
c.neighbors = [b, f]
d.neighbors = [a, e, g]
e.neighbors = [b, d, f, h]
f.neighbors = [c, e, i]
g.neighbors = [d, h]
h.neighbors = [e, g, i]
i.neighbors = [f, h]

let graph = Graph(nodes: Set([a, b, c, d, e, f, g, h, i]))

let path = aStar(start: a, goal: i, graph: graph)
print(path)
556 chars
25 lines