Created
May 15, 2021 23:14
-
-
Save 6167656e74323431/17aa0db00b7c0fe935edf611c04a5880 to your computer and use it in GitHub Desktop.
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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)}%" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment