Practice

Contest

CAKEWALK

# 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:

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:

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