18
\$\begingroup\$

You will be given two pieces of input: a string in run-length encoded format defining the running track, and a capital letter representing the lane to start from. For example, the string "3a4A6b5B" expands to "aaaAAAAbbbbbbBBBBB". You then use the expanded string to create a track, as such:

 A) aaaAAAA
 B) bbbbbbBBBBB

This is a track with two lanes. Lowercase letters represent air. You can not run on air! Uppercase letters represent road you can run on. Your goal for this challenge is, given a capital letter, output how far a racer starting on that lane could run. Racers are allowed to switch lanes if there is a piece of road directly above or below them. They are also allowed to run backwards! On this particular track the output is 0 for any letter input, because neither of the tracks has runnable road at position 1.

Examples:

Input: "4A5B4c3C", "A"

This code expands to a track that looks like this:

A) AAAA
B) BBBBB
C) ccccCCC

The output for this example is 7, because a runner starting on lane A could move down to lane B, and then lane C, and end up at the 7th position.

Input: "4A2B3D", "D"

Track:

A) AAAA
B) BB
C)
D) DDD

The output is 3, because a runner starting on lane D has no way to get to lane B or A

Input: "4A4a4A3b6B5C", "A"

Track:

A) AAAAaaaaAAAA
B) bbbBBBBBB
C) CCCCC

The output is 12, because the runner on A can switch over to B, and then come back to A at the end. The max distance for "C" is also 12. For "B" it is 0.

Input: "12M4n10N11O", "M"

Track:

M) MMMMMMMMMMMM
N) nnnnNNNNNNNNNN
O) OOOOOOOOOOO

Simple example with multi-digit run-lengths. Output is 14.

Input: "4A5B1b2B4c3C", "A"

Track:

A) AAAA
B) BBBBBbBB
C) ccccCCC

The output is 8, because the runner at A can go down to B, then down to C, then come back to B. (Thank you to FryAmTheEggman for this example.)

Input: "1a2A2a2B1c1C1d3D", "B"

Track:

A)aAAaa
B)BB
C)cC
D)dDDD

Output is 4. Runner has to check both paths two see which goes further. (Thanks to user81655 for this example.)

Input: "2A1b1B2C1D3E","A"

Track:

A) AA
B) bB
C) CC
D) D
E) EEE

Output is 3. You have to run backwards to reach the furthest destination. (Once again, thanks to user81655 for this example.)

Notes:

  • If a track does not have a letter at a certain position, that counts as air too. As such, if the input is "Q" and no road has been placed on lane "Q" the output should be 0.
  • There are two pieces of input. The first is a run-length encoded string. The second is a capital letter (you can use string or char datatype for this.) For readability, there should be some reasonable separator between these inputs (space, new line, tab, comma, semi-colon).
  • The run-length encoded string will always list elements in alphabetical order
  • The very longest the entire length of a lane can be is 1000. Therefore, the greatest possible output is 1000.

Track Generator:

In honor of our first answer, here is a track generator. Try to come up with something to stump the current answers! (Note: Just because the generator doesn't show an error message doesn't mean your track code is necessarily valid. See above examples for proper form.)

function reset() {
    var t = document.getElementById("track");
    t.innerHTML = "";
    for(var i = 0;i<26;i++) {
      var c = String.fromCharCode(i+65);
      t.innerHTML += "<div><span>"+c+") </span><span id='"+c+"'></span></div>";
      
    }
  }

function rand() {
  var track = "";
  for(var i = 0;i<26;i++) {
  var blocks = Math.floor(Math.random()*4);
  var start = Math.floor(Math.random()*2);
  for(var j = 0;j<blocks;j++) {
    var letter = String.fromCharCode(65+i+32*((start+j)%2));
    var length = Math.floor(Math.random()*4)+1;
    track += length+letter;
  }
  }
  document.getElementById("code").value = track;
}

  function gen() {
  var s = document.getElementById("code").value;
    var check = s.match(/(\d+[A-Za-z])+/);
    if(check == null || check[0]!=s) {
      alert("Invalid Track");
      return false;
    }
    reset();
  var n = s.match(/\d+/g);
    var o = s.match(/[A-Za-z]/g);
    for(var i = 0;i<n.length;i++) {
      var c = o[i].toUpperCase();
      document.getElementById(c).textContent += o[i].repeat(n[i]);
    }
    return true;
    }
<body onload="reset()">
Track: <input type="text" id="code" size="75%" /><input type="submit" onclick="gen()" /><input type="button" value="Random Track" onclick="rand()" /><code id="track"/>
  </body>

\$\endgroup\$
  • 3
    \$\begingroup\$ With the switch decisions and the backwards running it's more of a maze than a track now :P \$\endgroup\$ – user81655 Dec 19 '15 at 5:15
  • \$\begingroup\$ Is there only ever one route - as in the test cases? \$\endgroup\$ – RichieAHB Dec 19 '15 at 8:38
  • \$\begingroup\$ @RichieAHB There could be more than one route. \$\endgroup\$ – geokavel Dec 19 '15 at 14:51
  • \$\begingroup\$ Just wondering if maybe the complication of handling the missing C in 4A2B3D could be removed? For instance, adding 0c? If not, is it expected when say 1A1Z were given, lanes B-Y are assumed to exist (but are empty)? \$\endgroup\$ – Kenney Dec 19 '15 at 19:42
  • 1
    \$\begingroup\$ Also, the backwards running is a huge problem. The 12M4n10N11O example, output 14, is then false: the longest path starts at M0 and ends at C0, for a length of 25. \$\endgroup\$ – Kenney Dec 19 '15 at 19:55
3
\$\begingroup\$

Perl, 231 219 203 192 189 bytes

includes +1 for -p

sub f{my($l,$p,$m)=@_;map{$m=$_>$m?$_:$m}f($l,$p+1)+1,f($l-1,$p),f($l+1,$p),f($l,$p-1)-1if$L[$l][$p]&&!$V{$l}{$p}++;$m}s/(\d+)(.)\s*/push@{$L[ord$2&~32]},(0|$2lt'a')x$1;()/ge;$_=0|f(ord,0)

Less golfed:

sub f{                          # this is a recursive function, so we need locals.
    my($l,$p,$m)=@_;            # in: lane, position; local: max path length

    map{
      $m = $_ > $m ? $_ : $m    # update max
    }
    f( $l,   $p+1 )+1,          # same lane, forward
    f( $l-1, $p   ),            # left lane, same pos
    f( $l+1, $p   ),            # right lane, same pos
    f( $l,   $p-1 )-1           # same lane, backtrack
    if
        $L[$l][$p]              # check if there's road here
    && !$V{$l}{$p}++            # and we've not visited this point before.
    ;

    $m                          # return the max
}

s/(\d+)(.)\s*/                  # Parse RLE pattern, strip starting lane separator
  push@{ $L[ord$2&~32] }        # index @L using uppercase ascii-code, access as arrayref
  ,(0|$2lt'a')x$1               # unpack RLE as bitstring
  ;()                           # return empty list for replacement
/gex;                           # (x for ungolfing)
                                # $_ now contains trailing data: the start lane.

$_ =                            # assign output for -p
   0|                           # make sure we print 0 instead of undef/nothing
   f(ord,0)                     # begin calculation at start of current lane

Running

Store the code above in a file (say 231.pl). Input in the form of (\d+\w)+ *\w. Example: inputting track 4A5B4c3C and lane A:

echo 4A5B4c3C A | perl -p 231.pl

TestSuite

(not golfed)

printf "==== Testing %s\n", $file = shift // '231.pl';

sub t{
    my($input,$expect) = @_;
#   $input =~ s/\s//g;
    printf "TEST %-20s -> %-3s: ", $input, $expect;

    $output = `echo $input | perl -p $file`;

    printf "%-3s  %s\n", $output,
    $output == $expect
    ? " PASS"
    : " FAIL: $output != $expect";

}

t("4A5B4c3C A", 7);
t("4A5B4c3C C", 0);
t("4A2B3D D", 3);
t("4A4a4A3b6B5C A", 12);
t("4A4a4A3b6B5C B",  0);
t("4A4a4A3b6B5C C", 12);
t("12M4n10N11O M", 14 );
t("4A5B1b2B4c3C A", 8);
t("1a2A2a2B1c1C1d3D B", 4 );
t("2A1b1B2C1D3E A", 3 );
t("10A9b1B8c2C9D1E11F A", 11);
  • update 219 save 12 bytes by reworking array indices.
  • update 203 Save 16 bytes by refactoring recursion.
  • update 192 save 11 bytes by eliminating the @L=map{[/./g]}@L postprocessing.
  • update 189 save 3 bytes by postfixing if using map instead of for.
\$\endgroup\$
  • \$\begingroup\$ I don't if this is a Perl thing, but this runs FAST. \$\endgroup\$ – geokavel Dec 20 '15 at 15:38
6
\$\begingroup\$

JavaScript (ES6), 298 334 bytes

(t,s)=>[a=[],t.match(/\d+(.)(\d+\1)*/gi).map(l=>a[c=l.match`[A-Z]`+"",n=c.charCodeAt(),c==s?i=n:n]=l[r="replace"](/\d+./g,p=>(p.slice(-1)<"a"?"1":"0").repeat(parseInt(p))),i=o=-1),...a.join``,a[i]?a[i]=a[i][r](/^1/,2):0].map(_=>a.map((l,y)=>a[y]=l[r](/1/g,(c,x)=>((a[y-1]||s)[x]|(a[y+1]||s)[x]|l[x-1]|l[x+1])>1?(x>o?o=x:0,2):c)))&&o+1

Explanation

Basically this solution treats the track as a maze. It finds where all the tiles that are possible for the runner to reach are and returns the greatest value of the X index it found.

The first thing it does is decode the input string into an array of lines. Instead of using letters though, it turns a capital letter into a 1 and a lowercase letter into a 0. The resulting map will look something like this:

11100011
0011100
100111

After this it makes the first tile of the starting track a 2 (only if it is already 1) and loops through every tile checking adjacent tiles for a 2. If a 1 has an adjacent 2 it becomes a 2. The above map will become this if the runner started on the first line:

22200011
0022200
100222

The highest X index for a 2 becomes the result.

I made a very minor oversight when I did the initial version of this and it cost me 36 bytes to hack at it until it worked, so there's probably a lot of improvements that could be made to this. *sigh*

Ungolfed

(t,s)=>
  [

    // Decode run-length encoded string into an array of track lanes
    a=[],                           // a = array of track line strings, 0 = air, 1 = tiles
    t.match(/\d+(.)(\d+\1)*/gi)     // regex magic that separates pairs by their letter
    .map(l=>                        // for each line of pairs
      a[                            // add the tiles to the array
        c=l.match`[A-Z]`+"",        // c = pair character
        n=c.charCodeAt(),           // n = index of line
        c==s?i=n:n                  // if this line is the starting line, set i
      ]=l[r="replace"](/\d+./g,p=>  // match each pair, p = pair
        (p.slice(-1)<"a"
          ?"1":"0").repeat(         // repeat 0 for air or 1 for ground
            parseInt(p)             // cast of match would return NaN because of the
          )                         //     letter at the end but parseInt works fine
      ),
        i=                          // i = index of starting line, initialise as invalid
          o=-1                      // o = output (max value of x)
    ),

  // Find all positions that are possible for the runner to get to
    ...a.join``,                   // add every letter of the track lines to an array
    a[i]?a[i]=a[i][r](/^1/,2):0    // set the starting tile to 2 if it is already 1
  ].map(_=>                        // loop for the amount of tiles, this is usually way
                                   //     more than necessary but allows for hard to reach
                                   //     tiles to be parsed
    a.map((l,y)=>                  // for each line l at index y
      a[y]=l[r](/1/g,(c,x)=>       // for each character c at index x

        // Replace a 1 with 2 if there is a 2 to above, below, left or right of it
        ((a[y-1]||s)[x]|(a[y+1]||s)[x]|l[x-1]|l[x+1])>1?
          (x>o?o=x:0,2):c          // set o to max value of x for a 2 tile
      )
    )
  )
  &&o+1                            // return o + 1

Test

Bonus: Output includes the parsed map!

var solution = (t,s)=>[a=[],t.match(/\d+(.)(\d+\1)*/gi).map(l=>a[c=l.match`[A-Z]`+"",n=c.charCodeAt(),c==s?i=n:n]=l[r="replace"](/\d+./g,p=>(p.slice(-1)<"a"?"1":"0").repeat(parseInt(p))),i=o=-1),...a.join``,a[i]?a[i]=a[i][r](/^1/,2):0].map(_=>a.map((l,y)=>a[y]=l[r](/1/g,(c,x)=>((a[y-1]||s)[x]|(a[y+1]||s)[x]|l[x-1]|l[x+1])>1?(x>o?o=x:0,2):c)))&&o+1
function generateMap() { var start = 0; a.some((l, i) => l ? start = i : 0); var end = 0; a.map((l, i) => l && i <= 90 ? end = i : 0); for(var output = "", i = start; i < end + 1; i++) output += String.fromCharCode(i) + ") " + (a[i] || "") + "\n"; return output; }
Track = <input type="text" id="track" value="2A1b1B2C1D3E" /><br />
Starting Letter = <input type="text" id="start" value="A" /><br />
<button onclick="result.textContent=solution(track.value,start.value)+'\n\n'+generateMap()">Go</button>
<pre id="result"></pre>

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