import math
import random

def_cubes = ('tretyl', 'toesis', 'qnuhim', 'stdtyi',
            'ictumo', 'aganee', 'suinee', 'faskpf',
            'whervt', 'newehg', 'drevyl', 'spoach',
            'jabboo', 'dixerl', 'wattoo', 'znrnhl')

class Grid:
    def __init__(self):
        self.cubes = range(16)
        self.shuffle()

    def shuffle(self):
        random.shuffle(self.cubes);
        self.letters = [random.choice(def_cubes[c]) for c in self.cubes]

    def dump(self):
        print self.letters[0:4], '\n', self.letters[4:8]
        print self.letters[8:12], '\n', self.letters[12:]

    def get_neighbors(self, pos):
        row = pos / 4
        col = pos % 4
        nrows = [d + row for d in (-1, 0, 1)]
        ncols = [d + col for d in (-1, 0, 1)]
        ret = []
        for nrow in nrows:
            for ncol in ncols:
                if nrow < 4 and nrow >= 0 and ncol < 4 and ncol >= 0:
                    npos = nrow * 4 + ncol
                    if npos != pos: ret.append((npos, self.letters[npos]))
        return ret

    def findword(self, word):
        paths = filter(lambda x: self.letters[x] == word[0], xrange(16))
        paths = [[p] for p in paths]
        i = 1
        for char in word[1:]:
            npaths = []
            #print "char", i, char, "paths", paths
            for path in paths:
                n = self.get_neighbors(path[i - 1])
                #print path[i-1], "neighbors: ", n
                for ncube, nchar in n:
                    #check if letter on new cube is the same
                    #as letter we need:
                    if nchar != char: continue;
                    #check if new cube in path
                    if path.count(ncube): continue;
                    #we've passed both tests! append this path to npaths
                    #for the next round
                    #print "adding cube", ncube, "letter", nchar
                    npaths.append(path + [ncube])
            if npaths == []: return False
            paths = npaths
            i = i + 1
        return True

import sys

g = Grid()
g.dump()
successes = 0
iter = 100000
for i in xrange(iter):
    successes = successes + g.findword(sys.argv[1])
    g.shuffle()
    if not (i % 1000): print "\x0d%1f percent" % round(100. * i / iter, 2)
print successes, "successes (%f %%)" % (successes / 100000.)