gistfile1.py

import math
import random
import uuid
from collections import deque
from copy import deepcopy


def score(assignments):
    def num_letters(word):
        return len([c for c in word if str.isalpha(c)])

    def num_vowels(word):
        vowels = ['a', 'e', 'i', 'o', 'u', 'y']
        return len([c for c in word if c in vowels])

    def num_consonants(word):
        return num_letters(word) - num_vowels(word)

    def gcd(a, b):
        while b:
            a, b = b, a % b

    combined_score, i = 0, 0

    for pair in assignments:
        customer, offer = pair[0], pair[1]
        ss = 0.0

        if num_letters(offer) % 2 == 0:
            ss += num_vowels(customer) * 1.5
        else:
            ss += num_consonants(customer)

        if gcd(num_letters(customer), num_letters(offer)) > 1:
            ss *= 1.5

        combined_score += ss
        i += 1

    return combined_score


def generate_neighbor(assignments, delta_factor=.01):
    """
    assignments = [
        ['john smith', 'half gallon milk'],
        [sarah jane', 'colt ma124'],
        ['bob dylan', 'tesla motors model s']]
    """

    num_swaps = math.ceil(delta_factor * len(assignments))
    num_swaps = int(num_swaps) if num_swaps >= 1 else 1

    for _ in xrange(num_swaps):
        first_index, second_index = 0, 0

        # the probability that this conditional
        # will evaluate to false approaches 1.0 wrt time

        while first_index == second_index:
            first_index = random.randrange(0, len(assignments))
            second_index = random.randrange(0, len(assignments))

        buff = assignments[first_index][1]
        assignments[first_index][1] = assignments[second_index][1]
        assignments[second_index][1] = buff

    return assignments


def randomize(customers, offers):
    randomized = []

    random.shuffle(customers)
    random.shuffle(offers)

    c, o = 0, 0
    while c < len(customers) and o < len(offers):
        randomized.append([customers[c], offers[o]])
        c, o = c+1, o+1

    return randomized


def gaussian(x, variance=500):
    variance = math.sqrt(math.e / 2.0 * math.pow(variance, 2))
    return 1.0 - math.e * (math.pow(x,2.0) / (2.0*math.pow(variance, 2.0)))


def run_simulation(customers, offers, num_iters=10):
    top = deque(maxlen = 4)
    top.append(randomize(customers, offers))
    proposed = deepcopy(top[-1])

    for iteration in xrange(num_iters):
        cycle = 0
        while gaussian(cycle) > 0 and len(top) > 0:
            proposed = generate_neighbor(proposed)
            if score(proposed) > score(top[-1]):
                highest_scoring = proposed
                top.append(highest_scoring)
            else:
                rand_prob = random.uniform(0, 1)

                if iteration >= math.floor(.9 * num_iters) and len(top) > 0:
                    proposed = top.pop()
                elif gaussian(cycle) > rand_prob:
                    proposed = randomize(customers, offers)

            cycle += 1

    return highest_scoring


def perform_tests(num_inputs=40, num_runs=100):
    customers = []
    offers = []

    def run_test(in_func, verbose=True):
        scores = []
        for i in xrange(num_runs):
            scores.append(score(in_func(customers, offers)))
            if verbose:
                print "Test cycle: ", i+1
        return scores

    for i in xrange(num_inputs):
        customer = str(uuid.uuid4()).replace('-', '')
        offer = str(uuid.uuid4()).replace('-', '')

        # generate varying string lengths for
        # greater score distribution

        j = random.randrange(0, len(customer))
        k = random.randrange(0, len(offer))
        customers.append(customer[0:j])
        offers.append(offer[0:k])

    print "Running simulations..."
    simres = run_test(run_simulation)

    print "Getting randomized scores..."
    randres = run_test(randomize)

    return simres, randres