Connected integer lattice points symmetric about the axes

draw.py

from enumerate import visit_up_to_n
import matplotlib.pyplot as plt
import math

def draw( n ):
    figures = []
    
    def visitor( collection, cost ):
        if cost == n:
            figures.append( collection )

    visit_up_to_n( n, visitor )

    num = len( figures )
    height = math.isqrt( num )
    width = ( num + height - 1) // height

    sharedAxis = None

    # Allocate 200 pixels for each item?
    my_dpi = 200
    fig = plt.figure( figsize=(width,height), dpi=my_dpi )
    for (i,f) in enumerate(figures):
        ax = plt.subplot( height, width, i + 1, sharex = sharedAxis, sharey = sharedAxis )
        if sharedAxis is None:
            sharedAxis = ax
            
        points = set()
        for (x,y) in f:
            points.add( (x,y) )
            points.add( (-x,y) )
            points.add( (x,-y) )
            points.add( (-x,-y) )

        # Using markersize gives unpredictable results because its units
        # are in points.  We'll instead draw a small square for every point.
        margin = 0.45
        for (x,y) in points:
            ax.fill( [x - margin, x + margin, x + margin, x - margin ],
                     [y - margin, y - margin, y + margin, y + margin ],
                     'blue' )
        ax.set_xticks( [0] )
        ax.set_xticklabels( [] )
        ax.set_yticks( [0] )
        ax.set_yticklabels( [] )
        ax.set_aspect( 'equal' )


    fig.tight_layout(pad = 0.01)
    fig.savefig( f"all-{n}.png", dpi=my_dpi )

import sys

if __name__ == "__main__":
    if len( sys.argv ) > 1:
        n = int( sys.argv[1] )
        draw( n )
    else:
        for n in range( 4, 15 ):
            print( "Drawing", n )
            draw( n )

enumerate.py

# How many sets of integer lattice points are there with N elements
# that are symmetric about the x and y axes, which form a single connected
# unit (including diagonal connections.)
#
# A connected set must be connected in the first quadrant as well, so we can
# generate sets there and mirror them-- or simply count how many points
# there would be in the complete verison:
# (0,0) has 1 image
# (x,0) has 2 images
# (0,y) has 2 images
# (x,y) has 4 images
#
# The quadrant can only generate a connected unit after the mirroring
# if there is a point on the x axis and on the y-axis (which can be
# simultaneously satisfied by picking the origin.)
#
# In order to generate only connected units, we can pick points one at a time
# adjacent to points already in the set.  We do this using a total ordering
# of the lattice so that once we decide not to visit a point we don't later
# add it, introducing duplicate derivations of the same set. However,
# we still have to verify that the previous condition is met -- it would
# be nice to have a heuristic to ensure we didn't waste a lot of time
# searching configurations that couldn't possibly satisfy it.
#
# If there is A points on the origin, B points on the axes, and
# C points elsewhere in the quadrant, then applying the mirror symmetries
# gives N = A + 2B + 4C points.
#
# Thus if we want to search up to a given maximum, we can keep a running
# total and terminate whenever the configuration would exceed N.
# Every intermediate state which satisfies the connectivity condition can
# counted.
#
# We'll just use the tuples for our total order; I don't see any benefit
# to walking the diagonals?
#
#  ...
#  0,7
#  0,6
#  0,5
#  0,4
#  0,3  1,3
#  0,2  1,2  2,2
#  0,1  1,1  2,1  3,1
#  0,0  1,0  2,0  3,0  4,0
# 
# We can terminate the search whenever the first point we
# would pick in the first column could not reach the X axis in
# a connected group of less than N total cost. The cost of getting from
# (0,Y) back down to 0 is necessarily at least 4(Y-1) + 2
# N = 2 + 4(Y-1) + 2 = 4Y means the max is N / 4

def expand_frontier( coord, frontier, visited ):
    (x,y) = coord
    new_set = set()
    for dx in [-1, 0, 1]:
        for dy in ([-1,1] if dx == 0 else [-1, 0, 1]):
            nx = x + dx
            ny = y + dy
            if nx >= 0 and ny >=0 and (nx,ny) not in visited:
                new_set.add( (nx,ny) )
    return frontier.union( new_set )        

def cost( coord ):
    (x,y) = coord
    if x == 0:
        if y == 0:
            return 1
        else:
            return 2
    else:
        if y == 0:
            return 2
        else:
            return 4
        
# Call visit with the calculated cost and set of points
def visit_up_to_n( max_n, visit ):
    # Recursively use or discard the next point
    # frontier = all connected points not yet visited
    # visited = all points already discarded or included
    # collection = working set of points
    # collection_cost = total number of points after mirroring
    # collection_valid = the collection includes points on both axes
    def recurse( point, frontier, visited, collection, collection_cost,
                 collection_valid ):
        #print( f"{point=} {frontier=} {visited=} {collection=} cost={collection_cost} valid={collection_valid}")
        # Never consider this point again
        next_visit = visited.union( [point] )
        
        # Case 1: include this point
        next_cost = collection_cost + cost( point )
        next_frontier = expand_frontier( point, frontier, visited )
        next_collection = collection.union( [point] )
        # Valid if we have reached the x axis (we start on the y axis)
        next_valid = collection_valid or ( point[1] == 0 )
        if next_cost <= max_n and next_valid:
            visit( next_collection, next_cost )
            
        # Recursively visit the expanded collection, starting with
        # the minimum element in the expanded collection, if we haven't
        # definitely hit max_n and so could add another point.
        # (Adding the origin is not possible here, so the minimum cost
        # left in the frontier is 2.)
        # TODO: make this a heap instead?
        if next_cost + 2 <= max_n and len( next_frontier ) > 0:
            next_point = min( next_frontier )
            next_frontier.remove( next_point )
            recurse( next_point, next_frontier, next_visit, next_collection, next_cost, next_valid )

        # Case 2: exclude this point, frontier size decreases
        if len( frontier ) > 0:
            next_point = min( frontier )
            next_frontier = frontier.symmetric_difference( [next_point] )
            recurse( next_point, next_frontier, next_visit, collection, collection_cost, collection_valid )


    # Bootstrap by working our way up the Y axis, marking all previous
    # possible starting points as visited
    initial_visited = set()
    for y in range( 0, max_n // 4 + 1 ):
        initial_visited.add( (0,y) )
        initial_frontier = set()
        initial_collection = set()
        initial_valid = False
        initial_cost = 0
        
        recurse( (0,y), initial_frontier, initial_visited,
                 initial_collection, initial_cost, initial_valid )
            

def print_up_to( max_n ):
    def printer( collection, cost ):
        text = " ".join( str(x) for x in sorted( collection ) )        
        print( f"{cost} | {text}" ) 

    visit_up_to_n( max_n, printer )
    

def illustrate( collection ):
    max_x = max( x for (x,y) in collection )
    max_y = max( y for (x,y) in collection )
    rows = []
    for y in range( max_y, -1, -1 ):
        row = ""
        for x in range( 0, max_x + 1, 1 ):
            if (x,y) in collection:
                row += "X"
            else:
                row += "."
        rows.append( row )
    return "\n".join( rows )
    
def illustrate_up_to( max_n ):
    by_cost = [ [] for i in range( 0, max_n + 1 ) ]
    def visitor( collection, cost ):
        by_cost[cost].append( collection )

    visit_up_to_n( max_n, visitor )

    for n in range( 1, max_n + 1 ):
        print( f"### Cost {n}, total {len(by_cost[n])} ###" )
        for c in by_cost[n]:
            print( illustrate( c ) )
            print()
            
def count_up_to( max_n ):
    by_cost = [ 0 for i in range( 0, max_n + 1 ) ]
    def visitor( collection, cost ):
        by_cost[cost] += 1

    visit_up_to_n( max_n, visitor )

    for n in range( 1, max_n + 1 ):
        print( f"{n} | {by_cost[n]}" )