Бегунки

18

Вам будет дано два ввода: строка в кодированном формате длины пробега, определяющая беговую дорожку, и заглавная буква, представляющая полосу, с которой нужно начинать. Например, строка «3a4A6b5B» раскрывается в «aaaAAAAbbbbbbBBBBB». Затем вы используете расширенную строку для создания дорожки, как таковой:

 A) aaaAAAA
 B) bbbbbbBBBBB

Это трасса с двумя полосами движения. Строчные буквы обозначают воздух. Нельзя бегать по воздуху! Прописные буквы обозначают дорогу, по которой вы можете проехать. Ваша цель для этого задания - с учетом заглавной буквы вывести, насколько далеко может пробежать гонщик, стартовавший на этой дорожке. Гонщикам разрешено менять полосу движения, если непосредственно над или под ними находится участок дороги. Им также разрешено бежать назад! На этой конкретной дорожке выходной сигнал равен 0 для любого буквенного ввода, поскольку ни одна из дорожек не имеет беговой дороги в позиции 1.

Примеры:

Вход: "4A5B4c3C", "A"

Этот код расширяется до дорожки, которая выглядит следующим образом:

A) AAAA
B) BBBBB
C) ccccCCC

Выходные данные для этого примера - 7 , потому что бегун, начинающий на дорожке A, может переместиться вниз на дорожку B, а затем на дорожку C и в конечном итоге оказаться в седьмой позиции.

Вход: «4A2B3D», «D»

Трек:

A) AAAA
B) BB
C)
D) DDD

Выходное значение равно 3 , потому что бегун, стартующий на дорожке D, не может добраться до дорожки B или A

Вход: "4A4a4A3b6B5C", "A"

Трек:

A) AAAAaaaaAAAA
B) bbbBBBBBB
C) CCCCC

Выходное значение равно 12 , потому что бегущий на А может переключиться на В, а затем вернуться к А в конце. Максимальное расстояние для «C» также равно 12. Для «B» это 0.

Вход: "12M4n10N11O", "M"

Трек:

M) MMMMMMMMMMMM
N) nnnnNNNNNNNNNN
O) OOOOOOOOOOO

Простой пример с многозначными длинами серий. Выход 14 .

Входные данные: "4A5B1b2B4c3C", "A"

Трек:

A) AAAA
B) BBBBBbBB
C) ccccCCC

Выходное значение равно 8 , потому что бегун в А может опуститься до В, затем до С, а затем вернуться к В. (Спасибо FryAmTheEggman за этот пример.)

Вход: «1a2A2a2B1c1C1d3D», «B»

Трек:

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

Выход 4 . Бегун должен проверить оба пути, два см., Который идет дальше. (Спасибо user81655 за этот пример.)

Вход: "2A1b1B2C1D3E", "A"

Трек:

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

Выход 3 . Вы должны бежать назад, чтобы добраться до самого дальнего пункта назначения. (Еще раз спасибо пользователю 81655 за этот пример.)

Примечания:

  • Если у дорожки нет буквы в определенной позиции, это тоже считается воздухом. Таким образом, если вход «Q» и на полосе «Q» нет дороги, выход должен быть 0 .
  • Есть две части ввода. Первая строка - это кодированная строка. Вторая - заглавная буква (для этого вы можете использовать тип данных string или char.) Для удобства чтения между этими входами должен быть какой-то разумный разделитель (пробел, новая строка, табуляция, запятая, точка с запятой).
  • Зашифрованная строка длины выполнения будет всегда перечислять элементы в алфавитном порядке
  • Самая длинная длина полосы может быть 1000. Следовательно, максимально возможная производительность - 1000.

Трек-генератор:

В честь нашего первого ответа, вот трековый генератор. Попробуйте придумать что-нибудь, чтобы озадачить текущие ответы! (Примечание. Тот факт, что генератор не показывает сообщение об ошибке, не означает, что ваш трек-код обязательно верен. См. Примеры выше для правильной формы.)

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
источник
3
Теперь, когда решения о переключении и обратном ходу, это больше лабиринт, чем трек: P
user81655
Есть ли когда-нибудь только один маршрут - как в тестовых примерах?
RichieAHB
@RichieAHB Может быть несколько маршрутов.
геокавель
Просто интересно, может быть, 4A2B3Dможет быть устранена сложность обработки недостающего С ? Например, добавление 0c? Если нет, ожидается ли, когда, скажем, 1A1Zбыли даны данные, предполагается, что полосы BY существуют (но пусты)?
Кенни
1
Кроме того, обратный ход - огромная проблема. 12M4n10N11OПример, вывод 14, тогда неверно: самый длинный путь начинается в точке М0 и заканчивается на C0, при длине 25
Kenney

Ответы:

3

Perl, 231 219 203 192 189 байт

включает +1 для -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)

Менее гольф:

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

Бег

Сохраните код выше в файле (скажем 231.pl). Ввод в виде (\d+\w)+ *\w. Пример: ввод дорожки 4A5B4c3Cи полосы движения A:

echo 4A5B4c3C A | perl -p 231.pl

Тестирование

(не в гольф)

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);
  • обновить 219 сохранить 12 байтов путем переработки индексов массива.
  • обновить 203 Сохранить 16 байтов путем рефакторинга рекурсии.
  • обновить 192 сохранить 11 байтов за счет устранения @L=map{[/./g]}@Lпостобработки.
  • обновить 189 сохранить 3 байта путем постфикса, ifиспользуя mapвместо for.
Кинни
источник
Я не знаю, если это Perl, но это БЫСТРО.
геокавель
6

JavaScript (ES6), 298 334 байта

(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

объяснение

В основном это решение рассматривает дорожку как лабиринт. Он находит, где находятся все плитки, которые может достичь бегун, и возвращает наибольшее значение найденного им индекса Х.

Первое, что он делает, это декодирует входную строку в массив строк. Вместо того чтобы использовать буквы, он превращает заглавную букву в букву a, 1а строчную - в букву a 0. Полученная карта будет выглядеть примерно так:

11100011
0011100
100111

После этого он делает первый тайл стартовой дорожки a 2(только если он уже есть 1) и просматривает каждый тайл, проверяя наличие соседних тайлов 2. Если a 1имеет соседний, 2он становится 2. Приведенная выше карта станет такой, если бегун стартовал с первой строки:

22200011
0022200
100222

Самый высокий X-индекс для a 2становится результатом.

Я сделал очень незначительный надзор, когда сделал первоначальную версию этого, и мне стоило 36 байтов, чтобы взломать его, пока он не заработал, так что, вероятно, можно было бы сделать много улучшений. *вздох*

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

Тестовое задание

Бонус: выход включает в себя разобранную карту!

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
источник