pwnd speedy solution for Pawn Brotherhood by tarikki - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

pwnd solution in Speedy category for Pawn Brotherhood by tarikki

def safe_pawns(pawns):
    safe = 0
    pp = [] #possible protectors
    for pawn in pawns:
        pp.append(chr(ord(pawn[0])-1)+str(int(pawn[1])-1))  #a possible protector would be one down the alphabet, one line down
        pp.append(chr(ord(pawn[0])+1)+str(int(pawn[1])-1))  #or one up the alphabet, one line down
        if any(p in pawns for p in pp):                     #if the list of pawns has any of these two, 
            safe += 1                                       #the pawn in question is safe
        pp = []                                             #remember to reset the list
    return safe

if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert safe_pawns({"b4", "d4", "f4", "c3", "e3", "g5", "d2"}) == 6
    assert safe_pawns({"b4", "c4", "d4", "e4", "f4", "g4", "e5"}) == 1

Aug. 17, 2014

Comments:

nickie on Sept. 4, 2014, 9:04 p.m.
Could you explain why you think this solution is "speedy"?

tarikki on Oct. 5, 2014, 7:27 p.m.
Because you only have to iterate through the pawns once. At the beginning I thought of different implementations of this with more iterations, so I'm quite happy I came up with this solution :)

nickie on Oct. 5, 2014, 10:09 p.m.
But you're not iterating through the pawns just once. There's the "for pawn in pawns" loop and, inside, the "any (... for p in pp)". If you come to think of it, this is O(N^2) if N is the number of pawns.

tarikki on Oct. 6, 2014, 5:42 a.m.
Oh haha you're right! Should never reply to old posts too late at night! Thanks for pointing this out, will try to think of an O(N) solution or move it to "Clear".

Look up in the Dict()

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.