A program to simulate the likelihood of a wordsearch board containing a valid word, thus defeating the point of the impossible word search created in https://github.com/floundernews/floundernews.github.io/pull/61

word-search-simulation.rb

# word-search-simulation.rb: A program to simulate the likelihood of a word
# search board containing a valid word, thus defeating the point of the
# impossible word search created in
#      https://github.com/floundernews/floundernews.github.io/pull/61
#
# Usage: ruby word-search-simulation.rb COUNT
# 
# COUNT represents the number of blocks to be run. Each block consists of 1000 
# trials. If COUNT is 0, the results are only tallied, no new trials are run. 
# If COUNT is less than 0, the current set of results are thrown out (deleted).
# 
# Experimentally, after 1 million trials (taking between 30 minutes and 1 hour)
# the chance of a randomly generated board having a valid word in the word list
# was approximately 12.7715%.

BLOCKS = ARGV[0].to_i
TRIALS_PER_BLOCK = 1000

RESULTS_FILE = 'results.txt'

WORDS = ['ARTICLE', 'FACTS', 'FISH', 'FLOUNDER', 'ISSUE', 'JOURNALISM', 'MONTHLY', 'NEWS', 'REAL', 'SUBSCRIBE', 'TRUTH']

WORDS_TRIE = {}
WORDS.each do |word|
  level = WORDS_TRIE

  word.chars.each do |c|
    level[c] = {} unless level[c]
    level = level[c]
  end

  level[:exists] = true
end

def generate_board
  board = Array.new(15) { Array.new(15) { 'E'.dup } }

  1000.times do |i|
    x = rand(0...15)
    y = rand(0...15)
    word = WORDS.sample.dup

    si = rand(0...word.length)
    word[si] = ((word[si].ord + 1 - 'A'.ord) % 26 + 'A'.ord).chr

    if i % 2 == 0
      (x...[15, x + word.length].min).each do |j|
        board[j][y] = word[j - x]
      end
    else
      (y...[15, y + word.length].min).each do |j|
        board[x][j] = word[j - y]
      end
    end
  end

  board
end

def check_board(board)
  (0...15).each do |x|
    (0...15).each do |y|
      current_level = WORDS_TRIE
      (x...15).each do |i|
        return true if current_level[:exists]
        break unless current_level[board[i][y]]
        current_level = current_level[board[i][y]]
      end
      return true if current_level[:exists]

      current_level = WORDS_TRIE
      (y...15).each do |i|
        return true if current_level[:exists]
        break unless current_level[board[x][i]]
        current_level = current_level[board[x][i]]
      end
      return true if current_level[:exists]
    end
  end

  false
end

if BLOCKS < 0
  File.delete(RESULTS_FILE) if File.exist?(RESULTS_FILE)
  puts 'Data cleared.'
  exit 0
end

BLOCKS.times do |i|
  with_valid_words = 0
  TRIALS_PER_BLOCK.times do
    with_valid_words += 1 if check_board(generate_board)
  end

  puts "Trial #{i + 1} of #{BLOCKS}: #{with_valid_words}/#{TRIALS_PER_BLOCK}"
  File.open(RESULTS_FILE, 'a') do |f|
    f.puts with_valid_words
  end
end

data = File.readlines(RESULTS_FILE).map(&:to_i)
average_chance = data.sum.to_r/(data.length * TRIALS_PER_BLOCK)
puts "Average chance over #{data.length * TRIALS_PER_BLOCK} trials is #{average_chance} or #{(average_chance.to_f * 100).round(10)}%"