# -- UNIX users may add a "#! ....python" line here. They know what to do !

# author: Frederic van der Plancke
# NN WordSearch test problems. 
# These problems are designed so that:
#   * they challenge your implementation limits
#   * words trace many paths on the board
#   * the resulting problem looks like hard graph problems


import string
import whrandom
from whrandom import randint


# nn
# "nn"'s board consists mainly of 'A'; words too.
# 
# in: width; height; numwords; wordlength; numaltletters

def nn(width = 80, height = 26, numwords = 500, wordlength = 80, numaltletters = 25):
    output = [ str(height) + "\n", str(width) + "\n" ]

    board = []
    for i in range(height):
        board.append(width * ['A'] + ["\n"])

    #--- board

    num_board_alt_letters = max(3*numaltletters, width*height/4)
    numaltletters = min(numaltletters, num_board_alt_letters, 25)

    for i in range(num_board_alt_letters):
        found = 0
        while not found:
            (x,y) = divmod(randint(0, width * height - 1), height)
            found = (board[y][x] == 'A')
        if i < numaltletters:
            # each 'alt' letter present at least once
            board[y][x] = chr(ord('B') + i)
        else:
            board[y][x] = chr(randint(ord('B'), ord('A') + numaltletters))

    for line in board:
        output.append(string.join(line, ""))

    #--- words

    words = []
    # = list of strings

    for i in range(numwords):
        word = wordlength * ['A']
        if i < numaltletters:
            altleft  = chr(ord('B') +   i                  )
            altright = chr(ord('B') + (i+1) % numaltletters)
        else:
            altleft  = chr(randint(ord('B'), ord('A') + numaltletters))
            altright = chr(randint(ord('B'), ord('A') + numaltletters))

        posleft  = randint(0, wordlength/3)
        posright = randint((2*wordlength)/3, wordlength-1)
        
        word[posleft] = altleft
        word[posright] = altright

        wordstring = string.join(word, "") + "\n"
        if wordstring not in words:
            words.append(wordstring)

    ###output.append(words) #not good: words is a list, should be concatenated, not "append"ed

    #--- end

    return output + words           


def write_nn(filename, nn):
   success = 0
   f = open(filename, "w")
   try:
      f.writelines(nn)
      success = 1
   finally:
      f.close()
      # Python tip: ensure files are closed under _all_ circumstances
   return success


whrandom.seed(3, 141, 59)   # familiar number ;-) seeds in [0..255]

### The biggest POTM-compliant test. Will your program survive ?
big = nn()
### Smaller but probably much more challenging for the _algorithm_:
less_big = nn(wordlength = 21)

write_nn("nn_big.txt",      big)
write_nn("nn_less_big.txt", less_big)