Run-Length Racers

18

Se le darán dos entradas: una cadena en formato codificado de longitud de recorrido que define la pista de atletismo y una letra mayúscula que representa el carril desde el que comenzar. Por ejemplo, la cadena "3a4A6b5B" se expande a "aaaAAAAbbbbbbBBBBB". Luego usa la cadena expandida para crear una pista, como tal:

 A) aaaAAAA
 B) bbbbbbBBBBB

Esta es una pista con dos carriles. Las letras minúsculas representan aire. ¡No puedes correr en el aire! Las letras mayúsculas representan el camino por el que puede correr. Su objetivo para este desafío es, dada una letra mayúscula, indicar hasta qué punto podría correr un corredor que comience en ese carril. Los corredores pueden cambiar de carril si hay una carretera directamente encima o debajo de ellos. ¡También se les permite correr hacia atrás! En esta pista en particular, la salida es 0 para cualquier entrada de letras, porque ninguna de las pistas tiene una carretera en la posición 1.

Ejemplos:

Entrada: "4A5B4c3C", "A"

Este código se expande a una pista que se ve así:

A) AAAA
B) BBBBB
C) ccccCCC

La salida para este ejemplo es 7 , porque un corredor que comienza en el carril A podría descender al carril B, y luego al carril C, y terminar en la séptima posición.

Entrada: "4A2B3D", "D"

Pista:

A) AAAA
B) BB
C)
D) DDD

La salida es 3 , porque un corredor que comienza en el carril D no tiene forma de llegar al carril B o A

Entrada: "4A4a4A3b6B5C", "A"

Pista:

A) AAAAaaaaAAAA
B) bbbBBBBBB
C) CCCCC

La salida es 12 , porque el corredor en A puede cambiar a B y luego regresar a A al final. La distancia máxima para "C" también es 12. Para "B" es 0.

Entrada: "12M4n10N11O", "M"

Pista: 

M) MMMMMMMMMMMM
N) nnnnNNNNNNNNNN
O) OOOOOOOOOOO

Ejemplo simple con longitudes de ejecución de varios dígitos. La salida es 14 .

Entrada: "4A5B1b2B4c3C", "A"

Pista:

A) AAAA
B) BBBBBbBB
C) ccccCCC

La salida es 8 , porque el corredor en A puede bajar a B, luego bajar a C y luego volver a B. (Gracias a FryAmTheEggman por este ejemplo).

Entrada: "1a2A2a2B1c1C1d3D", "B"

Pista: 

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

La salida es 4 . El corredor tiene que verificar ambos caminos para ver cuál va más allá. (Gracias a user81655 por este ejemplo).

Entrada: "2A1b1B2C1D3E", "A"

Pista:

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

La salida es 3 . Tienes que correr hacia atrás para llegar al destino más alejado. (Una vez más, gracias a user81655 por este ejemplo).

Notas:

  • Si una pista no tiene una letra en una posición determinada, eso también cuenta como aire. Como tal, si la entrada es "Q" y no se ha colocado ninguna carretera en el carril "Q", la salida debería ser 0 .
  • Hay dos piezas de entrada. El primero es una cadena codificada de longitud de ejecución. La segunda es una letra mayúscula (puede usar string o char datatype para esto). Para facilitar la lectura, debe haber un separador razonable entre estas entradas (espacio, nueva línea, tabulación, coma, punto y coma).
  • La cadena codificada de longitud de ejecución siempre mostrará elementos en orden alfabético
  • Lo más largo que puede ser la longitud total de un carril es 1000. Por lo tanto, la mayor salida posible es 1000.

Generador de pistas:

En honor a nuestra primera respuesta, aquí hay un generador de pistas. ¡Trata de encontrar algo para confundir las respuestas actuales! (Nota: el hecho de que el generador no muestre un mensaje de error no significa que su código de seguimiento sea necesariamente válido. Consulte los ejemplos anteriores para obtener la forma correcta).

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>
Expandir fragmento

code-golf string path-finding geokavel
fuente
3
Con las decisiones de cambio y la marcha atrás, ahora es más un laberinto que una pista: P
user81655
¿Existe alguna sola ruta, como en los casos de prueba?
RichieAHB
@RichieAHB Podría haber más de una ruta.
geokavel
¿Me pregunto si tal vez se 4A2B3Dpodría eliminar la complicación de manejar la falta de C ? Por ejemplo, agregando 0c? Si no es así, ¿se espera que, por ejemplo, 1A1Zse den, se supone que existen carriles BY (pero están vacíos)?
Kenney
1
Además, la marcha atrás es un gran problema. El 12M4n10N11Oejemplo, salida 14, es entonces falso: el camino más largo comienza en M0 y termina en C0, por una longitud de 25.
Kenney

Respuestas:

3

Perl, 231 219 203 192 189 bytes

incluye +1 para -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)

Menos golfizado:

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

Corriendo

Almacene el código anterior en un archivo (digamos 231.pl). Entrada en forma de (\d+\w)+ *\w. Ejemplo: entrada de pista 4A5B4c3Cy carril A:

echo 4A5B4c3C A | perl -p 231.pl

Banco de pruebas

(no golfizado)

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);
  • la actualización 219 ahorra 12 bytes al reelaborar los índices de la matriz.
  • actualización 203 Ahorre 16 bytes refactorizando la recursividad.
  • La actualización 192 ahorra 11 bytes eliminando el @L=map{[/./g]}@Lpostprocesamiento.
  • actualización 189 guardar 3 bytes mediante la fijación posterior ifutilizando en maplugar de for.
Kenney
fuente
No sé si esto es algo de Perl, pero esto corre RÁPIDO.
geokavel
6

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

Explicación

Básicamente, esta solución trata la pista como un laberinto. Encuentra dónde están todos los mosaicos que es posible que alcance el corredor y devuelve el mayor valor del índice X que encontró.

Lo primero que hace es decodificar la cadena de entrada en una matriz de líneas. Sin embargo, en lugar de usar letras, convierte una letra mayúscula en 1ay una letra minúscula en a 0. El mapa resultante se verá así:

11100011
0011100
100111

Después de esto, hace el primer mosaico de la pista de inicio a 2(solo si ya lo está 1) y recorre cada mosaico comprobando los mosaicos adyacentes para a 2. Si a 1tiene un adyacente 2se convierte en a 2. El mapa anterior se convertirá en esto si el corredor comenzó en la primera línea:

22200011
0022200
100222

El índice X más alto para a se 2convierte en el resultado.

Hice una supervisión muy pequeña cuando hice la versión inicial de esto y me costó 36 bytes piratearlo hasta que funcionó, por lo que probablemente haya muchas mejoras que se podrían hacer. *suspiro*

Sin golf

(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

Prueba

Bonificación: ¡La salida incluye el mapa analizado!

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>
Expandir fragmento

usuario81655
fuente