#!/usr/bin/python -i

########################################################################
#
#  Giant steps, depth, and bridge numbers
#
#     by Sangbum Cho and Darryl McCullough
#
#  Version of May 3, 2009
#
#  Contact:  dmccullough@math.ou.edu
#
#  This is a Python 2.3 script that implements algorithms from the papers
#
#      "Constructing knots tunnels using giant steps" and
#      "Tunnel leveling, depth, and bridge numbers."
#
########################################################################
#
#  All the major functions accept either binary or step sequence inputs.
#
#  You can convert between the binary invariants string and the
#  step sequence of a principal path using these utilities:
#
#  Depth> steps2binary( 'DRRRDRDLLLDLDRR' )
#  '0011100011100'
#
#  Depth> binary2steps( '0011100011100' )
#  'DRRRDRDLLLDLDRR'
#
#  Depth> binary2steps( '0011100011100' ).lower()
#  'drrrdrdllldldrr
#
#  Like all functions accepting step sequences, binary2steps accepts
#  lower-case inputs.
#
########################################################################
#  
#  The function  gst  analyzes the constructions of a tunnel using
#  giant steps.
#  
#  For example, using the example from "The depth of a knot tunnel",
#  
#  Depth> gst( '0011100011100' )              
#  4
#
#  If you want more details of the calculation, use
#  
#  Depth> gst(  '0011100011100', verbose = True )
#  
#  The block configurations are R1, L2, L1, R2, and
#  
#     M_5 * ... * M_2 = [ [ 2, 2 ], [ 2, 2 ] ].
#  
#  This tunnel has 4 minimal giant step constructions
#  
#  Depth> gst(  '00111000111001', verbose = True )
#  
#  The block configurations are R1, L2, L1, R2, and
#  
#     M_5 * ... * M_2 = [ [ 2, 2 ], [ 2, 2 ] ].
#  
#  The final block is a nabla.
#  
#  This tunnel has 8 minimal giant step constructions.
#  
########################################################################
#  
#  The function  fibonacci  calculate the fibonacci number  F_\tau( a, b ).
#  For our standard example, we find
#  
#  Depth> fibonacci( '0011100011100', 2, 2, verbose=True )
#  
#  F_\tau( 2, 2 ) = 182.
#  
#  The iteration sequence is:
#  
#      2, 2, 4, 6, 10, 14, 18, 22, 40, 62, 102, 142, 182
#
#  The iteration sequence tells the intermediate values.
#
#  Depth> fibonacci( '0011100011100', 4, 5, verbose=True )
#
#  F_\tau( 4, 5 ) = 414.
#
#  The iteration sequence is:
#
#      4, 5, 9, 14, 23, 32, 41, 50, 91, 141, 232, 323, 414
#
#  The function  lowerBound  calls fibonacci with the minimum
#  possible starting values 2 and 2, and  upperBound  calls it
#  with the maximum possible starting values, based on the number
#  of depth 1 cablings in the cabling sequence.
#
#  Depth> lowerBound( '0011100011100' )
#  The minimum bridge number is 182.
#
#  Depth> upperBound( '0011100011100', verbose = True )
#
#  The maximum bridge number is 414.
#
#  The iteration sequence is:
#
#      4, 5, 9, 14, 23, 32, 41, 50, 91, 141, 232, 323, 414
#  
#  
#  fibonacci  warns of impossible inputs. For example:
#
#  Depth> fibonacci( '0011100011100', 3, 5, verbose=True )
#
#  Warning: The starting bridge numbers should satisfy 
#      2 <= c2 <= c3 <= c3 + 1.
#
#  F_\tau( 3, 5 ) = 373.
#
#  The iteration sequence is:
#
#      3, 5, 8, 13, 21, 29, 37, 45, 82, 127, 209, 291, 373
#
#  
#  To suppress warnings, set warnings = False:
#  
#  Depth> fibonacci( '0011100011100', 3, 5, verbose=True, warnings = False )
#
#  F_\tau( 3, 5 ) = 373
#
#  The iteration sequence is:
#
#      3, 5, 8, 13, 21, 29, 37, 45, 82, 127, 209, 291, 373
#
#
#  Finally, the function  bridgeSet  gives the set of possible
#  bridge numbers for the given principal path. It is not yet known
#  that these all occur, but it appears extremely likely that they do.
#
#  Depth> bridgeSet( '0011100011100' )
#
#  [182, 232, 273, 323, 364, 414]
#
########################################################################

import re, sys
sys.ps1 = 'Depth> '
sys.ps2 = '   ... '

class Matrix:
    def __init__( self, a=0, b=0, c=0, d=0 ):
        self.a, self.b, self.c, self.d =  a, b, c, d

    def __str__(self):
        return "[ [ %d, %d ], [ %d, %d ] ]" % (self.a, self.b, self.c, self.d)

    def __mul__(self,n):
        # defines self * n
        return Matrix( self.a * n.a + self.b * n.c,
                       self.a * n.b + self.b * n.d,
                       self.c * n.a + self.d * n.c,
                       self.c * n.b + self.d * n.d )

# regular expressions 

binary = re.compile( '(0|1)*' )
startingSteps = re.compile( 'DR' )
legalSteps = re.compile( 'LL|LD|DR|DL|RD|RR' )

def isBinary( s ):
    """Check whether a string consists of 0's and 1's."""
    if binary.match( s ).end() == len( s ):
        return True
    return False

def isSteps( s ):
    """Check whether a string consists of L's, D's, and R's and
    is a legal step sequence. Accepts small-letter strings."""
    s = s.upper()
    if startingSteps.match( s ) == None:
        return False
    for k in range(1,len(s)-1):
        if legalSteps.match( s[k:k+2] ) == None:
            return False
    return True

def binary2steps( inputString ):
    """Convert binary strings to step sequences."""
    if not isBinary( inputString ):
        print 'Error: illegal binary invariants string.'
        return

    reverseMode = { 'L' : 'R',
                    'R' : 'L' }
 
    returnString = 'DR'
    for s in inputString:
        if s == '0':
            if returnString[-1] == 'L':
                returnString += 'L'
            elif returnString[-1] == 'D':
                returnString += reverseMode[ returnString[-2] ]
            elif returnString[-1] == 'R':
                returnString += 'R'
        elif s == '1':
            if returnString[-1] == 'D':
                returnString += returnString[-2]
            else:
                returnString += 'D'

    return returnString

def steps2binary( inputString ):
    """Convert step sequences to binary strings."""
    if not isSteps( inputString ):
        print 'Error: illegal step sequence.'
        return

    returnString = ''
    previousStep = 'R'    
    secondPreviousStep = 'D'
    for step in inputString[2:]:
        if step == previousStep:
            returnString += '0'
        elif step == 'D':
            returnString += '1'
        elif step == secondPreviousStep:
            returnString += '1'
        else:
            returnString += '0'
        secondPreviousStep = previousStep
        previousStep = step

    return returnString

def numDepthOneCablings( inputString ):
    """Find the number of semisimple cablings of a principal path.
    Assumes that the tunnel is not semisimple, so returns 2 for
    empty string input."""
    if isSteps( inputString ):
        binary = steps2binary( inputString )
    elif isBinary( inputString ):
        binary = inputString
    else:
        print 'Error: illegal input string.'
        return None
    
    initialZeros = re.compile( '^0+' )
    initialZeroMatch = initialZeros.match( binary )

    if initialZeroMatch:
        return initialZeroMatch.end() + 2
    else:
        return 2

def depth( inputString ):
    if isBinary( inputString ):
        steps = binary2steps( inputString )
    elif isSteps( inputString ):
        steps = inputString.upper()
    else:
        print 'Error: illegal input string.'
        return None
    
    return len( [ x for x in steps if x == 'D' ] )

def findConfiguration( aBlock ):
    """An auxiliary function for  gst ."""
    if aBlock[1] == 'L':
        if len( aBlock ) == 2:
            return 'L1'
        else:
            return 'L2'
    if aBlock[1] == 'R':
        if len( aBlock ) == 2:
            return 'R1'
        else:
            return 'R2'

def gst( inputString, verbose=False ):
    if isBinary( inputString ):
        steps = binary2steps( inputString )
    elif isSteps( inputString ):
        steps = inputString.upper()
    else:
        print 'Error: illegal input string.'
        return None

    # Make dictionary to look up matrices according to block type.
    configurationMatrix = { 'R1' : Matrix(1, 1, 0, 1),
                            'L1' : Matrix(1, 0, 1, 1),
                            'R2' : Matrix(0, 1, 0, 1),
                            'L2' : Matrix(1, 0, 1, 0) }

    corridorBlocks = re.compile( 'DR+|DL+|D$' )
    blocks = corridorBlocks.findall( steps )

    # Check for depth 1 case.
    if len( blocks ) == 1:
        print '\nThe tunnel has depth 1, so has a unique', \
              'minimal giant step construction.\n'
        return
    
    matrixList = []
    configurations = []

    # always ignore the first block
    blocks = blocks[1:]
    
    # ignore the final block for now
    for aBlock in blocks[:-1]:
        conf = findConfiguration( aBlock )
        configurations.append ( conf )
        matrixList.append( configurationMatrix[ conf ] )

    if len( blocks[-1] ) > 1:
        # the tunnel does not form a nabla with \nabla( n )
        conf = findConfiguration( blocks[-1] )
        configurations.append ( conf )
        matrixList.append( configurationMatrix[ conf ] )

    matrixList.reverse()
    m = reduce( (lambda x, y: x * y), matrixList, Matrix(1, 0, 0, 1) )
    matrixList.reverse()

    if verbose == True and configurations != []:
        matrixPrintout = '\n   '.join( map( str, matrixList ) )
        if len( configurations ) == 1:
            print '\nThe block configuration is %s, and\n' % configurations[0]
            print '   M_2 = %s.' % matrixPrintout
        else:
            print '\nThe block configurations are %s, and\n' % \
              ', '.join( configurations )
            print '   M_%s * ... * M_2 = %s.' % ( 1+len(matrixList), str( m ) )
 
    # calculate the number of paths
    if len( blocks[-1] ) == 1:
        # bottom triangle of corridor is a nabla
        num = m.a + m.b + m.c + m.d
        if verbose == True:
            print '\nThe final block is a nabla.'
    else:
        if conf == 'L1' or conf == 'L2':
            num = m.a + m.b
        else:
            num = m.c + m.d

    if verbose == True:
        if num is 1:
            print '\nThis tunnel has 1 minimal giant step construction.\n'
        else:
            print '\nThis tunnel has %d minimal giant step constructions.\n' % num
    else:
        return num

def fibonacci( inputString, c2=2 , c3=2, verbose = False, warnings = True, \
               lb = False, ub = False ):
    if isSteps( inputString ):
        binary = steps2binary( inputString )
    elif isBinary( inputString ):
        binary = inputString
    else:
        print 'Error: illegal input string.'
        return None

    numDepthOnes = numDepthOneCablings( binary )

    if lb == True:
        c2, c3 = 2, 2
    elif ub == True:
        c2, c3 = numDepthOnes, numDepthOnes + 1

    # If warnings are in force, check for impossible inputs.
    if warnings == True:
        if c2 < 2 or 1 < c3 - c2 or c2 > c3:
            print '\nWarning: The starting bridge numbers should satisfy', \
             '\n    2 <= c2 <= c3 <= c3 + 1.'
        elif c2 > numDepthOnes or c3 > numDepthOnes + 1:
            print """\nWarning: The given starting bridge numbers are impossible.
                The cabling sequence contains %d depth 1 tunnels,
                so they should satisfy c2 <= %d and c3 <= %d.""" % \
                (numDepthOnes, numDepthOnes, numDepthOnes + 1)

    # Handle the semisimple case.
    input = binary.lstrip('0')
    if input == '':
        # The tunnel is semisimple.
        print 'This tunnel has depth 1. Its bridge number satisfies', \
              '2 <= b <= %d.' % numDepthOneCablings + 2
        return
    
    # The tunnel is regular.
    # Iteratively find the previous, pivot, and current minimum bridge numbers
    pivotBridgeNum = c2
    previousBridgeNum = c2
    currentBridgeNum = c3
    minList = [c2, c3]
    for step in input:
        if step == '0':
            previousBridgeNum = currentBridgeNum
        elif step == '1':
            pivotBridgeNum = previousBridgeNum
            previousBridgeNum = currentBridgeNum
        currentBridgeNum += pivotBridgeNum
        minList.append( currentBridgeNum )

    if verbose == True:
        if lb == True:
            print '\nThe lower bound for br(K_\\tau) is %d.' % currentBridgeNum
        elif ub == True:
            print '\nThe upper bound for br(K_\\tau) is %d.' % currentBridgeNum
        else:
            print '\nF_\\tau( %d, %d ) = %d.' % ( c2, c3, currentBridgeNum )
        print '\nThe iteration sequence is:'
        print '\n    %s\n' % ', '.join( map( str, minList) )
    else:
        return currentBridgeNum

def lowerBound( s ):
    fibonacci( s, verbose = True, lb = True ) 

def upperBound( s ):
    m = numDepthOneCablings( s )
    fibonacci( s, verbose = True, ub = True )

def bridgeSet( inputString ):
    if isSteps( inputString ):
        binary = steps2binary( inputString )
    elif isBinary( inputString ):
        binary = inputString
    else:
        print 'Error: illegal input string.'
        return None

    bridgeNumbers = []

    numDepthOnes = numDepthOneCablings( binary )
    for k in range(2, numDepthOnes + 1):
        bridgeNumbers.append( fibonacci( binary, k, k, verbose = False ) )
        bridgeNumbers.append( fibonacci( binary, k, k + 1, verbose = False ) )

    return bridgeNumbers