Python version of nossidge's C++ from https://gist.github.com/nossidge/5272238

Snowball

#!/usr/bin/env python
"""
Python version of nossidge's C++ from https://gist.github.com/nossidge/5272238
Original blurb:

~~ Snowball Poem ~~
Snowball (also called a Chaterism): A poem in which each line is a single word,
and each successive word is one letter longer. One of the constrained writing
techniques invented by the Oulipo (Workshop of Potential Literature).


~~ Program Description ~~
This program takes input from the file "input-raw.txt". It examines the file for
any word pairs which vary in length by one letter, eg. "any word", "word pairs".

To get the final Snowball poem, it starts at a one letter word ("A", "I", "O")
and randomly traverses a Markov tree that links the second of one pair to the
first of another if they are the same word. It then repeats this process,
stopping when it reaches a dead branch.


~~ Features ~~
The code scans through the input file, and examine each whitespace-separated
word. If the word contains punctuation or numbers then it is ignored. This
means that it also does not word pair between line breaks. This may perhaps be
an issue with books from Project Gutenburg; as their text files are fixed width,
we could be missing some word pairs, but it's not a big problem.


~~ Input File ~~
The text that I used is a bunch of novels from Project Gutenburg, all collated
into one file. Because of the prevalence of named characters, I have found it
beneficial to remove instances of the character names, or other things that are
specific only to the text. They look kinda rubbish when they work their way
into Snowballs. Also, watch out for characters with lisps or phonetically
written accents, and foreign words and phrases.

In my input file I replace all this stuff with the string "xxxxxx". The code
then ignores any words in the input that equal this string. This could be
automated in future by comparing each word to see if it is in a dictionary.


~~ Output Files ~~
The program produces four output files:
"output-wordPairsGrowing.txt" lists all word pairs, in the order that they
appear in the input file.
"output-followingWordsGrowing.txt" lists all word pairs as a map with each following
word underneath. The keys are in alphabetical order.
"output-lengthOfWordsGrowing.txt" lists all words first by length, and then by the
order that they appear in the input file.
"output-snowballPoems-1364561431.txt" (where the numbers are a timestamp) is the
final output of all the created poems.


~~ Sample Snowball Output ~~
Beware! The output will, for the most part, be absolute rubbish. But there will
be wheat in the chaff. These are some actual unedited generated poems. The input
was mostly Dickens.

i
am
but
dust
which
seemed
nothing
whatever

o
my
two
feet
again
walked
through
profound
solemnity

i
am
the
dawn
light
before
anybody
expected
something
disorderly

i
do
not
like
being
hungry



~~ Update 2013.04.27 ~~
There is also a constraint called the Melting Snowball. This is pretty much what
you'd expect it to be; it's a poem in which each line is a single word, and each
successive word is one letter SHORTER.

Some examples:
http://poetrywithmathematics.blogspot.co.uk/2010/11/celebrate-constraints-happy-birthday.html
http://jacketmagazine.com/37/bury-queneau.shtml

I figured it wouldn't be too much trouble to change this code so it can generate
these as well. I've found, though, that it tends to be much more difficult to
find good ones. And, they pretty much all have to end in "I".

Oulipo is a French movement; apparently this stuff is easier to do in French.
Well, I suppose that's why they call it a constraint.


Some generated examples:

solitary
brother
always
looks
good
but
do
i

schooling
business
matters
little
think
boys
and
so
i

shadowy
people
would
kill
you
as
i

"""
import argparse
from collections import defaultdict
from random import randrange
import time

try: import timing # optional
except: pass

# Should the Pairs list be deduped?
uniqueWordPairs = True

#     list[list[string]]
#     [keyWord], [followingWord]
#     {it},      {can}
#     {it},      {was}
#     {it},      {had}
wordPairsGrowing = []
wordPairsShrinking = []
wordPairsAll = []

# ////////////////////////////////////////////////////////////////////////////////

def sortListAndDedupe(listOfListsOfStrings):
    return dict((x[0], x) for x in listOfListsOfStrings).values()

def saveListToFile(wordPairList, filename):
    f = open(filename, "w")
    f.write("\n".join(" ".join(x) for x in wordPairList))
    f.close()

def populateLengthMap(inputList, filename):
    output_dict = defaultdict(list)

    for word_pairs in inputList:
        firstWord = word_pairs[0]
        wordLength = len(firstWord)
        output_dict[wordLength].append(firstWord)

    # Save the dict to a file
    f = open(filename, "w")
    for key, values in output_dict.iteritems():
        f.write("Key:    " + str(key) + "\n")
        f.write("Values: \n")
        for value in values:
            f.write(value +  "\n        ")
        f.write("\n")
    f.close()

    return output_dict

def populateFollowingWordsMap(input_list, filename):
    output_dict = defaultdict(list)

    # Add to lengthOfWordsGrowing map
    for word_pair in input_list:
        firstWord = word_pair[0]
        output_dict[firstWord].append(word_pair[1])

    # Save the dict to a file
    f = open(filename, "w")
    for key, values in output_dict.iteritems():
        f.write("Key:    " + str(key) + "\n")
        f.write("Values: \n")
        for value in values:
            f.write(value +  "\n        ")
        f.write("\n")
    f.close()

    return output_dict

# ////////////////////////////////////////////////////////////////////////////////

# Normal Snowball poem creator.
def createPoemSnowball():
    print "Creating snowball poems"
    filename = "output-snowballPoems-" + str(int(time.time())) + ".txt"
    f = open(filename, "w")

    # Make a thousand of them!
    for i in range(0, 1000):
        oneLetterWords = ["a","i","o"]

        # There are three approaches here.
        # Choose which one to use at random.
        startMethod = randrange(3) + 1

        # Select a random 1 letter word from {lengthOfWordsGrowing}
        if startMethod == 1:
            randIndex = randrange(len(lengthOfWordsGrowing[1]))
            chosenWord = lengthOfWordsGrowing[1][randIndex]
            f.write("1 " + chosenWord + "\n")

        # Just choose between one of A, I, or O
        elif startMethod == 2:
            randIndex = randrange(3)
            chosenWord = oneLetterWords[randIndex]
            f.write("1 " + chosenWord + "\n")

        # Select a 2 letter word, and use "o" as the first line
        elif startMethod == 3:
            randIndex = randrange(len(lengthOfWordsGrowing[2]))
            chosenWord = lengthOfWordsGrowing[2][randIndex]
            f.write("1 o\n")
            f.write("2 " + chosenWord + "\n")

        # Find a random matching word in {followingWordsGrowing}
        # Loop through the tree until it reaches a dead branch
        while len(followingWordsGrowing[chosenWord]) != 0:
            randIndex = randrange(len(followingWordsGrowing[chosenWord]))
            chosenWord = followingWordsGrowing[chosenWord][randIndex]
            f.write(str(len(chosenWord)) + " " + chosenWord + "\n")

        f.write("\n")

    f.close()

# ////////////////////////////////////////////////////////////////////////////////

# We need to loop through the Shrinking words backwards.
# Save to a list[string] buffer, and then output them forwards when it's
#   finished and we know how long the poem will be.
def createPoemSnowballMelting():
    print "Creating melting snowball poems"
    filename = "output-snowballPoemsMelting-" + str(int(time.time())) + ".txt"
    f = open(filename, "w")

    # Make a thousand of them!
    for i in range(0, 1000):
        currentPoem = []

        # Select a random 1 letter word from {lengthOfWordsShrinking}
        randIndex = randrange(len(lengthOfWordsShrinking[1]))
        chosenWord = lengthOfWordsShrinking[1][randIndex]
        currentPoem.append(chosenWord)

        # Find a random matching word in {followingWordsShrinking}.
        # Loop through the tree until it reaches a dead branch.
        while len(followingWordsShrinking[chosenWord]) != 0:
            randIndex = randrange(len(followingWordsShrinking[chosenWord]))
            chosenWord = followingWordsShrinking[chosenWord][randIndex]
            currentPoem.append(chosenWord)

        # We now have the poem backwards in the {currentPoem} list.
        # Loop backwards through the list and output to the file.
#         for i, chosenWord in reversed(list(enumerate(currentPoem))):
#              f.write(str(i)) + " " + chosenWord + "\n")
        for chosenWord in reversed(currentPoem):
             f.write(str(len(chosenWord)) + " " + chosenWord + "\n")

        f.write("\n")

    f.close()

# ////////////////////////////////////////////////////////////////////////////////

# This just creates a bunch of Markov gibberish, disregarding the "one letter
#   length difference" stuff. I don't know. I just thought it'd be interesting.
def createRandomMarkov():
    print "Creating a bunch of Markov gibberish"
    filename = "output-randomMarkov-" + str(int(time.time())) + ".txt"
    f = open(filename, "w")

    # Make a thousand of them!
    for i in range(0, 1):
        currentPoem = []

        randIndex = randrange(len(wordPairsAll))
        chosenWord = wordPairsAll[randIndex][0]
        f.write(chosenWord + " ")

        # Find a random matching word in {followingWordsAll}
        # Loop through the tree until it reaches a dead branch
        while len(followingWordsAll[chosenWord]) != 0:
            randIndex = randrange(len(followingWordsAll[chosenWord]))
            chosenWord = followingWordsAll[chosenWord][randIndex]
            f.write(chosenWord + " ")

        f.write("\n")

    f.close()

# ////////////////////////////////////////////////////////////////////////////////

if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='TODO.',
        formatter_class=argparse.ArgumentDefaultsHelpFormatter)
    parser.add_argument('-i', '--infile', default='input-raw.txt', help='Input file')
    args = parser.parse_args()

    file = open(args.infile)
    previousWord = ""

#   # Loop through the raw input file.
    while 1:
        lines = file.readlines(100000)
        if not lines:
            break
        for line in lines:
            pass # do something
            # Examine each individual word.
            for word in line.split():
                # If the word contains punctuation, then drop it.
                # Also get rid of names and stuff that's specific to the input text.
                # (So in the input file, replace "Jarndyce", "Pickwick", "Scrooge",
                # etc. with "xxxxxx")
                if not word.isalpha() or word in ["xxxxxx", "xxxxxx"]:
                    word = ""
                else:
                    # Make the word lowercase.
                    word = word.lower()

                    # Add the word pair to wordPairsAll, no matter what.
                    # Also, if the lengths are separated by just one letter, add
                    # to the approriate list, either Growing or Shrinking.
                    if len(previousWord) != 0:
                        singleWordPair = [previousWord, word]

                        wordPairsAll.append(singleWordPair)

                        if len(word) == len(previousWord) + 1:
                            wordPairsGrowing.append(singleWordPair)
                        elif len(word) + 1 == len(previousWord):
                            # Because we'll loop through the Shrinking words backwards,
                            # we need to flip the two strings around in the list.
                            wordPairsShrinking.append([word, previousWord])
                previousWord = word

    # Sort them and get rid of duplicates (if necessary)
    if uniqueWordPairs:
        wordPairsGrowing   = sortListAndDedupe(wordPairsGrowing)
        wordPairsShrinking = sortListAndDedupe(wordPairsShrinking)
        wordPairsAll       = sortListAndDedupe(wordPairsAll)

    # Write them back out to a file
    saveListToFile(wordPairsGrowing,   "output-wordPairsGrowing.txt")
    saveListToFile(wordPairsShrinking, "output-wordPairsShrinking.txt")
    saveListToFile(wordPairsAll,       "output-wordPairsAll.txt")

    # Create the length maps
    lengthOfWordsGrowing   = populateLengthMap(wordPairsGrowing,   "output-lengthOfWordsGrowing.txt")
    lengthOfWordsShrinking = populateLengthMap(wordPairsShrinking, "output-lengthOfWordsShrinking.txt")
    lengthOfWordsAll       = populateLengthMap(wordPairsAll,       "output-lengthOfWordsAll.txt")

    # Create the following words maps
    followingWordsGrowing   = populateFollowingWordsMap(wordPairsGrowing,   "output-followingWordsGrowing.txt");
    followingWordsShrinking = populateFollowingWordsMap(wordPairsShrinking, "output-followingWordsShrinking.txt");
    followingWordsAll =       populateFollowingWordsMap(wordPairsAll,       "output-followingWordsAll.txt");

    # Now let's run the actual output generators
    createPoemSnowball()
    createPoemSnowballMelting()
    createRandomMarkov() # careful now, might end up in an infinite loop

# End of file

Awesome! A python port! I'm so pleased that you like my little project. And your way of flipping the wordPairsShrinking as they're being written is much better than my way.

Oh, and the createRandomMarkov() infinite loop is fixed in my latest revision. As an example, my input text included the phrase "silokwe silokwe" from Huxley's Brave New World. Because it's the only time the nonsense word "silokwe" appears in the entire input, and the only thing the word matches to as a following word is itself, it loops forever.

So to fix it, it needs to loop through the tree until it reaches a dead branch OR it encounters a key that only contains one value, and the value is the same as the key.

Anyway. This fork is great and so are you.