Generalized color balls in a 4x4 grid

Question

This is a generalization of the Colored balls in a 4x4 grid puzzle that was proposed by Darrel Hoffman.

Colored balls from 4 different colors are placed in a 4x4 grid. There is at least one ball from each color. A move consists of swapping two adjacent (horizontally or vertically) balls. The value of the grid is the least number of moves required to form 4 connected components*, one for each color. Which grid has the highest value?

*Here a connected component is a collection of balls of the same color, such that there is a path of horizontal or vertical steps from any ball to any other ball.

Answer 1

With the normalization that the first color occurring (starting from top left) should be R and the second G there are $358,108,246$ positions. This is brute-forceable. I wrote a program that first finds all $342,074$ end positions, then those $914,980$ one step away from an end, then those $3,747,392$ two steps away and so on. Note that I did not enforce that all four colors must be present. This ended after

$13$ steps.

Shown below are $4$ of the

$28$

answers each with a random shortest solution (Solutions are non-unique).

Small letters indicate the pair to be swapped in the next move. More than two small letters indicate a remapping of colors which is sometimes required to uphold the R,G-first normalization.

 R G R b   R G R Y   R G r y   R G G B   R G g B   R G B B   R G B B

 B G Y y   b g Y B   g b y b   R Y B Y   R Y b Y   R y g Y   R G Y Y

 Y Y G B   Y Y G B   y y g b   B B R Y   B B R Y   B B R Y   B B R Y

 B R G R   B R G R   b r g r   Y g r G   Y R G G   Y R G G   Y R G G



 R G B B   R G B B   R G B B   R G B B   R G b b   R G G G   R G G G

 R B Y Y   R B Y Y   R B Y Y   R B Y Y   R B Y Y   R b Y Y   R G Y Y

 B G R Y   B g R Y   B y r Y   b r Y Y   R b Y Y   R g Y Y   R B Y Y

 y r G G   R y G G   R G G G   R G G G   R g g g   R B B B   R B B B 

 R G R B   R G R B   R G r B   R G G B   R G G B   R G G B   R G G B

 B Y G Y   B Y G Y   B Y g Y   B Y R Y   B Y r Y   B Y B y   B Y B B

 y G Y B   b g Y B   G B Y B   G b y B   G Y b B   G Y R b   G Y R Y

 b R G R   Y R G R   Y R G R   Y R G R   Y R G R   Y R G R   Y R G R



 R G G B   R G G B   R G G B   R g g b   R R R G   R R R G   R R R G

 B Y B B   B y B B   b g B B   g b b b   y G G G   R G G G   R G G G

 G y g Y   G g Y Y   G Y Y Y   g y y y   r B B B   y B B B   B B B B

 Y R R R   Y R R R   Y R R R   y r r r   B Y Y Y   b Y Y Y   Y Y Y Y 

 R G R y   R G R B   R G R B   R G R B   R G R B   R G r b   R G B R

 Y G B b   Y G B Y   Y G B Y   Y G B Y   y G B Y   B G b Y   B G R Y

 B B G Y   B B g y   B B y G   B B G G   b B G G   Y b G G   Y R G G

 Y R G R   Y R G R   Y R g R   Y r y R   Y Y R R   Y Y r r   Y Y B B



 R G R R   R G R R   R G R R   R G R R   R G R R   R g R R   R R R R

 B G b Y   B G g y   B g y G   b y G G   Y b G G   y r g g   G Y Y Y

 Y R g G   Y R B G   Y R B G   Y R B G   Y r B G   y B B g   G B B Y

 Y Y B B   Y Y B B   Y Y B B   Y Y B B   Y Y B B   y y B B   G G B B 

 R G R Y   R G R Y   R g r Y   R R G Y   R R G Y   R R G Y   R R G Y

 Y B G B   y b G B   B Y G B   B Y G B   B y g B   B G Y B   B G Y B

 B g b Y   B B G Y   B B G Y   B B g y   B B y g   B B G Y   B B G Y

 Y R G R   Y R G R   Y R G R   Y R G R   y R g R   G R y r   G R R Y



 R r g y   R G Y B   R G Y B   R G Y B   R G Y B   R G Y B   R G Y B

 b g y b   G Y b r   G y r B   G R Y B   g r Y B   R G Y B   R G Y B

 b r g y   R G Y B   R G Y B   R G Y B   R G Y B   R G Y B   R G Y B

 g b r y   Y R G B   Y R G B   y r G B   R Y G B   R y g B   R G Y B 

CODE:

file <cb_pr.py> compile using pythran -O3 cb_pr.py

import numpy as np

# pythran export check_patt(uint8[536870912])
# pythran export inc_depth(uint8[536870912],int,int)
# pythran export find_home(uint8[536870912],int[:],int[:],int[:,24])

# To make things fast and to save memory we encode positions as 32 bit ints,
# 2 bits per color, Due to our R-G-first convention The first three bits will
# always be zero, that was necessary because of RAM limitatioins on my machine.
# Since we store only one  byte, the distance to the nearest end position, we
# need in total 2^29 bytes to store the entire lookup table
 

# This function runs through all patterns, identifies end positions and marks
# them with 1.
# To efficiently check for connectedness of all four colors simultaneously
# the color representation is first expanded from  2 bits to 4 bits; this still
# fits in a 64 bit int and allows to set or clear each color in each cell
# simultneously and independently. We then do a bucket fill using bit
# twiddling, starting from a random single cell germ for each color.
# for example to check for the potential top neighbors of all cells we left
# shift by 16 bits. Similarly and simultaneously we check for the three other
# directions and OR everything together.
# and then AND with the original pattern to retain only actual neighbors.

def check_patt(out):
    cnt = 0
    for cc in range(len(out)):
        b = 0
        last = np.zeros(4,int)-1
        c = cc
        for d in range(16):
            b = b | (1<<((c&3)|(d<<2)))
            last[c&3] = d
            c = c >> 2
        germ = 0
        nxt = (15<<(last[last>=0]<<2)).sum()&b
        while nxt != germ:
            germ = nxt
            nxt = (germ | (germ<<16) | (germ>>16) |
                   ((germ<<4)&-0xf000f000f0010) |
                   ((germ>>4)&0xfff0fff0fff0fff)) & b
        if nxt==b:
            out[cc] = 1
            cnt += 1
    return cnt

# This function increases the search depth by one. It looks up all positions
# labeled with the current depth, computes all 24 single step reachable
# postitions, looks them up and if they are not labeled yet labels them with
# the current depth + 1.
# The only complication occurs when the move creates a position > 2^29. In that
# case colors must be remapped. This can be done relatively cheaply with bit
# manipulations but is not easy to read.

def inc_depth(out,depth,cnt):
    for cc in range(len(out)):
        if out[cc] == depth:
            for i in range(1,16):
                if i&3:
                    m = (3<<(i<<1)) & (cc ^ (cc<<2)) 
                    dd = cc ^ (m | (m>>2))
                    if dd >= 1<<30:
                        dd = dd ^ (((dd>>30)) * 0x55555555)
                    if (dd & 0x55555555) < (dd & 0xaaaaaaaa):
                        sp = dd
                        for sh in (16,8,4,2):
                            spn = sp >> sh
                            if spn >= 2:
                                sp = spn
                        if sp&1:
                            dd = dd ^ ((dd&0x55555555)<<1)
                        else:
                            dd = dd ^ (((dd^(dd>>1))&0x55555555)*3)
                        if(dd>=1<<29):
                            print(hex(dd),sp)
                    if out[dd] == 0:
                        out[dd] = depth+1
                        cnt += 1
            for i in range(4,16):
                m = (3<<(i<<1)) & (cc ^ (cc<<8))
                dd = cc ^ (m | (m>>8))
                if dd >= 1<<30:
                    dd = dd ^ (((dd>>30)) * 0x55555555)
                if (dd & 0x55555555) < (dd & 0xaaaaaaaa):
                    sp = dd
                    for sh in (16,8,4,2):
                        spn = sp >> sh
                        if spn >= 2:
                            sp = spn
                    if sp&1:
                        dd = dd ^ ((dd&0x55555555)<<1)
                    else:
                        dd = dd ^ (((dd^(dd>>1))&0x55555555)*3)
                    if(dd>=1<<29):
                        print(hex(dd),sp)
                if out[dd] == 0:
                    out[dd] = depth+1
                    cnt += 1
    return cnt

# This function uses the finalized lookup table to find one shortest way from
# a given position to one nearest end position

def find_home(out,p,cnts,rnd):
    d0 = out[p[0]]
    for d in range(d0-1):
        cnts[d] = 0
        for ii in rnd[d]:
            if ii < 12:
                i = (ii<<2)//3
                m = (3<<(i<<1)) & (p[d] ^ (p[d]>>2))
                pd = p[d] ^ (m | (m<<2))
            else:
                i = ii - 12
                m = (3<<(i<<1)) & (p[d] ^ (p[d]>>8))
                pd = p[d] ^ (m | (m<<8))
            if pd >= 1<<30:
                pd = pd ^ (((pd>>30)) * 0x55555555)
            if (pd & 0x55555555) < (pd & 0xaaaaaaaa):
                sp = pd
                for sh in (16,8,4,2):
                    spn = sp >> sh
                    if spn >= 2:
                        sp = spn
                if sp&1:
                    pd = pd ^ ((pd&0x55555555)<<1)
                else:
                    pd = pd ^ (((pd^(pd>>1))&0x55555555)*3)
            if out[pd]==d0-d-1:
                if cnts[d] == 0:
                    p[d+1] = pd
                cnts[d] = cnts[d] + 1
    return 0

main script:

import numpy as np
from cb_pr import check_patt,inc_depth,find_home

# allocate lookup table
out = np.zeros(1<<29,np.uint8)
# mark end postiions
cnt = check_patt(out)
# push depth
d = 1
while cnt < 1<<29:
    ncnt = inc_depth(out,d,cnt)
    if ncnt == cnt:
        break
    d += 1
# lookup table is done

# fancy visualisation ...
b = chr(11044)
# .. using tty color escapes ...
bullets = ["\x1b[31;47m"+b,"\x1b[32;47m"+b,"\x1b[34;47m"+b,"\x1b[33;47m"+b,
           "\x1b[31;49m"+b,"\x1b[32;49m"+b,"\x1b[34;49m"+b,"\x1b[33;49m"+b]
# ... or black and white unicode symbols
baw = chr(10680),chr(10682),chr(10687),chr(10686)
baws = baw

# the visualization function -- horrible code but does the job
# the "simple" style has PSE markup you may want to delete that for home use
def show(codes,style='simple',cut=7):
    codes = [codes[i:i+cut] for i in range(0,len(codes),cut)]
    if style=="baw":
        out = "\n\n".join("\n".join("   ".join(" ".join((baws[(x>>(30-2*i))&3]) for i in range(4*j,4*j+4)) for x in cod) for j in range(4)) for cod in codes)
    elif style=="color":
        out = "\n\n".join(" \x1B[0m \n".join(" \x1B[0m   ".join(" \x1B[0m".join((bullets[((x>>(30-2*i))&3)+(((i+j)&1)<<2)]) for i in range(4*j,4*j+4)) for x in cod) for j in range(4)) for cod in codes)
    else:
        out = []
        for cod in codes:
            dff = np.array(cod)
            dff[:-1] ^= dff[1:]
            dff[-1] = 0
            out.append("\n>! ".join("   ".join(" ".join(("RGBYrgby"[((x>>(30-2*i))&3)+4*(((y>>(30-2*i))&3)!=0)]) for i in range(4*j,4*j+4)) for x,y in zip(cod,dff)) for j in range(4)))
        out = ">! <pre> " + "\n>!\n>! ".join(out) + " </pre>"
    return out

# reconstruct solution given starting position p0 using loookup table out
def rec_sol(p0,style="simple"):
    d = out[p0]
    cnts = np.zeros(d-1,int)
    p = np.zeros(d,int)
    p[0] = p0
    rnd = np.array([np.random.permutation(24) for _ in range(d-1)],int)
    if find_home(out,p,cnts,rnd) < 0:
        raise RuntimeError
    print(show(p,style))
    return p,cnts

# some minimal statistics:
h = np.zeros(32,int)
CHUNK = 1<<24
for i in range(0,out.size,CHUNK):
    h += np.bincount(out[i:i+CHUNK],None,32)
# extract farthest from end positions:    
sols = (out==d).nonzero()[0]
for sol in sols:
    rec_sol(sol,"color")
    print();print()
# reset terminal colors
print("\x1B[0m")