IA

1-hungry.coffee

_ = require('underscore')

w = (str) -> str.split(' ')

cities =
  "Arad": {name: "Arad", distance: 366, neighbors: w "Zerind Timisoara Sibiu"}
  "Bucharest": {name: "Bucharest", distance: 0, neighbors: w "Urziceni Giurgiu Pitesti Fagaras"}
  "Craiova": {name: "Craiova", distance: 160, neighbors: w "Drobeta Pitesti Rimnicu"}
  "Drobeta": {name: "Drobeta", distance: 242, neighbors: w "Mehadia Craiova"}
  "Eforie": {name: "Eforie", distance: 161, neighbors: w "Hirsova"}
  "Fagaras": {name: "Fagaras", distance: 176, neighbors: w "Sibiu Bucharest"}
  "Giurgiu": {name: "Giurgiu", distance: 77, neighbors: w "Bucharest"}
  "Hirsova": {name: "Hirsova", distance: 151, neighbors: w "Urziceni Eforie"}
  "Iasi": {name: "Iasi", distance: 226, neighbors: w "Neamt Vaslui"}
  "Lugoj": {name: "Lugoj", distance: 244, neighbors: w "Mehadia Timisoara"}
  "Mehadia": {name: "Mehadia", distance: 241, neighbors: w "Drobeta Lugoj"}
  "Neamt": {name: "Neamt", distance: 234, neighbors: w "Iasi"}
  "Oradea": {name: "Oradea", distance: 380, neighbors: w "Zerind Sibiu"}
  "Pitesti": {name: "Pitesti", distance: 100, neighbors: w "Rimnicu Bucharest Craiova"}
  "Rimnicu": {name: "Rimnicu", distance: 193, neighbors: w "Sibiu Pitesti Craiova"}
  "Sibiu": {name: "Sibiu", distance: 253, neighbors: w "Oradea Arad Rimnicu Fagaras"}
  "Timisoara": {name: "Timisoara", distance: 329, neighbors: w "Lugoj Arad"}
  "Urziceni": {name: "Urziceni", distance: 80, neighbors: w "Hirsova Vaslui Bucharest"}
  "Vaslui": {name: "Vaslui", distance: 199, neighbors: w "Urziceni Iasi"}
  "Zerind": {name: "Zerind", distance: 374, neighbors: w "Oradea Arad"}

class SortedArray
	constructor: (@f) ->
		@array = []

	add: (x) =>
		@array.push(x)
		@array = _.chain(@array).sortBy(@f).uniq().value()

	get: (i) =>
		@array[i]

h = (city) -> cities[city].distance

frontier = new SortedArray((city) -> city.distance)

node = "Arad"
while node != "Bucharest"
	for neighbor in cities[node].neighborszz
		frontier.add cities[neighbor]
	node = frontier.get(0).name
	console.log

console.log node

2-astar.coffee

_ = require('underscore')

w = (str) -> str.split(' ')
nei = (str) -> 
  str.split(' ').reduce (memo, n) ->
    [name, distance] = n.split('_')
    memo[name] = +distance
    memo
  , {}

# Preguiça de pegar todas as cidades, tirei as que não fazem diferença
cities =
  "Arad": {name: "Arad", distance: 366, neighbors: nei "Zerind_75 Timisoara_118 Sibiu_140"}
  "Bucharest": {name: "Bucharest", distance: 0, neighbors: nei "Pitesti_101 Fagaras_211"}
  "Fagaras": {name: "Fagaras", distance: 176, neighbors: nei "Sibiu_99 Bucharest_211"}
  "Oradea": {name: "Oradea", distance: 380, neighbors: nei "Zerind_71 Sibiu_151"}
  "Pitesti": {name: "Pitesti", distance: 100, neighbors: nei "Rimnicu_97 Bucharest_101"}
  "Rimnicu": {name: "Rimnicu", distance: 193, neighbors: nei "Sibiu_80 Pitesti_97"}
  "Sibiu": {name: "Sibiu", distance: 253, neighbors: nei "Oradea_151 Arad_140 Rimnicu_80 Fagaras_99"}
  "Timisoara": {name: "Timisoara", distance: 329, neighbors: nei "Arad_118"}
  "Zerind": {name: "Zerind", distance: 374, neighbors: nei "Oradea_71 Arad_75"}

class SortedArray
  constructor: (@f) ->
    @array = []

  add: (x) =>
    @array.push(x)
    @array = _.chain(@array).sortBy(@f).uniq().value()

  next: =>
    @array.shift()

h = (city) -> cities[city].distance

frontier = new SortedArray((state) -> state.total)

makeState = (previous, goto) ->
  newState =
    name: goto
    path: _.clone(previous.path)
    travelled: previous.travelled + cities[previous.name].neighbors[goto]
  newState.path.push(previous.name)
  newState.total = newState.travelled + cities[goto].distance
  newState

state = {name: "Arad", path: [], travelled: 0, total: 0}
while state.name != "Bucharest"
  for neighbor in _.keys(cities[state.name].neighbors)
    frontier.add makeState(state, neighbor)
  state = frontier.next()

console.log 'final', state