Corredores de longa duração

18

Você receberá duas partes de entrada: uma string no formato codificado de duração que define a pista de corrida e uma letra maiúscula representando a pista para começar. Por exemplo, a cadeia "3a4A6b5B" se expande para "aaaAAAAbbbbbbBBBBB". Você usa a sequência expandida para criar uma faixa, como tal:

 A) aaaAAAA
 B) bbbbbbBBBBB

Esta é uma pista com duas faixas. Letras minúsculas representam ar. Você não pode correr no ar! Letras maiúsculas representam a estrada na qual você pode correr. Seu objetivo para este desafio é, dada uma letra maiúscula, mostrar até que ponto um corredor que começa nessa pista pode correr. Os corredores podem mudar de faixa se houver um pedaço de estrada diretamente acima ou abaixo deles. Eles também podem correr para trás! Nesta faixa em particular, a saída é 0 para qualquer entrada de letra, porque nenhuma das faixas possui estrada executável na posição 1.

Exemplos:

Entrada: "4A5B4c3C", "A"

Esse código se expande para uma faixa que se parece com isso:

A) AAAA
B) BBBBB
C) ccccCCC

A saída para este exemplo é 7 , porque um corredor que começa na pista A pode mover-se para a pista B e depois para a pista C e terminar na 7ª posição.

Entrada: "4A2B3D", "D"

Faixa:

A) AAAA
B) BB
C)
D) DDD

A saída é 3 , porque um corredor que começa na pista D não tem como chegar à pista B ou A

Entrada: "4A4a4A3b6B5C", "A"

Faixa:

A) AAAAaaaaAAAA
B) bbbBBBBBB
C) CCCCC

A saída é 12 , porque o corredor em A pode passar para B e depois voltar para A no final. A distância máxima para "C" também é 12. Para "B" é 0.

Entrada: "12M4n10N11O", "M"

Faixa:

M) MMMMMMMMMMMM
N) nnnnNNNNNNNNNN
O) OOOOOOOOOOO

Exemplo simples com comprimentos de vários dígitos. A saída é 14 .

Entrada: "4A5B1b2B4c3C", "A"

Faixa:

A) AAAA
B) BBBBBbBB
C) ccccCCC

A saída é 8 , porque o corredor em A pode descer para B, depois para C e depois voltar para B. (Obrigado a FryAmTheEggman por este exemplo).

Entrada: "1a2A2a2B1c1C1d3D", "B"

Faixa:

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

A saída é 4 . O corredor precisa verificar os dois caminhos para ver o que vai além. (Obrigado a user81655 por este exemplo.)

Entrada: "2A1b1B2C1D3E", "A"

Faixa:

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

A saída é 3 . Você tem que correr para trás para chegar ao destino mais distante. (Mais uma vez, obrigado a user81655 por este exemplo.)

Notas:

  • Se uma faixa não possui uma letra em uma determinada posição, isso também conta como ar. Assim, se a entrada for "Q" e nenhuma estrada for colocada na pista "Q", a saída deverá ser 0 .
  • Existem duas partes de entrada. A primeira é uma string codificada no comprimento da execução. A segunda é uma letra maiúscula (você pode usar o tipo de dados string ou char para isso.) Para facilitar a leitura, deve haver um separador razoável entre essas entradas (espaço, nova linha, guia, vírgula, ponto e vírgula).
  • A sequência codificada no comprimento da execução sempre listará os elementos em ordem alfabética
  • Quanto mais longo o comprimento de uma faixa puder ser de 1000, portanto, a maior saída possível é 1000.

Gerador de Pistas:

Em homenagem à nossa primeira resposta, aqui está um gerador de faixas. Tente inventar algo para esconder as respostas atuais! (Observação: o fato de o gerador não exibir uma mensagem de erro não significa que seu código de faixa seja necessariamente válido. Veja os exemplos acima para obter o formulário correto.)

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>

geokavel
fonte
3
Com as decisões de troca e o retrocesso, agora é mais um labirinto do que uma pista: P
user81655
Existe apenas uma rota - como nos casos de teste?
RichieAHB
@RichieAHB Pode haver mais de uma rota.
amigos estão dizendo sobre geokavel
Imaginando se talvez a complicação de lidar com o C ausente 4A2B3Dpoderia ser removida? Por exemplo, adicionando 0c? Caso contrário, é de se esperar que, digamos 1A1Z, as faixas BY sejam assumidas como existentes (mas estão vazias)?
19615 Kenney
1
Além disso, o retrocesso é um grande problema. O 12M4n10N11Oexemplo, saída 14, é falso: o caminho mais longo começa em M0 e termina em C0, com um comprimento de 25.
Kenney

Respostas:

3

Perl, 231 219 203 192 189 bytes

inclui +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 golfe:

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

Corrida

Armazene o código acima em um arquivo (digamos 231.pl). Entrada na forma de (\d+\w)+ *\w. Exemplo: introdução de faixa 4A5B4c3Ce pista A:

echo 4A5B4c3C A | perl -p 231.pl

Suíte de teste

(não jogou golfe)

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);
  • A atualização 219 salva 12 bytes, reformulando os índices da matriz.
  • atualização 203 Salve 16 bytes refatorando a recursão.
  • A atualização 192 salva 11 bytes, eliminando o @L=map{[/./g]}@Lpós - processamento.
  • atualização 189 salve 3 bytes postfixando ifusando em mapvez de for.
Kenney
fonte
Eu não sei se isso é uma coisa Perl, mas isso é executado rapidamente.
geokavel
6

JavaScript (ES6), 298334 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

Explicação

Basicamente, esta solução trata a pista como um labirinto. Ele encontra onde estão todos os blocos que o corredor pode alcançar e retorna o maior valor do índice X encontrado.

A primeira coisa que faz é decodificar a sequência de entrada em uma matriz de linhas. Em vez de usar letras, ele transforma uma letra maiúscula em uma 1e uma letra minúscula em a 0. O mapa resultante será mais ou menos assim:

11100011
0011100
100111

Depois disso, ele faz o primeiro bloco da trilha inicial a 2(apenas se já estiver 1) e percorre todos os blocos, verificando os blocos adjacentes quanto a 2. Se a 1tem um adjacente, 2ele se torna a 2. O mapa acima se tornará este se o corredor iniciar na primeira linha:

22200011
0022200
100222

O índice X mais alto para a 2se torna o resultado.

Fiz uma supervisão muito pequena quando fiz a versão inicial e me custou 36 bytes para hackear até que funcionasse, então provavelmente há muitas melhorias que podem ser feitas nisso. *suspiro*

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

Teste

Bônus: A saída inclui o mapa analisado!

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>

user81655
fonte