text:
Crack a Vigenère Cipher
A Vigenère Cipher is encrypted by repeating a keyword to be the length of the plaintext, and summing each character in that text with the corresponding letter in the plaintext modulo 26. (using A=0,B=1 etc.)
For example, if the keyword is LEMON and the plaintext is ATTACKATDAWN, then the key is repeated to form LEMONLEMONLE, which is summed with the plaintext to form the ciphertext, LXFOPVEFRNHR.
Write a program or function which, given a list of words and a ciphertext, outputs all possible plaintexts for that ciphertext, such that the plaintext is the concatenation of words in the list, and the key is also a word from the list.
All words use only upper-case letters A to Z.
Your code must run in polynomial time with respect to the total length of the ciphertext and words list.
Shortest code (in bytes) wins.
Example Inputs/Outputs
The input/output format for your program is flexible, but here I'm giving the list of words separated by commas followed by the ciphertext as input, and the output is the list of plaintexts separated by commas.
Inputs
LEMON,ATTACK,AT,DAWN,BUNNY
LXFOPVEFRNHR

A,AA,AAA,AAAA,AAAAA,AAAAAA,AAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

XHQT,GIXIIR,QTIA,AZXO,KSECS,THIS,CIPHER,IS,EASY,TO,CRACK,CODE,GOLF
ZVTXIWAMKFTXKODDZCNWGQV

A,B,C,D,E,F,G,H,Z
DBCCBHF

A,AA
AAA

Outputs
ATTACKATDAWN

(none)

THISCIPHERISEASYTOCRACK,XHQTGIXIIRQTIAAZXOKSECS

BZAAZFD,CABBAGE,DBCCBHF

AAA

Was about to post something similar... lol

Doesn’t respect specifications – OCaml - 118 bytes
I’ll get back to it when I’ll have time on my hand.
open Char;;
fun m->List.map(fun k->String.mapi(fun i c->chr(65+(code c-code k.[i mod String.length k]+26)mod 26))m);;

- : string -> string list -> string list = <fun>

As the function type shows, the function expect as arguments:

a string: the encoded message
a list of strings: the keys

It returns a list of strings, the messages as decoded by each string in the same order.
The function is anonymous, you can call it by inserting putting it inside parentheses (i.e. 2 bytes) and entering its arguments as follows:
open Char;;
(fun m->List.map(fun k->String.mapi(fun i c->chr(65+(code c-code k.[i mod String.length k]+26)mod 26))m)"ZVTXIWAMKFTXKODDZCNWGQV"["XHQT";"GIXIIR";"QTIA";"AZXO";"KSECS";"THIS";"CIPHER";"IS";"EASY";"TO";"CRACK";"CODE";"GOLF"];;

Ungolfed
(* unshift the character x back to what it was before being shifted by k *)
(* Char.chr and Char.code translate from ASCII int to char and back      *)
(* '+ 26' because the modulo operator can return negative numbers -__-   *)
open Char;;
let unshift k x = chr ( 65 + (code x - code k + 26) mod 26 );;
(* Use the n-th character of the key to decrypt x, loops when necessary  *)
let unshiftWithKeyAtPos key n x = unshift key.[n mod String.length key] x;;

(* Maps unshiftWithKeyAtPos key i x for each position i in cipherText    *)
(* where x = cipherText.[i] is the i-th character of cipherText.         *)
let decrypt key cipherText = String.mapi (unshiftWithKeyAtPos key) cipherText;;

(* Maps decrypt cipherText key for each key in keyList                   *)
let tryHard cipherText keyList = List.map (fun key -> decrypt key cipherText) keyList;;

(* And finally, call the function                                        *)
let hiddenMessage = "LXFOPVEFRNHR";;
let keys = ["LEMON";"CODE";"GOLF"];;
tryHard hiddenMessage keys;;

You're outputting plaintexts which aren't a concatenation of words in the list.  Sorry my wording was somewhat unclear, but I did say "the plaintext will be the concatenation of words in the list".
I've edited the question to be more clear about this.

Indeed, I have missed that point. I’ll try and fix it later.

Python 2.7 - 235
Example solution to start things off.  Should be pretty easy to beat.
Input is given as a python tuple from stdin (ex. (["A","AA"],"AAA").
W,c=input();M={}
def s(t,r):M[t]=r;return r
g=lambda t:M[t]if t in M else not t or s(t,any(t.startswith(w)and g(t[len(w):])for w in W))
print filter(g,set(''.join(chr((ord(a)-ord(w[i%len(w)]))%26+65)for i,a in enumerate(c))for w in W))

source: Stack Exchange

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

sort: votes


text:
Match strings with wildcards
Problem: given any input string that does not contain null bytes, determine whether or not the input string matches glob as defined below:
null   is disallowed in both string in glob
*      matches zero or more characters
**     is disallowed in glob
?      matches exactly 1 character
[ch]   matches a character class of the specified characters
       to include ] in a class, it must be the first character
[^ch]  matches a character class of all but specified characters
       to include ] in a class, it must be the first character after ^

The empty glob only matches the empty string.

The system glob() on the target platform implements glob where * doesn't match a /, so you can't use it. This has infested all shells. You could try converting to a regex; however this won't be as easy it it looks.
You must specify an encoding for your program. Your program must be valid in that encoding. All bytes including null are allowed in cp437. Your score is the number of characters in your encoding.
Bonus: If your program is expressed in a well-known encoding that uses 6 or fewer bits, your score is multiplied by the number of bits used in the encoding and divided by 7. Your program will be passed its arguments in ASCII in that case.
Your program will receive the string to match or not as the first argument and the glob pattern as the second argument. Your return code must be 0 on match and nonzero on nonmatch.
You may leave it undefined what happens if you get passed a disallowed glob.
Standard loopholes are disallowed; however the following are allowed:
 You may compress your program but it must work if executed directly.
 Binaries are allowed. Submit a disassembly with it so I can read it.
 Using two different chars which look the same is allowed.
 You may use trigraphs (but I can't see how it helps).

Examples:
"w*c*d" matches "wildcard" but doesn't match "wildcards"
"ww*w*d" matches "wwwdwd" but doesn't match "wwd"
"ww*[w-c]?*" matches "www-" and "wwcc" but doesn't match "wwc"
"[a-c]" matches "-" but doesn't match "b"
"^[*][^]]" matches "^*[" but doesn't match "^?[" or "^*]" or "**]"

Are unmatched brackets like ab[cd or a]b allowed in the pattern? Can a character class have duplicate chars?

All right, removed the null bytes rule as it was pretty useless. The special case of CP437 is to allow binary files to be submitted. (It is questionable whether CP437 allows nulls or not but all non-nulls are valid anyway.)

Yes, [a-c] matching a, -, and c is intentional. This is why converting to regex is hard.

@feersum: ab[cd isn't valid but a]b is. You won't see duplicate characters in a pattern so don't worry about it.

I assume, though it is not specified, that [^] matches ^ and [^]] matches anything but ].  I'm a bit confused, though: Couldn't [^]] also match ^]?  I guess my question is - How does one specify a character class of just ^?

Indeed [^]] matches anything but ]. [^] isn't a character class as it's missing its closing ]. A character class of just ^ doesn't need square brackets.

Should "[a-c] " match "-"? There's a trailing space in the glob but not in the string.

@senshin: Fixed typo, thanks.

The last two loopholes you mention (lookalike chars, trigraphs) only apply to underhanded challenges, where you write code to solve task A that appears to do something else. There's no need to explicitly allow them in a regular code golf challenge.

I suppose backslashes must be treated literally, right? i.e. wild\ness would be matched by w*\*s

Right, backslash is just another literal.

Inconsequentially, I think you mean the system fnmatch(), not the system glob(). (fnmatch() matches strings; glob() matches files in the filesystem.) The actual fnmatch() has a FNM_PATHNAME flag to control whether wildcard patterns cannot match /.

Common Lisp, 368 340
Encoding is implementation-dependent, but UTF-8 is generally supported among implementations (see also the set of standard characters that must be supported).
(ql:quickload'cl-ppcre)(lambda(s g)(ppcre:scan(do(e(L(coerce g'list))c p)((not L)`(:sequence,@(reverse e):end-anchor))(push(case(setf c(pop L))(#\*'(:regex".*"))(#\? :everything)(#\[(prog1`(,(or(and(char=(car L)#\^)(pop L):inverted-char-class):char-class),@(subseq L 0(setf p(position #\] L :start 1))))(setf L(nthcdr(1+ p)L))))(t c))e))s))

Pretty-printed
(lambda (s g)
  (cl-ppcre:scan
   (do (e
        (l (coerce g 'list))
        c
        p)
       ((not l) `(:sequence ,@(reverse e) :end-anchor))
     (push
      (case (setf c (pop l))
        (#\* '(regex".*")
        (#\? :everything)
        (#\[
         (prog1
             `(,(if (char= (car l) #\^)
                    (prog1 :inverted-char-class (pop l))
                    :char-class)
               ,@(subseq l 0 (setf p (position #\] l :start 1))))
           (setf l (nthcdr (1+ p) l))))
        (t c))
      e))
   s))

Converting to regex is not so hard when using non-string representations of regexes. CL-PPCRE is a regular expression library by Edi Weitz which accepts two ways of defining such expressions:

the usual string-based syntax, or
a more lispy approach using a DSL

Today I answered a question about alternative syntaxes for regular expressions, and this challenge is a good example of why a structured format can be useful instead of strings.
Example
For the following glob, "ww*[w-c]?*", the regular expression being built is described by this form:
(:sequence #\w
           #\w
           (:regex ".*")
           (:char-class #\w #\- #\c)
           :everything
           (:regex ".*"))

And we match "www-". The (:char-class ...) list takes indiviudal charaters, which does not need escaping like it would if I wrote "[w-c]" as a string regex.
Test suite
(loop for (glob match no-match) in
      '(("w*c*d"      ("wildcard")    ("wildcards"))
        ("ww*w*d"     ("wwwdwd")      ("wwd"))
        ("ww*[w-c]?*" ("www-" "wwcc") ("wwc"))
        ("[a-c]"      ("-")           ("b"))
        ("^[*][^]]"   ("^*[")         ("^?[" "^*]" "**]"))
        ("w*\\*s"     ("wild\\ness")  ()))

      for matchp = (lambda(s)(funcall *fun* s glob))

      always (every matchp match)
      never (some matchp no-match))

=> T

MUMPS, 397 387 bytes
Note that this code uses features of Caché ObjectScript (specifically, the * designator in a $EXTRACT call) and does not conform to the ANSI MUMPS standard.
f(g,s) f i=1:1:$L(g) d
    . s c=$E(g,i) i 'm s:"*?[]"'[c p=p_"1"""_c_"""" s:c="*" p=p_".E" s:c="?" p=p_"1E"
    . i c="]" s p=p_"1"_$E(b,1,*-1)_")" s m=0
    . s:c="[" a=$E(g,i+1)="^",m=a+1,b="(",i=i+a
    . i m s:$E(g,i+1)="]" d=1 s k=$F(g,"]",i+d)-2+d,r=$E(g,i+1,k),i=k
    . f j=1:1:$L(r) s:m=1 b=b_"1"""_$E(r,j)_""","
    . i m=2 f j=0:1:127 s:r'[$C(j) b=b_"1"""_$S(j=34:"""""",1:$C(j))_""","
    q s?@p

Haha, OP! I've foiled your plans! Sure, your glob syntax might be tricky to convert to a regex, but my language has no regexes! Instead, it has a crippled form of "pattern matching" (see docs, section 5.7) that happens to be pretty much exactly powerful enough to handle these globs.
Basically, what the code does is it converts OP-style globs into a string corresponding to the pattern match, and then evals that string, and tests the input string against the result of that eval. The one tricky point is that MUMPS pattern matches don't have a notion of an inverted character class ([^abc]), so we instead have to construct a character class consisting of all the ASCII characters except the ones specified in in the inverted character class.
Here are some correspondences between OP-style globs and MUMPS pattern matches:
OP              MUMPS
-----------------------------------------------------------
w*c*d           1"w".E1"c".E1"d"
ww*w*d          1"w"1"w".E1"w".E1"d"
ww*[w-c]?*      1"w"1"w".E1(1"w",1"-",1"c")1E.E
[a-c]           1(1"a",1"-",1"c")
^[*][^]]        [doesn't print well, because of the inverted character class thing]

There is probably room for additional golfing here. Here is an ungolfed version:
match(glob,string) ;
    ; the golfed version assumes a clean symbol table; here, I've explicitly cleaned it.
    new i,pattern,char,mode,buffer,range,advance,delta,j,k
    for i=1:1:$LENGTH(glob) do
    . set char=$EXTRACT(glob,i)
    . if ("*?[]"'[char),(mode=0) do
    . . set pattern=pattern_"1"""_char_"""" ; 1 of `char`
    . if (char="*"),(mode=0) do
    . . set pattern=pattern_".E" ; 0+ of any character
    . if (char="?"),(mode=0) do
    . . set pattern=pattern_"1E" ; 1 of any character
    . if (char="]") do
    . . set pattern=pattern_"1"_$EXTRACT(buffer,1,$LENGTH(buffer)-1)_")"
    . . set mode=0
    . if (char="[") do
    . . set advance=($EXTRACT(glob,i+1)="^") ; 0 or 1
    . . set mode=advance+1 ; 1 = in a char class; 2 = in an inverted char class
    . . set buffer="(" ; begin constructing an alternation
    . . set i=i+advance
    . if (mode'=0) do
    . . if ($EXTRACT(glob,i+1)="]") do
    . . . set delta=1
    . . . set k=$FIND(glob,"]",i+delta)-2+delta
    . . . set range=$EXTRACT(glob,i+1,k)
    . . . set i=k
    . for j=1:1:$LENGTH(range) do
    . . if (mode=1) do
    . . . set buffer=buffer_"1"""_$EXTRACT(range,j)_"""," ; add a character to the alternation
    . if (mode=2) do
    . . for j=0:1:127 do
    . . . if (range'[$CHAR(j)) do
    . . . . set buffer=buffer_"1"""_$SELECT(j=34:"""""",1:$CHAR(j))_""","
    quit string?@pattern ; eval `pattern` and test `string` against it, and return the outcome (0 or 1)

You didn't foil my plans. you did exactly what my plans were to require -- that is, parse and rebuild the glob before passing it into any match library.

Ceylon, 3514 2586 2360 2248 2228 2196 2059 1882 1620 1147 1130 858 830 693 658 bytes
import ceylon.language{B=Boolean,S=String,C=Character,o=false,r=process}shared void g(){B n(B(S)l,B(S)r)(S c)=>any{for(i in 0..c.size)l(c[0:i])&&r(c[i...])};B q(S c)=>c.size==1;B d({C*}s,B n)(S c){if(q(c),exists i=c[0]){return n!=i in s;}return o;}[B(S),S]h(S r){assert(exists s=r[0],exists e=r.firstOccurrence(']'));return[s=='^'then d(r[1..e],true)else d(r[...e],false),r[e+1...]];}B(S)p(S x){if(exists f=x[0]){value r=(f=='*'then[(S c)=>true,x.rest])else(f=='?'then[q,x.rest])else(f=='['then h(x.rest))else[d({f},o),x.rest];return n(r[0],p(r[1]));}else{return S.empty;}}assert(exists x=r.arguments[1],exists c=r.arguments[0]);r.exit(p(x)(c)then 0else 1);}

It seemed first that converting the glob to regular expressions is the easiest, but it also means escaping everything which is special in regular expressions but not in our globs ... I might try this in a different answer.
Due to popular demand I removed most of the the how-I-got-there .. who is interested, can have a look into the history.
So I build a new (limited) regexp-like matching engine, and a parser to convert our wildcard strings into such strings. (And some boiler plate for command line access and return code generation.)
Here is the same program formatted (i.e. with added whitespace) and with some documentation annotations:
import ceylon.language {
    B=Boolean,
    S=String,
    C=Character,
    o=false,
    r=process
}
"""A glob evaluation program.
   Takes two command line arguments, first is a candidate string,
   second one is a wildcard expression.

    Exits with code 0 if the expression is well-formed and
    matches the candidate, otherwise exits with 1.
   """
shared void g() {
    """A string predicate build from a left and a right predicate.
       It matches a string if that can be split in two substrings
       so the first one is matched by the left expression and
       the second one by the right expression.
       """
    B n(B(S) l, B(S) r)(S c) =>
            any {
        for (i in 0..c.size) l(c[0:i]) && r(c[i...])
    };

    """An expression which matches any string of length 1 (i.e. a single character).
       This corresponds to the question mark (`?`), therefore the name.
       """
    B q(S c) => c.size == 1;

    """A character class, i.e. an expression which matches any string of length 1,
       as long at it is (or is not) in a given list of characters.
       """
    B d(
        "The characters to be matched (or excluded)"
        {C*} s,
        "Is this negated? If true, matches only characters not in the list."
        B n)
            (
        "The candidate string."
        S c) {
        if (q(c), exists i = c[0]) {
            return n != i in s;
        }
        return o;
    }

    """Parses a started character class (i.e. the stuff after the `[`).

       Returns a tuple of the constructed matching function
       and the remaining string to be parsed for further expressions.
       """
    throws (`class AssertionError`, "if the expression is not well-formed, i.e. there is no `]` following.")
    [B(S), S] h(S r) {
        assert (exists s = r[0], exists e = r.firstOccurrence(']'));
        return [s == '^' then d(r[1..e], true) else d(r[...e], false), r[e + 1 ...]];
    }

    """Parses an glob expression from a string.
       Returns a string predicate.
       """
    B(S) p(
        "The string with the wildcard expression."
        S x) {
        if (exists f = x[0]) {
            value r = (f == '*' then [(S c) => true, x.rest])
                    else (f == '?' then [q, x.rest])
                    else (f == '[' then h(x.rest))
                    else [d({ f }, o), x.rest];
            return n(r[0], p(r[1]));
        } else {
            return S.empty;
        }
    }
    assert (exists x = r.arguments[1], exists c = r.arguments[0]);
    r.exit(p(x)(c) then 0 else 1);
}

I'm not sure if this is actually readable enough ... see the history of this answer for the original version with more readable names (and which was using interfaces and objects instead of just functions).
Some used tricks to make this shorter:

import with alias – we use String, Boolean and Character quite often, so give them one-letter aliases. When we are already doing this, adding the renaming for process (used three times) and false (used twice) doesn't take much overhead. (This only helps for stuff used several times – the ceylon.language stuff is imported automatically, so we have some overhead here.)
The possibleMatchLengths method was an optimization for speed – not needed when we are code-golfing. (I guess this can make matching quite slow in some extreme cases.)
the Implementations of the string attribute was also removed, it was just there for debugging the initial versions.
Instead of the implementations of the Glob interface in the first versions, we have just functions Boolean(String) (or B(S) in our short format), which saves quite some braces and class/object, and some functions returning such functions. Ceylon has a nice syntax for defining functions which return functions, used for the GlobList g and the CharacterClass c – simply a function with multiple argument lists.
I unified the methods for CharacterClass and NegatedCharacterClass, passing a boolean parameter for negated. It is used as negated != i in chars (shorter n!=i in s) instead of having one function with i in s and one with !i in s (and both having the remaining conditions twice).
The object/function emptyGlob was replaced by the static Reference String.empty (written S.empty, of course).
Where a function consists of just one return statement, we can write it with the "fat arrow" notation and save the braces and the return.
If such a function is used just once, sometimes we can put it directly where used, as an anonymous function definition. This is used for the * implementation.
The function q (for the question mark) is in addition used in the definition of the character class function d, as q(c) is shorter than c.size==1.
Instead of first defining a value with value f = ... or even with type Character f = ... and then doing an if (exists f) { or assert(exists f);, we can move the definition into the if or assert, saving some characters.
If we want to pass an iterable constructed from a comprehension to a function (like the any function used in the definition of g), we can write any{...} instead of any({...}) – this is the named argument syntax, which converts its last entry, if it's a comprehension, into an iterable, if the function accepts that.

You could reduce your byte count by eliminating unnecessary whitespace and shortening variable names to single characters.

@AlexA. yes, I'll do that at the end, when I find nothing else to do.

Was your goal to make your post as long as possible? Maybe golf it first, then post it.

While I appreciate explanations, I think you can remove previous versions of the code. After all, each answer's history is recorded.

As far as I'm concerned, he can leave it. We need a tutorial from time to time.

@mbomb007 I removed all the previous versions, and added some explanations and an expanded version here. (Also, got some more savings.)

@coredump Yes, in this case I guess you are right. I removed the old versions.

Perl, 88 bytes
$_=pop;s/((\*)|\?)|(\[\^?\]?)(.*?)\]|\W/$1?".$2":$3?qr#$3\Q$4\E]#:"\\$&"/eg/pop=~/^$_\z/

The encoding is ASCII. This works by translating to regular expressions with regular expressions. It exits with a division by zero error (hence, nonzero status) on match failure.
Some ideas adapted from recursive’s Python solution.

I was wondering when a Perl solution would appear.

Python 3, 209 207 bytes
The general strategy is transforming the glob spec into a regex.  That's accomplished by a function r, passed as the replacement parameter to re.sub(), (or s() in this case).  If no match is found, a run-time error is thrown, causing a positive exit code.
import sys,re
_,t,g=sys.argv
s=re.sub
def r(m):a,b,c,d,e=m.groups();return a and s(r"(?=[-\\])",r"\\",a)or b and".*"or c and"."or d and"\\"+d or e
re.match(s(r"(\[\^?.+?\])|(\*)|(\?)|(\W)|(.)",r,g)+"$",t).re

The patterns produced for the example globs show how it works.
Glob            Regex pattern
w*c*d           w.*c.*d$
ww*w*d          ww.*w.*d$
ww*[w-c]?       ww.*[w\-c].$
[a-c]           [a\-c]$
^[*][^]]        \^[*][^]]$
a[\]b           a[\\]b

Beware of backslashes. Running python file.py 'wildcard' 'w*[\]*d' results in a traceback.

@coredump: Good find.  I fixed it and made it smaller.

CJam, 125
{AC+:A;}:F;0alqW+:X;{"*?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)
^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F"N/T=S/(C#=~}fCX,(\-!

CJam has no regular expressions (yet), so I just implemented the wildcard matching directly.
The encoding here is plain old ASCII (I might try some compression tricks later).
Try it online
Explanation:
The idea is to go through the pattern (glob) and keep a list of indices possibly reached so far in the input string. Initial list is [0], ? advances all indices by 1, * goes to all indices from the minimum reached so far to the end of the string, and character sets and other non-special characters just select the indices that match and advance them by 1. At the end, the string matches if the list of indices contains the string length.
Character sets are constructed on the fly and recorded as a string A and a boolean flag B (for positive/negative match), and used when reaching the closing ].
{…}:F;      define a function F
  AC+:A;    add variable C to variable A (A+=C)
0a          push [0] (initial array of indices, let's call it I)
             it will be kept and updated on the stack
l           read the first input line (containing the pattern)
q           read the rest of the input (the string to match)
W+          append the number -1 (as an array element, following the characters)
             this is a dummy guard value that avoids costly empty-string checks
:X;         save the array in X
{…}fC       for each character C in the pattern
  "…"       push that long string, containing code to handle various cases
  N/        split into (two) lines
  T=        get the T'th line; T is 1 when parsing a character set and 0 otherwise
             (T is initially 0 by default)
  S/        split by space into an array of strings
  (         take out the first item (containing special characters to check)
  C#        find the index of C in that string
  =         get the corresponding string from the array
             (when C is not found, # returns -1 which gets the last array item)
  ~         execute that string
X,(         get the length of X and decrement it
             (to get the length of the input string)
\-          calculate the set difference between it and I (the list of indices)
             the result is empty (false) iff I contained the string length
!           negate, to obtain the final 1/0 result

Now the long string with various pieces of code. Each line has a few characters to check and then a block for handling each one, and the default case.
First line: *?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)
*?[       special characters to look for
######### first block, corresponding to character *
_         duplicate I on the stack
{…}&      if I is not empty
  0=      get the first (smallest) index from I
  X,      get the length of X (1 longer than the input string)
  ,       make an array [0 1 2 … length(input string)]
  >       slice the array starting at the smallest index from I
######### second block, corresponding to character ?
:)        increment all items of I
######### third block, corresponding to character [
1:T       set T=1, causing the next characters to be processed with the 2nd line
:B;       also set B=1, the boolean flag signifying positive match
L:A;      initialize A (the array of characters) with an empty string/array
######### last block, corresponding to other regular characters
{…},      filter I's items, using the block as a boolean condition
  X=      get the character from X at the given index (it wraps around)
           if the input string was empty, this will be -1 (the dummy value)
  C=      compare to C (the current character in the pattern)
:)        increment the remaining indices

Second line (for character sets): ^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F
^]        special characters to look for
######### first block, corresponding to character ^
A!B&      calculate not(A) & B, which is 1 (true) iff A is empty and B is 1
{…}       if true (first character and positive match, i.e. we're at "[^")
  0:B;    set B=0 (switch to negative match)
{…}       else
  F       call F, which just adds the character C to A
?         end if
######### second block, corresponding to character ]
A{…}      if A is not empty (it's a closing "]")
  0:T;    set T to 0, switching back to the first line
  {…},    filter I's items, using the block as a boolean condition
    X=    get the character from X at the given index
           if the input string was empty, this will be -1
    A-    calculate the set difference between it and A
    !     negate, obtaining 1 if the character was in A and 0 if it was not
    B=    compare to B (the positive/negative match indicator)
  :)      increment the remaining indices
{…}       else (A is empty, i.e. we're at "[]" or "[^]")
  F       call F to add the character to A
?         end if
######### last block, corresponding to other regular characters
F         call F

+1 This is interesting, but I am not sure I understand exactly how it works ;-)

@coredump check it now :) I also got another golfing idea while writing :p

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


text:
Capture on the Pawn Chessboard
You should write a program or function which receives a string representing a chessboard with only pawns as input and outputs or returns whether any capture is possible on the board.
Input is in a FEN-like notation describing positions of white and black pawns with no other pieces present. You should decide if there is a pawn which can capture an enemy one.

Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Each pawn is identified by a single letter (white pawn = "P", black pawn = "p", ). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks. (partially taken from Wikipedia)

For example
8/pppppppp/8/8/4P3/8/PPPP1PPP/8

describes the board
--------

pppppppp

    P

PPPP PPP

--------

A white pawn can capture a black one if the black one is positioned diagonally up from it (black is up-left or up-right) and a black pawn can capture a white one if the white one is diagonally below from it (white is down-left or down-right). No other capture move (en passant) should be considered.
Input

A FEN-like string consisting of the characters 12345678pP/.
The input describes the pawns of a valid chess game position. This means (among other more complex constraints) there will be at most 8 pawns for each side and no pawns on ranks 1 and 8.

Output

If there is a possible capture for either side you should output a truthy value and a falsy value otherwise.

Examples
Inputs with truthy output (one per line)
8/7p/6P1/8/8/8/8/8
8/8/p7/1P6/3P3p/8/8/8
8/2P5/8/4P1p1/2p2P2/3p4/3p1P2/8
8/P7/8/5P2/2pp4/3P2p1/3pP3/8
8/P7/p7/p1P1P3/1P3p2/8/1p6/8
8/4p1P1/2P2P1P/2p1pPpp/8/6P1/pP1p4/8

Inputs with falsy output (one per line)
8/8/8/8/8/8/8/8
8/7P/6p1/8/8/8/8/8
8/7p/7P/8/8/8/8/8
8/pppppppp/8/8/8/8/PPPPPPPP/8
8/p7/8/1p6/5P2/8/8/8
8/p7/P7/2P1p1p1/2p5/8/PP6/8

This is code golf so the shortest entry wins.

Shouldn't the example board be described by 8/pppppppp/8/8/8/7P/PPPP1PPP/8 ?

@TheNumberOne No, 7P would mean the pawn is on the last, 8th file. (The diagram was incorrect though, I corrected that.)

I feel removing en passant makes this a less interesting puzzle.

@corsiKa en passant requires more than one board to verify. For that, a very different approach is required.

@Razetime The same argument could be made for removing it, so meh... 5 years later is still feel the same way.

Did not expect such a quick response. Maybe I'll make a challenge for finding all possible captures.

Pyth, 25 bytes
/smC,>JsXz`M9*LN9dJ,8T"Pp

Test suite
Steps:
Transform the input by replacing the digits with the equivalent number of quote marks (N). This is saved in J. We then slice off the first 8 or 10 characters, and zip the result with the original. Any capturing pair will be transformed into "Pp", so we then find the count of that string in the resultant list. This is the output.
As a bonus, this actually counts the number of captures possible in the input.

Another 25 solution: :sXz`M9*LN9"p.{7}(..)?P"1
Sadly the last parameter of : is not optional (I think it should be).

@Jakube Will do.

Retina, 33 29 bytes
T`d`w
)`\d
$0.
_

p.{7}(..)?P

To run the code from a single file, use the -s flag.
Should be easily beatable by something like Perl where the expansion of digits into strings of spaces (or other characters) doesn't take up 17 bytes.
The output is positive (truthy) if there is a possible capture and zero (falsy) if there isn't.
Explanation
T`d`w
)`\d
$0.

This is a loop of two stages. The first one is a transliteration stage which decrements each digit, and turns zeroes to underscores. Why? Because d and w expand to the following two lines:
0123456789
_0123456789AB...YZab...yz

If the target set of a transliteration stage is longer than the source set, the extraneous characters are ignored, hence the decrementing behaviour (honestly, it was just luck that I decided to put the underscore in front of the digits when expanding the w character class).
Then the second stage is a replacement, which appends a . to each digit. That means that for each digit n, n periods are added before that digit is turned into an underscore.
_
<empty>

This just gets rid of the underscores.
p.{7}(..)?P

Finally, we find the matches. Since we're ignoring en passant, captures are only possible if there is a p and then a P diagonally below it. In the linear string, this simply means that there must be 7 or 9 characters between the two pawns. This matched with .{7}(..)? (i.e. match 7 characters and then, optionally, match another two).
Such a match stage returns the number of matches it found.

Re "Should be easily beatable by something like Perl where the expansion of digits into strings of spaces (or other characters) doesn't take up 17 bytes.": I can't get Perl to even tie your score, let alone beat it. (My Perl answer.) But maybe someone else can....

Javascript, 272 characters
function h(t){b=[[]];for(i=-1;i++<7;){c=0;b.push(l=[]);for(j=-1;j++<7;){o=t.split('/')[i][j];switch(o){case'P':l[c++]=-1;break;case'p':l[c++]=1;break;default:c+=parseInt(o);}}}b.push([]);for(i=1;i<9;i++)for(j=0;j<8;j++)if((p=b[i][j])&&(b[i+p][j-1]||b[i+p][j+1]))return 1;}

There's probably a lot of room for improvement.

Ruby, 145 123 46 bytes
->b{b.gsub(/\d/){|x|?.*x.to_i}=~/p.{7}(..)?P/}

I don't know why I didn't think about this in the first place. It's much shorter and also pretty readable.
Here's the test: http://ideone.com/Gzav8N

The old approach:
->b{l={}
r=p
b.split(?/).map{|s|c={}
i=0
s.chars.map{|x|n=x.to_i;c[i]=x;i+=n<1?1:n;x==?P&&r||=l[i-2]==?p||l[i]==?p}
l=c}
r}

Online test: http://ideone.com/9L01lf, version before golfing: http://ideone.com/CSmqlW
A history of modifications is available here.

ES6, 64 bytes
An appropriate byte count, if it lasts!
f=s=>/p.{7}(..)?P/.test(s.replace(/\d/g,n=>"        ".slice(-n)))

I actually thought of this solution without reading the other answers first, but I won't mind if you don't believe me.

Pip, 21 bytes
`p.{7}(..)?P`NaRXDsX_

Verify all test cases!
Explanation
Same regex-based solution as most of the other answers.
`p.{7}(..)?P`NaRXDsX_
              a        1st command-line argument
               R       Replace
                XD      regex matching a digit
                  sX_   with space repeated that many times
             N         Count occurrences of
`           `           this regex:
 p                       A black pawn
  .{7}                   followed by any 7 characters
      (..)?              optionally followed by 2 more characters
           P             followed by a white pawn

APL (Dyalog Unicode), 47 bytes
'p.{7}(..)?P'{≢⍺ ⎕S⍬⊢⍵}('\d'⎕R{' '⍴⍨⍎⍵.Match})⍞

I wanted to make a matrix based matching solution for this, but Martin Ender's Regex ended up being simpler.
Try it online!
Explanation
'p.{7}(..)?P'{≢⍺ ⎕S⍬⊢⍵}('\d'⎕R{' '⍴⍨⍎⍵.Match})⍞
                                              ⍞ String input
                            ⎕R                  Perform Regex replacement
                        '\d'                    match all digits
                              {' '⍴⍨⍎⍵.Match}   Execute match(convert to number), replace with that many spaces
             {≢⍺ ⎕S⍬⊢⍵}                         Tally number of matches of left argument in right
'p.{7}(..)?P'                                   Match two opposite colored pawns 7-9 spaces apart

39: ≢'p.{7}(..)?P'⎕S⍬⊢'\d'⎕R{''⍴⍨⍎⍵.Match}⍞

JavaScript (Node.js), 55 51 bytes
t=>/p.{7}(..)?P/.test(t.replace(/\d/g,i=>'1e'+i-1))

Try it online!
Replace numbers with spaces, then
12345678/
 P1234567
p   P1234
56789p
P1234567p ; attempt to make P and p not in neighbor line
       P1 ; and fail
23456789p

Oops basically Neil's solution

Oops basically Neil's solution

Shorter than Jelly!

Japt v2.0a0, 21 bytes
Adaptation of Neil's solution.
r\dÈ°çÃè/p{7ç.}(..)?P

Try it (Includes all test cases)

Perl 5, 30 bytes
29, plus 1 for -pe instead of -e
s/\d/1x$&/ge;$_=/p.{7}(..)?P/

A Perl copy of w0lf's Ruby answer.

PHP, 94 87 80 bytes
for(;$i++<8;)$t[$i]=$s.=" ";echo preg_match("#p.{7}(..)?P#",strtr($argv[1],$t));

That loop+strtr is a lot shorter than preg_replace_callback with str_pad.

Jelly, 88 84 79 72 69 65 64 63 60 bytes
Definitely room for improvement.
ØDṖḊ
”_x
e1£¬
1£iÐ€2Ŀ€
x"3Ŀ€;"ÇFṣ”/
w€⁾pPn0
5ĿUŒDÇ
5ĿŒD6ĿoÇS

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


text:
Shortest code to check if a string has only letters
Your task is to create a program which takes a string, and if it contains any numbers, symbols or other non-letter characters, it throws an error. Else, it returns the original string. (The string may include whitespace)
("Letters" are a-z and A-Z)
Examples:
Input: My name is Joe
Output My name is Joe

Input: My username is Joe32
Output: (insert an error)
(FYI this question has nothing to do with Don't Google google. It was identified as a possible copy.)

Can we read the string from stdin?

Specify the exact ASCII range that is allowed.

@sweerpotato Yes, you can

@minxomat a-z, A-Z, and whitespace.

possible duplicate of Don't google "google"

@mbomb007 In what way is this a duplicate of the linked question?

When you way "whitespace," do you mean any whitespace character, including tabs and newlines, or only spaces?

@Alex A. Yes, I mean any whitespace character

In fact, there are even more whitespace characters in the ASCII range namely vertical tabs, carriage returns and form feeds.

Retina would be a great programming language for this task...

@CᴏɴᴏʀO'Bʀɪᴇɴ Except, I can't think of a way to make it throw an error based on the input. :/

@AlexA. It's a simple "check the input, if fits certain condition, then throw error, else do something else simple" question.

@MartinBüttner Yeah, I was trying to think of a way for the Google one, but idk enough about the structure of Retina for that. Could you get a runtime error by having an invalid configuration string, or is there no way to make that step be skipped?

Stax, 8 bytes
êF┼Aµ╧û┤

Run and debug online!
Shortest solution so far but expect to be defeated soon.
Explanation
Uses the unpacked version to explain.
' Vl+-!uy
' Vl+        Alphabet plus space
     -       Remove from input
      !u     If result is not empty raise division by zero error
        y    Else print input

Julia, 53 bytes
s=readline();ismatch(r"[^a-z\s]"i,s)?error():print(s)

Read a string from STDIN using readline(). If any of its characters are not letters or whitespace (ismatch(r"[^a-z\s]"i, s)) then we error(), otherwise we print(s).

Gema, 14 characters
\W<-L>=@div{;}

Sample run:
bash-4.3$ gema '\W<-L>=@div{;}' <<< 'My name is Joe'
My name is Joe

bash-4.3$ gema '\W<-L>=@div{;}' <<< 'My username is Joe32'
Floating point exception (core dumped)

C++14, 132 126 121 117 121 bytes
#include<iostream>
main(){std::string s;getline(std::cin,s);for(char c:s)if(!isalpha(c)&!isspace(c))throw;std::cout<<s;}

We read a line from stdin, check if each character is a letter or space - if it's not, we throw an error. Finally outputs the input.
Thanks to Alex A for golfing off two bytes

Isn't std::getline defined in <string> header? Also, I think it is C++11 (I am not saying it is not C++14 though)

std::getline isn't defined in <string>. Yes, it probably is - but I'm compiling it in C++14 so I find it safer to write it that way. Thanks anyway :~)! Actually, regular getline is defined in iostream which saves me 5 bytes!

PowerShell, 24 bytes
Filter the pipeline input based on whether it matches the regex:
|?{$_-match'^[a-z\s]+$'}

e.g. try it by piping the string in:
PS C:\> "Test Test"|?{$_-match'^[a-z\s]+$'}
Test Test

PS C:\> "Test ! Test"|?{$_-match'^[a-z\s]+$'}

The error message is silence/empty result.
It matches case-insensitively by default.

Empty result isn't really an error, though? I came up with param($a)if($a-replace'[a-z\s]',''){1/0;exit}$a for 47 bytes.

STATA, 57 bytes
di _r(a)
gl b=1/regexm("$a","^[a-zA-Z ]*$")
di _d($b)"$a"

Uses a regex to match letters and space (STATA's regex doesn't include character classes). Set a variable to 1/match exists. Then it prints a that many times, if match exists=0, it says it's invalid syntax. Otherwise, it prints it 1/1 = 1 time.

CJam, 18 bytes
q_"
"'[,_el^|-!/

The multi-line string contains a tabulator, a space and a linefeed.
Try it online in the CJam interpreter.
How it works
q_                    Read all input from STDIN and push a copy.
  "\t \n"             Push that string.
         '[,_el^      Push all letters. See: codegolf.stackexchange.com/a/54348
                |     Concatenate both strings.
                 -    Remove their characters from the copy of the input.
                  !   Logical NOT. Pushes 0 if there are other characters.
                   /  Split. Doesn't affect output if successful. Errors on 0.

Python 3, 56 characters
import re;print(re.match(r'[a-z\s]+$',input(),2).string)

Usefully, match objects have this attribute string which is

The string passed to match() or search().

while None does not.
In [10]: import re;print(re.match(r'[a-z\s]+$',input(),2).string)
54
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-10-0851dec671d1> in <module>()
----> 1 import re;print(re.match(r'[a-z\s]+$',input(),2).string)

AttributeError: 'NoneType' object has no attribute 'string'

In [11]: import re;print(re.match(r'[a-z\s]+$',input(),2).string)
rffef
rffef

JavaScript, 48 46 45 46 31 Bytes
/[^a-z\s]/i.exec(a=prompt())?q:a

Accepts input, searches for invalid characters, if it finds any, returns a truthy value and thus evaluates the undefined character q. Otherwise, returns null and thus returns the string.
Old version, 44 bytes
~(a=prompt()).search(/[^a-z\s]/i)?eval("@"):a

Tries to evaluate the invalid character @ upon finding a numeric.

Edit 1: -2 bytes, thanks to @Alex A.
Edit 2: -1 byte, reworked. BONUS: Accounts for ALL whitespace! ^_^
Edit 3: +1 byte, added underscore testing.
Edit 4: Back to 46, unreworked.
Edit 5: -2 extra bytes to @edc65 (for old version; -1 for new).

Can you use a regex option to make it case insensitive? I don't know the JS regex flavor but you may be able to do /[^a-z ]/gi to save 2 bytes.

Per the OP's comment, looks like we need to account for all whitespace characters, not just spaces. For that you may be able use /[^a-z\s]/gi.

From the OP's second example, it looks like we are supposed to throw the error if numbers are in the string.

@AlexA. Yeah; by DeMorgan's laws, the negation of a disjunction (the regular expression) results in a conjuction of the negatives of the expression. Input the expression into RegExr.com to get a visual of the matched expressions.

@edc65 I don't know why your comment was upvoted. You are wrong in your statement.

We cannot know everything. I for instance don't know why you posted an aswer without trying the test in the question. Now that you fixed it, you can still save 2 bytes using ~(a=prompt()).search(/[^a-z\s]/i)?eval("@"):a

@edc65 It worked in the beginning; golfing complicated it.

Hassium, 166 Bytes
func main(){r="";foreach(c in input()){c=c.toString();if(!("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ \t\n\r".contains(c)))throw(c);else r+=c;}println(r);}

Run and see expanded here

PHP, 51 48 bytes
<?=preg_match('/[^a-z\s]/i',$a=$argv[1])?e():$a;

Runs from command line, like:
php test.php "Test me"

Using preg_match is shorter than using ctype_alpha as the latter needs whitespaces to be stripped.

As the error wasn't defined in the challenge, calling an undefined function seems the shortest way to generate an error. So this:
php test.php "Test me, 2"

leads to:

PHP Fatal error:  Call to undefined function e()

Edit
Saved 3 bytes by inverting the statement an by using the i-modifier. Thanks to fschmengler.

You can save a few bytes with the case insensitive modifier i instead of a-zA-Z. And even more if you negate the expression: <?=preg_match('/[^a-z\s]/i',$a=$argv[1])?e():$a; (it searches for any character that is not a white space or alphabetic character) I replaced `` with \s because the question said, all whitespaces are allowed.

@fschmengler Thanks a lot - I've updated the answer.

Haskell, 56 bytes
q x|all(`elem`(['a'..'z']++['A'..'Z']++['\t'..'\r']))x=x

Throws the Non-exhaustive patterns in function q error if the string contains forbidden characters.

Python 2, 60 bytes
import re;n=input();print[n][re.sub('[^a-zA-Z\s]+','',n)!=n]

Usage:
$ python -c "import re;n=input();print[n][re.sub('[^a-zA-Z\s]+','',n)!=n]"
"abcdefg"
abcdefg

Python 2, 68 71 70 69 bytes
import re;s=raw_input();print s if re.match(r'[a-z\s]+$',s,2)else 0/0

Thanks to Alex A. and Martin Büttner for saving a byte and NightShadeQueen for another byte!

You should be able to shorten your regex by removing the position anchors and the +. You could also take out one of A-Z or a-z if there's an easy way to make it a case-insensitive regex.

@AlexA. The + has to stay, because the regex ensures that the string consists only of those characters. But I think the anchors might be unnecessary, because IIRC match checks against the entire string anyway (scan looking for substrings instead).

Thanks both. I was able to remove the beginning anchor as yes, match automatically searches from the start of the string.

@AlexA. It looks like I can make the regex case-insensitive with re.match(r'[a-z\s]+$',s,re.I) but it's more bytes than the case-sensitive expression. Thanks though!

re.I is just 2. You could do re.match(r'[a-z\s]+$',s,2)

Ah, hadn't though of that; thanks @NightShadeQueen!

Java 127 Bytes
class A{public static void main(String[]a){String s=System.console().readLine();System.out.print(s.matches("[A-z ]+")?s:0/0);}}

In Java from the command line you can have input and with the help of regular expression [A-z ]+ which matches alphabets and space in the line, you can have this kind of trick.Moreover, 0/0 will throw ArithmeticException.

Ruby, 26 25 bytes
"undefined method `+@' for nil:NilClass (NoMethodError)":
+(gets=~/^[A-z]*$/);print

Previous 26 bytes, "in `/': divided by 0 (ZeroDivisionError)":
puts gets[/^[A-z]*$/]||1/0

C# - 174 157 148 bytes
using System.Linq;namespace System{class A{static void Main(string[]s){if(!s[0].All(char.IsLetter))throw new Exception();Console.WriteLine(s[0]);}}}

usage:
Console application that takes a parameter in the form of a string and checks via LINQ if all the characters in that string are letters. If so, writes it to console. Otherwise throws exception.
Not particularly short. Will keep tinkering!
Edit: Think I'm pretty much done. Can't get it much shorter don't think.


text:
How many three-fruit pies can you make?
A three-fruit pie is made of three different fruits. What is the most three-fruit pies you can make from the quantities of 5 fruits you have?
For example, with
1 apple
1 banana
4 mangoes
2 nectarines
0 peaches

you can make 2 pies:
apple, mango, nectarine
banana, mango, nectarine

Input: Five non-negative integers, or a list of them.
Output: The maximum number of three-fruit pies you can make from those quantities of fruit. Fewest bytes wins.
Test cases:
1 1 4 2 0
2
2 2 2 2 2
3
0 6 0 6 0
0
12 5 3 2 1
5
1 14 14 3 2
6
0 0 1 0 50
0

Leaderboard:

var QUESTION_ID=59192,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

I believe your example is missing two additional options:  Apple, Banana, Mango and Apple, Banana, Nectarine.  Thus the 1 1 4 2 0 test case should produce the output: 4.

@cobaltduck But if you use the Apple and Banana in your first pie (Apple/Banana/Mango), you don't have the Apple or Banana to use in your second pie (Apple/Banana/Nectarine).

@Timmy D:  Ah, got it.  It was not clear that the pies were being made simultaneously.

@cobaltduck I believe they don't have to be made simultaneously, but you can't cheat by reusing the fruits you used for the first one.

@Mr. Lister:  Semantics.  It is sufficient that there was a rule that was ambiguous (to at least one reader) and has since been clarified.

Pyth, 19 18 14 bytes
-1 byte by @FryAmTheEggman
14-byte program by @isaacg
I claim that the number of pies that can be formed from an ascending list [x1,x2,x3,x4,x5] is:
floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3))

Or in code:
JSQhS/Ls~PJ_S3

[See revision history for TI-BASIC and APL programs]
Proof of correctness
Let
s3 = x1+x2+x3
s4 = x1+x2+x3+x4
s5 = x1+x2+x3+x4+x5

We want to show that P(X)=floor(min(s5/3,s4/2,s3)) is always the greatest number of pies for a list x1≤x2≤x3≤x4≤x5 of numbers of fruits 1~5.
First, we show that all three numbers are upper bounds.

Since there are s5 total fruits, and each pie has three fruits, ⌊s5/3⌋ is an upper bound.
Since there are s4 fruits that are not fruit 5, and at least two non-5 fruits are required in each pie, ⌊s4/2⌋ is an upper bound.
Since there are s3 fruits that are neither fruit 4 nor fruit 5, and at least one such fruit is required in each pie, s3 is an upper bound.

Second, we show that the method of taking fruits from the three largest piles always satisfies the bound. We do this by induction.
Base case: 0 pies can obviously be formed from any valid list with P(X)>=0.
Inductive step: Given any list X where P(X) > 0, we can bake one pie, leaving behind a list X' with P(X') >= P(X)-1. We do this by taking a fruit from the largest three piles 3,4,5, then resorting if needed. Bear with me; there's some casework.

If x2<x3, then we don't need to sort the list after removing fruits. We already have a valid X'. We know that P(X') = P(X)-1 because s5' is 3 less (because three fruits of type 1~5 were removed), s4' is 2 less, and s3' is 1 less. So P(X') is exactly one less than P(X).
If x3<x4, then we're similarly done.
Now we take the case where x2=x3=x4. We'll need to rearrange the list this time.

If x5>x4, then we rearrange the list by switching piles 4 and 2. s5' and s4' are still a decrease of 3 and 2 respectively, but s3'=s3-2. This isn't a problem, because if x2=x3=x4, then 2*x4<=s3->2*x4+s3 <= 2*s3 -> (x4 + s4)/2 <= s3. We have two subcases:
Equality, i.e. (x4,x3,x2,x1)=(1,1,1,0), in which case P(X) = 1 and we can clearly make a pie from piles 5,4,3, or:
(s4+1)/2 <= s3, in which case decreasing s4 by an extra 1 doesn't mean an extra decrease to P(X).

Now we're left with the case where x1<x2=x3=x4=x5. Now s3 will also be decreased by 1, so we need (s5/3+1) to be <=s4/2; that is, 8x5+2x1+2<=9x5+3x1, or x5+x1>=2. All cases smaller than this can be checked manually.
If every number is equal, it is clear that we can achieve the bound of ⌊s5/3⌋, which is always less than the other two—we simply go through the numbers in sequence.

Finally we're done. Please comment if I'm missing something, and I'll be giving a small bounty for a more elegant proof.

I think your claim matches @fryamtheeggman's iterative solution.

@Sparr I'm trying to prove my bound is reachable using fryamtheeggman's method.

This can be golfed by 4 bytes by turning it into a loop: JSQhS/Ls~PJ_S3

I believe I have found a proof for n ingredients and k ingredients per pie, but it is too long for this comment box. Please point out any errors you might find, so that we can get this proved.

CJam, 34
q~L{J2be!\f{\.-_W#){j)7}|;}0+:e>}j

Try it online
Explanation:
q~          read and evaluate the input array
L{…}j       calculate with memoized recursion and no initial values
             using the input array as the argument
  J2b       convert 19 to base 2 (J=19), obtaining [1 0 0 1 1]
  e!        get permutations without duplicates
             these are all the combinations of three 1's and two 0's
             which represent the choices of fruit for one pie
  \         swap with the argument array
  f{…}      for each combination and the argument
    \       swap to bring the combination to the top
    .-      subtract from the argument array, item by item
    _       duplicate the resulting array
    W#)     does it contain the value -1? (calculate (index of W=-1) + 1)
    {…}|    if not
      j     recursively solve the problem for this array
      )7    increment the result, then push a dummy value
    ;       pop the last value (array containing -1 or dummy value)
  0+        add a 0 in case the resulting array is empty
             (if we couldn't make any pie from the argument)
  :e>       get the maximum value (best number of pies)

Does memoizing the recursion cost bytes? There's no run-time limit.

@xnor I think it actually saves 1 byte here :)

Haskell, 62 bytes
f x=maximum$0:[1+f y|y<-mapM(\a->a:[a-1|a>0])x,sum y==sum x-3]

This defines a function f that takes in the fruit list x and returns the maximum number of pies.
Explanation
We compute the number of pies recursively.
The part mapM(\a->a:[a-1|a>0])x evaluates to the list of all lists obtained from x by decrementing any positive entries.
If x = [0,1,2], it results in
[[0,1,2],[0,1,1],[0,0,2],[0,0,1]]

The part between the outer [] is a list comprehension: we iterate through all y in the above list and filter out those whose sum is not equal to sum(x)-3, so we get all lists where 3 different fruits have been made into a pie. Then we recursively evaluate f on these lists, add 1 to each, and take the maximum of them and 0 (the base case, if we can't make any pies).

C#, 67
Recursively make one pie per iteration with fruits you have the most until you run out.
int f(List<int>p){p.Sort();p[3]--;p[4]--;return p[2]-->0?1+f(p):0;}

Test cases here

Not familiar with C#, but can you perhaps do p[2]-- at the same time as checking p[2]>-1?

good point, I will update the answer in a second.

Pyth, 29
Wtt=QS-Q0=Q+tPPQtM>3.<Q1=hZ;Z

Test suite
Sorts the input list and removes zeroes. Then, as long as you have 3 fruits, decrement the first and two last elements, and add the remaining elements to the list, before sorting it and removing zeroes again. Then increment a counter by 1.
This is actually rather quick so long as there are only 5 fruits, it can solve for very large bins of fruits, i.e. 1000,1000,1000,1000,1000 in under a second.

Can you prove that it's correct?

@aditsu I haven't proved it, but I checked it against yours for several additional values. I haven't really written a proof for something like this before, but I'll try. For now, I'll say it makes sense that it should work because you always take only from the largest piles of fruit, until you exhaust the smaller ones. While greedy strategies are obviously not always inherently correct, I can't think of why it doesn't work here.

@FryAmTheEggman Do I understand right that you take the two most common fruits and the rarest fruit?

@xnor Yes, that is correct. Does that not work?

@FryAmTheEggman Not sure, but I haven't found a counterexample by hand. I'll try throwing more test cases at it.

@FryAmTheEggman Seems to work on all examples with nums up to 20.

So long as they're sorted at the outset, do you need to re-sort your fruits after you remove 0's? I used a similar greedy algorithm in my PowerShell answer with and without re-sorting on each loop, and all test cases I throw at them are equivalent.

@TimmyD No, I don't (think I) have to, however it doesn't cost any bytes to remove this functionality (it actually costs more). That said, I expect Reto Koradi's solution is shorter in most languages, and obviously Thomas's is much more concise. I think the reason you don't have to re-sort is related to it not mattering which of the 3 smaller piles you take from.

@FryAmTheEggman My quick CJam implementation of Thomas' solution was 24 bytes. So it wasn't really shorter than my solution. Of course there are people who mostly come up with shorter code, but that applies to both approaches.

Python, general solution, 128 92 bytes
-36 bytes from @xnor, you da real mvp
g=lambda l,k:0if k>sum(l)else-(-1in l)or-~g(map(sum,zip(sorted(l),[0]*(len(l)-k)+[-1]*k)),k))

def g(a,k):b=[i for i in a if i];return 0if len(b)<k;c=sorted(b,reverse=True);return 1+g([c[i]-(k-1>i)for i in range(len(c))],k)
This works so long as my proof is correct. If it's not, let me know why so I can try to fix it. If it's uncomprehendable, let me know, and I'll attack it after a few cups of coffee.

Everything seems tight to me now.

@Mego Thanks for working on this! Could you please include the proof in t the SE post? There's a general concern that someone reading this years later might find dead links. The LaTeX formatting should mostly just work in MathJax.

@Mego Oops, I forgot that MathJax isn't enabled here. Hmm, I'll ask what to do.

I'm awarding the bounty for this proof. Congrats!

@Mego Nope, I think your MathCloud link is the best we have.

@Mego I tried golfing your approach and got g=lambda l,k:-(-1in l)or-~g(map(sum,zip(sorted(l),[0]*(len(l)-k)+[-1]*k)),k). The main improvement is not bothering to removed 0's, but instead when we get a -1, we know we've gone one step too far, so we return -1.

No offense @Mego, but it is incomprehensible.

Doesn't work for the test case [1], 2.  Sorry. :P

Your other program still fails.

Sorry for the harsh critique.

Okay, will never, ever let up then. :P

Python 2, 78 bytes
Taking 5 numbers as input: 91 89 88 bytes
s=sorted([input()for x in[0]*5])
while s[2]:s[2]-=1;s[3]-=1;s[4]-=1;s.sort();x+=1
print x

Edit:
 Changing s=sorted([input()for x in[0]*5]) by s=sorted(map(input,['']*5));x=0 saves 1 byte.
Takes 5 numbers as input and prints the number of possible pies that can be made. It takes the same approach as Reto Koradi's answer -without improving byte count- but it felt like this question was missing an answer in Python.
Thanks @ThomasKwa and @xsot for your suggestion.
How it works
 s=sorted([input()for x in[0]*5]) takes 5 numbers as input, puts them in a list
                                  and sorts it in ascending order. The result
                                  is then stored in s

 while s[2]:                      While there are more than 3 types of fruit
                                  we can still make pies. As the list is
                                  sorted this will not be true when s[2] is 0.
                                  This takes advantage of 0 being equivalent to False.

 s[2]-=1;s[3]-=1;s[4]-=1          Decrement in one unit the types of fruit
                                  that we have the most

 s.sort()                         Sort the resulting list

 x+=1                             Add one to the pie counter

 print x                          Print the result

Note that variable x is never defined, but the program takes advantge of some leakage python 2.7 has. When defining the list s with list comprehension the last value in the iterable ([0]*5 in this case) is stored in the variable used to iterate.
To make things clearer:
>>>[x for x in range(10)]
>>>x
9

Taking a list as input: 78 bytes
Thanks @xnor @xsot and @ThomasKwa for suggesting changing the input to a list.
s=sorted(input());x=0
while s[2]:s[2]-=1;s[3]-=1;s[4]-=1;s.sort();x+=1
print x

How it works
It works the same way the above code, but in this case the input is already a list so there is no need of creating it and variable x has to be defined.
Disclaimer: This is my first attempt at golfing and it feels it can still be golfed, so suggest any changes that could be made in order to reduce byte count.

You're allowed to have the input already in a list; s[2]>0-> s[2], since the number in the pile is always nonnegative.

Thomas Kwa pointed out that you may assume the input is already given as a list, so you can just do s=sorted(input()). Also, your current byte count is 89; newlines count as a single char.

@ThomasKwa already pointed out that you could accept the input as a list, but if you insist on accepting multi-line input, replace the first line with the following to save a byte: s=sorted(map(input,['']*5));x=0.

CJam, 23 bytes
0l~{\)\$2/~+:(+_2=)}g;(

Try it online
This takes fruit from the 3 largest piles in each iteration, and counts the number of iterations.
I don't have a mathematical proof that this always gives the correct result. It does for the given test examples, and I'll believe that it works for all cases until somebody gives me a counter example.
The intuitive explanation I used to convince myself: To maximize the number of pies, you need to keep as many piles non-empty as you can. That's because you lose the ability to make more pies as soon as you have 3 or more empty piles.
This is achieve by always taking fruit from the largest piles. I can't think of a case where taking fruit from a smaller pile would lead to a better situation than taking fruit from a larger pile.
I have slightly more formal reasoning in my head. I'll try to think of a way to put it into words/formula.

I've been trying to use induction; maybe we can combine our ideas to find a formal proof.

@ThomasKwa I haven't come up with anything clear enough that would sound convincing if I write it down. It all comes down to the fact that I see absolutely no reason why it would ever be better to take from a smaller stack over a larger stack. While there are clearly situations where taking from a smaller stack would be worse. I also entered some random moderately large numbers into both mine and aditsu's solutions, and they produced the same result. My solution is also consistent with your formula for the examples I tried.

><>, 76 bytes
0&4\/~}&?!/
@:@<\!?:}$-1@@$!?&+&:)@:@
,:&:@(?$n;/++:&+::2%-2,:&:@(?$&~+:3%-3

Turns out sorting in ><> isn't easy! This program relies on the proof put forward by Thomas Kwa to be true, which certainly looks to be the case with the test cases.
The 5 input numbers are expected to be present on the stack at the program's start.
The first two lines sort the numbers on the stack, and the third performs the calculation floor(min((x1+x2+x3+x4+x5)/3,(x1+x2+x3+x4)/2,x1+x2+x3)), taken from Thomas's answer.

Would it be shorter if you calculate all the sums of three/four elements, and the min of those?

@ThomasKwa I looks like that would involve finding the permutations of the input set, summing the topmost 3 and 4 elements of each and taking the smallest of them? I don't think finding the permutations wouid be shorter than the sort/calculate approach I've used, especially in a stack-based language. If know of any handy algorithms for generating permutations in a stack-based language I'd be interested to see :o)

Python 2, 59 bytes
h=lambda l,k=3:k*'_'and min(h(sorted(l)[:-1],k-1),sum(l)/k)

A general method that works for any n and k. The k=3 makes the fruits per pie default to 3, but you can pass in a different value. The recursion uses the fact that strings are bigger than numbers in Python 2, letting the empty string represent the base case of infinity.
This method uses the fact that always taking the most common fruit is optimal, so we consider each possible rank of fruit as a limiting factor. I've reproven that fact below.

Mego's proof made me think of this more direct proof that repeatedly taking the most common fruits is optimal. This is stated with pies of k fruits.
Theorem: Repeatedly taking the k most common fruits gives the optimal number of pies.
Proof: We will show that if N pies are possible, then the most-common-fruit strategy produces at least N pies. We do this by switching fruits among the N pies to make them match the ones produced by this strategy, while keeping the pies valid.
Let's make it so the first pie (call it p) contain the most common fruits. If it doesn't yet, it must contain a fruit i, but not a more common fruit j. Then, the remaining pies have strictly more of fruit j than fruit i, and so some other pie q must contain j but not i. Then, we can swap fruit i from pie p with fruit j from pie q, which keeps N pies having distinct fruit.
Repeat this process until p has the k most common fruits.
Then, set pie p aside, and repeat this process for the next pie to make it have the most common remaining fruits. Keep doing this until the pies are the sequence produced by the most-common-fruit stategy.

PowerShell, 92 Bytes
$a=($args|sort)-ne0;while($a.count-ge3){$a[0]--;$a[-1]--;$a[-2]--;$a=($a-ne0;$c++}($c,0)[!$c]

Uses the same greedy-based algorithm as FryAmTheEggman's answer ... just a lot wordier in PowerShell....
$a=($args|sort)-ne0  # Take input arguments, sort them, remove any 0's
while($a.count-ge3){ # So long as we have 3 or more fruit piles
  $a[0]--            # Remove one from the first element...
  $a[-1]--           # ... the last element ...
  $a[-2]--           # ... and the second-to-last.
  $a=$a-ne0          # Remove any 0's from our piles
  $c++               # Increment how many pies we've made
}                    #
($c,0)[!$c]          # Equivalent to if($c){$c}else{0}


text:
Sieve of Sundaram (for finding prime numbers)
The Challenge
Implement the Sundaram sieve for finding prime numbers below n. Take an input integer, n, and output the prime numbers below n. You can assume that n will always be less than or equal to one million.

Sieve

Start with a list of the integers from 1 to n.
Remove all numbers that are in the form i + j + 2ij where:

i and j are less than n. j is always greater than or equal to i, which is greater than or equal to 1.
i + j + 2ij is less than or equal to n

Multiply the remaining numbers by 2, and add 1.

This will yield all the prime numbers (except 2, which should be included in your output) less than 2n + 2.

Here is an animation of the sieve being used to find primes below 202.

Output
Your output should be every prime integer ≤ n (in ascending order) followed by a newline:
2
3
5

Where n is 5.

Examples
> 10
2
3
5
7

> 30
2
3
5
7
11
13
17
19
23
29

Inputs are denoted by >.

Your example with n=30 is missing 29 in the output.

A trouble with challenges that ask to use a specific method is that it's not clear what modifications one can make. For example, your description checks only (i,j) with i<=j, but the result doesn't change if we ignore this requirement. Can we do so to save bytes?

I never said that you had to check if i <= j. It's just part of how the sieve works. So yes, you can leave out the i <= j in your code. @xnor

How much leeway do we have here? The sieve is equivalent to selecting all odd numbers (because the results are of the form 2n+1) which are not of the form 2(i + j  + 2ij)+1 - can we test this property directly on the potential primes or does our code have to do the times 2 plus 1 at some point?

You must multiply the filtered results by two and add one. @MartinBüttner

Nice challenge! I haven't heard of this method before. I got confused at "except two", as I thought it meant there were two primes not included. Perhaps you should just change it to "except 2" or something similar. Also, I believe you forgot the 5 in the first example (where n is 5), unless this was intentional.

Thanks for the suggestion! I've also fixed the example. @ETHproductions

i must be >1, j must be >i, so the sieve starts with i=2,j=3 and the first eliminated number is i + j + 2ij ->  2 + 3 + 2*2*3 = 17.  How is the example eliminating 4,7,10,12,13,15...?

I'm a little confused by what n is in the whole thing. In the method description, it says that it will generate all primes up to 2 * n + 2. But in the input/output description, it says that the input is n, and the output all primes up to n. So are we supposed to apply the method to generate all primes up to 2 * n + 2, and then drop the ones larger than n for the output? Or should we calculate the n in the method description from the input n?

You should calculate and then drop the ones larger than n. @RetoKoradi

There's a difference between text and formula. In the text, it says "j is always greater than i, which is greater than 1". In the formula, it shows >= for both of these, not >.

I've fixed it. @RetoKoradi

I assume it is legit to take n >= 2 as granted (considering it doesnt make sense to look for primes smaller than 2) as all of the solutions dont consider that case?

Does the initial array have to start with 1, or can it start with 0 to simplify indexing? Do all of the calculations have to be done in that order, or can you pre-calculate the 2n + 2 values?

Pyth, 23 bytes
2j@JSQmhyd-Jm+sdy*Fd^J2

Demonstration
Really just implements the algorithm as given.

Haskell, 93 90 bytes
import Data.List
g n=unlines[show$2*x+1|r<-[[1..n]],x<-2:(r\\[i+j+2*i*j|j<-r,i<-r]),2*x<n]

How it works: [i+j+2*i*j|j<-r,i<-r] are all i+j+2ij which are removed (\\) from [1..n]. Scale to 2x+1 and turn them into a string (show). Join with NL (unlines).

Scala, 115 124 122 115 114 bytes
n=>{println(2);for{m<-1 to n;if !(for{j<-1 to n;i<-1 to j}yield i+j+2*i*j).contains(m);o=2*m+1;if o<=n}println(o)}

An anonymous function; takes n as an argument and prints the result to stdout.

JavaScript (ES7), 107 105 bytes
Array comprehensions are awesome! But I wonder why JS has no range syntax (e.g. [1..n])...
n=>{for(a=[i=1];i<n;a[i++]=i);for(i=0;i++<n;)for(j=0;j<n;a[i+j+++2*i*j]=0);return[for(i of a)if(i)i*2+1]}

This was tested successfully in Firefox 40. Breakdown:
n=>{
  for(a=[i=1];i<n;a[i++]=i); // fill a list with 1..n
  for(i=0;i++<n;)            // for each integer i in 0..n
    for(j=0;j<n;)            //   for each integer j in 0..n
      a[i+j+++2*i*j-1]=0;    //     set the corresponding item of the list to 0
  return[for(i of a)         // filter the list by:
          if(i)              //   item != 0 AND item != undefined
           i*2+1]            // and return each result * 2 + 1
}

Alternative, ES6-friendly solution (111 bytes):
n=>{for(a=[i=1];i<n;a[i++]=i);for(i=0;i++<n;)for(j=0;j<n;a[i+j+++2*i*j]=0);return a.filter(x=>x).map(x=>x*2+1)}

Suggestions welcome!

MATLAB, 98
n=1:input('');m=n;for p=m for i=1:p j=i:p;for k=i+j+2*i*j n(n==k)=[];end;end;end;disp(2*n'+1);

And in a readable form
n=1:input(''); %Ask for the input number (e.g. 100) and form a range
m=n; %Back up the range as we will be editing 'n', but need 'm' as a loop list
for p=m %For each number between 1 and n inclusive
    for i=1:p %'i' is all numbers greater than or equal to 1 up to p
        j=i:p; %'j' is all numbers greater than or equal to i up to p
        for k=i+j+2*i*j %Calculate the numbers to remove, and loop through them
            n(n==k)=[]; %Remove that value from the 'n' array
        end
    end
end
disp([2;2*n'+1]); %An display the list including the number 2 seperated by a new line.

Java8 : 168 165 bytes
N->{int[]A=new int[N*N];int i=1,j;N=N/2;for(;i<N;i++)for(j=i;j<N;)A[i+j+2*i*j++]=1;System.out.println(N>1?2:\"\");for(i=1;i<N;i++)if(A[i]<1)System.out.println(2*i+1);}

For more bigger number data type with wide range can be used. We do not need to iterate for whole N indexes N/2 is sufficient.
To understand properly following is the equivalent method.
static void findPrimeSundar(int N){
    int[] A = new int[N*N];
    int i=1,j;
    N=N/2;
    for(;i<N;i++)
      for(j=i;j<N;)
        A[i+j+2*i*j++]=1;
    System.out.println(N>1?2:"");
    for(i=1;i<N;i++)
        if(A[i]<1)System.out.println(2*i+ 1);
}

N>=2 -> N>1? A[i]==0 -> A[i]<1?

@ThomasKwa Yes you are right. Thanks.

CJam, 35 bytes
2li:V,:)__2m*{_:+\:*2*+}%m2f*:)&+N*

Try it online
This seems somewhat lengthy relative to isaacg's Pyth solution, but it's... what I have.
Explanation:
2       Push a 2, will be part of final output.
li      Get input and convert to integer n.
:V      Save in variable V for later use.
,       Generate list [0 ... n-1].
:)      Increment list elements to get list [1 ... n].
__      Create two copies, one for sieve, and for clamping results.
2m*     Cartesian power, generating all i,k pairs.
{       Loop over all i,j pairs.
  _     Copy pair.
  :+    Calculate sum i + j.
  \     Swap copy of pair to top.
  :*    Calculate product i * j.
  2*    Multiply by 2, to get 2 * i * j.
  +     Add both values, to get i + j + 2 * i * j.
}%      End loop over all i,j pairs.
m       Sieve operation, remove the calculated values from the list of all values.
2f*     Multiply the remaining values by 2...
:)      ... and add 1 to the. We now have the list of all primes up to 2 * n + 2.
&       Intersect with [1 ... n] list, because output is only values <= n.
+       Concatenate with the 2 we pushed at the start.
N*      Join with newlines.

Perl 6, 96 bytes
If I strictly follow the description the shortest I managed to get is 96 bytes.
->\n {$_=@=1..n;for 1..n {for $^i..n {.[$i+$^j+2*$i*$j-1]=0}};2,|.[0..n].map(* *2+1).grep(3..n)}

->\n {
  $_=@=1..n; # initialize array
  for 1..n { # $i
    for $^i..n { # $j
      .[$i+$^j+2*$i*$j-1]=0 # remove value
    }
  };
  2,|.[0..n].map(* *2+1).grep(3..n)
}

If I could do the 2n + 1 on initialization of the array, pre-inserting 2, and limiting that to only the values less than or equal to n; it can be reduced to 84 bytes.
->\n {$_=@=2,{++$*2+1}...^*>n;for 1..n {for $^i..n {.[$i+$^j+2*$i*$j]=$}};.grep(?*)}

If I also ignore that j is supposed to be at least i, I can reduce it to 82 bytes.
->\n {$_=@=2,{++$*2+1}...^*>n;for 1..n X 1..n ->(\i,\j){.[i+j+2*i*j]=$};.grep(?*)}

Example usage:
my $code = ->\n {...} # insert one of the lambdas from above

say $code(30).join(',');
# 2,3,5,7,11,13,17,19,23,29

my &code = $code;
say code 11;
# (2 3 5 7 11)

PHP, 126 Bytes
$r=range(1,$n=$argn/2-1);for(;++$i**2<=$n;)for($j=$i;$n>=$d=$j+$i+2*$i*$j++;)unset($r[$d-1]);foreach($r as$v)echo 1+2*$v."\n";

Online Version

Julia 0.6, 65 bytes
n->[2;(p=setdiff(1:n,[i+j+2i*j for i=1:n for j=i:n])*2+1)[p.<=n]]

Try it online!
Not a great challenge in terms of golfing, but I just had to do it for the name. :)

Husk, 24 bytes
¶↑≤¹:2m+1mDṠ-om§+oDΠΣπ2ḣ

Try it online!
Ok, I'm not sure why increment → isn't working properly here. Once that works, this will be 23 (tied with Pyth).


text:
Levenshtein distance bias
Write a program in a language with name A that, given a string S, outputs the name of a different programming language B. The length of B must be equal to the Levenshtein distance (abbr. "LD") between A and S. To be considered a programming language, B must have an esolangs page or a Wikipedia page.
Example:
(Suppose the program is coded in Python)
Input: Jython
Output: R
Input: Pyt4oq
Output: Go
Input: Rs7hon
Output: C++

The LD between Python and Jython is one, so the output R
You only need to cover up to an LD of up to 12. You can assume that an LD of 0 will never occur.
This is code-golf, so the shortest program in bytes wins.
(This is my first challenge! Feedback is appreciated)

Leaderboard

var QUESTION_ID=58974,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

Why 12? Are there not languages with larger names?

@CᴏɴᴏʀO'Bʀɪᴇɴ It just seemed liek a reasonabl upperbnd.

@ThomasKwa I believe R is a programming language... it could have easily been C, D, etc.

so, you mean a name with a length equal to the Levenshtein distance? What counts as a programming language? Must it have an esolangs/Wikipedia page?

@ThomasKwa Yes (to the first). Either an esolang or wikipedia page will suffice

The LD of "Patton" and "Python" is 2, not 3.

This is a question that implicitly denies the validity of MetaCodeGolf, as it it becomes circular!

O, 107 bytes
Using the tip from @histocrat to make the distance calculation simpler.  Also used languages with The same starting letter to remove a few characters
"pyrodecimal""hakespeare""tackstack""nowflake""nowball""nowman""onata""ADOL""taq""oT""R"""ie\'O<-1-{;}d'Soo

Try it here

C, 183
main(s){char* a[12]={"R","C#","C++","Java","COBOL","Python","Clipper","VBScript","Smalltalk","Javascript","Mathematica","ActionScript"};printf(a[strlen(gets(&s))-!!strchr(&s,67)-1]);}

Picking a language with a one character name lets you cheat with the distance calculation: any string's distance from "C" is just the length of the string, minus one if it includes "C". I imagine R or J could beat this using the same strategy.

How come gets(&s) doesn't crash?

I'm not sure, it works on Anarchy Golf and ideone but is clearly not really cricket. I imagine it's using the unused memory allocated for ARGV.

I'm a bit late, but a[9];main(s){gets(a);s=strlen(a)-!!strchr(a,67);printf("S%s","\0R\0oT\0taq\0ADOL\0onata\0nowman\0nowball\0nowflake\0tackstack\0hakespeare\0pyrodecimal"+s*~-s/2);} is 162 bytes and avoids the worst of the compiler-specific behavior. It still requires ASCII, two's complement ~, and sizeof(int)>1.

PHP, 137 135
Requires error reporting off and PHP 5.4+. Input is GET variable a.
<?=explode(~ß,~ß¼Üß¼ÔÔßµž‰žß¬œž“žß¾Š‹¶‹ß¾‘“›¼ß«¶Ò½¾¬¶¼ß½Š“š˜Š’ßµž‰žŒœ–‹ß²ž‹—š’ž‹–œžß¾œ‹–‘¬œ–‹)[levenshtein(PHP,$_GET[a])-1];

Hexdump:
00000000: 3C 3F 3D 65 78 70 6C 6F - 64 65 28 7E DF 2C 7E AD |<?=explode(~ ,~ |
00000010: DF BC DC DF BC D4 D4 DF - B5 9E 89 9E DF AC 9C 9E |                |
00000020: 93 9E DF BE 8A 8B 90 B6 - 8B DF BE 8D 91 90 93 9B |                |
00000030: BC DF AB B6 D2 BD BE AC - B6 BC DF BD 8A 9D 9D 93 |                |
00000040: 9A 98 8A 92 DF B5 9E 89 - 9E 8C 9C 8D 96 8F 8B DF |                |
00000050: B2 9E 8B 97 9A 92 9E 8B - 96 9C 9E DF BE 9C 8B 96 |                |
00000060: 90 91 AC 9C 8D 96 8F 8B - 29 5B 6C 65 76 65 6E 73 |        )[levens|
00000070: 68 74 65 69 6E 28 50 48 - 50 2C 24 5F 47 45 54 5B |htein(PHP,$_GET[|
00000080: 61 5D 29 2D 31 5D 3B    -                         |a])-1];|
00000087;

Readable version:
<?=explode(' ','R C# C++ Java Scala AutoIt ArnoldC TI-BASIC Bubblegum Javascript Mathematica ActionScript')[levenshtein(PHP,$_GET[a])-1];

Perl 5, 325 276
Using a bit of recursion to calculate the Levenshtein distance.
@X=(P,e,r,l);$y=@Y=split//,pop;sub L{my($n,$m)=@_;return$m,if!$n;return$n,if!$m;my$c=$X[$n]eq$Y[$m]?0:1;(sort{$a<=>$b}(L($m-1,$n)+1,L($m,$n-1)+1,L($m-1,$n-1)+$c))[0]}print qw(C C# C++ Java COBOL Python Clipper VBScript Smalltalk Javascript Mathematica ActionScript)[L(4,$y)-1]

My original version had some issues with the longer inputs.
Till I realised that the Perl sort function sorts alphabetically.
Using substrings instead of arrays turns out to make it slightly longer.
@L=qw(C C# C++ Java COBOL Python Clipper VBScript Smalltalk Javascript Mathematica ActionScript);sub l{my($s,$t)=@_;return length($t)if!$s;return length($s)if!$t;my($u,$v)=(substr($s,1),substr($t,1));substr($s,0,1)eq substr($t,0,1)?l($u,$v):(sort{$a<=>$b}(l($u,$v),l($s,$v),l($u,$t)))[0]+1}print$L[l('Perl',pop)-1]

Test
$ perl levenshtein.pl Php
C++

J, 115 bytes
{&((}.&'YABC'&.>|.i.4),(g'SMITHb'),'Clojure';(g'ComeFrom2'),((g=:}:;])'StackStacks'),<'CoffeeScript')@<:@(#-'J'&e.)

This is using histocrat's calculation trick (using a 1-letter language), and generates the following list of languages:
┌─┬──┬───┬────┬─────┬──────┬───────┬────────┬─────────┬──────────┬───────────┬────────────┐
│C│BC│ABC│YABC│SMITH│SMITHb│Clojure│ComeFrom│ComeFrom2│StackStack│StackStacks│CoffeeScript│
└─┴──┴───┴────┴─────┴──────┴───────┴────────┴─────────┴──────────┴───────────┴────────────┘

e.g.:
   {&((}.&'YABC'&.>|.i.4),(g'SMITHb'),'Clojure';(g'ComeFrom2'),((g=:}:;])'StackStacks'),<'CoffeeScript')@<:@(#-'J'&e.) 'C++'
┌───┐
│ABC│
└───┘
   {&((}.&'YABC'&.>|.i.4),(g'SMITHb'),'Clojure';(g'ComeFrom2'),((g=:}:;])'StackStacks'),<'CoffeeScript')@<:@(#-'J'&e.) 'ActionScript'
┌────────────┐
│CoffeeScript│
└────────────┘
   f=:{&((}.&'YABC'&.>|.i.4),(g'SMITHb'),'Clojure';(g'ComeFrom2'),((g=:}:;])'StackStacks'),<'CoffeeScript')@<:@(#-'J'&e.)
   f 'Jython'
┌─────┐
│SMITH│
└─────┘
   f 'Python'
┌──────┐
│SMITHb│
└──────┘

05AB1E, 73 bytes
Not even a single-character language name and still the shortest answer here!
•äƵí•hR.L<Uõ'R„oT…taq.•₃γ•.•~ÙÚ•„€Ó…Ž„€Óïß…€ÓfŠ°„Â‚Â‚¦'Ïº¦“p¾»oãá“)Xè'Sìá

Try it online!
•äƵí•hR.L<U...Xè'Sìá  # full program
                   á  # get only letters of...
       .L             # Levenshtein distance between...
                      # implicit input...
       .L             # and...
•äƵí•                 # 14793296...
     h                # in hexadecimal...
      R               # reversed...
         <            # minus 1...
          U   Xè      # th element of...
           ...        # ["", "R", "oT", "taq", "ADOL", "onata", "now man", "now ball", "nowf lake", "tack stack", "hakespeare", "p yro decimal"]
                  ì   # prepended with...
                'S    # literal


text:
Invert a Minesweeper Board
Minesweeper is a popular computer game that you have probably wasted time playing where you try to reveal the cells that are mines in a rectangular grid based on hints of how many neighboring mines each non-mine cell has. And in case you haven't played it, do so here.
A nifty mathematical fact about a Minesweeper grid (a.k.a. board) is that:

A board and its complement have the same mine total number. (Proof)

That is to say that if you have a completely revealed Minesweeper grid, the sum all the numbers on that grid, i.e. the mine total, will equal the mine total of the complement of the grid, which is the grid where every mine has been replaced with a non-mine and every non-mine replaced with a mine.
For example, for the Minesweeper grid
**1..
34321
*2**1

the mine total is 1 + 3 + 4 + 3 + 2 + 1 + 2 + 1 = 17.
The grid's complement is
24***
*****
3*44*

which has mine total 2 + 4 + 3 + 4 + 4 = 17 again.
Write a program that takes in an arbitrary Minesweeper grid in text form where * represents a mine and 1 through 8 represent the number of mines adjacent to a non-mine cell. You can use . or 0 or   (space) to represent cells with no mine neighbors, your choice. You can assume that the input grid will be correctly marked, i.e. each non-mine cell will accurately denote the total number of mines immediately adjacent to it orthogonally or diagonally.
Your program needs to print the complement of the grid in the same format (using the same ., 0, or   as you expected in the input).
The shortest code in bytes wins.

Instead of a program you may write a function that takes the input grid as a string and prints or returns the complement grid.
A trailing newline in the input or output is fine, but there should be no other characters besides those that form the grid.
You can assume a 1×1 grid will be the smallest input.

Test Cases
All inputs and outputs could be swapped as the complement of the complement is the original grid. The grids can be rotated as well for further test cases.
Input:
111
1*1
111

Output:
***
*8*
***

Input:
.

Output:
*

Input:
*11*1.1**1...1***1.....1*****1..........

Output:
1**2***11*****1.1*******1...1***********

Input: (Cut The Knot example)
**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*

Output:
24***4**
***7**64
*8**7***
******8*
4**7****
*33**5*3

TI-BASIC cannot accept an empty line of input. Is using an end delimiter (for example ?) on the line after the final line of the board acceptable, or could I take the number of input lines through the command line?

@ThomasKwa An end delimiter sounds fine for TI-BASIC and other languages that have weird newline limitations.

Do any answer use the numbers in input?

Pyth, 39 38 bytes
j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z

Try it online: Demonstration
The main algorithm is really straightforward. I simply iterate over each cell, take the surrounding 3x3 box (or smaller when the cell is at the border) and print a star or the number of non-stars in that box.
Explanation:
j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z  implicit: .z = list of input strings
 .e                                 .z  map each index k, line b of .z to:
    .e                             b      map each index Y, char Z of b to:
         K\*                                assign "*" to K
                         +K.z               insert K at the front of .z
                        :    k+k3           slice from k to k+3
               :RtWYY+Y2                    take the slice from Y-1 or 0
                                            to Y+2 for each line
              s                             join, this gives the 3x3 rectangle
                                             (or smaller on the border)
             -                   K          remove all "*"s
            l                               take the length
        +K                                   "*" + ^
       -                          Z         remove Z from this string
      h                                     and take the first char
                                            (if cell=mine take the number,
                                             otherwise take the number)
  s                                       join the chars of one line
j                                       join by newlines

Really neat, +1

CJam, 58 57 bytes
0WX]2m*qN/{'*f+z}2*f{\~@m<fm<W<}:..+{W<{_'*#'*@'*-,?}/N}/

Input should not end with a linefeed. Output contains 0 for cells without nearby mines.
Try it online in the CJam interpreter.
Idea
We start by padding the input matrix with one row and one column of asterisks.
For input
*4*
**2

this results in
*4**
**2*
****

Now we generate all possible modifications that result of rotating the rows and columns 0, -1 or 1 units up/left:
*4** **** **2* **4* **** ***2 4*** **** *2**
**2* *4** **** ***2 **4* **** *2** 4*** ****
**** **2* *4** **** ***2 **4* **** *2** 4***

We discard the "padding locations" from each rotation, i.e.,
*4* *** **2 **4 *** *** 4** *** *2*
**2 *4* *** *** **4 *** *2* 4** ***

and form a single matrix by concatenating the corresponding characters of each rotation:
******4** 4*******2 **24*****
*******4* *4****2** 2***4****

The first character of each position is its original character.

If it is a non-asterisk, it has to be replaced with an asterisk.
If it is an asterisk, the number of non-asterisks in that string is the number of neighboring mines.

How it works
0WX]2m*   e# Push the array of all vectors of {0,-1,1}^2.
qN/       e# Read all input from STDIN and split at linefeeds.
{'*f+z}2* e# Append a '*' to each row and transpose rows with columns. Repeat.
f{        e# For each vector [A B], push the modified input Q; then:
  \~      e#   Swap Q with [A B] and dump A and B on the stack.
  @m<     e#   Rotate the rows of Q B units up.
  fm<     e#   Rotate each row of the result A units left.
  W<      e#   Discard the last row.
}         e# This pushes all nine rotations with Manhattan distance 1.
:..+      e# Concatenate the corresponding characters for each position.
{         e# For each row:
  W<      e#   Discard the character corresponding to the last column.
  {       e#   For each remaining string:
    _'*#  e#     Find the first index of '*' in a copy.
    '*    e#     Push '*'.
    @'*-, e#     Count the non-asterisks in the string.
    ?     e#     Select '*' if the index is non-zero, the count otherwise.
  }/      e#
  N       e#   Push a linefeed.
}/        e#

I'm scared - this is amazing.

You sir, have just broken the system. +1! May I ask where you found this theory?

@IonLee This one is all me. It's a pretty simple idea, really: Instead of checking the cells around a given cell, we move the entire grid around and observe what falls into the cell.

Bravo! I would of never of thought of that.

Ruby, 119
->s{w=1+s.index('
')
s.size.times{|c|t=0;9.times{|i|(s+?**w*2)[c+i/3*w-w+i%3-1]<?0||t+=1}
print [t,?*,'
'][s[c]<=>?*]}}

Ungolfed in test program:
f=->s{
  w=1+s.index("\n")                          #width of board
  s.size.times{|c|                           #iterate through input
    t=0;                                     #number of digits surrounding current cell
    9.times{|i|                              #iterate through 3x3 box (centre must be * if this ever gets printed.)
      (s+"*"*w*2)[c+i/3*w-w+i%3-1]<"0"||t+=1 #copy of s has plenty of * appended to avoid index errors
    }                                        #add 1 every time a number is found.
  print [t,"*","\n"][s[c]<=>"*"]             #if * print t. if after * in ACSII it's a number, print *. if before, it's \n, print \n
  }
}

f['**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*']

Octave, 76
m=@(s)char(conv2(b=(cell2mat(strsplit(s)'))~='*',ones(3),'same').*~b-6*b+48)

Explanation

Convert input string to matrix of strings using strsplit and
cell2mat.
Get the logical matrix containing 1 where there is no * in the
original matrix.
Take its convolution with a 3x3 matrix of 1's.
Mask it with the inverse logical matrix and put * in place of the
mask.
Note: Cells with no mine neighbors are represented as 0.

Execution
>> m(['**100' 10 '34321' 10 '*2**1'])   %// `10` is newline
ans =

24***
*****
3*44*

>> m(['24***' 10 '*****' 10 '3*44*'])
ans =

**100
34321
*2**1

Scala 3, 405 bytes
A port of @Level River St's Ruby answer in Scala.
405 bytes, it can be golfed more.

Golfed version. Attempt This Online!
def t(s:String):String={val l=s.split("\n");val h=l.length;val w=l.headOption.map(_.length).getOrElse(0)
(0to h-1).map{y=>(0to w-1).map{x=>l(y)(x)match{case'*'=>c(l,x,y).toString case _=>"*"}}.mkString}.mkString("\n")}
def c(l:Array[String],x:Int,y:Int):Int={val o=for{dy<- -1 to 1;dx<- -1 to 1;if y+dy>=0&&y+dy<l.length&&x+dx>=0&&x+dx<l(y+dy).length}yield(dx,dy)
o.count{case(dx,dy)=>l(y+dy)(x+dx)!='*'}}

Ungolfed version. Attempt This Online!
object Main {
  def main(args: Array[String]): Unit = {
    val board = "**212*32\n333*33**\n1*22*333\n222222*1\n*33*2232\n2**22*2*"
    println(transformBoard(board))
  }

  def transformBoard(s: String): String = {
    val lines = s.split("\n")
    val height = lines.length
    val width = lines.headOption.map(_.length).getOrElse(0)

    (0 until height).map { y =>
      (0 until width).map { x =>
        lines(y)(x) match {
          case '*' => countMines(lines, x, y).toString // Count surrounding numbers if it's a mine
          case _   => "*" // Turn every non-mine cell into a mine, mimicking the Ruby logic
        }
      }.mkString
    }.mkString("\n")
  }

  def countMines(lines: Array[String], x: Int, y: Int): Int = {
    val offsets = for {
      dy <- -1 to 1
      dx <- -1 to 1
      if y + dy >= 0 && y + dy < lines.length && x + dx >= 0 && x + dx < lines(y + dy).length
    } yield (dx, dy)

    offsets.count { case (dx, dy) =>
      val char = lines(y + dy)(x + dx)
      char != '*' // Count everything that is not a mine
    }
  }
}

Vyxal 3 j, 28 bytes
ᵛƛ•=[ð|•]:Þȯᵛᵛ•CZᵗZᵛᵛ₳•c¿•]“

Try it Online!
wish vectorize modifier deep vectorized
input is a 2d list of characters
ᵛƛ•=[ð|•]:Þȯᵛᵛ•CZᵗZᵛᵛ₳•c¿•]“
ᵛƛ      ]                     # map over each character
  •=[                         # is it a mine?
     ð|•]                     # if yes, replace with a space. if no, replace with a mine
         :                    # push two copies of the inverse mines
          Þȯ                  # grid neighbors
            ᵛᵛ•C              # counts of mines around each cell
                ZᵗZ           # zip each mine count with the inverted mine locations
                   ᵛᵛ₳    ]   # reduce each pair by
                      •c¿•    # if it contains a mine, set it to a mine, otherwise take the number
                           “  # join on nothing, j flag joins on newlines

Created with the help of Luminespire.

Uiua, 53 bytes
⍜☇≡(⟨@*◌|⊢°⋕/+¬⟩°⊂=@*)1⍉≡(↘⊟.¯1↻)☇1⊞⊟.0_1_¯1¤⬚@*↙+1△.

Try it in the pad!
Port of Dennis's CJam answer.