Run-Length Racers

18

Anda akan diberikan dua buah input: string dalam format yang dikodekan run-length mendefinisikan trek yang sedang berjalan, dan huruf kapital yang mewakili jalur untuk memulai. Misalnya, string "3a4A6b5B" berkembang menjadi "aaaAAAAbbbbbbbbBBBBBB". Anda kemudian menggunakan string yang diperluas untuk membuat trek, seperti:

 A) aaaAAAA
 B) bbbbbbBBBBB

Ini adalah trek dengan dua jalur. Huruf kecil mewakili udara. Anda tidak bisa berlari di udara! Huruf besar mewakili jalan yang bisa Anda jalankan. Tujuan Anda untuk tantangan ini adalah, diberi huruf besar, menampilkan seberapa jauh pembalap yang mulai berlari di jalur itu. Pembalap diizinkan untuk berpindah jalur jika ada bagian jalan langsung di atas atau di bawahnya. Mereka juga diizinkan berlari mundur! Pada trek khusus ini, outputnya adalah 0 untuk setiap input huruf, karena tidak satu pun track memiliki jalan yang dapat dijalankan di posisi 1.

Contoh:

Input: "4A5B4c3C", "A"

Kode ini diperluas ke trek yang terlihat seperti ini:

A) AAAA
B) BBBBB
C) ccccCCC

Output untuk contoh ini adalah 7 , karena pelari mulai dari lajur A bisa turun ke lajur B, dan kemudian lajur C, dan berakhir di posisi ke-7.

Input: "4A2B3D", "D"

Jalur:

A) AAAA
B) BB
C)
D) DDD

Outputnya adalah 3 , karena pelari yang memulai lane D tidak memiliki cara untuk mencapai lane B atau A

Input: "4A4a4A3b6B5C", "A"

Jalur:

A) AAAAaaaaAAAA
B) bbbBBBBBB
C) CCCCC

Outputnya adalah 12 , karena runner pada A dapat beralih ke B, dan kemudian kembali ke A di akhir. Jarak maksimum untuk "C" juga 12. Untuk "B" adalah 0.

Input: "12M4n10N11O", "M"

Jalur:

M) MMMMMMMMMMMM
N) nnnnNNNNNNNNNN
O) OOOOOOOOOOO

Contoh sederhana dengan run-length multi-digit. Output adalah 14 .

Input: "4A5B1b2B4c3C", "A"

Jalur:

A) AAAA
B) BBBBBbBB
C) ccccCCC

Outputnya adalah 8 , karena runner di A bisa turun ke B, lalu turun ke C, lalu kembali ke B. (Terima kasih kepada FryAmTheEggman untuk contoh ini.)

Input: "1a2A2a2B1c1C1d3D", "B"

Jalur:

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

Output adalah 4 . Pelari harus memeriksa kedua jalur dua melihat mana yang lebih jauh. (Terima kasih kepada user81655 untuk contoh ini.)

Input: "2A1b1B2C1D3E", "A"

Jalur:

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

Output adalah 3 . Anda harus berlari mundur untuk mencapai tujuan terjauh. (Sekali lagi, terima kasih kepada user81655 untuk contoh ini.)

Catatan:

  • Jika sebuah trek tidak memiliki huruf pada posisi tertentu, itu dianggap sebagai udara juga. Dengan demikian, jika inputnya adalah "Q" dan tidak ada jalan yang ditempatkan di jalur "Q" maka outputnya harus 0 .
  • Ada dua potong input. Yang pertama adalah string yang dikodekan run-length. Yang kedua adalah huruf kapital (Anda dapat menggunakan string atau tipe data char untuk ini.) Untuk keterbacaan, harus ada beberapa pemisah yang masuk akal antara input ini (spasi, baris baru, tab, koma, semi-colon).
  • String yang dikodekan run-length akan selalu daftar elemen dalam urutan abjad
  • Panjang jalur terpanjang yang paling panjang adalah 1000. Oleh karena itu, output terbesar yang mungkin adalah 1000.

Lacak Generator:

Untuk menghormati jawaban pertama kami, berikut adalah track generator. Cobalah untuk menemukan sesuatu untuk menghilangkan jawaban saat ini! (Catatan: Hanya karena generator tidak menampilkan pesan kesalahan tidak berarti kode lagu Anda valid. Lihat contoh di atas untuk formulir yang tepat.)

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
sumber
3
Dengan keputusan beralih dan menjalankan mundur itu lebih dari sebuah labirin daripada trek sekarang: P
user81655
Apakah hanya ada satu rute - seperti dalam kasus uji?
RichieAHB
@RichieAHB Mungkin ada lebih dari satu rute.
geokavel
Hanya ingin tahu apakah mungkin komplikasi penanganan C yang hilang 4A2B3Ddapat dihilangkan? Misalnya, menambahkan 0c? Jika tidak, apakah itu diharapkan ketika mengatakan 1A1Zdiberikan, jalur BY diasumsikan ada (tetapi kosong)?
Kenney
1
Juga, berlari mundur adalah masalah besar. The 12M4n10N11Ocontoh, keluaran 14, kemudian palsu: jalan mulai terpanjang di M0 dan berakhir pada C0, untuk panjang 25.
Kenney

Jawaban:

3

Perl, 231 219 203 192 189 byte

termasuk +1 untuk -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)

Kurang bermain golf:

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

Lari

Simpan kode di atas dalam file (katakanlah 231.pl). Masukan dalam bentuk (\d+\w)+ *\w. Contoh: memasukkan trek 4A5B4c3Cdan jalur A:

echo 4A5B4c3C A | perl -p 231.pl

TestSuite

(tidak golf)

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);
  • perbarui 219 hemat 12 byte dengan mengerjakan ulang indeks array.
  • perbarui 203 Hemat 16 byte dengan rekursi refactoring.
  • perbarui 192 hemat 11 byte dengan menghilangkan @L=map{[/./g]}@Lpostprocessing.
  • perbarui 189 hemat 3 byte dengan postfixing alih-alih ifmenggunakan .mapfor
Kenney
sumber
Saya tidak tahu apakah ini hal Perl, tetapi ini berjalan CEPAT.
geokavel
6

JavaScript (ES6), 298 334 byte

(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

Penjelasan

Pada dasarnya solusi ini memperlakukan trek sebagai sebuah labirin. Ia menemukan di mana semua ubin yang mungkin bagi pelari untuk mencapai berada dan mengembalikan nilai terbesar dari indeks X yang ditemukan.

Hal pertama yang dilakukannya adalah mendekode string input ke dalam array baris. Alih-alih menggunakan huruf, itu mengubah huruf kapital menjadi a 1dan huruf kecil menjadi a 0. Peta yang dihasilkan akan terlihat seperti ini:

11100011
0011100
100111

Setelah ini membuat ubin pertama dari trek awal 2(hanya jika sudah 1) dan loop melalui setiap ubin memeriksa ubin yang berdekatan untuk a 2. Jika 1memiliki yang berdekatan 2itu menjadi 2. Peta di atas akan menjadi ini jika pelari memulai pada baris pertama:

22200011
0022200
100222

Indeks X tertinggi untuk a 2menjadi hasilnya.

Saya membuat pengawasan yang sangat kecil ketika saya melakukan versi awal ini dan biayanya 36 byte untuk meretasnya sampai bekerja, jadi mungkin ada banyak perbaikan yang bisa dilakukan untuk ini. *mendesah*

Tidak disatukan

(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

Uji

Bonus: Output termasuk peta yang diuraikan!

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>

pengguna81655
sumber