Adventskalender für drei Personen: jede schenkt jeder jeweils 4 Geschenke, niemand sollte zweimal hintereinander etwas bekommen (sofern lösbar), und eine Person ist an mehreren Tagen abwesend

adventskalender.py

from datetime import datetime, timedelta
from collections import defaultdict

def solve_advent_calendar():
    persons = ['T', 'C', 'K']
    c_absent_days = {1, 2, 5, 6, 7, 8, 9, 10, 11, 15, 16, 17}
    
    # Jede Person muss jedem anderen genau 4 Geschenke geben
    # T->C: 4, T->K: 4, C->T: 4, C->K: 4, K->T: 4, K->C: 4
    gifts_needed = {
        ('T', 'C'): 4,
        ('T', 'K'): 4,
        ('C', 'T'): 4,
        ('C', 'K'): 4,
        ('K', 'T'): 4,
        ('K', 'C'): 4
    }
    
    calendar = {}
    gifts_remaining = gifts_needed.copy()
    last_receiver = {p: -2 for p in persons}  # Letzter Tag, an dem Person beschenkt wurde
    
    # Greedy-Ansatz mit Backtracking
    def find_solution(day):
        if day > 24:
            # Prüfe, ob alle Geschenke verteilt wurden
            return all(count == 0 for count in gifts_remaining.values())
        
        # Versuche alle möglichen Kombinationen für diesen Tag
        for giver in persons:
            for receiver in persons:
                if giver == receiver:
                    continue
                
                pair = (giver, receiver)
                if gifts_remaining[pair] == 0:
                    continue
                
                # Prüfe Constraint: nicht zweimal hintereinander
                if last_receiver[receiver] == day - 1:
                    # Versuche trotzdem, wenn nötig
                    pass
                
                # Prüfe C-Abwesenheit (nur wenn unbedingt nötig)
                if receiver == 'C' and day in c_absent_days:
                    # Erlaube es, wenn es keine bessere Option gibt
                    pass
                
                # Probiere diese Zuweisung
                calendar[day] = (giver, receiver)
                gifts_remaining[pair] -= 1
                old_last = last_receiver[receiver]
                last_receiver[receiver] = day
                
                if find_solution(day + 1):
                    return True
                
                # Backtrack
                del calendar[day]
                gifts_remaining[pair] += 1
                last_receiver[receiver] = old_last
        
        return False
    
    # Besserer Ansatz: Verwende eine heuristische Zuweisung
    def heuristic_solution():
        calendar = {}
        gifts_remaining = gifts_needed.copy()
        last_receiver = {p: -2 for p in persons}
        
        for day in range(1, 25):
            best_choice = None
            best_score = -1000
            
            for giver in persons:
                for receiver in persons:
                    if giver == receiver:
                        continue
                    
                    pair = (giver, receiver)
                    if gifts_remaining[pair] == 0:
                        continue
                    
                    score = 0
                    
                    # Bevorzuge: nicht zweimal hintereinander
                    if last_receiver[receiver] != day - 1:
                        score += 10
                    
                    # Bevorzuge: C nicht an Abwesenheitstagen
                    if receiver == 'C' and day in c_absent_days:
                        score -= 5
                    
                    # Bevorzuge: Geschenke gleichmäßig verteilen
                    score += gifts_remaining[pair] * 2
                    
                    if score > best_score:
                        best_score = score
                        best_choice = (giver, receiver)
            
            if best_choice:
                giver, receiver = best_choice
                calendar[day] = best_choice
                gifts_remaining[(giver, receiver)] -= 1
                last_receiver[receiver] = day
        
        return calendar
    
    return heuristic_solution()

def print_markdown_calendar(calendar):
    # Tag 1 ist Montag
    start_date = datetime(2024, 12, 1)  # Annahme: Dezember 2024, aber Tag 1 ist Montag
    
    print("# Adventskalender\n")
    print("| Mo | Di | Mi | Do | Fr | Sa | So |")
    print("|----|----|----|----|----|----|----|")
    
    week = []
    for day in range(1, 25):
        gift = calendar.get(day, (None, None))
        if gift[0]:
            cell = f"{day}<br>{gift[0]}→{gift[1]}"
        else:
            cell = str(day)
        
        week.append(cell)
        
        # Sonntag oder letzter Tag
        if day % 7 == 0 or day == 24:
            # Fülle die Woche auf
            while len(week) < 7:
                week.append("")
            print("| " + " | ".join(week) + " |")
            week = []
    
    # Statistik
    print("\n## Zusammenfassung\n")
    gifts_count = defaultdict(lambda: defaultdict(int))
    for day, (giver, receiver) in calendar.items():
        gifts_count[giver][receiver] += 1
    
    for giver in ['T', 'C', 'K']:
        for receiver in ['T', 'C', 'K']:
            if giver != receiver:
                count = gifts_count[giver][receiver]
                print(f"- **{giver} → {receiver}:** {count}x")

# Lösung finden und ausgeben
calendar = solve_advent_calendar()
print_markdown_calendar(calendar)