puzzle

puzzle.py

import random

import sys
print(sys.getrecursionlimit())
sys.setrecursionlimit(300000)



# singleton
class Graph(dict):
    instance = None
    n_bits = None
    def __new__(cls):
        if cls.instance is None:
            cls.instance = super().__new__(cls)
        return cls.instance
    
    def reset_colors(self):
        for n in self.values():
            n.color = None

    def __repr__(self):
        ns = [str(n) for n in self.values()]
        return "\n".join(ns)
    
    @classmethod
    def reset(cls):
        cls.instance = None


class Node(object):
    def __init__(self, id = frozenset()):
        self.color = None
        self.id = id
        self.nbs = []
        self.g = Graph()
        # register 
        self.g[id] = self
        
    def get_neighbours_sets(self):
        ns = []
        for i in range(self.g.n_bits):
            nid = set(self.id)
            if i in nid:
                nid.remove(i)
            else:
                nid.add(i)
            ns.append(frozenset(nid))
        return ns
    
    def init_neighbours(self, recursive = False):
        for ns in self.get_neighbours_sets():
            if ns not in self.g:
                n = Node(ns)
                if recursive:
                    n.init_neighbours(recursive = True)
            else:
                n = self.g[ns]
            self.nbs.append(n)

    def get_neighbours(self):
        # return [self.g[n] for n in self.get_neighbours_sets()]
        return self.nbs

    def __repr__(self):
        r = f"{self.color if self.color is not None else "?"}|" 
        for i in range(self.g.n_bits):
            r += "1" if i in self.id else "0"
        return r
    
    def colorize_neighbours(self, recursive = False, without_self = False):
        nbs_wo_ass = [n for n in self.get_neighbours() if n.color is None]
        
        nb_colors = set([n.color for n in self.get_neighbours() if n.color is not None])
        all_colors = set(list(range(self.g.n_bits + without_self)))
        miss_colors = all_colors - nb_colors

        if without_self:
            miss_colors = miss_colors - set([self.color])

        # print(f"colors missing: {len(miss_colors)}, unassigned neighbours: {len(nbs_wo_ass)}")
        
        if len(miss_colors) != len(nbs_wo_ass):
            raise Exception(f'Not possible (# missing colors: {len(miss_colors)}, # neighbours without assignments: {len(nbs_wo_ass)})')
        
        if len(nbs_wo_ass) == 0:
            return
        
        miss_colors_list = list(miss_colors)
        nbs_wo_ass_list = list(nbs_wo_ass)
        random.shuffle(nbs_wo_ass_list)
        for i, n in enumerate(nbs_wo_ass_list):
            n.color = miss_colors_list[i%len(miss_colors_list)]

        if recursive:
            for n in nbs_wo_ass_list:
                n.colorize_neighbours(recursive = True, without_self = without_self)




#
Graph.reset()
Graph.n_bits = 4

bn = Node()
bn.init_neighbours(recursive = True)

i = 0
while True:
    i += 1
    try:
        Graph().reset_colors()
        bn.color = 0
        bn.colorize_neighbours(recursive = True, without_self = False)
        break
    except Exception as e:
        pass

    if i%1000 == 0:
        print(i)
    
print(f"Iterations: {i}")

Graph()