9
\$\begingroup\$

(Note: this challenge is distinct from my other challenge (Draw a path made from direction changers) because of it's rendering of direction (horizontal or vertical), crossing points and single or double paths.)


Let's start with a frame drawn in Ascii characters. For this challenge it will always be 20 characters wide and 10 characters high.

+--------------------+
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
+--------------------+

It will begin populated with one of a number of objects:

| Name       | Char | Description                                    |
| Source     | *    | This will send a path to the North             |
| East       | >    | Any path meeting this will turn to the East    |
| West       | <    | Any path meeting this will turn to the West    |
| North      | ^    | Any path meeting this will turn to the North   |
| West       | V    | Any path meeting this will turn to the South   |

Your job will be to start with the objects above, and populate the grid with these characters, which will display the path they describe.

| Name                   | Char | Description                                                                   |
| Vertical path          | |    | The path is travelling North or South                                         |
| Horizontal path        | -    | The path is travelling East or West                                           | 
| Double Vertical path   | N    | The path is doubled and is travelling North or South                          |
| Double Horizontal path | =    | The path is doubled and is travelling East or West                            |
| Crossing point         | +    | A North/South path and an East/West path have met                             |
| Double crossing point  | #    | A North/South path and an East/West path have met and one or both are doubled |

Path drawing rules

When a path meets either the edge of the map or a source, it will stop there.

If a path meets a direction changer, they will go in it's direction, using the direction changer as a starting point, e.g.:

+--------------------+
|                    |
|                    |
|    >---------------|
|    |               |
|    |               |
|    |               |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

If a direction changer tells a path to go back the way it came, it will display a double path e.g.:

+--------------------+
|                    |
|                    |
|                    |
|    >====<          |
|    |               |
|    |               |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

If two paths cross, they will meet with a + symbol. E.g.:

+--------------------+
|        |           |
|        |           |
|        |           |
|    >---+-----------|
|    |   |           |
|    |   *           |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

If two paths cross, and one or both are doubled back, they will meet with a # symbol. E.g.:

+--------------------+
|        |           |
|        |           |
|        |           |
|    >===#===<       |
|    |   |           |
|    |   *           |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

If two paths meet the same direction changer from different directions, the ongoing path is merged (doubled up). E.g.:

+--------------------+
|         N          |
|         N          |
|       >-^-<        |
|       |   |        |
|       |   |        |
|       *   *        |
|                    |
|                    |
|                    |
|                    |
+--------------------+

Doubled paths are immutable, they can not be un-doubled or become any heavier than double paths.

The rules

  • It's code golf, try to write short code to do this.
  • Input and output are agnostic, I don't really mind about strings, arrays of chars, trailing and leading space etc. as long as I can see the outcome.
  • Standard loopholes etc.
  • Use any language you like.
  • Please include a link to an online interpreter.

Test cases

Simple

In:

+--------------------+
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|    *               |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|    |               |
|    |               |
|    |               |
|    |               |
|    |               |
|    |               |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

One turn

In:

+--------------------+
|                    |
|                    |
|    >               |
|                    |
|                    |
|                    |
|                    |
|    *               |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|                    |
|                    |
|    >---------------|
|    |               |
|    |               |
|    |               |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

Spiral

In:

+--------------------+
|                    |
|                    |
|                    |
|  <                 |
|                    |
|    >  V            |
|                    |
|    *               |
|  ^    <            |
|                    |
+--------------------+

Out:

+--------------------+
|                    |
|                    |
|                    |
|--<                 |
|  |                 |
|  | >--V            |
|  | |  |            |
|  | *  |            |
|  ^----<            |
|                    |
+--------------------+

Reflect

In:

+--------------------+
|                    |
|                    |
|                    |
|    >    <          |
|                    |
|                    |
|                    |
|    *               |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|                    |
|                    |
|                    |
|    >====<          |
|    |               |
|    |               |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

Two Sources

In:

+--------------------+
|                    |
|                    |
|                    |
|    >               |
|                    |
|        *           |
|                    |
|    *               |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|        |           |
|        |           |
|        |           |
|    >---+-----------|
|    |   |           |
|    |   *           |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

One Doubles Back

In:

+--------------------+
|                    |
|                    |
|                    |
|    >       <       |
|                    |
|        *           |
|                    |
|    *               |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|        |           |
|        |           |
|        |           |
|    >===#===<       |
|    |   |           |
|    |   *           |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

Path Meets Source

(Note that the path ends at the source, and does not join the other path and double up)

In:

+--------------------+
|                    |
|                    |
|                    |
|                    |
|                    |
|    >   *           |
|                    |
|    *               |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|        |           |
|        |           |
|        |           |
|        |           |
|        |           |
|    >---*           |
|    |               |
|    *               |
|                    |
|                    |
+--------------------+

Paths Merging

In:

+--------------------+
|                    |
|                    |
|       > ^ <        |
|                    |
|                    |
|       *   *        |
|                    |
|                    |
|                    |
|                    |
+--------------------+

Out:

+--------------------+
|         N          |
|         N          |
|       >-^-<        |
|       |   |        |
|       |   |        |
|       *   *        |
|                    |
|                    |
|                    |
|                    |
+--------------------+

Full Spiral

In:

+--------------------+
|     >        V     |
|      >      V      |
|       >    V       |
|        >  V        |
|         >V         |
|         *          |
|        ^ <         |
|       ^   <        |
|      ^     <       |
|     ^       <      |
+--------------------+

Out:

+--------------------+
|     >--------V     |
|     |>------V|     |
|     ||>----V||     |
|     |||>--V|||     |
|     ||||>V||||     |
|     ||||*|||||     |
|     |||^-<||||     |
|     ||^---<|||     |
|     |^-----<||     |
|     ^-------<|     |
+--------------------+

Let's Have Some Fun

In:

+--------------------+
|                    |
|                    |
|  V   V   V   V     |
|>                  <|
|^                  <|
|                  < |
|>                 ^ |
|                    |
|  * * * * * * * *   |
|*                  *|
+--------------------+

Out:

+--------------------+
|    |   |   |   |   |
|    |   |   |   |   |
|  V | V | V | V |   |
|>=#=#=#=#=#=#=#=#==<|
|^-#-+-#-+-#-+-#-+--<|
|--#-+-#-+-#-+-#-+-<||
|>-#-+-#-+-#-+-#-+-^||
|| N | N | N | N |  ||
|| * * * * * * * *  ||
|*                  *|
+--------------------+

Almost all cells visited twice

In:

+--------------------+
|>                  V|
| >                V |
|  >              V  |
|   >V>V>V>V>V>V>V   |
|                    |
|   *>^>^>^>^>^>^    |
|  ^             <   |
| ^               <  |
| V<V              < |
|^<^<^              <|
+--------------------+

Out:

+--------------------+
|>==================V|
|N>================VN|
|NN>==============VNN|
|NNN>V>V>V>V>V>V>VNNN|
|NNN||NNNNNNNNNNNNNNN|
|NNN*>^>^>^>^>^>^NNNN|
|NN^=#===========<NNN|
|N^==#============<NN|
|NV<V#=============<N|
|^<^<^==============<|
+--------------------+

Happy Golfing :)

\$\endgroup\$
  • 2
    \$\begingroup\$ Almost all squares visited twice. \$\endgroup\$ – Arnauld Dec 4 '19 at 14:25
  • \$\begingroup\$ @Arnauld Nice test case! Would you like to add it to the question? \$\endgroup\$ – AJFaraday Dec 5 '19 at 9:35
  • 1
    \$\begingroup\$ I've added @Arnauld's test case to the challenge. \$\endgroup\$ – Kevin Cruijssen Dec 6 '19 at 8:39
9
\$\begingroup\$

JavaScript (ES6),  201 197  195 bytes

Takes input as a matrix of characters. Outputs by modifying the input.

f=(m,X,Y,k,d)=>m.map((r,y)=>r.map((c,x)=>~(s=' -|=N+#^<V>',i=s.indexOf(c))?k&&x%21&&y%11?x-X-~-~-d%2|y-Y-~-d%2|k>>9||f(m,x,y,-~k,i>6?i-7:d,r[x]=s[(25464-11928*(d&1)+'6')[i]||i]):0:k||f(m,x,y,1)))

Try it online!

How?

Updating the matrix

We use the following lookup string \$s\$ to identify and write the characters from/into the matrix:

i =  0123456
s = ' -|=N+#^<V>'

NB: * is not included, so we have \$i=-1\$ in that case.

Characters with an index \$i\$ greater than \$6\$ are direction changers, which are immutable. For the other characters, we use two translation tables to update them according to the current direction.

For vertical moves:

' ' (0) + '|' = '|' (2)
'-' (1) + '|' = '+' (5)
'|' (2) + '|' = 'N' (4)
'=' (3) + '|' = '#' (6)
'N' (4) + '|' = 'N' (4)
'+' (5) + '|' = '#' (6)
'#' (6) + '|' = '#' (6)

And for horizontal moves:

' ' (0) + '-' = '-' (1)
'-' (1) + '-' = '=' (3)
'|' (2) + '-' = '+' (5)
'=' (3) + '-' = '=' (3)
'N' (4) + '-' = '#' (6)
'+' (5) + '-' = '#' (6)
'#' (6) + '-' = '#' (6)

Hence the character translation code:

r[x] = s[           // update r[x]:
  (                 //   build a lookup string:
    25464 -         //     use 25464 if d is even
    11928 * (d & 1) //     or 13536 if d is odd
    + '6'           //     coerce to a string and append a '6',
                    //     which gives '254646' and '135366' respectively
  )[i]              //   extract the i-th digit
  || i              //   or use i if it's undefined,
]                   //   which leaves the original character unchanged

Preventing an infinite loop

There is no explicit loop detection. Instead, we take advantage of the fixed size of the frame and simply stop the recursion when the number of moves from the source is greater than \$511\$ with:

k >> 9

This is enough to visit each cell twice (\$2\times20\times10=400\$). Beyond that, the board is guaranteed not to change anymore. We can get close to this with a configuration like this one.

Commented

f = (                          // f is a recursive function taking:
  m,                           //   m[] = input matrix
  X, Y,                        //   (X, Y) = current position
  k,                           //   k = number of moves from the source
  d                            //   d = current direction in [0..3]
) =>                           //       (counter-clockwise with 0 = North)
  m.map((r, y) =>              // for each row r[] at position y in m[]:
    r.map((c, x) =>            //   for each character c at position x in r[]:
      ~(                       //
        s = ' -|=N+#^<V>',     //     s = lookup string
        i = s.indexOf(c)       //     i = position of c in s
      ) ?                      //     if i is not equal to -1 (i.e. c is not '*'):
        k &&                   //       if this is not the first iteration
        x % 21 && y % 11 ?     //       and we're not located over a border:
          x - X - ~-~-d % 2 |  //         abort if x - X is not equal to dx
          y - Y - ~-d % 2 |    //         or y - Y is not equal to dy
          k >> 9 ||            //         or k is greater than 511
          f(                   //         otherwise, do a recursive call:
            m,                 //           pass m[] unchanged
            x, y,              //           pass the new position
            -~k,               //           increment k
            i > 6 ? i - 7 : d, //           update d to i - 7 if i > 6
            r[x] = …           //           update r[x] (see above)
          )                    //         end of recursive call
        :                      //       else:
          0                    //         do nothing
      :                        //     else (c = '*'):
        k ||                   //       unless this is not the first iteration,
        f(m, x, y, 1)          //       start a new path to the North
    )                          //   end of inner map()
  )                            // end of outer map()
\$\endgroup\$
2
\$\begingroup\$

Java 8, 275 bytes

m->{for(int r=11,c,R,C,k,d,v;--r>0;)for(c=21;--c>0;)if(m[R=r][C=c]==42)for(k=d=0;(v=m[R+=(d*2-1)%5%3][C+=d/2-d*2/5*2])!=42&R%11*(C%21)>0&k++<500;d=v==94?0:v==86?1:v==62?2:v==60?3:d)m[R][C]-=v==43?8:v==61&d<2?26:v==45?d<2?2:-16:v==78&d>1?43:v>99?d<2?46:81:v<33?d<2?-92:-13:0;}

Some inspiration taken from @Arnauld's JavaScript answer (mainly the strategy of looping a max of 400 instead of keeping track of which paths were visited (at least) twice).

Input as a character-matrix. Will modify the input instead of returning a new one to save bytes.

Try it online.

Explanation:

m->{                      // Method with char-matrix parameter and no return-type
  for(int r=11,c,         //  Current row/column indices of the outer loops
          R,C,            //  Current row/column indices of the inner loop
          k,              //  Counter of the current path
          d,              //  Direction (0=North; 1=South; 2=East; 3=West)
          v;              //  Current value
      --r>0;)             //  Loop `r` over the rows in the range (21,0):
    for(c=21;--c>0;)      //   Inner loop `c` over the columns in the range (11,0):
      if(m[R=r][C=c]==42) //    If the current cell contains a '*':
        for(k=d=0;        //     Reset `k` to 0, and the direction to North
            (v=m[R+=(d*2-1)%5%3] 
                          //     † Update the row `R`,
                [C+=d/2-d*2/5*2])
                          //     and the column `C`
                          //     Set `v` to the value at this new cell `R,C`
            !=42          //     Inner loop as long as this next value is not '*',
            &R%11*(C%21)>0//     nor are we on a border of the matrix,
            &k++<500      //     nor are we stuck in an infinite loop:
            ;d=           //       After every iteration: update direction `d`:
               v==94?     //        If the current cell contains '^':
                0         //         Update the direction to 0 (North)
               :v==86?    //        Else-if the current cell contains 'V':
                1         //         Update the direction to 1 (South)
               :v==62?    //        Else-if the current cell contains '>':
                2         //         Update the direction to 2 (East)
               :v==60?    //        Else-if the current cell contains '<':
                3         //         Update the direction to 3 (West)
               :          //        Else (any other character):
                d)        //         Keep the direction the same
                          //      †† Update the character at the current `R,C` cell
                          //      based on the current value and direction:
          m[R][C]-=v==43?8:v==61&d<2?26:v==45?d<2?2:-16:v==78&d>1?43:v>99?d<2?46:81:v<33?d<2?-92:-13:0;}

†: Go to the next coordinate:

I'm using the directions: North: \$0\$; South: \$1\$; East: \$2\$; West: \$3\$.

The coordinate changes we have to do are therefore:

direction d | new R,C coordinate
------------+-------------------
0 (North)   | R-1,C
1 (South)   | R+1,C
2 (East)    | R,C+1
3 (West)    | R,C-1

The straight-forward implementations would be these:

R+=d<1?-1:d<2?1:0
C+=d>2?-1:d>1?1:0

But they have been golfed to this (the / are integer-division):

R+=(d*2-1)%5%3 // maps to: 0→-1; 1→1; 2→0; 3→0
C+=d/2-d*2/5*2 // maps to: 0→0; 1→0; 2→1; 3→-1

†: Change the values:

We have to do the following mappings:

The characters *><^V# will always stay the same in the matrix (and we don't even have to check the * anyway, since we already stop the inner loop if we encounter another one).
That leaves us with the following mappings of the remaining characters, depending on the direction \$d\$:

current char (codepoint) | direction d | next char (codepoint)
---------------------------------------+----------------------
+ (43)                   | any         | # (35)
<space> (32)             | 0 or 1      | | (124)
<space> (32)             | 2 or 3      | - (45)
| (124)                  | 0 or 1      | N (78)
| (124)                  | 2 or 3      | + (43)
- (45)                   | 0 or 1      | + (43)
- (45)                   | 2 or 3      | = (61)
N (78)                   | 0 or 1      | N (78) - unchanged
N (78)                   | 2 or 3      | # (35)
= (61)                   | 0 or 1      | # (35)
= (61)                   | 2 or 3      | = (61) - unchanged

I'm currently using the following, although this can definitely be golfed with some magic number tricks:

m[R][C]-=  // Subtract from the codepoint of the current value:
 v==43?    //  If it contains a '+':
  8        //   Change it to '#' by subtracting 8
 :v==61    //  Else if it contains a '=',
 &d<2?     //  and the direction is vertical (north/south):
  26       //   Change it to '#' by subtracting 26
 :v==45?   //  Else-if it contains '-':
  d<2?     //   If the direction is vertical (north/south):
   2       //    Change it to '+' by subtracting 2
  :        //   Else (it's horizontal (east/west) instead):
   -16     //    Change it to '=' by adding 16
 :v==78    //  Else-if it contains a 'N',
 &d>1?     //  and the direction is horizontal (east/west):
  43       //   Change it to '#' by subtracting 43
 :v>99?    //  Else-if it contains a '|':
  d<2?     //   If the direction is horizontal (north/south):
   46      //    Change it to 'N' by subtracting 46
  :        //   Else (it's vertical (east/west) instead):
   81      //    Change it to '+' by subtracting 81
 :v<33?    //  Else-if it contains a ' ' (space):
  d<2?     //   If the direction is vertical (north/south):
   -92     //    Change it to '|' by adding 92
  :        //   Else (it's horizontal (east/west) instead):
   -13     //    Change it to '-' by adding 13
 :         //  Else (it's any other character):
  0;       //   Keep it the same by subtracting 0
\$\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.