DIRECTI - Editorial

Problem Link

Practice

Contest

Difficulty

CAKEWALK

Pre-requisites

Ad-hoc programming

Problem

Chef has printed directions from home to his new restaurant. You need to take these “printed directions” as input, and output printed directions from the restaurant back to his home.

Explanation

This was just a problem of parsing a little input and giving a good formatted output. Indeed, the problem statement itself described what to do: “When reversing directions, all left turns become right turns and vice versa, and the order of roads and turns is reversed.”

To illustrate the solution, let us consider the first Sample Input:

Begin on Road A

Right on Road B

Right on Road C

Left on Road D

Consider the input in the following 2 sequence manner. Sequence 1 is the set of directions: “Begin”, “Right”, “Right”, “Left”. Lets abbreviate this as BRRL. Sequence 2 is the set of Roads traversed: “Road A”, “Road B”, “Road C”, “Road D”.

Your output should just take sequence 1, put a “Begin” at the beginning, and flip L/R’s in reverse order, and concatenate it with the reverse of sequence 2. That means, reversing sequence 1 gives you: “LRRB”, which when you bring begin to the beginning, and flip L/Rs, gives you “BRLL”. Reversing Sequence 2 gives you: “Road D”, “Road C”, “Road B”, “Road A”.

Finally concatenating the 2 sequences gives you:

Begin on Road D

Right on Road C

Left on Road B

Left on Road A

which is the required output.

Implementation

The best way to implement this would be to (a) store the sequence of L/R values as seen in order, along with (b) an array of Strings determining the roads used (incl. of spaces). A nice trick to use here is to include the word “on” in the road name, so in the example, you would store “on Road A”, “on Road B”, “on Road C”, “on Road D”.
Then traverse the arrays in reverse direction and flip left/right values of the first array and concatenate it with that of the second array.

Author’s Solution

Can be found here

Tester’s Solution

Can be found here