Kattis Battle Simulation

Question

I have a working program for a problem, but need to optimize it in a way where the processing time is less than 3 seconds. This is where I found the problem:

https://open.kattis.com/problems/battlesimulation

Condensed description of the problem:

The input is a string that represents a combination of attacks from a monster (R, B, and L).
The program checks the attacks and provides a counter move based on the letter ('S' to counter 'R', 'K' to counter 'B', and 'H' to counter 'L').

However, if the combination of attacks is in the list called Combos ("RBL", "RLB", "BLR", "BRL", "LBR", "LRB"), your counter is a 'C' as opposed to what it would have been.

Sample	Input	Output
1	RRBBBLLR	SSKKKHHS
2	RBLBR	CKS

This is my code so far:

attack = input()

combos = ("RBL", "RLB", "BLR", "BRL", "LBR", "LRB")
counterattack = {"R": "S", "B": "K", "L": "H"}

defense = ''
b = -1

for i in range(len(attack)):
    if b-2 <= i <= b:
        continue
    if i < (len(attack)-2):
        combo = attack[i] + attack[i+1] + attack[i+2]
        if combo in combos:
            defense += "C"
            b = i+2
        else:
            defense += counterattack[attack[i]]
    else:
        defense += counterattack[attack[i]]

print(defense)

The b is just so that the for loop skips two letters if there is a combo. I couldn't find a way to do it without that.

And this was my first attempt:

attack = input()

combos = {"RBL", "RLB", "BLR", "BRL", "LBR", "LRB"}
counterattack = {"R": "S", "B": "K", "L": "H"}

defense = ''

while len(attack) >= 3:
    combo = attack[:3]
    if combo in combos:
        defense += "C"
        attack = attack[3:]
    else:
        defense += counterattack[attack[0]]
        attack = attack[1:]
for el in attack:
    defense += counterattack[el]
    
print(defense)

Could the problem be that I put too many if statements? How else could I check for the combo in the input?

Answer 1

Function

Put this code in a function. This way, you'll be able to easily test it on your system. Something like

def battle_simulator(attacks: str) -> str:
    ...

if __name__ == "__main__":
    print(battle_simulator(input())

This is a very good habit to do so.

Strings

Strings are immutable in Python. This means whenever you're changing a string, it creates a whole new object and often copies all the data. Try to avoid it:

defense = [] #list
...
defense.append(...) #instead of +=
...
return ''.join(defense)

The same applies to a simple adding: slices are faster. attack[i:i+3] is faster than attack[i]+attack[i+1]+attack[i+2], which creates 5 new objects.

Excessive check

i is always greater than b-2, no need to check

PEP8

Google it and try to make your code comply.

Conclusion

This is my refactoring of your code. I've checked, it passes tests:

def battle_simulator(attack: str) -> str:
    COMBOS = {"RBL", "RLB", "BLR", "BRL", "LBR", "LRB"}
    COUNTERATTACKS = {"R": "S", "B": "K", "L": "H"}

    defense = []
    last_combo = -1

    for i in range(len(attack)):
        if i <= last_combo:
            continue
        if attack[i:i+3] in COMBOS:
            defense.append("C")
            last_combo = i+2
        else:
            defense.append(COUNTERATTACKS[attack[i]])

    return ''.join(defense)

if __name__ == "__main__":
    print(battle_simulator(input()))

And this is my first attempt to solve it, it passes too:

def battle_simulator(attack: str) -> str:
    result = []
    i = 0
    while i < len(attack):
        if len(set(attack[i:i+3]))==3:
            result.append('C')
            i += 3
        else:
            result.append({"R": "S", "B": "K", "L": "H"}[attack[i]])
            i += 1
    return ''.join(result)

Answer 2

Kattis uses PyPy, where building a string of n characters by repeatedly appending single characters apparently takes Θ(n²) time. Even just timeit("s += '.'", "s = ''", number=10**5) already takes over 4 seconds (Try it online!). So really better build a list and join like the others showed. (In CPython the same test btw takes like 0.008 seconds, thanks to some optimization.)

Or... make some string functions do the work for you. I'd use a regex for the combos and then translate the remaining attacks. Accepted in 0.17 seconds:

import re

s = input()

s = re.sub('RBL|RLB|BRL|BLR|LRB|LBR', 'C', s)
s = s.translate(s.maketrans('RBL', 'SKH'))

print(s)

Answer 3

My first guess would be to address this issue by turning "attack" into an iterator and by adding our three hit combos to our dictionary of counter moves:

Note: For larger strings (10k - 1m characters) this produces a result in about 1/3rd the time as your "current attempt".

def battle_sim(attack):
    ## --------------
    ## Get an attack iterator allowing us to use next()
    ## --------------
    attacks = iter(attack)
    ## --------------

    ## --------------
    ## We could always use strings like "RLB"
    ## but tuples are slightly faster to construct
    ## --------------
    counters = {
        "R": "S",
        "B": "K",
        "L": "H",
        ("R","B","L"): "C",
        ("R","L","B"): "C",
        ("B","L","R"): "C",
        ("B","R","L"): "C",
        ("L","B","R"): "C",
        ("L","R","B"): "C"
    }
    ## --------------

    counter_moves = []

    ## --------------
    ## Queue up the first two unhandled moves
    ## --------------
    prior_prior_move = next(attacks, None)
    prior_move = next(attacks, None)
    ## --------------

    ## --------------
    ## Process the remaining moves (if any)
    ## --------------
    for current_move in attacks:
        ## --------------
        ## In theory we should always have 3 unhandled moves to look at now
        ## --------------
        unhandled_moves = (prior_prior_move, prior_move, current_move) # a little faster than building a string key like "RBL"
        ## --------------

        ## --------------
        ## Find the proper counter starting with a look at a possible combo
        ## --------------
        counter_move = counters.get(unhandled_moves, counters.get(prior_prior_move))
        ## --------------

        ## --------------
        ## Apply our counter move
        ## --------------
        counter_moves.append(counter_move)
        ## --------------

        ## --------------
        ## reset our prior moves
        ## --------------
        prior_prior_move, prior_move = (next(attacks, None), next(attacks, None)) if counter_move == "C" else (prior_move, current_move)
        ## --------------
    ## --------------

    ## ------------------
    ## If there are still unhandle moves, handle them now
    ## ------------------
    for move in [prior_prior_move, prior_move]:
        if move:
            counter_moves.append(counters[move])
    ## ------------------

    return "".join(counter_moves)

attack = "RRBBBLLR"
print(battle_sim(attack) == "SSKKKHHS")

attack = "RBLLLBRR"
print(battle_sim(attack) == "CHCS")

attack = "RBLBR"
print(battle_sim(attack) == "CKS")

This "should" give you :

True
True
True

If you want a "bigger" test then you can:

import random
attack = "".join(random.choice(list("RLB")) for _ in range(10_000))
print(battle_sim(attack))