#=
William John Holden
2019-08-10

A program to generate silly crossword horoscopes, but the output generated does not actually
contain any words. This is my first experiment with Julia. So far I like it. The crosswords
may contain words.

The algorithm I had in mind was to start at the top-left corner, considering each position
one at a time. Starting from all 26 letters, I eliminate all letters that could be used with
the letter above, left, or diagonal to this position to begin a word of any length. If you
never begin a word then there is actually no need to read deeply into this trie, but I had
not thought this that far through when I started coding.

In practice, most pairs of letters can form the beginning of some word. This program outputs
many letters "Z", "K", "X", "Q", and other less-used characters. If not for the PRNG it would
almost never output a vowel. No effort is made to prevent words from being constructed in
the other directions.

The results are actually a little bit better if you use a smaller dictionary. The sample
output shown is from a list of 1000 common english words.

Sample CLI syntax:

    julia.exe .\crossword.jl 20 60 .\1000.txt

Sample output:

    First three words you see are your reality.

    BFDMCZAERHMQBXIOYFPKYNHBBXQFFNFGXPJHYCQLBSNQKUMRNBJQFXMTMVDK
    PWKTDKQJZWLDZWYBMXNFPGGFFDGQCMQJKXXZVZJPDQNLFKXLVDMXGWGJQLTG
    VVUBJGCKAZLLQQGFTXRPFWBGHCWMMSNDZRSRSXMJZZDBTVUDTZWPVCMWGWJB
    LKJHDWXYQKJHFGVPTZSXPNMBPMMWPZSZFFGNGGFNQJPWXNYLBZBMQVTGZGDB
    ZUKHTQCXVJKWDJWMXMLDTQSNCDNKJKRJSNDZFXHSGMNNWQKCGDSSGZFPCPPM
    PQWSXMWTQGWGTPYKMRDJXJSJCZYMTZWWFJWNVFTQDPBJZSBSGNLXWNBWYYYB
    BQLXWSGSLKBFKSNQDPMMHMVSWDKCVSQJDYWVWCDPNBXXBQGQQHMZGXXXNNNZ
    HMCMSNVVQKTFKSBXWMBBFKWQQGWVMDQFNHQCFQYGXTNHCTKSBCSDJBXQZQTV
    HFXNBFKXSZVVKBDNFCMJGJQPFDSZCNZWNLWFDDFFVDQTCXQGSWGNHJDVJIGZ
    HCKYSBDYVLSJQZBNTGWXQTVJMMDFXMVVYWVPPSJXMPZQGPDZNJZGKFNMKQJD
    ZMKLGFFKKFZWJYZQPZXZAZLCBXXJQCDFPSNPNSZJXSFYQXXKZXMQJDYGCBCC
    RJQPWGXXKYDZGDLDSQXZEEQTFMNKFXDMKBXVCJBBZDWFYZYHRDQGJSFFJGWY
    VWQDQMNMGTDFGFGMQRYDQJJPPZCVTDCXCWWFCDZDHCBZTZVKKYPJCJGKJNSD
    ZLVKFBVQFBZYPCCWFQZZGVFXGPBXJFVVBMCDQJDXVJZXGGKHWFXJDQPXPBGW
    UZMMFVDWYPWJYKYMKCQMGKXTZTBDMQMSWCNZLXWNJJBFSQSZVQZDZDSWGVNQ
    LHVZJMXWMZSZFWZGJBBXXFVPTNTSQMCXNYDVJQGKSNMWBWZZNGVHLCGFVZKL
    FCTLDHGZDTFJDJTVCGZHYZWYXGGZBVZPZSWLHLQFJQZLDJXTSDVXWQCMFGCS
    QNQKFKSVQLVHXPCBWFBWQZUTTBXMGGKPDDXKBVMWGJSNNYWSDSXPJBBSSQSX
    OQQCCXDFMRBBPGKVQQKJKVXFKGBJQSZTJVCBPXLDXZDGKWKXXFDZYPWFDNZS
    XDNKZZDKJFJMJQZHCDZZTKVZZQPBKXWMQGXTPZTDXBBTVPVTVWXVKWFQTVLJ
=#

# Build a trie based on an input string.
function add(t::Dict, s::String)
    i = 1
    while i <= length(s)
        if !(haskey(t, s[i]))
            t[s[i]] = Dict()
        end
        t = t[s[i]]
        i = i + 1
    end
    t['$'] = '$'
end

# Deterine if a complete string exists in the trie
function contains(t::Dict, s::String)::Bool
    i = 1
    while i <= length(s)
        if !(haskey(t, s[i]))
            return false
        end
        t = t[s[i]]
        i = i + 1
    end
    return haskey(t, '$')
end

# Reconstruct and print each string in the trie
function printTrie(t::Dict, stack::String="", level::Int=0)
    for (k,v) in t
        if k == '$'
            println(stack)
        else
            printTrie(t[k], stack * k, level + 1)
        end
    end
end

# Count the '$' symbols representing strings in the trie
function countTrie(t::Dict)
    sum = 0
    for (k,v) in t
        if k == '$'
            sum += 1
        else
            sum += countTrie(t[k])
        end
    end
    return sum
end
    
# Generate an m x n matrix of random letters. There should be no words in this "puzzle".
function generate(m::Int, n::Int, t::Dict)
    M = fill('a', (m,n))

    for i in 1:m, j in 1:n
        domain = Set([collect('a':'z');])

        # Remove letters that could form a word with the letter above.
        if j > 1
            above = M[i, j - 1]
            if above in keys(t)
                setdiff!(domain, keys(t[above]))
            end
        end

        # Remove letters that could form a word with the letter to the left.
        if i > 1
            left = M[i - 1, j]
            if left in keys(t)
                setdiff!(domain, keys(t[left]))
            end
        end

        # Remove letters that could form a word with the letter diagonal to this one.
        if i > 1 && j > 1
            diagonal = M[i - 1, j - 1]
            if diagonal in keys(t)
                setdiff!(domain, keys(t[diagonal]))
            end
        end

        # If uisng a large dictionary you might need to bias your domain to get more
        # vowels. Otherwise you end up with lots of seldom-used consonants.
        # Fun observation - if you include "y" in your vowels then you can generate a matrix
        # of all y's.
        # domain_vowels = intersect(domain, ['a','e','i','o','u','y'])
        # if length(domain_vowels) > 0
        #    domain = domain_vowels
        # end

        # If the domain got depleted completely then there is no letter that cannot begin
        # a word with the adjacent letters. This might mean you need a smaller dictionary.
        v = isempty(domain) ? ' ' : rand(domain)

        M[i,j] = v
    end

    return M
end

t = Dict()
m = parse(Int, ARGS[1])
n = parse(Int, ARGS[2])
# Read a dictionary file directly from ARGS[3] if provided, otherwise read stdin.
input = (length(ARGS) > 2) ? readlines(ARGS[3]) : readlines()
for s in input
    add(t, s)
end
M = generate(m, n, t)

println("First three words you see are your reality.")
println()
for i in 1:m
    for j in 1:n
        print(uppercase(M[i,j]))
    end
    println()
end