In [ ]:
"""
UNIT 1: Bowling:
You will write the function bowling(balls), which returns an integer indicating
the score of a ten-pin bowling game. balls is a list of integers indicating
how many pins are knocked down with each ball. For example, a perfect game of
bowling would be described with:
>>> bowling([10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10])
300
The rules of bowling are as follows:
(1) A game consists of 10 frames. In each frame you roll one or two balls,
except for the tenth frame, where you roll one, two, or three. Your total
score is the sum of your scores for the ten frames.
(2) If you knock down fewer than ten pins with your two balls in the frame,
you score the total knocked down. For example, bowling([8, 1, 7, ...]) means
that you knocked down a total of 9 pins in the first frame. You score 9 point
for the frame, and you used up two balls in the frame. The second frame will
start with the 7.
(3) If you knock down all ten pins on your second ball it is called a 'spare'
and you score 10 points plus a bonus: whatever you roll with your next ball.
The next ball will also count in the next frame, so the next ball counts twice
(except in the tenth frame, in which case the bonus ball counts only once).
For example, bowling([8, 2, 7, ...]) means you get a spare in the first frame.
You score 10 + 7 for the frame; the second frame starts with the 7.
(4) If you knock down all ten pins on your first ball it is called a 'strike'
and you score 10 points plus a bonus of your score on the next two balls.
(The next two balls also count in the next frame, except in the tenth frame.)
For example, bowling([10, 7, 3, ...]) means that you get a strike, you score
10 + 7 + 3 = 20 in the first frame; the second frame starts with the 7.
"""
def bowling(balls):
"Compute the total score for a player's game of bowling."
## bowling([int, ...]) -> int
ball = 0
scores = 0
for _ in xrange(9):
if balls[ball] == 10:
scores += sum(balls[ball:ball+3])
ball += 1
elif balls[ball] + balls[ball+1] == 10:
scores += sum(balls[ball:ball+3])
ball += 2
else:
scores += sum(balls[ball:ball+2])
ball += 2
scores += sum(balls[ball:])
return scores
def test_bowling():
assert 0 == bowling([0] * 20)
assert 20 == bowling([1] * 20)
assert 80 == bowling([4] * 20)
assert 190 == bowling([9,1] * 10 + [9])
assert 300 == bowling([10] * 12)
assert 200 == bowling([10, 5,5] * 5 + [10])
assert 11 == bowling([0,0] * 9 + [10,1,0])
assert 12 == bowling([0,0] * 8 + [10, 1,0])
return "Test pass!"
print test_bowling()
In [ ]:
"""
UNIT 2: Logic Puzzle
You will write code to solve the following logic puzzle:
1. The person who arrived on Wednesday bought the laptop.
2. The programmer is not Wilkes.
3. Of the programmer and the person who bought the droid,
one is Wilkes and the other is Hamming.
4. The writer is not Minsky.
5. Neither Knuth nor the person who bought the tablet is the manager.
6. Knuth arrived the day after Simon.
7. The person who arrived on Thursday is not the designer.
8. The person who arrived on Friday didn't buy the tablet.
9. The designer didn't buy the droid.
10. Knuth arrived the day after the manager.
11. Of the person who bought the laptop and Wilkes,
one arrived on Monday and the other is the writer.
12. Either the person who bought the iphone or the person who bought the tablet
arrived on Tuesday.
You will write the function logic_puzzle(), which should return a list of the
names of the people in the order in which they arrive. For example, if they
happen to arrive in alphabetical order, Hamming on Monday, Knuth on Tuesday, etc.,
then you would return:
['Hamming', 'Knuth', 'Minsky', 'Simon', 'Wilkes']
(You can assume that the days mentioned are all in the same week.)
"""
import itertools as it
def logic_puzzle():
"Return a list of the names of the people, in the order they arrive."
orderings = list(it.permutations(range(5)))
def find_days():
return next((Hamming, Knuth, Minsky, Simon, Wilkes)
for laptop, droid, tablet, iphone, _ in orderings
if laptop is 2
if tablet is not 4
for Hamming, Knuth, Minsky, Simon, Wilkes in orderings
if Simon + 1 == Knuth
for programmer, writer, manager, designer, _ in orderings
if designer is not 3
if designer is not droid
if Wilkes is not programmer
if Minsky is not writer
if Hamming is programmer and Wilkes is droid
if Knuth is not manager and tablet is not manager
if manager + 1 == Knuth
if (Wilkes is writer and laptop is 0) or (Wilkes is 0 and laptop is writer)
if iphone is 1 or tablet is 1
)
Hamming, Knuth, Minsky, Simon, Wilkes = find_days()
return map(lambda x: x[1], \
sorted([(Hamming, "Hamming"), (Knuth, "Knuth"), (Minsky, "Minsky"), (Simon, "Simon"), (Wilkes, "Wilkes")]))
print logic_puzzle()
In [30]:
from collections import defaultdict
def decorator(d):
"Make function d a decorator: d wraps a function fn."
import functools
def _d(fn):
return functools.update_wrapper(d(fn), fn)
functools.update_wrapper(_d, d)
return _d
@decorator
def memo(f):
"""Decorator that caches the return value for each call to f(*args).
Then when called again with same args, we can just look it up."""
cache = {}
def _f(*args):
try:
return cache[args]
except KeyError:
result = f(*args)
try:
cache[args] = result
except TypeError: # args refuses to be a dict key
pass
return result
_f.cache = cache
return _f
def poly(coefs):
"""Return a function that is the polynomial with these coefficients.
For example if coefs=(10, 20, 30) return the function of x that computes
'30 * x**2 + 20 * x + 10'. Also store coefs on the .coefs attribute of
the function, and the str of the formula on the .__name__ attribute.'"""
return polynomial(canonical(coefs))
@memo
def polynomial(coefs):
"""Return a polynomial function with these attributes. Memoized, so any
two polys with the same coefficients will be identical polys."""
# Build a function by evaluating a lambda in the empty environment.
# Horner's rule involves fewer multiplications than the normal formula...
p = eval('lambda x: ' + horner_formula(coefs), {})
p.__name__ = polynomial_formula(coefs)
p.coefs = coefs
return p
def horner_formula(coefs):
"""A relatively efficient form to evaluate a polynomial.
E.g.: horner_formula((10, 20, 30, 0, -50))
== '(10 + x * (20 + x * (30 + x * x * -50)))',
which is 4 multiplies and 3 adds."""
c = coefs[0]
if len(coefs) == 1:
return str(c)
else:
factor = 'x * ' + horner_formula(coefs[1:])
return factor if c == 0 else '(%s + %s)' % (c, factor)
def polynomial_formula(coefs):
"""A simple human-readable form for a polynomial.
E.g.: polynomial_formula((10, 20, 30, 0, -50))
== '-50 * x**4 + 30 * x**2 + 20 * x + 10',
which is 7 multiplies and 3 adds."""
terms = [term(c, n)
for (n, c) in reversed(list(enumerate(coefs))) if c != 0]
return ' + '.join(terms)
def term(c, n):
"Return a string representing 'c * x**n' in simplified form."
if n == 0:
return str(c)
xn = 'x' if (n == 1) else ('x**' + str(n))
return xn if (c == 1) else '-' + xn if (c == -1) else str(c) + ' * ' + xn
def canonical(coefs):
"Canonicalize coefs by dropping trailing zeros and converting to a tuple."
if not coefs: coefs = [0]
elif isinstance(coefs, (int, float)): coefs = [coefs]
else: coefs = list(coefs)
while coefs[-1] == 0 and len(coefs) > 1:
del coefs[-1]
return tuple(coefs)
def is_poly(x):
"Return true if x is a poly (polynomial)."
## For examples, see the test_poly function
return callable(x) and hasattr(x, 'coefs')
def add(p1, p2):
"Return a new polynomial which is the sum of polynomials p1 and p2."
N = max(len(p1.coefs), len(p2.coefs))
coefs = [0] * N
for (n, c) in enumerate(p1.coefs): coefs[n] = c
for (n, c) in enumerate(p2.coefs): coefs[n] += c
return poly(coefs)
def sub(p1, p2):
"Return a new polynomial which is p1 - p2."
N = max(len(p1.coefs), len(p2.coefs))
coefs = [0] * N
for (n, c) in enumerate(p1.coefs): coefs[n] = c
for (n, c) in enumerate(p2.coefs): coefs[n] -= c
return poly(coefs)
def mul(p1, p2):
"Return a new polynomial which is the product of polynomials p1 and p2."
# Given terms a*x**n and b*x**m, accumulate a*b in results[n+m]
results = defaultdict(int)
for (n, a) in enumerate(p1.coefs):
for (m, b) in enumerate(p2.coefs):
results[n + m] += a * b
return poly([results[i] for i in range(max(results)+1)])
def power(p, n):
"Return a poly which is p to the nth power (n a non-negative integer)."
if n == 0:
return poly((1,))
elif n == 1:
return p
elif n % 2 == 0:
return square(power(p, n//2))
else:
return mul(p, power(p, n-1))
def square(p): return mul(p, p)
def deriv(p):
"Return the derivative of a function p (with respect to its argument)."
return poly([n*c for (n, c) in enumerate(p.coefs) if n > 0])
def integral(p, C=0):
"Return the integral of a function p (with respect to its argument)."
return poly([C] + [float(c)/(n+1) for (n, c) in enumerate(p.coefs)])
def test_poly():
global p1, p2, p3, p4, p5, p9
# global to ease debugging in an interactive session
p1 = poly((10, 20, 30))
assert p1(0) == 10
for x in (1, 2, 3, 4, 5, 1234.5):
assert p1(x) == 30 * x**2 + 20 * x + 10
assert same_name(p1.__name__, '30 * x**2 + 20 * x + 10')
assert is_poly(p1)
assert not is_poly(abs) and not is_poly(42) and not is_poly('cracker')
p3 = poly((0, 0, 0, 1))
assert p3.__name__ == 'x**3'
p9 = mul(p3, mul(p3, p3))
assert p9 == poly([0,0,0,0,0,0,0,0,0,1])
assert p9(2) == 512
p4 = add(p1, p3)
assert same_name(p4.__name__, 'x**3 + 30 * x**2 + 20 * x + 10')
assert same_name(poly((1, 1)).__name__, 'x + 1')
assert (power(poly((1, 1)), 10).__name__ ==
'x**10 + 10 * x**9 + 45 * x**8 + 120 * x**7 + 210 * x**6 + 252 ' +
'* x**5 + 210 * x**4 + 120 * x**3 + 45 * x**2 + 10 * x + 1')
assert add(poly((10, 20, 30)), poly((1, 2, 3))) == poly((11, 22, 33))
assert sub(poly((10, 20, 30)), poly((1, 2, 3))) == poly((9, 18, 27))
assert (mul(poly((10, 20, 30)), poly((1, 2, 3)))
== poly((10, 40, 100, 120, 90)))
assert power(poly((1, 1)), 2) == poly((1, 2, 1))
assert (power(poly((1, 1)), 10)
== poly((1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1)))
assert deriv(p1) == poly((20, 60))
assert integral(poly((20, 60))) == poly((0, 20, 30))
p5 = poly((0, 1, 2, 3, 4, 5))
assert same_name(p5.__name__,
'5 * x**5 + 4 * x**4 + 3 * x**3 + 2 * x**2 + x')
assert p5(1) == 15
assert p5(2) == 258
assert same_name(deriv(p5).__name__,
'25 * x**4 + 16 * x**3 + 9 * x**2 + 4 * x + 1')
assert deriv(p5)(1) == 55
assert deriv(p5)(2) == 573
#Additional Test Case:
p6 = poly((1,))
assert integral(p6)(10) == 10
return "Test Pass!"
def same_name(name1, name2):
"""Use same_name rather than name1 == name2 to allow for some
variation in naming conventions."""
def canonical_name(name): return name.replace(' ', '').replace('+-', '-')
return canonical_name(name1) == canonical_name(name2)
print test_poly()
In [ ]:
class poly(object):
"""poly objects are like the poly functions we defined earlier, but are
objects of a class. We coerce arguments to poly, so you can do (x + 1)
and the 1 will be converted to a poly first."""
def __init__(self, coefs):
coefs = canonical(coefs)
self.fn = eval('lambda x: ' + horner_formula(coefs), {})
self.__name__ = polynomial_formula(coefs)
self.coefs = coefs
def __call__(self, x): return self.fn(x)
def __eq__(self, other):
return isinstance(other, poly) and self.coefs == other.coefs
def __add__(self, p2): return add(self, coerce_poly(p2)) # p + p2
def __sub__(self, p2): return sub(self, coerce_poly(p2)) # p - p2
def __mul__(self, p2): return mul(self, coerce_poly(p2)) # p * p2
def __pow__(self, n): return power(self, n) # p ^ n
def __neg__(self): return poly((-c for c in self.coefs)) # - p
def __pos__(self): return self # + p
# A need the _r methods so that 1 + x works as well as x + 1.
def __rmul__(self, p2): return mul(self, coerce_poly(p2)) # 5 * x
def __radd__(self, p2): return add(self, coerce_poly(p2)) # 1 + x
# I added a __hash__ method after a suggestion by Jeffrey Tratner
def __hash__(self): return hash(self.coefs)
def __repr__(self):
return ''
def coerce_poly(p):
"Make this into a poly if it isn't already."
return p if isinstance(p, poly) else poly(p)
def is_poly(p): return isinstance(p, poly)
def Poly(formula):
"Parse the formula using eval in an environment where x is a poly."
return eval(formula, {'x': poly((0, 1))})
In [33]:
N = 8
def solve_parking_puzzle(start, N=N):
"""Solve the puzzle described by the starting position (a tuple
of (object, locations) pairs). Return a path of [state, action, ...]
alternating items; an action is a pair (object, distance_moved),
such as ('B', 16) to move 'B' two squares down on the N=8 grid."""
return shortest_path_search(grid(start, N), psuccessors, is_goal)
def is_goal(state):
"Goal is when the car (*) overlaps a goal square (@)."
d = dict(state)
return set(d['*']) & set(d['@'])
def psuccessors(state):
"""State is a tuple of (('c': sqs),...); return a {state:action} dict
where action is of form ('c', dir), where dir is +/-1 or +/-N."""
results = {}
occupied = set(s for (c, sqs) in state for s in sqs if c != '@')
for (c, sqs) in state:
if c not in '|@': # Walls and goals can't move
diff = sqs[1]-sqs[0]
# Either move the max of sqs up, or the min of sqs down
for (d, start) in [(diff, max(sqs)), (-diff, min(sqs))]:
for i in range(1, N-2):
s = start + d*i
if s in occupied:
break # Stop when you hit something
results[update(state,c,tuple(q+d*i for q in sqs))]=(c,d*i)
return results
def update(tuples, key, val):
"Return a new (key, val) tuple, dropping old value of key and adding new."
# Sort the keys to make sure the result is canonical.
d = dict(tuples)
d[key] = val
return tuple(sorted(d.items()))
def locs(start, n, incr=1):
"Return a tuple of n locations, starting at start and go up by incr."
return tuple(start+i*incr for i in range(n))
def grid(cars, N=N):
"""Return a tuple of (object, locations) pairs -- the format expected for
this puzzle. This function includes a wall pair, ('|', (0, ...)) to
indicate there are walls all around the NxN grid, except at the goal
location, which is the middle of the right-hand wall; there is a goal
pair, like ('@', (31,)), to indicate this. The variable 'cars' is a
tuple of pairs like ('*', (26, 27)). The return result is a big tuple
of the 'cars' pairs along with the walls and goal pairs."""
goals = ((N**2)//2 - 1,)
walls = (locs(0, N) + locs(N*(N-1), N) + locs(N, N-2, N)
+ locs(2*N-1, N-2, N))
walls = tuple(w for w in walls if w not in goals)
return cars + (('|', walls), ('@', goals))
def test_parking():
assert valid_solution(puzzle1, 4)
assert valid_solution(puzzle2, 7)
assert valid_solution(puzzle3, 7)
assert valid_solution(puzzle4, 8)
assert locs(26, 2) == (26, 27)
assert locs(20, 3, 8) == (20, 28, 36)
assert same_state(
grid((('*', locs(25, 2)),
('B', locs(19, 3, N)),
('P', locs(36, 3)),
('O', locs(45, 2, N)),
('Y', locs(49, 3)))),
(('*', (25, 26)), ('B', (19, 27, 35)), ('P', (36, 37, 38)),
('O', (45, 53)), ('Y', (49, 50, 51)),
('|', (0, 1, 2, 3, 4, 5, 6, 7, 56, 57, 58, 59, 60, 61, 62, 63,
8, 16, 24, 32, 40, 48, 15, 23, 39, 47, 55)),
('@', (31,))))
return "Test Pass!"
puzzle1 = grid((
('*', locs(26, 2)),
('G', locs(9, 2)),
('Y', locs(14, 3, N)),
('P', locs(17, 3, N)),
('O', locs(41, 2, N)),
('B', locs(20, 3, N)),
('A', locs(45, 2))))
puzzle2 = grid((
('*', locs(26, 2)),
('B', locs(20, 3, N)),
('P', locs(33, 3)),
('O', locs(41, 2, N)),
('Y', locs(51, 3))))
puzzle3 = grid((
('*', locs(25, 2)),
('B', locs(19, 3, N)),
('P', locs(36, 3)),
('O', locs(45, 2, N)),
('Y', locs(49, 3))))
puzzle4 = grid((
('*', locs(26, 2)),
('G', locs(9, 2)),
('Y', locs(14, 3, N)),
('P', locs(17, 3, N)),
('O', locs(41, 2, N)),
('B', locs(20, 3, N)),
('A', locs(45, 2)),
('S', locs(51, 3))))
def valid_solution(puzzle, length):
"Does solve_parking_puzzle solve this puzzle in length steps?"
path = solve_parking_puzzle(puzzle)
return (len(path_actions(path)) == length and
same_state(path[0], puzzle) and
is_goal(path[-1]) and
all(legal_step(path[i:i+3]) for i in range(0,len(path)-2, 2)))
def legal_step(path):
"A legal step has an action that leads to a valid successor state."
# Here the path must be of the form [s0, a, s1].
state1, action, state2 = path
succs = psuccessors(state1)
return state2 in succs and succs[state2] == action
def same_state(state1, state2):
"Two states are the same if all corresponding sets of locs are the same."
d1, d2 = dict(state1), dict(state2)
return all(set(d1[key]) == set(d2[key]) for key in set(d1) | set(d2))
from functools import update_wrapper
def decorator(d):
"Make function d a decorator: d wraps a function fn."
def _d(fn):
return update_wrapper(d(fn), fn)
update_wrapper(_d, d)
return _d
@decorator
def memo(f):
"""Decorator that caches the return value for each call to f(args).
Then when called again with same args, we can just look it up."""
cache = {}
def _f(*args):
try:
return cache[args]
except KeyError:
cache[args] = result = f(*args)
return result
except TypeError:
# some element of args refuses to be a dict key
return f(args)
_f.cache = cache
return _f
@memo
def shortest_path_search(start, successors, is_goal):
"""Find the shortest path from start state to a state
such that is_goal(state) is true."""
if is_goal(start):
return [start]
explored = set() # set of states we have visited
frontier = [ [start] ] # ordered list of paths we have blazed
while frontier:
path = frontier.pop(0)
s = path[-1]
for (state, action) in successors(s).items():
if state not in explored:
explored.add(state)
path2 = path + [action, state]
if is_goal(state):
return path2
else:
frontier.append(path2)
return []
def path_actions(path):
"Return a list of actions in this path."
return path[1::2]
print test_parking()
In [26]:
"""
In the game of darts, players throw darts at a board to score points.
The circular board has a 'bulls-eye' in the center and 20 slices
called sections, numbered 1 to 20, radiating out from the bulls-eye.
The board is also divided into concentric rings. The bulls-eye has
two rings: an outer 'single' ring and an inner 'double' ring. Each
section is divided into 4 rings: starting at the center we have a
thick single ring, a thin triple ring, another thick single ring, and
a thin double ring. A ring/section combination is called a 'target';
they have names like 'S20', 'D20' and 'T20' for single, double, and
triple 20, respectively; these score 20, 40, and 60 points. The
bulls-eyes are named 'SB' and 'DB', worth 25 and 50 points
respectively. Illustration (png image): http://goo.gl/i7XJ9
There are several variants of darts play; in the game called '501',
each player throws three darts per turn, adding up points until they
total exactly 501. However, the final dart must be in a double ring.
Your first task is to write the function double_out(total), which will
output a list of 1 to 3 darts that add up to total, with the
restriction that the final dart is a double. See test_darts() for
examples. Return None if there is no list that achieves the total.
Often there are several ways to achieve a total. You must return a
shortest possible list, but you have your choice of which one. For
example, for total=100, you can choose ['T20', 'D20'] or ['DB', 'DB']
but you cannot choose ['T20', 'D10', 'D10'].
"""
singles = range(1, 21) + [25]
points = set(m*s for s in singles for m in (1,2,3) if m*s != 75)
doubles = set(2*s for s in singles)
ordered_points = [0] + sorted(points, reverse=True)
def double_out(total):
"""Return a shortest possible list of targets that add to total,
where the length <= 3 and the final element is a double.
If there is no solution, return None."""
if total > 60 + 60 + 50:
return None
for dart1 in ordered_points:
for dart2 in ordered_points:
dart3 = total - dart1 - dart2
if dart3 in doubles:
solution = [name(dart1), name(dart2), name(dart3, 'D')]
return [t for t in solution if t != 'OFF']
return None
def name(d, double=False):
"""Given an int, d, return the name of a target that scores d.
If double is true, the name must start with 'D', otherwise,
prefer the order 'S', then 'T', then 'D'."""
return ('OFF' if d == 0 else
'DB' if d == 50 else
'SB' if d == 25 else
'D'+str(d//2) if (d in doubles and double) else
'S'+str(d) if d in singles else
'T'+str(d//3) if (d % 3 == 0) else
'D'+str(d//2))
def test_darts():
"Test the double_out function."
assert double_out(170) == ['T20', 'T20', 'DB']
assert double_out(171) == None
assert double_out(100) in (['T20', 'D20'], ['DB', 'DB'])
for total in range(2, 159) + [160, 161, 164, 167, 170]:
assert valid_out(double_out(total), total)
for total in [0, 1, 159, 162, 163, 165, 166, 168, 169, 171, 200]:
assert double_out(total) == None
return "Test Pass!"
def valid_out(darts, total):
"Does this list of targets achieve the total, and end with a double?"
return (0 < len(darts) <= 3 and darts[-1].startswith('D')
and sum(map(value, darts)) == total)
def value(target):
"The numeric value of a target."
if target == 'OFF': return 0
ring, section = target[0], target[1:]
r = 'OSDT'.index(target[0])
s = 25 if section == 'B' else int(section)
return r * s
print test_darts()
In [28]:
from collections import defaultdict
def best_target(miss):
"Return the target that maximizes the expected score."
return max(targets, key=lambda t: expected_value(t, miss))
def expected_value(target, miss):
"The expected score of aiming at target with a given miss ratio."
return sum(value(t)*p for (t, p) in outcome(target, miss).items())
def outcome(target, miss):
"Return a probability distribution of [(target, probability)] pairs."
results = defaultdict(float)
for (ring, ringP) in ring_outcome(target, miss):
for (sect, sectP) in section_outcome(target, miss):
if ring == 'S' and sect.endswith('B'):
# If sect hits bull, but ring misses out to S ring,
# then spread the results over all sections.
for s in sections:
results[Target(ring, s)] += (ringP * sectP) / 20.
else:
results[Target(ring, sect)] += (ringP * sectP)
return dict(results)
def ring_outcome(target, miss):
"Return a probability distribution of [(ring, probability)] pairs."
hit = 1.0 - miss
r = target[0]
if target == 'DB': # misses tripled; can miss to SB or to S
miss = min(3*miss, 1.)
hit = 1. - miss
return [('DB', hit), ('SB', miss/3.), ('S', 2./3.*miss)]
elif target == 'SB': # Bull can miss in either S or DB direction
return [('SB', hit), ('DB', miss/4.), ('S', 3/4.*miss)]
elif r == 'S': # miss ratio cut to miss/5
return [(r, 1.0 - miss/5.), ('D', miss/10.), ('T', miss/10.)]
elif r == 'D': # Double can miss either on board or off
return [(r, hit), ('S', miss/2), ('OFF', miss/2)]
elif r == 'T': # Triple can miss in either direction, but both are S
return [(r, hit), ('S', miss)]
def section_outcome(target, miss):
"Return a probability distribution of [(section, probability)] pairs."
hit = 1.0 - miss
if target in ('SB', 'DB'):
misses = [(s, miss/20.) for s in sections]
else:
i = sections.index(target[1:])
misses = [(sections[i-1], miss/2), (sections[(i+1)%20], miss/2)]
return [(target[1:], hit)] + misses
def Target(ring, section):
"Construct a target name from a ring and section."
if ring == 'OFF':
return 'OFF'
elif ring in ('SB', 'DB'):
return ring if (section == 'B') else ('S' + section)
else:
return ring + section
sections = "20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5".split()
targets = set(r+s for r in 'SDT' for s in sections) | set(['SB', 'DB'])
def same_outcome(dict1, dict2):
"Two states are the same if all corresponding sets of locs are the same."
return all(abs(dict1.get(key, 0) - dict2.get(key, 0)) <= 0.0001
for key in set(dict1) | set(dict2))
def test_darts2():
assert best_target(0.0) == 'T20'
assert best_target(0.1) == 'T20'
assert best_target(0.4) == 'T19'
assert same_outcome(outcome('T20', 0.0), {'T20': 1.0})
assert same_outcome(outcome('T20', 0.1),
{'T20': 0.81, 'S1': 0.005, 'T5': 0.045,
'S5': 0.005, 'T1': 0.045, 'S20': 0.09})
assert same_outcome(
outcome('SB', 0.2),
{'S9': 0.016, 'S8': 0.016, 'S3': 0.016, 'S2': 0.016, 'S1': 0.016,
'DB': 0.04, 'S6': 0.016, 'S5': 0.016, 'S4': 0.016, 'S20': 0.016,
'S19': 0.016, 'S18': 0.016, 'S13': 0.016, 'S12': 0.016,
'S11': 0.016, 'S10': 0.016, 'S17': 0.016, 'S16': 0.016, 'S15':
0.016, 'S14': 0.016, 'S7': 0.016, 'SB': 0.64})
assert same_outcome(outcome('T20', 0.3),
{'S1': 0.045, 'T5': 0.105, 'S5': 0.045,
'T1': 0.105, 'S20': 0.21, 'T20': 0.49})
assert best_target(0.6) == 'T7'
return "Test Pass!"
print test_darts2()
In [34]:
from collections import defaultdict
def natalie(words):
"Find the best Portmanteau word formed from any two of the list of words."
# First find all (start, mid, end) triples, then find the best scoring one
triples = alltriples(words)
if not triples: return None
return ''.join(max(triples, key=portman_score))
def alltriples(words):
"""All (start, mid, end) pairs where start+mid and mid+end are in words
(and all three parts are non-empty)."""
# First compute all {mid: [end]} pairs, then for each (start, mid) pair,
# grab the [end...] entries, if any. This approach make two O(N)
# passes over the words (and O(number of letters) for each word), but is
# much more efficient than the naive O(N^2) algorithm of looking at all
# word pairs.
ends = compute_ends(words)
return [(start, mid, end)
for w in words
for start, mid in splits(w)
for end in ends[mid]
if w != mid+end]
def splits(w):
"Return a list of splits of the word w into two non-empty pieces."
return [(w[:i], w[i:]) for i in range(1, len(w))]
def compute_ends(words):
"Return a dict of {mid: [end, ...]} entries."
ends = defaultdict(list)
for w in words:
for mid, end in splits(w):
ends[mid].append(end)
return ends
def portman_score(triple):
"Return the numeric score for a (start, mid, end) triple."
S, M, E = map(len, triple)
T = S+M+E
return T - abs(S-T/4.) - abs(M-T/2.) - abs(E-T/4.)
def test_natalie():
"Some test cases for natalie"
assert (natalie(['eskimo', 'escort', 'kimchee', 'kimono', 'cheese'])
== 'eskimono')
assert (natalie(['kimono', 'kimchee', 'cheese', 'serious', 'us', 'usage'])
== 'kimcheese')
assert (natalie(['circus', 'elephant', 'lion', 'opera', 'phantom'])
== 'elephantom')
assert (natalie(['adolescent', 'scented', 'centennial', 'always',
'ado', 'centipede'])
in ( 'adolescented', 'adolescentennial', 'adolescentipede'))
assert (natalie(['programmer', 'coder', 'partying', 'merrymaking'])
== 'programmerrymaking')
assert (natalie(['int', 'intimate', 'hinter', 'hint', 'winter'])
== 'hintimate')
assert (natalie(['morass', 'moral', 'assassination'])
== 'morassassination')
assert (natalie(['entrepreneur', 'academic', 'doctor',
'neuropsychologist', 'neurotoxin', 'scientist', 'gist'])
in ('entrepreneuropsychologist', 'entrepreneurotoxin'))
assert (natalie(['perspicacity', 'cityslicker', 'capability', 'capable'])
== 'perspicacityslicker')
assert (natalie(['backfire', 'fireproof', 'backflow', 'flowchart',
'background', 'groundhog'])
== 'backgroundhog')
assert (natalie(['streaker', 'nudist', 'hippie', 'protestor',
'disturbance', 'cops'])
== 'nudisturbance')
assert (natalie(['night', 'day']) == None)
assert (natalie(['dog', 'dogs']) == None)
assert (natalie(['test']) == None)
assert (natalie(['']) == None)
assert (natalie(['ABC', '123']) == None)
assert (natalie([]) == None)
assert (natalie(['pedestrian', 'pedigree', 'green', 'greenery'])
== 'pedigreenery')
assert (natalie(['armageddon', 'pharma', 'karma', 'donald', 'donut'])
== 'pharmageddon')
assert (natalie(['lagniappe', 'appendectomy', 'append', 'lapin'])
== 'lagniappendectomy')
assert (natalie(['angler', 'fisherman', 'boomerang', 'frisbee', 'rangler',
'ranger', 'rangefinder'])
in ('boomerangler', 'boomerangefinder'))
assert (natalie(['freud', 'raelian', 'dianetics', 'jonestown', 'moonies'])
== 'freudianetics')
assert (natalie(['atheist', 'math', 'athlete', 'psychopath'])
in ('psychopatheist', 'psychopathlete'))
assert (natalie(['hippo', 'hippodrome', 'potato', 'dromedary'])
== 'hippodromedary')
assert (natalie(['taxi', 'taxicab', 'cabinet', 'cabin',
'cabriolet', 'axe'])
in ('taxicabinet', 'taxicabriolet'))
assert (natalie(['pocketbook', 'bookmark', 'bookkeeper', 'goalkeeper'])
in ('pocketbookmark', 'pocketbookkeeper'))
assert (natalie(['athlete', 'psychopath', 'athletic', 'axmurderer'])
in ('psychopathlete', 'psychopathletic'))
assert (natalie(['info', 'foibles', 'follicles'])
== 'infoibles')
assert (natalie(['moribund', 'bundlers', 'bundt'])
== 'moribundlers')
return "Test Pass!"
print test_natalie()
Out[34]:
In [ ]: