Lösungen Aufgabe 13 2024

[ukleinek]

Mein Python-Programm ist etwas anders. Ich habe die Würfel und Quadrate und Kanten händisch erstellt. (Wobei ich kurz nachgedacht hatte, statt den Buchstaben `itertools.product([0, 1], repeat=4)` zu verwenden. Dann sind die Kanten die Punkte, die an 3 Komponenten übereinstimmen, die Quadrate die, die an 2 übereinstimmen und die Würfel an dreien. Naja.

Dann bin ich die Möglichen Teilmengen aufsteigend durchgegangen und habe alle Bedingungen geprüft.

Code:

#!/usr/bin/env python3

points = set('ABCDEFGHIJKLMNOP')

edges = set(frozenset(ed) for ed in 'AB CD EF GH IJ KL MN OP AC BD EG FH IK JL MO NP AE BF CG DH IM JN KO LP AI BJ CK DL EM FN GO HP'.split())

squares = set(frozenset(sq) for sq in 'ABDC EFGH IJLK MNPO ACGE BDHF IKOM JLPN ABFE CDHG IJNM KLPO ABJI CDLK EFNM GHPO ACKI BDHF EGOM FHPN'.split())

cubes = set(frozenset(cu) for cu in 'ABCDEFGH IJKLMNOP ABIJEFMN CDKLGHOP ABCDIJKL EFGHMNOP BDFHJLNP ACEGIKMO'.split())

def increasing_subsets(st):
    def ssos(st, size):
        if size == 0:
            yield set()
        elif st:
            nst = st.copy()
            elem = nst.pop()
            for ss in ssos(nst, size):
                yield ss
            for ss in ssos(nst, size - 1):
                yield {elem} | ss
    for i in range(len(st) + 1):
        for ss in ssos(st, i):
            yield ss

def isconnected(st):
    if not st:
        return True
    openset = set(st)
    closedset = { openset.pop() }
    changed = True
    while changed:
        changed = False
        for po in openset.copy():
            for pc in closedset:
                if frozenset({po, pc}) in edges:
                    openset -= { po }
                    closedset |= { po }
                    changed = True
                    break;

    if openset:
        return False
    else:
        return True

# Now assume A has a Ruby and B doesn't
pointswithoutAB = points - {'A', 'B'}

for nonrubies in increasing_subsets(pointswithoutAB):
    nonrubies = nonrubies | { 'B' }
    rubies = points - nonrubies

    print(f'check {nonrubies=}')

    if not isconnected(nonrubies):
        continue

    if not isconnected(rubies):
        continue

    if not all(isconnected(nonrubies & sq) for sq in squares):
        continue

    if not all(isconnected(nonrubies & cu) for cu in cubes):
        continue

    if not all(isconnected(rubies & sq) for sq in squares):
        continue

    if not all(isconnected(rubies & cu) for cu in cubes):
        continue

    if not all(any(not isconnected((rubies - {r}) & sq) for sq in squares) for r in rubies):
        continue

    print(f'{nonrubies=}')
    break