dnestoff
9/9/2016 - 2:29 AM

Algorithm: Grid search

A grid search method designed to find words in a grid (as a straight line).

require_relative '../word_search'

describe 'straight_line_include?' do
  let (:puzzle) { [
    ["a", "k", "f", "o", "x", "e", "s"],
    ["s", "o", "a", "w", "a", "h", "p"],
    ["i", "t", "c", "k", "e", "t", "n"],
    ["o", "t", "s", "d", "h", "o", "h"],
    ["s", "e", "x", "g", "s", "t", "a"],
    ["u", "r", "p", "i", "w", "e", "u"],
    ["z", "s", "b", "n", "u", "i", "r"]
  ] }

  it 'can determine if a word is in the puzzle' do
    expect(straight_line_include?("weo", puzzle)).to eq true
  end

  it 'can determine if a word is not in the puzzle' do
    expect(straight_line_include?("ever", puzzle)).to eq false
  end

  context 'find letters' do
    it 'can return the coordinate of all letter placements' do
      expect(find_letter_coordinates("a", puzzle)).to eq [[0,0], [1,2], [1,4], [4,6]]
    end

    it 'can return the indexes of a letter when it appears more than once' do
      row = ["s", "o", "a", "w", "a", "h", "p"]
      expect(find_indexes_of_letter("a", row)).to eq [2,4]
    end
  end

  context 'find words' do
    it 'returns true if a word exists forwards in a row' do
      word = "foxes"
      row = ["a", "k", "f", "o", "x", "e", "s"]
      expect(exists?(word, row)).to eq true
    end

    it 'returns true if a word exists backwards in a row' do
      word = "foxes"
      row = ["a", "k", "s", "e", "x", "o", "f"]
      expect(exists?(word, row)).to eq true
    end

    it 'returns false if a word doesnt exist in a row' do
      word = "home"
      row = ["a", "k", "s", "e", "x", "o", "f"]
      expect(exists?(word, row)).to eq false
    end

  context 'get arrays from puzzle' do
    it 'can grab a column of items when given a coordinate' do
      coordinate = [1,0]
      expect(grab_column(coordinate, puzzle)).to eq ["a", "s", "i", "o", "s", "u", "z"]
    end

    it 'can grab diagonally oriented items (NW to SE) when given a coordinate' do
      coordinate = [1,0]
      expect(grab_diagonal_NW_to_SE(coordinate, puzzle)).to eq ["s", "t", "s", "g", "w", "i"]
        end

    it 'can grab diagonally oriented items (SW to NE) when given a coordinate' do
      coordinate = [5,2]
      expect(grab_diagonal_SW_to_NE(coordinate, puzzle)).to eq ['s', 'p', 'g', 'h', 't', 'p']
    end

    it 'can grab a collection of all (4) straight line arrays' do
      coordinate = [5,0]
      possible_arrays = collect_possible_arrays(coordinate,puzzle)
      expect(possible_arrays.length).to eq 4
    end


  end

  end

end

describe 'snaking_include?' do
end

#pseudocode ================
# take first letter of word and search entire array
  #return coordinate of that number
  #check row string for word (forwards and backwards)
    # if TRUE, return true
  # check column for word (forwards and backwards)
    # if TRUE, return true
  # check both diagonals for word (forwards and backwards)
    # if TRUE, return true
  #ELSE return false
# for every letter in array

puzzle = [
  ["a", "k", "f", "o", "x", "e", "s"],
  ["s", "o", "a", "w", "a", "h", "p"],
  ["i", "t", "c", "k", "e", "t", "n"],
  ["o", "t", "s", "d", "h", "o", "h"],
  ["s", "e", "x", "g", "s", "t", "a"],
  ["u", "r", "p", "i", "w", "e", "u"],
  ["z", "s", "b", "n", "u", "i", "r"]
]


def straight_line_include?(word, puzzle)
  first_letter = word[0]
  at_coordinates = find_letter_coordinates(first_letter, puzzle)
  results_array = []
  at_coordinates.each do |coordinate|
    all_arrays = collect_possible_arrays(coordinate, puzzle)
    all_arrays.each do |letter_collection| 
      results_array << exists?(word, letter_collection)
    end
  end
  results_array.include?(true)
end

def snaking_include?(word, puzzle)
end


private

def collect_possible_arrays(coordinate, puzzle)
  directional_arrays = []
  directional_arrays << grab_row(coordinate, puzzle)
  directional_arrays << grab_column(coordinate, puzzle)
  directional_arrays << grab_diagonal_NW_to_SE(coordinate, puzzle)
  directional_arrays << grab_diagonal_SW_to_NE(coordinate, puzzle)
end

def grab_row(coordinate, puzzle)
  row = coordinate[0]
  puzzle[row]
end

def grab_column(coordinate, puzzle)
  column = coordinate[1]
  puzzle.collect { |index| index[column] }
end

def grab_diagonal_NW_to_SE(coordinate, puzzle)
  left_to_right = []
  starting_coord = top_leftmost_from_coordinate(coordinate)
  row = starting_coord[0]
  column = starting_coord[1]

  until row == puzzle.length || column == puzzle.length
    left_to_right << puzzle[row][column]
    row += 1
    column += 1
  end
  left_to_right
end

def grab_diagonal_SW_to_NE(coordinate, puzzle)
  right_to_left = []
  starting_coord = bottom_leftmost_from_coordinate(coordinate)
  row = starting_coord[0]
  column = starting_coord[1]
  until row < 0 || column == puzzle.length
    right_to_left << puzzle[row][column]
    row -= 1
    column += 1
  end
  right_to_left
end

def top_leftmost_from_coordinate(coordinate)
  row = coordinate[0]
  column = coordinate[1]
  until row == 0 || column == 0
    row -= 1
    column -= 1
  end
  [row, column]
end

def bottom_leftmost_from_coordinate(coordinate)
  row = coordinate[0]
  column = coordinate[1]
  until row == puzzle.length - 1 || column == 0
    row += 1
    column -= 1
  end
  [row, column]
end

def exists?(word, letter_array)
  letter_string = letter_array.join
  letter_string.include?(word) || letter_string.include?(word.reverse)
end

#input: a letter we want to find
#output: array of all coordinates with letter
def find_letter_coordinates(letter, puzzle)
  # puzzle.each_with_index { |row| row.include? letter}
  row_num = 0
  at_coordinates = []
  until row_num == puzzle.length
    if puzzle[row_num].include? letter
      columns = find_indexes_of_letter(letter, puzzle[row_num])
      columns.each { |column| at_coordinates << [row_num, column]}
    end
    row_num += 1
  end
  at_coordinates
end

# return array of two numbers
def find_indexes_of_letter(letter, row)
  #REFACTORED using each_index method
  letters_and_indexes = row.each_index.select { |index| row[index] == letter }
  # letters_and_indexes = row.each_with_index.select { |item, index| item == letter }
  # letters_and_indexes.flatten.reject { |item| item == letter }
end