Counting pairs of nonintersecting or semi-intersection lattice paths

ant_paths.py

import cairo
import math
import itertools

def base_position( i, j ):
    return (i * 60 + 10, j * 50 + 10)

def drawGrid( ctx, i, j ):
    ctx.set_line_width( 1 )
    ctx.set_source_rgba( 0.0, 0.0, 0.0, 1.0 )
    x0, y0 = base_position( i, j )
    for y in range( 0, 4 ):
        for x in range( 0, 5 ):
            ctx.arc( x0 + x * 10, y0 + y * 10, 1, 0, 2 * math.pi )
            ctx.fill()

def drawGrayPath( ctx, i, j, path ):
    ctx.set_line_width( 3 )
    ctx.set_source_rgba( 0.0, 0.0, 0.0, 0.5 )
    drawPath( ctx, i, j, path )

def drawRedPath( ctx, i, j, path ):
    ctx.set_line_width( 3 )
    ctx.set_source_rgba( 1.0, 0.0, 0.0, 0.85 )
    drawPath( ctx, i, j, path )

def drawBluePath( ctx, i, j, path ):
    ctx.set_line_width( 3 )
    ctx.set_source_rgba( 0.0, 0.0, 1.0, 0.85 )
    drawPath( ctx, i, j, path )
    
def drawPath( ctx, i, j, path ):
    x, y = base_position( i, j )
    ctx.move_to( x, y )
    for n in range( 7 ):
        if n in path:
            y += 10
        else:
            x += 10
        ctx.line_to( x, y )
    ctx.stroke()

# pointwise intersection
def intersects( path1, path2 ):
    x1, y1 = 0, 0
    x2, y2 = 0, 0
    for n in range( 6 ):  # Skip last segment
        if n in path1:
            y1 += 1
        else:
            x1 += 1
            
        if n in path2:
            y2 += 1
        else:
            x2 += 1

        if x1 == x2 and y1 == y2:
            return True
        
    return False

# traverses the same interior edge
def intersects_middle_edge( path1, path2 ):
    x1, y1 = 0, 0
    x2, y2 = 0, 0
    edges1 = set()
    edges2 = set()
    for n in range( 6 ):  # Skip last segment
        if n in path1:
            edges1.add( ((x1,y1), (x1,y1+1)) )
            y1 += 1
        else:
            edges1.add( ((x1,y1), (x1+1,y1) ) )
            x1 += 1
            
        if n in path2:
            edges2.add( ((x2,y2), (x2,y2+1)) )
            y2 += 1
        else:
            edges2.add( ((x2,y2), (x2+1,y2) ) )
            x2 += 1

    bad_edges = set([
        ((1,1), (2,1)),
        ((2,1), (3,1)),
        
        ((1,2), (2,2)),
        ((2,2), (3,2)),
        
        ((1,1), (1,2)),
        ((2,1), (2,2)),        
        ((3,1), (3,2)),  
    ])

    #print( "edges for", path1, "=", sorted( edges1 ) )
    #print( "edges for", path2, "=", sorted( edges2) )
    return len( edges1.intersection( edges2 ).intersection( bad_edges ) ) > 0

# traverses any common edge
def intersects_edge( path1, path2 ):
    x1, y1 = 0, 0
    x2, y2 = 0, 0
    edges1 = set()
    edges2 = set()
    for n in range( 7 ):
        if n in path1:
            edges1.add( ((x1,y1), (x1,y1+1)) )
            y1 += 1
        else:
            edges1.add( ((x1,y1), (x1+1,y1) ) )
            x1 += 1
            
        if n in path2:
            edges2.add( ((x2,y2), (x2,y2+1)) )
            y2 += 1
        else:
            edges2.add( ((x2,y2), (x2+1,y2) ) )
            x2 += 1

    #print( "edges for", path1, "=", sorted( edges1 ) )
    #print( "edges for", path2, "=", sorted( edges2) )
    return len( edges1.intersection( edges2 ) ) > 0


    
w, h = base_position( 36, 36 )

paths = list( itertools.combinations( range( 7 ), 3 ) )

with cairo.SVGSurface( "lattice-paths.svg", w, h ) as surface:
    surface.set_document_unit( cairo.SVG_UNIT_PX )
    ctx = cairo.Context(surface)
    
    ctx.rectangle( 0, 0, w, h )
    ctx.set_source_rgba( 1.0, 1.0, 1.0, 1.0 )
    ctx.fill()
    
    for i in range( 35 ):
         drawGrid( ctx, i+1, 0 )
         drawGrayPath( ctx, i+1, 0, paths[i] )
 
    for j in range( 35 ):
         drawGrid( ctx, 0, j+1 )
         drawGrayPath( ctx, 0, j+1, paths[j] )

    count = 0
    for i in range( 35 ):
        for j in range( 35 ):
            if not intersects_edge( paths[i], paths[j] ):
                drawRedPath( ctx, i+1, j+1, paths[i] )
                drawBluePath( ctx, i+1, j+1, paths[j] )
                count += 1
    print( count, "pairs of paths")
            
    surface.finish()
    surface.flush()