Robot Instructions

01 · Question

A robot program contains only L, R, and 2. L and R each emit one move. A 2 executes all instructions after it twice, but skips the first instruction character of that suffix during the second execution. A 2 never appears at the end of a valid program. Return the expanded sequence of L/R moves.

Examples: LL → LL; 2LR → LRR; 2L → L; 22LR → LRRLR; LL2R2L → LLRLL. Empty input produces an empty string.

02 · Analysis

Helper contract: visit(i) appends the expansion of the suffix beginning at i. At L/R, append that move and visit i+1. At 2, visit i+1 and then i+2, in that order. The second call skips one original instruction, not one expanded move.

The index increases on every edge, so the maximum active depth is O(n). Capture one input and one output buffer; Python slices and repeated string concatenation would add copying work. The helper mutates the buffer, so the wrapper calls it and then returns the assembled string.

For C calls and L output characters, O(C+L) time, O(n) stack, O(L) output storage. The worst case is exponential in n (O(2^n) is a valid upper bound); avoiding copies cannot avoid writing the output. Run the function twice to check that output state is not shared between invocations.

03 · Solution

Reference solution

1def robot_instructions(seq):
2    output = []
3    def visit(i):
4        if i == len(seq):
5            return
6        if seq[i] == '2':
7            visit(i + 1)
8            visit(i + 2)
9        else:
10            output.append(seq[i])
11            visit(i + 1)
12    visit(0)
13    return ''.join(output)

Nested Array Sum