text:
Write a Quine in Plain English
Write a quine that consists of real English words separated by single spaces. A "word" is defined as a string containing only lowercase and uppercase letters (/[a-zA-Z]+/ in regex). To be "real" your word must be recognized by the official Scrabble dictionary.
I'm using the Scrabble dictionary since it gives a definitive answer on what is and isn't valid. There are too many gray areas with a normal dictionary. Note that "A" and "I" (not to mention "quine") are not valid scrabble words.
Since writing a quine only using letters and spaces is close to impossible in most programming languages, you have the option to replace the single spaces between words with a character of your choice. You also have the option to append characters to the front of the first word and the end of the last word. These added characters may be anything (including newlines and non-ASCII) except letters (a-z, A-Z). There is a penalty for adding them though (see Scoring.)
Details

As usual, the quines may not read or access their own source code. (I'd say that HQ9+'s Q command violates this.)
Output should go to stdout or a similar alternative. There is no input.
The words do not need to be capitalized correctly. They can have caps and lowercase anywhere. The sequence of words does not need to make any sense.
No word may be used more than 3 times in your program. Differently capitalized words are still the same word (e.g. 'DOG', 'dog', and 'dOg' are all the same word).
Using languages like PHP or HTML that can just cat out their contents is considered a trivial loophole and is not allowed.
The program must contain at least one word.

Scoring
Your score is the number of "real words" in your program plus these penalties:

+1 for every space that was replaced with another character
nn for every n characters you added before the first word (yes, that's n to the power n)
nn for every n characters you added after the last word

For example, the program
We all LIKE PROgraMmING

would score 4 because it contains 4 words; no characters were added or replaced any spaces. It's output would of course be We all LIKE PROgraMmING.
The program
!We@all LIKE#PROgraMmING- =

would score 4 + 2 + 1 + 27 = 34; 4 for the words, 2 for the replaced spaces, 1 for the ! at the front, and 27 for the - = at the end. It's output would of course be !We@all LIKE#PROgraMmING- =.
The lowest score wins. Tiebreaker goes to the answer with the fewest penalty points. If there's still a tie the highest voted answer wins.

Does that dictionary also exist as a list? That would be a lot more helpful to browse through than having to check each word individually.

Shakespeare anyone?

@MartinBüttner, https://scrabblehelper.googlecode.com/svn-history/r20/trunk/ScrabbleHelper/src/dictionaries/sowpods.txt

Is "too hard" a valid downvote reason? Because I feel this is too hard.

@JanDvorak I don't think so... The fact that I can't write anything like this shouldn't make other people see this as a bad question, it's a valid, although pretty difficult, challenge, is it not?

I'm still interested in a Shakespeare solution.

@JanDvorak, I'm pretty sure that's impossible without using you,your,and,as, etc. more than 3 times.

@bmarks do you need those in a Shakespeare program? I can't see a requirement for a readable prose. I can still see why the triple occurence maximum is really problematic. In fact, in order for a character to be useful it must 1) be declared, 2) enter a scene and either 3a) speak or 3b) be spoken to, then leave. A speaker can't leave and they can't speak twice. Since Shakespeare doesn't like more than two characters on a stage, you are essentially limited to one or two monologues at most. Have fun.

@JanDvorak to assign variables you need to use you/thou. To do any kind of math operation (to limit the number of added characters) you need to use as. To do any comparison you need as or than. To do jumps/gotos (there are now other looping structures), there are a limited number of words you can use.
Essentially, Shakespeare would have the same problems assembly would have with the triple occurrence limit. Also, the variables (characters) are not normally valid English words anyway.

I'd like to drop the triple occurence limitation for Shakespeare, then. Even if it means I'm inegligible for winning.

@JanDvorak I'm fine with a Shakespeare submission that breaks that rule. Though to be fair it wouldn't be allowed to win.

Can we instead opt to omit the space between two words, instead of replacing it with another character?

This is an exceptionally difficult challenge.

If you have enough rep and want to sort by activity, open in private browsing (or Incognito, or InPrivate, whatever) mode helps. (Can't vote, though.)

@user23013 or you could just click the "active" link to sort by activity?

@immibis To hide so many deleted answers (which are already more than valid answers) after 2k rep.

@AJMansfield Sorry, no. It'd be unfair to make that a rule now since the challenge has been out for a while.

Is the string literal "programming" in php code. (i.e) the word programming by itself as answer completely valid? Is that a loophole?

Oh missed that distinction my bad!

@JanDvorak my SPL answer definitely breaks the repetition rule. I doubt a quine is possible with the basic dictionary of allowed words in SPL, but if you manage to create one, I would love to see it.

Can I treat a part that contain words as some replacement?

Are error quines okay? https://codegolf.stackexchange.com/a/96018/59376

golfscript, 8 words + 8 symbols = 20 16 (3?)
{four"words.written~twice"four}words.written~twice

The words are just a filler, the core is a tiny quine core:
{".~"}.~

Duplicates and evaluates a function that just appends the instructions to duplicate and evaluate itself. When a function is printed, it is stringified automatically. This is the smallest quine that does something.
Or we could just use a function literal that never gets evaluated. But it feels like cheating...
{whatever}

You don't need concatenation. {a`b"x.y~z"c}x.y~z

@Dennis I don't even need the inspection in that case. Thanks! I feel like I need to ask the OP something...

The rules say that the quines may not read or access their own source code. Your solution might violate that.

@Cephalopod I don't read my own source code. I'm just pushing a function onto the stack and the runtime prints it out for me, blissfully unaware of the fact that the entirety of my source code is a function literal.

I think the {whatever} would violate the too-trivial rule ("Using languages like PHP or HTML that can just cat out their contents is considered a trivial loophole and is not allowed.")

@Claudiu that's a rule against languages, not solutions. That's why I asked.

@JanDvorak: That's a good point

{whatever} is like 1 in a repl

><>, 25 words + (22 + 11 + 11) extra = 57 49
Oh god, my brain.
'brr3deep*clap6beep+orb5flap*leap4deep+clap5beep5flap*leap9deep9clap*beep+flap0placed apple alp0leap=clip?lob8blip*flip0clip.

Since the rules state "There is no input.", for this program to work you'll need to pipe in an empty file.
Oh and yes, brr is a valid Scrabble word, as are tsktsk and pfft.
Explanation
First of all, the following words are no-ops:
deep clap beep flap leap clip blip flip

This is because of two reasons:

abcdefl push numbers (10, 11, 12, 13, 14, 15 and the length of the stack respectively). In addition, i pushes -1 if EOF is met, seeing as there is no input.
The p command pops three chars v,y,x and places v at the position x,y.

Yes, ><> lets you modify the source code on the fly! We don't really make use of that though, as we only need the p for popping.
If we get rid of these no-ops, we get:
'brr3*6+orb5*4+55*99*+0placed apple alp0=?lob8*0.

In a similar way, the laced app part of placed apple and the e alp part of apple alp are also no-ops, and the rr of brr just reverses the stack twice, which we can also remove:
'b3*6+orb5*4+55*99*+0pl0=?lob8*0.

Finally, something that looks like a regular ><> program! The idea is to make use of the standard ><> quine, which works like so:

The initial ' starts string parsing, pushing every char met until we hit another '
We keep pushing chars until the end of the line, at which point we wrap the instruction pointer back to the start (since ><> is toroidal)
We land on the initial ' again, and stop string parsing. The result is that we've pushed every single char in the program (except the initial ') onto the stack.

Then the following happens:
b3*6+o                Print the initial ' quote (ASCII 39)
r                     Reverse the stack
b5*4+                 Push a ';' (ASCII 59)
55*99*+0p             Replace the 'l' of 'lob' with ';'

(print loop)
l0=?;                 If the stack is empty, terminate. Otherwise...
o                     Print the top of the stack
b8*0.                 Jump back to the beginning of the loop

"No word may be used more than 3 times in your program. Differently capitalized words are still the same word (e.g. 'DOG', 'dog', and 'dOg' are all the same word)." Anyway you get an upvote from me, sir.

@rcrmn I kept adding so many words I completely forgot about that rule! Fixed now, although I did want to avoid having to use i.

"leap" should be an option, too. How about "loop", what does o do?

@JanDvorak "leap" is already in there, and o prints the top of the stack. Unrecognised chars throw an error in ><>, which is also pretty annoying here...

TIL "pa", "la" and "be" are valid words in Scrabble

Reading your program aloud makes me imagine what punch card computers must have sounded like.

@Calvin'sHobbies I'm glad I'm not the only one who was hearing imaginary machine noises like that as I read it.

I think you've stolen that program from the source of R2D2's operating system.

Since there’s laxer rules on ending programs with an error now, you can do something like "clap:clap1clap-or>or#

Chicken, 1 word
I'm not normally into esolangs, but this one seemed perfect for this.  I think this is a true quine:
chicken

Pushes 1 chicken to the stack.  The stack is then displayed.

This (and the Julia answer) border on trivially invalid. You can keep them here but no promises on accepting.

@Calvin'sHobbies In the interests of fairness I will happily delete this if you feel it is too loopholey - Your call.  I was working on an applescript solution, but got frustrated by the "No word may be used more than 3 times" rule which seems to make this especially hard.  So I went for the cheap trick instead :-)

@Calvin'sHobbies: I'm the author of the Julia submission. I ditto DigitalTrauma's sentiment on removing my post if you feel it's too borderline. I also did R. Is that too close as well?

@Alex and DT: It's up to you guys. I probably won't accept either answer but I don't mind them being here. I'm still kinda torn on the R answer, though the idea is pretty much the same as the Julia one...

Python 2, 58 = 37 words + 21 punctuation marks
programming=puzzle=hash and'fear=coerce and"programming=puzzle=hash and%rif reload else fire;exec prog"or English;ramming=None or"ramming"if license else pirate;print fear%puzzle+ramming'if reload else fire;exec programming

With some newlines added:
programming=puzzle=hash and'fear=coerce and"programming=puzzle=hash
and%rif reload else fire;exec prog"or English;ramming=None or
"ramming"if license else pirate;print fear%puzzle+ramming'
if reload else fire;exec programming

The three uses per word restriction was what made this one difficult to write. I wanted to use the string with all the code more than 3 times, and every string had to be insulated with if else and or operators which I only had a limited supply of.

@user23013 Oops, forgot to replace it with a random identifier.

R, 2 words + 1 replacement + 1¹ trailing = 4
Objects which aren't assigned to anything are just printed to stdout. Since an expression is an object, the following code prints itself:
expression(puppy)

Previous submission, 5 points:
function(hello)hello

You were inspired by my cheaty 3-point solution, weren't you? ;-)

@JanDvorak: I actually didn't see that before I posted this, but it is now a retrospective source of inspiration.

Vyxal, 2 words + \$1^1 +1 = 4\$
`qUEued`qUEued

Try it Online!
Gosh this took ages to find.
Vyxal's a SBCS language, meaning most of its characters are unicode ones that we cannot use here. But it's still fairly usable without those.
The easiest way to make Vyxal quines is using the format `code`code, where the code prepends a backtick and doubles the result, or similar - this is pretty much exactly what the above program does.
`qUEued`       # Data string
        q      # Unevaluate; enclose in backticks
         U     # Uniquify, removing the trailing backtick
          E    # Evaluate as Python; NOP
           ue  # Extend to length -1; NOP
             d # Double, creating the quine!

Amazing!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Julia, 1 word + 1¹ preceding = 2
Julia has objects called symbols which are defined using a preceding :. Much like my R solution, this just prints when submitted.
:puppy

DOS command line, 10
& was unexpected at this time.

Error quine, not banned it seems

This code doesn't "encode" any part of the code. See our definition for a quine

@MilkyWay90 Using the definition & encodes the whole code and stop outputting

Oh, can you edit the answer so I can remove my downvote

Interesting loopholey answer...is & a word, though?

@RedwolfPrograms no, but &  is two symbols. 5 (words) + 1 (trailing) + 2^2 leading = 10.

Okay, I upvoted. You can remove the quote now

Runic Enchantments, Score 4+3+11+11 = 9
"hOt3OX4NOt+kNOt@

Try it online!
Words: hot ox not knot (4)
Replacements: 3 4 + (3)
Before: " (1)
After: @ (1)
All of the characters GNOQWghtxz are no-op in Runic (as well as space and period, but more spaces doesn't help scoring). Including the X and k required for functionality, this gives the following available word list:
5 Letter Word(s)
  thong
4 Letter Word(s)
  gong goth gowk gown hogg hong honk howk knot know nogg nowt tong town wonk wont zonk
3 Letter Word(s)
  got gox hog hon hot how nog noh not now nth own tho tog ton tow two who wok won wot
2 Letter Word(s)
  go ho no oh on ow ox to wo

I cherry picked based on the needs of the space it was going into and making it sound funny.
Removing all NOP characters gives the following quine:
"3X4+k@

Try it online!

huh? - 1 word + 1**1/1^1=1 char after the word = 2 total score.
Ouch!

Ouch! is a valid quine in huh?
Run it like pythuhn.py Ouch!, and there cannot be a file named Ouch! in the current directory.

Pip, 8 words + (6 + 11) = 15
HA:saY"HA:saY eyRIE:HARPy"eyRIE:HARPy

Includes a trailing newline. Try it online!
Explanation
This is an expansion of the repr-based quine Y"Y yRsRPy"yRsRPy.
HA:saY"HA:saY eyRIE:HARPy"eyRIE:HARPy
HA:s                                   Assign space character to the variable HA
    a                                  No-op
     Y"HA:saY eyRIE:HARPy"             Yank that string into the y variable
                          e            No-op
                           yR          In y, replace
                                HA     HA (space)
                             IE:       (and also assign space character to IE)
                                  RPy  with the repr of y (in this case, y wrapped in quotes)
                                       Autoprint (implicit)

The trailing newline is necessary because autoprint outputs a trailing newline.

Actually, 10 + 9 + 1 = 20
"AB9FAce+AE;Ah+AL"AB9FAce+AE;Ah+AL

Try it online!
Invalid instructions do nothing in Actually,
and removing them gives this:

"9FAc+;+"9FAc+;+
"9FAc+;+"        # String literal
         9FA     # Push abs(9th fibonacci number) = 34
            c    # 34th ascii character is "
             +   # Append the " to the start of the string
              ;+ # Append the string to itself

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

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


text:
Almost Lexicographical List Comparison
Input
Two lists A and B of nonnegative integers.
Output
Either 1, 0, or -1, depending on whether A is larger than, equal to, or smaller than B with respect to the twisted lexicographical ordering as defined below.
If you want, you can replace 1, 0 and -1 with any other three constant values.
The twisted lexicographical ordering is like the ordinary lexicographical ordering, in that you compare the lists element by element, and decide their order at the first differing index.
However, in the twisted version we use a different ordering for nonnegative integers at each index.
Namely, at every index i (indexing starts from 1), the order of the first i nonnegative integers (from 0 to i-1) is reversed, and they are moved above all the other numbers.
Moreover, the "missing element" that signifies one list being shorter than the other is moved directly below i-1.
Visually, the order at index i is
i < i+1 < i+2 < i+3 < ... < [missing element] < i-1 < i-2 < i-3 < ... < 2 < 1 < 0

Note that the first ... denotes infinitely many numbers. This means that the following lists are in ascending order with respect to the twisted lexicographical ordering:
[3,2,3,4]
[3,2,3,5]
[3,2,3,10]
[3,2,3,1341]
[3,2,3]
[3,2,3,3]
[3,2,3,2]
[3,2,3,1]
[3,2,3,0]

Rules
You can give a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
Output 1:
[0] []
[] [1]
[] [1,2,1,2]
[2,1] [1,1]
[0,1,2] [0,2,1]
[3,0] [3,1]
[3,1] [3]
[2] [2,2]
[2] [2,23]
[2,24] [2,23]
[2,1] [2,23]

Output 0:
[] []
[0] [0]
[1,1] [1,1]
[2,1,2] [2,1,2]

Output -1:
[1,2,1,1,2] [1,2,1,1,1]
[1,2,1,1,5] [1,2,1,1,4]
[1,2,1,1,5] [1,2,1,1]
[1,2,1] [1,2,1,1]
[1,2,1,1,5] [1,2,1,1,6]
[1,2,1,1,6] [1,2,1,1,7]

Are the input lists indexed from 0, from 1, or from whichever is appropriate for our language?

@PeterTaylor From 1. I'll clarify that.

Can i use Haskell's own enum for comparison results instead of -1/0/1 for the output?

@JanDvorak I'll allow that, and edit the challenge.

CJam - 57
q:S~=0{S~]:A:,~e>{A{_,I>{I=_I>0{W*2}?}1?[\]}%}fI]z~>2*(}?

Yeah it's still very long...
Try it online
Brief explanation:
The code outputs 0 if the arrays are equal in the traditional sense, otherwise it converts each item of each array to a 2-element array: [0 ai] if ai>i (0-based), [1 whatever] if ai is missing, and [2 -ai] if ai<=i. In the process, the shorter array is also extended to the larger size. Then the transformed arrays are compared lexicographically and the result is adjusted to -1/1.

Python 2, 76 bytes
c=lambda*a:cmp(*[[(max(i-x,-1),x)for i,x in enumerate(L)]+[(0,)]for L in a])

This replaces each integer in both lists with a 2-tuple to account for the twisted ordering. Python 2's cmp builtin does the rest.
Usage:
>>> c([1,2,1,1,6], [1,2,1,1,7])
-1

How does this account for a shorter list to go in between different longer lists ([3,2,3,1341] < [3,2,3] < [3,2,3,0]?

@nutki it adds the tuple (0,) to the end of each list, which is greater than any (-1, x) and less than (i-x, x) when i-x >= 0.

Oh, of course. I am not literate in Python.

Perl, 74
Without good array manipulation functions perl is not the optimal tool for the job, but it works.
#!perl -pa
$i=0,s/\d+,?/$s=sprintf"%9d",$&;$&>$i++?$s:~$s/ge for@F;$_=$F[0]cmp$F[1]

Test me.

J, 95 bytes
(Not super-short but whatever. Definitely golfable.)
f=.4 :0
m=.>:>./x,y
t=.(|+(1+m)*0>:*)@(i.@#-~])@(],m$~>&#*-&#)
x(t~(*@-&((m+#x,y)&#.))t)y
)

Passing all the test cases. (Great test case set! Thanks!)
Method:

Padding the shorter list with maxvalue+1 (m=.>:>./x,y). (],m$~>&#*-&#
Transforming list elements so normal comparison could be used. (|+(1+m)*0>:*)@(i.@#-~])
Calculating two baseX numbers from the two list with sufficient X. ((m+#x,y)&#.)
Returning the signum of the two numbers difference.*@-&

Jelly, 9 bytes
J_»0;1ż)M

Try it online!
Direct port of grc's Python solution. Monadic link taking a pair of its arguments and returning [1] for 1, [1, 2] for 0, and [2] for -1.
       )     For each element of the input:
 _           Subtract each element from
J            its 1-index,
  »0         take the maximum of each of those and 0,
    ;1       append 1,
      ż      and zip those with the original elements.
        M    Return the list of maximal indices.

Mathematica, 65
f=-Order@@MapIndexed[If[#>Last@#2,#,a-b#]&,PadRight[{##}+1],{2}]&

Usage:
f[{1, 2, 1, 1, 6}, {1, 2, 1, 1, 7}]

-1

source: Stack Exchange

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

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

sort: votes


text:
Paeth-transform arrays
One of the key parts of PNG's compression algorithm is the Paeth transformation, which transforms the image in a way that makes it compress better (usually). In this challenge, your task is to write a program to compute a Paeth transformation. The operation of a Paeth transformation is described below.
The Paeth Transformation
The Paeth transformation subtracts from each member X of a 2-dimensional array a predictor. The predictor is that element of the array member to the left (A), top (B), and top-left (C) of X whose value has the least difference to A + B - C.
┼─┼─┼
│C│B│
┼─┼─┼
│A│X│
┼─┼─┼

If one of A, B, or C, would be out of bounds, its value is replaced by 0. Here is pseudocode from the PNG specification outlining how this predictor is computed:
function PaethPredictor (a, b, c)
begin
     ; a = left, b = above, c = upper left
     p := a + b - c        ; initial estimate
     pa := abs(p - a)      ; distances to a, b, c
     pb := abs(p - b)
     pc := abs(p - c)
     ; return nearest of a,b,c,
     ; breaking ties in order a,b,c.
     if pa <= pb AND pa <= pc then return a
     else if pb <= pc then return b
     else return c
end

For this challenge, the array members are natural numbers in the range from 0 to 255. If the Paeth transformation results in a value outside of that range, it shall be reduced modulo 256 to a value in that range.
Input and Output
The input is two integers x and y in the range from 2 to 1023 denoting width and height of the matrix to transform and an array of x × y elements. The input is formatted as decimal numbers separated by one blank character terminated with a linefeed. Here is what this input could look like:
2 3 4 5 6 7 8 9

This would represent a 2 by 3 matrix with the entries:
4 5
6 7
8 9

The output shall have the same format as the input with the relaxiation that the numbers may be separated by an arbitrary non-zero amount of whitespace characters (space, horizontal or vertical tab, line or form feed) and be terminated by an arbitrary amount of whitespace characters.
Input shall be received from stdin, output shall go to stdout. If this is not possible, choose a different way of receiving input and writing output that is not hard-coding the input.
The behaviour of your program when presented with invalid input is not part of this challenge.
Judging and Reference Implementation
An ANSI C program is provided to generate sample input, solve instances and verify solutions. Call the program with g to generate input, with s to solve an input instance and with v to verify the correctness of a solution.
If you think the reference implementation is faulty, please let me know so I can correct it as soon as possible.
Example input and output
By popular request.
10 5 166 156 108 96 63 227 122 99 117 135 125 46 169 247 116 55 151 1 232 114 214 254 6 127 217 88 206 102 252 237 75 250 202 145 86 198 172 84 68 114 58 228 66 224 186 217 210 108 11 179

representing the array
166 156 108  96  63 227 122  99 117 135
125  46 169 247 116  55 151   1 232 114
214 254   6 127 217  88 206 102 252 237
 75 250 202 145  86 198 172  84  68 114
 58 228  66 224 186 217 210 108  11 179

is transformed into
166 246 208 244 223 164 151 233  18  18
215 177 123  78 125  84  96 135 231 138
 89 129   8 121 101 228  55 101  20 123
117 175 196 199 125 112 222 238  72  46
239 234 120 158  41  19  12  24 183 111

which is encoded as
10 5 166 246 208 244 223 164 151 233 18 18 215 177 123 78 125 84 96 135 231 138 89 129 8 121 101 228 55 101 20 123 117 175 196 199 125 112 222 238 72 46 239 234 120 158 41 19 12 24 183 111

Winning Condition
For this challenge, write a program that generates correct Paeth transformation of the input and writes them out. This is code-golf, the program with the least amount of characters in its source code wins. Please try to attach an explanation and a readable version of your code to your submission so others can see what it does.

What do you mean by "If the Paeth transformation results in a value outside of that range"? Since the result is always drawn from a set of three elements, all of which are within range, this seems to be covering an impossible case.

@PeterTaylor The Paeth transformation is for each array member the difference between the value of that member and the predictor for that member, which can be negative.

@MartinBüttner That must have slipped through the copy-editing.

@Alex whether 0 is a natural number highly depends on the author of your textbook.

@FUZxxl: Truth. Didn't realize there isn't universal agreement on that until a moment ago. But that was a total aside. Nice challenge.

@Alex I'm happy that you like it. Let's see if people appreciate me putting an input generator and validator into the question.

Btw, congratulations on posting question no. 3000! (Not counting deleted and locked questions.)

Oh wow. That's cool. I didn't even realize.

J - 77 char
Taking an approach that looks different from FUZxxl's answer but is actually very similar.
1!:2&4":2({.,|.@{.,@(256|$-0(0{[/:+`-/|@-])"1@|:(-#:1 2 3)|.!.0$)}.)0".1!:1]3

Some comments on the interesting bits.

1!:2&4": (...) 0".1!:1]3 - If J wasn't terrible about I/O and parsing, this could be refactored as to use &.".&.stdin'', to save 3 chars. But it is so we can't. Rest in peace, precious characters.
2 ({.,|.@{.,@( ... stuff using $ ... )}.) - This disassembles the input and reassembles the output. We use $ both as a reference to the input in stuff using $, and as an operation we need to perform on the input before running the stuff on it.
0( blah )"1@|: - Yes, that's a dyadic Transpose: we regroup the three rotation results as the innermost array axis, so that the Paeth logic can apply on each set separately with "1.
0{[/:+`-/|@-] - The Paeth logic: sort a,b,c by the magnitudes of (p minus each of a,b,c), and take the first.

This is really neat.

+1 for the dyadic transpose. Very nice.

J, 97 91 88 87 characters
Let's get this started. Notice the absent exit; J prints a prompt (three blanks) after all the output has been written, but then gets an EOF on stdin, causing it to terminate.
I believe that quite a couple of improvements are possible in this code.
1!:2&4":(|.@$,,)256|((-+`-/+[:(>&|{,)"0/]-"2+`-/)(3 2$-*i.3)|.!.0])2(|.@{.$}.)0".1!:1]3

Here is the code before golfing it; it's mostly equal to the current code.
NB. A, B, and C values
abc =: (0 _1 , _1 0 ,: _1 _1)&(|.!.0)
p =: +`-/@abc
NB. minimum of magnitudes
mmin =: (>&| { ,)"0
pred =: p + [: mmin/ abc -"2 2 p
paeth =: 256 | ] - pred
input =: [: (2&}. $~ 2 |.@{. ]) 0 ". 1!:1
output =: [: 1!:2&4 LF ,~ [: ": |.@$ , ,
output paeth input 3
exit 0

This code gives an incorrect output: 3 2$-*i:3 is not equivalent to 0 _1,_1 0,:_1 _1.

@algorithmshark Sorry. better this way?


text:
Dollar Divisibility and Perfect Change
I have $15 in my pocket.  Likewise, I am in a store which doesn't give change.  While browsing, I spot an item that costs $10 (tax included).  Can I buy that item without losing any money?
In this case, the answer is yes.  No matter how my $15 is divided up (one 10 and one 5, or three 5s, or something else), I will always have the exact $10 needed.
As a second example, I have $0.16 in my pocket.  What other amounts of money must I be able to pay exactly?
Possible Divisions:
0.01, 0.05, 0.10
0.01, 0.05 x 3
0.01 x 16
Guaranteed Exact Change:
0.01, 0.05, 0.06, 0.10, 0.11, 0.15, 0.16

What if I have $0.27 in my pocket?
Possible Divisions:
0.01 x 2, 0.25
0.01 x 2, 0.05, 0.10 x 2
0.01 x 2, 0.05 x 3, 0.10
0.01 x 2, 0.05 x 5
0.01 x 27
Guaranteed Exact Change:
0.01, 0.02, 0.25, 0.26, 0.27

In the above case, there were only a few amounts of money for which I would always have perfect change.
Your task
Write the shortest program (or named function) which takes A) an integer amount of money and B) a list of possible denominations as input, and outputs a list of the amounts of money for which I must have perfect change.  Input can be either STDIN or arguments for the program or function.  I'm not going to be super-strict on input formatting; it can match how your language formats arrays.
Perhaps a More Detailed Explanation
I have a certain amount of money in my pocket, which is formed from a set of possible demonstrations of currency.   If I have $8, and I know that the possible denominations are $2 and $3, then there's only so many different combinations of bills that could be in my pocket.  These are 2+2+2+2 and 3+3+2.  In order to be able to produce an exact amount of money, I have to be able to produce that quantity using the only the bills that are in my pocket.  If I had four 2s, I could produce 2, 4, 6, or 8. If I had two 3s and a 2, I could produce 2, 3, 5, 6, or 8 Since I don't know which of these combinations I actually have in my pocket, my final answer is reduced to 2, 6, 8.  These are the values I know I could produce from my pocket, given the total amount and the possible denominations.
Hand-Calculated Example I/O
7 [3, 4]
3, 4, 7        //only one possible division into 3 + 4

7 [3, 2]
2, 3, 4, 5, 7  //the only division is 3 + 2 + 2

6 [2, 3, 4]
6     //divisions are 2+2+2, 3+3, 2+4

16 [1, 5, 10, 25]          //this represents one of the examples above
1, 5, 6, 10, 11, 15, 16

27 [1, 5, 10, 25]          //another example from above
1, 2, 25, 26, 27

1500 [1, 5, 10, 25, 100, 500, 1000, 2000]
500, 1000, 1500

600 [100, 500, 1000, 2000]
100, 500, 600

600 [200, 1, 5, 10, 25, 100, 500, 1000, 2000]
600

Should the program run in reasonable time for all the inputs? E.g. my shortest idea is exponential in the starting amount and 2^1500 is a lot of anything.

What should the program do if the user inputs (amount of money and denominations) are inconsistent? For example, it is impossible to have 7 dollars in your pocket if the denominations are [2, 4, 6]--what should the program return in this case?

@mathmandan It doesn't matter.

Haskell, 132 109 bytes
n?y@(x:z)|n>0=map(x:)((n-x)?y)++n?z
n?_=[[]|n==0]
(x:n)#y=n#y||n#(y-x)
_#y=y==0
x%z=[y|y<-[1..x],all(#y)$x?z]

Try it online!
Explanation
This is a pretty straight-forward solution to the puzzle.

(?) takes an amount and a list of denominations and determines all ways to make the amount with the given denominations.  Solutions are sorted in the same order as the original denomination list.
This is just all the possible sets we could have in our pocket.

(#) an amount and a list of amounts and determines if the amount is the sum of a sub-list of the given list.
This is whether an amount can be made from a given set of bills.

(%) is the main function. It takes an amount, x, and a list of denominations, z.  For each amount, y, from 1 to the given amount it checks that for every way to make the initial amount (x?z), y is the sum of some sub-list of it.

Python 2, 200 197 193 140 bytes
f=lambda n,D,S={0}:sum([f(n-x,D,S|{x+y for y in S})for x in D],[])if n>0else[S]*-~n
g=lambda*a:(f(*a)and reduce(set.__and__,f(*a))or{0})-{0}

(Thanks to @Nabb for tips)
Here's a poorly golfed solution for now to get things started. Call with g(16, [1, 5, 10, 25]) — output is a set with the relevant denominations.
The approach is straightforward, and is broken down into two steps:

f looks at all ways of reaching n with denominations D (e.g. [1, 5, 10]), and for each one it works out all amounts that can be made with these denominations (e.g. set([0, 1, 5, 6, 10, 11, 15, 16])).
g calculates the intersections of the results of f, then removes 0 for the final answer.

The program solves cases 1-5 and 7 fine, stack overflows on 6 and takes forever on 8.
If there is no solution (e.g. g(7, [2, 4, 6])), then the program returns an empty set. If an error is allowed to be thrown for such a case, then here is a shorter g:
g=lambda*a:reduce(set.__and__,f(*a))-{0}

g=lambda L,c=0:L and g(L[1:],c)|g(L,c+L.pop(0))or{c} is a little shorter

A bit more by moving -{0} into g and using [L]*-~n instead of [L][-n:]

JavaScript (ES6) 162 203 207
Edit Changed the way to intersect result sets in array r. A bit faster, but the algorithm still stinks.
More detailed explanation will follow.
Shortly : c is a recursive function that enumerate all the possible subdivisions. k is a recursive function that enumerate all the possible sums without repetitions.
Any new result set found with k function is compared with the previous set found, only the common results are kept.
Why is it so slow? Having to manage a target total of, say, 1500 and a single piece of value 1, enumerating all the possibile sums is not a good idea.
F=(s,d,r,
  c=(s,i,t=[],v,k=(i,s,v)=>{for(;v=t[i++];)k(i,s+v);o[s]=s})=>
  {for(s||(i=k(o=[],0),r=(r||o).filter(v=>o[v]));v=d[i];++i)s<v||c(s-v,i,[...t,v])}
)=>c(s,0)||r

Ungolfed
F=(s,d)=>{
  var r
  var c=(s,i,t=[])=>
  {
    var o=[],v
    var k=(i,s)=> // find all sums for the current list t, set a flag in the o array
    {
      var v
      for(;v=t[i++];)k(i,s+v)
      o[s]=s
    }

    if (s==0) {
      k(0,0)
      if (r)
        r = r.filter(v=>o[v]) // after first loop, intersect with current
      else
        r = o.filter(v=>v) // first loop, keep all results
    }
    else
      for(;v=d[i];++i)
      {
        if (s >= v)
          c(s-v, i, t.concat(v))
      }
  }
  c(s,0) // enumerate all possible set of pieces
  return r
}

Test In Firefox/FireBug console
F(16,[1,5,10,25])

[1, 5, 6, 10, 11, 15, 16]

(time 84 msec)
F(27, [1, 5, 10, 25])

[1, 2, 25, 26, 27]

(time 147252 msec, so not sooo fast)

Wolfram Methematica, 104 bytes
Rest@*Intersection@@Map[Total]/@Subsets/@Union[Sort/@IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]]]&

Ungolfed (read from the end):
Rest@* // Removing 0
  Intersection@@   // Intersecting all totals
     Map[Total]/@  // Counting total of each subset
        Subsets/@  // Getting all the subsets of each partition
           Union[  // Removing duplicates
              Sort/@ // Sorting each partition (to remove duplicates next)
                 IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]] // Getting all Integer partitions
                ]&


text:
Find a numeric coincidence when representing numbers in various bases
Recently, when doing some code-golf challenge, I came up with with two solutions, in 69 and 105 bytes. It's a remarkable coincidence, because:

69 (decimal) = 105 (octal)
69 (hexadecimal) = 105 (decimal)

What other numbers have this property (using different bases)? You should help me answer this question!
Write a program or a subroutine that receives as input 3 numbers (base1, base2, base3, in ascending order), and prints two sequences of digits d1 d2 d3 ... and D1 D2 D3 ... that reproduce this numerical coincidence for the specified bases.
To make sure the various fine points are covered:

Evaluate one sequence as a number in base base1, and the other sequence in base base2 -- you must get the same number
Evaluate one sequence as a number in base base2, and the other sequence in base base3 -- you must get the same number
Both sequences must have finite length, which is greater than 1
Separate the sequences of digits with whitespace or in any other unambiguous way
Output to stdout or other similar output device
All digits must be between 0 and base-1; leading zeros are not allowed
If a digit is greater than 9, use a or A for 10, b for 11, ..., z for 35
You may assume that all bases are different, come in ascending order and are in the range 2...36; are represented in the most natural way for your language
If there is no answer, your code must signal it in some way (e.g. outputting nothing)
If there is an answer whose larger number is less than 1679616 (364), your code must find it; otherwise, it may output as if no solution exists
Code-golf: shortest code wins!

Example input:

8, 10, 16

Example output:

69 105

or

104 68

Or any other solution.
I'll be happy if you provide theoretical insights into this problem (How to determine whether a solution exists? Is there an infinite number of solutions?).

There can't be infinite number of solutions because the numbers will not have the right lengths, unless log(base1)/log(base2) = log(base2)/log(base3), where there are trivially infinite number of 1000000... solutions.

Do we have to provide one solution, or all solutions?

@Ypnypn Any one solution

You should better specify what is the meaning of the 2 sequences outputted, and that the numbers in them should be different.

@rcrmn I hope it's clear now. The numbers in them should be different, but I didn't mention this, because it follows from other conditions (base1 < base2 < base3)

why did the mathematician confuse halloween and christmas, etc. etc

Python 2, 158 bytes
Came a bit too easily, so I might be missing something obvious!
s=lambda n,b:(n/b and s(n/b,b)or'')+chr(48+n%b+39*(n%b>9))
def f(a,b,c):
 for n in range(b,36**4):
  x=s(n,a);y=s(n,b)
  if int(x,b)==int(y,c):print x,y;break

The base conversion function is lovingly stolen from @ugoren's solution to Print integers in any base up to 36. The code simply tries all possible values for the smaller number and the rest is fully determined. We start counting from base2 to ensure both sequences are at least length 2.
>>> f(8, 10, 16)
100 64
>>> f(8, 10, 17)
>>> f(16, 20, 24)
20 1c


text:
Water Balloon Wars
This king-of-the-hill game is a strategy game in which you must throw around a water balloon and avoid getting splashed by water. The goal is to obtain the most points. You will be given a map of the field and the location of the water balloon. You can either return that you want to hit the water balloon (if you are close enough) in a certain direction or that you want to move in a certain direction.
Specifically:
The water balloon will start at (0, 0) 30 units high and drop. If the water balloon hits the ground, a player will randomly be chosen to lose 4 points, with more weight given to those who are closer to the balloon. In addition, the player who last hit the balloon will earn 3 points. Therefore, if you hit the balloon straight down, you will most likely lose 1 point.
You will write a class that extends Player. You are required to implement the constructor. The constructor will look like:
public Player1() {
    super(/* Some numbers */ 3, 3, 4)
}

These numbers are doubles. The first number represents the player's speed, the second represents strength, and the third represents luck. The numbers must add up to 10 or less and no number may be less than or equal to zero.
Second, you must implement the move method. This is an example move method:
@Override
protected Action move(Map<Player, Point2D> map, Balloon b) {
    // Get my own location
    Point2D myself = map.get(this);
    // If I'm close enough to the balloon
    // then hit the balloon
    if (myself.distanceSq(b.getLocation()) <= 16) {
        double d = (r.nextDouble() - 0.5) * 3;
        // Random y direction, z direction is what's left
        return new Hit(0, d, Math.sqrt(9 - d*d));
    } else {
        double diffX = b.getLocation().getX() - myself.getX(),
                diffY = b.getLocation().getY() - myself.getY();
        // Move towards the balloon
        return new Movement(Math.signum(diffX)*3/Math.sqrt(2), Math.signum(diffY)*3/Math.sqrt(2));
    }
}

There are a number of important things here. First, notice that the field is passed as a Map<Player, Point2D>.  The field is infinite - there is no limit to how far you can go. It is not a 2-dimensional array or anything like that. In addition, this means that you will have non-integer coordinates as your location. This is perfectly okay.
Another consequence is that players and the balloon may overlap. In fact, two players may be in the exact same location!
The balloon has a certain velocity and direction. In general, it will fall at a rate of 3 units/step. It also moves in an x direction and y direction. When you return a Hit, you pass the x, y, and z directions that you are pushing the balloon. You cannot hit a balloon whose height is greater than 10 or whose distance from you (only on two dimensions) is greater than 4. In addition, if it is true that x^2 + y^2 + z^2 > s^2 where s is your strength, and x, y, and z are the directions that you hit, your action is discarded. The force of your hit is amplified by a random number between 0 and luck (which means it could go down if your luck is low).
Similarly, you can return a Movement with the x and y coordinates that you are moving (note that you cannot jump in the air). If x^2 + y^2 > s^2 where s is your speed, your action is discarded.
If the water balloon hits the ground then a random player is chosen, with more weight given to those who are closest -- but less weight to those who have more luck. The player that is chosen loses 4 points.
Controller: https://github.com/prakol16/water-balloon-wars/tree/master
The game lasts 1000 steps. At the end, there will be a file called log.out. Copy and paste the data into this fiddle to view the game: https://jsfiddle.net/prankol57/s2x776dt/embedded/result/
Or even better, view it in 3D: http://www.brianmacintosh.com/waterballoonwars (thanks to BMac)
The player with the highest sum of scores after 100 (may be more, but not less) games wins.
If you wish to submit a solution, you may want to read the really specific details at https://github.com/prakol16/water-balloon-wars/tree/master.
Edit 3/8:
These are the final scores for now (1000 iterations, without including players 1 and 2). If you edit your post, you can comment, and I will redo the scores:
{
    class players.BackAndForth=-75.343,
    class players.Hydrophobe=-0.800,
    class players.KeepAway=-53.064,
    class players.Weakling=39.432,
    class players.Repeller=21.238,
    class players.LuckyLoser=-30.055,
    class players.AngryPenguin=-49.310
}

The winner was Weakling with an average of 39 points. 2nd place was Repeller with 21 points.

What happens when you hit the balloon?  How does it move?  What if multiple people hit it?

The animation with the jsfiddle is really nice!

By the way, you should make the methods in the Player class final, otherwise submissions can override them.

You inverted speed and strength in the Player constructor.

@KeithRandall The dirX, dirY, and dirZ (amplified by your luck) are simply added to the velocities of the balloon. If multiple people hit it (somewhat unlikely) then the player who might get three points is decided on luck (see specific details)

@Thrax Thanks I mixed it up in the question. Fixed now.

BackAndForth
This bot tries to get close and hit the balloon until its height is too low and it tries to get away.
package players;

import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class BackAndForth extends Player {

    static int round = 0;
    static int speed = 3;
    static int strength = 1;
    static boolean hit = false;
    static double previousHeight = 30.0;

    public BackAndForth() {
        super(speed, strength, 10 - speed - strength);
    }

    @Override
    protected Action move(Map<Player, Point2D> map, Balloon b) {

        round++;

        Point2D me = map.get(this);
        Point2D balloon = b.getLocation();

        double distanceX = balloon.getX() - me.getX();
        double distanceY = balloon.getY() - me.getY();
        double distance = Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));

        double maxX = speed * distanceX / distance;
        double maxY = speed * distanceY / distance;

        if (previousHeight < b.getHeight())
            hit = false;

        if (hit || b.getHeight() < 3) {
            previousHeight = b.getHeight();
            return new Movement(-maxX, -maxY);
        } else {
            if (distance < 4 && b.getHeight() < 10) {
                hit = true;
                return new Hit(0, 0, strength);
            } else {
                if (Math.pow(distance, 2) <= Math.pow(speed, 2)) {
                    return new Movement(distanceX, distanceY);
                } else {
                    return new Movement(maxX, maxY);
                }
            }
        }

    }

}

it looks like your bot performs illegal moves and thus does nothing when it does.

@soktinpk I fixed my submission, it should do better now. Thanks Moogie too!

I am still finding that your bot is asking for movement beyond what is possible. I have put in an edit of your post for review. Basically you were using the balloon's position as movement.

@Moogie Right, thanks a lot!

Glad to help. Your bot is pretty good at getting positive scores. well done!

Simulator
I hope this is okay, since it isn't actually an entry. I really liked the idea of the visual simulator and I wanted to create my own that would make it a little easier to see everything at once (full 3D).
2/28 9:06AM PST: update with follow controls, colors
3/4 8:47AM PST: update with a slider for simulation speed, and made starting a new game actually work without refreshing the page (use Ctrl-F5 to reload cached script)
Online ThreeJS Visualizer

+1000 That is amazing. Thank you

Don't you mean Ctrl+F5, not Shift+F5?

Looks like both work in Chrome.

Weakling
This bot can only touch the balloon as it is so weak, instead it just relies on its high luck. It therefore performs similarly to LuckyLoser (from which this bot is inspired).
He seems to out perform all the current bots including Repeller.
package players;
import java.awt.geom.Point2D;
import java.util.Map;
import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class Weakling extends Player {

    static final private double STRENGTH = Double.MIN_VALUE;
    static final private double SPEED = 1.5;
    static final private double LUCK = 8.5;
    public Weakling() {
        super(SPEED,STRENGTH,LUCK);
    }

    protected Action move(Map<Player, Point2D> map, Balloon b) {
        Point2D start = map.get(this);
        Point2D balloon = b.getLocation();
        double distance = start.distance(balloon)+Double.MIN_VALUE;
        if(distance<=4 && b.getHeight()<=10){

            // just touch it :P
            return new Hit(0,0,0);
        }
        double x = start.getX()-balloon.getX();
        double y = start.getY()-balloon.getY();
        x /= distance;
        y /= distance;

        // move to directly underneath balloon
        x*=Math.min(SPEED, distance);
        y*=Math.min(SPEED, distance);
        return new Movement(-x, -y);
    }
}

EDIT: reduced speed in favour of luck

AngryPenguin
This penguin is angry because he can't fly up to the balloon, so he tries to hit the balloon into the face of people standing around him.
package players;

import java.awt.geom.Point2D;
import java.util.Map;
import java.util.Map.Entry;

import balloon.Action;
import balloon.Action.Hit;
import balloon.Action.Movement;
import balloon.Balloon;
import balloon.Player;

public class AngryPenguin extends Player {
    private static final double HIT_Z = 3;
    public AngryPenguin() {
        super(4, 4, 2);
    }

    @Override
    protected Action move(Map<Player, Point2D> map, Balloon balloon) {
        Point2D myself = map.get(this);

        double distanceX = balloon.getLocation().getX() - myself.getX();
        double distanceY = balloon.getLocation().getY() - myself.getY();
        double distance = Math.sqrt(Math.pow(distanceX, 2) + Math.pow(distanceY, 2));

        if (balloon.getHeight() < 2) {
            double[] xy = shrink(distanceX, distanceY, Math.pow(getSpeed(),2));
            return new Movement(-xy[0], -xy[1]);
        } else if (distance <= 4 && balloon.getHeight() <= 10) {
            double lowestDistance = Double.MAX_VALUE;
            Point2D nearestPlayerLoc = null;
            for (Entry<Player, Point2D> e : map.entrySet()) {
                if (e.getKey() != this) {
                    double d = e.getValue().distanceSq(myself);
                    if (d < lowestDistance) {
                        lowestDistance = d;
                        nearestPlayerLoc = e.getValue();
                    }
                }
            }
            double dX = nearestPlayerLoc.getX() - myself.getX();
            double dY = nearestPlayerLoc.getY() - myself.getY();
            double d = Math.pow(getStrength() - HIT_Z, 2);
            double[] xy = shrink(dX, dY, d);
            return new Hit(xy[0], xy[1], -HIT_Z);
        } else {
            double[] xy = shrink(distanceX, distanceY, Math.pow(Math.min(getSpeed(), distance), 2));
            return new Movement(xy[0], xy[1]);
        }
    }

    private double[] shrink(double x, double y, double totalPow) {
        double[] xy = new double[2];
        double ratio = y == 0 ? 0 :
                       x == 0 ? 1 : Math.abs(x) / Math.abs(y);
        if (ratio > 1)
            ratio = 1/ratio;
        xy[1] = totalPow * ratio;
        xy[0] = totalPow - xy[1];
        xy[0] = x < 0 ? -Math.sqrt(xy[0]) : Math.sqrt(xy[0]);
        xy[1] = y < 0 ? -Math.sqrt(xy[1]) : Math.sqrt(xy[1]);
        return xy;
    }

}

This is the one to beat.

Repeller
This bot relies has only one real move and that is to keep on pushing the balloon away from itself. i.e. repells the balloon.
It seems to perform well against the current crop of bots (LuckyLoser, AngryPenguin,        Hydrophobe, BackAndForth ) nearly always winning. However Hydrophobe, by inaction, is always ready to win if the other bots all manage to get negative score :P
package players;
import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class Repeller extends Player {

    static final private double STRENGTH = 3.5;
    static final private double SPEED = 2.5;
    static final private double LUCK = 4;
    public Repeller() {
        super(SPEED,STRENGTH,LUCK);
    }

    protected Action move(Map<Player, Point2D> map, Balloon b) {
        Point2D start = map.get(this);
        Point2D balloon = b.getLocation();
        double distance = start.distance(balloon)+Double.MIN_VALUE;
        if(distance<=4 && b.getHeight()<=10){
            double x = start.getX()-balloon.getX();
            double y = start.getY()-balloon.getY();
            x /= distance;
            y /= distance;
            x*=STRENGTH;
            y*=STRENGTH;

            // push the balloon away with all our strength
            return new Hit(-x,-y,0);
        }
        double x = start.getX()-balloon.getX();
        double y = start.getY()-balloon.getY();
        x /= distance;
        y /= distance;

        // if we are directly underneath then move away from balloon
        distance=distance<1?-1:distance;

        // if we are just off of directly underneath then stay put
        distance=distance<2?0:distance;

        // move to the desired location
        x*=Math.min(SPEED, distance);
        y*=Math.min(SPEED, distance);
        return new Movement(-x, -y);
    }
}

Lucky Loser
This bot relies on its high luck score. If it is not near the balloon, it runs towards the balloon. Once near the balloon, if there are at least 2 other players in range of the balloon, he'll spike it to the ground. Otherwise, he'll knock it straight up.
package players;
import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class LuckyLoser extends Player {
    public LuckyLoser() {
        super(1,1,8);
    }

    protected Action move(Map<Player, Point2D> map, Balloon b) {
        Point2D start = map.get(this);
        Point2D bLocation = b.getLocation();
        double distance = start.distance(bLocation);
        if(distance<=4){
            boolean foundMe = false;
            int numPlayersInRange=0;
            for(Point2D point:map.values()){
                if( !foundMe && point.equals(start))
                {
                    foundMe=true;
                    continue;
                }
                if(point.distance(bLocation)<=4)
                    numPlayersInRange++;
            }
            if(numPlayersInRange>1)
                return new Hit(0,0,-1);
            else
                return new Hit(0,0,1);
        }
        double x = start.getX()-bLocation.getX();
        double y = start.getY()-bLocation.getY();
        x /= distance;
        y /= distance;
        return new Movement(-x, -y);
    }
}

EDIT: Fixed movement bug which actually made me run away not towards the balloon >_< Now I just run straight towards the balloon if I can't hit it.

Hydrophobe
This is one of the simplest possible bot possible but as it is competitive I will post it.
Strategy: well... this bots hates water so it just goes away.
As the bot will be splashed very rarely it will score a little under 0 point in average. The sum of all bots' scores are -1 * [balloon hitting ground] so Hydrophobe will probably score above average.
package players;
import java.awt.geom.Point2D;
import java.util.Map;
import balloon.*;

public class Hydrophobe extends Player {
    public Hydrophobe() {super(8, 1, 1);}
    @Override
    protected Action move(Map<Player, Point2D> map, Balloon balloon) {
        return new Action.Movement(5.65,5.65);
    }
}

KeepAway
This player chases the balloon as long as its height is > 2. As soon as it can hit the balloon, it hits the balloon away from the closest player. When the balloon's height is < 2, this player runs away.
package players;

import java.awt.geom.Point2D;
import java.util.Map;

import balloon.Action;
import balloon.Balloon;
import balloon.Player;
import balloon.Action.Hit;
import balloon.Action.Movement;

public class KeepAway extends Player{

    public KeepAway() {
        super(5, 3, 2);
    }

    @Override
    protected Action move(Map<Player, Point2D> map, Balloon b) {

        Point2D myself = map.get(this);

        //if balloon is high up, run towards it
        if(b.getHeight() > 2){
            Point2D closest = getClosestPlayer(map);

            boolean canHit = b.getHeight() <= 10 && myself.distance(b.getLocation()) <= 4;

            //hit it when you can
            if(canHit){

                Point2D normHit = normalize(new Point2D.Double(myself.getX() - closest.getX(), myself.getY() - closest.getY()));
                Point2D forceHit = new Point2D.Double(normHit.getX() * getStrength(), normHit.getY() * getStrength());

                return new Hit(forceHit.getX(), forceHit.getY(), 0);
            }
            //if you can't hit it, keep running towards it
            else {

                Point2D normRun = normalize(new Point2D.Double(myself.getX() - b.getLocation().getX(), myself.getY() - b.getLocation().getY()));
                Point2D forceRun = new Point2D.Double(-normRun.getX() * getSpeed(), -normRun.getY() * getSpeed());
                return new Movement(forceRun.getX(), forceRun.getY());
            }
        }
        //if the balloon is low, run away
        else{
            Point2D normRun = normalize(new Point2D.Double(myself.getX() - b.getLocation().getX(), myself.getY() - b.getLocation().getY()));
            Point2D forceRun = new Point2D.Double(normRun.getX() * getSpeed(), normRun.getY() * getSpeed());
            return new Movement(forceRun.getX(), forceRun.getY());
        }

    }

    private Point2D getClosestPlayer(Map<Player, Point2D> map){

        double minDistance = Double.MAX_VALUE;
        Point2D closestPoint = null;
        Point2D myPoint = map.get(this);

        for(Player p : map.keySet()){
            if(this != p){

                if(myPoint.distance(map.get(p)) < minDistance){
                    minDistance = myPoint.distance(map.get(p));
                    closestPoint = map.get(p);
                }
            }
        }

        return closestPoint;
    }

    private Point2D normalize(Point2D p){
        double d = p.distance(0, 0);

        if(d == 0){
            return new Point2D.Double(0, 0);
        }

        return new Point2D.Double(p.getX()/d, p.getY()/d);
    }

}

Edit: I was playing with Player1 and Player2 included. This player wins in that case, but loses when I take them out. Booooo.


text:
Solve a Diagonal Burrows-Wheeler transform
Introduction
In this challenge you will be solving diagonal Burrows-Wheeler transforms. Here is a general overview of what a diagonal Burrows-Wheeler transform is. To encode a message, you first must guarantee that it is odd in length (i.e. 5, 7, 9, etc.). Then you make a grid, n by n, where n is the length of the message. The first row is the original message. Each row after that is the row above it, but shifted 1 character left with the first character moving to the back. For example:
Hello World
ello WorldH
llo WorldHe
lo WorldHel
o WorldHell
 WorldHello
WorldHello
orldHello W
rldHello Wo
ldHello Wor
dHello Worl

Then you take each letter on the NW to SE diagonal and put that into a new string:
Hello World  H
ello WorldH  l
llo WorldHe  o
lo WorldHel  W
o WorldHell  r
 WorldHello  d
WorldHello   e
orldHello W  l
rldHello Wo  (space)
ldHello Wor  o
dHello Worl  l

Your encoded message is HloWrdel ol. To decode, first take the length of the encoded message, add 1, and divide by 2. Lets call this number x. Now that we know x, starting at the first letter, each letter is x after the last, looping around. For example:
H   l   o   W   r   d   e   l     o   l
1

Then...

H   l   o   W   r   d   e   l     o   l
1                       2

And again...

H   l   o   W   r   d   e   l     o   l
1   3                   2

Until you get...

H   l   o   W   r   d   e   l       o   l
1   3   5   7   9  11   2   4   6   8  10

Now just rearrange the letters in the correct order to get Hello World!
Challenge
Your challenge is to write either two programs, functions, or one of each. However, both must use the same language. The first program will accept a string as input via STDIN, program arguments, or function parameters and encode it using this method. The second program will accept a string as input via STDIN, program arguments, or function parameters and decode it using this method.
Requirements
First Program/Function

A single string input using any method listed above.
Must encode the string using a diagonal Burrows-Wheeler transform style.

Second Program/Function

A single string input using any method listed above.
Must decode the string using a diagonal Burrows-Wheeler transform style.

Constraints

You cannot use any built-in or external functions that accomplish this task.
Standard loopholes are not allowed.
Both programs/functions must be in the same language.

Scoring
This is code golf, so shortest program in bytes wins.
If I need to add more information, leave a comment!

Do we have to convert even length input string to odd length ?

This is not a Burrows-Wheeler transoformation.

A Burrows-Wheeler transformation is different in that the array of all rotations is sorted lexicographically before you take the last items.

@Optimizer it is not necessary.

CJam, (4 + 8 = ) 12 bytes
Encoding program:
q2/z

Try it online here
Decoding program:
q_,2/)/z

Try it online here
How (or rather, why) they work:
The Diagonal Burrows-Wheeler transform is basically every other character of the string, with wrapping from the end. If we treat the String as a 2D matrix of 2 columns, it simply boils down to taking the transform of the matrix. Example:
Hello World

Is represented as 2D matrix as
He
ll
o
Wo
rl
d

Now, simply reading it column wise, give:
HloWrdel ol

Which is the Burrows-Wheeler transform.
Decoding is simply reverse of the process, write the string as a 2 row 2D matrix and read column wise.
Code expansion:
Encoder:
q          "Read the input";
 2/        "divide it into sub arrays of 2 characters";
   z       "Take transform";

Decoder:
q_,        "Read the input, take copy and get length of copy";
   2/      "Divide the length by 2";
     )/    "Increment and split the input into two rows";
       z   "Take transform";

Python 2, 57 bytes
E=lambda x:(x+x)[::2]
D=lambda y:(-~len(y)/2*y)[::len(y)/2+1]

Try it online!
Thanks to l4m2 for 4 bytes.
E encrypts and D decrypts. I'm not counting the E= and D= for the score.
The decryption takes every n'th character wrapping around, where n is half the string length round up. The reason this inverts is that 2 and n are inverses modulo the length of the string, so taking every nth character inverts taking every 2nd one.
If using a single function were allowed, I could do 44 bytes
def F(x,b):n=1+len(x)**b>>b;return(n*x)[::n]

The encrypts when b is False and decrypts when b is True. The expression 1+len(x)**b>>b is equal to [2,len(x)/2+1][b].

(x+x)[::2] like my py3 code do

J, 10 + 10 = 20
   ({~#|2*i.@#) 'Hello World'
HloWrdel ol

   (/:#|2*i.@#) 'HloWrdel ol'
Hello World

(Surrounding braces are not counted into the score as they are not part of the function definition.)
Thanks for FUZxxl for a 3-byte improvement.
Now it is nicely shown that the two functions are inverses as the first one takes characters from positions defined by the list #|2*i.@# and the second function arranges back the characters using the same list as ordering.
Try it online here.

The first one can be done in 10 characters as well: {~#|2*i.@#.

@FUZxxl Thanks, updated. Now the relation between the two functions is shown really nicely.

Pyth - 5 + 11 = 16 bytes
I noticed a pattern! ~Does happy dance~ The transform is just really just looping through the string picking every other elements. It only works on odd since otherwise it would never get half the elements. This is equivalent to rotating a 2 wide matrix.
Encoder:
%2*2z

Python's step slicing doesn't loop around so I repeated the string.
%2      Take every other elements
 *2z    Double input string

Decoder:
K/hlz2%K*Kz

Again no wrap-around for step-slicing.
K/hlz2       K=length of (input+1)/2
%K           Every kth element
 *Kz         From K*the input

@FryAmTheEggman I'm pretty sure that it is only supposed to take odd length string. It was in the beginning of the description.

Oops, sorry. :S

JavaScript ES6, 41 + 49 = 90 bytes
Encoder
(t=>t.replace(/./g,(_,o)=>t[o*2%t.length]))('Hello World')

Decoder
(t=>t.replace(/./g,(_,o)=>t[-~(l=t.length)/2*o%l]))('HloWrdel ol')

These are anonymous functions, so I only counting the code inside the parentheses because that is the whole function definition. Try it out with the snippet below: (modified to use ES5)

E=function(t){
  return t.replace(/./g,function(_,o){
    return t[o*2%t.length]
  })
}
D=function(t){
  return t.replace(/./g,function(_,o){
    return t[-~(l=t.length)/2*o%l]
  })
}
i=prompt();
alert('Encoded: '+E(i)+'\nDecoded: '+D(i))

How about this: [t=>t.replace(/./g,(_,o)=>t[o*2%t.length]),t=>t.replace(/./g,(_,o)=>t[(1+(l=t.length))/2*o%l])]? You use it like [...][0]('encode string') and [...][1]('decode string'). There is nothing saying that this can't be done! And you save 1 byte.

Thanks, bu it says to write 2 functions, and I don't think this would count.

That's still 2 functions. The rules don't specify names or ways to access the functions. It only says that you must use 2 functions.

@IsmaelMiguel Now that I think about it, I think anonymous functions are allowed by themselves, so using that saves me even more bytes.

I'm glad you cut down the byte count.

GNU sed -r, (20 + 104 + 1) = 125
The extra +1 in the score is for the -r option to sed.  Odd length input strings are assumed.
Encoder:
s/.*/&&/
s/(.)./\1/g

Double up the input string
Drop every odd (counting from 1) character

Decoder:
The decoder makes use of : as a temporary marker character, so if it appears in the input string, you'll get undefined behaviour.  If the input string is restricted to the 95 ASCII characters, then these markers can be replaced with something outside the ASCII range (e.g. BEL 0x7) to fix this.
s/.*/:&:/
:l;s/:(.)(.+)(.):/\1:\2:\3/;tl
s/:(.*)/\1:/
:m;s/(.)(.*):(.?)(.*):(.*)/\2:\4:\5\1\3/;tm
s/://g

Put : markers at the start and end of the input string
Shuffle the first : forward and second : backward one character at a time until the : markers are either side of the middle character
Remove the first : and add another : to the end leaving "A:B:", where A is the string composed of odd characters from the plaintext input and B is the string composed of the even characters
Riffle the characters of A and B together after the last : to reassemble the plaintext input
Remove the remaining : markers

Python 3 - 34 + 176 167 + 11 16(math) = 221 217
Messy, but I coded it all by myself:
import math as m
def a(x):
  return x[::2] + x[1::2]
def b(x):
  if len(x) % 2 == 0:
    x += " "
  c=""
  for i in range(m.floor(len(x)/2)):
    c+=x[i]
    c+=x[i+m.floor((len(x)+1)/2)]
  c+=x[m.floor((len(x)-1)/2)]
  return c

Edit 1: (literally as I write this, I realised how to shave off 4 bytes)
The encoder just takes every other character and combines them, and the decoder is the inverse of that (takes every n/2th character) in the most messy way possible.
(Also formatted)

Python 3, 58 bytes
A=lambda x:(x+x)[::2]
def B(x):t=1+len(x)>>1;return(x*t)[::t]

Try it online!

V (vim), 18 + 51 = 69 bytes
Encoder, 18 bytes
o<esc>kqqlxjpkl@qq@qgJ

Try it online!
Moves every other character to the next line, and joins the two.
Decoder, 51 bytes
YpC<c-r>=strlen('<c-r>"')/2+1
<esc>Dk@"li
<esc>jdd{qqld$}o<esc>pk0@qq@q

Try it online!
Uses a recursive macro to delete till the end and use it as a flatten-transpose. This took a while to figure out.

69 bytes. Very nice

Jelly, 2 + 3 = 5 bytes
Encoder
Œœ

Try it online!
Split the input into odd and even indices. The two strings are then implicitly concatenated.
Decoder
ŒHZ

Try it online!
Split into two halves, transpose, implicitly concatenate.

Vyxal, 2+7=9 bytes
Encoder
y+

Try it Online!
Decoder
:½h$½tY

Try it Online!


text:
Golf Down the PPCG Usernames
A comment I made in chat and the ensuing conversation inspired me to make this challenge.

Am I the only one referred to by initials around here? We are all about golfing things down. We can have MB and D-nob and ... O.

If I'm known as "CH" then I think everyone else ought to have an initial-based nickname as well.
Here's a list of the top 100 Programming Puzzles & Code Golf users by reputation to play with:
Martin Büttner
Doorknob
Peter Taylor
Howard
marinus
Dennis
DigitalTrauma
David Carraher
primo
squeamish ossifrage
Keith Randall
Ilmari Karonen
Quincunx
Optimizer
grc
Calvin's Hobbies
ugoren
Mig
gnibbler
Sp3000
aditsu
histocrat
Ventero
xnor
mniip
Geobits
J B
Joe Z.
Gareth
Jan Dvorak
isaacg
edc65
Victor
steveverrill
feersum
ace
Danko Durbić
xfix
PhiNotPi
user23013
manatwork
es1024
Joey
daniero
boothby
nneonneo
Joey Adams
Timwi
FireFly
dansalmo
grovesNL
breadbox
Timtech
Flonk
algorithmshark
Johannes Kuhn
Yimin Rong
copy
belisarius
professorfish
Ypnypn
trichoplax
Darren Stone
Riot
ProgramFOX
TheDoctor
swish
minitech
Jason C
Tobia
Falko
PleaseStand
VisioN
leftaroundabout
alephalpha
FUZxxl
Peter Olson
Eelvex
marcog
MichaelT
w0lf
Ell
Kyle Kanos
qwr
flawr
James_pic
MtnViewMark
cjfaure
hammar
bitpwner
Heiko Oberdiek
proud haskeller
dan04
plannapus
Mr Lister
randomra
AShelly
ɐɔıʇǝɥʇuʎs
Alexandru
user unknown

(this is how I got it)
Challenge
Write a program or function that takes in a list of strings and outputs another list of strings of their minimal, unique, initial-based nicknames, giving preference to those closer to the start of the list.
Apply this method to each string S in the list in the order given to create the nicknames:

Split S up into words separated by spaces, removing all spaces in the process.
List the nonempty prefixes of the string of the first letters of the words in S, from shortest to longest.
    e.g. Just Some Name → J, JS, JSN
Choose the first item in this list that is not identical to an already chosen nickname as the nickname for S. Stop if a nickname was chosen, continue to step 4 otherwise.
    e.g. if Just Some Name was the first string then J is guaranteed to be the nickname.
List the prefixes again, but this time include the second letter of the first word in it's natural place.
    e.g. Just Some Name → Ju, JuS, JuSN
Do the same as in step 3 for this list, stopping if a unique nickname is found.
Repeat this process with the remaining letters of the first word, eventually inserting letters into the second word, then the third, and so on, until a unique nickname is found.
    e.g. The first unique string listed here will be the nickname:
Jus, JusS, JusSN
Just, JustS, JustSN
Just, JustSo, JustSoN (note that o was not added after Just)
Just, JustSom, JustSomN
Just, JustSome, JustSomeN
Just, JustSome, JustSomeNa
Just, JustSome, JustSomeNam
Just, JustSome, JustSomeName

In the end all the input strings should end up with a unique nickname (potentially identical to the string). You may assume that none of the input strings will map to the same nickname using this method.
Example
Updated to fix my mistake!
For the input
Martin Buttner
Doorknob
Peter Taylor
Howard
marinus
Dennis
DigitalTrauma
David Carraher
Martin Bitter
Martin Butter
Martin Battle
Martini Beer
Mart Beer
Mars Bar
Mars Barn

the nicknames would be
M
D
P
H
m
De
Di
DC
MB
Ma
MaB
Mar
MarB
Mars
MarsB

Details

Input can be from a file (one name per line), or one name at a time via stdin/command line, or as a function argument of a list of strings, or as a function arg of a single string with newlines between names.
Output should be printed to stdout (one nickname per line) or returned by the function as a list of strings, or as one string with newlines between nicknames.
Ideally programs will work for names that contain any characters except line terminators. However, you may assume that all the names only contain printable ASCII. (The PPCG names don't.)
Only the regular space character counts as a word separator. Leading and trailing spaces can be ignored.

Scoring
The shortest submission in bytes wins. Tiebreaker goes to the answer posted earliest.

This explains why I woke up in the middle of the night with this vague sensation of feeling violated.

CJam, 58 53 bytes
This can be golfed a lot.. But for starters:
LqN/{:Q1<aQ,,:)QS/f{{1$<_,@-z1e>}%W<s}+{a1$&!}=a+}/N*

Code Expansion:
L                         "Put an empty array on stack. This is the final nickname array";
 qN/{  ...   }/           "Read the input and split it on new lines. Run the block for each";
     :Q1<a                "Store each name in Q and get its first char. Wrap it in an array";
          Q,,:)           "Get an array of 1 to length(name) integers";
               QS/        "Split the name on spaces";
f{{           }%   }      "for each of the integer in the array, run the code block";
                          "and then for each of the name part, run the inner code block";
   1$<                    "Copy the integer, take first that many characters from the";
                          "first part of the name";
      _,@-z1e>            "Get the actual length of the part and the number of characters";
                          "to be taken from the next name part, minimum being 1";
                W<        "Get rid of the last integer which equals 1";
                  s       "Concat all name parts in the array";
                    +     "Add the list of nick names as per spec with the first character";
{     }=                  "Get the first nick name that matches the criteria";
 a1$&                     "Wrap the nick name in an array and do set intersection with";
                          "the copy of existing nick names";
     !                    "Choose this nick name if the intersection is empty";
N*                        "After the { ... }/ for loop, the stack contains the final";
                          "nick names array. Print it separated with new lines";

Try it online here

See my comment to OP: if 'Ju' or 'Jus' are valid nicknames for 'Just Some Name', 'Maertin Butter' sholud be 'Ma', then 'MaB','Mar','MarB'.

What @edc65 says is true. Sorry about that. I'll allow you to not change things if you want; it was my mistake.

JavaScript (ES6) 159
Following the specs and not the example.
I generate the candidate nicknames having a current middle word (at the beginning, the first word). The words before the current are used 'as is'. The words after the current contribute with no - or just the first - character. The current word contributes with 1 more character for each loop.
Example 'Just Some Name' => 'Just','Some','Name'
Cw Just, position 1, try J, JS, JSN
Cw Just, position 2, try Ju, JuS, JuSN
Cw Just, position 3, try Jus, JusS, JusSN
Cw Just, position 4, try Just, JustS, JustSN
Now Just is exhausted, Some becomes Cw, position restarted to 2 (for position 1, all already tried)
Cw Some, position 2, try Just, JustSo, JustSoN
Cw Some, position 3, try Just, JustSom, JustSomN
Cw Some, position 4, try Just, JustSome, JustSomeN
Now Some is exhausted, Name becomes Cw, position restarted to 2
Cw Name, position 2, try Just, JustSome, JustSomeNa
Cw Name, position 3, try Just, JustSome, JustSomeNam
Cw Name, position 4, try Just, JustSome, JustSomeName
That's all folks!
The code
(q is current word position, p is slicing position)
F=l=>
  l.map(w=>{
    for(w=w.match(/[^ ]+/g),q=p=0;
        w.every((w,i)=>~o.indexOf(t+=i<q?w:i>q?w[0]:w.slice(0,p+1)),t='')
        &&(w[q][p++]||(p=1,w[++q]));
       );
    o.push(t)
  },o=[])&&o

Test In Firefox/FireBug console
F(['Martin Buttner','Doorknob','Peter Taylor','Howard','marinus'
  ,'Dennis','DigitalTrauma','David Carraher'
  ,'Martin Bitter','Martin Butter','Martin Battle','Martini Beer','Mart Beer'])

["M", "D", "P", "H", "m", "De", "Di", "DC", "MB", "Ma", "MaB", "Mar", "MarB"]

PHP, 327 289 275 274 270
There may still be a little golfing potential.
while($n=fgets(STDIN)){$c=count($w=preg_split('/\s+/',trim($n)));$p=[];for($k=0;$k<$c;$p[$k]++){for($t='',$j=0;$j<$c;$j++)$t.=substr($w[$j],0,$p[$j]+1);for($j=1;$j<=strlen($t);$j++)if(!in_array($v=substr($t,0,$j),$u))break 2;$k+=$p[$k]==strlen($w[$k]);}echo$u[]=$v,'
';}

Program operates on stdin/stdout, works on ASCII, buggy on UTF
usage: php -d error_reporting=0 golfnicks.php < nicknames.txt
or cat <<EOF | php -d error_reporting=0 golfnicks.php + list of names + EOF
To test as function in web browser: fetch the breakdown, uncomment all lines marked with // FUNC and comment the one marked with //PROG.
Try f(array_fill(0,21,'Just Some Name'));

breakdown
#error_reporting(0);function f($a){echo'<pre>'; // FUNC
#foreach($a as$n) // FUNC
while($n=fgets(STDIN)) // PROG
{
    $c=count($w=preg_split('/\s+/',trim($n)));     // split name to words, count them
    $p=[];                                         // initialize cursors
    for($k=0;$k<$c;$p[$k]++)
    {
        for($t='',$j=0;$j<$c;$j++)$t.=substr($w[$j],0,$p[$j]+1); // concatenate prefixes
        for($j=1;$j<=strlen($t);$j++)              // loop through possible nicks
            if(!in_array($v=substr($t,0,$j),$u))   // unused nick found
                break 2;                           // -> break cursor loop
        $k+=$p[$k]==strlen($w[$k]);                // if Cw exhausted -> next word
        // strlen()-1 would be correct; but this works too)
    }
    echo$u[]=$v,'
';
}
#echo '</pre>';} // FUNC


text:
From 0 to 2^n - 1 in POPCORN order
... Ah sorry, no popcorn here, just POPCNT.
Write the shortest program or function which takes in a number n and output all integers from 0 to 2n - 1, in ascending order of number of 1 bits in the binary representation of the numbers (popcount). No duplicates allowed.
The order of numbers with the same popcount is implementation-defined.
For example, for n = 3, all these output are valid:
0, 1, 2, 4, 3, 5, 6, 7
[0, 4, 1, 2, 5, 3, 6, 7]
0 4 2 1 6 5 3 7

The input and output format are implementation-defined to allow the use of language features to further golf the code. There are a few restrictions on the output:

The numbers must be output in decimal format.
The output must contain a reasonable separator between the numbers (trailing separator allowed, but not leading).
Line feed (\n), tab (\t), space, ,, ., ;, |, -, _, / are quite reasonable separator. I don't mind additional spaces for pretty printing, but don't use letter or digits as separators.
The numbers and separators can be surrounded by [ ], { } or any array or list notation.
Don't print anything else not stated above.

Bonus
Multiply your score by 0.5 if your solution can generate the number on the fly. The spirit of this bonus is that if you were to directly convert your printing solution to a generator, the generator only uses at most O(n) memory where n is the number of bits as defined above. (You don't have to actually convert your solution to generator). Note that while I impose n <= 28, the memory needed to store all numbers still grows exponentially, and a naive sorting solution would hog up at least 4 GB of memory at n = 28.
Please add some simple explanation of how your solution works before claiming this bonus.

It seems that the challenge as it is quite boring and would result in a bunch of sorting answers. I would like to add some bonus to make the challenge more interesting. Something along the line of "generating the numbers on the fly". If you are OK with it, please upvote this comment, then I will add it to the question.

If you disagree, please upvote this comment.

Please use the sandbox to ask for further suggestions on a question before posting it live.

@JanDvorak: It was on sandbox for one month.

I believe your incentive for finding a solution without sorting isn't enough. While I can think about some ways to compute the table without sorting, their implementation would be more than twice as long as my current code.

@FUZxxl: Agree, since no answer is going to get shorter than 9 characters. However, it's quite hard to change the requirement at this point. If you have any idea on how to improve the question, please let me know.

I think it's too late for this question. Generally, questions where you have to figure out a non-trivial algorithm aren't well suited for code golf in my opinion. Make them a code challenge instead and pose all the constraints you need.

@FUZxxl: I will keep that in mind next time. Actually PhiNotPi also suggested code challenge, but I forgot the initial goal of this question (as I found the solution previously), so I post the challenge as a code golf regardless.

Pyth, 9 bytes
osjN2U^2Q

order by the sum of the base 2 representation (jN2) over the range (U) of 2 ^ Q.
(Q = eval(input())).
Try it here.

Python 2, 72 bytes * 0.5 = 36
N=1<<input()
for k in range(N*N):
 if bin(k%N).count('1')==k/N:print k%N

Try it online!
A new method for this now-ancient challenge. The less-golfed below below might be easier to understand:
87 bytes
n=input()
for i in range(n+1):
 for x in range(2**n):
  if bin(x).count('1')==i:print x

Try it online!
We loop over target popcounts i in increasing order, and for each one iterate over the n-bit numbers and prints those with exactly i set bits.
Even though this loops over the n-bit numbers many times, it still satisfies the efficiency bonus criteria of only using O(n) memory if the loop were converted to a generator. If fact, the golfed code allocates n bits to the target popcount as well as n bits to the number being checked. They are stored as a 2*n-bit number, which allows counting up this single number and extracting the first and last n bits as needed.

Python 2, 59 bytes
lambda n:sorted(range(1<<n),key=lambda x:bin(x).count('1'))

Try it online!
A short sorting-based approach that does not qualify for the bonus.

Python 2, 75 bytes * 0.5 = 37.5
N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N

Try it online!
Repeatedly generates the next highest v with the same POPCOUNT by this bit-twiddling algorithm.
Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then v overflows 2**n, we simply remove all but n bits with &N where N=2**n-1, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next lower number with the same POPCOUNT.
Due to a fencepost issue, we need to start with v=2**(n+1)-1 so that the operation produces v=N-1 on the first loop.
Output for 4:
0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

There is no need for the number with the same popcount to be increasing. The order is implementation-defined.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ I'm aware, but I don't see how to save characters doing it differently.

With a naive 3 loops method, I score almost the same in JS (having console.log() vs print). Maybe the bit trick is too heavy.

One byte saving: v=N-~N

J, 19 characters, no bonus.
[:(/:+/"1@#:)@i.2^]

2 ^ y – two to the power of y.
i. 2 ^ y – the integers from 0 to (2 ^ y) - 1.
#: i. 2 ^ y – each of these integers represented in base two.
+/"1 #: i. 2 ^ y – the sums of each representation
(i. 2 ^ y) /: +/"1 #: i. 2 ^ y – the vector i. 2 ^ y sorted by the order of the items of the previous vector, our answer.

Python, 63 chars
F=lambda n:`sorted(range(1<<n),key=lambda x:bin(x).count('1'))`

>>> F(3)
'[0, 1, 2, 4, 3, 5, 6, 7]'

@Alex: The list of restrictions implied he wanted a string result.

Sorry, missed that.

C 179 * 0.5 = 89.5
main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(;n--;++i){for(o=0;o<m;++o){int bc=0,cb=28;for(;cb--;)bc+=o&(1<<cb)?1:0;if(bc==i)printf("%d ",o);}}printf("%d\n",m);return 0;}

EDIT: 157 * 0.5 = 78.5
main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(++n;n--;++i){for(o=0;o<=m;++o){int bc=0,cb=28;for(;cb--;)bc+=o&(1<<cb)?1:0;if(bc==i)printf("%d ",o);}}}

EDIT: 132 * 0.5 = 66
main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(++n;n--;++i){for(o=0;o<=m;++o){if(__builtin_popcount(o)==i)printf("%d ",o);}}}

or a bit nicer formatted:
main()
{
    int n, i = 0, m, o;
    scanf("%d", &n);
    m = ~((~0) << n);
    for(++n; n--; ++i)
    {
        for(o = 0; o <= m; ++o)
        {
            if (__builtin_popcount(o) == i)
                printf("%d ", o);
        }
    }
}

What it does?
m = ~((~0) << n);

calculates the last number to show (pow(2, n) - 1)
    for(++n; n--; ++i)
    {
        for(o = 0; o <= m; ++o)
        {

the outer loop iterates over the bit count (so 0 to n-1)
while the inner loop just counts from 0 to m
            if (__builtin_popcount(o) == i)
                printf("%d ", o);

On x86 there is the POPCNT instruction that can be used to count the set bits.
GCC and compatible compilers may support the __builtin_popcount function that basically compiles to that instruction.

Mathematica, 50 46
SortBy[Range[0,2^#-1],Tr@IntegerDigits[#,2]&]&

.
SortBy[Range[0,2^#-1],Tr@IntegerDigits[#,2]&]&

{0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20,
24, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 15,
23, 27, 29, 30, 31}

CJam, 13 bytes
2ri#,{2b1b}$p

Pretty straight forward implementation.
How it works:
2ri#,             "Get an array of 0 to 2^n - 1 integers, where n is the input";
     {    }$      "Sort by";
      2b1b        "Convert the number to binary, sum the digits";
            p     "Print the array";

Try it online here

K (ngn/k), 18 9 8 bytes
-9 bytes from @ngn's improvements
-1 byte from using where instead of take
<+/!2+&:

Try it online!
A tacit function, equivalent to {<+/!2+&x}.

2+&: generate x 2's
!... generate "odometer" of the input (in this case this provides the binary representation of the numbers from 0 to pow(2,x))
+/ sum column-wise
< "grade up" the sums (i.e. sort them by the number of 1's in the binary-representation of each value)

here t@<.. is the same as <..

odometer can be useful

@ngn very true! Somehow I missed that y\!1*/x#y is equivalent to !x#y.

Husk, 8 bytes
ÖoΣḋŀ`^2

Try it online!
     `^2  flip ^, partially applied, gets fully applied with implicit input, 2 ^ n
    ŀ     range from [0, n)
Ö         sort by
 o        composed function
  Σ       sum
   ḋ      binary digits

Bash + coreutils, 66
One to get you started:
jot -w2o%dpc $[2**$1] 0|dc|tr -d 0|nl -ba -v0 -w9|sort -k2|cut -f1

Nothing really exciting here.  Given your comment I will happily delete/revise this answer if you want to change the question.

Not sure if I should highlight your program must work for all values of n from 0 to 28 inclusive. I don't know how many answers here pass that requirement.

I have removed the clause, since people don't seem to notice it anyway.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳  Now, in theory at least it should work up to 28.  I've tested up to 22 so far, but of course this makes sort take a long time.  With n=28, sort will need to sort 2^28 lines / ~13GB of data.

Mathematica, 26
Tr/@(2^Subsets@Range@#/2)&

Example:
Tr/@(2^Subsets@Range@#/2)&[4]

{0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15}

JavaScript (ES6) 41 (82*0.5)
The simplest way, golfed
F=b=>{
  for(l=0;l<=b;l++)
    for(i=1<<b;i;t||console.log(i))
      for(t=l,u=--i;u;--t)
        u&=u-1;
}

Ungolfed
F=b=>
{
  for (l = 0; l <= b; l++)
  {
    for (i = 1 << b; i > 0; )
    {
      --i;
      for (t = 0, u = i; u; ++t) // Counting bits set, Brian Kernighan's way
        u &= u - 1;
      if (t == l) console.log(i);
    }
  }
}

Test In Firefox/FireBug console
F(4)

0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15

Haskell, (87 * 0.5) = 43,5
f n=[0..n]>>=(\x->x#(n-x))
a#0=[2^a-1]
0#_=[0]
a#b=[1+2*x|x<-(a-1)#b]++[2*x|x<-a#(b-1)]

Usage example: f 4, which outputs [0,1,2,4,8,3,5,9,6,10,12,7,11,13,14,15]
How it works: neither sorting nor repeatedly iterating over [0..2^n-1] and looking for numbers containing i 1s.
The # helper functions takes two parameters a and b and constructs a list of every number made up of a 1s and b 0s. The main function f calls # for every combination of a and b where a+b equals n, starting with no 1s and n 0s to have the numbers in order. Thanks to Haskell's laziness all those lists don't have to be constructed completely in memory.

Doesn't the ++ in a#b mean that the left hand side (which could be large) needs to be produced entirely and then copied before the first item in the result is produced, thus violating the requirements for the bonus?

Ah, no,  thinking about it can still lazily generate them while they're being produced, it just needs to make a copy of each item, which as both can be garbage collected during processing means that space usage is constant.  Ignore me.

Ruby 47 chars
Much like the Python one from @KeithRandall :
f=->n{(0..1<<n).sort_by{|x|x.to_s(2).count ?1}}

Jelly, 7 bytes
2*’BS$Þ

Try it online!
Explanation
2*’BS$Þ
2*      2^n
  ’     decremented
     $Þ sort the (implicit) range using the following two functions:
   B    binary
    S   summed

05AB1E, 7 bytes
oL<Σb1¢

Try it online!
oL<Σb1¢  # full program
   Σ     # sort...
 L       # [1, 2, 3...
o        # ...2 **...
         # implicit input
 L       # ]...
  <      # with one subtracted from...
         # (implicit) each element...
   Σ     # by...
      ¢  # number of...
     1   # ones...
      ¢  # in...
         # (implicit) current element in list...
    b    # in binary
         # implicit output

Alternative, 7 bytes
oL<Σ2вO

Try it online!
2вO  # full modified section
  O  # sum of...
 в   # list of (base-10) values of digits of...
     # (implicit) current element in list...
 в   # in base...
2    # literal

Another alternative, 7 bytes
oL<ΣbSO

Try it online!
bSO  # full modified section
  O  # sum of...
 S   # list of characters of...
     # (implicit) current element in list...
b    # in binary

Since [1,1,1]>[1,1], you can do oL<Σbʒ for 6 bytes.

@ovs Oh, that trailing ʒ to only keep all 1s is pretty smart. :)

Vyxal, 6 bytes
‹Eʁµb∑

Try it Online!
  ʁ    # 0...
‹E     # 2 ** (n-1)
   µ   # Sorted by
    b  # binary
     ∑ # Summed

Java 8, 205
public class S{public static void main(String[] n){java.util.stream.IntStream.range(0,1<<Integer.parseInt(n[0])).boxed().sorted((a,b)->Integer.bitCount(a)-Integer.bitCount(b)).forEach(System.out::print);}}

C++11, 117 characters:
using namespace std;int main(){ set<pair<int,int> > s;int b;cin>>b;int i=0;while(++i<pow(2,b))s.insert({bitset<32>(i).count(),i});for (auto it:s) cout <<it.second<<endl;}

Ungolfed:
using namespace std;
int main()
{
    set<pair<int,int> > s;
    int b;
    cin>>b;
    int i=0;
    while (++i<pow(2,b))  {
        s.insert({bitset<32>(i).count(),i});
    }
    for (auto it:s) {
        cout <<it.second<<endl;
    }
}

Explanation:
Create a set of int,int pairs. The first int is bit count, the second one is the number. Pairs compare themselves according their first parameter, so the set is sorted by bit count.

MathGolf, 6 bytes
óráÅàç

Try it online.
Explanation:
ó       # Push 2 to the power of the (implicit) input-integer
 r      # Pop and push a list in the range [0,2**input)
  á     # Sort this list by,
   Å    # using the following two characters as inner code-block:
    à   #  Convert it to a binary-string
     ç  #  And only leave the truthy digits, removing the 0s

Perl, 64/2 = 32
#!perl -ln
for$i(0..$_){$i-(sprintf"%b",$_)=~y/1//||print for 0..2**$_-1}

Simply iterate over the range [0..2^n-1] n + 1 times. In each iteration print only the numbers that have number of 1 bits equal to the iteration variable ($i). Bits are counted by counting 1's (y/1//) in the number converted to binary string with sprintf.
Test me.
Perl, 63
Sorting approach:
#!perl -l
print for sort{eval+(sprintf"%b-%b",$a,$b)=~y/0//dr}0..2**<>-1

@Optimizer, It uses O(1) memory. What other definition we have? Oops, that is not true as I print it live :)

@Optimizer, fixed.

Well, I am aware of this when I set the condition, but I allow it anyway, since I want to see what convoluted answers people can come up with.

I just asked "how" as I cannot read perl :) Care to add more explanation ?

@Optimizer, some more explanation added.

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳


text:
Pseudo-cyclic Number Evaluator
For the purposes of this challenge, let's define a cyclic number as an integer that passes the basic part of Midy's Theorem, but not necessarily the extended theorem. This means:

the digits in the second half of the repeating decimal period are [integer is] the 9s complement of the corresponding digits in its first half

In other words,
142857 is a cyclic number because 142 + 857 = 999 and 13358664 is a cylic number because 1335 + 8664 = 9999.
The Challenge
Given an even-digit integer n > 10, determine whether n is a cyclic number by our definition. If it is, return something truthy. If it's not, return the closest cyclic number to n.
Example:
> 18
True
> 133249
132867

This is code golf, so shortest code wins.

The pseudo-cyclic number 132867 is closer to 133249 than 133866 is. Are you only considering numbers higher than the original?

@xnor No, you're right. I'll change that.

As written, " If it [cyclic], return something truthy" lets you return the number itself. Actually, the non-cyclic outputs are all truthy too.

If the first sentence of the question is taken literally, neither 142857 nor 13358664 is a cyclic number because they both "pass" the extended theorem as well as the basic one.

@PeterTaylor the extended part is not a requirement.

Python 2, 73
n=input()
e=10**(len(`n`)/2)-1
N=n/e+n%e*2/e;N-=N>e+1
print n==N*e or N*e

A six-digit pseudo-cyclic number like 637362 is pseudo-cyclic exactly if it's a multiple of 999, except for 999999. So, we're looking for the multiple of 999 nearest to the input n. In general, replace 999 with e, which is one less that 10**(num_digits/2).
The nearest multiple below can n be found with integer division as n/e*e. We check whether to round up with n%e*2/e, which is 1 if n%e is closer to e, and 0 if it's closer to 0. In the latter case, we add e. We also handle the 999999 case by subtract if N is too large.
Finally, before printing, we check if the original number was a multiple of e and thus already pseudo-cyclic.

I think you need to add a check that ensures e!=n. Otherwise 99, etc. return true. This also seems to happen to the algorithm that finds the next/previous value.

@FryAmTheEggman You're right, good catch. I made a hackety fix.

Uh, the input__ surely must be input() ...? That said, everything seems ok except you sometimes get 9 as your output. i.e. for 11.

@FryAmTheEggman Is that not the intended output? As a two-digit number, 09 is pseudo-cyclic.

I believe they have to be >10 (and must be even-digited). Sorry :( Though I could be wrong, maybe ask op?

Pyth, 39
Jf!-`sjT^10/l`T2\9UyQ|}QJho%l`N2o^-QZ2J

... or
A version that might be against the rules: 33
ho%l`N2o^-QZ2f!-`sjT^10/l`T2\9UyQ

Try it online here.
The rules-breaking version just echoes the number if it is cyclic.
I believe this gives the correct output for all values, if you find something in my reasoning that is flawed, please tell me ;)
This begins by generating a list of all of the cyclic numbers from 0 to twice the input. This will obviously include each cyclic number less than the input, and includes the next cyclic number. You actually only need to add 10 ^ (digits_in_input / 2) to ensure this, but doubling takes fewer characters.
The numbers are found to be cyclic by converting them into base 10 ^ (digits_in_input / 2) and then summing the digits of this number together. All 9s are then removed from this list, and so if the list is empty the number is cyclic.
If the input is a member of this list, True is printed, otherwise the list is sorted, first by (input - value) ^ 2 and then by if the number contains an even or odd number of digits (sorting evens as less). Since pyth uses stable sorts, this is equivalent to sorting by both at once. Then the first number in this list is the nearest cyclic tag number.
This algorithm is fairly naive, but I believe it catches everything. I particularly think that the sorting could be golfed a lot.

Clip, 59
[vr[p[q?<a-vpa-vqp]q]}}f[d[q=qc$+n#q$dn+q$d'9]/l$d2},T*v2]n

Straightforward approach. It makes a list of all numbers, where if you the the two halves the result is all 9's, and finds which one is closest to the input. If the input is a cyclic number, it will be printed, which is allowed because all non-zero numbers are truthy.
Explanation:
[v               .- A function of v (which will be set to the input) -.
  r              .- Reduce, to find the best answer                  -.
   [p[q          .- A function of p, q                               -.
       ?         .- If                                               -.
        <        .- Compare                                          -.
         a-vp    .- the distance between one number and the input    -.
         a-vq    .- the distance between another number and the input-.
       p]q]      .- Return the closest                               -.
   }}
  f              .- Filter, to find solutions                        -.
   [d            .- A function of d (each possible value)            -.
     [q          .- Set q as... (half of length of d)                -.
       =q        .- Only if q equals...                              -.
         c       .-  the count, within...                            -.
          $      .-   the string form of...                          -.
           +     .-    the sum of...                                 -.
            n#q$d.-     the first q digits of d                      -.
            n+q$d.-     the last q digits of d                       -.
          '9     .- the digit 9                                      -.
     [/l$d2      .- half of length of d                              -.
   }
  ,T*v2          .- the numbers from 10 to double v                  -.
]n               .- With v set as the numeric value of...            -.

.-implicit-.     .- the first line of input                          -.

This passes the test-cases, though I'm not certain that the range is wide enough. If not, it can be increased by changing the *v2 to *v9 or greater.
Unfortunately, there's a bug in the interpreter's s sort-by function, so I had to use waste a few bytes using the r reduce function instead.

How can I download Clip? The esolangs page has the link password protected.

@Maltysen It's now unprotected. Sorry about that.

Python 2, 94 characters
def r(n):
 i=0;s=1
 while 1:
    n+=i*s;M=10**(len(str(n))/2);i+=1;s=-s
    if n/M+n%M==M-1:return n

Note: the last two lines use a tab character for indentation.
Given n, this checks numbers for cyclicity in the following order: n, n-1, n+1, n-2, n+2, etc... If n is a cyclic number, it returns n (which is a truthy value). If it isn't, it returns the closest one that is.

Ruby, 79 chars
p->n{t=n.to_s;s=t.size/2;u=t[0...s];v=t[s..-1];u.to_i+v.to_i==('9'*s).to_i}.(13358664)

Bash + coreutils, 118
m=$[10**(${#1}/2-1)]
jot -w%dd$1-n32Ppc $[m*9] $m$[m*9-1] $[(m*10-1)*m*10]|dc|tr -d -|sort -n|sed -n "/$1/!s/.* //p;q"

Calculates all cyclic numbers with the same number of digits as the input number, then uses sort to find the closest.  In true unix fashion, nothing is printed for the "true" / "success" case, but the nearest cyclic number is printed if the input is not cyclic.

Python 3
209 hardcoded or 200 with user input
x = [142857, 13358664, 18, 133249]
i=int
def g(x):
    a,b=str(x),i(len(str(x))/2)
    return (lambda d,c:i(d)+i(c)==10**len(d)-1 and x or g(i(d+c)-1))(a[:b],a[b:])
for y in x:print((g(y)==y and True or g(y)))

Output:
True
True
True
132867

The implementation here is fairly simple. I see other entries are quite shorter; so I'm not aiming to win here, just wanted to try. This code-golfing is still very new to me.
Amendment
Having user input is simple; with one exception. For some numbers the function will throw a RuntimeError if the recursion depth hits its limit while trying to obtain a valid number counting down. That means any reasonable programmer should eat this error apporpriately and simply return False. The exception also catches any number below 27.
i=int
def g(x):
    a,b=str(x),i(len(str(x))/2)
    try:return(lambda d,c:i(d)+i(c)==10**len(d)-1 and x or g(i(d+c)-1))(a[:b],a[b:])
    except:return False
y=input();print((g(y)==y and True or g(y)))

Amendment II
Actually, now that I think of it, the user input should take less time when the output is not True:
y=input();z=g(y);print((z==y and True or z))

I like your use of recursion. Can you put it in a format that allows user input? (Don't hardcode x)

@aks like that?

Yeah, except you you change it to just input() to save a couple bytes.

@aks. there you go