Loop the loops - Medium

Computer Science Level 3

In the world of pencil puzzles, there are many puzzle types where you have to draw a loop on a lattice grid, including Country Road , Masyu , Pure Loop , Slalom , and Yajilin . In most of these puzzles (and all of the linked above), the loop visits some of the cells, passing through the cells' centers, and may not use a cell more than once (which also means no intersections, no touching itself, etc).

Formally, on a polyomino $P$ , a loop is a sequence of $n \ge 4$ squares $(a_1, a_2, a_3, \ldots, a_n)$ such that all squares $a_i$ are in $P$ , $a_i$ and $a_{i+1}$ share a side for all valid $i$ , $a_n$ and $a_1$ also share a side, and all squares in the loop are distinct. Loops are cyclic (it can start from any square in the loop) and don't have any orientation (reversing the loop doesn't matter), thus $(a_1, a_2, a_3, a_4), (a_2, a_3, a_4, a_1), (a_4, a_3, a_2, a_1)$ all describe the same loop.

Determine the number of loops on a $5 \times 5$ square.

Too difficult? Go back to the easy difficulty . Want a harder challenge? Try the hard difficulty .

The answer is 9349.

2 solutions

Ivan Koswara
Aug 28, 2015

It's difficult to apply the case by case basis on the easy version here, since there's no systematic approach. (The easy version uses the givens instead.) So how can we begin tackling this problem?

First, we have an interesting observation. Look at the grid points:

Each grid point is either inside the loop or outside the loop:

This already shows how we can tackle this with brute force: consider the $2^{16}$ possibilities (two for each grid point, all multiplied together) one by one, and verify if it makes a loop. The problem is, how do we verify whether a selection of points make a loop? Additionally, is it possible that two loops produce the same grid points that are "in"?

The second question, that each configuration can only possibly produce one loop, is easier to answer. Note that the loop always goes between the inside part and the outside part (this is Jordan curve theorem ). Thus between two grid points of different "parity" (one "in" and one "out"), the loop must go there, and between two grid points of equal "parity" (both "in" or both "out"), the loop cannot go there. The outside of the grid also has grid points that are "out", so this defines the loop completely.

The first part is more difficult. Let's see what characteristics that a loop has.

First, there must be a single loop. This means all the "in" grid points together form a single region. In other words, if we attempt to use flood fill from an "in" point, we must find all "in" points.

Second, it cannot self-intersect. This means no square can be used four times. A square used four times means that the four grid points around it are colored in a checkerboard fashion:

We can actually simplify this assumption, which will also take care of another possibility. If we use the first condition that the "in" points must be connected, we will have something of this sort:

In other words, one of the two "out" grid points will eventually be sealed off from the outside. This also applies to another case that we missed previously, but clearly isn't allowable either:

In other words, if we flood fill from an "out" point, we must get another "out" point.

In fact, the two above are enough. A coloring of the grid points forms a loop if flood filling from any "in" point finds all "in" points, and flood filling from any "out" point finds all "out" points (if we assume the border is all "out" as well). Now onto the coding part. It's simple enough:

import itertools

def size(G, x, y):
    q = [(x, y)]
    S = [[0] * len(G[0]) for _ in range(len(G))]
    ans = 0
    while q:
        i,j = q.pop()
        if S[i][j]: continue
        if G[i][j] != G[x][y]: continue
        S[i][j] = 1
        ans += 1
        if i > 0: q.append((i-1, j))
        if j > 0: q.append((i, j-1))
        if i < len(G)-1: q.append((i+1, j))
        if j < len(G[0])-1: q.append((i, j+1))
    return ans

def check(G):
    r, c = len(G), len(G[0])
    x, y = None, None
    for i in range(r):
        if x != None: break
        for j in range(c):
            if G[i][j] == 1:
                x, y = i, j
                break
    if x == None: return False
    Gnew = [[0]*(c+2)] + [[0]+row+[0] for row in G] + [[0]*(c+2)]
    return (size(Gnew, 0, 0) + size(Gnew, x+1, y+1) == (r+2)*(c+2))

def solve(r, c):
    ct = 0
    for k in itertools.product([0,1], repeat=r*c):
        G = [list(k[i*c:(i+1)*c]) for i in range(r)]
        if check(G): ct += 1
    return ct

The function size(G, x, y) takes a grid G and a coordinate (x, y) , and uses flood fill to determine the size of the area containing it. The function check(G) begins by taking a grid G , checking that it has an "in" point (a grid of "out" points is useless; there's no loop), and padding the borders with out points. It then finds the area with an "out" point, finds the area with an "in" point, and adds the two together, if it's the entire size of the grid, then this is a valid grid, otherwise it's invalid. The function solve(r, c) takes two integers r, c and returns the number of valid grids for $r \times c$ point grid; that is, $(r+1) \times (c+1)$ square grid.

For our purpose, we need to find the number of solutions of $5 \times 5$ square grid, so we compute solve(4, 4) . The returned answer is $\boxed{9349}$ .

Moderator note:

What a beautiful solution. Your loop constructions are reminiscent of a very clever construction one can make to calculate the phase transition in a 2d Ising model called the Peierls argument.

Laurent Shorts
Apr 25, 2016

In Python. 1 second runtime.

HEIGHT = WIDTH = 5

# creates a grid where all cells before (sx,sy) are unavailable
def createGrid(sx, sy):
        global HEIGHT, WIDTH
        grid = []
        for line in xrange(sy):
                grid += [ WIDTH * [False] ]
        grid += [ sx * [False] + (WIDTH - sx) * [True] ]
        for line in xrange(sy + 1, HEIGHT):
                grid += [ WIDTH * [True] ]
        return grid

DIRECTIONS = [(1,0), (0,1), (-1,0), (0,-1)]
def getNbLoops(sx, sy, px, py, grid, directions = None):
        global DIRECTIONS
        # directions can be given at start to avoid coming directly back to start
        if directions == None:
                directions = DIRECTIONS

        # copy grid before making changes, otherwise it changes everywhere
        grid = [ t[:] for t in grid ]

        grid[py][px] = False
        nb = 0
        for (dx,dy) in directions:
                nx = px + dx
                ny = py + dy
                # coming back to start?
                if nx == sx and ny == sy:
                        nb += 1
                else:
                        if 0 <= nx and nx < WIDTH and 0 <= ny and ny < HEIGHT:
                                if grid[ny][nx]:
                                        nb += getNbLoops(sx, sy, nx, ny, grid)
        return nb

# count nb of loops for each possible start
nb = 0
for start in xrange(0, HEIGHT * WIDTH - WIDTH - 1):
        sx = start % WIDTH
        sy = start / WIDTH
        grid = createGrid(sx, sy)
        # Starting on the right, because up and left
        # are no more available, and down is the other way around on the loop
        if sx < WIDTH - 1:
                nb += getNbLoops(sx, sy, sx+1, sy, grid, [(1,0), (0,1)])

print nb

Loop the loops - Medium

Too difficult? Go back to the easy difficulty . Want a harder challenge? Try the hard difficulty .

The answer is 9349.

2 solutions

Moderator note:

0 pending reports