#!/usr/bin/env python
import random
import timeit

def rand(m, n):
    return random.randint(m, n)

def getDuplicates(numbers):
    nset = set()
    duplicates = set()
    for num in numbers:
        if num in nset:
            duplicates |= { num }
        else:
            nset |= { num }
    return duplicates

def checkSolutionContract(a, b, N):
    s = b - a
    assert a < b
    assert s >= N

def solutionOne(a, b, N):
    numbers = []
    while len(numbers) < N:
        num = rand(a, b)
        if num not in numbers:
            numbers.append(num)
    return numbers

def solutionTwo(a, b, N):
    possible = [ x for x in range(a, b + 1) ]
    numbers = []
    while len(numbers) < N:
        num = rand(0, len(possible) - 1)
        numbers.append(possible[num])
        possible.remove(possible[num])
    return numbers

def solutionThree(a, b, N):
    possible = [ x for x in range(a, b + 1) ]
    shuffle(possible)
    return possible[0:N] # return first N elements

def shuffle(arr): # Fisher-Yates shuffle
    for i in range(0, len(arr) - 1):
        j = rand(i, len(arr) - 1)
        # swap i-th and j-th element
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp

def solutionFour(a, b, N):
    s = b - a
    possible = { } # map, int -> int
    numbers = []
    for i in range(0, N + 1):
        num = rand(i, s - 1)
        if i not in possible:
            possible[i] = i
        if num not in possible:
            possible[num] = num

        numbers.append(possible[num] + a)
        tmp = possible[i]
        possible[i] = possible[num]
        possible[num] = tmp
    return numbers

def testSolution(solution, a, b, N, passes = 10000):
    checkSolutionContract(a, b, N)
    for i in range(0, passes):
        numbers = solution(a, b, N)
        duplicates = getDuplicates(numbers)
        assert len(duplicates) == 0, "%s have duplicates" % (duplicates)

def benchmarkSolution(solution, a, b, N):
    timer = timeit.Timer(lambda: solution(a, b, N))
    return timer.timeit(number = 100000)

def testSolutions(a, b, N):
    checkSolutionContract(a, b, N)
    print("testing solutions on: [%s, %s], N = %s" % (a, b, N))
    print("testing solution one...")
    testSolution(solutionOne, a, b, N)
    print("\tdone")

    print("testing solution two...")
    testSolution(solutionTwo, a, b, N)
    print("\tdone")

    print("testing solution three...")
    testSolution(solutionThree, a, b, N)
    print("\tdone")

    print("testing solution four...")
    testSolution(solutionFour, a, b, N)
    print("\tdone")

def benchmarkSolutions(a, b, N):
    checkSolutionContract(a, b, N)
    print("benchmarks on: [%s, %s], N = %s" % (a, b, N))
    print("\t  one: %s" % (benchmarkSolution(solutionOne, a, b, N)))
    print("\t  two: %s" % (benchmarkSolution(solutionTwo, a, b, N)))
    print("\tthree: %s" % (benchmarkSolution(solutionThree, a, b, N)))
    print("\t four: %s" % (benchmarkSolution(solutionFour, a, b, N)))

parameters = [
        (0, 99, 10),
        (0, 99, 50),
        (0, 99, 90),
        (0, 9999, 10),
        (0, 9999, 500),
        (0, 9999, 5000),
        (0, 9999, 9000),
    ]

testParameters = random.choice(parameters)
testSolutions(*testParameters)

for params in parameters:
    benchmarkSolutions(*params)