39
\$\begingroup\$

TAS Golf

SMB1 1-1 ending

In the style of a tool-assisted speedrun with a code-golf twist, the goal of this challenge is to complete World 1-1 of the original Super Mario Bros game for the NES in your chosen programming language in as few bytes as possible, using only the in-game controller inputs in the format I'll describe below. Your program must output to stdout a list of lines in this format, created specifically for this challenge:

up down left right start select A B

Starting with the first frame, each newline represents the inputs for Controller 1 for a particular frame. The order of buttons per frame does not matter, and they can be separated by any amount of non-newline whitespace. All or none or some of the button names can be included per line. For example, a simple Python program that presses the D-pad right for 3 frames and then presses A might look like this:

for _ in range(3): print('right')
print('A')

And its output (which I would feed into my emulator to verify) would be:

right
right
right
A

Here, we define 'success' as reaching the flag at the end of World 1-1 pictured above. The score for this example Python submission, if it succeeded (which it doesn't), would be 44 bytes, or the original length of the Python program.

For an example working input file I created based on the current fastest TAS, see this Github Gist: https://gist.github.com/anonymous/6f1a73cbff3cd46c9e1cf8d5c2ff58e1 Note that this file completes the entire game.

There is no way to enter subframe inputs. There is also no way to enter inputs in Player 2's controller, but that also shouldn't be necessary (or useful) for completing the level or game.

The version of SMB used will be the original USA / Japan iNES ROM (md5sum 811b027eaf99c2def7b933c5208636de -- the USA version is the exact same as the Japanese version so either will work, the ROM is commonly labeled Super Mario Bros (JU) (PRG 0) or similar).

To test the submissions, I will run the programs, pipe their stdout into an input.txt file, and load them into FCEUX using this Lua script mario.lua I wrote for this challenge:

for line in io.lines('input.txt') do
   local t = {}
   for w in line:gmatch("%S+") do
      t[w] = true;
   end;
   joypad.set(1, t);
   emu.frameadvance();
end;
while (true) do
   emu.frameadvance();
end;

The specific command I'll be using is fceux mario.nes --loadlua mario.lua. There is no time limit to the programs, though they must eventually terminate.

This is a little Bash one-liner I made to convert a FCEUX movie (.fm2) file to an input.txt for my script, if it helps:

cat movie.fm2 | cut -d'|' -f 3 | sed 's/\.//g' | sed 's/R/right /g' | sed 's/L/left /g' | sed 's/D/down /g' | sed 's/U/up /g' | sed 's/T/start /g' | sed 's/S/select /g' | sed 's/B/B /g' | sed 's/A/A /g' | tail -n +13 > input.txt

For reference, here is a full-resolution map of World 1-1 (open the image in a new tab for full resolution): World 1-1
(source: mariouniverse.com)

Note: At first glance, this may seem like a Kolmogorov complexity challenge on my given input.txt file. However, in reality the challenge is more complex than that because (a) the input.txt I provided is definitely not the shortest possible and (b) there has never been an attempt to create the shortest possible set of keypresses for SMB in this format. The 'fewest buttons possible' known TAS is different because it allows for holding of buttons for a long time, which would add length to the desired output in this challenge.

\$\endgroup\$
  • 1
    \$\begingroup\$ While you have provided a video of the level, I can't count how many rights are in the video. Could you tell us the moves needed? \$\endgroup\$ – user63571 Feb 3 '17 at 19:59
  • 1
    \$\begingroup\$ Did you post this in the Sandbox? I don't remember it. \$\endgroup\$ – user63571 Feb 3 '17 at 21:17
  • 1
    \$\begingroup\$ I think it's quite funny you have 16 upvotes and no answers :) \$\endgroup\$ – user63571 Feb 3 '17 at 23:02
  • 2
    \$\begingroup\$ @JackBates that's the sign of a good, challengjng, non-trivial question \$\endgroup\$ – FlipTack Feb 4 '17 at 6:10
  • 1
    \$\begingroup\$ 404 on that full resolution map image I think \$\endgroup\$ – Liam Feb 4 '17 at 15:45
20
\$\begingroup\$

Python 2, 69 48 46 44 bytes

print"start\n\n"*19+(27*"A right\n"+"\n")*99

See it in action on youtube!

Automatically found with (a modified version of) this hacky script:

start = 18
oncycle = 21
offcycle = 4


while true do
    emu.poweron()
    -- emu.speedmode("maximum")

    starting = 0
    i = 0
    frames = 0
    last_mario_x = -1

    emu.message(start .. " " .. oncycle .. " ".. offcycle)


    state = 0
    while state ~= 6 and state ~= 11 and frames < 4000 do
        if frames > 500 and frames % 100 == 0 then
            mario_x = memory.readbyte(0x6D) * 0x100 + memory.readbyte(0x86)
            if mario_x == last_mario_x then emu.message("stuck " .. mario_x .. " " .. last_mario_x); break end
            last_mario_x = mario_x
        end

        if starting < start then
            joypad.set(1, {start=1})
            emu.frameadvance(); frames = frames + 1;
            joypad.set(1, {})
            emu.frameadvance(); frames = frames + 1;
            starting = starting + 1
        else
            if i < oncycle then
                joypad.set(1, {A=1, B=1, right=1})
                i = i + 1
            else
                joypad.set(1, {})
                i = i +  1
                if i == oncycle + offcycle then
                    i = 0
                end
            end

            emu.frameadvance()
            frames = frames + 1
        end

        state = memory.readbyte(0x000E)
        if state == 4 then
            emu.message("success!")
            os.exit()
            break
        end

    end

    if start < 30 then
        start = start + 1
    elseif offcycle < 10 then
        start = 18
        offcycle = offcycle + 1
    else
        offcycle = 1
        oncycle = oncycle + 1
    end
end
\$\endgroup\$
  • 1
    \$\begingroup\$ @Harry Please verify new version. \$\endgroup\$ – orlp Feb 4 '17 at 4:43
  • 1
    \$\begingroup\$ @Harry I just added another new version that saves 2 more bytes by... not using the B button! It barely fits in the 99 repeats, almost had to waste a byte on doing 100+ repeats. \$\endgroup\$ – orlp Feb 4 '17 at 4:59
  • 1
    \$\begingroup\$ 44-byte version also confirmed, fun to watch! \$\endgroup\$ – Harry Feb 4 '17 at 5:12
  • 1
    \$\begingroup\$ Ahh, this is the kind of answer I was going for, but I couldn’t find the right numbers!! Very nicely done. \$\endgroup\$ – Lynn Feb 4 '17 at 16:47
  • 1
    \$\begingroup\$ @Harry This is a recording of mine: youtube.com/watch?v=2-I1EEOlQYA \$\endgroup\$ – orlp Feb 4 '17 at 17:55
5
\$\begingroup\$

Python 2, 107 bytes

i=0
print'\n'*33+'start'
for c in'~~22 +  2 2? @  F        . \r0'+'@'*10:print'A B right\n'[i:]*ord(c);i^=2
\$\endgroup\$
  • \$\begingroup\$ Very impressive and already much shorter than I thought! Maybe I should have stuck with the full game after all, haha. Also I tested this and can confirm it completes the level, if I can get it to record maybe I'll upload them all as YouTube videos! \$\endgroup\$ – Harry Feb 4 '17 at 1:57
1
\$\begingroup\$

JavaScript (ES6), 59 characters

_=>`start

`[a="repeat"](19)+(`A right
`[a](27)+`
`)[a](99)

This outputs the same text as orlp's answer. I tried coming up with a better method myself, but the movies I converted to an input.txt file did not always play properly. Whenever I tried running the emulator from cmd, I got an error stating "an unknown error occurred".

\$\endgroup\$
  • \$\begingroup\$ Can't run it right now on my end, but if it outputs the same input.txt as orlp's answer then we'll call it verified! \$\endgroup\$ – Harry Feb 4 '17 at 19:06

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.