GLaCOS (Genetic Lifeform and Cloud Operating System), your AI research assistant, had nothing to do lately, so you decided to create a little game for him to keep him entertained. You downloaded the cloud GLaCOS operates and stored it under the /root/devops/cloud directory. Here are the rules of the game you came up with.
There are a bunch of folders and files under the root/devops/cloud directory. The are two types of files in the system:
A hint. Each hint file starts with a line containing a single "Hint" word (without quotes or leading/trailing whitespace characters). The second line contains a sequence (possibly empty) of words "up" and "down", separated by a single whitespace character. Not a hint. It is guaranteed that the first line of the such a file is not "Hint". The goal of the game is to find a secret folder. It is known that there is a sequence of hints that leads to it, and that the first hint is called start.hint and is located in root/devops/cloud. Here's how to win the game starting with the first hint file:
Consider the second line of the hint file as a sequence of commands, where "up" means going one directory up, and "down" means going one directory down to any child directory. Consider all correct paths this sequence produces. It is guaranteed that among all such paths only one leads to a directory that contains exactly one hint file (all other paths either end up in a directory without hint files, or in a directory with two or more hint files). This hint file under this directory is the one you should consider next, and repeat the process until you visit a folder you've already visited (i.e. grabbed a hint from). Once a hint leads you to a folder you've already visited, you can stop the process: this folder is the one you've been looking for. The absolute path to the folder should be written as the output. You have prepared a bunch of tests for GLaCOS (he's very fond of tests), but at first you need to pass them yourself. Implement a script that will pass all the tests.
Example
Consider the following file structure under /root/devops/cloud:
dir1/ hintFile.txt dir2/ notahint.cpp totallyahint.java dir3/ secret/ congrats q.hello meh.md peh.txt start.hint Here are file contents:
start.hint:
Hint down hintFile.txt:
Hint! Well no, not really. notahint.cpp:
Hint up down down totallyahint.java:
hint up up up q.hello:
Hint down meh.md:
Hint up peh.text:
A cake is a lie congrats:
Hint
The output should thus be root/devops/cloud/dir3/secret.
The first hint (start.hint) leads one directory down. Only one subdirectory of root/devops/cloud contains exactly one hint file, which is folder root/devops/cloud/dir2. It contains a single hint file notahint.cpp, which leads to directory root/devops/cloud/dir3/secret (since this is the only folder in clouds that contains a subfolder). congrats hint file doesn't lead anywhere, i.e. it leads to the current directory, which is the answer.
[time limit] 4000ms (sh)