Foren / Forums › Lösungen / Solutions › Aufgabe 13 / Challenge 13
Lösungen Aufgabe 13 2024

margarita
Lösungen Aufgabe 13 2024
15
850
  • 0 Bewertung(en) - 0 im Durchschnitt
  • 1
  • 2
  • 3
  • 4
  • 5
Baumstrukturmodus
Lösungen Aufgabe 13 2024

margarita

Administrator*in
*******
Beiträge:
152
Themen:
40
Registriert seit:
Oct 2023
Bewertung:
16
Lösungsideen
Suchen
Zitieren

V_B

Junior Member
**
Beiträge:
10
Themen:
0
Registriert seit:
Dec 2024
Bewertung:
0
Wer aktiviert denn hier jedesmal (aktuell für Aufgabe 11, 12 und 13) die alten Threads vom Januar 2024?
Suchen
Zitieren

marac

Junior Member
**
Beiträge:
34
Themen:
0
Registriert seit:
Nov 2024
Bewertung:
8
Entscheidend ist hier Regel 5: jeder Rubin muss in einem Quadrat der "mittlere" sein.
Damit ein Rubin der mittlere sein kann, dürfen in diesem Quadrat dann aber auch nur drei Rubine vorhanden sein.
Nachdem es für jeden Rubin ein solches Quadrat geben muss, kann es nicht mehr Rubine als Nicht-Rubine geben, bei 16 Ecken insgesamt kann es also nicht mehr als acht Rubine geben.

Wenn man nun ein gültiges Design findet, das acht Rubine enthält, ist dies gleichzeitig optimal. Und das kann man auf Grundlage der Idee, dass die Rubine eine durchgängige geschlossene Kette bilden müssen, recht leicht bilden (z.B. MOPLDBAE).

--> Antwort 5
Suchen
Zitieren

st1974

Junior Member
**
Beiträge:
26
Themen:
1
Registriert seit:
Nov 2024
Bewertung:
4
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.
Suchen
Zitieren

built_different

Junior Member
**
Beiträge:
5
Themen:
0
Registriert seit:
Dec 2024
Bewertung:
0
(12-20-2024, 06:53 PM)marac schrieb: Entscheidend ist hier Regel 5: jeder Rubin muss in einem Quadrat der "mittlere" sein.
Damit ein Rubin der mittlere sein kann, dürfen in diesem Quadrat dann aber auch nur drei Rubine vorhanden sein.
Nachdem es für jeden Rubin ein solches Quadrat geben muss, kann es nicht mehr Rubine als Nicht-Rubine geben, bei 16 Ecken insgesamt kann es also nicht mehr als acht Rubine geben.

Wenn man nun ein gültiges Design findet, das acht Rubine enthält, ist dies gleichzeitig optimal. Und das kann man auf Grundlage der Idee, dass die Rubine eine durchgängige geschlossene Kette bilden müssen, recht leicht bilden (z.B. MOPLDBAE).

--> Antwort 5

Ein Nicht-Rubin kann doch theoretisch auch für mehrere Rubine der Nicht-Rubin sein, oder?
Suchen
Zitieren

marac

Junior Member
**
Beiträge:
34
Themen:
0
Registriert seit:
Nov 2024
Bewertung:
8
(12-20-2024, 07:35 PM)built_different schrieb: Ein Nicht-Rubin kann doch theoretisch auch für mehrere Rubine der Nicht-Rubin sein, oder?

Hmm, da fällt mir in der Tat spontan kein Gegenargument ein... Klingt nach Lösung richtig, aber Beweis unvollständig... Big Grin
Suchen
Zitieren

Optimismus

Junior Member
**
Beiträge:
1
Themen:
0
Registriert seit:
Nov 2024
Bewertung:
0
(12-20-2024, 06:53 PM)marac schrieb: [...] Und das kann man auf Grundlage der Idee, dass die Rubine eine durchgängige geschlossene Kette bilden müssen, recht leicht bilden (z.B. MOPLDBAE).

--> Antwort 5


Ich habs mir auch ähnlich gedacht: Da man keinen "fehlenden" Rubin erkennen kann, wenn dieser am Ende einer Kette an Rubinen ist, müssen alle Rubine Teil eines Rings sein. Ich habe keinen Weg gefunden einen Ring mit mehr als 8 Rubinen zu bauen, ohne dabei eine der Bau-Regeln zu verletzen. Meine Lösung ist daher auch 8 Rubine.

Nur dass ich gerade gemerkt habe, dass ich statt "5. 8 Rubine" auf Antwort 8 geklickt habe.  Cry
Suchen
Zitieren

DFUx

Junior Member
**
Beiträge:
36
Themen:
4
Registriert seit:
Nov 2024
Bewertung:
4
(12-20-2024, 07:35 PM)built_different schrieb: Ein Nicht-Rubin kann doch theoretisch auch für mehrere Rubine der Nicht-Rubin sein, oder?

Nein, dass geht nicht, wenn jeder dieser zwei Rubine ein mittlerer Rubin mit zwei Nachbarn sein muss. Das führt dann ganz schnell zu einem Würfel mit nicht zusammenhängenden Nicht-Rubinen, weil diese zwei Rubine immer in einem Würfel liegen. 

Sei C der Nicht-Rubin für zwei mittlere Rubine. Diese zwei Rubine könnten dann E, H, B sein oder I, O, L. Diese liegen paarweise immer in einem Würfel. Und in diesem Würfel hängen dann entweder die Nicht-Rubine nicht zusammen, oder die Bedingung, dass jeder Rubin wegen der Fehlererkennung ein mittlerer sein muss, kann nicht erfüllt werden.
Grüße
DFUx
Suchen
Zitieren

Kosakenzipfel

Junior Member
**
Beiträge:
38
Themen:
2
Registriert seit:
Nov 2024
Bewertung:
3
(12-20-2024, 07:32 PM)st1974 schrieb: 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.

Vielen Dank
Bin gespannt, wie man es machen kann. Wird mein Nacht-Programm.
Suchen
Zitieren

Georg J. aus D.

Junior Member
**
Beiträge:
19
Themen:
2
Registriert seit:
Nov 2024
Bewertung:
1
Das ist bisher meine Lieblingsaufgabe in diesem Jahr, denn ich konnte endlich programmieren.

Was mir bei den 24 Designs aufgefallen ist: Die 8 Eckenpaare, deren Ecken voneinander maximal entfernt sind (Abstand = 4), sind entweder beide Rubine oder beide Nicht-Rubine: (A, P), (B, O), (C, N), ..., (H, I)

Code:
A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
0  0  0  1  1  0  1  1  1  1  0  1  1  0  0  0
0  0  0  1  1  1  0  1  1  0  1  1  1  0  0  0
0  0  1  0  0  1  1  1  1  1  1  0  0  1  0  0
0  0  1  0  1  1  1  0  0  1  1  1  0  1  0  0
0  0  1  1  0  1  0  1  1  0  1  0  1  1  0  0
0  0  1  1  1  0  1  0  0  1  0  1  1  1  0  0
0  1  0  0  0  1  1  1  1  1  1  0  0  0  1  0
0  1  0  0  1  1  1  0  0  1  1  1  0  0  1  0
0  1  0  1  0  0  1  1  1  1  0  0  1  0  1  0
0  1  0  1  1  1  0  0  0  0  1  1  1  0  1  0
0  1  1  1  0  0  1  0  0  1  0  0  1  1  1  0
0  1  1  1  0  1  0  0  0  0  1  0  1  1  1  0
1  0  0  0  1  0  1  1  1  1  0  1  0  0  0  1
1  0  0  0  1  1  0  1  1  0  1  1  0  0  0  1
1  0  1  0  0  0  1  1  1  1  0  0  0  1  0  1
1  0  1  0  1  1  0  0  0  0  1  1  0  1  0  1
1  0  1  1  0  0  0  1  1  0  0  0  1  1  0  1
1  0  1  1  1  0  0  0  0  0  0  1  1  1  0  1
1  1  0  0  0  1  0  1  1  0  1  0  0  0  1  1
1  1  0  0  1  0  1  0  0  1  0  1  0  0  1  1
1  1  0  1  0  0  0  1  1  0  0  0  1  0  1  1
1  1  0  1  1  0  0  0  0  0  0  1  1  0  1  1
1  1  1  0  0  0  1  0  0  1  0  0  0  1  1  1
1  1  1  0  0  1  0  0  0  0  1  0  0  1  1  1
Die Lösung ist vom Lösungsweg unabhängig.
Suchen
Zitieren


Gehe zu:


Benutzer, die gerade dieses Thema anschauen:
1 Gast/Gäste