Lösungen Aufgabe 13 2024

[st1974]

Ich habe im Feedback-Forum meine Programmlösung versprochen (Python):

Code:

def Teilmengen(s):
    if len(s)==0 :
        yield ""
    else:
        for t in Teilmengen(s[1:]):
            yield t
            yield s[0]+t


class Tesserakt:
    def __init__(self):
        self.Kanten = set()
        self.Quadrate = set()
        self.Wuerfel = set()
        self.add_Wuerfel("ABDCEFHG")
        self.add_Wuerfel("IJLKMNPO")
        self.add_Wuerfel("ABFEIJNM")
        self.add_Wuerfel("BDHFJLPN")
        self.add_Wuerfel("CDHGKLPO")
        self.add_Wuerfel("ACGEIKOM")
        self.add_Wuerfel("ABDCIJLK")
        self.add_Wuerfel("EFHGMNPO")
    def add_Wuerfel(self,P):
        self.Wuerfel.add(P)
        self.add_Quadrat(P[:4])
        self.add_Quadrat(P[4:])
        self.add_Quadrat(P[0]+P[1]+P[5]+P[4])
        self.add_Quadrat(P[1]+P[2]+P[6]+P[5])
        self.add_Quadrat(P[2]+P[3]+P[7]+P[6])
        self.add_Quadrat(P[3]+P[0]+P[4]+P[7])
    def add_Quadrat(self,P):
        L = list(P)
        L.sort()
        Psort = "".join(L)
        self.Quadrate.add(Psort)
        self.add_Kante(P[0],P[1])
        self.add_Kante(P[1],P[2])
        self.add_Kante(P[2],P[3])
        self.add_Kante(P[3],P[0])
    def add_Kante(self,p1,p2):
        if p1<p2 :
            P = p1+p2
        else:
            P = p2+p1
        self.Kanten.add(P)
    def Verbundenheit(self,Rubine,Menge):
        M0 = M1 = ""
        for m in Menge:
            if m in Rubine:
                M1 += m
            else:
                M0 += m
        return (self.cluster(M0) < 2) and (self.cluster(M1) < 2)
    def cluster(self,M):
        if len(M)<2 : return len(M)
        L =[(m,) for m in M]
        for Kante in self.Kanten:
            v1,v2 = tuple(Kante)
            if v1 in M and v2 in M:
                t1,t2 = (),()
                for i in range(len(L)):
                    if v1 in L[i] :
                        t1 = L.pop(i)
                        break
                for i in range(len(L)):
                    if v2 in L[i] :
                        t2 = L.pop(i)
                        break
                L.append(t1+t2)
        return len(L)
    def ist_zulaessig(self,Rubine,nurQuadrate = False):
        if not nurQuadrate:
            # 1. mindested ein Rubin
            if len(Rubine)==0 : return False
            # 2. Verbundenheit der Rubine
            if not self.Verbundenheit(Rubine,"ABCDEFGHIJKLMNOP"):
                return False
            # 3. Verbundenheit in jedem Wuerfel
            for w in self.Wuerfel:
                if not self.Verbundenheit(Rubine,w):
                    return False
        # 4. Verbundenheit in jedem Quadrat
        for q in self.Quadrate:
            if not self.Verbundenheit(Rubine,q):
                return False
        return True
       

T = Tesserakt()
maxRubine = 0

for Rubine in Teilmengen("ABCDEFGHIJKLMNOP"):
    if len(Rubine) < maxRubine : continue
    if T.ist_zulaessig(Rubine):
        unvollstaendigesQuadrat = True
        for i in range(len(Rubine)):
            if T.ist_zulaessig(Rubine[:i]+Rubine[i+1:],True):
                unvollstaendigesQuadrat = False
                break
        if not unvollstaendigesQuadrat:
            continue
        print(Rubine)
        maxRubine = len(Rubine)
   
print(maxRubine)

Dieses Programm liefert 24 Lösungen mit jeweils 8 Rubinen.