Help pannenkoek count A presses

Question

pannenkoek2012 aims to complete Super Mario 64 with as few presses as possible of the A button, which makes Mario jump. Each "A press" consists of three parts:

• Pressing the button
• Holding it for any length of time
• Releasing it

See this video (1:15 - 3:23) for a great explanation that includes the above image. (However, this challenge will not use the half-A-press terminology and will posit obstacles that require releasing A.)

Task:

Given a sequence of obstacles requiring pressing (P), holding (H), or releasing (R) the A button, output the smallest number of presses required to overcome them in the order given. The A button is initially not held.

Stated formally: given a string S of characters PHR, consider strings of form (PH*R)* that contain S as a subsequence, and output the smallest possible number of P's in such a string. Or, alternatively, find the smallest number of chunks of the form P?H*R? that S can be split into.

Example

Let's look at input RHRPHHHR. The A button starts not held, so overcoming the initial obstacle R requires the button be pressed and then released (press #1). Next we are required to hold the button H, which again requires it first be pressed (press #2). Then, it can then be released afterwards to satisfy the R after it. Finally, the remaining PHHHR can be satisfied by a single press (press #3) followed by holding HHH and releasing R. So, the output count is 3.

Another way to see it, is that we can split the input string into 3 parts of form PHH..HHR where letters may be omitted.

R
HR
PHHHR    

Input format

The input will be a list or string of elements representing press, hold, and release as your choice of:

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

matched in the order given. The input will not be empty.

Test cases:

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

Leaderboard:

var QUESTION_ID=152701,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/152701/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Retina, 9 bytes

1>`P?H*R?

Try it online!

Answer 2

Pyth, 13 bytes

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

Try it here! or Verify all the test cases.

Note that 1 also works in place of 3.

How it works?

tl:z"P?H*R?"3 | Full program. Takes input from STDIN, outputs to STDOUT.

  :z        3 | Split the input string on matches of...
    "P?H*R?"  | The regular expression "P?H*R?".
 l            | Get the length.
t             | Decrement (because splitting includes the empty string).

More about the regex:

P?     | P – The literal character P, case sensitive.
       | ? – Quantifier. Matches either one or zero times the previous character.
  H*   | H – The literal character H, case sensitive.
       | * – Quantifier. Matches any number of occurrences of the previous character.
    R? | R – The literal character R, case sensitive.
       | ? – Quantifier. Matches either one or zero times the previous character.

Answer 3

Jelly, 10 bytes

o5ḄƝ%⁵>4S‘

A monadic chain taking a list (the P,H,R : 0,1,2 option) and returning an integer, the count.

Try it online! or see the test-suite

How?

Effectively works by getting all adjacent pairs then counting any that are not "continuation pairs" (PR, PH, HR, or HH) and adding one.

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

---

Previous 11 byte solution:

ḅ3Ɲạ3ḟ1,2L‘

Try it online! or see the test-suite

How?

Works like the above, but in a completely different way...

ḅ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

and another, again quite different:

+19*Ɲ%13ḂS‘

(add 19 to each, then for adjacent pairs perform exponentiation, modulo by 13, modulo by 2, sum and add one).

Answer 4

Batch, 69 bytes

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

Takes input as a list of 0-indexed command-line parameters, but you can use a list of letters p, h, r in either upper or lower case if you type set /a p=0, h=1, r=2 first. Explanation: b maintains the last input (defaulting to 2 for released) and n the count of presses. Each input adds a press if the last input was a release or the current input is a press.

Answer 5

Python 2, 44 bytes

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

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

Answer 6

Deorst, 11 bytes

'P?H*R?'ggL

Try it online!

Uses Mr. Xcoder's regex

Answer 7

Japt, 11 bytes

è"P?H*R?" É

Try it | Check all test cases

è counts the number of matches of the RegEx in the input and É subtracts 1.

Answer 8

Python 2, 48 bytes

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

Try it online!

Takes 0,1,2 as input.

Answer 9

Jelly, 10 bytes

Pn1></µƝS‘

Try it online! or Test suite! (Stolen Borrowed from Jonathan.)

Alternative:

P=1=</µƝS‘

Try it 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.

---

Jelly, 11 bytes

Saved 1 byte with help from caird coinheringaahing.

ḅ3Ɲf⁽vḲD¤L‘

Try it online!

Answer 10

Husk, 6 5 bytes

Lġo&ε

Try it online! Input is a list over 0,1,2 (the TIO link uses letters for easier copy-pasting of test cases).

Explanation

I use the same general idea as Jonathan Allan's Jelly answer: split on occurrences of the "discontinuity pairs" PP, HP, RH, RR and RP, and count the resulting blocks. In the 0,1,2 encoding, these pairs are exactly those whose left element is 2 or right element is 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.

Answer 11

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

Answer 12

Haskell, 36 bytes

f a=sum[1|(x,y)<-zip(2:a)a,x>1||y<1]

Try it online!

Uses the 0,1,2 encoding.

Answer 13

Kotlin, 36 bytes

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

Beautified

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

Test

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

Answer 14

J, ₁₈ 17 bytes

-1 Thanks to @FrownyFrog

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

Takes input in the form of 0,1,2. The helper function on TIO converts the test cases to this form.

Try it online!

The logic of the comparisons may still be golfable. I'm twisting my brain into knots trying to think of more equivalent and shorter statements.

Explanation (previous solution)

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

The only difference between the current solution and the previous one is how the comparisons are generated. The current solution explicitly compares adjacent elements by offsetting the array and the previous solution compares adjacent elements by looking at infixes of 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

This would be a lot cleaner if two holds did nothing. The code takes infixes of two and checks if they are not ascending and not two holds. If this is the case, then we add one to our final count. We have to add 1 to the end since we're off by one otherwise (or you could prepend an _ or any value greater than 2).

The way it checks if the infix is two holds is by multiplying the two values together and seeing if it is one (two holds are 1 1).

Answer 15

Vim + wc, 25 bytes

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

␊ is the return key and ␘ is Ctrl+X

Try it online!

Explanation

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