28
\$\begingroup\$

Sandboxed

Given a set of closed non-overlapping 2d contours (separated by at least one space even on diagonals) with arrows oriented consistently in the same clockwise or counter-clockwise direction (each contour has its own direction) and a positive number n, move the arrows n steps along the contours in the respective direction. The arrows are represented by > v < ^ respectively for right, down, left and up directions. There the other characters are - (horizontal), | (vertical) and + (corner). When an arrow is on a corner, it keeps its current direction and changes it only after the turn is taken.

There will always be a straight segment (or a space) between any two corners (like +-+ for the horizontal and similar for the vertical) - in other words the sharp U turns are forbidden. The segments between the corners are either vertical or horizontal and the bend at a corner is always 90 degree.

Input:

  • a positive integer - n - number of steps
  • an ASCII representation of the contours - it can be a multiline string, a list of strings, a list of characters and so on.

Output:

The same contours with all arrows shifted n steps in each contour's overall direction.

Test cases:

1.

Input:

n = 1

 +----->->            
 |       |            
 |       v---+        
 |           |        
 +---<-------+      

Output:

 +------>+
 |       v
 |       +>--+
 |           |
 +--<--------+

2.

Input:

n = 2

 +-----+ +---+        
 |     | |   |        
 +-->--+ |   v  
         |   | 
 +--->---+   |        
 |           |         
 +------<<---+       

Output:

 +-----+ +---+
 |     | |   |
 +---->+ |   |
         |   | 
 +----->-+   v
 |           |     
 +----<<-----+        

3.

Input:

n = 3

 +---+   +---+   +-------+      
 |   |   |   v   |       |      
 ^   |   |   |   +-<-+   |      
 |   |   ^   |       |   v      
 |   +---+   +-->----+   |      
 |                       |      
 |   +-------+   +---+   |      
 |   |       |   v   |   |      
 +---+       +---+   +---+      

Output:

 +>--+   ^---+   +-------+
 |   |   |   |   ^       |
 |   |   |   |   +---+   |
 |   |   |   |       |   |
 |   +---+   v----->-+   |
 |                       |
 |   +-------+   +---+   v 
 |   |       |   |   |   |
 +---+       +-<-+   +---+  

4.

Input:

n = 1

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

Output:

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

5.

Input

n = 4

^>>>>
^   v
^   v>>>>
^       v           
<<<<<<<<v

Output:

^>>>>
^   v
^   v>>>>
^       v           
<<<<<<<<v

6.

Input:

n = 1

^->
^ v
<<v

Output:

^>+
^ v
<<v

Write a function or a program solving the above task. The shortest code in bytes in every language wins. Don't be discouraged by the golfing languages. Explanation of the algorithm and the code is highly appreciated.

\$\endgroup\$
  • \$\begingroup\$ Can two contours touch their corners on a diagonal, or a contour touch itself like that? \$\endgroup\$ – xnor Jul 31 at 6:57
  • 4
    \$\begingroup\$ "Given a set of closed non-overlapping 2d contours ... with arrows oriented consistently in the same clockwise or counter-clockwise direction" sounds to me like every contour is oriented in the same direction, whereas from the test cases, it seems the arrows only have be consistent within a contour. \$\endgroup\$ – xnor Jul 31 at 7:00
  • 3
    \$\begingroup\$ @xnor Thanks for your comments! - No, contours are not allowed to touch each other/itself on a diagonal. - Each contour has its own directon. I'll update the description. \$\endgroup\$ – Galen Ivanov Jul 31 at 7:11
  • 2
    \$\begingroup\$ Is input with no space between the walls possible? Eg: Try it online!. I know you said "separated by at least one space" but I was unclear if that applied only to independent loops or if it applied to a single loop as well. \$\endgroup\$ – Jonah Aug 1 at 0:21
  • 1
    \$\begingroup\$ @Jonah No, it's not possible: There will always be a straight segment (or a space) between any two corners (like +-+ for the horizontal and similar for the vertical) - in other words the sharp U turns are forbidden. \$\endgroup\$ – Galen Ivanov Aug 1 at 6:19
14
\$\begingroup\$

JavaScript (ES6),  210 ... 182  180 bytes

Takes input as (m)(n), where \$m\$ is a list of lists of characters. Returns the result in the same format.

m=>g=n=>n?g(n-1,m=m.map((r,y)=>r.map((c,x)=>(i=0,h=$=>~$?(m[Y=y+($-2)%2]||0)[X=x+~-$%2]>h?"-|+"[n+=`;m[${Y}][${X}]=S[${$}]`,i?2:$&1]:h($^++i):c)((S="<^>v").indexOf(c)))),eval(n)):m

Try it online!

How?

You can follow this link to see a formatted version of the source.

Wrapper

The recursive function \$g\$ is just used as a wrapper that invokes the main code to move all arrows by 1 step and keeps calling itself with \$n-1\$ until \$n=0\$.

Update method

We can't safely move each arrow one at a time because we would run the risk of overwriting non-updated arrows with updated ones. Instead, we first remove all arrows and compute their new positions. We apply the new positions in a second time.

This is done by re-using \$n\$ as a string to store the position updates as JS code.

For instance, in the first test case, \$n\$ is set to:

"1;m[0][7]=S[2];m[1][8]=S[3];m[2][9]=S[2];m[4][3]=S[0]"

(Note that the leading number -- which is the original value of \$n\$ -- is harmless.)

The new positions are applied by just doing eval(n).

Directions

Each arrow is converted into a direction \$d\$ (named $ in the code), using the following compass:

$$\begin{matrix} &1\\ 0&+&2\\ &3 \end{matrix}$$

The corresponding values of \$dx\$ and \$dy\$ are computed this way:

 d | dx = (d - 1) % 2 | dy = (d - 2) % 2
---+------------------+------------------
 0 |        -1        |         0
 1 |         0        |        -1
 2 |        +1        |         0
 3 |         0        |        +1

Corners

If the next character in the identified direction is a space or is out of bounds, it means that we're located on a corner and we need to take a 90° or 270° turn. This is why the helper function \$h\$ is testing up to 3 distinct directions: \$d\$, \$d\operatorname{xor}1\$ and \$d\operatorname{xor}3\$.

If we're located on a corner, we overwrite the cell with +. Otherwise, we overwrite it with either - or |, depending on the parity of \$d\$.

Note: The parameter of \$h\$ is not named $ just because it looks uber l33t but also because it allows us to compare a given character with \$h\$ (implicitly coerced to a string) to know if it's a space (below "$"), a contour character (above "$") or another arrow (also above "$").

Animated version

f=
m=>g=n=>n?g(n-1,m=m.map((r,y)=>r.map((c,x)=>(i=0,h=$=>~$?(m[Y=y+($-2)%2]||0)[X=x+~-$%2]>h?"-|+"[n+=`;m[${Y}][${X}]=S[${$}]`,i?2:$&1]:h($^++i):c)((S="<^>v").indexOf(c)))),eval(n)):m

m = [
  [..."+---+   +---+   +-------+"],
  [..."|   |   |   v   |       |"],
  [..."^   |   |   |   +-<-+   |"],
  [..."|   |   ^   |       |   v"],
  [..."|   +---+   +-->----+   |"],
  [..."|                       |"],
  [..."|   +-------+   +---+   |"],
  [..."|   |       |   v   |   |"],
  [..."+---+       +---+   +---+"]
];

(F = _ => (o.innerHTML = m.map(r => r.join('')).join('\n'), m = f(m)(1), window.setTimeout(F, 100)))()
<pre id=o></pre>

\$\endgroup\$
  • \$\begingroup\$ Thank you for the explanation! \$\endgroup\$ – Galen Ivanov Aug 1 at 6:20
8
\$\begingroup\$

K (ngn/k), 183 161 157 bytes

{A:"^>v<";D,:-D:(-1 0;!2);s:(#x;#*x);c:~^x;r:" -+|"c*+/'3'0,c,0;$[#p:+s\&~^t:A?,/x;;:r];q:q@'*'&'~^x ./:/:q:+p+/:D@4!(t^0N)+/:0 1 3;s#@[,/r;s/+q;:;A@D?q-p]}/

Try it online!

{ }/ when called with an int left arg n, this will apply the function in { } n times to the right arg

A:"^>v<" arrows

D,:-D:(-1 0;!2) ∆y,∆x for the 4 cardinal directions

s:(#x;#*x) shape of the input: height,width

c:~^x countours - boolean matrix showing where the non-spaces are

r:" -+|"c*+/'3'0,c,0 recreate the character matrix with a countour but without arrows, by counting self+upper+lower for each cell in c and replacing 1->-, 2->+, 3->|

t:A?,/x types of arrows: 0 1 2 3 for ^>v<, all other cells are represented as 0N (null)

p:+s\&~^t coordinates of the arrows

$[#p ;;:r] if there aren't any arrows, return r

q:+p+/:D@4!(t^0N)+/:0 1 3 all 3 possible new positions for each arrow - if it keeps going forward, if it turns left, and if it turns right

q:q@'*'&'~^x ./:/:q for each arrow choose the first option that lands on the countour

@[,/r;s/+q;:;A@D?q-p] flatten r and put on it the arrows at their new positions and with their new directions

s# reshape to the original shape

\$\endgroup\$
  • 2
    \$\begingroup\$ You are fast! I hope you'll explain the code after finish golfing it. \$\endgroup\$ – Galen Ivanov Jul 31 at 7:50
  • \$\begingroup\$ Thank you for the explanation! \$\endgroup\$ – Galen Ivanov Jul 31 at 12:24
4
\$\begingroup\$

Charcoal, 105 bytes

W¬ΦυΣκ⊞υS≔⊟υη≔⪫υ⸿θ≔⟦⟧υ≔>^<vζPθFθ¿№ζι«⊞υ⟦⌕ζιⅉⅈ⟧§+|-↨EKV›κ ²»ιFυ«J⊟ι⊟ι≔⊟ιιFIη«≔⊟Φ⁴∧﹪⁻⊖ι⊕λ⁴›§KV⁻⁵λ ιM✳⊗黧ζι

Try it online! Link is to verbose version of code. Includes 22 bytes used to avoid requiring a cumbersome input format. Explanation:

W¬ΦυΣκ⊞υS≔⊟υη≔⪫υ⸿θ≔⟦⟧υ

Conveniently input the contours and the number of steps.

≔>^<vζ

The direction characters are used several times so the string is cached here. The index of a direction character in this string is known as its direction.

Pθ

Print the original contours without moving the cursor.

Fθ

Loop over the characters in the contour.

¿№ζι«

If the current characters is a direction character...

⊞υ⟦⌕ζιⅉⅈ⟧

... then save the direction and position in a list...

§+|-↨EKV›κ ²

... and replace the character with the appropriate line character.

»ι

Otherwise output the character and move on to the next character.

Fυ«

Loop over the saved positions.

J⊟ι⊟ι

Jump to the saved position.

≔⊟ιι

Extract the saved direction.

FIη«

Loop over the appropriate number of steps.

≔⊟Φ⁴∧﹪⁻⊖ι⊕λ⁴›§KV⁻⁵λ ι

Find the direction of the next step, which is any direction that is neither reverse nor empty.

M✳⊗ι

Take a step in that direction. (Charcoal direction indices for the Move command are twice the value of my direction.)

»§ζι

Print the appropriate direction character.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the explanation! \$\endgroup\$ – Galen Ivanov Aug 1 at 6:20
2
\$\begingroup\$

APL (Dyalog Unicode), 111 bytesSBCS

{A[D⍳q-p]@q⊢' |+-'[c×3+/0,c,0]⊣q←⊃¨(⍸c←' '≠⍵)∘∩¨↓⍉D[4|0 1 3∘.+4~⍨,t]+⍤1⊢p←⍸4>t←⍵⍳⍨A←'v>^<'⊣D←9 11∘○¨0j1*⍳4}⍣⎕⊢⎕

Try it online!

similar to my k answer

\$\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.