After your disastrous canoe ride, you ended up falling off a waterfall at the end of the river rapids. Your canoe exploded, but you managed to survive the explosion. However, your river journey went completely off the map - you have now found yourself lost in the midst of a forest. Luckily, you still have your programming skills, so you decide to carve a program into the side of a tree to help you find your way through the forest. However, there is not much surface area on the tree, so you must make your program as short as possible.
The forest can be described as a
n > 5) square of characters, which will only consist of the lowercase letters
a-z. An example forest:
anehcienwlndm baneiryeivown bnabncmxlriru anhahirrnrauc riwuafuvocvnc riwnbaueibnxz hyirorairener ruwiiwuauawoe qnnvcizdaiehr iefyioeorauvi quoeuroenraib cuivoaisdfuae efoiebnxmcsua
You may have noticed that in this forest, there is a diagonal line of
a characters running through it from the top left corner to the bottom right corner. This is a "path" through the forest which will lead you somewhere if you follow it. Your task is to write a program which will find the singular path. I will now more specifically describe what connotates a "path" in this challenge.
A "path", in this challenge, is defined as a line similiar to one which might have been generated with a Bresenham algorithm, but with the added requirements that:
- The line must be a minimum 6 characters long
- Each collinear (completely adjacent) group of characters in the line must be the same length.
- It will begin at one edge of the forest and end at the opposite edge (see my comment here for elaboration)
To explain the second requirement more clearly, consider the following line:
aaa aaa aaa aaa aaa
This line is composed of collinear "segments" of characters, each of which are exactly three characters long. It qualifies as a path. Now consider this line:
a aa a aa a aa
This line is composed of collinear "segments" that are not all exactly the same length of characters (some of them are 1 character long and some of them are 2). Thus, this one does not qualify as a path.
Your program, given a map of the forest, identify the characters used in the path. Input is to whatever is convienient (e.g. command line argument, STDIN,
prompt(), etc.). It cannot be pre initialised into a variable. The first part of the input is a single integer
n representing the size of the forest (the forest is always a square). After that is a space and then the entire forest as a single string. For instance, the example forest would be presented, as an input, like this:
The output for this would be:
because the path is formed using the letter
a. There will only be one path in the forest. This is code golf, so the lowest number of characters wins. If you have questions, ask in the comments.