practice

improving.py

"""
Given k and n, return a list of all the positive integers less than n 
such that the sum of the kth powers of their individual digits equals the integer itself.
For example, with k=3 and n=1000, one of the numbers we would return in the list would be 371, 
because 371 = 3^3 +7^3 + 1^3 = 27 + 343 + 1. (This problem inspired by Project Euler.) 

powersum(1, 10) → [1, 2, 3, 4, 5, 6, 7, 8, 9]
powersum(2, 100) → [1]
powersum(3, 1000) → [1, 153, 370, 371, 407]"""

def powersum(k, n):

    def equal(i):
        s = str(i)
        return sum(pow(int(i), k) for i in s) == i

    return [i for i in range(1, n) if equal(i)]

"""
In the card game SET, you try to find three cards that make a set.
Each card has four attributes: number of objects (1, 2, or 3), 
color (Red,Green, or Purple, which we abbreviate R,G,P);
solidity (outline, filled, or striped, abbreviated O,F,S);
and shape (oval, diamond or squiggle, abbreviated O,D,S).
Three cards form a set if each of the four attributes are either all the same or all different,
and is not a set if any attribute has two cards that are the same and one that is different. 
For example, the three cards "3RFD", "2RFD", "1RFD" 
(which corresponds to 3, 2, and 1 red filled diamonds)
is a set because they are all different numbers,
and all the same on the other three attributes.
But ['3RFD', '2GFO', '1PFO'] is not a set, because of the fourth attribute:
there is one diamond (D) and two ovals (O).
Write the function is_set(cards) 
which takes a list of three cards and returns True if the cards are a set. 

set_card_game(['3RFD', '2RFD', '1RFD']) → True
set_card_game(['3RFD', '2GFD', '1PFD']) → True
set_card_game(['3RFD', '2GFO', '1PFO']) → False
"""

def set_card_game(cards):
    attributes = [[card[i] for card in cards] for i in range(4)]
    for a in attributes:
        L = len(set(a))
        if L == 2:
            return False
    return True


"""
A mobile is a sculpture consisting of hanging things with rods connecting them.
Each thing can be either (1) a 'piece': a decorative design that we will
represent as a string, or (2) a complete mobile. For example '###' is a piece;
we say it has a weight of 3 (because it has a length of 3). A mobile can either
be a single piece, or it can be two mobiles connected by a rod, with a balance
point somewhere on the rod. We will use a list of length 4 to represent the
mobile: (L, Lrod, Rrod, R), where L and R are mobiles, and Lrod and Rrod are
integers representing the lengths of the rod to the left and right. The
function balanced(M) should return true if the mobile M is balanced: an
individual piece is always balanced, and a mobile with a rod is balanced if
each of the L and R pieces is balanced and if the weight of the L branch times
the distance Lrod is equal to the weight of the R branch times the distance
Rrod. The weight of a mobile is just the sum of the weights of the component
pieces (the rods are thin and their weight can be ignored). 

balanced(['###', 2, 3, '@@']) → True
balanced(['##', 1, 1, '@@@']) → False
balanced([[['@', 3, 1, 'cod'], 20, 10, ['whale', 3, 5, 'eel']], 17, 17,
['shark', 14, 10, 'octopus']]) → True"""


def balanced(m):
    return True if helper(m) else False

def helper(m):
    if isinstance(m, str):
        return True
    L, Lrod, Rrod, R = m
    L, R = weight(L), weight(R)
    if not L or not R:
        return False
    return mobile(L, Lrod, Rrod, R)

def mobile(L, Lrod, Rrod, R): 
    return L+R if len(L) * Lrod == Rrod * len(R) else False

#def weight(m):
#    return m if isinstance(m, list) else helper(m)
#
#def balanced(m):
#    if isinstance(m, str):
#        return True
#    L, Lrod, Rrod, R = m
#    return balanced(L) and balanced(R) and weight(L) * Lrod == weight(R) * Rrod
#
#def weight(m):
#    if isinstance(m, str):
#        return len(m)
#    else:
#        L, _, _, R = m
#        return weight(L) + weight(R)
""" 
In the game of Nim, there is a pile of cigars (or they could be squirrels). You
and another player take turns removing cigars from the pile. On each turn you
can take 1, 2, or 3. The player to take the last cigar wins. Write the function
nim(n), which returns the number of the n cigars you should take to guarantee
an eventual win regardless of what the other player does. If there is no way to
guarantee a win, just take 1 cigar -- leaving as big a pile as possible so
maybe the opponent will make a mistake.
nim(3) → 3
nim(7) → 3
nim(8) → 1
"""
def nim(n):
    return (n if n <= 3 else
            3 if loss(n-3) else
            2 if loss(n-2) else
            1)

def win(n):
    return n <= 3 or loss(n-3) or loss(n-2) or loss(n-1)

def loss(n):
    return not win(n)

"""
We want to make a row of bricks that is goal inches long. We have a number of
small bricks (1 inch each) and big bricks (5 inches each). Return True if it is
possible to make the goal by choosing from the given bricks. This is a little
harder than it looks and can be done without any loops. See also: Introduction
to MakeBricks 

make_bricks(3, 1, 8) → True
make_bricks(3, 1, 9) → False
make_bricks(3, 2, 10) → True

"""

def make_bricks(small, big, goal):
    c, r = divmod(goal, 5) 
    return goal - 5*smaller(big,c) <= small

def smaller(a, b):
    return a if b>a else b

"""

Given a string, does "xyz" appear in the middle of the string?
To define middle,
we'll say that the number of chars
to the left and right of the "xyz" must differ by at most one.
This problem is harder than it looks. 

xyzMiddle("AAxyzBB") → true
xyzMiddle("AxyzBB") → true
xyzMiddle("AxyzBBB") → false
"""

def xyzMiddle(s):
    L = s.index('xyz')
    return abs(len(s[:L]) - len(s[L+3:])) <= 1


"""
Given 3 int values, a b c, return their sum.
However, if one of the values is the same as another of the values,
it does not count towards the sum. 

lone_sum(1, 2, 3) → 6
lone_sum(3, 2, 3) → 2
lone_sum(3, 3, 3) → 0 """

def lone_sum(a, b, c):
    s = set([a, b, c])
    return (0 if len(s) == 1 else 
            sum(s) if len(s) == 3 else
            [e for e in s if [a, b, c].count(e) == 1][0])

"""

Given 3 int values, a b c, return their sum. However,
if one of the values is 13 then it does not count towards the sum
and values to its right do not count. So for example,
if b is 13, then both b and c do not count. 

lucky_sum(1, 2, 3) → 6
lucky_sum(1, 2, 13) → 3
lucky_sum(1, 13, 3) → 1"""

def lucky_sum(a, b, c):
    if a == 13:
        return 0
    elif b == 13:
        return a
    elif c == 13:
        return a+b
    return a+b+c

"""

Given 3 int values, a b c, return their sum.
However, if any of the values is a teen -- in the range 13..19 inclusive --
then that value counts as 0, except 15 and 16 do not count as a teens.
Write a separate helper 
"def fix_teen(n):"that takes in an int value and returns that value fixed for the teen rule.
In this way, you avoid repeating the teen code 3 times (i.e. "decomposition"). 
Define the helper below and at the same indent level as the main no_teen_sum(). 

no_teen_sum(1, 2, 3) → 6
no_teen_sum(2, 13, 1) → 3
no_teen_sum(2, 1, 14) → 3"""

Teens = [13, 14, 17, 18, 19]
def no_teen_sum(a, b, c):
    return sum(fix_teen(i) for i in (a, b, c))

def fix_teen(n):
    return 0 if n in Teens else n

"""
For this problem, we'll round an int value up to the next multiple of 10 if its
rightmost digit is 5 or more, so 15 rounds up to 20. Alternately, round down to
the previous multiple of 10 if its rightmost digit is less than 5, so 12 rounds
down to 10. Given 3 ints, a b c, return the sum of their rounded values. To
avoid code repetition, write a separate helper "def round10(num):" and call it
3 times. Write the helper entirely below and at the same indent level as
round_sum(). 

round_sum(16, 17, 18) → 60
round_sum(12, 13, 14) → 30
round_sum(6, 4, 4) → 10 
"""

def round_sum(a, b, c):
    return int(sum(map(round10, [a, b, c])))

def round10(n):
    if n < 10:
        s = '0' + str(n)
    else:
        s = str(n)
    i = '.'.join(s)
    return round(float(i)) * 10

#def round_sum(a, b, c):
#    return sum(map(round10, [a, b, c]))
#
#def round10(n):
#    mod = n % 10
#    n -= mod
#    if mod >= 5:
#        n += 10
#    return n
#

"""

A bowling game consists of ten frames. In each frame you get up to two balls to
attempt to knock down the 10 pins. If you knock down all 10 pins on the first
ball, that's called a strike; congratulations, sit down, you're done for the
frame, and you only used one ball. However, the scoring for the frame involves
more than just the one ball you used: you get 10 points for knocking down the
10 pins, plus whatever score you get on the next two balls (those balls will
count both in this frame and the next). If you don't get all the pins on your
first ball, you use a second ball; if that knocks down the remaining pins it is
called a spare. The score for a spare is 10 for the pins you knocked down with
the two balls, plus whatever you score on your next ball (which will also be
counted in the next frame). Finally, if you get less than 10 pins down on the
two balls, that's called an open frame; you score the total of the two balls.
Some examples: if your first three balls are [10, 3, 4], then the 10 is a
strike; score 10+3+4 = 17 for the first frame, and 3+4 = 7 on the second frame.
If you roll a [7, 3, 5, 4], then the 7-3 is a spare, score 7+3+5 = 15 in the
first frame, and the 5+4 = 9 on the second frame. The score for the game is the
sum of the scores for the ten frames. One exception to these rules: if you get
a spare or strike in the tenth frame, you roll three balls in that frame and
score their total -- that is the only case where you use more than two balls in
a frame (and the only case where the extra balls after a spare or strike only
count once). Write the function bowling(balls) which is passed a list of
integers indicated the number of pins knocked down for each ball. You can
assume that the list has exactly the right number of entries: it won't stop
before the end of the tenth frame, nor go beyond it. """

""" bowling([9, 1, 0, 10, 10, 10, 6, 2, 7, 3, 8, 2, 10, 9, 0, 9, 1, 10]) → 168
    bowling([10, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) → 24
    bowling([10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]) → 300"""

def bowling(scores):
    current_frame, frames = [], []
    for pos in range(0, len(scores)):
        if len(frames) == 9:
            return sum(scores[pos:]) + sum(frames)
        current_frame.append(scores[pos])
        if current_frame[-1] == 10:
            frames.append(10 + scores[pos+1] + scores[pos+2])
            current_frame = []
        if len(current_frame) == 2:
            if sum(current_frame) == 10:
                frames.append(10 + scores[pos+1])
            else:
                frames.append(sum(current_frame))
            current_frame = [] 

#def bowling(balls):
#    total = 0
#    for frame in range(1, 11):
#        used, scoring = analyze_frame(frame, balls)
#        total += sum(balls[:scoring])
#        balls = balls[used:]
#    return total
#
#def analyze_frame(frame, balls):
#    if frame == 10:
#        return len(balls), len(balls)
#    if balls[0] == 10:
#        return 1, 3
#    if balls[0] + balls[1] == 10:
#        return 2, 3
#    else:
#        return 2, 2
#
"""

When the mathematical genius Srinivasa Ramanujan was dying of tuberculosis in a
hospital, his friend G. H. Hardy, the leading mathematician in England at the
time, would visit. C. P. Snow reports that on one of those visits: "Hardy had
gone out to Putney by taxi, as usual his chosen method of conveyance. He went
into the room where Ramanujan was lying. Hardy, always inept about introducing
a conversation, said, probably without a greeting, and certainly as his first
remark: 'I thought the number of my taxicab was 1729. It seemed to me rather a
dull number.' To which Ramanujan replied: 'No, Hardy! No, Hardy! It is a very
interesting number. It is the smallest number expressible as the sum of two
cubes in two different ways.'" Since then, integer solutions to: M = I^3 + J^3
= K^3 + L^3 have been called Ramanujan Numbers. Write ramanujan(N) to return a
list of all [M, I, J, K, L] tuples that satisfy this relation, sorted by
smallest M value first, with the restriction that I,J,K,L are all less than N,
the input to the function. So as not to list duplicates, only give answers
where I<=J, K<=L, and I<K. 

ramanujan(10) → []
ramanujan(15) → [[1729, 1, 12, 9, 10]]
ramanujan(20) → [[1729, 1, 12, 9, 10], [4104, 2, 16, 9, 15]]

"""
# too wasteful
def ramanujan(N):
    n = range(N)
    return [[I**3 + J**3, I, J, K, L] 
            for I in n 
            for J in n
            for K in n
            for L in n
            if I**3 + J**3 == K**3 + L**3 and
            I <= J and K <= L and I < K]

#much better
#def ramanujan(N):
#    n = range(N)
#    d, res = {}, []
#    for K in n:
#        for L in n:
#            M = K**3 + L**3
#            old = d.get(M)
#            if not old:
#                d[M] = [K, L]
#            else:
#                oldK, oldL = d[M]
#                if not (K in d[M] and L in d[M]) and K <= L: 
#                    res.append([M, oldK, oldL, K, L])
#    return res

"""

You are in a grid of city blocks, and you want to know how many different paths
there are between your current corner and a destination corner (without taking
any steps in the wrong direction). The current corner is given by two
non-negative integers x, y indicating the number of blocks east and north you
are, respectively, of the destination (in other words the desitination is at
0,0). For example, if you start at (1, 1) then there are 2 paths: you could go
west one block and then south, or south one block and then west. If you start
at (2, 1) there are three paths: [west, west, south], [west, south, west], and
[south, west, west]. Write num_paths(x, y) that returns the number of paths
from location x,y to the destination 0,0. (You don't need to say what the
individual paths are, just count them.) 

num_paths(1, 1) -> 2
num_paths(5, 0) -> 1
num_paths(0 ,10) -> 1
"""

def num_paths(x, y):
    if x == 0 or y == 0:
        return 1
    return num_paths(x-1, y) + num_paths(x, y-1)


"""
 "I noticed that the last 4 digits were palindromic. I drove a mile, and the
 last 5 were palindromic. I drove another mile and the middle 4 were
 palindromic, and the ends were not involved. And then one mile later, all 6
 digits were palindromic." The question is, what did Terry see on the odometer
 when he first looked?"""


def is_pal(m):
    return m == m[::-1]

def meterPuzzle():
    return  next((M)
            for M in range(100000, 1000000)
            if is_pal(str(M)[-4:])
            if is_pal(str(M+1)[-5:])
            if is_pal(str(M+2)[-5:-1])
            if is_pal(str(M+3)))

def palindromic_odometer(M):
    return (is_pal(str(M)[-4:])
            and is_pal(str(M+1)[-5:])
            and is_pal(str(M+2)[-5:-1])
            and is_pal(str(M+3)))

"""
Then, the temperature comes up in Fahrenheit, and a few seconds later it comes
up in centigrade. Stevie says, "Hah! That's interesting. The digits are exactly
reversed." For example, it might have read 31 degrees Fahrenheit, and when it
showed the centigrade reading it said "13." He thinks, "I've never seen that
before." The light turns green, and off he goes to work. Well, because he got
to work so late, he decided to stay late. When he comes out of work, he
realizes he should have checked the weather forecast, because it's drizzly,
rainy, and cold. He's riding home, when he comes to the same intersection. He
thinks, "What are the chances I'd ever see that again?" He knows it's a
different temperature because it's not warm and sunny like it was when he went
to work, and now it's cold, drizzly, and rainy. He sees the temperature in
Fahrenheit, and the temperature in centigrade. TOM: Let me guess! They're the
same digits reversed, again. RAY: What are the chances? Only in a puzzler could
this happen! The question is, what was the temperature in the morning when he
went to work, and what was the temperature when he went home? For CodingBat,
return your answer as a list of two numbers, in Fahrenheit. I apologize that
the single test case gives away the solution. Of course you could define
stevie_and_his_moto to just do """

def F_to_C(f):
    return int(round(5 * (f - 32) / 9.0))

def steevie_and_his_moto():
    return [x for x in range(99, 33, -1)
            if str(F_to_C(x)) == str(x)[::-1]]


""" 
This is Car Talk Puzzler #201144, Hall of Lights: RAY: This puzzler is from my
"ceiling light" series. Imagine, if you will, that you have a long, long
corridor that stretches out as far as the eye can see. In that corridor,
attached to the ceiling are lights that are operated with a pull cord. There
are gazillions of them, as far as the eye can see. Let's say there are 20,000
lights in a row. They're all off. Somebody comes along and pulls on each of the
chains, turning on each one of the lights. Another person comes right behind,
and pulls the chain on every second light. TOM: Thereby turning off lights 2,
4, 6, 8 and so on. RAY: Right. Now, a third person comes along and pulls the
cord on every third light. That is, lights number 3, 6, 9, 12, 15, etcetera.
Another person comes along and pulls the cord on lights number 4, 8, 12, 16 and
so on. Of course, each person is turning on some lights and turning other
lights off. If there are 20,000 lights, at some point someone is going to come
skipping along and pull every 20,000th chain. When that happens, some lights
will be on, and some will be off. Can you predict which lights will be on?
Write hall_of_lights(n), which, when passed a number of lights, n, returns the
list of the light numbers that will be on when all the switching is done. The
result should be a list of integers, in increasing order, but whereas Python
uses index 0 for the first light, this puzzle calls the first light number 1,
so that's what you should do.""" 

#hall_of_lights(20) → [2, 5, 10, 17]
#hall_of_lights(2) → [2]
#hall_of_lights(1) → []

def hall_of_lights(n):
    lis = [1] + [1 for i in range(n)] 
    for d in range(2, n):
        for i in range(d, n, d): 
            lis[i] = not lis[i]
    return [i+1 for i in range(1, len(lis)-1) if lis[i]]

"""
 if she's 73, I'm 37. We wondered how often this has happened over the years
     but we got sidetracked with other topics and we never came up with an
     answer. "When I got home I figured out that the digits of our ages have
     been reversible six times so far. I also figured out that if we're lucky
     it would happen again in a few years, and if we're really lucky it would
     happen one more time after that. In other words, it would have happened 8
     times over all. So the question is, how old am I now?" NOTE: to adapt this
     Puzzler to CodingBat, write flipping_ages(diff) as a function to return a
     list of Wendy's ages at which she is the reverse of her mom's age, given
     that their difference in age is diff. (Note: for the purpose of this
     puzzle, the reverse of "30" is "03".) To avoid giving away the answer to
     the Puzzler, the entry with the correct answer will be hidden in the
     "other tests"."""

def age_puzzle():
    return [Mom for Mom in range(100, 1, -1) if helper(Mom)][2]

#[95, 85, 75, 69, 68, 67, 65, 6]
# mom is 75 years old

def helper(Mom):
    return sum(reversible(m, w) for m, w in age_range(Mom)) == 6

def age_range(Mom):
    return zip(range(Mom, 0, -1), range(rev_age(Mom), 0, -1))

def rev_age(age):
    return int(str(age)[::-1])

def reversible(Mom, Wendy):
    return rev_age(Mom) == Wendy 

"""
ally invited 17 guests to a dance party at her estate in the Hamptons. She
assigned each guest a number from 2 to 18, keeping 1 for herself. At one point
in the evening when everyone was dancing, Sally noticed the sum of each
couple's numbers was a perfect square. Everyone was wearing their numbers on
their clothing. The question is, what was the number of Sally's partner? Here's
a reminder: a perfect square is attained by squaring, or multiplying by itself,
an integer. So four is a perfect square of two. Nine is a perfect square of
three. Sixteen is a perfect square of four. So these numbers are adding up to
either 4, 9, 16, 25, etc. And the question is, with the information you have
available to you, what's the number of her partner? Write the function
perfect_square_dance(n), which takes the number of dancers n as input. As
output, it should return not just Sally's partner, but a list of pairs of
partner numbers, sorted by lowest numbers first (both withn a pair and across
all pairs). Return None if it can't be done."""

"""
perfect_square_dance(18) → [[1, 15], [2, 14], [3, 13], [4, 12], [5, 11], [6, 10], [7, 18], [8, 17], [9, 16]]
perfect_square_dance(8) → [[1, 8], [2, 7], [3, 6], [4, 5]]
perfect_square_dance(10) → None
"""


def perfect_square_dance(n):
    squares = [i**2 for i in range(1, int((2*n)**.5))]
    mandatory = []
    numbers = range(1, n+1)
    candidates = dict((j, set(i for i in numbers if i+j in squares and i != j))
                       for j in range(1, n+1))
    return pair(candidates)

def pair(candidates):
    while candidates:
        if not any(len(candidates[k]) == 1 for k in candidates):
            return None
        for k, v in candidates.items():
            if len(v) == 1:
                x = v.pop()
                if k not in mandatory:
                    mandatory.append(k)
                if x not in mandatory:
                    mandatory.append(x)
                try:
                    candidates.pop(k)
                    candidates.pop(x)
                except KeyError:
                    continue
        for j, i in candidates.items():
            for k in mandatory:
                try:
                    i.remove(k)
                except KeyError:
                    continue
    res = [mandatory[i:i+2] for i in range(0, len(mandatory)-1, 2)]
    return sorted([sorted(r) for r in res])

# peter's solution fuck!! awesome
#def perfect_square_dance(n):
#    guests = range(1,n+1)
#    squares = set(i**2 for i in range(1,int((2*n)**.5)))
#    partners = dict((g, [p for p in guests if p!=g and p+g in squares]) for g in guests)
#    return pairup(guests, partners)
#
#def pairup(guests, partners):
#    if len(guests) == 0:
#        return []
#    g = guests[0]
#    for p in partners[g]:
#        if p in guests:
#            rest = pairup([x for x in guests[1:] if x != p], partners)
#            if rest is not None:
#                return [[g, p]] + rest
#
"""write a RPN so test pass"""

def test():
    assert RPN('1 2 +') == 3.0
    assert RPN('6 3 /') == 2.0
    assert RPN('1 2 3 4 5 +') == 9.0
    assert RPN('6 2 1 + / 2 -') == 0.0
    print 'pass'

def calc(b, a, oper):
    return (a * b if oper == '*' else
            a - b if oper == '-' else
            a / b if oper == '/' else
            a + b)

def RPN(expr):
    stack = []
    for e in expr.split(' '):
        res = (int(e) if e not in '+-/*' else
                calc(stack.pop(), stack.pop(), e))
        stack.append(res)
    return float(stack[-1])