Code Golf: 2D Platformer

Question

The Challenge

• Reach the end of the level!
• Bonus points if you hit each of the (C)oin blocks exactly 2 times.

Disallowed

• Hard coding the command sequence in any way.
• Your favorite "One character language" that happens to do exactly one thing, which is solving this golf.

How To

Your program receives the level below(without line breaks) via standard input.
It then has to print out a commands which are needed to successfully complete the level.

The Level

• S is your starting position.
• E the position you need to be in to complete the level.
• C is a coin block with 2 coins in it, you'll never have to skip one of these in order to be able to complete the level.
• Both C and _ count as ground, there's only solid ground no floating platforms.
• | is a wall, all the walls you'll need to jump up in order to complete the level are at maximum 1 wall tall, everything that's higher you can consider an abyss you can't get out of in any way.
• x are spikes, guess what happens if you touch'em. Spikes will always be one level below the ground that is surrounding them.

All levels are 4 lines height, with each of the lines 63 chars wide. That makes a total of 252 characters per level.

>                       ______  ____       ________  ___        <
>    C            ______|    |  |  |  C  __|      |  | |   ____E<
>S______  __  ____|          |  |  |_____|        |__| |___|    <
>       xx  xx                xx                                <

Notes: The >< are just to illustrate the borders, they are NOT included in the input to your program. Also watch out for your text editor, as mine screwed up the whitespace a number of times

The Commands

• M = Moves you 1 to the right, if there's no ground beneath you, you will fall until you hit it. You cannot move while you are falling.
• J = Jump, moves you up by 1 for the next 3 commands or until you hit a (C)oin Block. After that, you will fall until you reach the ground. You can only jump when on the ground. If an M brings you on the same level as the ground, the jump gets canceled.
• O = NOP, will make you wait/do nothing. This way you can jump holes and spikes which a only 1 block wide(You don't need this for the level above, but you'll earn extra points if you can solve levels which need this).

The Solution(With Coin Blocks)

Successive commands are stacked on top of each other.
F indicates where you will fall(remember you can't do anything while falling),

                            MMMF                 MMMF            
    M                 MMMMMMJ  MMMMF M   MMMMMMMMJ  MMMF        
M   J MMMFMMMF  MMMMMMJ|    |  |  |F J MMJ|      |  | |F MMMMME
SMMMJMJ  MJ  MMMJ|          |  |  |MMJMJ|        |__| |MMJ|    
       xx  xx                xx                                

Resulting command sequence, 75 characters long:

MMMMJJMMJMMMMJMMMMMMJMMMMMMJMMMMMMJMMMMMMMMMJJMMJMMJMMMMMMMMJMMMMMMMMJMMMMM

Hope this yields some interesting results... and not tons of flames :O

EDIT

OK, there are way more possibilities than I initially thought of, I apologize for all the edits.

Connelley

"Moves you 1 to the left" ... shouldn't that be "Moves you 1 to the right"? – Tamie

M moves you right, not left. There may be multiple optimal solutions (e.g. at the end of the sample, it looks like you could jump off the high point, rather than fall and then jump up to the last plateau). It would be good to have a second sample board to prevent 'hardcoding'. I presume all boards will be solvable. Might be interesting, we'll see :) – Reduplicative

Can platforms 'float'? E.g. an underscore that has another underscore directly above it? – Reduplicative

@Tamie Oops, a bit late over here, fixed the left. @Brian, you can't move while you're falling, I'll clarify that in the rules. – Connelley

Might there be coin blocks you need to skip to complete the level? (e.g. if you jumped from below them, you can't complete because you need to jump atop them to jump high enough to scale an upcoming cliff? if so, a test case would help much) – Reduplicative

In the level above there are two possibilities, you can for example jump onto the second coin block to reach the end faster. But this way you won't get the bonus. Currently there's no plan for different levels than this one, I'll add another note for the cliffs though. – Connelley

Also, there won't be any platforms, only solid ground I've added that to the description of the level. – Connelley

Is there a way to 'wait to fall'? What if you encounter _x_x_x_ (with xs a level below)? You need to JMM(wait)JMM(wait), but how can you? – Reduplicative

I like that... you're not thinking of just solving the above level you want to write something that can solve every possible level :D I'll add a just NOP for you ;) – Connelley

"Each of the 5 lines is 63 characters long, which makes a total of 255 chars as the input." - typo? 5*63 != 255. even if you meant 4*63, that's not equal to 255. If you include linebreaks, then it is; however, you said linebreaks are not part of the input. Please clarify. – Melancholic

My answer is officially done, I hope there will be more. Good luck to everyone participating. – Carny

@wallacoloo ...my dear, how many mistakes can I make in one post >_> Fixed the line/char count. – Connelley

Is the height or width of the levels fixed? Or is the input separated by newlines? If neither applies, I can't see how you'd know where each line starts/ends. – Charlet

+1 for disallowing your favorite "One character language" that happens to do exactly one thing, which is solving this golf. – Guffey

@Setsuna As of now there is only the one level above, so that's currently not a problem, but I guess if there would be any others they would be 63 characters wide too. – Connelley

@Guffey that was a clear reference to #285297 Jon Skeet won't be able to be sneaky this time. – Carny

@HoLyVier: Yeah, I've seen that. It's outrageous that it got so many upvotes, which is why I'm glad that this explicitly disallows it. – Guffey

Can we assume that E is always at position 63 (at the 'end' of the level), so to say? – Sheathe

Yes E will always be at the end of the level(63). – Connelley

What about my favorite "Two character language" that happens to do exactly one thing, which is solving this golf? – Me

"there are way more possibilities than I initially thought of" @Ivo: They are harder to write than they look. No complaints about the quality of this post, though it wouldn't hurt to have a look at the (more or less) consensus on code-golf. Maybe if I find time I'll take a crack at this one. – Counterbalance

I'm waiting for a Perl guy to solve this and ascii-artify the source to look like this: pastebin.com/LqTGMWzN – Sheathe

Answer 1

Javascript:

Short Version (334 280 256 240 238 236 233 223 207 205 196 184 182 characters)

a=prompt();j=i=0;while(a[++j*63]<(o="M"));while(++i<62){while(a[h=j*63+i]<"_")j++;if(a[h-63]>"B")o+="JJ";if(a[h+1]>"z")o+="J",j--;if(a[h+3]+a[h+1]=="_ ")o+="JMM",i+=2;o+="M"}alert(o)

Note: The Javascript method prompt tends to remove space on some browser (ex.: Google Chrome). It might not work as expected for that reason for those browsers. On others (ex.: Firefox), it will work fine.

Commented Version

a=prompt(); // Read the input //
j=i=0;
while(a[++j*63]<(o="M")); // Place the cursor at the "S" //
while(++i<62){ // While we are not at the end point //
 while(a[h=j*63+i]<"_")j++; // If we are on a space, we fall //
 if(a[h-63]>"B")o+="JJ";// We jump for coins //
 if(a[h+1]>"z")o+="J",j--; // We jump when we reach a wall //
 if(a[h+3]+a[h+1]=="_ ")o+="JMM",i+=2; // We jump on gap //
 o+="M" // We add the movemment in the output
}
alert(o) // Output

Carny

Equality is a long operator. =="|" could be >"z". Your last if statement could be a[jv+i+1]+a[jv+i+3]==" _" -- do you even need to test for a floor tile there? Even better would be to move the increment to a[++i+jv]. If you can't do that, changing jv+(++i) to ++i+j*v would still save a couple of bytes. – Habana

@Habana For ++i+j*v, it's invalid synthax, I tried it on Firefox and it just throws a synthax error. We need to test for a floor title, look at the end we need to drop, not jump. – Carny

Uh nearly forget about the whole thing here, sorry. I'm going to accept this one, since the Python Version, even though it's shorter, is basically the same approach just with different syntax. – Connelley

@Ivo Wetzel It is now shorter than Python. – Carny

You can also do a=prompt(j=i=0);. Saves 1 character, although it then shows 0 inside the prompt box (should not matter). – Lithium

Answer 2

Python 2.6 318 - 302 - 300 - 284 - 277 - 206 - 203 - 191 - 184 characters

Basically the same approach as HoLyVieR (I wonder if there can be lots of radically different directions solution-wise). Reads from stdin.

Update 1 (318 -> 302): don't check for E but assume it is on position 63 (as asked in a comment).
Update 2 (302 -> 300): changed range(0,252,63) to (0,63,126,189) (two whole characters) Update 3 (300 -> 284): seems raw_input also fetches stdin so import sys etc can be dropped. Update 4 (284 -> 277): [y][x+3]=="_"and p[y][x+1]==" " to p[y][x:x+4]==list("_ _") Update 5 (277 -> 206): went for string instead of 2-dimensional list processing, big save...
Update 6 (206 -> 203): implemented suggestions in a comment on HoLyVieR's answer (by Nabb) Update 7 (203 -> 191): breaking the 200 char-limit by using boolean string building...
Update 8 (191 -> 184): minor tweaks

All comments or suggestions welcome!

Note: I added an (unneeded) \ and newline in the code below (EOL 5->6) (to avoid scrollbars here)

l=raw_input()
x,y,o=0,l.index('S')//63,''
while x<62:
 while l[y*63+x]==" ":y+=1
 b=y*63+x;g=l[b+1]>"z";h=l[b:b+4]=="_  _";o+=(l[b-63]>"A")*"JJ"+g*"J"+h*"JMM"+\
"M";y-=g;x+=1+h*2
print o

Usage: python 2dplatform.py < level.txt

Sheathe

Nice, 1 character shorter than the JavaScript version :D – Melancholic

You can still reduce it of 1 character (y-1)*63+x is the same as y*63-63+x – Carny

@HoLyVieR: thanks for the catch, but my version got updated ;-) – Sheathe

@ChristopheD: Save 3 characters by choosing Python 3. – Perdita

Answer 3

Ruby - 231 226 218 198 197 characters

It can handle one-character gaps and blindly jumps off any cliffs. Falls off if it tries to get a coin immediately to the left of a pit.

l=?\s*63+gets
c=l=~/S/
r=->{c-=62;'JM'}
(print l[c-63]==?C?r[]:(l[c+1]>?\s&&l[c+1]<?x?(c+=1;?M):(l[c+1]<?C&&l[c]>?\s?(c-=61;'JMM'+(l[c+63]<?C?(c+=1;?M):?O)):r[]))
c+=63 while l[c]<?C)while l[c]!=?E

Gabrielson

Any reason you use ?\s instead of shorter 32? – Maintopmast

@Maintopmast I'm using Ruby 1.9, so ?\s returns " ". – Correctitude

Answer 4

C - 275 bytes (DOS line endings)

#define A(B,C)!memcmp(p+1,B,C)
#define P printf
char*p,l[318],k=63;f(){P("M");++p;while(*p<33)p+=k;}main(){read(0,l+k,4*k);p=strchr(l+k,83);while(*p!=69)p[-k]==67?(P("JJM"),++p):(p[1-k]>94?(P("JM"),p+=1-k):(A("  _",3)?(P("JMMM"),p+=3):(A(" _",2)?(P("JMMO"),p+=2):f())));}

This caters for 1-char gaps, and the case where the player is walking across the very top line of the level. You could save a bit if you didn't care about those 2 cases.

Progressive