### Problem You are given a text file that describes **batches of register operations** (reads and writes) on integer-indexed registers. Your task is to **schedule and execute** these operations using provided functions, while respecting timing constraints and (for Level 2) intra-batch dependencies. You may **reorder operations within a batch**, but must obey all constraints described below. Implement the function: ```python def execute_operations_from_file(file_path: str): ... ``` You are provided with the following primitives (assume they are already implemented): ```python def read_reg(register_index: int) -> int: """Return the current value of the register with the given index.""" ... def write_reg(register_index: int, value: int) -> None: """Write `value` into the register with the given index.""" ... ``` Your implementation of `execute_operations_from_file` must read the file, compute a valid schedule, and invoke `read_reg` / `write_reg` in that order. --- ### Timing model and global constraints Use a **logical time** measured in milliseconds (ms). You do **not** need to wait in real time; just ensure your computed schedule respects these rules: 1. **Single operation at a time** At any logical time, at most **one** operation (read or write) may be executing. 2. **Minimum gap between operations** Treat each operation as taking negligible time, but the **start times** of any two consecutive operations must be at least **1 ms apart**. - If one operation starts at time `t`, the next operation may start at time `t + 1` or later. 3. **Read-after-write hazard** After a **write** to register `r` starts at time `t`, no **read** of register `r` may start until time **`t + 10`** or later. - That is, between a write to register `r` and any subsequent read of `r`, there must be at least 10 ms. Your goal is to produce a **valid schedule** that respects all of the above rules. Within a batch, you may choose any ordering that leads to a valid schedule. (You may try to minimize the total completion time of all operations, but correctness—i.e., respecting constraints—is the primary requirement.) --- ### Input format The input is a plain text file. Each **non-empty** line is one of the following forms: 1. **Write operation** ```text w ``` - ``: an integer register index (e.g., `0`, `1`, `2`, ...). - `w`: the literal character `w` (write). - ``: an integer value to be written. Example: ```text 2 w 100 ``` means: *write the value `100` to register `2`*. 2. **Read operation (Level 1)** ```text r ``` - ``: an integer register index. - `r`: the literal character `r` (read). Example: ```text 5 r ``` means: *read from register `5`*. 3. **Batch separator** ```text p ``` or ```text P ``` (case-insensitive: treat `p` and `P` the same). Each `p` line **ends the current batch** and starts a **new batch**. The file therefore consists of one or more batches of operations, separated by `p` lines. #### Batch semantics - Operations in **different batches must be strictly sequential**: - **No operation in batch `k+1` may start before all operations in batch `k` have finished**, according to the logical time schedule. - Operations within the **same batch** may be **reordered arbitrarily**, as long as: - All global timing constraints (single operation, 1 ms gap, 10 ms read-after-write) are respected. - All Level 2 dependency constraints (if used) are respected. - It is **guaranteed** that within a single batch, **no register index appears in more than one operation**: - i.e., in any batch, there is never more than one operation involving the same ``. --- ### Level 2: intra-batch read dependencies For Level 2, some read operations within a batch may have an additional dependency on another operation line within the **same batch**. Such a dependent read operation has the format: ```text r ``` where: - ``: an integer register index to be read. - `r`: the literal character `r`. - ``: a **1-based line index within the same batch**, referring to another operation **line** in that batch. - Count only **operation lines**, not `p`/`P` lines. - Line numbering restarts at 1 for each batch. - The referenced line can be either a read or a write operation. - It is guaranteed that `` is valid and refers to a line in the same batch as this read. **Dependency rule:** A read operation written as ` r ` must **not** be scheduled before the operation on the referenced line has executed. In other words, for that pair of operations, your schedule must respect the given precedence constraint in addition to all global timing constraints. All previous rules (single operation at a time, 1 ms gap, 10 ms read-after-write, batch ordering) still apply. --- ### Sample input Example input file (showing multiple batches): ```text 2 w 100 3 w 10 4 w 10 5 r p 4 r 1 r 2 r p 3 w 10 p 2 w 10 3 w 8 5 r ``` This file describes multiple batches of reads and writes, separated by lines containing `p`. --- ### Requirements for `execute_operations_from_file` 1. **Parsing** - Open and read the file at `file_path`. - Split the contents into batches using `p`/`P` lines as separators. - Within each batch, parse each operation line into an internal representation that captures: - the operation type (read or write), - the register index, - the value (for writes), - for Level 2, the optional dependency on another line within the same batch. 2. **Scheduling** - Using a logical time in milliseconds, compute a valid schedule that assigns a **start time** to each operation such that: - Only one operation executes at any given time. - There is at least 1 ms between the start times of consecutive operations. - No read of a register occurs within 10 ms of a previous write to the same register. - All operations in batch `k` finish before any operation in batch `k+1` begins. - For Level 2, each dependent read occurs **after** its referenced operation line in the same batch. 3. **Execution** - Invoke `write_reg` and `read_reg` according to the order implied by your schedule. - You do **not** need to actually sleep or delay in real time; it is sufficient that the logical schedule you compute respects all constraints. 4. **Return value** - `execute_operations_from_file` does not need to return any value; its effect is the sequence of calls to `read_reg` and `write_reg` executed in an order that satisfies all constraints above.

Ixana Coding & Algorithms Interview Questions

Schedule batched register operations optimally