# ProblemSolving

I cleaned the code considerably, and posted at rosettacode.

```NB. verbs and adverb
parse_table=: ;:@:(LF&= [;._2 -.&CR)
mp=: \$:~ :(+/ .*)                       NB. matrix product
min=: <./                               NB. minimum

'LINK WEIGHT'=. , (0 _ ,. 2) <;.3 y
FRONTIER=. , < {. x
GOAL=. {: x
enumerate=. 2&([\)&.>
while. FRONTIER do.
PATH=. I >@{ FRONTIER
STATE=. {: PATH
if. STATE -: GOAL do. PATH return. end.
FRONTIER=. (<<< I) { FRONTIER  NB. elision
ADJACENCIES=. (STATE = SOURCE) # SINK
FRONTIER=. FRONTIER , PATH <@,"1 0 ADJACENCIES
end.
EMPTY
)

NB. The specific problem

INPUT=: noun define
a	 b	 7
a	 c	 9
a	 f	 14
b	 c	 10
b	 d	 15
c	 d	 11
c	 f	 2
d	 e	 6
e	 f	 9
)

T=: parse_table INPUT
NODES=: ~. , NAMED_LINKS                NB. vector of boxed names
WEIGHTS=: _ ".&> _ _1 {. T
GRAPH=: NUMBERED_LINKS ,. WEIGHTS NB. GRAPH is the numerical representation

TERMINALS=: NODES (i. ;:) 'a e'

NODES {~ TERMINALS dijkstra GRAPH

Note 'Output'
┌─┬─┬─┬─┐
│a│c│d│e│
└─┴─┴─┴─┘
)
```

```NB. to do: store frontier both as priority queue and as a set.

Note 'tree_search'

The dyads are designed to take the universe as y and
as x, whatever may be appropriate.

The adverbs construct a verb from a gerund.
The verbs of the gerund need to be self consistent
with the universe.  I haven't tried other variations.

comments lie,  this note isn't current
(initialState;goal) gerund treeSearch problemSpace
gerund m shall be
isEmpty`isGoal`removeChoice`followPath
isEmpty problemSpace   Boolean determines if the problem space is empty
isGoal
removeChoice frontier  returns a (carefully selected) choice from the frontier and removes it from the frontier.

)

RomanianCities=: ;:'Arad Zerind Oradea Sibiu Fagaras Timisoara Lugoj Mehadia Drobeta Craiova RimnicuVilcea Pitesti Bucharest Giurgiu Urziceni Hirsova Eforie Vaslui Iasi Neamt'

0  1  75
0  3 140
0  5 118
1  2  71
2  3 151
5  6 111
6  7  70
7  8  75
8  9 120
9 10 146
9 11 138
3 10  80
3  4  99
4 12 211
10 11  97
11  9 138
11 12 101
12 13  90
12 14  85
14 15  98
15 16  86
14 17 142
17 18  92
18 19  87
)

NB. An admissible heuristic does not overestimate the distance to the goal.
h=: 0 : 0 NB. crow's distance heuristic from named city to Bucharest.
Zerind        374
Sibiu         253
Fagaras       176
Timisoara     329
Lugoj         244
Drobeta       242
Craiova       160
RimnicuVilcea 193
Pitesti       100
Bucharest       0
Giurgiu        77
Urziceni       80
Hirsova       151
Eforie        161
Vaslui        199
Iasi          226
Neamt         234
)

Crow=: _2({.,".&.>@{:)\;:(LF=h)}h,:' '  NB. noun, n by string;integer

NB. city Crow Heuristic Universe
NB. node heuristic_noun heuristically Universe
heuristically=: 1 : '(((] >@{:@{~ (i.~ _ 1&(,@{.)))&m)@<@toString) :: 0:'

extractCities=: 0&{::
extractPaths=: 1&{::

links=: 2&(]\>)  NB. nodes 0 3 4 12

NB. cost function
weigh=: [: +/ links@:>@[ ((i.~ _ 2&{.) { 2&{"1@]) extractPaths@] NB. path weigh Universe
steps=: #@>@[   NB. path steps Universe
AStar=: weigh + Crow heuristically

Choice=:2 : '{.@I.@(= u)@:(v"0 _)'  NB. frontier (<./)Cost steps Universe
IndexShortest=: <./ Choice steps NB. frontier IndexShortest Universe
IndexLongest=:  >./ Choice steps NB. needs all paths, works not
IndexCheapest=: <./ Choice weigh
IndexAStar=: <./ Choice (weigh + AStar)

NB. conversions to index from index or string
toString=: >@(({~ 0&+)~ :: [) extractCities   NB. 1 toString Universe
toIndex=:  (0+[) :: (]i.<@:>@[) extractCities NB. 1 toIndex Universe

Display=: smoutput@toString

ExtractFrontier=: toIndex ((I.@e.~ _ 1 ,@{. ]) { ]) extractPaths@]  NB. 'Arad'ExtractFrontier Universe

Transition=: 1&{"1@ExtractFrontier

NB. frontier is a list of boxed paths
NB. frontier Choose universe returns index of next path to follow

IsEmpty=: 0 = #
IsGoal=: 1 : (':'; 'x m&-:@toString y')
:
'`display isEmpty choose isGoal transition'=. m
'initial goal'=. x
universe=. y
frontier=. ,<initial toIndex universe
while. 0=isEmpty frontier do.
i=. frontier choose universe
path=. i >@{ frontier
state=. {: path
if. state isGoal universe do. path return. end.
frontier=. (<<<i){frontier  NB. elision
frontier=. frontier , path <@,"1 0 adjacencies
end.
EMPTY
)

g=: Display`IsEmpty`0:`('Bucharest'IsGoal)`Transition

:
'`display isEmpty choose isGoal transition'=. m
'initial goal'=. x
universe=. y
explored=. ''
frontier=. ,<initial toIndex universe
while. 0=isEmpty frontier do.
i=. frontier choose universe
path=. i >@{ frontier
state=. {: path
if. state isGoal universe do. path return. end.
frontier=. (<<<i){frontier  NB. elision
explored=. explored , state
frontier=. frontier , path <@,"1 0 unseenAdjacencies
end.
EMPTY
)

Note 'Examples'

NB. Choose cheapest from the frontier
Universe toString~   (;:'Arad Bucharest')(Display`IsEmpty`IndexCheapest`('Bucharest'IsGoal)`Transition) graphSearch Universe
Sibiu
RimnicuVilcea
Pitesti
Bucharest

NB. Choose longest from the frontier
Universe toString~ (;:'Arad Bucharest')(Display`IsEmpty`IndexLongest`('Bucharest'IsGoal)`Transition) graphSearch Universe
Zerind
Sibiu
RimnicuVilcea
Pitesti
Bucharest

NB. Choose shortest from the frontier
Universe toString~   (;:'Arad Bucharest')(Display`IsEmpty`IndexShortest`('Bucharest'IsGoal)`Transition) graphSearch Universe
Sibiu
Fagaras
Bucharest

NB. A* search, choose minimal estimated distance to goal + distance covered so far
Universe toString~ (;:'Arad Bucharest')(Display`IsEmpty`IndexAStar`('Bucharest'IsGoal)`Transition) graphSearch Universe
Sibiu
RimnicuVilcea
Pitesti
Bucharest

)
```