9
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Out of curiosity: Do you have a workable method of scoring, i.e. determining the smallest number of moves for a given position? $\endgroup$ Nov 10, 2020 at 17:12
  • $\begingroup$ Not yet. But I am working on it. $\endgroup$ Nov 10, 2020 at 21:53
  • 1
    $\begingroup$ I have a solver now :) $\endgroup$ Nov 13, 2020 at 1:37
  • $\begingroup$ Just answered. I'm not 100% confident in my program. Could you perhaps use your solver to double check a few of my positions (just the number of steps since the solution paths are not unique)? $\endgroup$ Nov 15, 2020 at 0:40

1 Answer 1

3
$\begingroup$

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")
$\endgroup$
8
  • $\begingroup$ wow great work! I haven't checked your solutions yet, but I wasn't able to find anything that takes more than 13 steps too. $\endgroup$ Nov 15, 2020 at 21:26
  • $\begingroup$ I ran my solver on your first grid and I was able to do it in 12 moves: pastebin.com/Z4J9pHTa $\endgroup$ Nov 17, 2020 at 4:40
  • $\begingroup$ However the second grid seems to require at least 13 moves, so it is a valid solution. $\endgroup$ Nov 17, 2020 at 4:49
  • $\begingroup$ @DmitryKamenetsky Are you sure you copied that correctly? I don't think I had any solution that wasn't 4 of each color. $\endgroup$ Nov 17, 2020 at 5:24
  • $\begingroup$ Yes you are right! Looks like I made a mistake during copying. $\endgroup$ Nov 17, 2020 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.