Resistance Is Not Futile ACM Problem

resistance_is_not_futile.py

#!/usr/bin/env python3
import math
from pprint import pprint
from collections import deque

#resistors = [10, 12, 15, 18, 22, 27, 33, 39, 47, 56, 68, 82]
resistors = [82, 68, 56, 47, 39, 33, 27, 22, 18, 15, 12, 10]
decades = {}

# generate and cache decade lists on demand
def decade(d):
    if d not in decades:
        decades[d] = list(map(lambda x: x * 10 ** (d-1), resistors))
    return decades[d]

# finds the largest resistor that is within tolerance
# returns None if no resistor is found
def find_largest_resistor(rsum, rmax):
    if rsum <= rmax:
        dmax = int(math.log10(rmax-rsum))
        for d in range(dmax, 0, -1):
            for i, r in enumerate(decade(d)):
                if r + rsum <= rmax:
                    return r

# returns the next resistor smaller than r, or None
def next_smaller(r):
    d = int(math.log10(r))
    i = decade(d).index(r)
    i += 1
    if i >= len(resistors):
        i = 0
        d -= 1
    if d >= 1:
        return decade(d)[i]

# returns a list-of-lists containing resistors
# whose sums are between rmin and rmax
def find_resistor_lists(rmin, rmax):
    rlists = []
    qlists = deque()
    maxlen = float('inf')
    nearest = find_largest_resistor(0, rmax)
    if nearest is not None:
        qlists.append([nearest])
    while qlists:
        if rlists:
            maxlen = len(min(rlists, key=len))
        cur = qlists.popleft()
        lasti = -1
        nextlist = cur[0:lasti]
        nextsum = sum(nextlist)
        if len(nextlist) < maxlen:
            r = next_smaller(cur[lasti])
            if r is not None:
                qlists.append(nextlist + [r])
        rlist = cur
        rsum = sum(rlist)
        if rmin <= rsum <= rmax:
            rlists.append(rlist[:])
        elif rsum < rmin and len(rlist) < maxlen:
            nearest = find_largest_resistor(rsum, rmax)
            if nearest is not None:
                if nearest > rlist[-1]:
                    nearest = rlist[-1]
                qlists.append(rlist + [nearest])
    return rlists

# Returns the single list that best fits the solution definition
def break_ties(rlists, r):
    def helper(rlists, f):
        smallest = float('inf')
        smallests = []
        for rlist in rlists:
            value = f(rlist)
            if value < smallest:
                smallest = value
                smallests = [rlist]
            elif value == smallest:
                smallests.append(rlist)
        return smallests

    shortests = helper(rlists, len) # just in case
    if len(shortests) > 1:
        nearests = helper(shortests, lambda lst: perror(sum(lst), r))
        if len(nearests) > 1:
            #return min(nearests, key=sum)
            mns = helper(nearests, sum)
            if len(mns) > 1:
                return min(mns)
            else:
                return mns[0]
        else:
            return nearests[0]
    else:
        return shortests[0]

def main(v, i):
    r = resistance(v, i)

    if r < 10:
        return 'Impossible'
    else:
        rmin = ( r ) / ( 1 / 100 + 1 )
        rmax = ( r ) / ( -1 / 100 + 1 )
        lists = find_resistor_lists(rmin, rmax)
        if lists == []:
            return 'Impossible'
        final_list = break_ties(lists, r)
        return final_list, lists, rmin, rmax

# percent error between target and value
def perror(value, target):
    return abs(target - value) * 100 / value

def resistance(v, i):
    return v / i

# formats output for debugging
def run_sample(v, i):
    result = main(v, i)
    if len(result) == 4:
        final_list, lists, rmin, rmax = result
        pprint(final_list)
        pprint((rmax, rmin))
        pprint(list(map((lambda x: (x, sum(x))), lists)))
    else:
        print(result)
    print()

if __name__ == '__main__':
    # uncomment to read from stdin
##    v, i = input().split()
##    v, i = int(v), int(i)
##    result = main(v, i)
##    if len(result) == 4:
##        print(' '.join(result[0]))
##    else:
##        print(result)

    # included test cases
    print('sample 1')
    run_sample(50000, 5)
    print('sample 2')
    run_sample(44558, 10)
    print('sample 3')
    run_sample(1, 1)

This is great, but unfortunately Python is not a permitted language in the ACM contest. Also, your program must have dynamic input and output. It isn't enough to just have three test cases that work. HOWEVER, great work nonetheless.
-Jesse

This demonstrates why every programmer should learn Python (or a similar dynamic language). I didn't intend to make a working program, I just had an idea that I needed to write down and explore. Before I knew it, I only needed a little boilerplate to get it to run. At this point, rewriting it in Java or C++ would be straightforward; much more so than starting in those languages.

Also, (commented) lines 52-54 read from stdin; the rest is so I didn't have to retype those test cases every time it ran.

Oh I see. If you can make it to one of the MW 4:30 meetings you should, I think you should meet Anthony, he's running the ACM teams this year. Cheers