Coin Jam

coinjamv1.py

import datetime


def makeJamCoin(n):
    result = []
    maxN = int("1" * (n - 2), 2)
    changable = 0
    while changable <= maxN:
        result.append("1" + "{0:b}".format(changable).zfill(n - 2) + "1")
        changable += 1
    return result


def conversorToBase(binary_number, base):
    n = base ** (len(binary_number) - 1)
    # print "n is " + str(n)
    result = 0
    for b in binary_number:
        # print b + " * " + str(n) + " = " + str(int(b) * n)
        result = result + (int(b) * n)
        n = n / base
    return result


def conversor(binary_number):
    elements = []
    for base in range(2, 11):
        elements.append(conversorToBase(binary_number, base))
    return elements


def getDivisor(n):
    for i in range(2, int(n**0.5)+1):
        if (n % i == 0):
            return i

    return -1


def getDivisors(n):
    numberInDifferentBases = conversor(n)
    divisors = []
    for numberBase in numberInDifferentBases:
        divisor = getDivisor(numberBase)
        # print str(numberBase) + " is divisible by " + str(divisor)
        if (divisor == -1):
            return divisors
        else:
            divisors.append(divisor)
    return divisors


def getJamCoins(possibleJamCoins, total):
    i = 0
    result = []
    while len(result) < j:
        jamcoin = possibleJamCoins[i]
        divisors = getDivisors(jamcoin)
        if (len(divisors) != 9):
            print jamcoin + " is not a jamcoin"
        else:
            print jamcoin + " is a jamcoin!"
            result.append(jamcoin + " " + " ".join(str(e) for e in divisors))
        i = i + 1
    return result


def addingCase(n, text):
    resultCase = "Case #" + str(n) + ": \n"
    resultCase += text
    print resultCase
    return resultCase


inFile = open("C-large-practice.in", "r")
outFile = open("C-large-practice.out", "w")

t = int(inFile.readline())
print "number of test case is ", t
print datetime.datetime.now()

icase = 1
while icase <= t:
    line = inFile.readline().split(" ")
    n = int(line[0])
    j = int(line[1])
    print "n = " + str(n) + " and j = " + str(j)
    jamcoins = getJamCoins(makeJamCoin(n), j)
    outFile.write(addingCase(icase, "\n".join(jamcoins)))
    icase = icase + 1


print datetime.datetime.now()
outFile.close()
inFile.close()

coinjamv2.py

import datetime


def convertFromBinaryTo(binary_number, base):
    n = base ** (len(binary_number) - 1)
    result = 0
    for b in binary_number:
        result = result + (int(b) * n)
        n = n / base
    return result


def convertFromBinaryToOtherBases(binary_number):
    elements = []
    for base in range(2, 11):
        elements.append(convertFromBinaryTo(binary_number, base))
    return elements


def getDivisor(n):
    # We do not need to find all the jamcoins. Just one divisor
    for i in range(2, 10000):
        if (n % i == 0):
            return i
    return -1


def getDivisors(n):
    numberInDifferentBases = convertFromBinaryToOtherBases(n)
    divisors = []
    for numberBase in numberInDifferentBases:
        divisor = getDivisor(numberBase)
        if (divisor == -1):
            return divisors
        else:
            divisors.append(divisor)
    return divisors


def firstJamCoin(n):
    return "1" + "{0:b}".format(0).zfill(n - 2) + "1"


def nextJamCoins(last):
    n = len(last)
    changable = last[1:n-1:]
    changable = int(changable, 2) + 1
    return "1" + "{0:b}".format(changable).zfill(n - 2) + "1"


def getJamCoins(n, total):
    i = 0
    result = []
    jamcoin = firstJamCoin(n)
    enoughJamCoins = len(result) >= j
    while not enoughJamCoins:
        divisors = getDivisors(jamcoin)
        isJamCoin = len(divisors) != 9
        if (isJamCoin):
            print jamcoin + " is not a jamcoin or maybe yes " + \
                "but it took too much time to find divisors examples"
        else:
            print jamcoin + " is a jamcoin!"
            result.append(jamcoin + " " + " ".join(str(e) for e in divisors))
        i = i + 1
        jamcoin = nextJamCoins(jamcoin)
        enoughJamCoins = len(result) >= j

    return result


def addingCase(n, text):
    resultCase = "Case #" + str(n) + ": \n"
    resultCase += text
    print resultCase
    return resultCase


inFile = open("C-large-practice.in", "r")
outFile = open("C-large-practice.out", "w")

t = int(inFile.readline())
print "number of test case is ", t
print datetime.datetime.now()

icase = 1
while icase <= t:
    numbers = inFile.readline().split(" ")
    n = int(numbers[0])
    j = int(numbers[1])
    print "n = " + str(n) + " and j = " + str(j)
    jamcoins = getJamCoins(n, j)
    outFile.write(addingCase(icase, "\n".join(jamcoins)))
    icase = icase + 1


print datetime.datetime.now()
outFile.close()
inFile.close()