text:
Programming with a Sporadic Shift Key
There's something wrong with your keyboard. The Shift key has a mind of its own. Every time you type a character you have no idea whether it will come out shifted or not (though it is 50-50). Besides the standard character keys, nothing on the keyboard is functional. There is no mouse or other means of input.
Somehow you know the only way to fix things is to write a program that outputs Dear Computer, please stop giving me shift! to stdout. Luckily your IDE is open and you are capable of running a program, but of course as you type it you won't know which characters will be shifted.
What sequence of key-presses would you use to write a program that has the best possible chance of working on the first try?
Details
You are using a standard QWERTY keyboard, so there are 50 character keys you can press.
Unshifted versions (47 only):
`1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./

Shifted versions (47 only):
~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:"ZXCVBNM<>?

The last 3 keys are Enter, Tab, and Space, which are the same shifted and unshifted.
A sequence of N of these characters has 2N - (whitespace char count) ways it might have been output if you had typed them with your faulty keyboard. For example, typing A Space m might have yielded
a m or A m or a M or A M.
Write a program these characters and look at all of its 2N - (whitespace char count) possible shift combinations. The more combinations that output Dear Computer, please stop giving me shift! the better. Your score is the number of working combinations (valid programs) divided by the total number of combinations. The highest score wins.
Notes

For valid programs, printing precisely Dear Computer, please stop giving me shift! and nothing else to stdout should be the only side effect.
Valid programs should not take input.
Invalid programs can do anything whatsoever.
Comments may be used anywhere.
Whitespace answers cannot win because getting a 100% score is (relatively) trivial. You may still submit a Whitespace solution for fun.
Your program must be at most 1024 characters long.

Update: Changed Stop giving me shift! to Dear Computer, please stop giving me shift! to allow for more complex answers. Existing answers may stay the way they are if desired.

Why's the 1024-character restriction?

@JanDvorak Without a limit there might be ways to make the limit of valid programs approach 100% as the size of the program increases. (Though that would be pretty cool.)

I can't think of any way to improve the baseline score of 2^-(18 + whatever the language needs)

Please ping me once there is a better answer than mine

@JanDvorak Without the restriction, you could do something like  exec(min(["code","code","code",...])), with a ginormous number of copies of your code to run a lower-cased version of it basically guaranteed.

+1, it's a great challenge, but I wish you'd given us a longer output string. I've thought of several clever tricks, but all of them take more than 18 characters in all the languages I know.

@Nathaniel I was just wishing that too,. It's only been an hour, I may change it.

@Calvin'sHobbies but... what about the current answers?

@xnor the problem with your suggestion is that each pair quotes is a 2^-1 to your score and so are the commas inbetween. Unless you do something like .words

I have changed the phrase. Existing answers can stay, though not a ton may need to change in them. Apologies for rule change. (@Nathaniel)

@Calvin'sHobbies Now the score becomes a non standard as the previous string will always result in a lower score. Can you either switch back to older string or mandate the use of new one ?

@Optimizer Sorry but it would be unfair to the original answers to force the change. All new answers must use the new string through, and it may be possible to beat the best old answer.

@Calvin'sHobbies It's not! And the 1024 limitation prevents that very well too. given all this, I am voting for this to close as unclear what you are asking. Please do not change spec which gives disadvantage to most of the answers

@Calvin'sHobbies Too bad there's the 1024 char limit. I'm going to need to rethink my answer...

@Optimizer I have removed the 2^-7 one in the answer. So there isn't much trouble now.

@user23013 There are other answers based on the previous string too.

@Optimizer At least they won't win.

I'm assuming you're not allowed or able to hold down the other shift key to force everything shifted?  Or would doing so give you a 75% chance of being shifted and 25% of unshifted if both of your shift keys act identical?

@WOUNDEDStevenJones No. Assume pressing either shift does nothing. The computer just thinks shift is being pressed randomly.

For once in my life, knowledge of VB is more useful than knowledge of C++.

A perfect time to use WhiteSpace?

@awashburn That's not allowed (for winning). See rules.

Applescript, 20 (100%)
I believe I can claim a perfect score here:

The Applescript Editor (my IDE) automatically converts all keywords to lower case upon compiling/running
Furthermore, defined variable and handler names are case insensitive - For example if a handler myFunc is defined, then the IDE will automatically convert MYFUNC, myfunc, MyFuNc, etc references to myFunc
I have only used alphabetic characters, spaces and newlines, so I don't need to worry about shifted numbers and punctuation characters.

Here is is:
global f
on j at a
set end of a to j
end
on c at a
j at a
j at a
end
on k at a
repeat with q in system info
j at a
end
end
on w at a
set d to count a
j at a
return string id d
end
on z at a
set end of f to a
end
set h to space
set y to h as list
k at y
k at y
set x to w at y
c at y
c at y
c at y
c at y
c at y
set q to w at y
k at y
c at y
c at y
copy y to b
c at y
set s to w at y
set d to w at y
set f to d as list
k at b
k at b
set a to w at b
c at b
j at b
set e to w at b
set y to w at b
set g to w at b
set d to w at b
set i to w at b
c at b
set l to w at b
set m to w at b
set n to w at b
set o to w at b
set p to w at b
j at b
set r to w at b
z at e
z at a
z at r
z at h
z at s
set s to w at b
set t to w at b
set u to w at b
set v to w at b
z at o
z at m
z at p
z at u
z at t
z at e
z at r
z at q
z at h
z at p
z at l
z at e
z at a
z at s
z at e
z at h
z at s
z at t
z at o
z at p
z at h
z at g
z at i
z at v
z at i
z at n
z at g
z at h
z at m
z at e
z at h
z at s
z at d
z at i
z at y
z at t
z at x
f as text

Thanks to the help of @kernigh and @paradigmsort, this is now 1020 bytes, just squeaking in under the 1024 byte limit!
Explanation:

The characters for output string are generated using string id <n>, which returns the character corresponding to the ascii value n
Because we are avoiding digits, each n has has to be generated by more fundamental means.  Specifically we generate each n by counting a list, and then adding another item to that list.  The repeat with q in system info allows us to do this 16 times, as system info always returns a 16-item list.
Using a similar technique, we add each character of the final string in turn to a list.
Finally that last list is coerced to text and printed.

Output:
Using the osascript interpreter, but the Applescript Editor works just as well:
$ # Interpret as-is:
$ osascript dearcase.scpt
Dear Computer, please stop giving me shift!
$
$ # Interpret all lower case:
$ tr A-Z a-z < dearcase.scpt | osascript
Dear Computer, please stop giving me shift!
$
$ # Interpret all upper case:
$ tr a-z A-Z < dearcase.scpt | osascript
Dear Computer, please stop giving me shift!
$
$ # Interpret random case for each letter:
$ while read; do for ((i=0;i<${#REPLY};i++)); do c="${REPLY:i:1}"; if ((RANDOM%2)); then printf "%s" "$(tr a-z A-Z <<< "$c")"; else printf "%s" "$(tr A-Z a-z <<< "$c")"; fi; done; echo; done < dearcase.scpt | osascript
Dear Computer, please stop giving me shift!
$

Very very cool! I hope you can get it to 1024. Mind explaining the code a bit?

@Calvin'sHobbies Applescript is supposed to be one of the most readable languages - you really don't understand this? ;-)  I'll try to add an explanation in a bit...

Please post the golfed version, with no indentation and no name in end name. As is, I must use sed -e 's/^ *//' -e 's/^end.*/end/' dearcase.scpt | wc -c to count it.  Also, you can get down from 1044 to 1037 by changing count of a to count a, and deleting log from log f as text.  I test with an old OS X 10.4 system, where log command has empty result; osascript only prints the result, not the event log, so I get no output unless I delete log.

Changing c to call j twice instead of three times and updating the call sites as needed saves 7 characters and gets you under the limit.

# Interpret all upper case: $ tr A-Z a-z - The args are backwards, right?

@Izkata Yes, copy/paste error - good catch.

PHP, 2^-12
echo ucwords(strtolower('Dear Computer, ')).strtolower('please stop giving me shift!');

PHP being PHP, capitalization of echo, ucwords, and strtolower don't matter. The calls to ucwords and strtolower ensure that the case of the strings won't change the output.
Therefore, the only characters that can't be changed are ((,)).(!); (10 characters).
Each pair of quotes also has a 50% chance of being valid ('' and "" are valid, but '" and "' are not), therefore each adding another power of two.

@edc65 ucwords capitalizes the first letter of each word

a good IDE will add the correct closing quotes for you (you'll only ever end up with '' or "", as well as the closing parentheses, so though you still have a 50% chance for (, the ) should be automatic.

shoot, you can't use any sort of navigation keys (arrows), so even if your IDE did autocomplete correctly, you'd need to type that same character again or else it will insert the new (wrong) one, like this: strtolower("Dear Computer, '"0)...

@WOUNDEDStevenJones I believe relying on IDE features would be counted as cheating.

What about <? at the start of the program?

CJam, 2-7 2-12 chance
'D"ear Komputer, please stop giving me shift!"el4'Ct

It has similar idea as Quincunx's first answer, but in CJam.

Is this intentionally a K instead of C?

@PaŭloEbermann That character is independent. It can also be a space or something else.

Whitespace (645 bytes, 2^0 probability)
Since this program only uses tabs, spaces and newlines (which are all unaffected by shifting), it gives a 100% success rate.

Program run

But note that this is off-competition as per the rules.

Python 2, 2-20 chance
print'S'+'top giving me shift!'.lower()

print, S, +, !, and .lower() must all be the correct version; that's 18 chars. The two quotes for the strings must also align, that makes two more powers of two.
For any of the top giving me shift, if it is converted to the capital version, we convert it to lowercase and it works properly.
Sadly, I can't make use of Python's nifty capitalize(), because that takes one more character.

If it helps, the phrase is now longer (but not capitalized normally).

@Calvin'sHobbies I saw that. It doesn't help; it harms.

CJam, 2-9 chance, 739 bytes
"
(lines of space characters)
                                        "N/2fb:c

base64:
IiAJICAgIAkgCQkgICAJICAKICAgCSAJCSAgIAkJCQkgCQoJCQkJIAkgIAkJIAkJICAJCiAJICAg
IAkgCQkgICAgCSAKICAgCSAJCSAgCSAgICAgIAogCQkJCSAJICAJCSAJIAkJCgkJCSAJICAJCSAJ
CSAJCQkKIAkgCQkgIAkgICAgIAkgCQoJIAkJICAJICAgIAkgICAgCgkgIAkJIAkJCQkgIAkJIAkK
CQkgCSAgCQkgCQkJIAkgIAogICAJIAkJICAgCQkJCSAJCiAJICAgIAkgCQkgICAgCSAKIAkJCQkg
CSAgCQkgCQkgIAogICAJIAkJICAJICAgICAgCgkgCQkgIAkgICAgCSAgICAKCSAgCSAgICAJIAkg
CQkgIAogICAJIAkJICAgCQkJCSAJCgkJCQkgCSAgCQkgCQkgIAkKICAgIAkgCQkgICAJCSAJCQog
ICAJIAkJICAgCQkJCSAJCiAgIAkgCQkgIAkgICAgICAKICAgIAkgCQkgICAJCSAJCQoJCSAJICAJ
CSAJCQkgCSAgCgkJCSAJICAJCSAJCSAJCQkKCSAJCSAgCSAgICAJICAgIAogICAJIAkJICAJICAg
ICAgCgkgCSAgCQkgCQkJIAkJCQkKICAJCSAJCQkJIAkgICAgCQogCQkgIAkgICAgCSAgCQkgCiAg
CQkgCQkJCSAJICAgIAkKICAJICAgIAkgCSAJCQkJIAoJIAkgIAkJIAkJCSAJCQkJCiAgIAkgCQkg
IAkgICAgICAKIAkgCQkgIAkgICAgIAkgCQogICAJIAkJICAgCQkJCSAJCiAgIAkgCQkgIAkgICAg
ICAKICAgIAkgCQkgICAJCSAJCQogCQkgCQkJCSAJICAJICAgCiAgCQkgCQkJCSAJICAgIAkKCQkg
CQkJCSAJICAJIAkJIAoJCSAJICAJCSAJCQkgCSAgCgkJIAkJCQkgCSAgCQkgIAkiTi8yZmI6Yw==

Based on the idea of Optimizer and Quincunx's answer.

VisualBasic.net 2^-18
Critical chars: .("DearC"+",!".())
Sub Main
  console.write("Dear C"+"omputer, please stop giving me shift!".tolower())
End Sub

Tested in LINQPad, Language = "VB Program"

I think visual studio would auto-correct the casing for you.

@Pharap but the casing outside quotes is not the problem... VS would not correct a '(' shifted to '9'

In that case, something more useful: you can get rid of the potential case of getting > instead of . by changing Console.Write(string) to Write(string) and swapping (string).ToLower() out for LCase(string).

Pyth, 2**-15
+"S"$"top giving me shift!".lower()

I can't seem to find Pyth's version of lower(), so I'll borrow from Python. The characters that can't be swapped are +"S"$, !, and .lower(), for a total of 14 chars. The quotes after the $ must match, adding another power of 2.

Pyth doesn't have a lower() - it wasn't getting used enough. I should probably add it back in.

CJam, 2-13 chance
As per the updated string (696 bytes).
"

             "N/:,2/Kfb:c

Only ""N/:,2/Kfb:c are at risk right now.
Try it online here and since this text editor is eating up all the spaces, here is the gist with the correct code.

Rant, 2-21
[caps:first][?[caps:word][?[caps:lower]Dear Computer][caps:lower], please stop giving me shift!]

A series of metapatterns and caps calls force proper formatting. Function names and arguments are case insensitive.
Online version

VB.NET, 2^-12 2^-11
2-12
Module All
  Sub Main
    Console.WriteLine StrConv("Dear Computer, ", vbTuesday) & "please stop giving me shift!".ToLower
  End Sub
End Module

2-11
Imports System.Console

Module All
  Sub Main
    Write StrConv("Dear Computer, ", vbTuesday)
    WriteLine "please stop giving me shift!".ToLower
  End Sub
End Module

I thought about my answer before getting to the '50 characters including only Enter, Tab, Space' rule. So mine is not valid.
Seems having case insensitive programming languages is the key here. Alternatively, if you could use a Real standard QWERTY keyboard (including Caps Lock, the other Shift, Backspace, and the Numpad Period) there would only be 2 necessary 50% chances which would only result in 2 additional key presses per failure. My invalid answer for a C# Console Application pointing out actual key presses:
HoldShift(C CpsLockOn onsole)

NumPadPeriod

HoldShift(
CpsLockOff W CpsLockOn rite("
CpsLockOff D CpsLockOn ear space
CpsLockOff C CpsLockOn omputer
)

, (repeat with Backspace until correct)

HoldShift( please stop giving me shift!"))

; (repeat with Backspace until correct)

76 minimum presses with only 2 necessary 50% chances

Excel, 2-11
=PROPER("Dear Computer, ")&LOWER("please stop giving me shift!")

Case of PROPER and LOWER don't matter.
Entering a formula starting with + automatically inserts required =.
So only (, ", ,, ), &, ! can break.

authors: ابونصر البحار


text:
Draw a Golden Spiral!
Given a number n, you must output a golden spiral with the number of quarter turns being n.
The spiral must be completely black and the background must be completely white. This must be output as a φ⌊n/4⌋*4 by φ⌊n/4⌋*4 PNG file (you may output a PPM and convert it later). The shortest code wins.
The radius of the smallest quarter turn should be φ-3.
In geometry, a golden spiral is a logarithmic spiral whose growth factor is φ, the golden ratio.That is, a golden spiral gets wider (or further from its origin) by a factor of φ for every quarter turn it makes.

So, this is actually Draw a black golden spiral then?

@Compass You should draw it with coffee or oil, probably, but there are other options.

@Geobits Just don't use Marmite

If someone was to use blockly, would they have to screen-shot their code?  How would byte-count be decided?  For the curious, the turtle is shown drawing what looks at a glance like the golden spiral: https://blockly-demo.appspot.com/static/apps/index.html?lang=en

@Will That's not a golden spiral in the icon, it's not even a logarithmic spiral. It's an arithmetic/archimedian spiral (that grows by the same amount each revolution.) A golden spiral is a type of logarithmic spiral (that grows by the same ratio each revolution.) Another characteristic of a logarithmic spiral is that for any point on the spiral there is a constant angle between the radius passing through that point and the spiral itself, so the spiral looks the same when you zoom in or out. I can't get the blockly sample program to run, though.

What do the ⌊ and ⌋ mean in the exponent of the height and width? Can they just be read as ( and )?

@britishtea They resemble the flooring function. Similarly, if they are the other way round, they resemble the ceiling function.

Mathematica, 169 bytes
All those annoying options. :(
f=Export[p=GoldenRatio;"a.png",ParametricPlot[p^(2t-3){Cos[a=t*Pi],Sin@a},{t,0,#/2},PlotRange->{r={m=-p^(#-3),-m},r},PlotStyle->Black,Axes->1<0,ImageSize->p^#~Floor~4]]&

This function saves the spiral to a.png in wherever your current working directory is.
The result of f[9]:

The result of f[12]:

I hope I understood all the bits about the scaling correctly.
There's not a whole lot to say about the code. I'm using ParametricPlot to draw curve as a parameterised function in t which advances by 1/2 for each quarter turn. The rest is done in the options:

PlotRange->{r={m=-p^(#-3),-m},r} makes sure we have an square aspect ratio which just covers the outermost point of the spiral.
PlotStyle->Black overwrites Mathematica's blue default colour.
Axes->1<0 is just Axes->False (and turns off the axes, who knew!).
ImageSize->p^#~Floor~4 sets the correct dimensions in pixels, by noticing that ⌊n/4⌋*4 just means "n rounded down to the nearest multiple of 4".

Hmm... I think it could perhaps be slightly shorter as a PolarPlot, but it probably wouldn't differ too much.

@Tally Ah, I keep forgetting about PolarPlot. I'll have a look at that later.

What? Mathematica doesn't have GoldenSpiral[]? I'm dissapoint

Python 3 - 290 269
This will get crushed by any kind of built-in parametrics, but I figured I'd post it as an example of a point-by-point solution.
Edit: Thanks for the golfing tips! If you have any more, please make them.
from math import *
from PIL import Image as I, ImageDraw as D
n=eval(input())
G=(1+5**.5)/2
w=int(G**(4*(n//4)))
i=I.new("RGB",(w,w),"white")
d=D.Draw(i)
k=pi/180
d.line([(G**(j/90)*cos(j*k)+w/2,G**(j/90)*sin(j*k)+w/2)for j in range(n*90)],fill=0)
i.save("s.png","PNG")

You can really golf this down.  You can from math import * to avoid the M. prefix everywhere and you can turn the for loop into a comprehension.  However, when I run this, I had to remove the eval() on the input() for entering a number, and I couldn't get the expected graph for the size.  Setting n to a big number like 10 or 20 and it never finishes; setting it to a bigger number like 50 and it immediately aborts because the numbers are too big.

Thanks for the tips, Will! I'm not sure how to make it work for large n, as the requirements specify an exponential image size.

You can create your image like so if you only use B&W : i=I.new('L',(w,w)) and display it with i.show().

Can shave off two bytes by changing from math import * to from math import* and from PIL import Image as I, ImageDraw as D to from PIL import Image as I,ImageDraw as D

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Write a square program that outputs the number of times it has been "unrolled"
Consider a square block of text, N characters wide by N tall, for some odd integer N greater than 1.
As an example let N = 5 and the text be:
MLKJI
NWVUH
OXYTG
PQRSF
ABCDE

Notice that this is the alphabet (besides Z) spiraled around counter-clockwise from the lower left corner. It's kind of like a rolled up carpet.

"Unrolling" the text by one quarter turn clockwise so FGHI are on the same level as ABCDE results in:
     PONM
     QXWL
     RYVK
     STUJ
ABCDEFGHI

This unrolling can be done 7 more times until the text is a single line:
         SRQP
         TYXO
         UVWN
ABCDEFGHIJKLM

             UTS
             VYR
             WXQ
ABCDEFGHIJKLMNOP

                WVU
                XYT
ABCDEFGHIJKLMNOPQRS

                   XW
                   YV
ABCDEFGHIJKLMNOPQRSTU

                     YX
ABCDEFGHIJKLMNOPQRSTUVW

                       Y
ABCDEFGHIJKLMNOPQRSTUVWX

ABCDEFGHIJKLMNOPQRSTUVWXY

Challenge
The challenge is to write a program that is an N×N block of text that outputs the number of times it has "unrolled" by a quarter turn when it is rearranged into the unrolling patterns and run.
There are really two contests here: (hopefully it won't be too messy)

Do this with the smallest N. (down to a limit of N = 3)
Do this with the largest N. (no limit)

There will not be an accepted answer but the winner in each of these categories will receive at least 50 bounty rep from me. In case of ties the oldest answers win.
Example
If your code block is
MyP
rog
ram

running it as is should output 0.
Running
   rM
   oy
ramgP

should output 1.
Running
     or
ramgPyM

should output 2.
Running
       o
ramgPyMr

should output 3.
Finally, running ramgPyMro should output 4.
Details

The output should be printed to stdout (or the closest alternative) by itself. There is no input.
You may only use printable ASCII (hex codes 20 to 7E, that includes space) in your code.
Spaces fill the empty space in the unrolling arrangements. (Unless you're unrolling to the left.)
Only the arrangements from completely square to completely flat need to have valid output. No other arrangements will be run.
You may not read your own source.
You may use comments.
N = 1 is excluded since in many languages the program 0 would work.
If desired you may unroll to the left rather than the right. So e.g.
MyP
rog
ram

becomes
Pg
yo
Mrram

and so on. No extra spaces are added when rolling this way. The lines just end

(Related: Write a Rectangular Program that Outputs the Number of Times it was Rotated)

Before I read the "challenge" paragraph, I was expecting a challenge to write a program that outputs itself unrolled

why does N have to be odd?

@JanDvorak I suppose N didn't have to be odd, but it makes the spirals more standardized. It's staying that way but feel free to post an N = 2 as a comment if you find one.

Do you know if N=3 is possible?

Just an idea: Unrolling the "carpet" to the right creates many lines starting with whitespace, eliminating languages like Python. If you'd allow unrolling to the left, there'd be no need for additional whitespace and Python is (theoretically) possible.

@Falko Good point. I'll allow unrolling to the left instead.

Do you have a magic book with infinite great challenge ideas? How else do you keep coming up with such interesting challenges?

@Quincunx Someday when I'm tired of PPCG I'll upload my entire tome ;) (But sadly this particular challenge is already almost totally solved by Jan.)

@JanDvorak I don't know about N = 3. I'm guessing no.

It's the first time I want a language (APL for instance) to have base 10 logarithm by default. 00\n⍟1 returns the result times ln(10).

Golfscript, N <- [5,7..]
.   .
 . .
 ..
.  .#
],9\-

Fully unrolled:
],9\-#  .   .  .  . . ...

Explanation:

. (multiple times) - duplicate the input
] - collect the stack into a single array
, - take its length
9\- - subtract it from 9
# - line comment

Whitespace is a NOP, but any other NOP would have worked just as well.
Fully rolled up, it uses nine copies of the input (contents ignored) as the stack; 9 - 9 = 0; it has not been unrolled.
Each unroll hides one more dot (duplicate) behind the comment, shrinking the stack once, incrementing the output.
Fully unrolled, it uses only the input (contents ignored) as the stack; 9 - 1 = 8; it has been unrolled 8 times.
The same approach works for any N > 4: Change 9 to the appropriate value of 2*N+1, then extend the pattern of dots (duplicate) using the same spiral pattern that ensures exactly one dot gets unrolled during each unroll.

Well, unless someone finds N = 3, this will be the winning answer in both categories.

@Calvin'sHobbies should I be a total dick and post a left-unrolling solution as well? :-)

Why not. Another answer seems unlikely otherwise :P

Why not go for one which can unroll in both directions? :)

@BetaDecay hmm... :-)

@Calvin'sHobbies So, I am not certain about how golfscript works with integer overflow, but I would assume this will actually explode around 2^32 (or sooner on a stack overflow?). If I'm right, would something that works for a larger value beat this?

@FryAmTheEggman Golfscript is based on Ruby, and Ruby has an arbitrary-sized integers. What are you in, Java? Moreover, this program doesn't use it anyways. As for stack overflow - I'm pretty sure your IDE will run out of memory (N=64ki yields a 4GiB source file) far sooner than my script (N=64ki = 256ki frames, but GFS stack actually lies on the heap ;-))

@FryAmTheEggman Even still, I wouldn't be a stickler about that. And where would you post such a huge spiral? ;)

@Calvin'sHobbies Well, presumably I would post a program that writes the program... :) I was mostly asking to see if it was worth trying, because I think python might actually be able to beat 64ki. Although I actually have to get it to work first :p

GolfScript, N = 4
This one right rolls as original spec.
.. .
...#
.#.~
],8-

Here are the unrolls:
    ...
    #..
    ..
],8-~#.

       .#.
       ...
],8-~#. ..

          ..
          .#
],8-~#. ....

            ..
],8-~#. ....#.

              .
],8-~#. ....#..

],8-~#. ....#...

Try it here

How did you think of this arrangement?

@proudhaskeller It's better if you don't know ...

Did you brute-search a solution?

Special challenge: can you make one out of .s and #s?

I like the trailing ~. Maybe I can steal it for N=3?

Note that I didn't look for an N=4 solution because the spec specified that N be 4

@JanDvorak I tried a lot for N = 3 with all the techniques at hand. Feel free to look for it.

APL, N = 3
201
340
5|0

Unrolled:
   32
   40
5|001

     43
5|00102

       4
5|001023

5|0010234

Try it online.
It calculates the remainder of that number divided by 5. Only the result of last line is printed.
APL, N = 2
⍬∞
≡0

Unrolled:
  ⍬
≡0∞

≡0∞⍬

Try it online.
≡ returns the depth (not to be confused with the dimension or length) of an array:

0 is not an array. So the depth is 0.
0∞ is an array with two items 0 and ∞ (infinity). It has depth 1.
0∞⍬ has another item ⍬, which is an empty array with depth 1. So 0∞⍬ has depth 2.

These two programs also works in the online interpreter. I'm not sure if the later one is syntactically correct.
⍬0
≡∞

⍬¯
≡0

APL, for any N >= 4
For N = 4:
∞  ∞
 ∞∞
∞ ∞
⍴1↓∞

Fully unrolled:
⍴1↓∞  ∞  ∞ ∞ ∞∞∞

For N = 5:
∞   ∞
 ∞ ∞
 ∞∞
∞  ∞
⍴1↓ ∞

Fully unrolled:
⍴1↓ ∞   ∞   ∞  ∞  ∞ ∞ ∞∞∞

1↓ removes an item in the array. It also returns the empty array if the argument is scalar. ⍴ gets the array length.

Any explanations?

@proudhaskeller Edited.

You can ideally use the same depth logic for any N. Thanks to APL

@Optimizer It is not that easy. Things before the last line still have to be syntactically correct. So I can't use most of the functions or other punctuation characters like ()[] as they will appear at some unwanted place.

I meant like:  ⍬ \n⍬⍬0\n≡ ∞ (Not exactly that, but you get the idea)

@Optimizer ∞0 ⍬ ⍬⍬ is the array consisting of ∞, 0 and 3 empty arrays. It also have depth 2.

I basically meant that the depth technique can be used in N = 3 case as well.

@Optimizer But it doesn't work. Feel free to post another answer if you can fix it. I'll try some different techniques for N >= 4.

I don't know APL

@Optimizer Well, I think the array length will work for N >= 4. I'll edit soon. Did you think the depth should mean length or something?

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Pixel art, episode 2: Display the map 1-1 of Super Mario Bros
Last challenge (Pixel-art, episode 1: display Super Mario) was just a training... (and you completed it in amazing ways, thanks!)
This time, you have to work a little bit more. You have to display all the first overworld map of Super Mario bros on NES, without enemies, and without Mario.
Your program or function must display all the pixels of the following image OR produce an image file similar to it (BMP, PNG, or GIF).
Your program must not access the internet in any way.
The output can be zoomed if you want, and the pixels can be ASCII or HTML elements if you want, as long as they have the right color.
Here's the model you have to follow:

The whole image: https://i.stack.imgur.com/2kfVc.png

The tileset (if you need it): http://img.ctrlv.in/img/14/10/19/5443f44c7eb78.png

You can produce your own tileset, subset or superset of this one.
You can use your tileset as a separate image file or include it in your code (for example, in base64). If it's separate, add its size in bytes to your score.
The map with coordinates: http://goo.gl/c8xJIx or http://img.ctrlv.in/img/14/10/19/544373adc9f64.png

The colors:

Sky blue: #5C94FC
Black: #000000
Pink: #FCBCB0 (for the blocks and the castle)
Brown: #C84C0C (for the blocks and the castle)
Orange: #FC9838 (for the "?" block)
Light green: #80D010 (for bushes, mountains, flagpole, warp)
Dark green: #00A800 (for bushes, mountains, flagpole, warp)
White: #FCFCFC (clouds)
Light blue: #3CBCFC (clouds)

Shortest answer wins.
EDIT: There will be two score boards, one where scores are counted in bytes and one where they are counted in characters.
Good luck!
P.S: Here are some notes that could help you optimizing your program:

Clouds, bushes and mountains have a repeating pattern (every 48 columns)
Flying blocks are only present on lines 4 and 8
Each tile or sprite of the map uses at most 4 colors (including blue or transparent, depending on how you see it)
Bushes are just "top of clouds" with a diferent color palette
Single, double and triple bushes/clouds can easily be formed using the same mini set of 16x16px pieces. This is also true for the single and triple mountains

Is episode N going to be making playable 1-1?

hey, stop spoiling! :D (btw: no)

You might want to specify that you can't just download the image and show it.

@BetaDecay I could but... the frontier is very thin between including an image and producing a similar image programatically. Also, I'm curious to see someone else make another hardcoded solution in less than 4012 chars. Theoretically, the hardcoded image could fit in less than 2400 Unicode characters.

FYI I added lots of information in the OP (map, palette, tileset)

I never realised the bushes were the tops of the clouds... Well well well!

@BetaDecay NES developpers were the code-golfers of the 80's ;) All the SMB game (dozens of sprites, palettes, sounds, musics, physics engine, game engine, AI, ...) fits in 32kb. It blows my mind. This challenge is a tribute to it, btw.

@xem: There's one tile missing in your tileset: complete dark green (for the hills), f.e. in the large map at (2, 11). I'd suggest to replace the redundant complete blue tile above the hill in the tilemap, like this: http://img.ctrlv.in/img/14/10/19/54439ba9d530d.png

@xem: Another one: The castle has complete brick blocks (f.e. at (202,10)) that differs from the other brick blocks (f.e. at (168,8)) which have orange lines at the top. Updated tileset: http://img.ctrlv.in/img/14/10/19/5443f44c7eb78.png

thanks again and sorry for not noticing that earlier

@xem it would probably be a good idea to put the images on the i.stack.imgur.com server (use the upload image tool) so they don't magically disappear.

Done. I also added info on how to use and count the score of the tileset.

Is PPM out ok, and is it ok to expect a data file to be written in over stdin?  I can try and do the UTF-8 string in an eval instead of a separate file, but things will be much more readable if I just put the gzipped data file separately.

@Will Sorry, I don't know what PPM means, but basically, yeah, your program can use any file, gzipped or not, passed in argument or used directly using its path. Your score will be the size of your program (in chars) + the size of your files (in bytes)

PPM is an image format: Portable PixMap.

The reference image is incorrect, the right-most hill spot is in the wrong location, and the bushes are not repeated correctly. You can compare it to your grid image, or http://www.mariomayhem.com/downloads/mario_game_maps/super_mario_bros_maps/SuperMarioBros-World1-Area1.png

I'm sorry, I can't spot the error you're talking about. Is it the mountain on the right of the map? where should it be if instead?

Look at the spots on the mountain on the gridded version (grid 3,11) verses your reference image - the spots should be on the left of the tile, not the right. Your bushes look like they are shifted to the right one pixel, this causes part of the black outline to be cut off when they repeat.

Its a real shame that it comes down to whether you can compress the source code as well as the data; rather than going the unicode eval route which makes for an ugly entry, can't we just count the lzma size of the python sourcecode?

@Will Sorry for this rule that doesn't please everyone. To fix it, I'll make two leaderboards, ine where scores are in bytes and one where scores are in characters. So go ahead, and don't worry about Unicode or lzma.

@xem no no no, its not that bad a case of sour grapes ;)  Keep things as they are; python too can do the eval trick although perhaps statically-typed languages can't follow.

x86 Machine Code, 1729 1619 1468 1382 Bytes
How it works: Tiles are generated by a combination of RLE compression, 2bit images, and procedural code. Once the tiles are generated in memory, the program then creates a matrix of tile indexes. This is first loaded with the repeating background. After that, the pipes, floating blocks, pyramids, and the flag pole are drawn procedurally. The pipes, hills, bushes, and pyramids can extend below the ground, but are covered up when the rock tiles get written next. Finally, the castle tile values are simply copied into the correct location.
To generate the image file, the BMP header and palette is stored in the file as data, and is written first. The program then runs through the matrix, writing the appropriate row from the corresponding tile for each position.
Usage: Run mario.com, it will generate "m.bmp", a standard BMP image file. The file is created as a hidden file, since that ended up being less bytes.
Download a ZIP file containing the source code and binary, plus output.

Assembly code to generate the executable file:
org 100h
code_start:

;xor    cx,cx
mov    cx,12+14+256*3
mov    dx,filename
mov    ah,0x3c
int    21h
mov    bx,ax
push   ax

;mov    dx,BITMAPFILEHEADER
inc    dx
inc    dx
mov    ah,0x40
int    21h

mov di,tiles
xor ax,ax
mov ch,48
rep stosw

cwd             ; load the cloud sprite
mov si,cloud
call    DrawSprite
call    DrawHill

mov dx,14*256+12*16
PipeTileLoop:                ;Pipe
mov si,pipe0
call    DrawSprite
sub dh,2
jns PipeTileLoop

mov dx,32+12*16
call    DrawSprite
mov dh,13
;mov     si,pipe2
call    DrawSprite

cwd
xor ax,ax                ; move to the tile array
mov cl,6
MoveTileLoop:
call    MoveTile
loop    MoveTileLoop
mov word [BITMAPFILEHEADER+5+2],0x607     ; bushes
sub dl,3*16
mov cl,13
jnc MoveTileLoop

mov dx,0x1004
mov si,ball
call    DrawSprite
mov dl,0
call    MoveTile

xor bx,bx       ; pole
pole:
mov word[bx+tiles+22*256+7],0x707
add bl,16;
jnc pole

mov word [BITMAPFILEHEADER+5+2],0x805      ; qbrick
mov si,qbrick
call    DrawSprite
call    MoveTile

mov byte[BITMAPFILEHEADER+5+3],4

mov al,1            ; bricks & castle
call    Clear
mov al,23
call    MoveTile        ; black door
mov dx,0x800+64
BrickLoop:
xor dh,8
mov si,bricks
call    DrawSprite
sub dl,dh
jg  BrickLoop

cwd
call    MoveTile         ; left window
call    MoveTile         ; castle brick
mov al,3
mov di,image+15*256+16
mov cl,16
rep stosb
mov al,26
mov dl,16
call    MoveTile         ; reg brick

;mov     dl,32
;mov     si,door
call    DrawSprite
;mov     dl,32
call    MoveTile        ; door top
mov dx,48 +8*256
;mov     si,cren
call    DrawSprite
push    si

mov dh,0
call    MoveTile        ; crenulation 1
mov si,image+48+256  +4
mov di,image+48+256*9+4
mov bl,7
CrenLoop:
mov cl,7
rep movsb
mov dl,256-7
add si,dx
add di,dx
dec bx
jnz CrenLoop
mov dl,3*16
call    MoveTile        ; crenulation 2

pop si
mov cl,3
jmp skip
LastLoop:
;call    MoveTile        ; right window
                 ; block
                 ; rocks
call    DrawSprite
skip:
call    MoveTile
loop    LastLoop

xor ax,ax              ; Begin drawing world using the tiles
call    Clear
mov bl,48*4
BackgroundLoop:
lea di,[bx+image+2*256]
SmallHill:
mov al,10
mov cl,5
HillRow0:
stosb
inc ax
loop    HillRow0
mov dword [di+256-4],10+11*256+256*256*14
mov byte [di+512-3],15
sub di,256-10
cmp di,image +256
ja  SmallHill

mov si,fluff         ; draw clouds, bushes
FluffDrawLoop:
lodsw
add ax,bx
add ax,image
xchg    ax,di
lodsb
aam
mov cl,ah
;call    DrawFluff;

mov ah,1
FluffLayer2:
stosb
inc ax
push    cx
rep stosb
inc ax
stosb
pop cx
add di,256-2
sub di,cx
inc ax
dec ah
jns FluffLayer2

cmp si,pa
jl  FluffDrawLoop

sub bl,48
jnc BackgroundLoop

;mov     si,pa
mov cl,6
PipePlace:
lodsw
xchg    bx,ax
mov di,image
mov word [bx+di],18+19*256
PipeLoop:
dec bh
mov word[bx+di],16+17*256
jnz PipeLoop
loop    PipePlace

;mov     si,dba          ; draw the various floating blocks
mov cl,4
DrawBlockLoop:
lodsw
xchg    ax,bx
mov ah,bl

cwd
lodsb
BlockLoop:
mov bl,al
mov byte [bx+di],ah
lodsb
cmp al,dh
mov dh,al
ja  BlockLoop

dec si
loop    DrawBlockLoop

mov bx,198+256*12
FlagPole:             ; Draw flag pole
mov byte [bx+di],22
dec bh
jg  FlagPole
inc si
;mov     si,pyr            ; pyramid blocks
mov cl,8
PyrMainLoop:
lodsw
shr ah,1
cwd
inc dx
jnc NoNeg
neg dx
NoNeg:
mov bx,ax
PyrDrawLoop:
mov byte [bx+di],32
dec bh
jnz PyrDrawLoop
add ax,dx
dec ah
jnz NoNeg
loop    PyrMainLoop

;mov     si,ground        ; ground blocks
;mov     di,image
mov bl,4
push    di
GroundLoop:
lodsb
xchg    ax,cx
mov al,33
rep stosb
lodsb
add di,ax
dec bx
jnz GroundLoop
push    si
inc ch
mov si,di
sub si,cx
rep movsb

pop si
pop di
;push    di
;mov     si,copy         ; Draw Castle, flag ball
mov  dl,6
CopyLoop:
lodsw
mov cx,ax
shr cx,12
and ah,15
xchg    bx,ax
CopyRun:
lodsb
mov [bx+di],al
inc bx
loop    CopyRun
dec dx
jnz CopyLoop;

xor ax,ax
xor bx,bx ; image y        ; write the image to file
pop dx
WriteTileStep:
WriteRowStep:
mov bl,0 ; image x
WriteStep:
pusha
mov ah,[bx+di]
mov bx,dx
add ax,tiles
xchg    ax,dx
mov cl,16
mov ah,0x40
int 21h
popa
inc bx
cmp bl,212
jb  WriteStep
add al,16
jnz WriteRowStep
inc bh
cmp bh,14
jl  WriteTileStep
;pop     bx
;mov     ah,0x3e
;int     21h

;ret

DrawSprite: ; dx=x,y, si=data
pusha
mov bp,dx
;cwd
mov di,temp
push    di
lodsw              ; w, h*2+flag
mov dl,al
shr ah,1
pushf
mul ah
xchg    bx,ax
popf
jc  BitMapped
RunLoop:
lodsb
mov cl,al
shr cx,2
sub bx,cx
rep stosb
jnz RunLoop
jmp MoveData
BitMapped:
BitMappedLoop:
lodsb
mov cl,4
BitMappedQuad:
stosb
shr ax,2
loop    BitMappedQuad
sub bx,4
jg  BitMappedLoop
MoveData:
mov bx,sp
mov [bx+4],si
pop si
mov bx,di
lea di,[bp+image]
mov dh,-1
MoveLoop:
mov cl,dl
rep movsb
sub di,dx
cmp si,bx
jl  MoveLoop
popa
ret

MoveTile: ; dx =x,y, bx=y,ax=t-1
inc ax
pusha
mov si,dx

xchg    al,ah
xchg    di,ax
mov ax,16
TileLoop:
mov cl,16
TileTrans:
mov bx,[si+image]
inc si
and bx,3
mov bl,[bx+BITMAPFILEHEADER+5]
mov [di+tiles],bl
inc di
loop    TileTrans
add si,256-16
dec ax
jnz TileLoop
popa
add dl,16
ret

Clear: ; al = value
mov di,image
mov ch,48
rep stosb
ret;

DrawHill:
pusha
xor bx,bx
mov al,3
HillLoop:
lea di,[bx+image+6*16]
inc byte [di]
inc di
mov cl,16*5-2
sub cl,bl
sub cl,bl
rep stosb
inc byte [di]
inc bx
inc bh
cmp bl,16
jl  HillLoop

mov si,spot
push    si
mov dx,32-7+256*8 + 6*16
call    DrawSprite
mov dl,32+17    + 6*16
pop si
call    DrawSprite
mov dx,5*16      + 6*16
call    DrawSprite
popa
ret

filename: db 'm','.'
BITMAPFILEHEADER: db 66,77,'P',0,12,0,1,2,3,0,26,3,0,0
BITMAPCOREHEADER: db 12,0,0,0,64,13,224,0,1,0,8,0
colors: db 252,148,92,0,0,0,252,252,252,252,188,60,176,188,252,12,76,200,0,168,0,16,208,128,56,152,252

;pal: db 0,1,2,3
cloud: db 88,32,224,5,114,5,228,5,122,5,224,5,122,5,228,9,106,5,6,5,240,102,5,4,5,240,5,86,5,10,5,252,5,78,5,4,5,6,5,252,4,13,66,5,8,5,92,13,16,17,136,5,14,7,42,5,100,9,14,5,4,9,18,9,4,9,120,5,14,11,14,7,18,5,96,5,26,5,34,5,10,9,116,5,26,7,22,5,84,13,18,11,18,15,34,9,108,5,38,5,6,5,84,5,22,27,6,23,38,108,5,34,5,4,5,88,5,10,19,14,19,18,7,34,5,108,9,26,5,92,5,10,7,10,7,26,7,54,5,120,5,18,5,92,5,10,7,46,7,46,5,128,17,56
spot: db 6,17,245,95,255,245,93,87,127,245,87,127,245,223
hilltop: db 16,3*2,0x9, 0x33, 0x9, 0x8, 0xD, 0x1B, 0xD, 0x1C, 0x19, 0x14
ball: db 8,17,80,5,244,31,253,127,253,127,249,127,249,127,228,31,80,5
pipe0: db 64,5,0x90,0xFA,0xAA,0xAE,0xFF,0xFF,0xBB,0x06,0xA9,0xAF,0xAA,0xEB,0xFF,0xFF,0xBB,0x6B,0x90,0xFA,0xAA,0xAE,0xFF,0xFF,0xAE,0x06,0xA9,0xAF,0xAA,0xEB,0xFF,0xFF,0xEF,0x6A
pipe1:db 32,4,8,113,8,129
pipe2:db 32,12,5,23,26,79,9,122,133
qbrick: db 16,33,85,85,85,85,254,255,255,127,222,255,245,119,254,191,246,127,254,191,254,127,254,255,245,127,254,191,246,127,254,191,86,127,254,215,106,127,254,218,107,127,254,218,107,127,254,90,233,127,254,171,250,127,222,255,255,119,254,255,255,127,168,170,170,42
bricks: db 8,16,33,14,5,30,5,30,5,18,33,30,5,30,5,30,5
door: db 16,32,0xFD, 0xFD, 0x89, 0x6, 0x39, 0xA, 0x39, 0x6, 0x41, 0xA, 0x31, 0x6, 0x5, 0xE, 0x29, 0xA, 0x5, 0x16, 0x19, 0x12, 0x5
cren: db 16,17,213,255,255,85,234,0,192,170,234,0,192,170,234,0,192,170,234,0,192,170,234,0,192,170,234,0,192,170,255,0,192,255
block: db 16,32,61,6,7,53,6,5,11,45,6,9,15,37,6,13,19,34,17,19,34,17,19,34,17,19,34,17,19,34,17,19,34,17,19,34,17,19,34,17,15,6,35,17,11,6,43,13,7,6,51,9,6,59,5
rocks: db 16,33,86,149,87,149,171,106,171,90,171,127,171,106,251,85,171,106,95,170,173,106,165,170,173,106,171,170,182,106,171,170,182,106,171,170,182,106,171,170,246,127,171,170,102,149,171,170,118,106,171,170,182,106,171,170,182,106,171,170,182,106,254,255,231,191
fluff: db 8,10,11,     19,11,11,       27,10,31,       36,11,21,    11,1,34,    23,1,14,       41,1,24
pa: db 28,3,38,4,46,5,57,5,163,3,179,3
dba:db 21,5
qb: db 16,21,23,78,106,109,112,170, 21,9
qb2: db 22,94,109,129,130, 27,5
ba: db 20,22,24,77,79,94,100,101,118,129,130,168,169,171  , 27,9
ba2: db 80,81,82,83,84,85,86,87,91,92,93,121,122,123,128,131,0
pyr: db 137,5*2+1,140,5*2,151,5*2+1,152,5*2+1,155,5*2,188,9*2+1,189,9*2+1,198,4
ground: db 69,2,86-69-2,3,153-86-3,2,256-153-2,0
copy: db 202,2+5*16,26,26,24,26,26,   202,3+5*16,26,26,28,26,26,    202,4+5*16,29,30,30,30,29,   203,5+3*16,31,26,25,  203,6+3*16,29,29,29, 198,12+16,20
temp: rb 256*48
tiles: rb 34*16*16
image:

Incredible! There are still people out there writing assembly :D

+1000 Easily the best entry!  So, no standard libraries at all eh?  That's really simply leagues ahead smaller than the HLL entries :D

Javascript minified (*): 1285 1258 1253 1205 1186 1171 characters
(*) Minified using Closure, RegPack and ObfuscaTweet, as suggested by xem
Unicode version is 4549 bytes in size, without ObfuscaTweet (Closure and Regpack only), size is 2251 bytes.
History:
1285 -> 1258: variable A for 48 (thx @hsl), merged some of the for loops, merged mt() and mu(), using tile indices instead of tile strings, optimized png with PNGOUT
1258 -> 1253: merged some more for loops; renamed mt() to r(); removed unnecessary braces; variable B for 16; defining 16 unused CSS sprites (replaces 32 with A); showing 1 unused row (replaces 14 with B); removed function e(); shortened t(), g(), c(); using for(i=0;i<n;)f(i++) instead of for(i=0;i<n;i++)f(i) where possible
1253 -> 1205: moved body style to CSS part instead of <body style=...>; replaced some for loops with f calls; optimized functions r,q; </head><body> seems to be unnecessary, <html><head> too; function t(i) for CSS mapping removed; CSS names b0..b31 instead of a..z,aa..ff
1205 -> 1186: function n renamed to N; new function n that operates on an array with delta coding
1186 -> 1171: hills and warps can be drawn "big" anytime, the lower parts get overdrawn by stone blocks; use d for both clouds and bushes; removed some unnecessary semicolons
This is a procedural attempt. There are patterns everywhere, one of the magic numbers is 48 (tile gap between clouds, bushes and mountains). The tileset is encoded as Base64 data url string and used as a CSS stylesheet. In Javascript, the 212x14 array m is filled with tile indices. See the commented unminified version for more details.
Works in Chrome 38 (Ctrl+T for new tab, Ctrl+Shift+J for javascript console, paste code there) and Firefox 33 (if wrapped with HTML javascript tags). There's a JS bin version, too.
There's still some room for optimizations, I'll post updates and it would be nice if some JS/CSS/HTML people could suggest optimizations/corrections.
Minified:
eval(unescape(escape('').replace(/uD./g,'')))

Unminified and commented:
// map width
W=212;
// helper constants
A=48;B=16;
// array containing the map, generated at runtime
m=[];
function w(s){document.write(s)}
// set a map tile
function N(i,s){m[i]="b"+s.toString()}
function n(i,s){z=0;for($ in i){z+=i[$];N(z,s)}}
// set a row of map tiles (index a..a+b)
function f(a,b,s){for(k=a;k<=a+b;)N(k++,s);}
// set a block of map tiles (index a and b define upper left and lower right corner)
function g(i,j,s){for(x=i%W;x<=j%W;x++)for(y=i/W|0;y<j/W|0;)N(y++*W+x,s)}
// helper for clouds and bushes - j=1..3 sets map tiles to XYZ, XYYZ or XYYYZ
function c(i,j,a){N(i,a);f(i+1,j-1,a+1);N(i+j+1,a+2)}
// clouds/bushes
function d(i,j,a){c(i,j,a);c(i+W,j,a+16)}
// hill
function p(i){N(i+2,8);n([i+213,211],23);n([i+214,211,2],24);n([i+215,213],25);N(i+426,9)}
// warps
function q(i){N(i,10);N(i+1,11);l(i+W,3,26);l(i+213,3,27)}
// stairs - d=1 for upwards, d=0 for downwards
function r(i,d){for(j=0;j<4;j++)f(i+d*(3-j)+j*W,j,0);}
// set a column of map tiles (index i, height j)
function l(i,j,s){for(k=0;k<j;k++)N(i+k*W,s);}
// fill map with sky tiles
f(0,2967,7);
// clouds and bushes - some of the bushes will be overdrawn by blocks and the castle, so draw them first
for(i=0;i<4;i++){d(231+i*A,1,4);d(248+i*A,2,4);d(451+i*A,3,4);d(432+i*A,1,4);d(2343+i*A,3,17);d(2355+i*A,1,17);d(2373+i*A,2,17)}d(624,1,4);N(2539,19)
// '?' blocks
n([870,72,15,20,1,734,5,2,55,28,3,3,58],3)
// brick blocks and castle
f(928,7,2);f(939,2,2);f(969,2,2);n([976,3,737,2,2,53,2,15,6,18,11,1,38,1,2],2);N(1900,B);g(2322,2535,B);g(2325,2538,B);f(1687,2,13);N(1899,29);N(1901,31);f(2110,4,13);f(2111,2,15);N(2324,14);N(2536,30)
// big and small hills - one of the big hills will be overdrawn by the stairs, the small hills are big hills overdrawn by stone blocks
for(i=0;i<5;i++){p(1908+i*A);p(2135+i*A)}
// warps (often overdrawn by stone blocks), stairs and block below pole
q(1742);q(1753);q(1946);q(2148);q(2283);q(2299);r(1830,1);r(1844,1);r(1877,1);r(1033,1);r(1836,0);r(1851,0);g(1881,2520,0);l(1037,4,0);l(1848,4,0);l(1885,4,0)
// pole
N(410,12);l(622,9,28);N(2530,0)
// lower row of stone blocks
f(2544,423,1);
// gaps in stone blocks
g(2613,2826,7);g(2630,2844,7);g(2697,2910,7)
// HTML start and CSS spritesheet base (tileset PNG encoded as base64)
w("<style>body{width:3400px}div{background:url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAQAAAAAgBAMAAAAPh7vXAAAAG1BMVEVclPwAAAAAqADITAyA0BD8/Pz8vLD8mDg8vPyQWLLUAAACwklEQVR4XrWWS4rjMBCGXcxjrfKje23hA4wRJNtJ8AEmi4JsTUD7phd9gkCOPSWN5OiRttsx8xGJ2CKpj99SJcVOW8bdv+miHd+U5VfxRaQDE/y61jz91FqpHrFSPb/rFRctXEW8KF668E31b+w/LG+BAOIXBOoh4uDX1c4ImCLIVFxcmaEKbSMYc4FXWz8QACKxLFBKyQLS02YCaAkEbAQ4CaBj//GuVJgANESnryRgBLqjZLquyxJAh9rx9GIEtGKcwKh6n8H+Q2G1DwQaYgFYJSCP+SPo0VKZ+HkkAj1WgcDre58IUCO2JLAsoPU4J3DmDLYmgI5MIN8Db68qEAA6X+lKp2cTwBfN4IS/DgSyY/je412g4er0RAL++PrvRYe/nheYTgEgOQSsTQCOUiwLWKUXFTcinAQa8ohGrEygNt1gWUAjCwSGJoG9FwCaOJFYlYAXwE8o9IhMjxfbjII+ED6CHxQgxLoESivgs0WHvy40GioursdIgFsxulYMDQWcko0IiGImgSWBES09FzdjWgh/jBqKiAXQFMCZX0OQUswIuOuq5zHywIQlAXR1paPIP25n/IRpd0aZiiRkighXQVpaOd20z+A4BI3w+2/XBzDB3HskUPPnYpozGc55AKULoGwfCHTdUwLImyiL4GoUrlkCIL2AFE8mgI57sYERIo3gdqXbjR3iCMq7QDufAH7CtDtjgcMhESAufzuzAvMn2wElsomYTSA8AeFJeCzQpQ8BkA34ZQMQaQBt2Zp5JoEVAjbCoxHIMjgR0wT1QXoBaRDPJJDtAWB7JhOAhgQSIQQLZSzQrt8DeR/Aevo/nSgApn/MQSaI7X0ABs8B2H6eUia02/tAPUzUSwIgM8TmPjAEHGBdAEy7tQ/gEFKLdQEwYlsfgCFGrAuAaZME/qMAyIeIbX2gjgQOawNg2rV74C9KQ+xyNDQoswAAAABJRU5ErkJggg==)}")
// generate CSS classes 'b0'..'b31' for the 32 used tiles
// this actually generates 16 additional unused classes to reuse the constant A and save 1 byte
for(i=0;i<A;i++){j=(i%B)*-B;k=i>15?-B:0;w(".b"+i.toString()+"{background-position:"+j+"px "+k+"px;width:16px;height:16px;float:left;}")}
// some more HTML
w("</style>")
// body of HTML contains all tiles as <div> elements arranged in <span> columns
for(x=0;x<W;x++){w("<span class=b0>");for(y=0;y<B;){w("<div class="+m[y++*W+x]+"></div>")}w("</span>")}

Very impressive for a first draft, and thanks for putting so many efforts into it. Here are a few optimizations you could use: remove , ,  tags, type="text/javascript", (or text/css) attribute, minify your JS code (use http://closure-compiler.appspot.com/home), then pack it ( use http://siorki.github.io/regPack.html) then obfuscate it in Unicode chars (use http://xem.github.io/obfuscatweet/). But please, if you do so, keep the "unminified" version in your answer so thah people can read it. To count your score in number of chars, use https://mothereff.in/byte-counter. ;)

Also, no need to document.write closing tags alone (you can remove 'w("")'), no need to put quotes around the values of your style and class attributes. You can remove all the style of your "new" body element, excemt its width. Then, on the JS side: no space after "for", no ";" before "}", no line-breaks, ... (but any JS minifier will remove those extra bytes for you)

also, try hosting your code on http://c99.nl, it may fix your graphical issue with bushes and clouds

Semicolons are automatically inserted at the end of lines, so you can safely remove those.

@hsl, I guess you suggest removing trailing semicolons. I'd rather suggest removing line breaks, i.e. pass that code through a minifier :)

@xem I prefer line breaks because they make the code look neater and cut down on horizontal scrolling, but removing newlines works too and has the same char count.

Thanks for all the advice, as you can see, most of it worked :) The graphical issues were already resolved in the second version.

You could shave off a few characters by storing 48 as a variable and using that in all the for loops.

That's unminified!?!?!?!?

@AnubianNoob: Yep :D. It's still golfed, though. Perhaps I'll post more info on what the code does later.

You may want to replace your s with s (it's shorter, plus, you don't have to close  tags.) As mentioned before, document.write closing tags alone is unnecessary. So, I think you can remove 'w("")'

@xem: If there is content inside the tag, you have to use closing tags. Both replacing <div> and removing </span> won't work, see http://jsbin.com/jovexaqezu/edit (<p></p> instead of <div></div>), http://jsbin.com/kameqohegi/edit (no </p>) and http://jsbin.com/zesudeyaxa/edit (no </span>)

function l(i,j,s){for(k=0;k<j;k++)n(i+k*W,s);} can be shortened by extracting k++ to the function, I think? So can the next line with j.

@schnaader sorry, I mixed up document.write("...") and document.body.innerHTML += "...". With the latter, closing tags is not necessary. But it doesn't matter very much.

(How many bytes is this?)

@Will: As stated in the answer, the score is 1171 characters (Unicode) or 2251 bytes (ASCII). The ASCII byte score can be reproduced by running Closure and RegPack on the unminified and commented code.

Javascript, 1069 1072 1024 characters (1957 bytes)
RegPacked and Obfuscatweeted
eval(unescape(escape('').replace(/uD./g,'')))

Unobfuscated code
I hid this code because there's ungolfed code below.

function R(s,t){return new Array(t+1).join(s)}
function b(n){return"<div style='background: url(data:;base64,iVBORw0KGgoAAAANSUhEUgAAAQAAAAAgBAMAAAAPh7vXAAAAG1BMVEVclPwAAAAAqADITAyA0BD8/Pz8vLD8mDg8vPyQWLLUAAACwklEQVR4XrWWS4rjMBCGXcxjrfKje23hA4wRJNtJ8AEmi4JsTUD7phd9gkCOPSWN5OiRttsx8xGJ2CKpj99SJcVOW8bdv+miHd+U5VfxRaQDE/y61jz91FqpHrFSPb/rFRctXEW8KF668E31b+w/LG+BAOIXBOoh4uDX1c4ImCLIVFxcmaEKbSMYc4FXWz8QACKxLFBKyQLS02YCaAkEbAQ4CaBj//GuVJgANESnryRgBLqjZLquyxJAh9rx9GIEtGKcwKh6n8H+Q2G1DwQaYgFYJSCP+SPo0VKZ+HkkAj1WgcDre58IUCO2JLAsoPU4J3DmDLYmgI5MIN8Db68qEAA6X+lKp2cTwBfN4IS/DgSyY/je412g4er0RAL++PrvRYe/nheYTgEgOQSsTQCOUiwLWKUXFTcinAQa8ohGrEygNt1gWUAjCwSGJoG9FwCaOJFYlYAXwE8o9IhMjxfbjII+ED6CHxQgxLoESivgs0WHvy40GioursdIgFsxulYMDQWcko0IiGImgSWBES09FzdjWgh/jBqKiAXQFMCZX0OQUswIuOuq5zHywIQlAXR1paPIP25n/IRpd0aZiiRkighXQVpaOd20z+A4BI3w+2/XBzDB3HskUPPnYpozGc55AKULoGwfCHTdUwLImyiL4GoUrlkCIL2AFE8mgI57sYERIo3gdqXbjR3iCMq7QDufAH7CtDtjgcMhESAufzuzAvMn2wElsomYTSA8AeFJeCzQpQ8BkA34ZQMQaQBt2Zp5JoEVAjbCoxHIMjgR0wT1QXoBaRDPJJDtAWB7JhOAhgQSIQQLZSzQrt8DeR/Aevo/nSgApn/MQSaI7X0ABs8B2H6eUia02/tAPUzUSwIgM8TmPjAEHGBdAEy7tQ/gEFKLdQEwYlsfgCFGrAuAaZME/qMAyIeIbX2gjgQOawNg2rV74C9KQ+xyNDQoswAAAABJRU5ErkJ)-"+(n%16)*16+"px -"+(n/16|0)*16+"px;width:16px;height:16px;float:left}'></div>"}
function M(s){m="";for(_ in s)m+=b(parseInt(s[_],32));return m}
function C(s,a){c="";for($ in a)c+=$%2?M(a[$]):R(s,a[$]);return c}
O="<body style='width:3392px'>";
O+=R(s=b(7),212);
O+=R(C(s,[19,"456",14,"4556",8]),4);
O+=C(s,[6,"c",13]);
O+=R(C(s,[8,"456",8,"klm77777455567777kllm",8]),4);
O+=C(s,[6,"s7456",9]);
O+=R(C(s,[8,"klm",16,"klllm",16]),4);
O+=C(s,[6,"s7klm",31,"3",57,"222222227772223",14,"3",11,"22277772332",56,"00",8,"s",200,"000",8,"s",199,"0000",8,"s",198,"00000",8,"s7777ddd",22,"377723232",21,"ab",9,"ab",18,"232",14,"2777772777773773773777772",10,"22",6,"0770",10,"00770",12,"2232",12,"000000",8,"s7777tgv",8,"8",35,"ab",6,"qr778",6,"qr",39,"8",37,"007700777787770007700",26,"000000077778777s777dfffd",6,"nop",13,"8",10,"ab",8,"qr",6,"qr7nop",5,"qr",6,"8",31,"nop",13,"8",21,"0007700077nop700007700077787ab",14,"ab700000000777nop77s777ggegg77877no9op",6,"hiiijnop7777hij77qr",8,"qr7hiij7qrno9op7777qrhiiijnop7777hij",15,"hiij777no9op",6,"hiiijnop",4,"hij",12,"0000ii0000no9o00000770000jnopqr77hij",9,"qr00000000077no9op70777gguggjnop7"]);
O+=R(C(b(1),[69,"77",15,"777",64,"77",57]),2);
document.write(O);

Ungolfed code

function repeat(s, t) { var S=s; while(t-- > 1) S += s; return S; }
function block(n) { return "<div style='background: url(data:;base64,iVBORw0KGgoAAAANSUhEUgAAAQAAAAAgBAMAAAAPh7vXAAAAG1BMVEVclPwAAAAAqADITAyA0BD8/Pz8vLD8mDg8vPyQWLLUAAACwklEQVR4XrWWS4rjMBCGXcxjrfKje23hA4wRJNtJ8AEmi4JsTUD7phd9gkCOPSWN5OiRttsx8xGJ2CKpj99SJcVOW8bdv+miHd+U5VfxRaQDE/y61jz91FqpHrFSPb/rFRctXEW8KF668E31b+w/LG+BAOIXBOoh4uDX1c4ImCLIVFxcmaEKbSMYc4FXWz8QACKxLFBKyQLS02YCaAkEbAQ4CaBj//GuVJgANESnryRgBLqjZLquyxJAh9rx9GIEtGKcwKh6n8H+Q2G1DwQaYgFYJSCP+SPo0VKZ+HkkAj1WgcDre58IUCO2JLAsoPU4J3DmDLYmgI5MIN8Db68qEAA6X+lKp2cTwBfN4IS/DgSyY/je412g4er0RAL++PrvRYe/nheYTgEgOQSsTQCOUiwLWKUXFTcinAQa8ohGrEygNt1gWUAjCwSGJoG9FwCaOJFYlYAXwE8o9IhMjxfbjII+ED6CHxQgxLoESivgs0WHvy40GioursdIgFsxulYMDQWcko0IiGImgSWBES09FzdjWgh/jBqKiAXQFMCZX0OQUswIuOuq5zHywIQlAXR1paPIP25n/IRpd0aZiiRkighXQVpaOd20z+A4BI3w+2/XBzDB3HskUPPnYpozGc55AKULoGwfCHTdUwLImyiL4GoUrlkCIL2AFE8mgI57sYERIo3gdqXbjR3iCMq7QDufAH7CtDtjgcMhESAufzuzAvMn2wElsomYTSA8AeFJeCzQpQ8BkA34ZQMQaQBt2Zp5JoEVAjbCoxHIMjgR0wT1QXoBaRDPJJDtAWB7JhOAhgQSIQQLZSzQrt8DeR/Aevo/nSgApn/MQSaI7X0ABs8B2H6eUia02/tAPUzUSwIgM8TmPjAEHGBdAEy7tQ/gEFKLdQEwYlsfgCFGrAuAaZME/qMAyIeIbX2gjgQOawNg2rV74C9KQ+xyNDQoswAAAABJRU5ErkJ)-" + (n%16) * 16 + "px -" + (n/16|0) * 16 + "px; width: 16px; height: 16px; float: left; }'></div>"; }
function blocks(s) { var S=""; for(var i in s) S += block(parseInt(s[i], 32)); return S; }
var output = "<body style=width:3392px>";
output += repeat(block(7), 212);
output += repeat(blocks("777777777777777777745677777777777777455677777777"), 4);
output += blocks("777777c7777777777777");
output += repeat(blocks("7777777745677777777klm77777455567777kllm77777777"), 4);
output += blocks("777777s7456777777777");
output += repeat(blocks("77777777klm7777777777777777klllm7777777777777777"), 4);
output += blocks("777777s7klm777777777");
output += blocks("777777777777777777777737777777777777777777777777777777777777777777777777777777772222222277722237777777777777737777777777722277772332777777777777777777777777777777777777777777777777777777770077777777s7777777777777");
output += blocks("777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777700077777777s7777777777777");
output += blocks("777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777000077777777s7777777777777");
output += blocks("777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777770000077777777s7777ddd777777");
output += blocks("7777777777777777377723232777777777777777777777ab777777777ab7777777777777777772327777777777777727777727777737737737777727777777777227777770770777777777700770777777777777223277777777777700000077777777s7777tgv777777");
output += blocks("77877777777777777777777777777777777777ab777777qr778777777qr7777777777777777777777777777777777777778777777777777777777777777777777777777700770077778777000770077777777777777777777777777000000077778777s777dfffd77777");
output += blocks("7nop777777777777787777777777ab77777777qr777777qr7nop77777qr77777787777777777777777777777777777777nop777777777777787777777777777777777770007700077nop700007700077787ab77777777777777ab700000000777nop77s777ggegg77877");
output += blocks("no9op777777hiiijnop7777hij77qr77777777qr7hiij7qrno9op7777qrhiiijnop7777hij777777777777777hiij777no9op777777hiiijnop7777hij7777777777770000ii0000no9o00000770000jnopqr77hij777777777qr00000000077no9op70777gguggjnop7");
output += repeat( repeat(block(1), 69) + blocks("77") + repeat(block(1), 15) + blocks("777") + repeat(block(1), 64) + blocks("77") + repeat(block(1), 57), 2);
document.write(output);

I first made tiles into sprites with @schnaader's minified data URI. 0 ~ v (which is 0 ~ 31 in base 31) represents each tile.
And I converted map to tiles by hand. This data has 212 characters per row.
Then I replaced repeating character (like 7(sky) and 1(ground)) with repeat().
I found 7s and some blocks, and another 7 pattern is repeated. So I made another function to make it compact. You can see it at unobfuscated source code.
Finally I RegPacked, and Obfuscatweeted my 2341 bytes golfed code.
It was very funny challenge. Thanks! And thanks to @xem for more tricks.

Let's get dirty. Here are some tips to lose a few dozen chars: you can remove the quotes in  and in . You can write your  and . You can remove the leading "image/png" and the trailing "ggg==" in your base64. You can omit the
Good work! I thought my procedural attempt would beat coding the map, now I have something to catch up with ;)

Python3 1638 1576 1616 1513 bytes
581 code + 932 data

↑ This top is the original level.  In the middle is the PPM generated by this script.  At the bottom is a diff, and this shows that the palette and the map do not agree exactly!  I put this down to data glitch and not my script ;)
# 759808 is 212*14 tiles at 16*16 each - the size of the map
import lzma;B,E,R,X=bytearray,759808,range,16
D=B(lzma.decompress(open("i","rb").read())+B(E)) # put canvas on end of data array
i,P=8218,lambda x,y:8622+y*54272+x*X # 8622 is length of decompressed data
def Q(s,n,d): # copies a 16x16 tile from s to d
 # n is the stride for the source s, which is different for put and copy
 for m in R(0,256,X):e=d+m*212;D[e:e+X]=D[s+m*n:s+m*n+X]
for j in R(4): # there are 4 command sections
 j&=1;i+=1+j;r=D[i-1]<<8 # j is now truthy if this is a copy buffer
 for k in R(D[i]): # this many commands
  a,b,w,h,c,d=D[i+1:i+7];q=h>32 # unpack it; put doesn't use all these
  # do the put/copy
  for z in R(((a,h-32)[q],w*h)[j]):Q((D[(i+4+z,i+5)[q]]<<8,P(a+z%w,b+z//w))[j],1+211*j,
      (P(b+z,w),P(c+(z%w,w-z%w-4)[r&1],d+z//w))[j])
  i+=((3+a,5)[q],6)[j&1];r>>=1 # move i to next command
for y in R(2,11):Q(28<<8,1,P(198,y)) # special case flagpole
o=open("o","wb");o.write(b"P6 3392 224 255 ") # header for PPM
for c in D[8622:]:o.write(D[8192+c*3:][:3]) # decompress palette to RGB

(bytes counted without comments, line-unwrapped and second level indent being \t)
Data (base64-encoded to be pasted; decode and save as a file named "i"):
/Td6WFoAAATm1rRGAgAhARwAAAAQz1jM4CGtA2JdAACA3BlsBrac0zEPcSPZ/qSCuw0fuG0WYiRk
w+pNfoBEsFJBEXgxJ73nEPREKmuJUHyg+jhBTQcbUI0gChatJ7D6ZqYmLz4P34OFSxUMWF+aGhm2
+8mNqw264w0JIjW9ogeNpJX6pgH/xJ/D2qlfqfCuz0cOR1sPAAcMrue1y9joUaDauFLj8QhbExen
lQkUMfMePbMnn4nJ0aVXBeHdKIwSeFQdFz/Aj695kKi0x8+MXR84cpNh3U8y7deiyjbNyIgu7vLn
WBxzXhEtrV9svBETfQpxj2qYI11ALgWlhoxdoABE3ocVgE1Qo35dnoJe+1DJFvqIzFOoxSJEckUk
T89RIjARdA/Ax6UTiitivZp4EhM+xczasrm+2XFy68mA96xmEMKp9ZpoApNIU0ShMMW1Im0QFeuS
aCl43qJuintArMAeDiOlmkbDNzMzHZIgDFeklUnnKG9xHXPQXNQVyJ9I7z+rLHh1VtuXDyAErKTL
VY/Xai2pIUlSt5H1KGEExdHu3O17XKbar11Jad6nFjDKOZFwamJQTFIG6dru2UXVJq29pGCnKLlB
lOmls4agigMI7QJ5K/Rzf15ZuIQ7U9MKJ3E4llbwqs6vDk+Ln/ceRVfl5Fm/Ne056ZLDp6VIf5zs
EMWra8UnjndkigqAyp8D62AcrPFIp9EdJmgiGzfhNCQ1JptRN/z01mNomtwVJfqeLTqgvRgXXG3P
8p+6s1rjEfblMBNyMxdYvJZXLE0wgu4xhH3fiNTT+RyTIJ1MZZ1zhksfe2SnNTbL2JYGven1WPfI
YP+M4NI/vpQ4bGsuJ8w//x01GpkTLfMZtZgBhx0dx1Wu9i0JY9hhtoI2/tGR4sNHfpSs7xD/Zz+7
6Z18z3AQn4dC7Trp0WndI/zS8eRZlRgKxA/lb09MZ87ugbXnm2+oBQFSLEtg/rqg398pDWx9W4Zk
6GeRTqvp9CJ9meMagUnGHKnAj+05PE0XgEXO6r9B8ltgoHf0+wXFevBHVupfiH9MApUxd0TPzv16
Y5Rfjxao0wLcIbxKMd3vtI1rCvOdq0OysWNrtcH9EBKjx9+CnGFBFZI9w9kCMJ8ZT0m9nsNYPelL
29KbQMt+K213+7o0MS3DxeGTHSW9CiEOTzNeqvsXN6IcIxjJIkgH8MuAAAAA5PpImPBeeH8AAf4G
rkMAALsE5byxxGf7AgAAAAAEWVo=

The data file is a custom format I made for this problem and is stored as LZMA.
First all 32 tiles are serialized.  There are 9 colours in the palette, and this takes 8219 bytes uncompressed.  (I found that trying to compress the tiles at 4-bits-per-pixel didn't help compression at all.  I did not try and brute-force the best ordering of the tiles, and I probably lose a few points here.)
There are 212x14=2968 blocks making up the map.
Then the instructions to recreate the map are now encoded.
First comes a section of "put" commands that place some sequence of tiles from the tile-palette on the map at a particular x,y.  As there are 32 tiles, I specify a run of the same tile using a number bigger than 32 rather than the tile index.
Then comes a section of "copy" commands that copy some rectangle of the current map to some other place.  There is a special bit-mask that marks if the copy should be mirrored.
A short example command buffer:
16, # there are 16 put commands
3, # place 3 tiles
8,2, # dest x, y
4,5,6, # these three tiles
3, # place 3 tiles
8,3, # dest x, y
20,21,22, # these three tiles
5, # place 4 tiles
27,2, # dest x, y
4,5,5,5,6, # these five
...,
8, # bits set if copy reversed (high 8 bits of a uint16 mask)
14, # there are 14 copy commands
8,2, # src x, y
3,2, # w, h to copy
19,1, # dest x, y
1,9, # src x, y
3,2, # w, h to copy
16,10, # dest x, y
...,
13, # there are 13 put commands
...
7, # bits set if copy reversed (high 8 bits of a uint16 mask)
15, # there are 15 copy commands
...

(I said short, but that's actually nearly half the total command buffer needed to make the whole map; the vast majority of the bytes in the data are the 32 source tiles themselves)
Then comes a second section of "put" commands and finally another section of "copy" commands.
Because these can overwrite each other, I can build copy parts that I later erase or change.
I can doubtless shave a few more bytes off it by - for example - turning puts into small copies and by doing the eval trick on a gzipped source-code, or playing with PNG (which is DEFLATE with image-specific filters) too.  But I like things verbose as they are.

Great work! About the diff, if the images of the OP are wrong (which is totally possible, I made that with paint), can you please provide better images for the map (or better values for the palette, idk). Thanks :)

Also, all the clouds and bushes appear in the diff. Do you think it's because of colors or because of an offset of 1-2 pixels between the two images? Looks like an offset to me

@xem I don't think the problem is so bad and I don't think it needs urgent fixing.  In your map the tile at 3,11 seems to be missing from the palette.  There seems to be some noise in the map around 20,12 and the general outline of trees and clouds may be an off-by-one alignment glitch in the palette?  There's only 9 colours, so it can't be any kind of blending artifact.

the bricks are totally my fault yeah :D. I tried to hide a goomba and made a 1px offset. I didn't touch bushes and clouds at all though. But I think your image is righter than mine, so I take it :p

I also failed hiding mario and all the other goombas in front of mountains, actually, d'uh. Thanks!

using your correct image in my hardcoded entry (http://codegolf.stackexchange.com/a/40010/10732) helped a lot! Almost 100 chars less :)

I updated the OP with your correct image, you can remove your diff ... or update it to show that your image is equal to ...your image :)

JavaScript: 3620 (ouch) 3429 3411

Updates

Update #1: Removed var definitions and put the variable declarations inside brackets of first use. Removed getElementById() as it is also available on load as a varaible by ID. Using cloneNode() instead of createElement('CANVAS'). Renamed main from xMx to M. Removed the scaling feature :(, (still available in the example.)
Added some comments to the expanded code. (That code is not updated with the removals. The line below, ("Mini code"), is.)

Update #2: Removed the main function M() as a whole and let the code run at root. This would require the code be placed inside a load wrapper or at end of document.

Update #3: Added statistics.

Mini code:
K=126,f=['#000','#c84c0c','#fc9838','#00a800','#80d010','#fcbcb0','#3cbcfc','#fcfcfc'],X='Å=!15d>KIRiE%>?D^?C^FVNBTJ@M^>>]ANtN?ZCW]@QM4Gb1>EVWEZAEZN@VfMI?MPckVAwNEZWNV>Q]@YT2n6d@%vN4Gb@MABMALT>JTABM>Qz@FCTI`ZEE@L?E@CDD{EE@L_A5G>%>IVEB_DHTCC{PC{HDzlz]A4o5d>KIR5G}LZ?YZIAZI`ZH]LE]BBVL>VBHXLEXBLMLAM3n7y$",2EEKIR&O30y$",2E}?Q6&o9y$",2EbD?Q6&n2pI`ZJNM`BRG~J`M`CRO9dBKIRibPC@NMBNB]6n0dBKIRib>C@CVBCE]6n1dBKIR6n3y*",~1F0G%Ii%1R6Ob")",?-1n4y*",BK0G%1Ri%I6Ob")",In8dEKIRib"*",b1F0G%Ii%1R6O>%CCD8Gb")",An9p@ciuB?LFD?`RC?Ji~F?JRBc6OUdBKIAib1Bciu1>?JFDtDM>DV>DZ>DX>QtQM>QV>a>>PT>PwPr>Pa>s>WT[][M[V[Z[XAI]AIMAICAo1eKIREJ`NGuv`3G~>{AB@MC@JJ@SJES2o2eKIREI`NGBKJ`2GCKAEABBfPT>PwPr>Pa>s>WT[V[Z[XAI]AIM^T^_^r^aA^vATA@VA@ZA@XAJ]AJSO0dHKQFXRC{NzB@D@ZNG}r>>Z>@TBB@Mw>F?C[>>^MJ@VABTACVAE_3GF%Cr>EFMP_[FAO3dHKIFFBFB[FNG}w>FMBHTFZ>HwDFS?HCACFJGFK@T>>>>{ZCCMF@VX>>PtPBE[CBACSO5dH%WBHL[ELBPLGbWwQT@W@S[v@aABDLO4dH%1>?@JB?B4Gb1?]^>v@MJBCLGF%1B]AVvESodHK?EF_@3G}w>FMBEMECMEtZ>>HSndH%I?EF`zCBP|}XSt@a>BX>CaB`M>R>>>YMBREAo3duH?J6o4d~EPFiu`]@FP|bFDVREVN]N[>CEa[aAIV>`CAo6dEK?Cl?E7G}YF9GE%BHWG>K>BRMCF?DHBDDHBN@HBI{LJ@C3o7eKIRi>K?B@?@MB?S>?CATSCMAEV@?V2o8eKIR6O6y(",E%H4&O7y(",bHCF3&O8y(",>%H4&&&#;Ø=Kxt3r@6X>8_J1ZA3TJ6VA8>>@PM2D{5HM7F@L0ES2C@L5BS7zBU>JG>x>>>3a>6a>8rA1rA3_A6_A8T[M3>M5DM7PS0FS2HS5CS7EMU@JG@x>M3PM6PM8HS1HS3ES6ES8BS?T3>T5DT7PBA0FBA2HBA5CBA7ETU@LGBx?M3Hz6DM8E@J1FS3B@J6CS8>zPT2DBB5HT7FBL0EBA2CBL5BBA7{BU>LGu1PM3FM6HM8CS1ES3@S6BS8?MDT2HT5FT7EBA0CBA2BBA5{A7>TU?LGE%1a>3Z>6r>8VA1_A3MA6TA8tDM2HM5FM7ES0CS2BS5@S7>MU?JGF%1^>2L>>4^@5s7^>8jA0lA1jA3lA5lA6l>U`|H%1fB2N>>4f@6kB7f>9kJ0gL2kA3gJ5gA6g>UR|D%1`>>2`>>4N>>6L>>7L>>9fA1^A2^A4kA5jA6sUY|P%^Al>4s6`>>9lA1Lv4`v6^hL>>UsJ]5I]9Qc4Rc9NIG1bL>>5^>9jA4lh`|1>%f>5k>9gA4R>hN|1@%1Y]6`c1Lc6[>UW]@a5?a9DPA4FPhCWG1~kAR>>4g>6N>>9Rv1fA4Nv6khf>Ug>[>4W]9Yc4`c9LIG1uNvg>5f>6Rv0kA1Nv6fhR>>21k>L]5[>9Wc4Yc9`IG1E%IB6P7ALE8WB6N5`B5HI@6P7AJE8W@6N5`@57G1F%1FX2>X2BX7Dm0Fm0Pm1@m7?X2@V9CCA0PCA2PC2G1Hx?X2@X2CX7HX7PX9Cm0?m1Dm2PDJ6DDJ7>X8?CD9>CL2>CL2DCA3>NG1D%13N>N4kN4g`5`>N8^W9gA3`?L4I?L4W?N5`?L8J?Q3FPJ4?PJ5?PL5EPJ8BPY3Hm4?m5>DJ5Em8CDR8EH`8FFN8HEL8DC2G1Pxg>3g>4R>>5lA6Lv7s3Q]4R]5Y]4Fa5HWqb2s3s4l>5gA6Nv8k>3W]4Y]5Q]4Ha5DWq>xQc6Lc7W]3Da4FX5HQq@xWc6Nc8I]3Pa4HX5DQq~19Qc9DPhDDhDHhDFhDEhDChDBhDJqu19mqE%Uf@U`>@UJ?@U`?@Uf@U`>@UCXUBP3qF%U@PEUBH3qH%UNIqD%UNAqP%UBQG3bUEQ&&';'B%?KAG@B@@p"%2_>>AC%]>j>H>G2e%O2O1DAY>I>W>6GA9Q>J>:K:%?A?%P>E1E>A>?>A?F>H1D>P1C>20B>@AF1D19,&GC1@>B1%?@1?17,&,6,5,8,4,3,>12,0,1,'.match(/../g).forEach(function(v){X=X[u='split'](String.fromCharCode(K--))[U='join'](v);if(K==92)K=91});eval(X[u]('*')[U]('f')[u](')')[U]('d')[u]('(')[U]('b')[u]('&')[U](']')[u]('%')[U]('[')[u]('#')[U]('}')[u]('!')[U]('{'));function e(k,d,i){for(s[Y]=k,i=0;i<d[L];)s.rect[G](s,d.slice(i,i+=4))}function _(d,i,q){for(S.width=R,i=0;i<d[L];++i,s.fill(),s.beginPath())F[q=d[++i][0]]?F[q](d[i]):e(f[d[i-1]],d[i])}F={$:function(d){_(Å[d[1]].concat(d.slice(2)))},b:function(d){_(Å[d[1]].slice().map(function(i,x){return(x=d[2].indexOf(i))>-1?d[2][++x]:i}))},f:function(d,i){for(s[Y]=f[d[1]],s.moveTo[G](s,d[2]),i=3;i<d[L];++i)s.lineTo[G](s,d[i])},d:function(d,x,y,g){for(s[Y]=f[d[1]],g=d[2],y=g>0?0:15,x=0;x<R;++x,y+=g)s.rect(x,y,1,1)}};R=16;c.width=3392;c.height=224;;S=c.cloneNode();c=c[G='getContext']('2d');s=S[G]('2d');c[Y='fillStyle']='#5c94fc';c.rect[G='apply'](c,[0,0,3392,224]);c.fill();for(k=0;k<Ø[L='length'];++k)for(_(Å[Ø[k]]),t=Ø[++k],i=0;i<t[L];i+=3)for(j=0;j<t[i+2]*R;j+=R)c.drawImage(S,t[i]*R+j,t[i+1]*R)

Blah blah:
– Demo at end of post.
Using canvas as base for an attempt to solve this. Ended up with about 6000 chars, but after some fiddling (and a custom compression - with fiddling and tweaks on that as well) I'm now at the stated number. Still high, but then again the quality is good ;-).
It also includes a scale option, first argument to the xMx(), aka "main" function. 1 = normal size (as in 16 bit tiles). There is not much room for tweaking, so if one use fractions some of the tiles does not fit best together. At whole numbers it should be OK. [1]
But: warning, going up, quickly eats resources and makes for a huge canvas. (It is all painted in one go.) When the original width is 3392 pixels it quickly becomes huge. [1]
[1] As of update #1 this has been removed. It is present in the demo.

Stats:

Main code           　:  870
Compression:

Main data         : 2176   (17,480 bits)
Key               :  128   ( 1,024 bits)
Code              :  236
Whole she bang    : 2540
Decompressed data : 5608   (44,864 bits)

Total               　: 3410                　 [1]

[1]: +1 byte, ";", between the main / data code.
The compressed data is one array, Å, and one "object", Ø. Where Å is holding the tile placement and the Ø holding the data for painting the tiles. The Ø should have been an array as well – but as my code started out with something like this:
var tiles = {
   brick: [
        ...
   ],
   qmark: [
        ...
   ],
};

It ended up as is. I'll perhaps see if I can't fix this. Ideally I would have made it parseable with JSON instead of eval(), but that would not be a point in a contest like this. As it is now it can not be JSON parsed due to missing quotes around the id parts.

Demo
Here is a fiddle where one can view the code in action. The code in the fiddle I have expanded somewhat (And added some HTML / CSS styling around the world – but the image of itself is self sustained.):
MARIOS WORLD

Expanded code:
Expanded and (a bit) rearranged code:
var D, C, c, S, s,   // Document, canvas and shadow canvas.
    R, F, Z, X,
    Ø, Å,            // Due to the compression we have a couple of non-ascii
    K,               // variable names.
    L = 'length',
    Y = 'fillStyle',
    u = 'split',
    U = 'join',
    f = [
        '#000',    '#c84c0c', '#fc9838', '#00a800',
        '#80d010', '#fcbcb0', '#3cbcfc', '#fcfcfc'
    ]
;

/* ----------------------- data unpackeer and loader ------------------------ */
X='Å=!15d>KIRiE%>?D^?C^FVNBTJ@M^>>]ANtN?ZCW]@QM4Gb1>EVWEZAEZN@VfMI?MPckVAwNEZWNV'+
'>Q]@YT2n6d@%vN4Gb@MABMALT>JTABM>Qz@FCTI`ZEE@L?E@CDD{EE@L_A5G>%>IVEB_DHTCC{PC{H'+
'Dzlz]A4o5d>KIR5G}LZ?YZIAZI`ZH]LE]BBVL>VBHXLEXBLMLAM3n7y$",2EEKIR&O30y$",2E}?Q6'+
'&o9y$",2EbD?Q6&n2pI`ZJNM`BRG~J`M`CRO9dBKIRibPC@NMBNB]6n0dBKIRib>C@CVBCE]6n1dBK'+
'IR6n3y*",~1F0G%Ii%1R6Ob")",?-1n4y*",BK0G%1Ri%I6Ob")",In8dEKIRib"*",b1F0G%Ii%1R'+
'6O>%CCD8Gb")",An9p@ciuB?LFD?`RC?Ji~F?JRBc6OUdBKIAib1Bciu1>?JFDtDM>DV>DZ>DX>QtQ'+
'M>QV>a>>PT>PwPr>Pa>s>WT[][M[V[Z[XAI]AIMAICAo1eKIREJ`NGuv`3G~>{AB@MC@JJ@SJES2o2'+
'eKIREI`NGBKJ`2GCKAEABBfPT>PwPr>Pa>s>WT[V[Z[XAI]AIM^T^_^r^aA^vATA@VA@ZA@XAJ]AJS'+
'O0dHKQFXRC{NzB@D@ZNG}r>>Z>@TBB@Mw>F?C[>>^MJ@VABTACVAE_3GF%Cr>EFMP_[FAO3dHKIFFB'+
'FB[FNG}w>FMBHTFZ>HwDFS?HCACFJGFK@T>>>>{ZCCMF@VX>>PtPBE[CBACSO5dH%WBHL[ELBPLGbW'+
'wQT@W@S[v@aABDLO4dH%1>?@JB?B4Gb1?]^>v@MJBCLGF%1B]AVvESodHK?EF_@3G}w>FMBEMECMEt'+
'Z>>HSndH%I?EF`zCBP|}XSt@a>BX>CaB`M>R>>>YMBREAo3duH?J6o4d~EPFiu`]@FP|bFDVREVN]N'+
'[>CEa[aAIV>`CAo6dEK?Cl?E7G}YF9GE%BHWG>K>BRMCF?DHBDDHBN@HBI{LJ@C3o7eKIRi>K?B@?@'+
'MB?S>?CATSCMAEV@?V2o8eKIR6O6y(",E%H4&O7y(",bHCF3&O8y(",>%H4&&&#;Ø=Kxt3r@6X>8_'+
'J1ZA3TJ6VA8>>@PM2D{5HM7F@L0ES2C@L5BS7zBU>JG>x>>>3a>6a>8rA1rA3_A6_A8T[M3>M5DM7P'+
'S0FS2HS5CS7EMU@JG@x>M3PM6PM8HS1HS3ES6ES8BS?T3>T5DT7PBA0FBA2HBA5CBA7ETU@LGBx?M3'+
'Hz6DM8E@J1FS3B@J6CS8>zPT2DBB5HT7FBL0EBA2CBL5BBA7{BU>LGu1PM3FM6HM8CS1ES3@S6BS8?'+
'MDT2HT5FT7EBA0CBA2BBA5{A7>TU?LGE%1a>3Z>6r>8VA1_A3MA6TA8tDM2HM5FM7ES0CS2BS5@S7>'+
'MU?JGF%1^>2L>>4^@5s7^>8jA0lA1jA3lA5lA6l>U`|H%1fB2N>>4f@6kB7f>9kJ0gL2kA3gJ5gA6g'+
'>UR|D%1`>>2`>>4N>>6L>>7L>>9fA1^A2^A4kA5jA6sUY|P%^Al>4s6`>>9lA1Lv4`v6^hL>>UsJ]5'+
'I]9Qc4Rc9NIG1bL>>5^>9jA4lh`|1>%f>5k>9gA4R>hN|1@%1Y]6`c1Lc6[>UW]@a5?a9DPA4FPhCW'+
'G1~kAR>>4g>6N>>9Rv1fA4Nv6khf>Ug>[>4W]9Yc4`c9LIG1uNvg>5f>6Rv0kA1Nv6fhR>>21k>L]5'+
'[>9Wc4Yc9`IG1E%IB6P7ALE8WB6N5`B5HI@6P7AJE8W@6N5`@57G1F%1FX2>X2BX7Dm0Fm0Pm1@m7?'+
'X2@V9CCA0PCA2PC2G1Hx?X2@X2CX7HX7PX9Cm0?m1Dm2PDJ6DDJ7>X8?CD9>CL2>CL2DCA3>NG1D%1'+
'3N>N4kN4g`5`>N8^W9gA3`?L4I?L4W?N5`?L8J?Q3FPJ4?PJ5?PL5EPJ8BPY3Hm4?m5>DJ5Em8CDR8'+
'EH`8FFN8HEL8DC2G1Pxg>3g>4R>>5lA6Lv7s3Q]4R]5Y]4Fa5HWqb2s3s4l>5gA6Nv8k>3W]4Y]5Q]'+
'4Ha5DWq>xQc6Lc7W]3Da4FX5HQq@xWc6Nc8I]3Pa4HX5DQq~19Qc9DPhDDhDHhDFhDEhDChDBhDJqu'+
'19mqE%Uf@U`>@UJ?@U`?@Uf@U`>@UCXUBP3qF%U@PEUBH3qH%UNIqD%UNAqP%UBQG3bUEQ&&';

K = 126;  // Key pos (char) counting down.
('B%?KAG@B@@p"%2_>>AC%]>j>H>G2e%O2O1DAY>I>W>6GA9Q>J>:K:%?A?%P>E1E>A>?>A?F>H1D>P'+
'1C>20B>@AF1D19,&GC1@>B1%?@1?17,&,6,5,8,4,3,>12,0,1,').match(/.{2}/g).forEach(
    function (v) {
        X = X[u](String.fromCharCode(K--))[U](v);
        if (K === 92)
            K = 91;
    }
);

/*
* Initially JSON, but got lost in compression work + a somewhat bad design
* on the obj. to begin with. Is eval, at least for now.
*
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
try {
    eval(X
    [u]('*')[U]('f')
    [u](')')[U]('d')
    [u]('(')[U]('b')
    [u]('&')[U](']')
    [u]('%')[U]('[')
    [u]('#')[U]('}')
    [u]('!')[U]('{')
    );
} catch (e) {
    console.warn(e);
}

// Scaling function
function z(a) {
    return a.slice().map(
        function (v) {
            return v * Z;
        }
    );
}
// Tile painter "normal tiles"
function e(k, d, i) {
    for (s[Y] = k, i = 0; i < d[L];)
        s.rect.apply(s, z(d.slice(i, i += 4)));
}
//
function _(d, i, q) {
    S.width = R;
    for (i = 0; i < d[L]; ++i) {
        s.beginPath();
        F[q=d[++i][0]] ? F[q](d[i]) : e(f[d[i-1]],d[i]);
        s.fill();
    }
}
F = {
    $ : function (d) {  // Expand a tile (e.g. add border on top
                        // of "normal" bricks as with the "in-air".
        _(Å[d[1]].concat(d.slice(2)));
    },
    b : function (d) {  // Replace colors. (Used for bushes.)
        _(Å[d[1]].slice().map(
            function(i,x){
                return(x = d[2].indexOf(i)) > -1 ? d[2][++x] : i;
            }
        ));
    },
    f : function (d, i) { // Free-paint (fill). E.g. "hill-sides"
        s[Y] = f[d[1]];
        s.moveTo.apply(s, z(d[2]));
        for (i = 3; i < d[L]; ++i)
            s.lineTo.apply(s, z(d[i]));
    },
    d : function (d, x, y, g) { // Diagonal lines.
        s[Y] = f[d[1]];
        g = d[2] * Z;
        y = g > 0 ? 0 : 15 * Z;
        for (x = 0; x < 16 * Z; x += Z, y += g)
            s.rect(x, y, Z, Z);
    }
};
// Main function.
function xMx(h, k, i, j, t) {
    Z = h || 1;
    R = 16 * Z;
    D = document;
    C = D.getElementById('m');              // Doc canvas
    c = C.getContext('2d');
    S = D.createElement('CANVAS');          // Memory canvas
    s = S.getContext('2d');

    C.width  = 3392 * Z;
    C.height =  224 * Z;
    c[Y] = '#5c94fc';
    c.rect.apply(c, z([0, 0, 3392, 224]));  // Blue sky (rest is tiles)
    c.fill();

    for (k = 0; k < Ø[L]; ++k) { // Loop coordinate array. This has fixed
        _(Å[Ø[k]]);              // order.
        t = Ø[++k];
        for (i = 0; i < t[L]; i += 3) {
            for (j = 0; j < t[i+2] * R; j += R)
                c.drawImage(S, t[i] * R + j, t[i+1] * R); // Apply tile.
        }
    }
}

xMx(); // Load main.

woah, That's great! +1 for the nice presentation in the provided link. +1 for the homemade packer. If only you could avoid using non-ASCII chars (like Å,Ø), you could use tools like http://xem.github.io/obfuscatweet/ to compress (much) more, because the score is counted in chars.

You don't need to use var to declare variables; they are automatically declared when you define them, so you should be able to remove var D,C,c,S,s,R,F,Z, from your code. (also you can replace /.{2}/ with /../.)

@hsl: Yes, thank you. I thought of doing the removal of var but left it as I had to run when I posted it. Done now. The RegExp was a nice one, somehow did not manage to see that ;)

@xem: Thank you. There is no problem using the Unicode trick with ÆØÅ as those are within the first set (0x80+0xNN) where 0xNN is the interesting part. I was not sure, however, if that was "legal" as it depends on how one view it. A code point above 0x7f has a length of 2. As such the code would be equal in length (+1 byte if odd - or, actually longer by 45 bytes due to the ev(a|i)l routine). If it is "legal" then OK.

You're right, those chars are okay: eval(unescape(escape('').replace(/uD./g,'')))works as intended. And yes, your score is counted in characters so you can totally use tricks like Unicode compression and eval.You could have a score near 1750 with that!

Python 1331 1326 1314 1272 1268 1217 bytes
(code: 219 214 202 186 182, data: 362+750=1112 363+723=1086 346+689=1035)
The idea here is that I first generate a map one 16th the size in each dimension, where each pixel is colored by the index in the tile map. To ensure that the same pallette was used, I first combined the given tile map and the map into a single image. From this and the tile map (both minified pngs) we can now regenerate the original map. (The code for this process can be seen below the submission code). It should be noted that I saved the tile map as a file "t" and the generated map as an image "m"
EDIT: I started exploring how the ordering of the tiles influenced the compression, and for the sake of exploration I generated 10000 random permutations and compressed them with this result:
This was all with the tiles in one line, as that reduced the code quite a bit. I tried similar things with different configurations (2*16, 4*8), but none with a better average result.
Assuming that png would compress better with greater continuous similar regions, I built a tool that would let me move the tiles around, and using what I perceived to be a more continuous image I got the tile image down to 723 from 750b.
EDIT2: Afte rmuch (much) more analysis on how png actually works, and a lot of experimenting (still ongoing), the images have now been compressed even further. Link below updated. I'll write more about this analysis later when it is complete.
New images used are here: https://i.stack.imgur.com/gofpw.jpg
Here are the other images generated in the process: https://i.stack.imgur.com/9s1GD.jpg, though some are a bit outdated because of above edit.
import PIL.Image as I
O=I.open
t=O("t")
m=O("m").load()
o=I.new("RGB",(3392,224))
s=16
for i in range(2968):y=i/212;x=i%212;v=s*m[x,y];o.paste(t.crop((v,0,v+s,s)),(x*s,y*s))
o.show()

The script I wrote to reduce the map is pretty crude, but here goes (also might be outdated because of changes above):
from PIL import Image

blockSize = 16
combined = Image.open("combined.png")
tileImage = combined.crop((0,224,256,224+32))
w,h = tileImage.size

tiles = []
for y in range(0,h,16):
    for x in range(0,w,16):
        tiles+=[list(tileImage.crop((x,y,x+blockSize,y+blockSize)).getdata())]

referenceImage = combined.crop((0,0,3392,224))
w,h = referenceImage.size

mapImage = Image.new("RGB", (w/blockSize, h/blockSize))

colorScale = 256/len(tiles)

for y in range(0,h,16):
    for x in range(0,w,16):
        i = tiles.index(list(referenceImage.crop((x,y,x+blockSize,y+blockSize)).getdata()))
        mapImage.putpixel((x/16,y/16),(i*colorScale,i*colorScale,i*colorScale))

mapImage.save("map.png")

Wow, that's really impressive. And it's even more impressive when we see that you count in bytes and not chars. Congrats!

Perl 5 + PNG: 689 + 593 = 1282
A failed attempt to replace PNG compressed tile map from Christian's solution with Perl code. In the end it is 65 bytes longer. Takes the same PNG tiles on input and generates a PNG on the output.
Usage: perl mario.pl <tiles.png >world.png
eval'+s/\d+(<?)(.+?)\1/$2x$&/ge'x2?$x|=$_:
map{/A/&&y'{}['Y';push@l,split"";y/D-IMNOY[|_@-_/EF@EE}JKLY~__@/;
s'@Y'YY'g;s'y@'yy'g;s'@E'DE'g;s'E@'EG'g}($x)x$_
for@z=qw(256@ 1
4<19@MNO14@MNNO8@<6@I 1
5<8@MNO16@M3NO16@< 2
22@X57@8T3@3TX14@X11@3T4@TXXT56@YY 3
203@3U 1
16@X3@TXTXT21@[|9@[|18@TXT14@T5@T5@X2@X2@X5@T10@2T6@Y2@y10@YY2@y12@TTXT31@QPS 1
5<2@H45@< 38@[|162@U3VU 1
5<17@H30@< 28@[|133@[|14@[|21@PPWPP 1
4<11@A3BC7@ABC15@ABBC3@<10@PPRPPC48@2<69Z2@15Z3@64Z2@101Z< 1);
$p=GD::Image;use GD;$f=new$p(3392,224);$k=newFromPng$p('-');
copy$f($k,map$_*16,$i%256,$i++>>8,31&ord,0,1,1)for@l;print$f->png

JS: 4012 3921 chars
JS is used to unpack many Unicode characters and write an img tag which src is the image given in the OP, saved as PNG, compressed, encoded in base64 and trimmed.
document.write(unescape(escape('').replace(/uD./g,'')))

Demo: http://jsbin.com/fojidejoco/1/
PS: I know it's a little bit cheating (even if the rules allow it), but at least, it gives us a goal: do it in less than 4012 chars.
Tools used:

https://tinypng.com/
http://xem.github.io/miniURI/
http://xem.github.io/obfuscatweet/

I know that this is a non-optimal solution, but why have you answered your own question so soon?

An additional option would be to use a sprite sheet and an array of where the sprites go. o_O

@BetaDecay to get rid of this "hardcoded" approach asap and let people do something more creative, like, use a sprite sheet and an array. :p

Counting unicode characters as 'chars', seems little unreasonable. How many bytes is that uncoded into UTF-8?
If we are taking a char to be a single displayed unicode character, you can make arbitarily large unicode characters.

I disagree. There is a limited number of possible Unicode characters (U+0000 to U+10FFFF). whichever encoding you use (utf-8, 16, 32, ...) a character stays a character. Only the size in bytes varies.

And I would disagree with that. It's pretty easy to encode binary data as Unicode via simple methods, and thus we'll all end up writing uninteresting extra code in order to pretend binary data is really Unicode. That is the opposite of being creative in my opinion.

You can indeed encode up to 20 bits per Unicode character, and for this exact reason, I think it can lead to interesting and creative approaches.

Then the task really becomes two unrelated tasks - Encode the image data as small as possible, then convert the compressed data to as few Unicode characters as possible. I think the second task hinders being creative on the first, and would be better off as it's own challenge.

authors: Кондратьев Дмитрий

authors: สามารถ กัณหาบุตร


text:
Riemann Series Theorem
The Riemann series theorem states that the terms of a conditionally convergent series can be permutated such that the resulting series converges to an arbitrary value.
The Challenge
Write a program or function that takes in three parameters via stdin (or equivalent) or as parameters:

The expression for the sequence x_n (with variable n). The exact format (e.g., whether a power is represented as ^, pow() or **) is irrelevant and may be chosen to fit your language. Alternatively you may pass a function directly as an argument. The definition of the function does not count towards the byte count.
A value S that we want to approach. Numerical values only are fine, you don't need to support mathematical expressions.
A threshold t>0. Numerical values only are fine here as well.

Your program/function must output (to stdout or equivalent) resp. return a space- or newline-separated list p_1, ..., p_N of indices.
Your output must satisfy the condition that the sum from k = 1..N over x_(p_k) differs from S no more than t in terms of the absolute difference. In other words, it must satisfy

So far, since the output will be a finite number of indices, the order would not matter. Therefore, another restriction applies: with decreasing threshold t, you may only add indices to the output (assuming a fixed S).
In other words, for a fixed S, if t_1 < t_2 and [x_1, ..., x_N] is a solution for t_2, then a solution for t_1 must be of the form [x_1, ..., x_N, ..., x_M] with M >= N.
Details and Restrictions

The order of the arguments may be changed to suit your needs.
Provide an example call with the arguments from the example below. Ideally, post a link to an online interpreter/compiler.
eval and the like are explicitly allowed for the purpose of evaluating mathematical expressions.
Sequences are 1-based, so the first index is 1.
You don't need to take special care of big integers or floating point problems. There will be no extreme test cases such as using machine precision as the threshold.
Standard loopholes apply.
You may assume that the sequence passed to your program is conditionally convergent, i.e. that it is possible to solve the task with the given parameters.

Example
Say your program is in a file riemann.ext, then a call might be
./riemann.ext "(-1)^(n+1)/n" 0.3465 0.1

Scoring
This is code-golf. The shortest program in bytes (UTF-8 encoding) wins. In case of a tie, the earlier entry wins.

Why would you penalize answers for supporting expressions? :P

@Dennis score in code golf is the code length. You want to minimize the score.

@JanDvorak: Right, and subtracting -10 adds 10.

I shall change the wording. ;) edit: done.

Is it okay if we require such implementation crud in x_n as Javascript's Math.pow or Haskell's fromInteger for sequences that involve manipulating integers? (as in, assume the expression is eval-ready no matter how non-pseudocodey it is)

Yes, that was the idea. The challenge should not be to parse expressions.

If the task isn't to parse an expression, why can't we just input a function and save ourselves 6 characters or more?

I meant it shouldn't be to parse expressions yourself but have your language tools do it for you. Allowing anything but a string would sort of make it unfair between different languages, imho.

Namely, Haskell requires quite a bit of extra characters to eval stuff. Namely, it requires an import and it returns a value in the form IO(Maybe a), which requires fromJust and an IO action to undo. The former merely requires a bunch of characters, but the latter requires the resulting function to be an IO action (to load the dependencies).

Nearly every language I can think of supports passing function arguments in some sort. Even C has function pointers (but not eval). Even Java has objects (but not eval). Even in PHP you can name a global function. Even brainfuck... well... brainfuck doesn't even have eval. Allowing function input actually levels the playing field.

Point taken. You may pass functions. I'll change the description.

Requiring eval is unfair against languages that don't have eval (C++, Java...) or languages where eval requires quite a few extra bytes (Haskell - also, eval is an I/O operation) - and a solution in Assembly would be awesome to see.

note that your bonus doesn't really make much sense now. You're essentially awarding ten points for two function calls - and Haskell doesn't even distinguish between nullary functions and actual values (though you do have a feature called "polymorphic constants", which do act as nullary functions) - unless you want us to require a function that ignores its sole numeric argument

You're saying that the program has to be able to find a subset of an infinite set of terms defined by any symbolic expression that sums to within any arbitrarily small distance of any target sum?

@COTO as long as the symbolic expression represents a conditionally convergent function, yes

@JanDvorak: I'll upvote any submission that can find a solution for even one symbolic expression and run in less than a fortnight. :D

@COTO to within which precision?

@COTO got it. It works like a charm. Now I just need to do basic golfing.

@JanDvorak: Try ./riemann.ext "(-1)^(n+1)/n" 1e5 1, or ./riemann.ext "4*(-1)^(n-1)/(2*n-1)" 3.141592653589793238 1e-12. ;)

@COTO umm... the harmonic series doesn't grow quite that fast. Remember you have to actually output the indexes.

@COTO The latter keeps spitting out hundreds of indexes per second, too. At 15000 indexes I'm nearing three digits of precision. And I'm pretty sure a smarter algorithm (fewer indices) would be even slower ;-)

Well... this will take a while. But you've said "any symbolic expression", and I've got to choose one.

@JanDvorak: I know. Most conditionally convergent series converge painfully slowly. It's a trivial matter to choose a reasonably low target sum and a reasonably large target precision such that the routine will never converge simply due to the sheer number of terms needed. You can also try something like ./riemann.ext "4*(-1)^(n-1)/(2*n-1)" 1e-4 1e-7 and I suspect the sum would never converge.

I think there should be another restriction: any element of the sequence should, at some point, appear in the sequence for some arbitrary small t

That's a theoretical problem, though. I choose a rather benevolent precision in my tests.

@proudhaskeller my algorithm satisfies that

@JanDvorak: I know. ;)  A simple greedy algorithm that picks positive terms as long as the sum is too low, and negative terms as long as the sum is too high, will always find a solution, even if it takes forever. And if the sum contains complex-valued terms... well, you're pooched. :P

@JanDvorak I meant this should be a part of the restrictions of the challenge as every real permutation satisfies that

@COTO a simple greedy algorithm is what I'm golfing ;-) Note that the "every term appears eventually" restriction prevents any other solution.

@JanDvorak: Put 'er in and I'll vote for her. ;)

@COTO complex values? Umm... They don't seem to be required. Are they?

Somehow I don't think the Riemann series theorem even works in complex numbers... The harmonic series diverges, the alternating harmonic series converges, yet it's clearly not possible  no hit 0+1i as the limit as the terms are all real.

@JanDvorak: Absolute value is just the complex modulus in that case. All the same, complex numbers add a whole new dimension of hurt and you're wise to simply ignore them.

Unfortunately I'm not home. Does any answer claim the bonus? If not Jan is right that it makes little sense now and should be removed, but I don't want to upset anyone.

Two more things: 1) complex numbers can be ignored here, it won't happen. 2) it might be a few days before I can verify submissions correctly, I apologize for that.

Can we rearrange inputs? I'd like the sequence last.

Yes, it already says in the details that you are free to chose the order of inputs.

Python – 88
def R(x,S,t):
 I=[0,0]
 while abs(S)>t:
    i=I[S>0]=I[S>0]+1
    if x(i)*S>0:S-=x(i);print i,

I stores the indices for positive and negative numbers and to reduce the number of variables, I do not sum up to 0 until I reach S, but subtract from S until I reach 0.
I am not entirely sure whether this complies with the restrictions on the input.
The used algorithm should be very nice for a stack-based language.

So, this adds positive number until it reaches S and then adds negatives until it reaches 0 again? I'm afraid that this doesn't follow the spec

@proudhaskeller: No. If we forget about the subtraction trick, it either A) adds positive elements until the sum is larger than S B) adds negative elements until the sum is smaller than S. It alternatingly repeats those steps until the sum is sufficiently close to S. The subtraction trick is that instead of going from 0 to S by summation, I go from S to 0.

oh I see. I should be able to use in my code. thanks.

Haskell, 161 158 144
because Haskell can deal with infinite lists, instead of doing the parsing stuff this solution receives an infinite list as the sequence.
r l s t=unwords[show$[i+1|i<-[0..],l!!i==x]!!0|x<-s%filter(>0)l$filter(<0)l]where(g%j@(p:o))y@(n:b)|abs g<t=[]|g<0=n:((g-n)%j)b|0<1=p:((g-p)%o)y

example output:
*Main> let harm = zipWith (*) (cycle [1,-1]) (map (1/) [1..]) -- the alternating harmonic numbers
*Main> r harm 3 0.001
"1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 2 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307"

Damn it. And I thought my 162-character solution was kinda decent...

@JanDvorak was yours in Haskell too?

It was... I'm not done golfing, but don't think I can beat you.

I think I'm going to steal something...

@JanDvorak what is it that you are going to steal?

... or maybe not. I don't think I can work that into my solution. I am using partition in my code instead of a pair of filters.

The output doesn't look like indices to me since it's not integers. Am I misunderstanding something?

@IngoBürk oh it's supposed to be a list of indices? I missed that

Yes, it's supposed to be the indices in the order they should be added, separated by a space. Newlines are fine too though. What exactly do you output (out of curiosity)?

Ah, you output the actual permutated sequence. Gotcha. But it should be the indices instead. I'm sure it's not too hard to fix that :) printing separated by newline instead of whitespace is fine now too if that makes anything easier for you.

@IngoBurk if anything I would like to return a list or a [ ] enclosed comma-seperated list.

Yeah, I figured. But I think newline separated is a pretty common and sensible output format.

@IngoBürk Sure then. There isn't really a difference between spaces and newlines (just replace unwords with unlines).

Haskell, 206 characters
import Data.List
r t e f=unwords.map(show.snd)$(\(x,y:_)->x++[y])$span(\(s,_)->abs(t-s)>e)$m 0$partition(<(0,0))$zip f[1..] where m s(a@((b,c):d),w@((x,y):z))|s<t=(x+s,y):m(x+s)(a,z)|1>0=(b+s,c):m(b+s)(d,w)

The sequence itself is an implicit last argument. Usage:
r 2 0.001 [(-1)**(n+1) / n | n <- [1..]]

Beaten before even having been posted, but - oh well. Posted anyways. I also took the liberty of accepting an infinite list as my first argument.
readable version:
import Data.List
import Debug.Trace
riemannConverge :: (Integral ix, Num v, Ord v, Show ix, Show v) => (ix -> v) -> v -> v -> String
riemannConverge target maxError series =
    unwords $
    map (show . \(_,ix) -> ix) $
    (\(xs,y:_) -> xs++[y]) $
    span (\(s,_) -> abs (target - s) > maxError) $
    map (\x -> traceShow x x) $
    mergeNP 0 $
    partition (\(x,_) -> x<0) $
    zip series [1..]
  where
    mergeNP s (nss@((nVal,nIx):ns), pss@((pVal,pIx):ps))
     | s < target = (pVal + s, pIx) : mergeNP (pVal + s) (nss,ps)
     | otherwise  = (nVal + s, nIx) : mergeNP (nVal + s) (ns,pss)

Unfortunately I don't know Haskell. Does this print the list of indices? Just asking since the other Haskell solution doesn't.

It does. That's what the map snd $ ... $ zipWith [1..] is for.

Do you require a string instead of a list of numbers?

If Haskell automatically prints a list of numbers in the correct format (space or newline separated)  without further modification then it's okay.

@IngoBürk GHCi produces a comma-separated list. Buh oh well... here we go.

@archaeophyrryx can we meet in a chat room? Please invite me.