16
\$\begingroup\$

The Challenge

Create a function that, when given an input of ASCII art (directing a path that may eventually loop), outputs the length of the loop (if there is one) and the length of the "tail" leading into the loop in one of the forms below.


Input

Your input must be passed to a function. Below is an example of a simple input.

# --> # --> #
      ^     |
      |     |
      |     v
      # <-- #

You could visualize the above blocks like this

The "tail" is one item, while the loop is four long.

A more difficult one:

            # --> # --> #
            ^           |
            |           |
            |           v
      # --> # <-- #     # --> #
      ^           ^           |
      |           |           |
      |           |           v
# --> #           # <-- # <-- #

Output

You must output through STDOUT or your language's closest alternative.

Your two output integers should be the length of the tail and the length of the loop. This output can be in two forms.

  1. a space-delimited string: "2 10"
  2. an array of integers: [2, 10]

Rules

  • Every block, or #, will only have a single path away from itself.

  • Every arrow is two line segments and one head.

  • The starting block will always be in the leftmost column.

  • The input will never be just a loop.


Example

# --> # --> # --> #
^     ^           |
|     |           |
|     |           v
#     # <-- # <-- #

This one has a tail length of 2 and a loop length of 6. Below, the tail and loop are separated.

Tail

# -->
^
|
|
#

Loop

# --> # --> #
^           |
|           |
|           v
# <-- # <-- #

The correct outputs are [2, 6] and "2 6".

If the input is only a tail, the loop length is zero.

# --> # --> # --> #
                  |
                  |
                  v
        <-- # <-- #

The correct outputs for the above input are [6, 0] and "6 0"

\$\endgroup\$
  • \$\begingroup\$ @orlp I think you're confusing input and output. \$\endgroup\$ – Sanchises Sep 17 '15 at 20:59
  • 1
    \$\begingroup\$ Can the input have extra disconnected pieces of path? \$\endgroup\$ – xnor Sep 17 '15 at 21:00
  • \$\begingroup\$ I think the intro is confusing. It makes me think the problem will be about program analysis, whereas it is about path-finding in ASCII art. \$\endgroup\$ – xnor Sep 17 '15 at 21:01
  • \$\begingroup\$ I've removed the intro. It was a bit confusing/misleading. @xnor \$\endgroup\$ – Zach Gates Sep 17 '15 at 21:03
  • 3
    \$\begingroup\$ Related: Where is the arrow pointing? \$\endgroup\$ – mınxomaτ Sep 17 '15 at 21:12
11
+50
\$\begingroup\$

JavaScript (ES6), 221 229

A function with the input as a parameter, output as a string via popup window (alert).

Scan repeatedly the input:
at each step

  • remove the end of the tail
  • count the remaining '#'

When there is not more tail to remove, the number of the steps so far is the size of the tail and the number of remaining '# is the size of the loop.

All the newlines inside backticks are significant and counted

Test running the snippet below with Firefox (not Chrome, as it does not support ...)

F=s=>{s=`


${s}


`.split`
`.map(r=>[...r]);for(t=0,f=1;f;)s.map((r,y)=>r.map((c,x)=>c=='#'&&((r[x+2]+r[x-2]+s[y-1][x]+s[y+1][x]).match`[v<>^]`?++l:t+=(f=r[x-4]=r[x+4]=s[y-3][x]=s[y+3][x]=r[x]=1))),f=l=0);alert(t+' '+l)}

// Less golfed
U=s=>{
  s=`\n\n\n${s}\n\n\n`.split`\n`.map(r=>[...r])
  t=0
  do {
    f=l=0
    s.forEach((r,y) => {
      r.forEach((c,x) => {
        if (c == '#')
        {
          if (!(r[x+2] == '<' || r[x-2] == '>' || s[y-1][x] == 'v' || s[y+1][x] == '^'))
            t+=(f=r[x-4]=r[x+4]=s[y-3][x]=s[y+3][x]=r[x]=1)
          else
            ++l
        }
      })
    })
  } while(f)
  alert(t+' '+l)
}  

//Test

// Redefine console.log
alert=(...x)=>O.innerHTML+=x+'\n'

test=[`
# --> # --> #
      ^     |
      |     |
      |     v
      # <-- #`
,`
            # --> # --> #
            ^           |
            |           |
            |           v
      # --> # <-- #     # --> #
      ^           ^           |
      |           |           |
      |           |           v
# --> #           # <-- # <-- #`
,`
# --> # --> # --> #
^     ^           |
|     |           |
|     |           v
#     # <-- # <-- #`      
]

test.forEach(t=>(alert(t),F(t)))
<pre id=O></pre>

\$\endgroup\$
  • \$\begingroup\$ ... is the spread operator right? You might want to name it this way since it exists in other languages (like groovy) by other syntaxes (*:list for groovy). Nice solution anyway ! \$\endgroup\$ – Aaron Sep 18 '15 at 12:31
  • 1
    \$\begingroup\$ +1 I was thinking 'There must be a smart way to do this', came up with this solution, only to scroll down to this answer. \$\endgroup\$ – Sanchises Sep 28 '15 at 9:23
8
\$\begingroup\$

Ruby, 287 278 bytes

->i{n={}
g=->x{n[x]||=[0,p]}
t=y=0
i.lines{|l|x=0
l.chars{|c|x+=1
'><'[c]&&(r=c.ord-61;s,d=[y,x-4*r],[y,x+2*r])
'^v'[c]&&(r=c<?_?1:-1;s,d=[y+r*3,x],[y-r,x])
s&&(g[s][1]=g[d])[0]+=1}
y+=1}
c,*_,s=n.values.sort_by{|v|v[0]}
l=n.size
s[0]>1?((t+=1;c=c[1])while c!=s):t=l-=1
[t,l-t]}

Try it here.

This builds a hash (dictionary) of nodes. For each node, the number of incoming connections and the (possibly null) next node are stored.

Finally:

  • If there is no node with 2 incoming connections (meaning no loop), return 0 for the tail and the number of existing nodes for the loop.
  • Otherwise, start iterating from the node with 0 incoming connections (start) via next->...->next until the node with 2 incoming connections (loop start) is reached. Return the appropriate counts.

The readable version of the code is available here.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 276

->s{a=k=w=s.index(r='
')*2+2
s=r*w+s+r*w
(s.size).times{|i|s[i,2]=='
#'&&(s[3+j=i+1]+s[j+w]+s[j-w]).strip.size<2&&(a=[j]
d=0
loop{("|-|-"[d])+?#=~/#{s[k=j+[-w,3,w,-3][d]]}/?(a.include?(k)&&break;a<<(j=k);d-=1):d=(d+1)%4}
)}
u=a.size
v=a.index(k)
t=(u-v)/4*2
print u/2-t," ",t}
\$\endgroup\$

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.