Fivethirtyeight dwarves problem

dwarves.py

permutations = []
def next_step(permutation, dwarf):
    if dwarf == 7:
        permutations.append(tuple(permutation))
        return
    
    if permutation[dwarf] == -1:
        permutation[dwarf] = dwarf
        next_step(permutation, dwarf + 1)
    else:
        for i in range(len(permutation)):
            if permutation[i] == -1:
                pl = list(permutation)
                pl[i] = dwarf
                next_step(pl, dwarf + 1)


starting = [
    [-1, 0, -1, -1, -1, -1, -1],
    [-1, -1, 0, -1, -1, -1, -1],
    [-1, -1, -1, 0, -1, -1, -1],
    [-1, -1, -1, -1, 0, -1, -1],
    [-1, -1, -1, -1, -1, 0, -1],
    [-1, -1, -1, -1, -1, -1, 0],
]
for s in starting:
    next_step(s, 1)

wellplaced_eldest = 0
misplaced_dwarves = 0
wellplaced_dwarves = 0
for p in permutations:
    if p[-1] == 6:
        wellplaced_eldest += 1
    for dwarf, place in enumerate(p):
        if dwarf == place:
            wellplaced_dwarves += 1
        else:
            misplaced_dwarves += 1


print len(permutations) #63
print wellplaced_eldest #31

print wellplaced_dwarves #186
print misplaced_dwarves #255

"""
All possible permutations
(1, 0, 2, 3, 4, 5, 6)
(2, 0, 1, 3, 4, 5, 6)
(2, 1, 0, 3, 4, 5, 6)
(3, 0, 1, 2, 4, 5, 6)
(3, 0, 2, 1, 4, 5, 6)
(3, 1, 0, 2, 4, 5, 6)
(3, 1, 2, 0, 4, 5, 6)
(4, 0, 1, 2, 3, 5, 6)
(4, 0, 1, 3, 2, 5, 6)
(4, 0, 2, 1, 3, 5, 6)
(4, 0, 2, 3, 1, 5, 6)
(4, 1, 0, 2, 3, 5, 6)
(4, 1, 0, 3, 2, 5, 6)
(4, 1, 2, 0, 3, 5, 6)
(4, 1, 2, 3, 0, 5, 6)
(5, 0, 1, 2, 3, 4, 6)
(5, 0, 1, 2, 4, 3, 6)
(5, 0, 1, 3, 2, 4, 6)
(5, 0, 1, 3, 4, 2, 6)
(5, 0, 2, 1, 3, 4, 6)
(5, 0, 2, 1, 4, 3, 6)
(5, 0, 2, 3, 1, 4, 6)
(5, 0, 2, 3, 4, 1, 6)
(5, 1, 0, 2, 3, 4, 6)
(5, 1, 0, 2, 4, 3, 6)
(5, 1, 0, 3, 2, 4, 6)
(5, 1, 0, 3, 4, 2, 6)
(5, 1, 2, 0, 3, 4, 6)
(5, 1, 2, 0, 4, 3, 6)
(5, 1, 2, 3, 0, 4, 6)
(5, 1, 2, 3, 4, 0, 6)
(6, 0, 1, 2, 3, 4, 5)
(6, 0, 1, 2, 3, 5, 4)
(6, 0, 1, 2, 4, 3, 5)
(6, 0, 1, 2, 4, 5, 3)
(6, 0, 1, 3, 2, 4, 5)
(6, 0, 1, 3, 2, 5, 4)
(6, 0, 1, 3, 4, 2, 5)
(6, 0, 1, 3, 4, 5, 2)
(6, 0, 2, 1, 3, 4, 5)
(6, 0, 2, 1, 3, 5, 4)
(6, 0, 2, 1, 4, 3, 5)
(6, 0, 2, 1, 4, 5, 3)
(6, 0, 2, 3, 1, 4, 5)
(6, 0, 2, 3, 1, 5, 4)
(6, 0, 2, 3, 4, 1, 5)
(6, 0, 2, 3, 4, 5, 1)
(6, 1, 0, 2, 3, 4, 5)
(6, 1, 0, 2, 3, 5, 4)
(6, 1, 0, 2, 4, 3, 5)
(6, 1, 0, 2, 4, 5, 3)
(6, 1, 0, 3, 2, 4, 5)
(6, 1, 0, 3, 2, 5, 4)
(6, 1, 0, 3, 4, 2, 5)
(6, 1, 0, 3, 4, 5, 2)
(6, 1, 2, 0, 3, 4, 5)
(6, 1, 2, 0, 3, 5, 4)
(6, 1, 2, 0, 4, 3, 5)
(6, 1, 2, 0, 4, 5, 3)
(6, 1, 2, 3, 0, 4, 5)
(6, 1, 2, 3, 0, 5, 4)
(6, 1, 2, 3, 4, 0, 5)
(6, 1, 2, 3, 4, 5, 0)
"""