19
\$\begingroup\$

Find X

I was inspired by math questions in which one is asked to "Find X" for a given shape. Originally, I was just going to have the challenge be to print the x and y location of the character 'x' in a String. But I supposed that would be too simple. So I considered the context they were normally in, and decided finding the length of a Line next to the x just seemed appropriate.

Given a string input containing a Diagram of ascii 'lines' as well as a single 'x' and potentially junk characters, print the length of the only line that has an 'x' directly adjecent to it.

Examples

Input:

|
|
|x
|
|

Ouput:

5

Input:

|\
| \x
|  \
|___\

Output:

4

Input:

Diagram of a Wobbly Line:
IRRELEVANTTEXT____
____     ____/
    \___/ X ;)   
      x

Output:

3

Input:

  ______________
 / ____________ \
 |/ __________ \|
 ||/ ________ \||
 |||/ ______ \|||
 ||||/      \||||
 |||||/  x  |||||
 |||||\_____/||||
 ||||\_______/|||
 |||\_________/||
 ||\___________/|
  \_____________/

Output:

5

Notes

  • The Valid line characters are \/_|
  • \ connects the top left and bottom right of itself.
  • / connects the top right and bottom left of itself.
  • _ connects the left and right of itself
  • | connects the top and bottom of itself
  • A line will always be straight, and only consist of one of the line characters repeated n times.
  • The x will always be lowercase, and it will always be the only one in the diagram.
  • Adjecent refers to the x being exactly one character above, below, or besides.
  • The x will always be next to exactly one Line.
  • Tabs will never appear in the input.
  • Input and Output may be any acceptable format.
  • This is Code Golf, so Shortest Code Wins!
  • HAVE FUN. DO IT. ENJOY YOURSELF.

Reference Implementation

\$\endgroup\$
5
  • \$\begingroup\$ Nice challenge, but I think it would be better to guarantee no tabs in input. By saying they may occur, you´re effectively forcing everyone to add code to convert tab into 4 spaces, which has nothing to do with the main challenge. \$\endgroup\$ Nov 7, 2016 at 1:02
  • \$\begingroup\$ Yeah, you've got a good point. I'll snip that. \$\endgroup\$
    – ATaco
    Nov 7, 2016 at 1:04
  • \$\begingroup\$ You should add a testcase that has a shape similar to @ to stress-test answers. \$\endgroup\$
    – orlp
    Nov 7, 2016 at 1:50
  • \$\begingroup\$ Very clever challenge, I look forward to seeing some of the tactics used to solve it \$\endgroup\$
    – Darren H
    Nov 7, 2016 at 7:59
  • 1
    \$\begingroup\$ tex.stackexchange.com/a/18354 \$\endgroup\$
    – Neil
    Nov 7, 2016 at 9:48

4 Answers 4

8
\$\begingroup\$

Python 3, 428 408 385 378 bytes

Working, but has a ton of potential to be golfed. I'm a bit rusty.

Assumes input is padded with spaces to make a rectangle.

EDIT: Thanks to @Artyer for 23 byte savings!

EDIT2: Wow I completely missed a 6 byte savings. Saved 1 more by swapping sides of an equals check.

*i,=map(list,input().split('\n'))
r=c=s=q=e=w=0
o=lambda y,x:len(i[0])>x>=0<=y<len(i)
d='\/_|'
for l in i:
 if'x'in l:r=i.index(l);c=l.index('x')
for a,b in(1,0),(0,1),(-1,0),(0,-1):
 y,x=r+a,c+b;f=o(y,x)and i[y][x]
 if f in d:s=f;w=d.index(f);q,e=y,x
k=lambda y,x,g=[1,1,0,1][w],v=[1,-1,1,0][w]:o(y,x)and s==i[y][x]and(exec('i[y][x]=0')or 1+k(y+g,x+v)+k(y-g,x-v))
print(k(q,e))

Expanded version with explanation:

inputtt='''  ______________.
 / ____________ \
 |/ __________ \|
 ||/ ________ \||
 |||/ ______ \|||
 ||||/      \||||
 |||||/  x  |||||
 |||||\_____/||||
 ||||\_______/|||
 |||\_________/||
 ||\___________/|
  \_____________/'''

# First, we get the input from STDIN and make it
# into a doubly-nested array

*input_text,=map(list,inputtt.split('\n'))

# A pretty cool Python trick to assign 0 to
# mulitple variables at once.

row=col=line_letter=line_row=line_col=line_char_index=0

# A function to check if a certian row and col is
# in bounds or not. Uses python's comparator chaining

in_bounds=lambda y,x:len(input_text[0])>x>=0<=y<len(input_text)

# A string to store all the line characters.
chars='\/_|'

# Search for the x
for line in input_text:

 # If this line contains the x...
 if'x'in line:

     # Mark the row and column
     row=input_text.index(line);col=line.index('x')

# For each direction...
for down,right in(1,0),(0,1),(-1,0),(0,-1):

 # Move in that direction
 y,x=row+down,col+right

 # If the position is in bounds, mark the char at that position
 line_found=in_bounds(y,x)and input_text[y][x]

 # If the char is a line char, set all the variables saying we found it
 if line_found in chars:
  line_letter=line_found
  line_char_index=chars.index(line_found)
  line_row,line_col=y,x

recur=lambda y,x,\
       # Find which directions we are supposed to recur in based on the line char
       g=[1,1,0,1][line_char_index],v=[1,-1,1,0][line_char_index]:\
       # If the char is in bounds and we are still on the line...
       in_bounds(y,x)and input_text[y][x]==line_letter and\
       # Set the spot to a 0, so we won't go back, increment,
       # and recur in both directions
       (exec('i[y][x]=0')or 1+recur(y+g,x+v)+recur(y-g,x-v))

# Finally, print the answer
print(recur(line_row,line_col))
\$\endgroup\$
4
  • \$\begingroup\$ I've made some golfing suggestions at pastebin.com/zKENQUeR. Feel free to use them if you want (Total: -18 bytes). Also, you might want to add <!-- language-all: lang-py --> for syntax highlighting. \$\endgroup\$
    – Artyer
    Nov 7, 2016 at 21:17
  • \$\begingroup\$ @Artyer Thank you! I was stupid to not do most of those, but I had no idea about the non-escaping backslash. I'm currently on mobile, but I'll be sure to incorporate your suggestions later! \$\endgroup\$
    – Blue
    Nov 7, 2016 at 21:54
  • \$\begingroup\$ Oh, and one more: First line to *i,=map(list,inputtt.split('\n')) (*i, makes i a list instead of a map) (-6 more bytes) \$\endgroup\$
    – Artyer
    Nov 7, 2016 at 22:03
  • \$\begingroup\$ Wow... golfing in its entirety. \$\endgroup\$ Nov 8, 2016 at 12:46
3
\$\begingroup\$

JavaScript (ES6), 165, 155 bytes

EDIT: Inlined x and w, to save some more bytes.

Golfed (assumes input is padded with spaces to make a rectangle)

t=>([k=e=o=1,v=t.search`\n`+2,-1,-v].some(h=>i=({"|":v-1,"_":1,"/":v,"\\":v})[d=t[r=l=t.search`x`+h]]),[...t].map(_=>o+=(k&=t[l-=i]==d)+(e&=t[r+=i]==d)),o)

Expanded

/*
   G(<input string,space padded>) => line length
*/
G=t=> {

    /*
     ! Note that these two are inlined, in the "golfed" version !
     "w" - line "width"
     "x" - index of "x"
    */
    x=t.search`x`;
    w=t.search`\n`+1;

    /*
    Locate the "line"    
     l,r - left cursor, right cursor (for navigating along the line)
     k - left stop flag, e - right stop flag
     i - increment
     d - direction (char)
    */
    [k=e=o=1,v=w+1,-1,-w-1].some(h=>i=({"|":w,"_":1,"/":v,"\\":v})[d=t[r=l=x+h]]);

    /* 
     Travel along the line axis in both directions
    
     Note, the stop condition should rather be: while(k|e), 
     but we iterate over all the chars with map instead (as o is guaranteed to be < # chars),
     to save some space
    */
    [...t].map(_=>o+=(k&=t[l-=i]==d)+(e&=t[r+=i]==d));

    /* 
      Resulting line length
    */
    return o;
};

Test

G= 
t=>([k=e=o=1,v=t.search`\n`+2,-1,-v].some(h=>i=({"|":v-1,"_":1,"/":v,"\\":v})[d=t[r=l=t.search`x`+h]]),[...t].map(_=>o+=(k&=t[l-=i]==d)+(e&=t[r+=i]==d)),o);

[
G( 
 "| \n" +
 "| \n" +
 "|x\n" +
 "| \n" +
 "| \n"
),

G(
"|\\   \n" +
"| \\x \n" +
"|  \\ \n" +
"|___\\\n"
),

G(
"Diagram of a Wobbly Line:\n" +
"IRRELEVANTTEXT____       \n" +
"____     ____\/           \n" +
"    \___\/ X ;)           \n" +    
"      x                  \n"
),

G(
" ______________ \n"  +
"/ ____________ \\\n" +
"|/ __________ \\|\n" +
"||/ ________ \\||\n" + 
"|||/ ______ \\|||\n" +
"||||/      \\||||\n" +
"|||||/  x  |||||\n"  +
"|||||\_____\/||||\n" +
"||||\_______\/|||\n" +
"|||\_________\/||\n" +
"||\___________\/|\n" +
" \_____________\/\n"
)
]

Sample output (if you run this in Google Chrome Developer Tools console)

[5, 4, 3, 5]

\$\endgroup\$
0
\$\begingroup\$

Lua, 480 Bytes

Lua, Being the Verbose Language it is, doesn't beat the Python Answer. But it doesn't need to.

a=...s={}for _ in a:gmatch"[^\n]*"do s[#s+1]={}for S in _:gmatch"."do if S=="x"then x=#s[#s]+1y=#s end s[#s][#s[#s]+1]=S end end c="\\/_|"X={-1,1,1,0}Y={-1,-1,0,-1}for _,d in pairs({{x-1,y},{x,y-1},{x+1,y},{x,y+1}})do K=d[2]k=d[1]h=s[K]w=h and h[k]C=w and c:find(w)if C then n=1 j=k J=K while true do j=j+X[C]J=J+Y[C]if s[J]and s[J][j]==w then n=n+1 else break end end j=k J=K while true do j=j-X[C]J=J-Y[C]if s[J]and s[J][j]==w then n=n+1 else break end end print(n)break end end

Similar to my reference implementation, but takes an actual shot at golfing, and does some things a bit more smartly than before. Still could probably be golfed a bit better though.

With comments.

a=... -- Take the input from the command line.
s={}  -- Store the string as a 2D Table, instead of a multiline string.
for _ in a:gmatch"[^\n]*"do -- For each new row.
    s[#s+1] = {}            -- Make a new sub-table. This is our line.
    for S in _:gmatch"."do  -- For every character.
        if S=="x"then x=#s[#s]+1y=#s end -- If it's an x, mark down the X and Y position of it.
        s[#s][#s[#s]+1]=S                -- Push the character. This could probably be better golfed.
    end
end
c="\\/_|"   -- The ascii line characters.
X={-1,1,1,0}    -- Their X Directionals.
Y={-1,-1,0,-1}  -- Their Y Directionals.
                -- These are inversed to get their opposite direction.
for _,d in pairs({{x-1,y},{x,y-1},{x+1,y},{x,y+1}}) do -- For each up down left and right.
    K=d[2]  -- K = y
    k=d[1]  -- k = x
    h=s[K]  -- h = the yth row
    w=h and h[k]    -- w = the xth character of the yth row, if the yth row exists.
    C=w and c:find(w) -- C = the id of the ascii line character, if w existed.
    if C then
        n=1 -- n = the length of the line.
        j=k -- Temp x
        J=K -- Temp y
        while true do
            j=j+X[C] -- Increment j by the directional of the ascii.
            J=J+Y[C] -- Ditto. for J
            if s[J]and s[J][j]==w then -- if it's still the same.
                n=n+1 -- Add 1 to the length.
            else
                break -- Or stop.
            end
        end
        j=k -- Re-assign the temps as their original.
        J=K
        while true do
            j=j-X[C] -- Search in the other direction.
            J=J-Y[C]
            if s[J]and s[J][j]==w then
                n=n+1
            else
                break
            end
        end
        print(n) -- Print the length.
        break
    end
end
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 175

Assuming input is padded with spaces to make a rectangle.

s=>(o=>{s.replace(/[_|\\/]/g,(c,p)=>[o,-o,1,-1].map(d=>s[p+d]=='x'?[q,k]=[p,c]:c));for(n=z=k>'_'?o:k>'\\'?-1:k>'/'?o-1:o+1;s[q+=z]==k||z<0&&(n=-1,z=-z);)n++})(~s.search`
`)||n

Less golfed

s=>{
  o = ~s.search`\n`; // offset between rows (negated)
  // look for a line character near an 'x'
  s.replace(/[_|\\/]/g, 
     (c,p)=> // for each line char 'c' in position 'p'
     [o,-o,1,-1].map(d=>s[p+d]=='x' // found a near 'x' ?
                        ?[q,k]=[p,c] // remember char and position
                        :c)
  );
  n=0;
  z=k>'_'?o:k>'\\'?-1:k>'/'?o-1:o+1; // offset to prev char of line
  while (s[q+=z]==k // move to left/top first
         || z<0 && (n=0,z=-z) // at left/top, go back and start counting
        )
    n++;
  return n-1;
}

Test Dots instead of spaces for clarity

f=
s=>(o=>{s.replace(/[_|\\/]/g,(c,p)=>[o,-o,1,-1].map(d=>s[p+d]=='x'?[q,k]=[p,c]:c));for(n=z=k>'_'?o:k>'\\'?-1:k>'/'?o-1:o+1;s[q+=z]==k||z<0&&(n=-1,z=-z);)n++})(~s.search`
`)||n

out=x=>O.textContent+=x

;["|.\n|.\n|x\n|.\n|.\n", "|\\...\n|.\\x.\n|..\\.\n|___\\\n"
,"Diagram of a Wobbly Line:\nIRRELEVANTTEXT...........\n____.....____/...........\n....\\___/.X.;)...........\n......x..................\n"
,"./ ____________ \\\n.|/ __________ \|\n.||/ ________ \\||\n.|||/ ______ \\|||\n.||||/      \\||||\n.|||||/  x  |||||\n.|||||\\_____/||||\n.||||\\_______/|||\n.|||\\_________/||\n.||\\___________/|\n. \\_____________/\n"].forEach(s=>out(s+f(s)+'\n\n'))
<pre id=O></pre>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.