Measure the Diamond Road

Question

Background

You are planning your trip away from the Diamond City, and must travel through Diamond Road. However, Diamond Road branches away from Diamond City to different locations.

Out of curiosity, you'd like to measure the total distance of unique roads used for all paths.

We define a path as a string that only contains / or \, which represent roads. You will be given a list of paths that can be traversed.

Starting from a central left most point, a path can be plotted on a map such that every / denotes a path upwards and every \ denotes a path downwards. On every path, each road must strictly go from left to right.

Subsequent roads must be joined at the same level as the previous road if they are different types. If they are the same type, the level will change.

For example:

Given //\\/\\\

The map generated would be:

              /\
Start here _ /  \/\
                   \
                    \

Since you can have multiple paths, these paths may cross and share the same road.

For example:

Given /\ /\/

The map generated would be:

Start here _ /\/

Here, the first two roads in both paths are shared, but the total length of roads used would be 3, as shown on the map.

You must calculate the amount of unique roads used in all paths.

Your Task

• Sample Input: A list of paths used, or a string of paths separated by spaces.

• Output: Return the total length of roads used.

Explained Examples

Input => Output

/ \ / \ => 2


Map:

Start here _ /
             \

Of the roads used, the total distance is 2.

Input => Output

/\/ \/\ /// => 8


Map:
               /
              /
Start here _ /\/
             \/\

Of the roads used, the total distance is 8.

Input => Output

//// \/\/ /\/\ //\\ => 12


Map:
                /
               /
              /\
Start here _ /\/\
             \/\/

Of the roads used, the total distance is 12.

Input => Output

/\//\//\/ \/\/\\//\ \//\/\/\/ \//\//\// /\/\/\/ \/ \\\ \//\/ \ => 28


Map:
                
                   /\/
                /\/\/
Start here _ /\/\/\/\/
             \/\/\  /\
              \   \/
               \

Of the roads used, the total distance is 28.

Test Cases

Input => Output
/ \ / \ => 2
/\/ \/\ /// => 8
//// \/\/ /\/\ //\\ => 12
/\//\//\/ \/\/\\//\ \//\/\/\/ \//\//\// /\/\/\/ \/ \\\ \//\/ \ => 28

\ => 1
/ => 1
\ \/\ => 3
/\ \/\/\/ => 8
/\ / \/\ \ => 5
//////////////////// => 20
////////// ////////// => 10
////////// \\\\\\\\\\ => 20
\ /\ \/ /\ \\\\\\\\\\ => 13
\/\ /\/ //\ \\/ \/ /\ / \ => 10
/\ /\/ /\/\ /\/\/ /\/\/\ /\/\/\/\ => 8
/\ \/ /\ /\ \/ /\ /\ \/ \/ \/ /\ /\ => 4
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ / => 2

This is code-golf, so shortest answer wins.

ps. I need help with tagging this question

Answer 1

Python, 59 bytes

lambda L,*i:len({i:=(*sorted(i),d)*(d>" ")for d in L}-{()})

Attempt This Online!

Takes inputs as in the test cases, i.e. a single space separated string.

How?

Encodes unique path elements by their left end and their direction.

Answer 2

Nekomata + -n, 7 bytes

~pᵉloÐũ

Attempt This Online!

A port of @Albert.Lang's Python answer.

~pᵉloÐũ
~           Choose any item from the input
 p          Choose a prefix
  ᵉ  Ð      A pair of
   l            Last item of the prefix and
    o           The prefix sorted
      ũ     Remove duplicate results

---

Nekomata + -n, 11 bytes

~e:∫xᵈÐcŤ~ũ

Attempt This Online!

-2 bytes thanks to @Kevin Cruijssen.

~e:∫xᵈÐcŤ~ũ
~               Choose any item from the input
                    Each item represents a path
 e              Character code
                    So / and \ are represented by two different numbers
  :             Duplicate
                    The first copy represents the directions of the roads
   ∫            Cumsum
                    These are the y coordinates of the end points
    x           Range from 0 to length - 1 (without popping)
                    These are the x coordinates of the end points
     ᵈÐc        Group the above three results into a list
        Ť       Transpose
         ~      Choose any of the (x, y, direction) triples
          ũ     Remove duplicate results

-n counts the number of results.

Answer 3

JavaScript (Node.js), 61 bytes

s=>s.map(c=>x/=1/c?x:c<{_:s[x+c]=s[x+c]||++n}?2:5,x=1,n=0)&&n

Try it online!

-2B from Arnauld

JavaScript (ES12), 55 bytes

s=>s.map(c=>x/=1/c?x:c<{_:s[x+c]||=++n}?2:5,x=1,n=0)&&n

Attempt This Online!

Answer 4

Excel (ms365), 251 bytes

Not short perse, but I tried to make it so that one could freely add more values to column A:

Formula in B1:

=LET(x,TOCOL(A:A,1),s,SEQUENCE(MAX(LEN(x))),r,REDUCE(EXPAND(0,ROWS(x),,0),s,LAMBDA(y,z,HSTACK(y,TAKE(y,,-1)+SWITCH(MID(x,z,1),"/",1,"\",-1,"")))),REDUCE(0,s,LAMBDA(y,z,LET(c,CHOOSECOLS(r,z+{0,1}),y+ROWS(UNIQUE(FILTER(c,MMULT(--ISERR(c),{1;1})=0)))))))

There is probably still a considerable amount of bytes to be saved.

My idea was:

• Start with an array of zero's based on the amount of rows in input;
• Iterate as much as the longest input;
• During step 2 we add 1 if character equals '/', -1 if character is '/' or we add an empty string (results in error);
• If this 2d-array is completed we can iterate each pair of columns (thus: 1 & 2, 2 & 3 etc.) to count the unique rows if no error exists;
• Do this for all pairs and we get the total amount of distance travelled.

Answer 5

05AB1E, 16 14 13 bytes

εÇDηOā)ø}€`Ùg

Input as a list of strings.

Port of @alephalpha's Nekomata's answer, so make sure to that answer as well!
-2 bytes thanks to @alephalpha

Try it online or verify all test cases.

Explanation:

ε        # Map over each string of the (implicit) input-list:
 Ç       #  Convert the string to a list of codepoint integers (47 if /; 92 if \)
  D      #  Duplicate this list of 1s and -1s
   η     #  Get the prefixes of the copy
    O    #  Sum each prefix together
     ā   #  Push a list in the range [1,length] (without popping the list)
      )  #  Wrap all three lists on the stack into a list
       ø #  Zip/transpose; swapping rows/columns, to create a list of triplets
}€`      # After the map: flatten the list of lists of triplets one level down
   Ù     # Uniquify this list of triplets
    g    # Pop and push its length
         # (which is output implicitly as result)

Answer 6

Pyth, 11 bytes

l{sm.e,bS<d

Try it online!

Uses the idea that each unique road can be identified by its angle and starting position. Given any prefix of any input element this corresponds to looking at the last character and a "path key" which is the path up to that character sorted.

Explanation

l{sm.e,bS<dkdQ    # implicitly add kdQ
                  # implicitly assign Q = eval(input())
   m         Q    # map Q over lambda d
    .e      d     #   enumerated map d over lambda b, k
      ,           #     2 element list:
       b          #     value  (last char)
        S<dk      #     sorted(d[:k])  (path key)
  s               # flatten nested list
 {                # deduplicate
l                 # get the length

Answer 7

J, 20 bytes

[:#@~.@;(/:~,{:)\&.>

Try it online!

This is mostly a port of Albert Lang's excellent approach, with one twist:

• Instead of sorting the prefix and appending the last element, we can sort everything (including the last elm) and append the last element.
• This allows for the golfier (/:~,{:) to replace (/:~@}:,{:).

Answer 8

Retina 0.8.2, 24 bytes

.
$%`$&¶
%O`.(?=.)
D`
.+

Try it online! Takes input on separate lines but link is to test suite which accepts a list of space-separated examples for convenience. Explanation:

.
$%`$&¶

Get all of the prefixes of all of the roads.

%O`.(?=.)
D`

Remove prefixes that have the same number of each type of road, excluding the last road.

.+

Count the total unique distance.

Answer 9

JavaScript (ES12), 52 bytes

My initial answer was buggy. This fixed version takes inspiration from @l4m2 and @Albert.Lang (although the relationship with the latter one is not obvious anymore).

Expects a list of characters.

a=>a.map(c=>1/c?s=1:a[c+=s*=2^c>{}]||=++n,s=1,n=0)|n

Attempt This Online!

Commented

a =>             // a[] = input array
a.map(c =>       // for each character c in a[]:
  1 / c ?        //   if c is a space:
    s = 1        //     reset s to 1
  :              //   else:
    a[           //
      c +=       //     build a lookup key by appending to c:
        s *=     //       the updated 'signature' s of the path:
          2 ^    //         obtained by multiplying by 2 if c = '/'
          c > {} //         or by 3 if c = '\'
    ] ||= ++n,   //     increment n if this key was not yet encountered
  s = 1,         //   start with s = 1
  n = 0          //   start with n = 0
) | n            // end of map(); return n

Answer 10

Charcoal, 25 bytes

ＷＳ«Ｊ⁰¦⁰Ｆι≡κ/↗¹¶\»≔ＬＫＡθ⎚Ｉθ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

ＷＳ«

Loop over the roads.

Ｊ⁰¦⁰

Start each road at Diamond City.

Ｆι

Loop over each road segment.

≡κ/

If it's a /, then...

↗¹

... draw a / and move up left, otherwise...

¶\

... move down and draw a \.

»≔ＬＫＡθ

Get the count of cells covered.

⎚Ｉθ

Clear the canvas and output the count.

The first 16 bytes suffice to output the map itself:

ＷＳ«Ｊ⁰¦⁰Ｆι≡κ/↗¹¶\

Try it online! Link is to verbose version of code.

Answer 11

C (gcc), 99 bytes

f(char*p){int a[4096]={},n=0,s=0,c;while(c=*p++)~c&4?s=0:a[s+=1<<(c&=1)*6]&++c||(a[s]|=c,n++);p=n;}

Try it online!

it will collide when the strings have >= (2^6 = 64) of either direction. increase the 6 (+1) and 4096 (*4) to make it even better, to a theoretical maximum of 16 and 4294967296 (16 GiB of RAM, max 65535 of either direction). on TIO it only works up to 10 and 1048576 (4 MiB of RAM, max 1023).