December 13th

Stables

Every OTHER night of the year, Father Christmas must call the reindeer from the fields, feed them and bed them down for the night in the stables. Their stalls are labelled: Dasher, Dancer, Prancer, Vixen, Rudolph, Comet, Cupid, Donder, Blitzen but they don't usually arrive in the correct order.

As each reindeer arrives you must locate its correct position in the line and move all the reindeer in front of it forward one space. Once the reindeer are in the correct order you can lead them into their stalls.

The Problem

You must rearrange each set of reindeer into the correct order, and count the TOTAL number of reindeer that had to be moved in the process. The correct order of the reindeer's stalls is (see picture): 

'DAS DAN PRA VIX RUD COM CUP DON BLI'


Examples

line1 = 'DAS DAN PRA'
arrived = 'BLI'
Result: Blitzen comes last, so just Insert at end. Total moves: 0

line2 = 'DAS DAN PRA BLI'
arrived = 'CUP'
Result: CUP needs to be inserted between PRA and BLI, so BLI has to move 1 space. Total moves: 1

line3 = 'DAS DAN PRA CUP BLI'
arrived = 'COM'
Result: COM needs to be inserted between PRA and CUP, so CUP and BLI both have to move 1 space. Total moves: 2

Decomposition

Compare

Since you're not sorting in alphabetic or numeric order, you'll first need to write a comparison function def later(r1, r2) which takes two reindeer and returns reindeer 1 if it should be later in the line or reindeer 2 if that reindeer should be later.

later('RUD', 'VIX')  # returns 'RUD'
later('VIX', 'COM')  # returns 'COM'
later('DAN', 'VIX')  # returns 'VIX'

Insert

Next write an insertion function: insert(line, arrival) which takes a line of deer and a new arrival and returns a list containing the total number of shifts and the new list of deer.

insert(['DAN', 'PRA'], 'DAS')
# returns [2,['DAS', 'DAN', 'PRA']] 

Sort

Finally, write an order(arrivals) function that takes a list of the deer in the order they arrive and returns the total number of insertion shifts it took to get them into the correct order and a list of the reindeer in the correct order so they can go into the stable:

start = 'DAN PRA DAS BLI CUP COM'.split(' ')
after = ['DAS', 'DAN', 'PRA', 'COM', 'CUP', 'BLI']
assert order(start) == [5, after]

Tips (Python)

Python lists have an 'index' method which returns the position of an item in a list. Useful for the 'later' comparison function:

['A', 'B', 'C', 'D'].index('C')  # returns 2


To add an item to the end of a list, use .append(item):

['A', 'B', 'C', 'D'].append('E')


You can join two lists with the + operator:

['A', 'B'] + ['C', 'D']  # returns ['A', 'B', 'C', 'D']

Testing

# Unit tests for sub-functions

# compare two reindeer, return right-most

assert later('RUD', 'VIX') == 'RUD'

assert later('VIX', 'COM') == 'COM'

assert later('DAN', 'VIX') == 'VIX'


# set up reindeer insertion sequence

wDAN = ['DAN']

wPRA = ['DAN', 'PRA']

wDAS = ['DAS', 'DAN', 'PRA']

wBLI = ['DAS', 'DAN', 'PRA', 'BLI']

wCUP = ['DAS', 'DAN', 'PRA', 'CUP', 'BLI']

wCOM = ['DAS', 'DAN', 'PRA', 'COM', 'CUP', 'BLI']


# Check each insertion gives correct result

assert insert(line=wDAN, arrival='PRA') == [0, wPRA]  # insert at end, so 0 moves required

assert insert(line=wPRA, arrival='DAS') == [2, wDAS]  # insert at start, so 2 moves required

assert insert(line=wDAS, arrival='BLI') == [0, wBLI]  # insert at end, so 0 moves required

assert insert(line=wBLI, arrival='CUP') == [1, wCUP]  # insert between PRA and BLI, so BLI has to move 1 space. Total moves: 1

assert insert(line=wCUP, arrival='COM') == [2, wCOM]  # insert between PRA and CUP, so CUP and BLI both have to move 1 space. Total moves: 2


# Integration tests

assert order(['DAN', 'PRA', 'DAS', 'BLI', 'CUP', 'COM']) == [5, ['DAS', 'DAN', 'PRA', 'COM', 'CUP', 'BLI']]

assert order(['DON', 'PRA', 'DAS', 'RUD']) == [4, ['DAS', 'PRA', 'RUD', 'DON']]


Your data set:

# the order of the reindeers' stalls

STALLS = ['DAS', 'DAN', 'PRA', 'VIX', 'RUD', 'COM', 'CUP', 'DON', 'BLI']


# the arrival order of the reindeer over 50 nights. Sort them, count the number of shifts required each night, and total ALL the shifts across all 50 nights.

nights = [['CUP', 'BLI', 'RUD', 'PRA'], ['PRA', 'DON', 'BLI', 'CUP', 'RUD', 'DAS', 'DAN'], ['CUP', 'PRA', 'RUD'], ['VIX', 'PRA', 'DAN', 'CUP', 'COM', 'DON', 'BLI'], ['VIX', 'COM', 'CUP', 'DON'], ['DAS', 'PRA', 'BLI'], ['BLI', 'DON', 'DAS', 'COM'], ['PRA', 'VIX', 'DAN', 'DON', 'RUD', 'DAS'], ['CUP', 'BLI', 'DAS', 'DAN', 'PRA', 'VIX'], ['VIX', 'COM', 'BLI'], ['RUD', 'PRA', 'DON', 'BLI', 'COM', 'DAN', 'VIX', 'CUP'], ['DON', 'COM', 'CUP', 'BLI', 'PRA', 'DAN', 'RUD', 'DAS'], ['RUD', 'COM', 'PRA', 'DAN'], ['CUP', 'DAN', 'VIX'], ['BLI', 'PRA', 'RUD', 'COM'], ['DON', 'DAN', 'PRA', 'COM', 'BLI', 'DAS', 'CUP', 'VIX', 'RUD'], ['DAS', 'DAN', 'COM', 'VIX', 'BLI', 'CUP', 'PRA'], ['RUD', 'BLI', 'DAS', 'VIX', 'CUP', 'COM', 'PRA'], ['DON', 'PRA', 'BLI', 'RUD', 'VIX', 'DAS', 'DAN', 'COM', 'CUP'], ['DAN', 'COM', 'DAS', 'DON'], ['DAN', 'DON', 'VIX', 'BLI', 'COM', 'DAS'], ['DAS', 'DAN', 'VIX', 'BLI', 'RUD', 'PRA', 'CUP', 'DON'], ['DAS', 'BLI', 'DAN', 'CUP', 'RUD', 'DON', 'COM', 'PRA', 'VIX'], ['CUP', 'BLI', 'RUD', 'VIX', 'DAS', 'PRA'], ['VIX', 'PRA', 'DON', 'DAS', 'CUP', 'DAN', 'COM', 'BLI', 'RUD'], ['PRA', 'DON', 'BLI', 'RUD', 'CUP', 'DAN', 'DAS', 'VIX'], ['DON', 'DAN', 'DAS', 'CUP', 'VIX', 'RUD', 'BLI'], ['COM', 'BLI', 'DON', 'CUP', 'DAS', 'PRA', 'RUD', 'VIX', 'DAN'], ['DON', 'PRA', 'DAS', 'RUD'], ['DON', 'COM', 'DAN', 'RUD', 'PRA'], ['RUD', 'DON', 'DAN', 'BLI', 'CUP', 'DAS', 'VIX'], ['DAS', 'DAN', 'CUP', 'DON', 'BLI', 'PRA', 'RUD', 'VIX', 'COM'], ['RUD', 'DAN', 'DON', 'PRA', 'DAS', 'BLI', 'CUP', 'VIX', 'COM'], ['DAS', 'DON', 'CUP', 'COM', 'VIX', 'BLI', 'DAN'], ['DON', 'DAN', 'BLI', 'PRA', 'VIX'], ['DON', 'DAN', 'PRA', 'RUD', 'CUP', 'VIX', 'DAS', 'COM'], ['DAS', 'DAN', 'BLI'], ['DAS', 'VIX', 'CUP', 'DON', 'COM', 'PRA', 'RUD'], ['DAN', 'PRA', 'DAS', 'DON', 'BLI'], ['RUD', 'DAN', 'PRA', 'BLI', 'CUP', 'VIX', 'DON', 'COM'], ['DAN', 'COM', 'VIX', 'RUD', 'DON', 'CUP', 'PRA', 'BLI'], ['DAN', 'RUD', 'VIX'], ['RUD', 'DAS', 'VIX', 'COM', 'CUP'], ['BLI', 'RUD', 'PRA', 'CUP', 'DON', 'COM'], ['COM', 'DON', 'CUP', 'VIX', 'DAS', 'RUD', 'PRA', 'BLI', 'DAN'], ['VIX', 'DAS', 'PRA', 'RUD', 'CUP'], ['PRA', 'VIX', 'CUP', 'DON', 'COM', 'BLI', 'RUD'], ['DAS', 'COM', 'BLI', 'CUP', 'DON', 'RUD', 'VIX', 'DAN'], ['BLI', 'DON', 'RUD'], ['DON', 'DAN', 'CUP', 'RUD']]