The Forest Path

Question

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 by n (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:

13  anehcienwlndmbaneiryeivownbnabncmxlriruanhahirrnraucriwuafuvocvncriwnbaueibnxzhyirorairenerruwiiwuauawoeqnnvcizdaiehriefyioeorauviquoeuroenraibcuivoaisdfuaeefoiebnxmcsua

The output for this would be:

a

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.

Answer 1

Lua - 506 380 - bytes

I felt kinda bad that you hadn't received any submission for your well thought out challenge, so I threw this together. It was quit fun inferring what the minimum distinguishable properties the path must have from the information you gave. I hope I got it right... AND correctly implemented it.

a=io.read"*l"n=a:match("%d+")+0 m=a:match"[a-z]+"o=""for i=1,n do for k=1,n^2,n do o=o..m:sub(i+k-1,i+k-1)end end q={m,o}for g=1,n^2 do for u=1,2 do l=q[u]:sub(g,g)for r=1,n do i=1 t=0 e=0 while i do s,e=q[u]:find(l:rep(r),e+1)if s then x=s-(e-s)-i-1 print(s,i,r,n,r)if x==n or x==n-2 or t==0 then t=t+1 i=s end else i=nil end end if t*r==n then print(l)os.exit()end end end end

It can be tested with:

lua divisorPath.lua "input"

If a wild challenger appears, I'll look to golf my code for what it's worth.

Update: golfed in honour of those who will rise above us. While I was at it I had to fix my code to recognized path going from right to left. Oops.

Answer 2

APL (Dyalog 14) (70)

⎕ML←3⋄Z/⍨1=≢¨Z←∪¨(↓⍉F),(↓F),{(⍳≢⍵)⌷¨↓⍵}¨(⊂F),⊂⌽F←⊃{⍵⍴⍨2/⍎⍺}/I⊂⍨' '≠I←⍞

Explanation:

• ⎕ML←3: set ML to 3, meaning ⊂ has its APL2 meaning.
• I←⍞: read a line from the keyboard and store it in I
• I⊂⍨' '≠I: split I on the spaces
• {...}/: apply this function to the two resulting strings:
  • 2/⍎⍺: evaluate the left argument and replicate it twice, giving the matrix size
  • ⍵⍴⍨: format the right argument using that size
• F←⊃: unbox it and store it in F.
• {(⍳≢⍵)⌷¨↓⍵}¨(⊂F),⊂⌽F: get the diagonals: from each row in both F and ⌽F (vertically mirrored F), get the value at column X, where X is its row number
• (↓⍉F),(↓F),: get the rows and columns of F
• Z←∪¨: find the unique values on each row, column and diagonal and store them in Z.

Since the 'forest' is rectangular, if there is a valid path it means one of these will consist of only one character, which is the path character, so:

• Z/⍨1=≢¨Z: take those subarrays from Z that have only one element.

This will display the characters for all valid paths, but since there should be only one that doesn't matter.

Answer 3

MATLAB - 270 characters

The following defines a function x that accepts a forest string as an argument and returns the character representing the valid "path" through the forest subject to the given rules.

function F=x(s),A=sscanf(s,'%d%s');n=A(1);A=reshape(A(2:end),n,n);for c=A(:)',B=A==c;for i=1:n,if~mod(n,i),C=[kron(eye(i),ones(n/i,1)),zeros(n,n-i)];for j=0:n-i,f=@(B)sum(sum(B&circshift(C,[0,j]))==n;D=fliplr(B);if f(B)|f(B')|f(D)|f(D'),F=char(c);end;end;end;end;end;end

The non-minified version is

function F = x(s)
    A = sscanf( s, '%d %s' );
    n = A(1);
    A = reshape( A(2:end), n,n );
    for c = A(:)'
        B = A==c;
        for i = 1:n
            if ~mod( n, i )
                C = [kron( eye(i), ones( n/i,1 ) ), zeros( n,n-i )];
                for j = 0:n-i
                    f = @(B) sum(sum( B & circshift( C, [0 j] ))) == n;
                    D = fliplr(B);
                    if f(B) | f(B') | f(D) | f(D')
                        F = char(c);
                    end
                end
            end
        end
    end
end

The basic premise is to construct a boolean mask for every possible valid path and return any character whose index function in the matrix covers any mask. To accomplish this, only vertical or top-to-bottom backslash-shaped masks are created, but the forest matrix is compared in all four orientiations: identity, flipped, rotated 90°, flipped rotated 90°.

The function runs for any n. An example of it being invoked on the commandline is

x('13 anehcienwlndmbaneiryeivownbnabncmxlriruanhahirrnraucriwuafuvocvncriwnbaueibnxzhyirorairenerruwiiwuauawoeqnnvcizdaiehriefyioeorauviquoeuroenraibcuivoaisdfuaeefoiebnxmcsua')

ans =

    a

Answer 4

Python - 384 325 275

This Algorithm basically checks the first and last row of the matrix for matching characters and then calculates the length of each line segment

012345
------
aaVaaa|0
aaVaaa|1
aaaVaa|2
aaaVaa|3
aaaaVa|4
aaaaVa|5

In the Example above:
The V in the first row is at index 2, the V in the last row at index 4.
So the length of each line segment would be n / (4-2)+1 = 2 with n=6.

It then checks if the line is valid.

In order to find a path from left to right, it swaps rows with columns and does the same thing again.

Edit: Can't quite get to 270 (Damn you Python and your damn indentation!!)

n,m=raw_input().split()
n,r=int(n),range
t=r(n)
a=[m[i:i+n]for i in r(0,n*n,n)]
for v in a,["".join([a[i][j]for i in t])for j in t]:
 for i in t:
  for j in t:
   p=1-2*(j-i<0);d,c=p*(j-i)+1,v[0][i]
   if 6<=sum([v[z][i+(z/(n/d))*p*(n%d==0)]==c for z in t])==n:print c;exit()