Ajuda pannenkoek contar A prensas

28

O pannenkoek2012 tem como objetivo completar o Super Mario 64 com o menor número possível de pressionamentos do botão A, o que faz Mario pular. Cada "A press" consiste em três partes:

  • Pressionando o botão
  • Segurando-o por qualquer período de tempo
  • Liberando-o

Partes de uma impressora A, do vídeo de Pannenkoek2012

Veja este vídeo (1:15 - 3:23) para uma ótima explicação que inclui a imagem acima. (No entanto, esse desafio não usará a terminologia de meia imprensa e colocará obstáculos que exigem a liberação de A.)

Tarefa:

Dada uma sequência de obstáculos que exigem pressionar (P), segurar (H) ou soltar (R) o botão A, produz o menor número de pressionamentos necessários para superá-los na ordem indicada. O botão A inicialmente não está pressionado.

Declarado formalmente: dada uma sequência S de caracteres PHR, considere as sequências de forma (PH*R)*que contenham S como uma subsequência e produza o menor número possível de Ps nessa sequência. Ou, como alternativa, encontre o menor número de pedaços da forma em P?H*R?que S pode ser dividido.

Exemplo

Vamos dar uma olhada na entrada RHRPHHHR. O botão A começa a não Rser pressionado ; portanto, para superar o obstáculo inicial, é necessário pressionar e soltar o botão (pressione # 1). Em seguida, é necessário manter o botão pressionado H, o que novamente exige que ele seja pressionado primeiro (pressione # 2). Em seguida, ele pode ser liberado posteriormente para satisfazer o Rdepois. Por fim, o restante PHHHRpode ser satisfeito com uma única pressão (pressione # 3) seguida de segurar HHHe soltarR . Portanto, a contagem de saída é 3.

Outra maneira de ver isso é que podemos dividir a string de entrada em 3 partes do formulário, PHH..HHRonde as letras podem ser omitidas.

R
HR
PHHHR

Formato de entrada

A entrada será uma lista ou sequência de elementos que representam pressionar, segurar e liberar como sua escolha:

  • P, H, R
  • p, h, r
  • 1, 2, 3
  • 0, 1, 2

correspondido na ordem indicada. A entrada não estará vazia.

Casos de teste:

P 1
H 1
R 1
HP 2
RHP 3
HHR 1
PHRH 2
RHRPHHHR 3
HHHHHH 1
PPRRHHPP 6
HPPRHRPRHPPRHPPHRP 12
PRHRHPHHPRRRHPPRHHPPRRRHRHPRPHPRPRHHRPPPRHPRP 28

Entre os melhores:

Mostrar snippet de código

code-golf sequence subsequence xnor
fonte
1
E quanto aos obstáculos que exigem que o botão A não seja pressionado? Existem quatro estados de botão no gráfico (I pensar que estes pudessem realmente existir no jogo, também)
Random832
3
Na realidade, existem três estados: pressione, retido e não retido. Nenhum estado requer um botão A. Solte. O desafio está um pouco errado em comparação com a realidade.
precisa saber é o seguinte
1
@ 11684 "quanto ao lançamento, bem, atualmente não há casos em que isso seja útil ou importante, então não se preocupe com essa parte." (1:48 - 1:52)
user202729
3
Alguém quer fazer isso no assembly MIPS? (o idioma usado para programar Super Mario 64)
user202729
1
@ user202729 Uau, essa é uma panqueca completa. Obrigado!
11684

Respostas:

3

Pitão , 13 bytes

tl:z"P?H*R?"3

Experimente aqui! ou Verifique todos os casos de teste.

Observe que 1também funciona no lugar de 3.

Como funciona?

tl: z "P? H * R?" 3 | Programa completo. Pega a entrada de STDIN, sai para STDOUT.

  : z 3 | Divida a sequência de entrada em correspondências de ...
    "P? H * R?" | A expressão regular "P? H * R?".
 eu Pegue o comprimento.
t Decremento (porque a divisão inclui a sequência vazia).

Mais sobre o regex:

P? | P - O caractere literal P, que diferencia maiúsculas de minúsculas.
       | ? - Quantificador. Corresponde a uma ou zero vezes o caractere anterior.
  H * H - O caractere literal H, que diferencia maiúsculas de minúsculas.
       | * - Quantificador. Corresponde a qualquer número de ocorrências do caractere anterior.
    R? | R - O caractere literal R, que diferencia maiúsculas de minúsculas.
       | ? - Quantificador. Corresponde a uma ou zero vezes o caractere anterior.
Mr. Xcoder
fonte
Ah, merda, você me venceu!
Shaggy
legais! A penúltima linha na descrição do regexp deve dizer "Caractere literal R", certo?
vidstige 7/01/18
@vidstige Sim, obrigado. Corrigido
Mr. Xcoder
2

Gelatina , 10 bytes

o5ḄƝ%⁵>4S‘

Uma cadeia monádica pegando uma lista (a P,H,R : 0,1,2opção) e retornando um número inteiro, a contagem.

Experimente online! ou veja a suíte de testes

Quão?

Efetivamente funciona, obtendo todos os pares adjacentes, em seguida, contar os que não são "pares de continuação" ( PR, PH, HRou HH) e adicionando um.

o5ḄƝ%⁵>4S‘ - Link: list of integers (in [0,1,2])  e.g.: [0,0,1,0,2,1,1,2,2,0] (representing PPHPRHHRRP)
o5         - logical OR with 5                          [5,5,1,5,2,1,1,2,2,5]
   Ɲ       - for all adjacent pairs:              i.e.: [5,5],[5,1],[1,5],[5,2],[2,1],[1,1],[1,2],[2,2],[2,5]
  Ḅ        -   convert from binary                      [ 15 ,  11 ,  7  ,  12 ,  5  ,  3  ,  4  ,  6  ,  9 ]
     ⁵     - literal ten
    %      - modulo                                     [  5 ,   1 ,  7  ,   2,   5  ,  3  ,  4  ,  6  ,  9 ]
      >4   - greater than four?                         [  1 ,   0 ,  1  ,   0,   1  ,  0  ,  0  ,  1  ,  1 ]
        S  - sum                                        5
         ‘ - increment                                  6

Solução anterior de 11 bytes:

ḅ3Ɲạ3ḟ1,2L‘

Experimente online! ou veja a suíte de testes

Quão?

Funciona como o descrito acima, mas de uma maneira completamente diferente ...

ḅ3Ɲạ3ḟ1,2L‘ - Link: list of integers (in [0,1,2])  e.g.: [0,0,1,0,2,1,1,2,2,0] (representing PPHPRHHRRP)
  Ɲ         - for all adjacent pairs:              i.e.: [0,0],[0,1],[1,0],[0,2],[2,1],[1,1],[1,2],[2,2],[2,0]
ḅ3          -   convert from base three                  [ 0  ,  1  ,  3  ,  2  ,  7  ,  4  ,  5  ,  8  ,  6 ]
   ạ3       - absolute difference with three             [ 3  ,  2  ,  0  ,  1  ,  4  ,  1  ,  2  ,  5  ,  3 ]
     ḟ1,2   - filter discard if in [1,2]                 [ 3        ,  0        ,  4              ,  5  ,  3 ]
         L  - length                                     5
          ‘ - increment                                  6

e outro, novamente bem diferente:

+19*Ɲ%13ḂS‘

(adicione 19 a cada um e, em seguida, para os pares adjacentes, faça exponenciação, módulo por 13, módulo por 2, somar e adicionar um).

Jonathan Allan
fonte
Nova geléia rápida!
precisa saber é o seguinte
2

Lote, 69 bytes

@set/ab=2,n=0
@for %%b in (%*)do @set/an+=b/2^|!%%b,b=%%b
@echo %n%

Recebe entrada como uma lista de parâmetros de linha de comando indexados a 0, mas você pode usar uma lista de letras p, h, rem maiúsculas ou minúsculas se digitar set /a p=0, h=1, r=2primeiro. Explicação: bmantém a última entrada (padrão 2para liberada) e na contagem de impressoras. Cada entrada adiciona uma impressora se a última entrada foi uma liberação ou a entrada atual é uma impressora.

Neil
fonte
Ah, setpode definir várias variáveis ​​ao mesmo tempo? Útil saber.
precisa saber é o seguinte
1
@ user202729 set /aé uma avaliação aritmética, desde que todas as variáveis ​​que você deseja definir sejam numéricas, você pode simplesmente usar o operador de vírgula para concatenar as expressões de atribuição.
Neil
2

Python 2, 44 bytes

Usa P-> 1 H-> 2 R-> 3

lambda a:sum(1/y|x/3for x,y in zip([3]+a,a))
feersum
fonte
1

Python 2 , 48 bytes

f=lambda a,*l:l==()or(a>l[0]or l[0]==a!=1)+f(*l)

Experimente online!

Toma 0,1,2como entrada.

ovs
fonte
1

Casca , 6 5 bytes

Lġo&ε

Experimente online! A entrada é uma lista acima 0,1,2(o link TIO usa letras para facilitar a cópia e colar dos casos de teste).

Explicação

Eu uso a mesma idéia geral da resposta de Jonathan Allan Jelly : divida nas ocorrências dos "pares de descontinuidade" PP, HP, RH, RR e RP e conte os blocos resultantes. Na codificação 0,1,2, esses pares são exatamente aqueles cujo elemento esquerdo é 2 ou elemento direito é 0.

Lġo&ε  Input is a list.
 ġ     Split between pairs that do not satisfy:
    ε  the left element is at most 1
  o&   and the right element is truthy.
L      Length.
Zgarb
fonte
1

Javascript (ES6), 30 bytes

f=s=>s.match(/P?H*R?/g).length-1
<input id=i oninput="o.innerText=f(i.value)" value="PHHR"><pre id=o>l
Expandir snippet

Herman L
fonte
1

Gelatina , 10 bytes

Pn1></µƝS‘

Experimente online! ou suíte de teste! ( Roubado emprestado de Jonathan.)

Alternativo:

P=1=</µƝS‘

Experimente online!

Pn1></µƝS‘ | Monadic chain.

      µƝ   | Map over each pair of "neighbours" (x, y) in the list.
P          | And check whether their product...
 n1        | ... 1 if it doesn't equal 1, 0 otherwise...
   >       | Is higher than?
    </     | The pair reduced by "Smaller than?". 1 if x < y, else 0.
        S  | Sum.
         ‘ | Add 1.

Gelatina , 11 bytes

Guardou 1 byte com a ajuda de caird coinheringaahing.

ḅ3Ɲf⁽vḲD¤L‘

Experimente online!

Mr. Xcoder
fonte
Aww, eu perdi a chance de ser o primeiro a usar os vizinhos rapidamente :(
caird coinheringaahing
Você pode remover a μpartir do terceiro
caird coinheringaahing
1

Kotlin , 36 bytes

Regex("P?H*R?").findAll(i).count()-1

Embelezado

Regex("P?H*R?").findAll(i).count()-1

Teste

fun f(i:String) =
Regex("P?H*R?").findAll(i).count()-1
data class Test(val input: String, val output: Int)

val TESTS = listOf(
        Test("P", 1),
        Test("H", 1),
        Test("R", 1),
        Test("HP", 2),
        Test("RHP", 3),
        Test("HHR", 1),
        Test("PHRH", 2),
        Test("RHRPHHHR", 3),
        Test("HHHHHH", 1),
        Test("PPRRHHPP", 6),
        Test("HPPRHRPRHPPRHPPHRP", 12),
        Test("PRHRHPHHPRRRHPPRHHPPRRRHRHPRPHPRPRHHRPPPRHPRP", 28)
)

fun main(args: Array<String>) {
    for ((input, expectded) in TESTS) {
        val actual = f(input)
        if (actual != expectded) {
            throw AssertionError("$input $expectded $actual")
        }
    }
}

TIO

TryItOnline

jrtapsell
fonte
0

J , 18 17 bytes

-1 Obrigado a @FrownyFrog

1+1#.}:(<+:1=*)}.

Recebe entrada na forma de 0,1,2. A função auxiliar no TIO converte os casos de teste para este formulário.

Experimente online!

A lógica das comparações ainda pode ser jogável. Estou torcendo meu cérebro, tentando pensar em declarações mais equivalentes e mais curtas.

Explicação (solução anterior)

1+1#.2(</+:1=*/)\]

A única diferença entre a solução atual e a anterior é como as comparações são geradas. A solução atual compara explicitamente elementos adjacentes deslocando a matriz e a solução anterior compara elementos adjacentes observando infixes de 2.

1 + 1 #. 2 (</ +: 1 = */)\ ]
         2               \ ]  On infixes of 2 on the input
                  1 = */        Is the infix 1 1 (two holds)?
            </                  Is the infix x y such that x < y?
               +:               These results NORed
    1 #.                       Add all of the results together (debase to base 1)
1 +                            Add one

Isso seria muito mais limpo se duas retenções não fizessem nada. O código pega infixes de dois e verifica se eles não estão em ascensão e não em duas retenções. Se for esse o caso, adicionamos um à nossa contagem final. Nós temos que adicionar 1 ao final, já que estamos fora de um caso contrário (ou você pode acrescentar um _ou qualquer valor maior que 2).

A maneira como verifica se o infixo é duas retenções é multiplicando os dois valores e ver se é um (duas retenções são 1 1).

Cole
fonte
1
1+1#.}:(<+:1=*)}.é um mais curto.
precisa saber é o seguinte
@FrownyFrog inteligente, eu vou editar esse no.
cole
1
14:1+1#.0=}.*2-}:
FrownyFrog
0

Vim + wc, 25 bytes

:s/P\?H*R\?/a/g␊V!wc -c␊␘

␊é a chave de retorno e ␘é Ctrl+X

Experimente online!

Explicação

:s/P\?H*R\?/a/g␊    Replace all button presses with the character a
V!wc -c␊␘          Count the characters using the wc command
Herman L
fonte