13
\$\begingroup\$

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 , so shortest answer wins.

ps. I need help with tagging this question

\$\endgroup\$
9
  • 5
    \$\begingroup\$ Why is the answer to the second last test case 2 and not 4? \$\endgroup\$ Jul 10 at 7:54
  • 1
    \$\begingroup\$ @Arnauld Mine returns 28 and I tested it manually it's 28 \$\endgroup\$
    – l4m2
    Jul 10 at 8:30
  • 4
    \$\begingroup\$ It took some staring for me to figure out that paths travel from left to right, and a path is made of diagonally-oriented roads laid end to end with the right end of each road connecting to the left end of the next road. Each path is drawn from the same starting point, and overlapping roads can be shared between paths. I'd also suggest using "total length" instead of "distance" for the output, since distance reads to me like it's about how far away you end up. \$\endgroup\$
    – xnor
    Jul 10 at 9:00
  • \$\begingroup\$ @l4m2 My bad. The starting position in my answer was off by 1, and that's the only test case where this is an issue. \$\endgroup\$
    – Arnauld
    Jul 10 at 9:29
  • \$\begingroup\$ Hey - sorry. Changed the wording and fixed the second to last test case, which does give 4 and the 4th, which gives 30. Please send any more corrections. \$\endgroup\$ Jul 10 at 10:27

11 Answers 11

11
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Can you subtract 1 rather than removing empty? \$\endgroup\$
    – l4m2
    Jul 10 at 16:32
  • 1
    \$\begingroup\$ @l4m2 empty is only added at the reset between individual input chains (when a space is encountered). When there is only one input chain it doesn't happen, so subtracting 1 would break those cases. \$\endgroup\$ Jul 10 at 20:11
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ 63 bytes, or 57 bytes with ||=. \$\endgroup\$
    – Arnauld
    Jul 10 at 8:54
  • \$\begingroup\$ -1 byte for the 1st version. \$\endgroup\$
    – Arnauld
    Jul 10 at 12:58
  • \$\begingroup\$ Could you actually do 2^c<{...} instead of c<{...}?2:5? \$\endgroup\$
    – Arnauld
    Jul 10 at 14:19
  • \$\begingroup\$ @Arnauld I asked on meta but no response \$\endgroup\$
    – l4m2
    Jul 10 at 16:29
6
\$\begingroup\$

Excel (ms365), 251 bytes

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

enter image description here

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.
\$\endgroup\$
2
  • 3
    \$\begingroup\$ "per se" is Latin for "in itself". "perse" is Finnish for "ass" \$\endgroup\$
    – JollyJoker
    Jul 10 at 17:55
  • \$\begingroup\$ And I made it Dutch \$\endgroup\$
    – JvdV
    Jul 10 at 18:26
5
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ You don't need ·<. The directions can be represented by 1 and 0 as well. \$\endgroup\$
    – alephalpha
    Jul 10 at 11:06
  • 1
    \$\begingroup\$ @alephalpha I think I don't need the È either in that case. (And I think you can golf the £E in your answer as well?) \$\endgroup\$ Jul 10 at 11:43
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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 (/:~@}:,{:).
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Seems like ATO is down. Here is a 56-byte ES6 version. \$\endgroup\$
    – Arnauld
    Jul 10 at 14:58
1
\$\begingroup\$

Charcoal, 25 bytes

WS«J⁰¦⁰Fι≡κ/↗¹¶\»≔LKAθ⎚Iθ

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

WS«

Loop over the roads.

J⁰¦⁰

Start each road at Diamond City.

Fι

Loop over each road segment.

≡κ/

If it's a /, then...

↗¹

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

¶\

... move down and draw a \.

»≔LKAθ

Get the count of cells covered.

⎚Iθ

Clear the canvas and output the count.

The first 16 bytes suffice to output the map itself:

WS«J⁰¦⁰Fι≡κ/↗¹¶\

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

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

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).

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Fail long \$\endgroup\$
    – l4m2
    Jul 12 at 10:56
  • \$\begingroup\$ i was wondering if someone would point that out. it passes the test cases at least! but i can add a few more bytes :) \$\endgroup\$ Jul 12 at 12:24
  • \$\begingroup\$ turns out changing one character improved the hash function, but i'll look into it further. \$\endgroup\$ Jul 12 at 12:44
  • 1
    \$\begingroup\$ \\\/ ///(1st) \\/ //(2nd) \$\endgroup\$
    – l4m2
    Jul 12 at 15:37
  • \$\begingroup\$ ok fine i'll just delete those \$\endgroup\$ Jul 12 at 15:37

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.