28
\$\begingroup\$

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

Parts of an A press, from video by Pannenkoek2012

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>

\$\endgroup\$
  • 1
    \$\begingroup\$ What about obstacles requiring the A button to not be held? There are four button states in the graph (I think that these might actually exist in the game, too) \$\endgroup\$ – Random832 Jan 7 '18 at 5:16
  • 3
    \$\begingroup\$ In reality, there are 3 states: Press, Held, and Not-held. No state require an A button Release. The challenge is slightly wrong in comparison with the reality. \$\endgroup\$ – user202729 Jan 7 '18 at 7:26
  • 1
    \$\begingroup\$ @11684 "as for the release, well, there is currently no cases where that's useful or important so don't worry about that part." (1:48 - 1:52) \$\endgroup\$ – user202729 Jan 7 '18 at 15:44
  • 3
    \$\begingroup\$ Anyone want to do this in MIPS assembly? (the language used to program Super Mario 64) \$\endgroup\$ – user202729 Jan 7 '18 at 15:45
  • 1
    \$\begingroup\$ @user202729 Wow, that’s one thorough pancake. Thanks! \$\endgroup\$ – 11684 Jan 7 '18 at 15:45

15 Answers 15

5
\$\begingroup\$

Retina, 9 bytes

1>`P?H*R?

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Ah, feck, you beat me to it! \$\endgroup\$ – Shaggy Jan 6 '18 at 21:29
  • \$\begingroup\$ nice! Second to last line in the regexp description should say "Literal character R", right? \$\endgroup\$ – vidstige Jan 7 '18 at 11:08
  • \$\begingroup\$ @vidstige Yes, thanks. Fixed \$\endgroup\$ – Mr. Xcoder Jan 7 '18 at 11:12
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ New Jelly quick! \$\endgroup\$ – user202729 Jan 7 '18 at 8:36
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Oh, set can set multiple variables at once? Useful to know. \$\endgroup\$ – user202729 Jan 7 '18 at 11:46
  • 1
    \$\begingroup\$ @user202729 set /a is arithmetic evaluation, so as long as all the variables you want to set are numeric, you can simply use the comma operator to concatenate the assignment expressions. \$\endgroup\$ – Neil Jan 7 '18 at 14:03
2
\$\begingroup\$

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))
\$\endgroup\$
1
\$\begingroup\$

Deorst, 11 bytes

'P?H*R?'ggL

Try it online!

Uses Mr. Xcoder's regex

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Aww, I missed the chance to be the first to use the neighbours quick :( \$\endgroup\$ – caird coinheringaahing Jan 7 '18 at 2:30
  • \$\begingroup\$ You can remove the μ from the third one \$\endgroup\$ – caird coinheringaahing Jan 14 '18 at 22:11
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

J, 18 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).

\$\endgroup\$
  • 1
    \$\begingroup\$ 1+1#.}:(<+:1=*)}. is one shorter. \$\endgroup\$ – FrownyFrog Jan 7 '18 at 0:36
  • \$\begingroup\$ @FrownyFrog clever, I’ll edit that in. \$\endgroup\$ – cole Jan 7 '18 at 0:38
  • 1
    \$\begingroup\$ 14: 1+1#.0=}.*2-}: \$\endgroup\$ – FrownyFrog Jan 7 '18 at 10:14
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.