import unittest

def r(acc, n):
    if acc[0] == n:
        acc[1] += 1
        return acc
    acc[2].append((n, acc[1] + 1))
    acc[0] = n
    acc[1] += 1
    return acc

def findChanges(l):
    acc = ["",0,[]]
    return reduce(r, l, acc)[2]

def r2(acc, n):
    #d print "acc: %(acc)s n: %(n)s" % vars()
    if n[0] != n[1]:
        acc.append((n[1],n[2]))
    return acc

def findChangesDup(l):
    dup = map(None, [None] + l[:-1], l, range(len(l)))
    #d print "*** dup: " , dup
    return reduce(r2, dup, [])

def findChangesComp(l):
    dup = map(None, [None] + l[:-1], l, range(len(l)))
    return [t[1:] for t in dup if t[0] != t[1]]

class TestR(unittest.TestCase):
    def testR(self):
        pass
    def testFindChanges(self):
        self.assertEquals([], findChanges([]))
        self.assertEquals([('a', 1)], findChanges(['a']))
        self.assertEquals([('a', 1), ('b', 2), ('c', 3)], findChanges(list('abc')))
        self.assertEquals([('a', 1), ('b', 3), ('c', 4)], findChanges(list('aabc')))
        self.assertEquals([('a', 1), ('b', 2), ('c', 4), ('d', 7), ('e', 8), ('a', 9)], findChanges(list('abbcccdeaa')))
        self.assertEquals([('al', 1), ('bob', 2), ('john', 4), ('al', 7)], findChanges(['al', 'bob', 'bob', 'john', 'john', 'john', 'al']))
        self.assertEquals([('al', 1), ('bob', 2), ('john', 4), ('al', 7)], findChanges(['al', 'bob', 'bob', 'john', 'john', 'john', 'al', 'al', 'al']))

    def testFindChangesDup(self):
        self.assertEquals([], findChangesDup([]))
        self.assertEquals([('a', 0)], findChangesDup(['a']))
        self.assertEquals([('a', 0), ('b', 1), ('c', 2)], findChangesDup(list('abc')))
        self.assertEquals([('a', 0), ('b', 2), ('c', 3)], findChangesDup(list('aabc')))
        self.assertEquals([('a', 0), ('b', 1), ('c', 3), ('d', 6), ('e', 7), ('a', 8)], findChangesDup(list('abbcccdeaa')))
        self.assertEquals([('al', 0), ('bob', 1), ('john', 3), ('al', 6)], findChangesDup(['al', 'bob', 'bob', 'john', 'john', 'john', 'al']))
        self.assertEquals([('al', 0), ('bob', 1), ('john', 3), ('al', 6)], findChangesDup(['al', 'bob', 'bob', 'john', 'john', 'john', 'al', 'al', 'al']))


    def testFindChangesComp(self):
        self.assertEquals([], findChangesComp([]))
        self.assertEquals([('a', 0)], findChangesComp(['a']))
        self.assertEquals([('a', 0), ('b', 1), ('c', 2)], findChangesComp(list('abc')))
        self.assertEquals([('a', 0), ('b', 2), ('c', 3)], findChangesComp(list('aabc')))
        self.assertEquals([('a', 0), ('b', 1), ('c', 3), ('d', 6), ('e', 7), ('a', 8)], findChangesComp(list('abbcccdeaa')))
        owners = ['al', 'bob', 'bob', 'john', 'john', 'john', 'al']
        self.assertEquals([('al', 0), ('bob', 1), ('john', 3), ('al', 6)], findChangesComp(owners))
        self.assertEquals([('al', 0), ('bob', 1), ('john', 3), ('al', 6)], findChangesComp(owners + ['al', 'al']))


if __name__ == '__main__':
    unittest.main()