>>> assert contract("1 1 1 2 2 3") == "3*1 2*2 1*3"
    >>> assert contract("1 1 3 2 3") == "2*1 1*3 1*2 1*3"

def contract(s):
    """
    >>> assert contract("1 1 1 2 2 3") == "3*1 2*2 1*3"
    >>> assert contract("1 1 3 2 3") == "2*1 1*3 1*2 1*3"
    """
    if not s: return s

    tokens = s.split()
    old = tokens[0]
    count = [[1, old]]

    for t in tokens[1:]:
        if t == old:
            count[-1][0] += 1
        else:
            old = t
            count.append([1, t])

    return " ".join("%d*%s" % (c, t) for c, t in count)