🌙 The Ramadan Cleanup: Memory Management Challenge

A dual-strategy garbage collection simulator implementing Reference Counting and Periodic Mark-and-Sweep to manage a heap of interconnected objects.

---

📋 Challenge Overview

The ship's memory heap has ballooned overnight. To prevent a system crash, we implement two reclamation strategies:

graph TD
    A[Heap Operations] --> B{Strategy}
    B -->|Part 1| C[Reference Counting]
    B -->|Part 2| D[Mark-and-Sweep]
    C --> C1[Immediate Cascade Free]
    D --> D1[Periodic BFS Traversal]
    D1 --> D2[Sweep Unreachable]

Loading

---

🛠️ Architecture & Logic

The solver is implemented in solution.py, featuring a high-performance graph model using adjacency sets and breadth-first search (BFS) for reachability analysis.

🔍 Strategy 1: Reference Counting

Tracks the number of incoming references. An object is "alive" if it has at least one reference (either from another alive object or as a root).

• Multiplicity: Reference counts are incremented on every REF assignment, even if the pointer already exists.
• Cascading Free: When a count hits zero, the object is immediately freed, and all its outgoing references are decremented, potentially triggering a chain reaction of deallocations.
• Weakness: Cannot reclaim cyclic garbage (e.g., two objects pointing only to each other).

🧹 Strategy 2: Periodic Mark-and-Sweep

Ignores individual counts and instead validates reachability from the root set at specific intervals ($K$).

• GC Trigger: Every $K$ non-ALLOC operations involving alive objects trigger a GC cycle.
• Mark Phase: BFS traversal starting from all active roots.
• Sweep Phase: Any allocated object not reached during the Mark phase is deallocated. Incoming and outgoing edges are stripped to prevent "ghost" references.
• Strength: Efficiently reclaims cycles and leaked objects that were never reachable.

---

🚀 Key Implementation Details

⚡ Performance Optimizations

• Adjacency Sets: Used set() for outgoing and incoming references to ensure $O(1)$ average time complexity for edge mutations.
• Bidirectional Tracking: Maintained incoming edges specifically for Part 2 to allow fast cleanup of references when an object is swept.
• Memory Efficiency: Avoided recursion in free_object and run_gc by using iterative deque-based traversals to prevent stack overflow on deep object chains.

🧪 Decision Log: "Effective" Operations

One of the most critical aspects of Part 2 is defining what counts as an "effective" operation for the GC counter:

The successful implementation counts every non-ALLOC operation targeting objects that are currently allocated, even if the operation doesn't change the graph structure (e.g., a duplicate REF).

---

📊 Final Results

Part	Description	Calculated Value
Part 1	Total Size (Ref Counting)	15,115,224
Part 2	Combined Score	2,507,296,607,940

---

📂 Project Structure

• solution.py: The complete Python implementation.
• input.txt: The puzzle input (92k+ operations).
• README.md: This documentation.

---

⚙️ How to Run

python3 solution.py input.txt