#!/usr/bin/env python

# We need this for the cross-product we'll use later
import itertools
import random

class Language:
    def __init__(self):
        self.lang_m2s = {}
        self.lang_s2m = {}

    # Input: A meaning, can be any Python object
    # Output: The symbol chosen by the language to represent the meaning
    #    The symbol will not overlap with any other symbol in the language
    def learn(self, meaning):
        pass

    # Input: A meaning
    # Output: The symbol associated with that meaning
    def speak(self, meaning):
        return self.lang_m2s[meaning] if meaning in self.lang_m2s else None

    # Input: A symbol
    # Output: The meaning associated with that symbol
    def hear(self, symbol):
        return self.lang_s2m[symbol] if symbol in self.lang_s2m else None

    def symbols(self):
        return self.lang_s2m.keys()

    def meanings(self):
        return self.lang_m2s.keys()

    # Returns the proportion of meanings without a unique symbol
    def ambiguity(self):
        # NUmber of ambiguous meanings
        n = 0
        for symbol in self.lang_s2m:
            meanings = self.lang_s2m[symbol]
            if len(meanings) > 1:
                n += len(meanings)
        return n / (1.0 * len(self.lang_m2s))

    # Input: A symbol to perturb
    # Output: Perturbed symbol
    def perturb_symbol(self, s):
        pass

    # Input: probability of SOME symbol changing in SOME way
    # Output: New symbol, the internal state is updated to reflect
    #    the new symbol's replacing of the old one.
    def perturb(self, p):
        r = random.random()
        if r < p:
            # Change something
            # First, choose a random symbol
            s = random.sample(self.lang_s2m.keys(), 1)[0]
            s_old = s
            m = self.lang_s2m[s]

            # We need to remove the old symbol from the language
            del self.lang_s2m[s]

            s = self.perturb_symbol(s)

            # Now, add the new perturbed symbol to the language.
            # If the symbol is already there, add the meaning to the list
            if s in self.lang_s2m:
                # In Python, the increment operator also concatenates lists
                self.lang_s2m[s] += m
            else:
                self.lang_s2m[s] = m

            for meaning in m:
                self.lang_m2s[meaning] = s

            return (s_old, s)
        else:
            return None

    def __repr__(self):
        return __str__(self)

class MoreNumbers(Language):
    # Example: A0, B000, D0
    valid_letters = [ chr(ord('A') + i) for i in range(26) ]
    max_zeros = 10

    def learn(self, meaning):
        # Don't relearn meanings
        symbol = self.speak(meaning)
        if symbol != None:
            return symbol

        while True:
            symbol = random.sample(self.valid_letters, 1)[0] + "".join('0' * random.randint(1, self.max_zeros))
            if (symbol not in self.lang_s2m) or (len(self.lang_s2m) == 0):
                break

        self.lang_s2m[symbol] = [ meaning ]
        self.lang_m2s[meaning] = symbol

    def perturb_symbol(self, s):
        # Randomly add/subtract a zero
        # If we didn't do that, randomly twiddle the character up/down one (wrap at a-1, z+1)
        r = random.random()
        if r > 0.5:
            # Change the letter
            l = s[0]

            # This is ugly, but it's some modular arithmetic to wrap around the alphabet
            l = chr(ord('a') + (ord(l) + 1 - ord('a')) % 26)
            s = l + s[1:]
        else:
            # Change the number of zeroes
            r = random.randint(0,1)
            z = "".join('0'*(len(s) - 1 + (2 * r - 1)))

            if len(z) == 0:
                z = "0"
            s = s[0] + z

        return s

    def __str__(self):
        return "MoreNumbers"

class NumberFirst(Language):
    # Example: 0a, 8f, 1s
    valid_letters = [ chr(ord('a') + i) for i in range(26) ]
    valid_numbers = [ chr(ord('0') + i) for i in range(10) ]

    def learn(self, meaning):
        # Don't relearn meanings
        symbol = self.speak(meaning)
        if symbol != None:
            return symbol

        while True:
            symbol = random.sample(self.valid_numbers, 1)[0] + random.sample(self.valid_letters, 1)[0]
            if (symbol not in self.lang_s2m) or (len(self.lang_s2m) == 0):
                break

        self.lang_s2m[symbol] = [ meaning ]
        self.lang_m2s[meaning] = symbol

    def perturb_symbol(self, s):
        r = random.random()
        if r > 0.5:
            # Change the letter
            l = s[1]

            # This is ugly, but it's some modular arithmetic to wrap around the alphabet
            l = chr(ord('a') + (ord(l) + 1 - ord('a')) % 26)
            s = s[0] + l
        else:
            # Change the number
            n = s[0]

            # This is ugly, but it's some modular arithmetic to wrap around the alphabet
            n = chr(ord('0') + (ord(n) + 1 - ord('0')) % 10)
            s = n + s[1]

        return s

    def __str__(self):
        return "NumberFirst"

class NumberLast(Language):
    # Example: a0, g7, t1
    valid_letters = [ chr(ord('a') + i) for i in range(26) ]
    valid_numbers = [ chr(ord('0') + i) for i in range(10) ]

    def learn(self, meaning):
        # Don't relearn meanings
        symbol = self.speak(meaning)
        if symbol != None:
            return symbol

        while True:
            symbol = random.sample(self.valid_letters, 1)[0] + random.sample(self.valid_numbers, 1)[0]
            if (symbol not in self.lang_s2m) or (len(self.lang_s2m) == 0):
                break

        self.lang_s2m[symbol] = [ meaning ]
        self.lang_m2s[meaning] = symbol

    def perturb_symbol(self, s):
        r = random.random()
        if r > 0.5:
            # Change the letter
            l = s[0]

            # This is ugly, but it's some modular arithmetic to wrap around the alphabet
            l = chr(ord('a') + (ord(l) + 1 - ord('a')) % 26)
            s = l + s[1]
        else:
            # Change the number
            n = s[1]

            # This is ugly, but it's some modular arithmetic to wrap around the alphabet
            n = chr(ord('0') + (ord(n) + 1 - ord('0')) % 10)
            s = s[0] + n

        return s

    def __str__(self):
        return "NumberLast"

# Instantiate some languages
langs = [ MoreNumbers(), NumberFirst(), NumberLast() ]

# Here, our 'meanings' are arbitrary, as long as they are common, and each language knows them
# We can just use integers
meanings = range(100)

# Now, teach the languages some stuff
for m in meanings:
    for l in langs:
        l.learn(m)

# Now we want to do a quick check that for each meaning, there's no overlap
# If we've build out languages properly, that should be true.
for m in meanings:
    for l1, l2 in itertools.product(langs, langs):
        # If it's the same language for both the speaker and listener, we expect it
        # to work out
        if l1 == l2:
            heard_meaning = l2.hear(l1.speak(m))
            if m not in heard_meaning:
                print "Language %s didn't understand %s properly (%s)" % (str(l1), str(m), str(heard_meaning))
            #else:
                #print "Language %s is OK" % str(l1)
        # If it's different languages, this should fail
        else:
            heard_meaning = l2.hear(l1.speak(m))
            if heard_meaning != None:
                print "Languages %s and %s have overlap with meaning %s" % (str(l1), str(l2), str(m))
            #else:
                #print "Language %s successfully heard %s spoken by %s" (str(l2), str(m), str(l1))

import copy
langs_orig = copy.deepcopy(langs)

# Create a few generations of each language, changing one symbol each time.
for l in langs:
    #print
    #print str(l)
    #print "Starting:", l.lang_s2m
    for i in range(15):
        r = l.perturb(0.5)
        #if r != None:
            #print "Perturbed %s to %s" % (str(r[0]), str(r[1]))
        #print "Generation %d:" % (i+1), l.lang_s2m

# Now, compare this child language with the ancestor, and see how many meanings
# can be unambiguously conveyed
for l_old, l_new in zip(langs_orig, langs):
    n = 0
    for m in meanings:
        # Try to speak the meaning in the old language to the new language
        m_new = l_new.hear(l_old.speak(m))
        if m_new != None and len(m_new) == 1 and m in m_new:
            n += 1
    print "Language %s has %g%% meanings still available" % (str(l_old), 100.0 * n / len(meanings))