Solutions to Warby Parker Programming Contest (SWE Guild, 12/22/2016)

a-adam.py

# Problem A - The 3n + 1 problem
# https://vjudge.net/contest/145712#problem/A
# Author: Adam

import sys
import functools

@functools.lru_cache(maxsize=1000000)
def cycle_len(k):
    if k == 1:
        return 1
    if k % 2 == 0:
        return 1+cycle_len(k/2)
    return 1+ cycle_len(3*k + 1)

def solve(i, j):
    return max(cycle_len(k) for k in range(i, j+1))

inp = iter(sys.stdin)

for l in inp:
    i, j = (int(x) for x in l.strip().split())
    print('%d %d %d' % (i, j, solve(*sorted((i,j)))))

a-sean.py

# Problem A - The 3n + 1 problem
# https://vjudge.net/contest/145712#problem/A
# Author: Sean


import fileinput


stored_results = {}


def max_cycle_length(i):
    if i == 1:
        # base case
        return 1

    elif i in stored_results:
        # memoized
        return stored_results[i]

    elif i % 2:
        # odd case
        res = max_cycle_length(3*i + 1) + 1
        stored_results[i] = res
        return res

    else:
        # even case
        res = max_cycle_length(i/2) + 1
        stored_results[i] = res
        return res


def solve(low, high):
    res = 0

    for i in range(low, high+1):
        res = max(res, max_cycle_length(i))

    return res


def main():
    for line in fileinput.input():
        i, j = [int(x) for x in line.split()]
        low = min(i, j)
        high = max(i, j)
        print('%d %d %d' % (i, j, solve(low, high)))


if __name__ == '__main__':
    main()

b-sean.py

# Problem B - Maximum Sub-sequence Product
# https://vjudge.net/contest/145712#problem/B
# Author: Sean


import fileinput


def solve(sequence):
    res = -10000000

    for i in range(len(sequence)):
        product = 1

        for j in range(i, len(sequence)):
            product *= sequence[j]
            res = max(res, product)

    return res


def main():
    sequence = []
    for line in fileinput.input():
        for word in line.split():
            x = int(word)
            if x == -999999:
                res = solve(sequence)
                print(res)
                sequence = []
            else:
                sequence.append(x)


if __name__ == '__main__':
    main()