11
\$\begingroup\$

Background

Most (halfway decent) text editors allow you to navigate text using the arrow keys. Up and down allow you to navigate lines, while left and right move across a line but also wrap around. Furthermore, if the line is shorter than your cursor's X position, the cursor appears at the end of the line but returns to the same X position if you keep moving up or down. Perhaps the following visual explanation will help:

Examples Of Motion

A simple sample of text could look like this. The cursor will be inserted between two characters in this text, or at an end.

-----
---
------

let's put the cursor here:

X-----
---
------

move down (v):

-----
X---
------

move left (<):

-----X
---
------

v

-----
---X
------

v (notice how the X position of the cursor has been maintained)

-----
---
-----X-

^

-----
---X
------

>  (more line wrapping)

-----
---
X------

<

-----
---X
------

^ (the X-position from earlier is no longer maintained due to the left-right motion)

---X--
---
------

The Challenge

Given several lines of ASCII test, find the shortest path from the start location to the end location. The start location is represented by ^ and the end location is represented by $, and there will only be one of each. These aren't considered part of the text and don't contribute to that line's "length."

The input will consist of several non-blank lines of text. Output will be a series of ^v<> characters that show one of the shortest paths. You may optionally assume an additional newline at the end of each, but that is not included as part of the navigable text.

You can write a program or named function. The winner will be the shortest submission, measured in bytes.

Example I/O

^Squares
are
fun$ny

vv<v  (which is better than the naive vv>>>)

Squares
^are
funny$

<vv

Alp$habet^
Song

v<^

Mary had a little lamb,
His fleece was white as snow,
And$ everywhere that ^Mary went,
The lamb was sure to go.

^^>>>>v>>>

$^degenerate case

(no output)
\$\endgroup\$
  • \$\begingroup\$ "The cursor will be inserted between two characters in this text, or at the end" -- proceeds to put the cursor at the beginning in the first example \$\endgroup\$ – aditsu Feb 9 '15 at 4:41
  • \$\begingroup\$ There are two ends of every line. Edited to "an end." \$\endgroup\$ – PhiNotPi Feb 9 '15 at 4:47
  • \$\begingroup\$ Vim allows arrows. I have a real vi on my AIX box that does not ( I have added map statements to my startup file). "halfway decent"... yep \$\endgroup\$ – Jerry Jeremiah Feb 9 '15 at 6:13
  • \$\begingroup\$ The first example's output could also be v<vv, right? Or would that end after the last character on that line? \$\endgroup\$ – mbomb007 Feb 11 '15 at 20:33
  • \$\begingroup\$ @mbomb007 It would end after the last character of the line. \$\endgroup\$ – PhiNotPi Feb 11 '15 at 21:11
7
\$\begingroup\$

CJam, 139 bytes

Well this took many hours to come to something that feels done. It feels like the time it takes to aggressively optimize CJam code is something larger than O(n) with respect to the size of the code...

You can try it online, but for any input for which the best path is at least 6 operations or so, you should probably try it offline with a faster interpreter.

Squished:

q_'$-_'^-:T;'^#\'^-'$#W{)2$5Y$5b+{:D[L"_T<W%_N#)_@>N+N#X-Ue>+-"_"W%-U"--2'<t2'>t'++'(')]=~0e>T,e<D3/1$T<N\+W%N#X?:X;}/2$-}g5b{" ^v<>"=}%]W=

Expanded and commented:

q               "Read the input";
_'$-            "Remove the end marker";
_'^-:T;         "Remove the start marker and save the text";
'^#             "With only the end marker removed, locate the start marker";
\'^-'$#         "With only the start marker removed, locate the end marker";
W               "Initialize the path number to -1";
{               "Do...";
  )               "Increment the path number";
  2$              "Initialize the cursor position to that of the start marker";
  5Y$5b+          "Convert the path number to base 5, then add a leading 5
                   (the leading 5 will act to initialize the column memory)";
  {:D             "For each digit in the path digit string:";
    [               "Begin cases:";
      L               "0: Do nothing";
      "_T<W%_N#)_@>N+N#X-Ue>+-"
"REFS: [   1   ][  2  ][ 3 ]45
                       1: [1] Calculate the distance to the end of the previous
                              line (0 if no such line)
                          [2] Calculate the length of the previous line (0 if
                              no such line)
                          [3] Calculate the distance to move backwards in the
                              previous line as the maximum of the length of the
                              previous line minus the column memory and 0
                          [4] Calculate the total distance to move as the sum 
                              of [1] and [3]
                          [5] Subtract [4] from the cursor position";
      _"W%-U"-        "2: Start with a base of the logic of case 1, but with a
                          few operations adjusted.";
      -2'<t2'>t       "   [1] Calculate the distance to the *start* of the
                              *next* line (0 if no such line)
                          [2] Calculate the length of the *next* line (0 if no
                              such line)
                          [3] Calculate the distance to move *forwards* in the
                              *next* line as the *minimum* of the length of the
                              *next line* and *the column memory*
                          [4] Calculate the total distance to move as the sum 
                              of [1] and [3]";
      '++             "   [5] *Add* [4] *to* the cursor position";
      '(              "3: Decrement the cursor position";
      ')              "4: Increment the cursor position";
    ]=~             "Execute the case corresponding to the path digit mod 5";
    0e>T,e<         "Clamp the cursor position to [0, text length]";
    D3/             "Check if the path digit is not 0, 1, or 2...";
    1$T<N\+W%N#     "Calculate the current column";
    X?:X;           "If the above check succeeded, update the column memory";
  }/              "End for each";
  2$-             "Subtract the end marker position from the cursor position";
}g              "... While the above subtraction is nonzero";
5b              "Convert the path number to base 5";
{" ^v<>"=}%     "Map each digit in the path string to its operation symbol";
]W=             "Clean up";

Overall, this is a pretty straightforward solution. It "executes" the digits of the base-5 representation of a path number that is incremented every iteration, starting with 0, until a path works. The digits 1-4 map to the operations up, down, left, and right, and 0 does nothing. The first iteration using a path of just 0 catches the degenerate case. All other paths that contain a 0 are never selected because they're just versions of already-tested paths with added no-ops.

The state is modeled in as minimalistic of a way as possible: the text with start and end markers removed, the cursor position in the text, and the "column memory." Newlines are mostly treated like any other character, so there's no concept of a row, and the cursor position is just an index. This makes moving left and right dead simple, which are just implemented as decrement and increment (with clamping to the size of the text). Moving up and down is a bit trickier, but still manageable.

Code reuse was a pretty vital optimization tactic. Examples of this include:

  • Writing the code for moving up in a way such that it's smaller to generate the code for moving down at runtime than to write its own code. This is done by copying the code for moving up and removing/replacing a few characters.
  • Updating the "column memory" is done conditionally based on the path digit divided by 3 instead of it being coded into the logic of the operation. This also allows initialization of the column memory by adding a dummy 5 operation to the start of the path string, which also just so happens to use the 0 no-op logic due to circular array indexing and there being only 5 defined operations.

Overall, I'm very happy with how this came out. This is definitely the most work I've put into a code golf answer to date (for something that fits into a tweet!?). The run time is pretty abysmal, though. CJam isn't exactly the fastest language to begin with and this algorithm has a complexity of something like O(m*5n), where m is the size of the input and n is the size of the output. Good thing speed doesn't count!

\$\endgroup\$
  • \$\begingroup\$ Nice :) I feel a bit guilty for indirectly making you spend so much time on this :p \$\endgroup\$ – aditsu Feb 11 '15 at 20:39
2
\$\begingroup\$

Python 2: 446

Q=input().split('\n');
def g(c):l=[l for l in Q if c in l][0];return Q.index(l),l.index(c)
a,b=g('^');c,d=g('$');Q=map(len,Q);Q[a]-=1;Q[c]-=1
if a==c:d-=b<d;b-=d<b
t=-1
while Q:
 l=[];T=t=t+1;x,y,z=a,b,b
 while T:l+=[T%5]*(T%5>0);T/=5
 for T in l:A=":x+=T+T-3;y=min(Q[x],z)";B="x<len(Q)-1";exec"if "+["","x"+A,B+A,"y:y=z=y-1\nelif x:x-=1;y=z=Q[x]","y<Q[x]:y=z=y+1\nelif "+B+":x+=1;y=z=0"][T]
 if(x,y)==(c,d):print''.join(' ^v<>'[x]for x in l);Q=0

Straightforward solution. I'm performing a breadth-first search. t iterates over all different paths. I convert t into base 5, but only use the entries, which are nonzero. 1 is up, 2 is down, 3 is left and 4 is right.

I keep the current position of the cursor in 3 variables x, y and z. x is the line, y the column position, and z the 'hidden' column position, if you go up or down and the line is too short. Lots of ifs decide, how the variable change during a move.

Preprocessing is really lengthy, the first 4 lines perform only this task.

The long testcase takes a really long time. The algorithm has a complexity of O(N*5^N), where N is the length of the shortest solution.

Usage: Input the lines as a single string (lines seperated by \n) like "Alp$habet^\nSong"

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

CJam - 274

No answer yet? Ok, here's one :)

qN/_{0:V;{_'^={[UVV]:B;;}{'$={[UV]:E;}{V):V;}?}?}/U):U;}/"^$"f-:,:A;{:X0=[X0=(_A=X2=_@e<\]X?}:U;{:X0=A,(=X[X0=)_A=X2=_@e<\]?}:D;{:X1=[X~;(_]{X0=[X0=(_A=_]X?}?}:L;{:X1=X0=A=={X0=A,(=X[X0=)0_]?}[X~;)_]?}:R;[[BM]]{_{0=2<E=},_{0=1=o0}{;[{"U^DvL<R>"2/\f{[~@1/~@\+@@~\]}~}/]1}?}g;

Try it at http://cjam.aditsu.net/ ... except for the Mary example or something of that size, you'll probably want the java interpreter.

\$\endgroup\$
  • 1
    \$\begingroup\$ WTF? 274 !!!!!! \$\endgroup\$ – Optimizer Feb 10 '15 at 15:25
  • \$\begingroup\$ @Optimizer hahaha, well, I wasted enough time on it, go ahead and golf it more if you want :p \$\endgroup\$ – aditsu Feb 10 '15 at 15:26

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.