"Exercise: WordSearch"

wordSearch: words grid: grid
"In word search puzzles you get a square of letters and have to find specific words in them.
    Words can be hidden in all kinds of directions: left-to-right, right-to-left, vertical and diagonal.
    Given a puzzle and a list of words return the location of the first and last letter of each word."
"((self new wordSearch: #('clojure') grid: #('clojurermt')) at: 'clojure') first >>> 1 @ 1"
| rows cols wordGrid directions charAt find result |
	rows := grid size.
	cols := grid isEmpty
		        ifTrue: [ 0 ]
		        ifFalse: [ grid first size ].

	wordGrid := grid collect: [ :rowString | rowString asArray ].

	directions := (0 @ 0) eightNeighbors.

	charAt := [ :pt |
		          ((pt y between: 1 and: rows) and: [
			           pt x between: 1 and: cols ]) ifTrue: [
			          (wordGrid at: pt y) at: pt x ] ].

	find := [ :aWord :source :bearing :onFound |
		        | current matched |
		        current := source.
		        matched := true.
		        aWord
			        do: [ :char |
				        (charAt value: current) = char ifFalse: [
					        matched := false ] ]
			        separatedBy: [ current := current + bearing ].
		        matched ifTrue: [ onFound value: source value: current ] ].

	result := Dictionary new.

	words do: [ :word |
			1 to: rows do: [ :r |
					1 to: cols do: [ :c |
							directions do: [ :d |
									find
										value: word
										value: c @ r
										value: d
										value: [ :start :end |
												result at: word put: {
														start.
														end } ] ] ] ] ].

	^ result


"Tests"
testWordSearch
| result |

  "01 Should accept an initial game grid and a target search word"
  result := task wordSearch: #('clojure') grid: #('jefblpepre').
  self assert: (result at: 'clojure' ifAbsent: [ nil ]) isNil.

  "02 Should locate one word written left to right"
  result := task wordSearch: #('clojure') grid: #('clojurermt').
  self assert: (result at: 'clojure') first y equals: 1.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 1.
  self assert: (result at: 'clojure') last x equals: 7.

  "03 Should locate the same word written left to right in a different position"
  result := task wordSearch: #('clojure') grid: #('mtclojurer').
  self assert: (result at: 'clojure') first y equals: 1.
  self assert: (result at: 'clojure') first x equals: 3.
  self assert: (result at: 'clojure') last y equals: 1.
  self assert: (result at: 'clojure') last x equals: 9.

  "04 Should locate a different left to right word"
  result := task wordSearch: #('coffee') grid: #('coffeelplx').
  self assert: (result at: 'coffee') first y equals: 1.
  self assert: (result at: 'coffee') first x equals: 1.
  self assert: (result at: 'coffee') last y equals: 1.
  self assert: (result at: 'coffee') last x equals: 6.

  "05 Should locate that different left to right word in a different position"
  result := task wordSearch: #('coffee') grid: #('xcoffeezlp').
  self assert: (result at: 'coffee') first y equals: 1.
  self assert: (result at: 'coffee') first x equals: 2.
  self assert: (result at: 'coffee') last y equals: 1.
  self assert: (result at: 'coffee') last x equals: 7.

  "06 Should locate a left to right word in two line grid"
  result := task wordSearch: #('clojure') grid: #('jefblpepre' 'tclojurerm').
  self assert: (result at: 'clojure') first y equals: 2.
  self assert: (result at: 'clojure') first x equals: 2.
  self assert: (result at: 'clojure') last y equals: 2.
  self assert: (result at: 'clojure') last x equals: 8.

  "07 Should locate a left to right word in three line grid"
  result := task wordSearch: #('clojure') grid: #('camdcimgtc' 'jefblpepre' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 3.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 3.
  self assert: (result at: 'clojure') last x equals: 7.

  "08 Should locate a left to right word in ten line grid"
  result := task wordSearch: #('clojure') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.

  "09 Should locate that left to right word in a different position in a ten line grid"
  result := task wordSearch: #('clojure') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'clojurermt' 'jalaycalmp').
  self assert: (result at: 'clojure') first y equals: 9.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 9.
  self assert: (result at: 'clojure') last x equals: 7.

  "10 Should locate a different left to right word in a ten line grid"
  result := task wordSearch: #('fortran') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'fortranftw' 'alxhpburyi' 'clojurermt' 'jalaycalmp').
  self assert: (result at: 'fortran') first y equals: 7.
  self assert: (result at: 'fortran') first x equals: 1.
  self assert: (result at: 'fortran') last y equals: 7.
  self assert: (result at: 'fortran') last x equals: 7.

  "11 Should locate multiple words"
  result := task wordSearch: #('fortran' 'clojure') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'fortranftw' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'fortran') first y equals: 7.
  self assert: (result at: 'fortran') first x equals: 1.
  self assert: (result at: 'fortran') last y equals: 7.
  self assert: (result at: 'fortran') last x equals: 7.

  "12 Should locate a single word written right to left"
  result := task wordSearch: #('elixir') grid: #('rixilelhrs').
  self assert: (result at: 'elixir') first y equals: 1.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 1.
  self assert: (result at: 'elixir') last x equals: 1.

  "13 Should locate multiple words written in different horizontal directions"
  result := task wordSearch: #('elixir' 'clojure') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.

  "14 Should locate words written top to bottom"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.

  "15 Should locate words written bottom to top"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript' 'rust') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.
  self assert: (result at: 'rust') first y equals: 5.
  self assert: (result at: 'rust') first x equals: 9.
  self assert: (result at: 'rust') last y equals: 2.
  self assert: (result at: 'rust') last x equals: 9.

  "16 Should locate words written top left to bottom right"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript' 'rust' 'java') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.
  self assert: (result at: 'rust') first y equals: 5.
  self assert: (result at: 'rust') first x equals: 9.
  self assert: (result at: 'rust') last y equals: 2.
  self assert: (result at: 'rust') last x equals: 9.
  self assert: (result at: 'java') first y equals: 1.
  self assert: (result at: 'java') first x equals: 1.
  self assert: (result at: 'java') last y equals: 4.
  self assert: (result at: 'java') last x equals: 4.

  "17 Should locate words written bottom right to top left"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript' 'rust' 'java' 'lua') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.
  self assert: (result at: 'rust') first y equals: 5.
  self assert: (result at: 'rust') first x equals: 9.
  self assert: (result at: 'rust') last y equals: 2.
  self assert: (result at: 'rust') last x equals: 9.
  self assert: (result at: 'java') first y equals: 1.
  self assert: (result at: 'java') first x equals: 1.
  self assert: (result at: 'java') last y equals: 4.
  self assert: (result at: 'java') last x equals: 4.
  self assert: (result at: 'lua') first y equals: 9.
  self assert: (result at: 'lua') first x equals: 8.
  self assert: (result at: 'lua') last y equals: 7.
  self assert: (result at: 'lua') last x equals: 6.

  "18 Should locate words written bottom left to top right"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript' 'rust' 'java' 'lua' 'lisp') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.
  self assert: (result at: 'rust') first y equals: 5.
  self assert: (result at: 'rust') first x equals: 9.
  self assert: (result at: 'rust') last y equals: 2.
  self assert: (result at: 'rust') last x equals: 9.
  self assert: (result at: 'java') first y equals: 1.
  self assert: (result at: 'java') first x equals: 1.
  self assert: (result at: 'java') last y equals: 4.
  self assert: (result at: 'java') last x equals: 4.
  self assert: (result at: 'lua') first y equals: 9.
  self assert: (result at: 'lua') first x equals: 8.
  self assert: (result at: 'lua') last y equals: 7.
  self assert: (result at: 'lua') last x equals: 6.
  self assert: (result at: 'lisp') first y equals: 6.
  self assert: (result at: 'lisp') first x equals: 3.
  self assert: (result at: 'lisp') last y equals: 3.
  self assert: (result at: 'lisp') last x equals: 6.

  "19 Should locate words written top right to bottom left"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript' 'rust' 'java' 'lua' 'lisp' 'ruby') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.
  self assert: (result at: 'rust') first y equals: 5.
  self assert: (result at: 'rust') first x equals: 9.
  self assert: (result at: 'rust') last y equals: 2.
  self assert: (result at: 'rust') last x equals: 9.
  self assert: (result at: 'java') first y equals: 1.
  self assert: (result at: 'java') first x equals: 1.
  self assert: (result at: 'java') last y equals: 4.
  self assert: (result at: 'java') last x equals: 4.
  self assert: (result at: 'lua') first y equals: 9.
  self assert: (result at: 'lua') first x equals: 8.
  self assert: (result at: 'lua') last y equals: 7.
  self assert: (result at: 'lua') last x equals: 6.
  self assert: (result at: 'lisp') first y equals: 6.
  self assert: (result at: 'lisp') first x equals: 3.
  self assert: (result at: 'lisp') last y equals: 3.
  self assert: (result at: 'lisp') last x equals: 6.
  self assert: (result at: 'ruby') first y equals: 6.
  self assert: (result at: 'ruby') first x equals: 8.
  self assert: (result at: 'ruby') last y equals: 9.
  self assert: (result at: 'ruby') last x equals: 5.

  "20 Should fail to locate a word that is not in the puzzle"
  result := task wordSearch: #('clojure' 'elixir' 'ecmascript' 'rust' 'java' 'lua' 'lisp' 'ruby' 'haskell') grid: #('jefblpepre' 'camdcimgtc' 'oivokprjsm' 'pbwasqroua' 'rixilelhrs' 'wolcqlirpc' 'screeaumgr' 'alxhpburyi' 'jalaycalmp' 'clojurermt').
  self assert: (result at: 'clojure') first y equals: 10.
  self assert: (result at: 'clojure') first x equals: 1.
  self assert: (result at: 'clojure') last y equals: 10.
  self assert: (result at: 'clojure') last x equals: 7.
  self assert: (result at: 'elixir') first y equals: 5.
  self assert: (result at: 'elixir') first x equals: 6.
  self assert: (result at: 'elixir') last y equals: 5.
  self assert: (result at: 'elixir') last x equals: 1.
  self assert: (result at: 'ecmascript') first y equals: 1.
  self assert: (result at: 'ecmascript') first x equals: 10.
  self assert: (result at: 'ecmascript') last y equals: 10.
  self assert: (result at: 'ecmascript') last x equals: 10.
  self assert: (result at: 'rust') first y equals: 5.
  self assert: (result at: 'rust') first x equals: 9.
  self assert: (result at: 'rust') last y equals: 2.
  self assert: (result at: 'rust') last x equals: 9.
  self assert: (result at: 'java') first y equals: 1.
  self assert: (result at: 'java') first x equals: 1.
  self assert: (result at: 'java') last y equals: 4.
  self assert: (result at: 'java') last x equals: 4.
  self assert: (result at: 'lua') first y equals: 9.
  self assert: (result at: 'lua') first x equals: 8.
  self assert: (result at: 'lua') last y equals: 7.
  self assert: (result at: 'lua') last x equals: 6.
  self assert: (result at: 'lisp') first y equals: 6.
  self assert: (result at: 'lisp') first x equals: 3.
  self assert: (result at: 'lisp') last y equals: 3.
  self assert: (result at: 'lisp') last x equals: 6.
  self assert: (result at: 'ruby') first y equals: 6.
  self assert: (result at: 'ruby') first x equals: 8.
  self assert: (result at: 'ruby') last y equals: 9.
  self assert: (result at: 'ruby') last x equals: 5.
  self assert: (result at: 'haskell' ifAbsent: [ nil ]) isNil.

  "21 Should fail to locate words that are not on horizontal, vertical, or diagonal lines"
  result := task wordSearch: #('aef' 'ced' 'abf' 'cbd') grid: #('abc' 'def').
  self assert: (result at: 'aef' ifAbsent: [ nil ]) isNil.
  self assert: (result at: 'abf' ifAbsent: [ nil ]) isNil.
  self assert: (result at: 'ced' ifAbsent: [ nil ]) isNil.
  self assert: (result at: 'cbd' ifAbsent: [ nil ]) isNil.

  "22 Should not concatenate different lines to find a horizontal word"
  result := task wordSearch: #('elixir') grid: #('abceli' 'xirdfg').
  self assert: (result at: 'elixir' ifAbsent: [ nil ]) isNil.

  "23 Should not wrap around horizontallx to find a word"
  result := task wordSearch: #('lisp') grid: #('silabcdefp').
  self assert: (result at: 'lisp' ifAbsent: [ nil ]) isNil.

  "24 Should not wrap around verticallx to find a word"
  result := task wordSearch: #('rust') grid: #('s' 'u' 'r' 'a' 'b' 'c' 't').
  self assert: (result at: 'rust' ifAbsent: [ nil ]) isNil.