SRM 612: Python SRM II

This was the second SRM in which I used python exclusively, I think I did just okay.

Div1 250: The one with copy paste

You have one character, you want to reach smilies characters (smilies is between 2 and 1000). You have three operations: Delete one character. Copy all current characters to the clipboard and paste the characters from the clipboard (without replacing the current ones). What is the minimum number of steps?

Define state `(s,c)`, where `s` is the current number of characters and `c` the number of characters in clipboard. Then a delete operation is to move to `(s-1,c)`, a copy operation is to move to `(s,s)` and a paste operation is to move to `(s+c,c)`. The rest is just to code a Breadth-first-search (Or you know, A Dijkstra where all edge weights are 1), because we want to find the minimum-length path from `(1,0)` to any `("smilies",c)` (We start at `(1,0)` because there is one character and the clipboard is empty).

So I just needed to code BFS in python. I had a bit of difficulty because I forgot how to do queues in python... turns out you just do .pop(0) to remove and return the front element.

class EmoticonsDiv1:
 def printSmiles(self, smiles):
    v = [ (1,0) ]
    dist = dict()
    dist[(1,0)] = 0

    def neighbors(s,c):
        if s > 0:
            yield (s-1, c) #del
        yield (s,s)        #copy
        yield (s+c,c)      #paste
    
    # BFS
    while len(v) > 0:
        (s,c) = v.pop(0)
        d = dist[(s,c)]
        if s == smiles:
            return d            
        for x in neighbors(s,c):
            if x not in dist:
                dist[x] = d + 1
                v.append(x)

Why to do a BFS and not just a dynamic programming? The recurrence relation is cyclic. So, really, don't try to do dynamic programming here.

Note the cute usage of yield.

Later

Tried div1 medium but seems difficult. Decided to skip the rest of this SRM and finish the editorial for SRM 611.

I think python really helped me in this problem. I was able to quickly modify my tester to quickly test for all possible values of smilies, so I am quite sure I passed. I had a delay remembering about pop(0), but I also coded very quickly thanks to python, I think I would have taken a bit more time in c++-