# -*- Mode: Python -*-

# N people meet for the first time in a room.
# If we want everybody to shake hands with everyone else, then we'll
#
#        (N-1)*N
# need   ------- handshakes in total.
#           2
#
# ok, now think like an algorithms geek.  Tell the N people how to
#   do it.  The simplest solution is to pick a guy, have him shake
#   everyone's hand, and sit down.  But that's pretty inefficient.  O(N^2).
# Can we do better? Sure!
# What's the best we can possibly do?
# Well, we can't shake more than N/2 times in one step.  That works
#  out to a best possible solution of N-1 steps, with no wasted shakes. O(N).

# I played around with this for a while, but the solution is not very
#  obvious.  It seemed to me that if you put people into two rings,
#  with one rotating, that some combination of swap/rotate could solve
#  it.  So I wrote this code to search that space.  There are a lot of
#  solutions, but no super-obvious simple pattern that leaps out.
#  However, there's one that I think is simple enough to explain to a
#  crowd, look at the bottom of this file for my choice.

import sys
from pprint import pprint as pp

def gen_perms (n):
    result = []
    for i in range (n):
        for j in range (i):
            if i < j:
                result.append ((i,j))
            else:
                result.append ((j,i))
    return result

# ok, now treat it like a ring puzzle
#   see if we can always find a solution

#    3
#    0
#  2   1
# 5     4          

def rotations (p, name):
    # there are two rotations, either forward or backward
    # 012345 => 012453, 012534
    # so the second half rotates
    perm0 = p[:]
    perm1 = p[:]
    n = len(p)/2
    for i in range (n-1):
        perm0[i+n]   = p[i+n+1]
        perm1[i+n+1] = p[i+n]
    perm0[-1] = p[n]
    perm1[n]  = p[-1]
    return [(name+'l',perm0), (name+'r', perm1)]

def gen_moves (p):
    moves = rotations (p, '')
    # now try a swap then turn
    n = len(p)/2
    for i in range (n):
        perm = p[:]
        perm[i], perm[i+n] = p[i+n], p[i]
        moves.extend (rotations (perm, str(i)))

    return moves

def gen_pairs (p):
    n = len(p) / 2
    r = set()
    for a, b in [(p[i], p[i+n]) for i in range (n)]:
        if a < b:
            r.add ((a,b))
        else:
            r.add ((b,a))
    return r

solutions = []

def search (p, solution, left, d=0):
    # algorithm only works for even numbers
    assert (n%2 == 0)
    moves = gen_moves (p)
    for op, move in moves:
        # a move is only valid if
        # 1) it creates pairs we have not yet seen
        pairs = gen_pairs (move)
        for pair in pairs:
            if pair not in left:
                break
        else:
            # it's a valid move.
            # are we done?
            if len(left) == len (pairs):
                solutions.append (solution + [(op, move)])
                #solutions.append (solution + [op])
            else:
                search (move, solution + [(op, move)], left - pairs, d+1)
                #search (move, solution + [op], left - pairs, d+1)

def go (n):
    global solutions
    p = range (n)
    # remove the initial pairs...
    left = set (gen_perms (n))
    left = left - gen_pairs (p)
    search (p, [], left, 0)
    for i in range (len (solutions)):
        solution = solutions[i]
        print '%2d:' % (i,),
        for o, s in solution:
            print o,
        print

def animate (solution):
    W = sys.stdout.write
    p = range (n)
    solution = [ ('start', p)] + solution
    for i in range (len (solution)):
        move, state = solution[i]
        rp = [str(x) for x in state]
        W ('%6s:  %s\n' % (move, ' '.join (rp[:n/2])))
        W ('%6s   %s\n' % (''  , ' '.join (rp[n/2:])))

# SPOILER: a relatively simple solution.
#   arrange the people into two rings.  at each step, everyone in the outer ring
#   shakes with the person next to them on the inner ring.
#   1a) shake.        
#   1b) swap the inner/outer persons at position 0.
#   1c) rotate the outer ring clockwise.
#   2) repeat 1 a-c (i.e., swap/rotate position 0 twice)
#   3) repeat steps 1-2, but swapping at position 1,2,3,4,...
#   4) after you've swapped each position twice, you're done!        

# It's probably more practical to line the people up in two rows, just
#   remember that when a guy pops off the end upon rotation to put him
#   on the other end.        

# my chosen solution always shows up as solution 3N+1
        
if __name__ == '__main__':
    if len(sys.argv) > 1:
        n = int (sys.argv[1])
    else:
        n = 6
    go (n)
    print 'my chosen solution:'
    animate (solutions[3*n+1])