[Bug] Marking the Event Timeline - Solution Incorrectly Prevents Valid Overwrites

[akashsv01]

Hello CodePath Team,

While working through TIP103 Unit 3, I noticed that the solution provided for the "Marking the Event Timeline" problem does not produce the expected outputs. The issue lies in the can_place function, which prevents overwriting characters - a behavior that is clearly allowed based on the problem's own example.

Problem Overview
The goal is to find a sequence of indices where placing the event string will eventually construct the timeline string.

Expected Behavior

print(mark_event_timeline("abc", "ababc"))      # Expected: [0, 2]
print(mark_event_timeline("abca", "aabcaca"))   # Expected: [3, 0, 1]

Proof That Overwrites Are Allowed (From the Problem's Own Example)

The problem statement provides this explanation for "ababc":

• Start with t = "?????"
• Place "abc" at index 0 → t = "abc??"
• Place "abc" at index 2 → t = "ababc" - timeline is complete.

Step 1: Place "abc" at index 0
  Before: ['?', '?', '?', '?', '?']
           ─────────
           place here
  After:  ['a', 'b', 'c', '?', '?']

Step 2: Place "abc" at index 2
  Before: ['a', 'b', 'c', '?', '?']
                    ─────────
                    place here
  After:  ['a', 'b', 'a', 'b', 'c']
                    ↑
                    'c' was OVERWRITTEN with 'a'

The example explicitly shows that 'c' at index 2 gets overwritten with 'a'. This proves overwrites are allowed.

The Bug

The current can_place function blocks any overwrite of existing characters:

def can_place(t, event, start):
    for i in range(event_len):
        if t[start + i] != '?' and t[start + i] != event[i]:
            return False  # ❌ This prevents valid overwrites
    return True

Proposed Fix
Remove the can_place restriction entirely (since overwrites are allowed) and add a visited set to prevent infinite loops:

from collections import deque

def mark_event_timeline(event, timeline):
    t_len = len(timeline)
    event_len = len(event)
    queue = deque([(['?'] * t_len, [])])
    max_turns = 10 * t_len
    visited = set()
    visited.add(tuple(['?'] * t_len))

    def place_event(t, start):
        new_t = t[:]
        for i in range(event_len):
            new_t[start + i] = event[i]
        return new_t
    
    turns = 0
    while queue and turns < max_turns:
        current_t, indices = queue.popleft()
        
        for i in range(t_len - event_len + 1):
            new_t = place_event(current_t, i)
            new_indices = indices + [i]
            
            state_key = tuple(new_t)
            if state_key in visited:
                continue
            visited.add(state_key)
            
            if ''.join(new_t) == timeline:
                return new_indices
            
            queue.append((new_t, new_indices))
        
        turns += 1
    
    return []

The problem's own examples demonstrate that overwriting is allowed ('c' → 'a' at index 2). However, the current solution's can_place function incorrectly blocks such overwrites, making it impossible to reach valid solutions. The fix removes this restriction and adds state tracking to ensure correctness.

Thanks for all the great content - happy to discuss further!

Best Regards,
Akash S Vora