--- /dev/null
+#!/usr/bin/env swipl
+
+:- initialization(main).
+:- dynamic neighbours/2.
+
+build_rooms:-
+ get_rooms(Rooms),
+ build_neighbours(Rooms).
+
+get_rooms(Rooms):-
+ setup_call_cleanup(
+ open('08-rooms.txt', read, In),
+ read_data(In, Rooms),
+ close(In)
+ ).
+
+
+read_data(In, L):-
+ read_line_to_codes(In, H),
+ ( H == end_of_file
+ -> L = []
+ ; L = [H|T],
+ read_data(In,T)
+ ).
+
+
+alphabet_codes(A):-
+ string_codes('abcdefghijklmnopqrstuvwxyz', A).
+
+adjacent(Word, Adjacents):-
+ length(Word, N),
+ adjacent(N, Word, Adjacents).
+
+adjacent(N, Word, SAdjacents):-
+ (N = 0 -> Adjacents = []
+ ;
+ swap_char(N, Word, NWords),
+ N1 is N - 1,
+ adjacent(N1, Word, RAdjacents),
+ append(NWords, RAdjacents, Adjacents)),
+ list_to_ord_set(Adjacents, SAdjacents).
+
+swap_char(N, Word, Swapped):-
+ alphabet_codes(As),
+ setof(W,
+ A^(member(A, As),
+ nth1(N, Word, L, Rest),
+ L \= A,
+ nth1(N, W, A, Rest)),
+ Swapped).
+
+build_neighbours(Words):-
+ build_neighbours(Words, Words).
+
+build_neighbours([], _).
+build_neighbours([Word|Words], Dictionary):-
+ adjacent(Word, Adjacents),
+ intersection(Adjacents, Dictionary, Neighbours),
+ string_codes(SWord, Word),
+ maplist(string_codes, SNeighbours, Neighbours),
+ assertz((neighbours(SWord, SNeighbours):-!)), % Need the cut to keep lookup deterministic in this dynamic predicate
+ build_neighbours(Words, Dictionary).
+
+
+
+
+extend([W|Chain], Closed, Extended):-
+ neighbours(W, Ns),
+ ord_subtract(Ns, Closed, Successors),
+ extend_chain(Successors, [W|Chain], Extended).
+
+extend_chain([], _, []).
+extend_chain([N|Ns], Chain, [[N|Chain]|Extended]):-
+ extend_chain(Ns, Chain, Extended).
+
+
+distance([], _, 0).
+distance([C|Cs], [O|Os], N):-
+ ( C == O
+ -> distance(Cs, Os, N)
+ ; distance(Cs, Os, N1),
+ N is N1 + 1).
+
+estimated_costed([W|C], Goal, N-[W|C]):-
+ length([W|C], N1),
+ string_codes(W, Cs),
+ distance(Cs, Goal, N2),
+ N is N1 + N2.
+
+estimated_costed_all([], _, []).
+estimated_costed_all([C|Cs], Goal, [A|As]):-
+ estimated_costed(C, Goal, A),
+ estimated_costed_all(Cs, Goal, As).
+
+
+astar(Start, SGoal, Path):-
+ string_codes(SGoal, Goal),
+ estimated_costed([Start], Goal, Costed),
+ astar([Costed], SGoal, Goal, [], Path).
+
+astar([], _, _, []).
+astar([_-Current|Agenda0], SGoal, Goal, Closed0, FoundPath):-
+ %% write_ln([N-Current, SGoal, Goal]),
+ ( Current = [W|_],
+ W == SGoal
+ -> FoundPath = Current
+ ; [Word|_] = Current,
+ ord_add_element(Closed0, Word, Closed),
+ extend(Current, Closed, Extended),
+ estimated_costed_all(Extended, Goal, ExtraAgenda),
+ append(ExtraAgenda, Agenda0, Agenda1),
+ keysort(Agenda1, Agenda),
+ astar(Agenda, SGoal, Goal, Closed, FoundPath)
+ ).
+
+
+reachable(Word, Steps, N):-
+ reachable(Steps, [Word], [Word], Reachable),
+ length(Reachable, ReachableN),
+ N is ReachableN - 1.
+
+
+reachable(N, Found0, Boundary0, Reachable):-
+ ( N == 0
+ -> Reachable = Found0
+ ; maplist(neighbours, Boundary0, FoundL),
+ flatten(FoundL, Found1),
+ list_to_ord_set(Found1, Boundary1),
+ ord_subtract(Boundary1, Found0, Boundary),
+ ord_union(Found0, Boundary, Found),
+ N1 is N - 1,
+ reachable(N1, Found, Boundary, Reachable)
+ ).
+
+main(_Argv):-
+ time(build_rooms),
+ time(astar("coax", "stay", P)),
+ length(P, Part1),
+ time(reachable("coax", 10, Part2)),
+
+ writef('Part 1: %w steps from coax to stay\n', [Part1]),
+ writef('Part 2: %w rooms reacable in 10 steps from coax\n', [Part2]).
{
"cell_type": "code",
"execution_count": 5,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 6,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 10,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 11,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 13,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 15,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 16,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 17,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 20,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 22,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 23,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 24,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 25,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 27,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 29,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 30,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 31,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 32,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
"cell_type": "code",
"execution_count": 33,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
{
"cell_type": "code",
"execution_count": 34,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 35,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 36,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 40,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 41,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 42,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 73,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 43,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 44,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 45,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 46,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 47,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": null,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [],
"source": [
"# %time len(bfs_search('wars', 'love'))"
{
"cell_type": "code",
"execution_count": null,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [],
"source": [
"%time len(bfs_search_closed('wars', 'love'))"
{
"cell_type": "code",
"execution_count": 50,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 51,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 52,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 53,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 54,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 55,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 56,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 57,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 58,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 59,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 60,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 66,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 67,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 68,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 69,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 70,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 71,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
{
"cell_type": "code",
"execution_count": 72,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.5.2"
+ "version": "3.5.2+"
}
},
"nbformat": 4,
{
"cell_type": "code",
"execution_count": 2,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
}
],
"source": [
- "words = [w.strip() for w in open('08-offices.txt').readlines()]\n",
+ "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
"len(words)"
]
},
{
"cell_type": "code",
"execution_count": 15,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 16,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 17,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 18,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 19,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [],
"source": [
"# len(bfs_search('vice', 'wars'))"
{
"cell_type": "code",
"execution_count": 20,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 21,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 22,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 273 µs per loop\n"
+ "10000 loops, best of 3: 153 µs per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 23,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 25.6 ms per loop\n"
+ "100 loops, best of 3: 15.7 ms per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 24,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 300 µs per loop\n"
+ "10000 loops, best of 3: 165 µs per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 25,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [],
"source": [
"# %%timeit\n",
{
"cell_type": "code",
"execution_count": 26,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 664 ms per loop\n"
+ "1 loop, best of 3: 446 ms per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 27,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 147 ms per loop\n"
+ "10 loops, best of 3: 91.4 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 52,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 29,
+ "metadata": {},
"outputs": [
{
"data": {
" 'rasp']"
]
},
- "execution_count": 52,
+ "execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 30,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
]
},
- "execution_count": 29,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 31,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '<code>bash</code>, <code>cash</code>, <code>dash</code>, <code>gash</code>, <code>hash</code>, <code>lash</code>, <code>mash</code>, <code>rasp</code>, <code>rush</code>, <code>sash</code>, <code>wash</code>')"
]
},
- "execution_count": 47,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 32,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '`base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, `wish`')"
]
},
- "execution_count": 30,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 51,
+ "execution_count": 33,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '<code>base</code>, <code>bash</code>, <code>bask</code>, <code>bass</code>, <code>bast</code>, <code>bath</code>, <code>bosh</code>, <code>bush</code>, <code>case</code>, <code>cash</code>, <code>cask</code>, <code>cast</code>, <code>dash</code>, <code>dish</code>, <code>gash</code>, <code>gasp</code>, <code>gosh</code>, <code>gush</code>, <code>hash</code>, <code>hasp</code>, <code>hath</code>, <code>hush</code>, <code>lash</code>, <code>lass</code>, <code>last</code>, <code>lath</code>, <code>lush</code>, <code>mash</code>, <code>mask</code>, <code>mass</code>, <code>mast</code>, <code>math</code>, <code>mesh</code>, <code>mush</code>, <code>push</code>, <code>ramp</code>, <code>rasp</code>, <code>ruse</code>, <code>rush</code>, <code>rusk</code>, <code>rust</code>, <code>sash</code>, <code>sass</code>, <code>tush</code>, <code>wash</code>, <code>wasp</code>, <code>wish</code>')"
]
},
- "execution_count": 51,
+ "execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 34,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"180"
]
},
- "execution_count": 31,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 35,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"2195"
]
},
- "execution_count": 32,
+ "execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 36,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"2192"
]
},
- "execution_count": 33,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 37,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 8.95 ms per loop\n"
+ "100 loops, best of 3: 5.84 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 35,
+ "execution_count": 38,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 4.14 ms per loop\n"
+ "100 loops, best of 3: 2.79 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 36,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 39,
+ "metadata": {},
"outputs": [
{
"data": {
"2188"
]
},
- "execution_count": 36,
+ "execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 40,
+ "metadata": {},
"outputs": [
{
"data": {
"2193"
]
},
- "execution_count": 37,
+ "execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 38,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 41,
+ "metadata": {},
"outputs": [
{
"data": {
"280"
]
},
- "execution_count": 38,
+ "execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 39,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 42,
+ "metadata": {},
"outputs": [
{
"data": {
"296"
]
},
- "execution_count": 39,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 40,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 43,
+ "metadata": {},
"outputs": [
{
"data": {
"text/plain": [
- "'leak drab twin glib yell jets heed prep dram step grey keep sacs hock bloc bees hews bend chit sots rent knit brat bobs news gram boot baas grad beet door keen toot mewl plus dial bows jeep boom aloe fret need foul beep brew peek veep poop blue weep akin coop lead foot deed hoot teem quit chop teed bias moor sack atop went bier vets teen pout eery leaf drag belt crag peed czar gees veil whip bout jock wees twit beck boos tell vial pees brag tout sped weed geed load book crop text deem shes mead mock very sewn feet sows cell leis dell hemp week yens than mean send chin sill reek wiry knot reed crew peps pest stem melt room coup yews dock less suck boon clef emit bras loot boob pegs pews bran thin well geek boss term pled whir feed whom rock foam dent glue mews rood goat next sort tens goop stay soft perk troy held meet fees best lees reel gent nest brow spec fest coat leek sues pier moot knob test bogs boys said heft hell flee thaw clue prom self felt hair shoe airs cent whet pock gets pent sics pelt bent club berm saws pets blur prod bops whim sick bell trap lets herd help chip loan sued pens dyer peep peel dual sits suet flue goad toad brad peck moan fell cock been whit lens leap omit wets char crow gout frog shoo nets fist root prim lean jell trig coot flea prop meek beef loam bolt chow skid chew crab floe yeps moat tram vent bets jeez soil soon yous unit newt lock bled deep fled tent tees poor heel grab skis rend lent draw know grow doer yock pert legs'"
+ "'akin moot mead clef yens bees sewn yous grow pelt less sacs pens gout pegs heel whom reel gent czar boot whim lens toot dial goat prop boob dock fret help blue bell sits lead vial vent reed mean need poor cent peek bras lets wees bolt knit foul boos twin baas boss toad bier frog tout hews dell week fell pier omit coup skid whet trig newt peps prom leap atop mews quit hair leek wets rood know book geek teed moat yeps draw sort goad tens door skis weed whip troy lean club pets crow dent sows suck bout well reek floe bogs test sues dram deem legs tram spec peep room hoot flee shoe stem airs teem rent pert peel belt char sped sics moan loot prod lent heft next boom bias chow said news beep step dyer herd sick deep send boys stay leak yock mewl very bops fled moor aloe dual sots peck teen tent whir nest bows coat pout beef sued shes brew jell grey trap glue feed doer been flue drab whit bran hemp saws boon blur coot beet jets text thaw keen jock eery mock foam heed brow deed rend drag crew feet thin grab bend chip veep grad pled tees crab veil chit cell fees meet jeez went goop load self keep emit rock crop sack chin soon pock meek tell yell pews pest soil bled knot pees gees jeep gets loam sill berm chop than glib brag lock hock plus crag bloc prim foot root coop cock twit brad pent soft leis bent hell bobs fist gram term held vets wiry perk flea clue shoo brat bets peed loan yews knob geed poop nets beck fest suet best felt chew lees prep leaf weep unit melt'"
]
},
- "execution_count": 40,
+ "execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 41,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 44,
+ "metadata": {},
"outputs": [
{
"data": {
"['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
]
},
- "execution_count": 41,
+ "execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 42,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 45,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "CPU times: user 2.35 s, sys: 0 ns, total: 2.35 s\n",
- "Wall time: 2.35 s\n"
+ "CPU times: user 1.54 s, sys: 0 ns, total: 1.54 s\n",
+ "Wall time: 1.54 s\n"
]
},
{
"data": {
"text/plain": [
- "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']"
+ "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
]
},
- "execution_count": 42,
+ "execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 48,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 46,
+ "metadata": {},
"outputs": [],
"source": [
"# %time bfs_search('coax', 'stay')"
},
{
"cell_type": "code",
- "execution_count": 44,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 47,
+ "metadata": {},
"outputs": [
{
"data": {
"['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
]
},
- "execution_count": 44,
+ "execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 49,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 48,
+ "metadata": {},
"outputs": [],
"source": [
"# %time bfs_search('czar', 'stay')"
},
{
"cell_type": "code",
- "execution_count": 50,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 49,
+ "metadata": {},
"outputs": [],
"source": [
"# %time bfs_search('coax', 'stay')"
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.5.2"
+ "version": "3.5.2+"
}
},
"nbformat": 4,
projects / ou-summer-of-code-2017.git / commitdiff