21
\$\begingroup\$

Related | Related


Given an ASCII art with |, _, and , check if you can draw the art in one stroke.

Description

Your task is, if the ASCII art is representing lines, then check if you can draw the whole art in one stroke, which means:

  • without drawing an already drawn line again
  • without lifting and continuing the stroke with skipping blocks

Connection Rules

  • A pipe is connected to the left end of the underscore when:
    • the pipe is left to the underscore |_
    • the pipe is bottom-left to the underscore, but only when it's below a space
 _
|
  • A pipe is connected to the right end of the underscore when:
    • the pipe is right to the underscore _|
    • the pipe is bottom-right to the underscore, but only when it's below a space
_
 |
  • An underscore is connected to another underscore if it is left/right to it ___
  • A pipe is connected to another pipe if it is above/under it
|
|
|

A space should not be viewed as a line but as a gap. It can't connect to a pipe or an underscore.


So this art can be drawn in one stroke:
Image for clarification
(Start at the red cross and end at the blue cross)

Rules

Examples

[In]:
 __
|__|

[Out]: True

[In]:

|__|
|__|

[Out]: False

[In]:
 ___
|___|_ |

[Out]: False (because of the space)

[In]:
 _
|_|_
  __|
 |__|

[Out]: True

[In]:
 _
|_|_
  |_|

[Out]: True

[In]:
 _   _
|_| |_|

[Out]: False

[In]:
    _
|_||_|

[Out]: False (the middle pipes are not connected)

[In]:
__
|_|

[Out]: True (begin top-left)

[In]:
___
|_

[Out]: False (the pipe can't connect to the above underscore)

[In]:
___
   |
   |
   |
[Out]: True

[In] (example by DLosc):
 _
|_|_
  |_

[Out]: False (the two pipes are connected to each other, and so is each underscore it the upper pipe, but the central underscores are not (because there's a pipe between them) and neither underscore to the lower pipe (because the pipe is not below a space)

Good luck!

\$\endgroup\$
8
  • \$\begingroup\$ Can we assume input will be rectangular (padded with spaces so each line is equal length)? \$\endgroup\$ Mar 7 at 0:50
  • \$\begingroup\$ You said a pipe is connected to underscore if the pipe at bottom of underscore. But no testcase for this. You could consider add a testcase for it or remove this behavior from specification. \$\endgroup\$
    – tsh
    Mar 7 at 2:29
  • \$\begingroup\$ @LevelRiverSt yes \$\endgroup\$
    – mathcat
    Mar 7 at 6:41
  • \$\begingroup\$ @tsh thanks, edited \$\endgroup\$
    – mathcat
    Mar 7 at 6:42
  • \$\begingroup\$ @DLosc thanks, I'll edit it, but according to the current rules you would have to do this and then you would have to revisit the line again. \$\endgroup\$
    – mathcat
    Mar 7 at 19:54

1 Answer 1

5
+50
\$\begingroup\$

Python 3.8 (pre-release), 524 bytes

def o(A,C=[5]*3,L=[],E=enumerate):d=A.split('\n');Q=A.count;l,c,r=C;return len(L)==Q('|')+Q('_')or any(r<5and[(T:=(Y:=[int(g)-1for g in str(U)])[:4]*all(len(d)>l+u>-1<c+v<len(d[0])!='|_ '[w]==d[l+u][c+v]for u,v,w in zip(Y[4::3],Y[5::3],Y[6::3])))and r==T[0]and(O:=[l+T[1],c+T[2]])not in L and o(A,O+T[3:],L+[O])for U in[3111,3213211,3124122,3102102,1113,1011011,1024013022,1002013002,4112,4124122,4121121,4223123221,2114,2102102,2101101,2203103201]]or[o(A,[i,j,e+(c<'|')])for i,l in E(d)for j,c in E(l)for e in[0,2]if' '<c])

Try it online!

Input must be rectangular.

What a mess. The ungolfed version (with long variable names) was a nice 2700 bytes (or so), but I have golfed it down so much that it's down to 524.

Brute-force method. We try to start at every point: for every character that is either a pipe or an underscore, we determine whether:

  • it is possible to start at the top of that character if it is a pipe, or the left if it is an underscore, and follow the path of the art (recursively calling the function to move forward, and if there are two or more directions possible, try all of them) until all lines are used up and no line is used more than once; or
  • the same is possible with the bottom if pipe, or right if underscore.

When trying to move forward, we store all possible connections according to which character we are currently at and which side of that character we are at, and we use all the connections that are not yet used. If there are none, then it is not possible to draw in one stroke.

\$\endgroup\$
6
  • \$\begingroup\$ wth this is so much golfed \$\endgroup\$
    – mathcat
    Mar 19 at 17:49
  • \$\begingroup\$ @mathcat Is that a compliment or sarcasm? I can't tell. \$\endgroup\$
    – ophact
    Mar 19 at 18:00
  • 1
    \$\begingroup\$ @ophatct oh sorry, it was meant as a compliment, good job! \$\endgroup\$
    – mathcat
    Mar 20 at 9:44
  • \$\begingroup\$ @mathcat Thanks then! ;) \$\endgroup\$
    – ophact
    Mar 20 at 9:47
  • \$\begingroup\$ @mathcat And by the way... that ungolfed code had a lot of whitespace. \$\endgroup\$
    – ophact
    Mar 20 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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