Haskell subset → C - 18926 characters

This compiles a small subset of Haskell to C.  Features it supports:

Pattern matching and guards
Data declarations
Select infix operators
Lazy evaluation

The biggest missing features are nested variables (meaning no lambda/let/where/case), type checking, and type classes.  Resulting programs leak memory, and self-compilation takes about 200 megabytes on my system (the Boehm garbage collector helps a lot, but only if the compiler optimizes tail recursion well).

To bootstrap, uncomment the first three lines (not counted in the score) and compile with GHC.  The compiler takes Haskell-subset code on stdin and produces C code on stdout.

It's long not because the language is complex, but because I'm lazy.  However, it's currently the shortest solution  Not anymore.  Guess I won't be bored this weekend.

-- import Prelude hiding (fmap, lookup, snd, zip);import Data.Char
-- import Data.List hiding (lookup, zip);data P a b = P a b;data B = B
-- add=(+);sub=(-);showInt=show;append[]ys=ys;append(x:xs)ys=x:append xs ys
data Program = Program [[Constructor]] [Function]
data Toplevel = TD [Constructor] | TE Equation | TO
data Constructor = Constructor String Int
data Function = Function String Int [Equation]
data Equation = Equation String [Pattern] (Maybe Expression) Expression
data Pattern = PVar String | PCon String [Pattern]
data Expression = Var String | Con String | Int String | Char String | String String | Ap Expression Expression
data Environment = Environment [P String Int] [P String VarInfo]
data VarInfo = VBox String | VArg Int | VItem VarInfo Int
main = interact (compile . parse)
constructorName (Constructor name _) = name
functionName (Function name _ _) = name
equationName (Equation name _ _ _) = name
sortToplevels [] = (P [] [])
sortToplevels (TD x : xs) = applyFst ((:) x) (sortToplevels xs)
sortToplevels (TE x : xs) = applySnd ((:) x) (sortToplevels xs)
sortToplevels (TO : xs)   = sortToplevels xs
pcons x xs = PCon "Cons" [x, xs];pnil = PCon "Nil" []
ebinary op a b = Ap (Ap (Var op) a) b;ebinaryE op a b = Ap (Ap op a) b
econs x xs = Ap (Ap (Con "Cons") x) xs
enil = Con "Nil"
listEq eq [] [] = True
listEq eq (x:xs) (y:ys) | eq x y = listEq eq xs ys
listEq _ _ _ = False
snd (P a b) = b
zip = zipWith P
lookup q (P k v : _)  | listEq (==) q k = Just v
lookup q (_     : xs)                   = lookup q xs
lookup q _                              = Nothing
compose2 f g x y = f (g x y)
applyFst f (P x y) = P (f x) y
applySnd f (P x y) = P x (f y)
fMaybe f Nothing  = Nothing
fMaybe f (Just x) = Just (f x)
cond f t False = f
cond f t True = t
condList f t [] = f
condList f t xs = t xs
countFrom n = n : countFrom (add n 1)
range l h | l > h = []
range l h         = l : range (add l 1) h
parse = makeProgram . sortToplevels . concatMap parse_p . ((:) prelude) . preprocess
parse_p (P lineno line) = maybe (parse_err lineno line) snd (parseLine line)
parse_err lineno line = error (concat ["Parse error on line ", showInt lineno, ": `", line, "`"])
preprocess = filter (not . isCommentOrEmpty . snd) . zip (countFrom 1) . map (dropWhile isBlank) . lines
isCommentOrEmpty = parserSucceeds (pro (ignore (pro (parseS "--") (parseS "import "))) parseEof)
liftA2 f a b = ap (fmap f a) b
parserSucceeds p s = maybe False (const True) (p s)
fmap f p = fMaybe (applySnd f) . p
pure x s = Just (P s x)
ap1 b (P s x) = maybe Nothing (ap2 x) (b s)
ap2 x (P s y) = Just (P s (x y))
empty = (const Nothing)
pro a b s = maybe (b s) Just (a s)
ap a b = maybe Nothing (ap1 b) . a
prc = liftA2 (:)
pra = liftA2 append
prl = liftA2 const
prr = liftA2 (const id)
many p = pro (some p) (pure [])
some p = prc p (many p)
optional p = pro (fmap Just p) (pure Nothing)
choice = foldr pro (const Nothing)
parseEof = parseEof_1
parseEof_1 [] = Just (P "" B)
parseEof_1 _  = Nothing
parsePred pred = parsePred_1 pred
parsePred_1 pred (x:xs) | pred x = Just (P xs x)
parsePred_1 _    _               = Nothing
manyParsePred = justFlipSplit
justFlipSplit pred xs = Just (P (dropWhile pred xs) (takeWhile pred xs))
someParsePred pred = prc (parsePred pred) (manyParsePred pred)
parseC = parsePred . (==)
parseS = foldr (prc . parseC) (pure [])
wrapC = wrapSpace . parseC
wrapS = wrapSpace . parseS
skipPred pred = prr (parsePred pred) (pure B)
manySkipPred pred = prr (manyParsePred pred) (pure B)
preSep p sep = many (prr sep p)
sepBy1 p sep = prc p (many (prr sep p))
sepByChar p c = pro (sepByChar1 p c) (pure [])
sepByChar1 p c = sepBy1 p (wrapSpace (parseC c))
wrapSpace p = prl (prr skipSpace p) skipSpace
ignore = fmap (const B)
isBlank c | c == ' ' || c == '\t' = True
isBlank _                         = False
isDigit1 c = c >= '1' && c <= '9'
parseBetween l r p = prl (prr (parseC l) (wrapSpace p)) (parseC r)
skipSpace = manySkipPred isBlank
chainl1 f sep p = fmap (foldl1 f) (sepBy1 p sep)
chainr1 f sep p = fmap (foldr1 f) (sepBy1 p sep)
chainl f z sep p = pro (fmap (foldl f z) (sepBy1 p sep)) (pure z)
chainr f z sep p = pro (fmap (foldr f z) (sepBy1 p sep)) (pure z)
parseNonassoc ops term = liftA2 (flip ($)) term (pro (liftA2 flip (choice ops) term) (pure id))
parseVar = prc (parsePred (orUnderscore isLower)) (many (parsePred (orUnderscore isAlphaNum)))
orUnderscore p c | p c || c == '_' = True
orUnderscore _ _ = False
parseCon = prc (parsePred isUpper) (many (parsePred (orUnderscore isAlphaNum)))
parseInt = pro (parseS "0") (prc (parsePred isDigit1) (many (parsePred isDigit)))
parseEscape q (c:x:xs) | c == '\\' = Just (P xs (c:x:[]))
parseEscape q [c]      | c == '\\' = Just (P [] [c])
parseEscape q (c:xs)   | c /= q    = Just (P xs [c])
parseEscape q _                    = Nothing
parseStringLiteral q = pra (parseS [q]) (pra (fmap concat (many (parseEscape q))) (parseS [q]))
parsePattern = chainr1 pcons (wrapC ':') (pro (liftA2 PCon parseCon (preSep parsePatternPrimary skipSpace)) parsePatternPrimary)
parsePatternPrimary = choice [fmap PVar parseVar, fmap (flip PCon []) parseCon, parseBetween '(' ')' parsePattern, parseBetween '[' ']' (fmap (foldr pcons pnil) (sepByChar parsePattern ','))]
relops f = relops_1 (ops_c f)
otherops f = f ":" (Con "Cons") : otherops_1 (ops_c f)
ops_c f x y = f x (Var y)
relops_1 f   = [f "<=" "_le", f "<" "_lt", f "==" "_eq", f ">=" "_ge", f ">" "_gt", f "/=" "_ne"]
otherops_1 f = [f "$" "_apply", f "||" "_or", f "&&" "_and", f "." "_compose"]
parseRelops = parseNonassoc (relops parseRelops_f)
parseRelops_f op func = prr (wrapS op) (pure (ebinaryE func))
parseExpression = chainr1 (ebinary "_apply") (wrapC '$') $ chainr1 (ebinary "_or") (wrapS "||") $ chainr1 (ebinary "_and") (wrapS "&&") $ parseRelops $ chainr1 econs (wrapC ':') $ chainr1 (ebinary "_compose") (wrapC '.') $ chainl1 Ap skipSpace $ choice [fmap Var parseVar, fmap Con parseCon, fmap Int parseInt, fmap Char (parseStringLiteral '\''), fmap String (parseStringLiteral '"'), parseBetween '(' ')' (pro parseSection parseExpression), parseBetween '[' ']' (chainr econs enil (wrapC ',') parseExpression)]
parseSection = choice (append (relops parseSection_f) (otherops parseSection_f))
parseSection_f op func = prr (wrapS op) (pure func)
parseEquation = ap (ap (ap (fmap Equation parseVar) (many (prr skipSpace parsePatternPrimary))) (optional (prr (wrapC '|') parseExpression))) (prr (wrapC '=') parseExpression)
skipType = ignore (sepBy1 (sepBy1 skipTypePrimary skipSpace) (wrapS "->"))
skipTypePrimary = choice [ignore parseVar, ignore parseCon, parseBetween '(' ')' skipType, parseBetween '[' ']' skipType]
parseDataDecl = prr (parseS "data") (prr skipSpace (prr parseCon (prr (preSep parseVar skipSpace) (prr (wrapC '=') (sepByChar1 (liftA2 Constructor parseCon (fmap length (preSep skipTypePrimary skipSpace))) '|')))))
skipTypeSignature = prr parseVar (prr (wrapS "::") skipType)
skipTypeAlias = prr (parseS "type") (prr skipSpace (prr parseCon (prr (preSep parseVar skipSpace) (prr (wrapC '=') skipType))))
parseToplevel = choice [fmap (const TO) (pro skipTypeSignature skipTypeAlias), fmap TD parseDataDecl, fmap TE parseEquation]
parseLine = prl (prl (sepByChar1 parseToplevel ';') skipSpace) parseEof
patternCount (Equation _ ps _ _) = length ps
makeProgram (P ds es) = Program ds (makeFunctions es)
makeFunctions = map makeFunctions_f . groupBy makeFunctions_g
makeFunctions_f []     = error "Internal error: No equations in binding group"
makeFunctions_f (x:xs) = cond (error (concat ["Equations for ", equationName x, " have different numbers of arguments"])) (Function (equationName x) (patternCount x) (x:xs)) (all (((==) (patternCount x)) . patternCount) xs)
makeFunctions_g (Equation name_a _ _ _) (Equation name_b _ _ _) = listEq (==) name_a name_b
lookupCon name (Environment c _) = lookup name c
lookupVar name (Environment _ v) = lookup name v
walkPatterns f = walkPatterns_items f VArg
walkPatterns_items f base = concat . zipWith (walkPatterns_f2 f) (map base (countFrom 0))
walkPatterns_f2 f v (PCon name ps) = append (f v (PCon name ps)) (walkPatterns_items f (VItem v) ps)
walkPatterns_f2 f v p              = f v p
compile (Program decls funcs) = concat [header, declareConstructors decls, declareFunctions funcs, boxConstructors decls, boxFunctions funcs, compileConstructors decls, compileFunctions (globalEnv decls funcs) funcs]
globalEnv decls funcs = Environment (append (globalEnv_constructorTags decls) (globalEnv_builtinConstructors)) (append (map (globalEnv_f . functionName) funcs) globalEnv_builtinFunctions)
globalEnv_f name = (P name (VBox name))
globalEnv_constructorTags = concatMap (flip zip (countFrom 0) . map constructorName)
globalEnv_builtinConstructors = [P "Nil" 0, P "Cons" 1, P "P" 0]
globalEnv_builtinFunctions = map globalEnv_f ["add", "sub", "_lt", "_le", "_eq", "_ge", "_gt", "_ne", "_and", "_or", "divMod", "negate", "not", "error"]
localEnv ps (Environment t v) = Environment t (append (walkPatterns localEnv_f ps) v)
localEnv_f v (PVar name) = [P name v]
localEnv_f _ (PCon _ _)  = []
declareFunctions_f [] = ""
declareFunctions_f xs = concat ["static Function ", intercalate ", " xs, ";\n"]
declareConstructors = declareFunctions_f . map ((append "f_") . constructorName) . concat
declareFunctions = declareFunctions_f . map ((append "f_") . functionName)
boxConstructors = concatMap boxConstructors_f . concat
boxConstructors_f (Constructor name n) = boxThing name n
boxFunctions = concatMap boxFunctions_f
boxFunctions_f (Function name n _) = boxThing name n
boxThing name n | n == 0 = concat ["static Box b_", name, " = {0, f_", name, ", NULL};\n"]
boxThing name n = concat ["static Partial p_", name, " = {", showInt n, ", 0, f_", name, "};\n", "static Box b_", name, " = {1, NULL, &p_", name, "};\n"]
compileConstructors = concatMap (concat . zipWith compileConstructors_f (countFrom 0))
compileConstructors_f tag (Constructor name n) = concat ["static void *f_", name, "(Box **args)\n", "{\n", allocate n, "\tv->tag = ", showInt tag, ";\n", concatMap initialize (range 0 (sub n 1)), "\treturn v;\n", "}\n"]
allocate n | n == 0 = "\tValue *v = malloc(sizeof(Value));\n\t(void) args;\n"
allocate n = concat ["\tValue *v = malloc(sizeof(Value) + ", showInt n, " * sizeof(Box*));\n"]
initialize i = concat ["\tv->items[", showInt i, "] = args[", showInt i, "];\n"]
compileFunctions env = concatMap (compileFunction env)
compileFunction env (Function name argc equations) =  concat ["static void *f_", name, "(Box **args)\n", "{\n", concatMap (compileEquation env) equations, "\tNO_MATCH(", name, ");\n", "}\n"]
compileEquation genv (Equation _ patterns guard expr) = compileEquation_a (localEnv patterns genv) patterns guard expr
compileEquation_a env patterns guard expr = compileEquation_b (concat ["\treturn ", compileExpressionStrict env expr, ";\n"]) (append (compilePatterns env patterns) (compileGuard env guard))
compileEquation_b returnExpr preds = condList returnExpr (compileEquation_f returnExpr) preds
compileEquation_f returnExpr xs = concat ["\tif (", intercalate " && " xs, ")\n\t", returnExpr]
compilePatterns env = walkPatterns (compilePatterns_f env)
compilePatterns_f _ _ (PVar name) = []
compilePatterns_f env v (PCon name ps) = compilePatterns_h v name (lookupCon name env)
compilePatterns_h v name (Just n) = [concat ["match(", compileVarInfo v, ",", showInt n, ")"]]
compilePatterns_h v name Nothing  = error (append "Not in scope: data constructor " name)
compileGuard env Nothing     = []
compileGuard env (Just expr) = [concat ["isTrue(", compileExpressionStrict env expr, ")"]]
compileExpressionStrict env (Var name) = concat ["force(", compileVar (lookupVar name env) name, ")"]
compileExpressionStrict _   (Con name) = concat ["force(&b_", name, ")"]
compileExpressionStrict _   (Int s)    = concat ["mkInt(", s, ")"]
compileExpressionStrict _   (Char s)   = concat ["mkInt(", s, ")"]
compileExpressionStrict _   (String s) = concat ["mkString(", s, ")"]
compileExpressionStrict env (Ap f x)   = concat ["apply(", compileExpressionStrict env f, ",", compileExpressionLazy env x, ")"]
compileExpressionLazy env (Var name) = compileVar (lookupVar name env) name
compileExpressionLazy _   (Con name) = concat ["&b_", name, ""]
compileExpressionLazy _   (Int s)    = concat ["box(mkInt(", s, "))"]
compileExpressionLazy _   (Char s)   = concat ["box(mkInt(", s, "))"]
compileExpressionLazy _   (String s) = concat ["box(mkString(", s, "))"]
compileExpressionLazy env (Ap f x)   = concat ["deferApply(", compileExpressionLazy env f, ",", compileExpressionLazy env x, ")"]
compileVar (Just v) _    = compileVarInfo v
compileVar Nothing  name = error (append "Not in scope: " name)
compileVarInfo (VBox name) = append "&b_" name
compileVarInfo (VArg n)    = concat ["args[", showInt n, "]"]
compileVarInfo (VItem v n) = concat ["item(", compileVarInfo v, ",", showInt n, ")"]
header="#include <assert.h>\n#include <stdarg.h>\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\ntypedef struct Box Box;\ntypedef struct Value Value;\ntypedef struct Partial Partial;\ntypedef void *Function(Box**);\nstruct Box{int state;Function *func;void*vc;Box*fx[];};\nstruct Value{int tag;Box *items[];};\nstruct Partial{int remaining;int applied;Function *func;Box *args[];};\n#define copy(...)memdup(&(__VA_ARGS__), sizeof(__VA_ARGS__))\n#define countof(...)(sizeof(__VA_ARGS__) / sizeof(*(__VA_ARGS__)))\n#define match(box, expectedTag)(((Value*)force(box))->tag == (expectedTag))\n#define item(box, n)(((Value*)(box)->vc)->items[n])\n#define isTrue(value)(!!*(int*)(value))\n#define NO_MATCH(func)fatal(\"Non-exhaustive patterns in function \" #func)\nstatic void fatal(const char *str){fprintf(stderr,\"*** Exception: %s\\n\", str);exit(EXIT_FAILURE);}\nstatic void *memdup(void *ptr, size_t size){void*ret=malloc(size);memcpy(ret,ptr,size);return ret;}\nstatic void *force(Box *box){switch(box->state){\ncase 0:box->state=2;box->vc=box->func(box->vc);box->state=1;\ncase 1:return box->vc;\ndefault:fatal(\"infinite loop\");}}\nstatic void *apply(Partial*f,Box*x){Partial*f2=malloc(sizeof(Partial)+(f->applied+1)*sizeof(Box*));\nmemcpy(f2->args,f->args,f->applied*sizeof(Box*));f2->args[f->applied]=x;\nif(f->remaining>1){f2->remaining=f->remaining-1;f2->applied=f->applied+1;f2->func=f->func;return f2;\n}else return f->func(f2->args);}\nstatic void*deferApply_cb(Box**a){return apply(force(a[0]),a[1]);}\nstatic Box*deferApply(Box*f,Box*x){\nBox*ret=malloc(sizeof(Box)+2*sizeof(Box*));\nret->state=0;\nret->func=deferApply_cb;\nret->vc=ret->fx;\nret->fx[0]=f;\nret->fx[1]=x;\nreturn ret;}\n\nstatic Box*defer(Function*func,void*ctx){\nBox*ret=malloc(sizeof(Box));\nret->state=0;\nret->func=func;\nret->vc=ctx;\nreturn ret;}\n\nstatic Box *box(void *value)\n{\n\tBox *ret = malloc(sizeof(Box));\n\tret->state = 1;\n\tret->func = NULL;\n\tret->vc = value;\n\treturn ret;\n}\n\nstatic int *mkInt(int n)\n{\n\tint *ret = malloc(sizeof(*ret));\n\t*ret = n;\n\treturn ret;\n}\n\nstatic Function f_Nil, f_Cons, f_P;\nstatic Box b_Nil, b_Cons, b_P, b_main;\n\n#define FUNCTION(name, argc) \\\n\tstatic Function f_##name; \\\n\tstatic Partial p_##name = {argc, 0, f_##name}; \\\n\tstatic Box b_##name = {1, NULL, &p_##name}; \\\n\tstatic void *f_##name(Box **args)\n\n#define intop(name, expr) \\\n\tFUNCTION(name, 2) \\\n\t{ \\\n\t\tint a = *(int*)force(args[0]); \\\n\t\tint b = *(int*)force(args[1]); \\\n\t\treturn mkInt(expr); \\\n\t}\n\n#define intop1(name, expr) \\\n\tFUNCTION(name, 1) \\\n\t{ \\\n\t\tint a = *(int*)force(args[0]); \\\n\t\treturn mkInt(expr); \\\n\t}\n\nintop(add,  a + b)\nintop(sub,  a - b)\n\nintop(_lt,  a <  b)\nintop(_le,  a <= b)\nintop(_eq,  a == b)\nintop(_ge,  a >= b)\nintop(_gt,  a >  b)\nintop(_ne,  a != b)\nintop(_and, a && b)\nintop(_or,  a || b)\n\nintop1(negate, -a)\nintop1(not,    !a)\n\nFUNCTION(divMod, 2)\n{\n\tint n = *(int*)force(args[0]);\n\tint d = *(int*)force(args[1]);\n\tint div = n / d;\n\tint mod = n % d;\n\t\n\tif ((mod < 0 && d > 0) || (mod > 0 && d < 0)) {\n\t\tdiv--;\n\t\tmod += d;\n\t}\n\t\n\tBox *pair[2] = {box(mkInt(div)), box(mkInt(mod))};\n\treturn f_P(pair);\n}\n\nstatic void *mkString(const char *str)\n{\n\tif (*str != '\\0') {\n\t\tBox *cons[2] =\n\t\t\t{box(mkInt(*str)), defer((Function*) mkString, (void*)(str + 1))};\n\t\treturn f_Cons(cons);\n\t} else {\n\t\treturn force(&b_Nil);\n\t}\n}\n\nstatic void putStr(Value *v, FILE *f)\n{\n\tif (v->tag == 1) {\n\t\tint c = *(int*)force(v->items[0]);\n\t\tputc(c, f);\n\t\tputStr(force(v->items[1]), f);\n\t}\n}\n\nFUNCTION(error, 1)\n{\n\tfflush(stdout);\n\tfputs(\"*** Exception: \", stderr);\n\tputStr(force(args[0]), stderr);\n\tputc('\\n', stderr);\n\texit(EXIT_FAILURE);\n}\n\nstruct mkStringFromFile\n{\n\tFILE *f;\n\tconst char *name;\n};\n\nstatic void *mkStringFromFile(struct mkStringFromFile *ctx)\n{\n\tint c = fgetc(ctx->f);\n\t\n\tif (c == EOF) {\n\t\tif (ferror(ctx->f))\n\t\t\tperror(ctx->name);\n\t\treturn force(&b_Nil);\n\t}\n\t\n\tBox *cons[2] = {box(mkInt(c)), defer((Function*) mkStringFromFile, ctx)};\n\treturn f_Cons(cons);\n}\n\nint main(void)\n{\n\tstruct mkStringFromFile c_in = {stdin, \"<stdin>\"};\n\tBox *b_in = defer((Function*) mkStringFromFile, copy(c_in));\n\tputStr(apply(force(&b_main), b_in), stdout);\n\treturn 0;\n}\n"
prelude = P 0 "_apply f x=f x;_compose f g x=f(g x);data List a=Nil|Cons a(List a);data P a b=P a b;data B=B;data Maybe a=Nothing|Just a;data Bool=False|True;id x=x;const x _=x;flip f x y=f y x;foldl f z[]=z;foldl f z(x:xs)=foldl f(f z x)xs;foldl1 f(x:xs)=foldl f x xs;foldl1 _[]=error\"foldl1: empty list\";foldr f z[]=z;foldr f z(x:xs)=f x(foldr f z xs);foldr1 f[x]=x;foldr1 f(x:xs)=f x(foldr1 f xs);foldr1 _[]=error\"foldr1: empty list\";map f[]=[];map f(x:xs)=f x:map f xs;filter p[]=[];filter p(x:xs)|p x=x:filter p xs;filter p(x:xs)=filter p xs;zipWith f(x:xs)(y:ys)=f x y:zipWith f xs ys;zipWith f _ _=[];append[]ys=ys;append(x:xs)ys=x:append xs ys;concat=foldr append[];concatMap f=concat.map f;length[]=0;length(_:l)=add 1(length l);take n _|n<=0=[];take _[]=[];take n(x:xs)=x:take(sub n 1)xs;takeWhile p[]=[];takeWhile p(x:xs)|p x=x:takeWhile p xs;takeWhile _ _=[];dropWhile p[]=[];dropWhile p(x:xs)|p x=dropWhile p xs;dropWhile p xs=xs;span p[]=P[][];span p(x:xs)|p x=span_1 x(span p xs);span p xs=P[]xs;span_1 x(P ys zs)=P(x:ys)zs;break p=span(not.p);reverse=foldl(flip(:))[];groupBy _[]=[];groupBy eq(x:xs)=groupBy_1 x eq(span(eq x)xs);groupBy_1 x eq(P ys zs)=(x:ys):groupBy eq zs;maybe n f Nothing=n;maybe n f(Just x)=f x;all p=foldr(&&)True.map p;intersperse _[]=[];intersperse _[x]=[x];intersperse sep(x:xs)=x:sep:intersperse sep xs;intercalate xs xss=concat(intersperse xs xss);isDigit c=c>='0'&&c<='9';isAlphaNum c=c>='0'&&c<='9'||c>='A'&&c<='Z'||c>='a'&&c<='z';isUpper c=c>='A'&&c<='Z';isLower c=c>='a'&&c<='z';showInt n|n<0='-':showInt(negate n);showInt n|n==0=\"0\";showInt n|n>0=reverse(map(add 48)(showInt_1 n));showInt_1 n|n==0=[];showInt_1 n=showInt_2(divMod n 10);showInt_2(P div mod)=mod:showInt_1 div;lines []=[];lines s=lines_1(break((==)'\\n')s);lines_1(P l[])=[l];lines_1(P l(_:s))=l:lines s;interact=id"


Use a text editor

The editor that comes with Pure Data is really useful for making programs that work or helping you to understand existing programs.  However if you want to golf, the files it creates are full of extra stuff that can be removed with an text editor (e.g. vim).

This post will serve as a list of a bunch of small byte saving tricks accessible only through or more easily though a traditional editor.

Use defaults on canvas:  Your file needs a canvas line.  #N canvas; is enough to get things to run without error. The missing arguments default to zero.
Newlines are optional:  The graphical editor puts newlines between statements.  Presumably to make these files somewhat readable.  However these are not strictly required and can be removed with an editor.
Rearrange your objects for better object indices:  Since connections identify objects by their order in the source, placing objects with a lot of connections earlier in the file can shorten your source.  Make sure that you update all the references once you reorder.
Put everything in the top left:  Since object location is purely a graphical aid, you can place them wherever. Single digit locations are the shortest so changing the location to 0 0 or something similar will save you.  This turns your code into an unreadable blob so it is probably best to do this once everything already works.


Python, 76 69 68 63 62 60 57 bytes

f=lambda n,k=0:n>>k&(n&n>>k>n>>k+1)and(n&n+1>0)-~f(n,k+1)

Try it online!

How it works

This is a recursive solution that takes an input n and keeps incrementing k – starting at 0– while both LSBk(n) (bit at index k from the right) and MSBk(n) (bit at index k from the left) are set. Once finished, it returns k if all of n's bit are set and 2k if not.

Let's start by rewriting the lambda f as a named function F, with an auxiliary variable t.

def F(n, k = 0):
    t = n >> k
    return t & (n & t > t >> 1) and (n & (n + 1) > 0) + 1 + F(n, k + 1)

In each invocation of F, we first bit-shift n a total of k units to the right and store the result in t. This way, LSB0(t) = LSBk(n), so t is odd if and only if LSBk(n) is set.

Determining whether MSBk(n) is set is slightly trickier; this is what n & t > t >> 1 achieves. To illustrate how it works, let's consider an integer n = 1αβγδεζη2 of bit-length 8 and analyze the function call F(n, 3), i.e., k = 3.

We're trying to determine whether MSB3(n) = γ is set by examining the truth value of the comparison (n & t > t >> 1) = (1αβγδεζη2 & 1αβγδ2 > 1αβγ2). Let's examine the involved integers.

MSB-index  012k4567

n          1αβγδεζη
t             1αβγδ

t >> 1         1αβγ

We claim that γ = 1 if and only if n & t > t >> 1.

If γ = 1, then n & t has bit-length 5 while t >> 1 has bit-length 4, so n & t > t >> 1.

This proves that γ = 1 implies n & t > t >> 1.
If n & t > t >> 1, there are two options: either γ = 1 or γ = 0. In the first case, there's nothing left to prove.

In the second case, we have that αβγδ2 ≥ n & t > t >> 1 = 1αβγ2.

Since αβγδ2 > 1αβγ2, we must have MSB0(αβγδ2) ≥ MSB0(1αβγ2), meaning that α = 1.

This way, 1βγδ2 > 11βγ2, so we must have MSB1(1βγδ2) ≥ MSB1(11βγ2), meaning that β = 1.

In turn, this implies that 11γδ2 > 111γ2. Remembering that γ = 0 in the second case, we get the inequality 110δ2 > 11102, which is false since MSB2(110δ2) = 0 < 1 = MSB2(11102).

Thus, only the first case is possible and n & t > t >> 1 implies γ = 1.

Summing up, if both LSBk(n) and MSBk(n) are set, t will be odd and n & t > t >> 1 will be True, so t & (n & t > t >> 1) will yield 1. However, if LSBk(n) or MSBk(n) is unset (or if both are), t will be even or n & t > t >> 1 will be False, so t & (n & t > t >> 1) will yield 0.

Calling F with a single argument initializes k = 0. While the condition we've discussed earlier holds, the code after and is executed, which (among other things) recursively calls F with incremented k.

Once LSBk(n) or MSBk(n) is unset, the condition fails and F(n, k) returns 0. Each of the preceding k function calls adds (n & (n + 1) > 0) + 1 to F(n, k) = 0, so F(n) returns ((n & (n + 1) > 0) + 1)k.

Now, if all bits of n are equal (i.e., if n is either 0 or all of its bits are set), n + 1 will not have any bits in common with n, so n & (n + 1) = 0 and F(n) returns k. However, if n has both set and unset bits, n & (n + 1) > 0 and F(n) returns 2k.


R, 84 bytes

function(s,w,S=el(strsplit(s," ")),t=tolower)cat(S[!duplicated(x<-t(S))|!x%in%t(w)])

Try it online!

Less than 100 bytes on a string challenge that's not also kolmogorov-complexity?

Explanation:

After we break up the string into words, we need to exclude those that are

duplicates and
in w

or alternatively, turning that on its head, keeping those that are

the first occurrence of a word OR
not in w.

duplicated neatly returns logical indices of those that are not the first occurrence, so !duplicated() returns indices of those which are first occurrences, and x%in%w returns logical indices for x of those which are in w. Neat.


Approximated (unsorted) square from a set of values

Mathematica, 91 bytes

n=RandomInteger@199+1
TableForm@Partition[Range@9~RandomChoice~n,Divisors@n~Nearest~Sqrt@n]

I hope I got this right:

Generate a random length between 1 and 200 (inclusive).
Generate a list of that length with numbers from 1 to 9 (inclusive).
Find one of the two divisors closest to the square root, with Divisors@n~Nearest~Sqrt@n.
Break the list into rows of that length.
Display the grid with TableForm.

Example run:


Python 2, 77 76 bytes

lambda s:'VFULJSGEalmeoylspaballaporrftvc'[hash(s)%3695%8::8]+'reon'[s<'V':]

Try it online!

In Python 2, the hash function consistently (across runs and also on different platforms) converts any immutable value into a 64-bit integer. By taking that integer first mod 3695, then mod 8, we get an integer 0<=i<8 (3695 was found by brute force checking all possible values upto 10000).

A common trick is used to encode a list of same-size strings into a single string and then using slicing via [i::8]to extract the strings without using .split or similar strategy. Only two options are not of length 4: Esp and Vapor. The former is handled by making it the last of the 8 strings encoded; and Vapor is handled using the final slicing 'reon'[s<'V':].


Look mom! I made my own (Base 10) numeral system!

05AB1E, 10 9 bytes
žh‡.Eò¹Åв

(Now) outputs as a list of characters.
Try it online or verify all test cases.
Explanation:

  ‡        # Transliterate the second (implicit) input, replacing every character of
           # the first (implicit) input with:
žh         # The builtin "0123456789"
   .E      # Then evaluate it as Elixir code
     ò     # Round it to the nearest integer
      ¹Åв  # And change it back by using a custom base-conversion with the first input as
           # base (which results in a character list)
           # (after which that result is output implicitly)

The new version of 05AB1E is build is build in Elixir. The .E function will call call_unary(fn x -> {result, _} = Code.eval_string(to_string(x)); result end, a), where the Code.eval_string is an Elixir builtin.
Note that the legacy version of 05AB1E won't work for this, because it is build in Python. The numbers with leading 0s won't be evaluated:
See all test cases in the legacy version (which uses the 10-byte version because the Åв builtin is new).


Java- 1254 bytes- a very poor solution
import java.util.Arrays;
public class z{
static boolean u=1>0,v=0<1;
public static void main(String[] a){
int y=a.length,x=a[0].length();Boolean[][] l=new Boolean[x][y];for(int i=0;i<a.length;i++){l[i]=m(a[i]);}
Boolean[] n=new Boolean[x*y];for(int i=0;i<n.length;i++){n[i]=v;}
while(n.length==x*y){Boolean[][] o=new Boolean[x][y];for(int i=0; i<n.length;i++){o[i%x][i/x]=n[i];}
n=p(n);o=q(o,x,y);int r=0;for(int i=0;i<x*y;i++){if(o[i%x][i/x]&&l[i%x][i/x])r++;}
if(r==x*y){System.out.println("evolved");return;}}System.out.println("created");}
public static Boolean[][] q(Boolean[][] o,int bx,int by){Boolean[][] s=new Boolean[bx][by];for(int x=0; x<bx; x++){for(int y=0;y<by;y++){
int t=0;for(int tx=-1;tx<2;tx++){for(int ty=-1;ty<2;ty++){if(ty+y<0||ty+y>by-1||tx+x<0||tx+x>bx-1)continue;if(o[tx+x][ty+y]){t++;}}}
if(t>1&&t<4){s[x][y]=u;}else{s[x][y]=v;}}}return s;}
public static Boolean[] p(Boolean[] b){boolean w=u;Boolean[] x=new Boolean[b.length];for(int i=0;i<b.length;i++){if(w&&b[i]){x[i]=u;w=u;}else if(b[i]||w){x[i]=u;w=v;}else{x[i]=v;w=v;}
}if(w){x=Arrays.copyOf(x,x.length+1);x[x.length]=u;}return x;}
public static Boolean[] m(String s){Boolean[] x=new Boolean[s.length()];for(int i=0;i<s.length();i++){x[i]=s.charAt(i)=='1';}return x;}}

It takes input via command line.
What it does
No fancy tricks here, simply a brute force solution. It goes through every possible beginning board of size X,Y and iterates it once thru the Game of Life algorithm and checks it against the input board. This takes a VERY long time, as each board of size x by y has 2^(x*y) possible combinations. It took almost 10 minutes to run a 4x5 board. Stupidly silly for something that is simpler than it is.
If it is possible that it was an evolved board, it prints "evolved.", and if it couldn't have been evolved, it prints "created.".


SOGL V0.12, 24 bytes
u%⅝⁾⁷‰┘Η:⅛6s⁹№K⌠RΝīL°‘§╬

Try it Here!
A simple compression solution:
....‘    push "@-.¶===(¶----(¶=====(¶_____(¶\/\/\¶/\/\¶\/\¶/\¶\"
     §   pad with spaces and reverse horizontally
      ╬  palindromize with 0 overlap and mirroring the characters

No compression version - way longer as SOGLs compression works nice for this


C++, 168 + 135 = 303 bytes

EDIT: saved one byte by requiring uppercase input

I like doing these in C++ because I get to do all sorts of fun nastiness I would never ever do in C++ code.

Encoder (168):

Takes a string of uppercase letters and spaces as an argument.

#include<cstdio>
int main(int h,char**c){c[0][3]=0;for(c++;h=**c;c[0]++){h=h&32?26:h-65;for(int d=2,e;d+1;d--){h=(h-(e=h%3))/3;c[-1][d]=e&2?88:e*47+32;}printf(c[-1]);}}

Readable:

#include<cstdio>
int main(int h,char**c)
{
    c[0][3]=0;
    for(c++;h=**c;c[0]++)
    {
        h=h&32?26:h-65;
        for(int d=2,e;d+1;d--)
        {
            h=(h-(e=h%3))/3;
            c[-1][d]=e&2?88:e*47+32;
        }
        printf(c[-1]);
    }
}

Decoder (135):

Takes a string of X, O, and space as an argument.

#include<cstdio>
int b=9,v;int main(int h,char**c){for(c++;h=**c;c[0]++){v+=(h&16?2:h&1)*b;b/=3;if(!b)putchar(v==26?32:v+97),v=0,b=9;}}

Readable:

#include<cstdio>
int b=9,v;
int main(int h,char**c)
{
    for(c++;h=**c;c[0]++)
    {
        v+=(h&16?2:h&1)*b;
        b/=3;
        if(!b)putchar(v==26?32:v+97),v=0,b=9;
    }
}


Input text from one file, output it to another

C
The whole point of having multiple programming languages, is that you need to use the right tool for the job.
In this case, we want to copy bytes from one file to another.
While we could use something fancy like bash or ruby, or fall to the power of ASM, we need something quick, good with bits and fast.
The obvious choice is C.
The SIMPLEST way of doing it would be like so:
#include <stdio.h>
#define THEORY FILE
#define AND *
#define PRACTICE myfile1
#define SOLUTIONS myfile2
#define ARE fopen
#define IMPORTANT "r"
#define BAD "w"
#define LOL fclose
#define PLEASE fgetc
#define HELP fputc
#define ME return
#define NEVER for
#define SURRENDER !=
#define VERY filename1
#define NOT filename2
#define _ 1

int copyFile(char* filename1, char* filename2)
{
  THEORY AND PRACTICE = ARE (VERY, IMPORTANT);
  THEORY AND SOLUTIONS = ARE (NOT, BAD);
  NEVER (;_;)
  {
    HELP(PLEASE(PRACTICE),SOLUTIONS);
  }
  ME _SURRENDER_;
}

This  is evil because it will read garbage on things like cygwin, is completely chinese for a beginner, will scare him when he realizes it's a call for help and, obviously, because C.


Solve an equation with (almost) any numbers you like

Retina, 58 bytes

[-+]
$&1
\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&
+`1_

1+
$.&

Try it online!

Alternative solution at the same byte count:

((\+)|(-))*
$._$*1$#3$*1$#2$*_$&
+`1_

([+-])1*
$+1
1+
$.&

Try it online!

Explanation

The basic idea is to turn all the +s and -s into simple +1 and -1 operations and then to prepend a sufficiently large number that makes all the equations work. To make the equations match, we can simply prepend the same number to each of them, and then reduce it by one for each +1 and increase it by one for each -1 after it. Since we'll be working with unary numbers, the only catch is that the first number needs to be large enough that we can reduce it by 1 enough times.

[-+]
$&1

We start by inserting a 1 after each - or +.

\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&

The \B ensures that these matches are either at the beginning of the input, or between a = and a + or -, i.e. all the positions where we want to insert the leading number of an expression. The  ((\+1)|(-1))* part then simply counts the number of +1s and -1s in groups 2 and 3 respectively. Now let's break down the substitution string:

$._$*1   # For each character in the current string, insert a 1. This is
         # an offset which is the same for each expression and is guaranteed
         # to be large enough that all subsequent +1s can be cancelled.
$#3$*1   # For each -1, insert a 1.
$#2$*_   # For each +1, insert a _.
$&       # Re-insert the string of +1s and -1s.

+`1_

Repeatedly drop 1_ from the string, applying the required cancellation from the +1s.

1+
$.&

Finally, replace all the strings of 1s with their lengths to convert from unary to decimal.


The teacher is always wrong, flip his answer

05AB1E, 45 41 40 39 38 bytes

Code:

“‰¦žä¥æ€¸pe…Ü€¸“ð¡2ôDí«D€™«vy`:D_D¹Êiq

Explanation:

It first starts with the compression:

“‰¦žä¥æ€¸pe…Ü€¸“

This is a compressed version of "true false yeah nope yes no". After that, we split on the spaces with ð¡, resulting into:

['true', 'false', 'yeah', 'nope', 'yes', 'no']

We slice this array into pieces of 2 with 2ô, resulting into:

[['true', 'false'], ['yeah', 'nope'], ['yes', 'no']]

We duplicate this array and reverse each element of it with Dí. Then we append this to our first array with «, resulting into:

[['true', 'false'], ['yeah', 'nope'], ['yes', 'no'], ['false', 'true'], ['nope', 'yeah'], ['no', 'yes']]

To get the titlecased words, we duplicate the array again and convert each word to titlecase with €™. Finally, this is appended to the initial array. So, the final list is:

[['true', 'false'],
 ['yeah', 'nope'],
 ['yes', 'no'],
 ['false', 'true'],
 ['nope', 'yeah'],
 ['no', 'yes'],
 ['True', 'False'],
 ['Yeah', 'Nope'],
 ['Yes', 'No'],
 ['False', 'True'],
 ['Nope', 'Yeah'],
 ['No', 'Yes']]

The imporant part here is that Nope comes before No. Eventually, we get to this part of the code:

vy`:D_D¹Êiq

Explanation:

v            # For each in the array...
 y`          #   Push the array (containing 2 words) and flatten.
   :         #   Replace the first word with the second.
    D_       #   Duplicate and negate (resulting 0 into 1 and 1 into 0).
                 If this is not possible, this results into nothing.
      D      #   Duplicate the top of the stack again.
       ¹Ê    #   If it's not equal to the inital input string...
         iq  #     Quit the program and implicitly print the processed string.

Uses the CP-1252 encoding. Try it online!.


J, 4 characters
p:i.

Usage:
   p:i.10
2 3 5 7 11 13 17 19 23 29

The problem with using J here is that I don't really know how efficient it is. I'd assume that as a language specialising in "mathematical, statistical, and logical analysis of data", that the algorithm used to generate the primes is pretty good.
I did look at the C source for clues, but it turns out that the C source for J is almost as unreadable as J itself. :-)
(The file is called v2.c for anyone who wants to have a look)


Python (imperfect) 493 474 - 300 = 174
There are a fair number of issues with this solution, firstly  that it ignores any exponent that is too large (any in which the exponent is greater than 100). I actually don't think this removes any possibilities for inputs less than or equal to 5, but I'm not 100% sure.
Another thing is that it does not consider any unary square roots, as it would get complicated (any solution with any term equal to 0 or 1 would produce an infinite number of solutions). It also does not consider any unary negation (the '-' symbol) for the same reason, as well as the fact that I'm not actually sure if the question asked for it.
I also considered what criteria should decide if two expressions were equivalent, but I couldn't find a way to rigorously define it in a way I found to be intuitive, so (for now at least) I didn't implement anything like that. This does mean that it outputs quite a few results, and it also uses parenthesis in a fairly naive way.
On a side note I think that this might include the longest single line of code I've written, especially before it was fully golfed.
R=range
F=lambda s:lambda a,b:eval(s)
L=lambda D,N:[(int(str(D)*N),str(D)*N)]+[(o(u,v),"(%s%s%s)"%(s,c,t))for p in R(1,N)for u,s in L(D,p)for v,t in L(D,N-p)for c,o in[('+',F('a+b')),('-',F('a-b')),('*',F('a*b')),('/',F("1.*a/b if b else''")),('^',F("''if(a<0 and int(b)!=b)|(a and b<0)|(b>99)else a**b")),('v',F("b**(1./a)if a and(a>=0 or b)and(b>=0 or int(1./a)==1./a)&(1./a<99)else''"))]if o(u,v)!='']
A=L(*input())
for i in R(11):
 for v,s in A:
    if v==i:print i,s[1:-1]

Example: ('v' represents '√')
2,3

0 2*(2-2)
0 2v(2-2)
0 (2-2)*2
0 (2-2)/2
0 (2-2)^2
1 2^(2-2)
1 2-(2/2)
1 2v(2/2)
1 (2/2)^2
2 2v(2+2)
2 2+(2-2)
2 2-(2-2)
2 2v(2*2)
2 2*(2/2)
2 2/(2/2)
2 2^(2/2)
2 2v(2^2)
2 (2+2)-2
2 (2+2)/2
2 (2-2)+2
2 (2*2)-2
2 (2*2)/2
2 (2/2)*2
2 (2/2)v2
2 (2^2)-2
2 (2^2)/2
3 2+(2/2)
3 (2/2)+2
6 2+(2+2)
6 2+(2*2)
6 2+(2^2)
6 (2+2)+2
6 (2*2)+2
6 (2^2)+2
8 2*(2+2)
8 2*(2*2)
8 2*(2^2)
8 (2+2)*2
8 (2*2)*2
8 (2^2)*2


How to simplify ternary expressions in Javascript

If you know that x and y cannot contain falsy values, as your code examples suggest, you can do the following to eliminate duplicate evaluation of A or D:

a += A && (B && x || C && y) || D;

Demo code and test cases in the following snippet:

// return x
test(1,1,0); // A and B
test(1,1,1); // A and B (and C)

// return y
test(1,0,1); // A and C

// return D
test(0,0,0); //
test(0,0,1); // C
test(0,1,0); // B
test(0,1,1); // B and C
test(1,0,0); // A

function test(A, B, C) {
  var x = 'x', y = 'y', D = 'D';
  a = A && (B && x || C && y) || D;
  expected = (A && B ? x : A && C ? y : D);
  var ws = ' ';
  console.log(
    [
      A && 'A' || ws,
      B && 'B' || ws,
      C && 'C' || ws
    ].join(ws),
    ' ==> a = ' + a,
    a === expected ?
      'Passed' :
      'Failed, expected ' + expected
  );
}

Otherwise, if falsy values are possible, you could do this:

a += [D, x, y][A && (B && 1 || C && 2) || 0];

Demo code and test cases in the following snippet:

// return x
test(1,1,0); // A and B
test(1,1,1); // A and B (and C)

// return y
test(1,0,1); // A and C

// return D
test(0,0,0); //
test(0,0,1); // C
test(0,1,0); // B
test(0,1,1); // B and C
test(1,0,0); // A

function test(A, B, C) {
  var x = false, y = 0, D = '';
  A = !!A; B = !!B; C = !!C;
  a = [D, x, y][A && (B && 1 || C && 2) || 0];
  expected = (A && B ? x : A && C ? y : D);
  var ws = ' ';
  console.log(
    [
      A && 'A' || ws,
      B && 'B' || ws,
      C && 'C' || ws
    ].join(ws),
    ' ==> a = ' + xyD(a, x, y, D),
    a === expected ?
      'Passed' :
      'Failed, expected ' + xyD(expected, x, y, D)
  );
}

function xyD(result, x, y, D) {
  return result === x ? 'x' :
         result === y ? 'y' :
         result === D ? 'D' : '<error>' ;
}


1. Retina, 0 bytes

Try it online!

The empty program prints 1 when given empty input (i.e. itself), because it counts how often the empty regex matches the input (which is always 1+length(input)).


Ruby, 115 characters

f=->a,t{[a,a.rotate(~s=r=0),a.reverse].map{|x,*y|(t>Time.gm(x<100?x+2e3-100*x/=50:x,*y)||r+=100
s+=1)rescue p}
r/s}

This defines a function f that takes two arguments: an array containing the input, and "today's" date.

Examples:

f[[14,12,14], Time.new]
100
f[[8,2,2006], Time.new]
0
f[[8,2,2006], Time.new(2006, 7, 5)]
50
f[[6,7,5], Time.new(2006, 7, 5)]
33


JavaScript (ES6), 171 bytes

Takes input in currying syntax (width)(height). Returns an array of strings.

w=>h=>[...Array((h>0?h:-h)*16||1)].map((_,y)=>'012345678'.replace(/./g,x=>' #'[((c=+'3733317900134444'[(h<0?16-~y/h:y/h)|0]||17)>>4-x|c>>x-4)&1|!h].repeat(w>0?w:-w))||'#')

Try it online!

How?

Only the left half of the sheriff is encoded as binary bitmasks, including the middle column:

    ##.         00011     3
   ###..        00111     7
    ##.         00011     3
    ##.         00011     3
    ##.         00011     3
     #          00001     1
   ###..        00111     7
  #  #  .       01001     9
 #   #   .  --> 10001 --> 17
 #   #   .      10001     17
     #          00001     1
    ##.         00011     3
   #   .        00100     4
   #   .        00100     4
   #   .        00100     4
   #   .        00100     4

Because there are only two values greater than \$9\$ and they're both equal to \$17\$, we can replace them with \$0\$ in order to have one character per row and still have a rather straightforward decoding process. Hence the packed string:

'3733317900134444'

For \$0 \le x \le 8\$ and \$0 \le y \le 15\$, the 'pixel' at \$(x,y)\$ is given by:

' #'[                                  // character lookup:
  (                                    //   0 = space
    (                                  //   1 = '#'
      c = +'3733317900134444'[y] || 17 // extract the bitmask for this row; 0 -> 17
    )   >> 4 - x                       // test the left part, middle column included
    | c >> x - 4                       // test the right part, middle column also included
  ) & 1                                // isolate the least significant bit
]                                      // end of character lookup


Python3, 363 chars

Since no answer is given till today, I hand in what I got. Sadly, the try/except block is too fat, I didn't found a way to save chars there. It is really tricky with the nested loops there, not all can be done with list comprehensions I think, but maybe someone can tell me how.

However, I restricted the challenge myself to only use basic math '+-*/' and no parentheses.

a,b = input().split()
r=0
for time in [c for c in range(int(a),int(b)) if c/10%10<6]:
 t,*ts='%04d'%time
 e=[t]
 for d in ts:
  e=[(n+o+d,n+d)[o==' '] for o in ' -+*/=' for n in e]
 for h in [g for g in [e.split('=') for e in e if '='in e] if len(g)>1]:
  for k in h:
   try:
    if eval(h[0]) != eval(k):
     break
   except:
    break
  else:
   r+=1
print(r)

My full code (hope something explanatory) on this CodeGolf can be found on my pastebin.


JavaScript (ES6), 171 bytes
Takes input in currying syntax (a)(n). Outputs by modifying the input matrix.

a=>g=(n,y=a[F='findIndex'](r=>~(i=r[F](v=>v>'?'))),x=i,R=a[y])=>!n--|[-1,0,1,2].every(d=>(R[x]='<^>v'[d+1],(c=(a[Y=y+~-d%2]||0)[X=x+d%2])<1?g(n,Y,X):n|c!='$')&&(R[x]=' '))

Try it online!
Commented
a =>                           // a[] = input matrix
g = (                          // g = recursive function taking:
  n,                           //   n = number of remaining moves
                               //   (x, y) = current coordinates, initialized as follows:
  y = a[F = 'findIndex'](r =>  //     y = index of the row containing the starting point,
    ~(i = r[F](v => v > '?'))  //         found by iterating over all rows r until we
  ),                           //         find some i such that r[i] > '?'
  x = i,                       //     x = index of the column of the starting point
  R = a[y]                     //   R[] = current row
) =>                           //
  !n-- |                       // decrement n; force failure if we're out of moves
  [-1, 0, 1, 2].every(d =>     // for each direction d, where -1 = left, 0 = up,
    (                          // 1 = right and 2 = down:
      R[x] = '<^>v'[d + 1], (  //   update the current cell with the direction symbol
        c = (                  //   c = content of the new cell at (X, Y) with:
          a[Y = y + ~-d % 2]   //     Y = y + dy
          || 0                 //     (use a dummy value if this row does not exist)
        )[X = x + d % 2]       //     X = x + dx
      ) < 1 ?                  //   if c is a space:
        g(n, Y, X)             //     we can go on with a recursive call
      :                        //   else:
        n | c != '$'           //     return false if n = 0 and we've reached the target
    ) &&                       //   unless the above result is falsy,
    (R[x] = ' ')               //   restore the current cell to a space
  )                            // end of every()


Python 3, 9796 bags

Building on Jonathan's answer:

import itertools as it

def powerset(iterable):
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

def f(a,m,l):
 r=[];b=[]
 while a:
  c =  min(list(powerset(a[:l])),key=lambda w: abs(sum(b)+sum(w)-m))
  if sum(c)==0:
   c = a[:l]
  b+=[a.pop(a.index(min(c,key=lambda w: abs(sum(b)+w-m))))]
  if sum(b)>=m:r+=[b];b=[]
 return r

This relies on powerset from itertool's cookbook. First finds optimal subset of the buffer based on minimizing difference from target weight for all subsets, and then picks an element out of this subset based on same criterion. If no optimal subset selects from the whole buffer.


Infinitely Print Zeno's Dichotomy Paradox (1/(2^n))

05AB1E, 10 9 bytes

Saved 1 byte thanks to Erik the Outgolfer

[No…+1/J?

Try it online!

Explanation

[           # loop over N infinitely [0 ...]
 No         # calculate 2^N
   …+1/J    # join with the string "+1/"
        ?   # print without newline


APL (61)

{∇n⊣⎕DL.1⊣⎕SM←1 1,⍨⊂' '⍪⊖⍉↑⍴∘'▇'¨,0,⍪n←24⌊0⌈⍵+3-?5/⍨⍴⍵}?24/40

It starts with random-sized bars, and changes the height of each of the bars by a random number between -2 and 2 each frame.

Screenshot:


Create your own Gym Exercise and follow along irl

SpecBAS - 387 bytes

1 DIM m$=" @"#13"/|\"#13"/ \","\@/"#13" |"#13"/ \","|@_"#13" |"#13"/ \","_@|"#13" |"#13"/ \","@/"#13" |"#13"/|\"," \@"#13" |"#13"/|\","|@|"#13" |"#13"/ \","\@\"#13" |"#13"/ \","/@/"#13" |"#13"/ \"
2 INPUT a$: o=0
3 IF LEN a$<2 OR LEN a$>100 THEN 10
4 FOR i=1 TO LEN a$
5 n=VAL(a$(i))
6 IF n=0 OR n=o THEN 10
7 CLS : ?m$(n): o=n: WAIT 750
8 NEXT i
9 GO TO 4
10 CLS : ?" @"#13"-O-"#13"/ \"#13"FAT"

Keeps looping until you press ESC. Failure to exercise properly (incorrect input - in this example a 0 as one of the steps) leads to fatness. The GIF loops, in the program it just stops at that point.

#13 is the SpecBAS equivalent to \n and lets you include line feed in strings.


Python 2, 409 390 377 bytes

def f(p):
 p=map(lambda s:map(lambda d:d==3*(' ',)and(0,-1)or(int(d[0]+d[1]),'><^v'.index(d[2])),zip(s[::3],s[1::3],s[2::3])),p);x,y=max([(x,y)for x in range(len(p[0]))for y in range(len(p))],key=lambda(x,y):p[y][x][0]);r=o=0
 try:
  while 1:
   1/(y*x>=0);d=p[y][x]
   if-1<d[1]:r=eval('r%sd[0]'%'+-*/'[o]);o=d[1];a=(-(o==1),1)[o<1];b=(-(o==2),1)[o>2]
   x+=a;y+=b
 except:print r

The second and third indent levels are a raw tab and a raw tab plus a space, respectively. Markdown mangles the raw tabs, so they've been replaced by two spaces.

Ungolfed:

def follow(path):
  # Split path's strs into DDAs ((0, -1) for blank, else (int, int))
  path = map(
    lambda s: map(
      lambda dda: (0, -1) if dda == (' ', ' ', ' ') else (int(dda[0] + dda[1]), '><^v'.index(dda[2])),
      zip(s[::3], s[1::3], s[2::3])
    ),
    path
  )

  # Find highest DDA
  x, y = max([(x, y) for x in range(len(path[0])) for y in range(len(path))], key=lambda (x, y): path[y][x][0])

  result = 0
  op = 0  # addition
  try:
    # Keep following the path until we get an IndexError
    while True:
      if y < 0 or x < 0: raise IndexError

      dda = path[y][x]
      if dda[1] != -1:
        # It's not empty - do the operation & change direction
        const = dda[0]

        result = eval('result %s const' % '+-*/'[op])

        op = dda[1]

        dx = 1 if op == 0 else -1 if op == 1 else 0
        dy = 1 if op == 3 else -1 if op == 2 else 0

      # Move to the next thing
      x += dx
      y += dy
  except IndexError:
    # We've exited the path - return
    print result

Ideone it! (all test cases)


Jelly,  77 73  71 bytes

“£RĿÐƭðṚ°ƲṂṾẒ=ʂXḣsịɠ<»Ḳµ,Ṛ;€"“¡D⁺“a&»j“¿<z»W¤ṙ3
×20<“FYeoy³ƓɗʋṆ‘Sị¢⁾. y

A monadic link taking the number and returning a list of characters; or a full program printing the result.

Try it online!

How?

“ ... »Ḳµ,Ṛ;€"“¡D⁺“a&»j“¿<z»W¤ṙ3 - Link 1, name list: no arguments
“ ... »                          - compression of "Ultra Extremely Very.strongly Strongly Moderately Slightly"
       Ḳ                         - split at spaces
        µ                        - monadic chain separation, call that adjectives
          Ṛ                      - reverse adjectives
         ,                       - pair these two lists
              “¡D⁺“a&»           - compression of [" alkaline"," acidic"]
             "                   - zip with:
           ;€                    -   concatenate for €ach
                             ¤   - nilad followed by links as a nilad
                       “¿<z»     -   compression of "Neutral"
                            W    -   wrap in a list
                      j          - join
                              ṙ3 - rotate left by 3: ["Strongly alkaline","Moderately alkaline","Slightly alkaline","Neutral","Slightly acidic","Moderately acidic","Strongly acidic","Very.strongly acidic","Extremely acidic","Ultra acidic","Ultra alkaline","Extremely alkaline","Very.strongly alkaline"]

×20<“FYeoy³ƓɗʋṆ‘Sị¢⁾. y - Main link: number, pH
×20                     - multiply by 20
    “FYeqy³ƓɗʋṆ‘        - code-page indexes = [70,89,101,111,121,131,147,157,169,180]
   <                    - less than? (vectorises)
                        -   i.e.: pH < [3.5,4.45,5.05,5.55,6.05,6.55,7.35,7.85,8.45,9]
                S       - sum
                  ¢     - call last link (1) as a nilad
                 ị      - index into (1-indexed and modular)
                        - ...note that the sum is never 11 or 12, so "Ultra alkaline" and
                        -    "Extremely alkaline" wont be fetched, but that a sum of 0
                        -    fetches "Very.strongly alkaline", as required.
                   ⁾.   - literal list of characters ['.', ' ']
                      y - translate (replace any '.' with a ' ' i.e. for "Very.strongly")
                        - if running as a full program, implicit print


Write a program that always prints N when it is shifted N times up the ASCII alphabet


Given the names of two planets, give the distance

CJam, 54 51 44 bytes

2{"X84VT:Z/3KD'Y->>6\ Ta "3/r26b93%=70be4}*-

Try it online in the CJam interpreter.

Idea

We use a simple hashing function to identify all eight planets. By considering each name as the array of its code points, converting them from base 26 to integer and taking the result modulo 93 then modulo 8, Mercury, Venus, Earth, etc. map to 2, 4, 0, 1, 3, 5, 6 and 7.

Now, we choose a point that lies 320,000 km behind Neptune and calculate the distances of all eight planets to that point. After dropping four trailing zeroes and reordering the planets so that they fit the 8 indexes from above, we obtain the array

[435172 427338 444341 372299 439312 307672 162777 32]

which, if we encode each integer in base 70, yields the following:

[
   [1 18 56 52] [1 17 14 58] [1 20 47 51] [1 5 68 39]
   [1 19 45 62] [  62 55 22] [  33 15 27] [       32]
]

Remembering that two adjacent digits (A B) can be replaced with ((A-1) (B+70)), we can modify the array from above so that all integers can be encoded as printable ASCII characters:

["X84" "VT:" "Z/3" "KD'" "Y->" ">6\\" " Ta" " "]

Code

2{                         e# Do twice:
  "X84VT:Z/3KD'Y->>6\ Ta " e#   Push that string.
  3/                       e#   Chop it into chunks of length 3.
  r                        e#   Read a token from STDIN.
  26b                      e#   Convert from base 26 to integer.
  93%                      e#   Take the result modulo 93.
  =                        e#   Retrieve the chunk at that index.
  70b                      e#   Convert from base 70 to integer.
  e4                       e#   Multiply by 10,000.
}*                         e#
-                          e# Subtract the two results.


Create every combination of variable groups up to order n

LATEX, 354 bytes

When I saw this I knew it had to be done in Latex.  Equations just look so crisp and clean in Latex and I can't stand using ^ for power.

\documentclass{article}\input tikz\usepackage{intcalc}\usepackage{ifthen}\begin{document}\typein[\a]{}\typein[\b]{}\foreach\x in{1,...,\intcalcPow{\b+1}{\a}}{\begin{equation}\foreach[count=\i]\y in{a,...,z}{\ifthenelse{\(\i<\a\)\OR\(\i=\a\)}{\y^\intcalcDiv{\intcalcMod{\x}{\intcalcPow{\b+1}{\i}}}{\intcalcPow{\b+1}{\i-1}}}{}}\end{equation}}\end{document}

Explanation

There are three main forces at work here \typein  which is what allows us to take input from the command line, the intcalc package which is what allows us to make calculations with our variables, and the Latexequation environment.

Once we have taken in input we begin a loop we loop \intcalcPow{\b+1}{\a} times, once for each result we want to print.  Each loop we begin an equation environment and loop through the alphabet keeping track of \y for the current letter and \i for the current number of runs.  If \i is greater than or equal to \a we don't print anything at all (according to the specs this is not strictly necessary however Latex will overflow for values greater than 1 if we don't do this).  We then print \y to our equation and raise it to the power of

\intcalcDiv{\intcalcMod{\x}{\intcalcPow{\b+1}{\i}}}{\intcalcPow{\b+1}{\i-1}}

That whole mess simply means take the \ith digit of \x in base \b+1.  This ensures that the powers are decoded properly.

Example output:

Here is the output for 3, 2


Jelly, 19 bytes

11ị“bMAanlseovc”iµÞ

This is a monadic link that takes a list as argument and sorts it. Try it online!

Background

Jelly uses modular, 1-based indexing. If we repeat the months names often enough to obtain 11 characters, we get the following array.

J a n u a r y J a n u
F e b r u a r y F e b
M a r c h M a r c h M
A p r i l A p r i l A
M a y M a y M a y M a
J u n e J u n e J u n
J u l y J u l y J u l
A u g u s t A u g u s
S e p t e m b e r S e
O c t o b e r O c t o
N o v e m b e r N o v
D e c e m b e r D e c

In the 11th (last) column, all characters are different, so we can use them to identify the order of the months.

How it works

11ị“bMAanlseovc”iµÞ  Monadic link. Argument: A (array of months)

                 µ   Combine the preceding chain into a link.
                  Þ  Sort A by that link.
11ị                    Select the 11th character of the month's name.
   “bMAanlseovc”       Find the index of that character in "bMAanlseovc".
                       For 'u' ("January"), this returns 0 (not found).


Mathematica, 42 bytes

2Boole[#==ToeplitzMatrix[#&@@@#,#&@@#]]-1&

Mathematica doesn't have a built-in to check whether something is a Toeplitz matrix, but it does have a built-in to generate one. So we generate one from the first column (#&@@@#) and the first row (#&@@#) of the input and check whether it's equal to the input. To convert the True/False result to 1/-1 we use Boole (to give 1 or 0) and then simply transform the result with 2x-1.


Char Count 61

lon|ct|oh|^ra|...t.+i|^c?u|or.+u|r.+c.|e..+e|f.?e|^h?as|be*.i

One 3 characters better than accepted answer!

63-character solution found with Peter Norvig's Regex golf solver. 61-character improvement found by a personal rewrite of that program in Go.


Python 2, 50 49 bytes

-1 byte thanks to @Jonathan Allan

f=lambda n,A:n>=0and(n<1)+sum(f(n-x,A)for x in A)

Try it online!


Infinite Sequence of Unique Random Integers

Python 3, 137 127 123 138 117 99 98 bytes

  A named or unnamed function which returns an infinite iterable (such as a Python generator)

from random import*
def f(x=[],y=1):
 while y in x or.5<random():y+=1
 yield y;yield from f(x+[y])

-10 bytes by putting the conditional in one line (Thanks, @Dennis)
-4 bytes by initializing r at the beginning of the loop
+15 bytes by remembering numbers can contain zeroes...
-21 bytes by renaming randint, and moving the condition in the head of the inner loop
-18 bytes by switching to a functional paradigm
-1 bytes by moving from or ...>.5 to .5<random() (thanks, @JonathanAllan)


Can this container hold this much liquid?

Snails, 58 bytes

Input is taken exactly as in the examples.

t\ t\L{t\L?t\ z!.o=(\ ,\C},!(tz(\L!.!~|\ !.o=(\ ,\C},!(t\L

A 4 bytes longer version is fast enough to instantly complete the test cases (Try this version online):

?^
t\ t\L{t\L`?t\ z!.o=(\ ,\C},!(tz(\L!.!~|\ !.o=(\ ,\C},!(t\L

An indented formatting of the latter:

?^
    t\
    t\L
    {
        t\L`?
        t\
        z!.
        o=(\ ,\C
    },
    !(tz(
         \L!.!~
         |
         \ !.o=(\ ,\C
},
!(t\L


Retina 0.8.2, 56 bytes

(?=( \S+)+)
x^$#1
\b0x.\d+

\b1x
x
x.1
x
 0

 -
-

+

Try it online! Link includes test cases. Explanation:

(?=( \S+)+)
x^$#1

Insert all of the powers of x, including x^1 but not x^0.

\b0x.\d+

Delete all powers of x with zero coefficients, but not a trailing 0 (yet).

\b1x
x

Delete a multiplier of 1 (but not a constant 1).

x.1
x

Delete the ^1 of x^1.

 0

Delete a constant 0 unless it is the only thing left.

 -
-

Delete the space before a -.

+

Change any remaining spaces to +s.


Bash (31)

[ -e x ]&&diff data x;cp data x

Kinda obvious.


Snakes and Ladders probability of winning

C, ~.25 seconds

I have calculated by using dynamic simulations instead of probability of each dice roll. The more accurate the probability, the slower... here a brief code...

Compile using:

gcc -o Snakes snakes.c

Code:

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

int main()
{
    srand(time(0));

    // initialize principal variables
    int NumberOfSpaces   = 100,
    NumberOfPlayers  = 4,
    PlayerPosition[] = { 46, 56, 36, 66 };
    //PlayerPosition[] = {0, 0, 0, 0};

    // arrays of positions, must be in numerical order,
    // must be in (start, end) format. correct - 1, 2, 5, 6, 8, 9
    //                               incorrect - 1, 2, 8, 9, 5, 6
    int LadderPositions[10] = { 3, 10, 5, 20, 20, 31, 22, 49, 44, 87 },      // positions of ladders
    SnakePositions[10] = { 11, 3, 15, 1, 35, 22, 54, 29, 60, 20 }, // positions of snakes
    SnakesLadders    = 10;                                       // # of snakes + ladders

    // static arrays to hold
    // # of dice rolls to complete game
    int Player1Wins[10000],
    Player2Wins[10000],
    Player3Wins[10000],
    Player4Wins[10000];

    int NumberOfSimulations = 10001;

    int OutsideLoop, Counter = 1, i, a, Win, EvenArray;
    for (OutsideLoop = 0; OutsideLoop < NumberOfPlayers; OutsideLoop++)      // do a simulation for each player
        for (a = 0; a < NumberOfSimulations; a++)                       // play for each simulation
        {
            for (i = PlayerPosition[OutsideLoop]; i <= NumberOfSpaces + 1; i += (rand() % 6 + 1)) // roll the dice for each turn
            {
                Counter++ ;
                for (EvenArray = 0; EvenArray < SnakesLadders; EvenArray+=2) // check if space is snake or ladder
                {
                    if (i == LadderPositions[EvenArray])
                        i = LadderPositions[EvenArray + 1];
                    if (i == SnakePositions[EvenArray])
                        i = SnakePositions[EvenArray + 1];
                }
             }
             // put value in array
             if (OutsideLoop == 0)
                 Player1Wins[a] = Counter;
             else if (OutsideLoop == 1)
                 Player2Wins[a] = Counter;
             else if (OutsideLoop == 2)
                 Player3Wins[a] = Counter;
             else if (OutsideLoop == 3)
                 Player4Wins[a] = Counter;
             Counter = 0;
        }

    // count how many time each person won
    int P1Wins = 0, P2Wins = 0, P3Wins = 0, P4Wins, Ties = 0;
    for (Win = 0; Win < NumberOfSimulations; Win++)
    {
        if (Player1Wins[Win] < Player2Wins[Win] && Player1Wins[Win] < Player3Wins[Win] && Player1Wins[Win] < Player4Wins[Win])
            P1Wins++;
        else if (Player2Wins[Win] < Player1Wins[Win] && Player2Wins[Win] < Player3Wins[Win] && Player2Wins[Win] < Player4Wins[Win])
            P2Wins++;
        else if (Player3Wins[Win] < Player1Wins[Win] && Player3Wins[Win] < Player2Wins[Win] && Player3Wins[Win] < Player4Wins[Win])
            P3Wins++;
        else if (Player4Wins[Win] < Player1Wins[Win] && Player4Wins[Win] < Player2Wins[Win] && Player4Wins[Win] < Player3Wins[Win])
            P4Wins++;
        else if (Player2Wins[Win] == Player1Wins[Win] == Player3Wins[Win])
            Ties++;
    }

    printf("[ + ] Namaste! Welcome to the Snakes & Ladders guess who wins program!\n");
    printf("[ + ] I will run 10K simulations of the game to make a guess on the probability of the winner.\n");
    printf("[ + ] Given %i players, with starting positions of :\n[ + ] P1 - %i\n[ + ] P2 - %i\n[ + ] P3 - %i\n[ + ] P4 - %i\n[ + ] Here's the probability I think each player has of winning...\n", NumberOfPlayers, PlayerPosition[0], PlayerPosition[1], PlayerPosition[2], PlayerPosition[3]);
    printf("[ + ] P1 = %i / 10000\n[ + ] P2 = %i / 10000\n[ + ] P3 = %i / 10000\n[ + ] P4 = %i / 10000\n[ + ] Ties = %i\n", P1Wins, P2Wins, P3Wins, P4Wins, Ties);
    return 0;
}

Environment - timed using time (bash command) on linux core i7

10    simulations ~ .003 second

10000 simulation  ~ .030 second

Sample outputs :

time ./Snakes
[ + ] Namaste! Welcome to the Snakes & Ladders guess who wins program!
[ + ] I will run 10K simulations of the game to make a guess on the probability of the winner.
[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 10
[ + ] P2 - 21
[ + ] P3 - 50
[ + ] P4 - 70
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 86 / 10000
[ + ] P2 = 254 / 10000
[ + ] P3 = 131 / 10000
[ + ] P4 = 9098 / 10000
[ + ] Ties = 0
real    0m0.036s
user    0m0.036s
sys 0m0.000s

Alt input position:

[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 15
[ + ] P2 - 5
[ + ] P3 - 60
[ + ] P4 - 50
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 955 / 10000
[ + ] P2 = 3041 / 10000
[ + ] P3 = 1833 / 10000
[ + ] P4 = 3572 / 10000
[ + ] Ties = 0
real    0m0.024s
user    0m0.024s
sys     0m0.000s

More input:

[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 46
[ + ] P2 - 56
[ + ] P3 - 36
[ + ] P4 - 66
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 94 / 10000
[ + ] P2 = 442 / 10000
[ + ] P3 = 2454 / 10000
[ + ] P4 = 6319 / 10000
[ + ] Ties = 0
real    0m0.018s
user    0m0.018s
sys     0m0.000s


Create this "String Mix-Up" function in as few bytes as possible

Stax, 16 11 bytes

ÄE┘¢8·╦Ωb•∩

Run and debug it online

The corresponding ascii representation of the same program is this.

Y#xyz|eyr|Sx?

This fixes the bugs in original version.  It uses conditionals and stuff.

Y                   Save 2nd input in y.  Now the two inputs are x and y.
 #                  Occurrences of y in x. (a)
  xyz               x, y, ""
     |e             replace first occurrence
       yr|S         surround with y reversed. (b)
           x        first input. (c)
            ?       a ? b : c

The result is printed implicitly.


What's the most popular question right now?

JavaScript + JQuery, 178 bytes

Quite a simple approach that makes the StackExchange API do all the work.

$.ajax('//api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&notice=False&pagesize=5&site=codegolf').pipe(x=>x.items.map(x=>document.write(x.title+'
')))

a=x=>x.items.map(x=>document.write(x.title+'
'))
document.write('StackExchange&nbsp;Site:&nbsp;<input value="codegolf"> <button onclick="$.ajax({success:x=>{try{document.getElementById('pre').innerHTML=x.items.map(x=>x.title).join('\n')+'\n\nQueries left: ' + x.quota_remaining}catch(e){try{document.getElementById('pre').textContent='Queries left: ' + (x.quota_remaining || 'Error')}catch(e){document.getElementById('pre').textContent='Error'}}},url:'//api.stackexchange.com/search/advanced?sort='+document.getElementById('s').value+'&closed=False&wiki=False&notice=False&pagesize=5&site=' + this.previousElementSibling.value})">Go</button> Sort&nbsp;by:&nbsp;<select id='s'><option value="activity">Active</option><option value="votes" selected="selected">Score</option><option value="creation">New</option></select>

Some caveats while answering this question:

StackExchange API always trys to returns gzipped data. In JS, the browser un-gzips for you.
The API only seems to be able to return the top 100 at maximum, so if you were to filter out the closed questions programatically, you must assume that less than 96 of the top 100 questions are closed, which you can't so you have to do everything in the APIs query.
The things in the API are HTML encoded, so you must also decode those. In JS, I let the browser decode it, but in something like Python, you must employ an external library, or else hard-code the dozens of entities.

That said, here is my Python solution that has to jump all of those hoops:

Python 3, 259 bytes

import urllib.request as r,gzip,html,json
for i in json.loads(gzip.decompress(r.urlopen('http://api.stackexchange.com/search/advanced?sort=votes&closed=False&wiki=False&notice=False&pagesize=5&site=codegolf').read()))['items']:print(html.unescape(i['title']))


Transferring the DNA of bacteria from generations

Haskell -- 349

import Control.Monad
import System.Random
import Data.List
a=[0,1,2,3,3,1,1,2,0,0]
b=[a,a,a,a]
f 3 _=randomRIO(0,3)
f _ 3=randomRIO(0,3)
f x y=return$div(x+y)2
z::[Integer]->[Integer]->IO[Integer]
z x y=zipWithM f x y
c=filter(\x->length x==2).subsequences
r=sequence.map(\x->z(x!!0)(x!!1)).c
y=foldr(<=<)return.replicate 20
main=y r b>>=mapM_ print

Try it online with nicer looking source code: http://ideone.com/9FUMLd

The online example does only till 2 instead of 20 because of ideone's time limit.


Husk, 14 10 bytes

~f`öΠFf†€Ṗ

Takes three inputs: number of people to go, 2-row matrix of the constraints, and list of all people involved, in this order.
Returns all possible lists of people who go.
If you want to output only one list, replace the leftmost f by ḟ.
Try it online!

Explanation

The idea is to loop over the size-n subsets of p and keep those that satisfy the condition imposed by g: if the first person in a pair goes, then the second person must go too.

~f`öΠFf†€Ṗ  Implicit inputs, say n=3, g=[[1,3,3],[4,1,4]] and p=[1,2,3,4]
         Ṗ  All n-element subsets of p: [[1,2,3],[2,3,4],[1,3,4],[1,2,4]]
~f          Keep those subsets (say q=[1,2,4]) for which
  `ö        this function gives a truthy (nonzero) result:
       †     Deep map over g:
        €    index in q, or 0 if doesn't occur: [[1,0,0],[3,1,3]]
     Ff      Fold by select (filter second row by truthiness on first row): [3]
    Π        Product: 3

This program is one of those where it's really hard to explain how the program arguments are passed to the correct functions, but I'll try.
First, n is the first argument, so it can be given to Ṗ directly, making it a function that takes a list and returns its n-subsets.
The next two inputs are g and p, and the program's shape at this point is ~(f)(`öΠFf†€)(Ṗn) with parentheses added for clarity.
The operator ~ gives g to `öΠFf†€ and p to Ṗn, and combines the results with f.
Ṗnp is just the n-subsets of p, so that's simple.
The operator ` causes öΠFf†€ to take its arguments in the reverse order, so g is actually the second argument of this function.
The first argument is an element q of Ṗnp, which is extracted by f (filter).
We give q as an argument to €, which becomes a function for testing membership in q, and deep map that over the second argument, which is g.
Then ΠFf are applied to the result.
The role of ö is just to compose ΠFf†€ into one function, which we can then pass on to ` and ~f.


Convert Numbers to Letters, and vice-versa in a string

bash, 18 bytes

tr 1-90a-j a-j1-90

Try it online!


CJam, 105 99 bytes

{{": "+ol}%.=_:+\,:LX$-X$LX$e2Ld/]"
Number Correct: %d
Number Wrong: %d
Score: %d / %d * 100 = %.2f%%"e%}

This defines an anonymous function.

The code is 110 bytes long and qualifies for the × 0.9 randomization bonus.

Test run

$ cat qna.cjam
[
  [
    "42"
    "Yes"
    "4"
  ]

  [
    "What is the meaning of life, the universe, and everything"
    "Am I awesome(Yes/No)"
    "What is 2+2"
  ]
]

{zmrz~{": "+ol}%.=_:+\,:LX$-X$LX$e2Ld/]"
Number Correct: %d
Number Wrong: %d
Score: %d / %d * 100 = %.2f%%"e%}

~

$ cjam qna.cjam
What is 2+2: 4
Am I awesome(Yes/No): No
What is the meaning of life, the universe, and everything: 42

Number Correct: 2
Number Wrong: 1
Score: 2 / 3 * 100 = 66.67%


Python with PIL, score 0.094218

Compressor:
#!/usr/bin/env python
from __future__ import division
import sys, traceback, os
from PIL import Image
from fractions import Fraction
import time, io

def image_bytes(img, scale):
    w,h = [int(dim*scale) for dim in img.size]
    bio = io.BytesIO()
    img.resize((w,h), Image.LANCZOS).save(bio, format='PPM')
    return len(bio.getvalue())

def compress(img):
    w,h = img.size
    w1,w2 = w // 256, w % 256
    h1,h2 = h // 256, h % 256
    n = w*h
    total_size = 4*1024 - 8 #4 KiB minus 8 bytes for
                            # original and new sizes
    #beginning guess for the optimal scaling
    scale = Fraction(total_size, image_bytes(img, 1))
    #now we do a binary search for the optimal dimensions,
    # with the restriction that we maintain the scale factor
    low,high = Fraction(0),Fraction(1)
    best = None
    start_time = time.time()
    iter_count = 0
    while iter_count < 100: #scientifically chosen, not arbitrary at all
        #make sure we don't take longer than 5 minutes for the whole program
        #10 seconds is more than reasonable for the loading/saving
        if time.time() - start_time >= 5*60-10:
            break
        size = image_bytes(img, scale)
        if size > total_size:
            high = scale
        elif size < total_size:
            low = scale
            if best is None or total_size-size < best[1]:
                best = (scale, total_size-size)
        else:
            break
        scale = (low+high)/2
        iter_count += 1
    w_new, h_new = [int(dim*best[0]) for dim in (w,h)]
    wn1,wn2 = w_new // 256, w_new % 256
    hn1, hn2 = h_new // 256, h_new % 256
    i_new = img.resize((w_new, h_new), Image.LANCZOS)
    bio = io.BytesIO()
    i_new.save(bio, format='PPM')
    return ''.join(map(chr, (w1,w2,h1,h2,wn1,wn2,hn1,hn2))) + bio.getvalue()

if __name__ == '__main__':
    for f in sorted(os.listdir(sys.argv[1])):
        try:
            print("Compressing {}".format(f))
            with Image.open(os.path.join(sys.argv[1],f)) as img:
                with open(os.path.join(sys.argv[2], f), 'wb') as out:
                    out.write(compress(img.convert(mode='RGB')))
        except:
            print("Exception with {}".format(f))
            traceback.print_exc()
            continue

Decompressor:
#!/usr/bin/env python
from __future__ import division
import sys, traceback, os
from PIL import Image
from fractions import Fraction
import io

def process_rect(rect):
    return rect

def decompress(compressed):
    w1,w2,h1,h2,wn1,wn2,hn1,hn2 = map(ord, compressed[:8])
    w,h = (w1*256+w2, h1*256+h2)
    wc, hc = (wn1*256+wn2, hn1*256+hn2)
    img_bytes = compressed[8:]
    bio = io.BytesIO(img_bytes)
    img = Image.open(bio)
    return img.resize((w,h), Image.LANCZOS)

if __name__ == '__main__':
    for f in sorted(os.listdir(sys.argv[1])):
        try:
            print("Decompressing {}".format(f))
            with open(os.path.join(sys.argv[1],f), 'rb') as img:
                decompress(img.read()).save(os.path.join(sys.argv[2],f))
        except:
            print("Exception with {}".format(f))
            traceback.print_exc()
            continue

Both scripts take input via command line arguments, as two directories (input and output), and convert all images in the input directory.
The idea is to find a size that fits under 4 KiB and has the same aspect ratio as the original, and use a Lanczos filter to get as high of a quality out of the downsampled image as possible.
Imgur album of compressed images, after resizing to original dimensions
Scoring script output:
Comparing corpus/1 - starry.png to test/1 - starry.png... 0.159444
Comparing corpus/2 - source.png to test/2 - source.png... 0.103666
Comparing corpus/3 - room.png to test/3 - room.png... 0.065547
Comparing corpus/4 - rainbow.png to test/4 - rainbow.png... 0.001020
Comparing corpus/5 - margin.png to test/5 - margin.png... 0.282746
Comparing corpus/6 - llama.png to test/6 - llama.png... 0.057997
Comparing corpus/7 - kid.png to test/7 - kid.png... 0.061476
Comparing corpus/8 - julia.png to test/8 - julia.png... 0.021848
Average score: 0.094218


JavaScript (ES6), 27 31 30 bytes

Returns 0 for 0 or an array of solutions otherwise.

n=>n&&[...1e9+''].map(_=>n+=9)

Demo

let f =

n=>n&&[...1e9+''].map(_=>n+=9)

for(n = 0; n < 10; n++) {
  console.log(n, JSON.stringify(f(n)));
}


Labyrinth, 2 bytes

>@

The > rotates the source so that it becomes

@>

The instruction pointer is now in a dead end and turns around to hit the @ which terminates the program.

Of course, <@ would also work.


Convert a program to a palindromic program

Perl, 55 54 bytes

undef$/;$a=<>."\n__END__\n";print$a,scalar reverse$a;

Reads program source from stdin and writes to stdout.

Result of running on itself:

undef$/;$a=<>."\n__END__\n";print$a,scalar reverse$a;

__END__

__DNE__

;a$esrever ralacs,a$tnirp;"n\__DNE__n\".><=a$;/$fednu


Python 3, 124 123 111 96 bytes
f=lambda s,n=1:[x for x in[s[i:i+n]for i in range(len(s)+1)]if s.find(x)==s.rfind(x)]or f(s,n+1)

Looks for strings such that the first occurrence from the left is the same as the first occurrence from the right. The +1 in the range is to accommodate for the empty string case.
Now if only Python had a .count() which counted overlapping matches, then this would have been a fair bit shorter.


MATL, 46 43 bytes

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

Input is a 2D array with semicolon as row separator. For example, the input for the last test case is

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Try it online! Or verify all test cases (code slightly modified to take all inputs; the results appear after a few seconds)

Explanation

Let the input be an N×N matrix. The code first computes all (N+1)-tuples of block sizes that produce the appropriate matrix size. For example, for N=4 the tuples are 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. For each tuple it builds the block-diagonal matrix with those block sizes. It then checks if the matrix covers all the 1 entries in the input, and if so takes note of the number of 1 entries that were not present in the input. The final result is the minimum of all the obtained numbers.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display


APL (Dyalog Classic), 40 39 bytes

-1 thanks to Erik the Outgolfer

{⌈⌿↑⍺(⍉(1-⌈/+⌿+∘×⍨2⌈/0,+/⌈\↑(⌽⍺)⍵)↑⍉⍵)}

Try it online!


Python, 307 chars

S={'0001001011000':[]}
for i in[0]*7:
 for s in dict(S):
  for m in range(6):S.setdefault(''.join(s[int(x,16)]for x in['2150483769abc','3106428759abc','0326159487abc','0421753986abc','01234587a6c9b','012345976b8ca'][m]),[m]+S[s])
for j in[0]*input():
 L=S[raw_input()];print len(L)
 for m in L:print m/2,m%2

Computes S which is a mapping from a state (a string just like the input) to a list of move numbers which solve the state.  Generates a complete S on startup (only 715 states), then looks up each input and prints the answer.

Moves are implemented using a string of hex digits indicating where each result vertex comes from.

Takes about 0.15 seconds regardless of how big the input is.


x86_64 bytecode, 15 bytes

   0:   c7 04 24 00 00 04 00    movl   $0x40000,(%rsp)
   7:   9d                      popfq
   8:   8b 04 25 01 00 00 00    mov    0x1,%eax

Turns on the misaligned address trap flag and then immediately triggers it.


GNU Octave / MATLAB, 14

f=@(n)n+sin(n)

You don't generally take a standard input with Octave programs, so this is a function which gives an improved estimate of pi after every call on its previous output. Sample run:

octave> f=@(n)n+sin(n);
octave> format 'long'
octave> n = 1;
octave> n = f(n)
n =  1.84147098480790
octave> n = f(n)
n =  2.80506170934973
octave> n = f(n)
n =  3.13527633289972
octave> n = f(n)
n =  3.14159261159065
octave> n = f(n)
n =  3.14159265358979


Python 3, 190 bytes

lambda a:re.match("(the '!the %(: tokyo drift)?|(2# ' (2# %|'!%|' (five#|'!% (6#|% (7#|the fate of the %|f(9#)$".translate({33:" (and|&) ",35:"|10|ten)",39:"fast",37:"furious"}),a)
import re

Try it online!
A very naive attempt at this.


Retina, 48 bytes

i`(?<=([aeiou]).*?[^\W\d_aeiou])(?![aeiou])
$l$1

Try it online! Explanation: The lookahead searches for a point not followed by a vowel, while the lookbehind searches for an immediately preceding consonant and a previous vowel, which is then inserted in lower case.


Implement the Max-Pooling operation from Convolutional Neural Networks

Python 3, 101 108 bytes

def f(m,w):r=range(0,len(m),w);return[[max(sum([x[i:i+w]for x in m[j:j+w]],[]))for i in r]for j in r]

Thanks to Jo King and Jonathan Allan for some more bytes off!

Try it online!

Alternate (longer) version as a single Lambda expression:

Try it online!


Python 2, 154 bytes
I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
print D[T*L]

A straightforward DP approach. A fair chunk of the program is just reading input.
Explanation
We calculate a 2D dynamic programming table where each row corresponds to the first n parking spots, and each column corresponds to the number of trucks (or parts of a truck) placed so far. In particular, column k means that we've placed k//L full trucks so far, and we're k%L along the way for a new truck. Each cell is then the minimal number of cars to clear to reach the state (n,k), and our target state is (P, L*T).
The idea behind the DP recurrence is the following:

If we're k%L > 0 spaces along for a new truck, then our only option is to have come from being k%L-1 spaces along for a new truck
Otherwise if k%L == 0 then we have either just finished a new truck, or we'd already finished the last truck and have since skipped a few parking spots. We take the minimum of the two options.

If k > n, i.e. we've placed more truck squares than there are parking spots, then we put ∞ for state (n,k). But for the purposes of golfing, we put k since this is the worst case of removing every car, and also serves as an upper bound.
This was quite a mouthful, so let's have an example, say:
5 1 3
..##.

The last two rows of the table are
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]

The entry at index 2 of the second last row is 2, because to reach a state of 2//3 = 0 full trucks placed and being 2%3 = 2 spaces along for a new truck, this is the only option:
  TT
..XX

But the entry at index 3 of the second last row is 1, because to reach a state of 3//3 = 1 full trucks placed and being 3%3 = 0 spaces along for a new truck, the optimal is
TTT
..X#

The entry at index 3 of the last row looks at the above two cells as options — do we take the case where we are 2 spaces along for a new truck and finish it off, or do we take the case where we have a full truck already finished?
  TTT            TTT
..XX.     vs     ..X#.

Clearly the latter is better, so we put down a 1.
Pyth, 70 bytes
JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ

Basically a port of the above code. Not very well golfed yet. Try it online
Expanded
Jmvdczd              J = map(eval, input().split(" "))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
>                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]=="#")
>%hT@J2Z                                                           (T+1)%J[2]>0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Now, if only Pyth had multiple assignment to >2 variables...


Python 2, 56 48 bytes

thanks to dingledooper for -8 bytes!

lambda s:0x420AF14A5F8266>>hash(s)%3317%890%57&1

Try it online!

All these answers do the same thing:

Convert the string into an unique integer.
Makes these integers smaller by repeated modulo operations.
These operations are bruteforced to make the numbers as small as possible while not mixing up the two classes.
Index into a binary lookup table.

Python 3, 59 58 bytes

lambda s:0x48A2D06199310566F06>>int(s[:4],36)%542%400%78&1

Try it online!

lambda s:0x453CCA1066840810431C1>>int(s,36)%2387%1770%86&1

Try it online!

lambda s:0x42744262AEA01A914800A12C>>int(s,36)%155687%95&1

Try it online!

05AB1E, 30 29 28 bytes

4öŽ3¹%Ƶ™%84%o•1±87÷Ðˆù³Í:•&Ā

Try it online!

6öŽ9{%521%76%o•B&¦¿³ʒв F6•&Ā

Try it online!


Shortest program whose concatenated program+output is a permutation of the 95 printable ASCII characters

GolfScript, 14 characters
{`),32>46-^}.~

Output:
 !"#$%&'(*+/015789:;<=?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]_abcdefghijklmnopqrstuvwxyz|


JavaScript (ES6), 133

Recursive function.

F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

Less golfed and not recursive

F=m=>{
  for(k=[];!k[m];) // use k to find a repeated state and exit the loop
  {
    k[m]=1
    console.log(m)
    // loop for swap and mark swap position in array f
    f=m.map((x,i)=>(
      y=m[i+1], // next element
      w=x-y,    // difference
      x%w==0&y%w==0 // if common divisor ...
        ?m[m[i+1]=x,i]=y // swap elements,mark with nonzero
        :0 // no swap, mark with 0
    ))
    m=m.filter((x,i)=>f[i-1]|f[i]) // remove elements not swapped
  }
  return m.length
}

Test

F=(m,k=[])=>(k[m]=m,f=m.map((x,i)=>x%(w=x-(y=m[i+1]))==0&y%w==0?m[m[i]=y,i+1]=x:0),k[m=m.filter((x,i)=>f[i-1]|f[i])]?m.length:F(m,k))

console.log=x=>O.textContent+=x+'\n'

;[[1,1],[1,2],[1,2,3],[4,6,8],[99,1,3],[4,5,2,4],[12,4,6,3],[9,6,10,18]
,[ 55, 218, 654, 703, 948, 960 ],[ 954, 973, 925, 913, 924, 996, 927, 981, 905 ]]
.forEach(t=>console.log(t+' -> '+F(t)))


ES6, 118 81 78 bytes

n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r

Someone's bound to tell me there's a shorter way of concatenating the numbers up to n.

Saved a cool 37 bytes by taking @edc65's idea and running it on steroids. (Save an extra byte by using '|' instead of && but that limits the result to 31 bits.)

Edit: Saved 3 further bytes again thanks to @edc65.


Perl, score 254 + 2 = 256

Here's a hex dump of one program:

00000000: 6c65 6e67 7468 2700 0102 0304 0506 0708  length'.........
00000010: 090a 0b0c 0d0e 0f10 1112 1314 1516 1718  ................
00000020: 191a 1b1c 1d1e 1f20 2123 2425 2628 292a  ....... !#$%&()*
00000030: 2b2c 2d2e 2f30 3132 3334 3536 3738 393a  +,-./0123456789:
00000040: 3b3c 3d3e 3f40 4142 4344 4546 4748 494a  ;<=>?@ABCDEFGHIJ
00000050: 4b4c 4d4e 4f50 5152 5354 5556 5758 595a  KLMNOPQRSTUVWXYZ
00000060: 5b5d 5e5f 6061 6263 6465 6667 6869 6a6b  []^_`abcdefghijk
00000070: 6c6d 6e6f 7071 7273 7475 7677 7879 7a7b  lmnopqrstuvwxyz{
00000080: 7c7d 7e7f 8081 8283 8485 8687 8889 8a8b  |}~.............
00000090: 8c8d 8e8f 9091 9293 9495 9697 9899 9a9b  ................
000000a0: 9c9d 9e9f a0a1 a2a3 a4a5 a6a7 a8a9 aaab  ................
000000b0: acad aeaf b0b1 b2b3 b4b5 b6b7 b8b9 babb  ................
000000c0: bcbd bebf c0c1 c2c3 c4c5 c6c7 c8c9 cacb  ................
000000d0: cccd cecf d0d1 d2d3 d4d5 d6d7 d8d9 dadb  ................
000000e0: dcdd dedf e0e1 e2e3 e4e5 e6e7 e8e9 eaeb  ................
000000f0: eced eeef f0f1 f2f3 f4f5 f6f7 f8f9 fafb  ................
00000100: fcfd feff 273d 3d32 3533 6f72 2078 2829  ....'==253or x()

and here's the other program:

"\\"

Perl isn't normally thought of a compiled language, but it is; it's first compiled to bytecode, and then the bytecode is executed. You can apply a filter on the bytecode (e.g. to dump it rather than running the program) using the -MO option. Both these programs compile into the following bytecode (disassembled using -MO=Terse):

LISTOP (0x564fcd99f020) leave [1]
    OP (0x564fcd99f148) enter
    COP (0x564fcd99f068) nextstate
    OP (0x564fcd99f100) null [5]

Explanation

Perl replaces all statements with no effect (such as string literals on their own) with a hardcoded "statement with no effect" statement in the resulting bytecode, so both programs compile to the same thing. In terms of character replacements, replacing most of the characters from program 1 with apostrophes will cause it to fail to compile (or replacing the apostrophes with 0). In program 2, replacing the any character with c will cause the program to fail to compile (as \c takes an argument).

As for character deletions, the first version of this answer predated the "radiation hardening rule" (that deleting any character must change the behaviour of the program). This updated, radiation-hardened version works via the use of a checksum; if deleting a character doesn't outright cause a syntax error, the code will compile into a call to the nonexistent function x. The Perl compiler doesn't optimize out the call in the case where it's made (and in general doesn't seem aware that the function doesn't exist), and thus the output is different. However, Perl's constant folder is capable of seeing that the un-mutated program is a single statement with no effect, and thus optimizes the whole thing down into a single statement like before.

I originally misread the question as counting only unique characters from one program, and tried to optimize for that. Clearly, program 2 needs to contain at least one character in order to generate the "statement with no effect" opcode, meaning that the best possible score in one program is 255. I haven't yet found a way to include a backslash in program 1 in such a way that the character immediately following it can't be replaced in such a way as to cause the program to break, but it wouldn't surprise me if it were possible (leading to a score of 255 + 1 = 256).


Match strings whose length is a fourth power

Perl / Java / PCRE / .NET, 39 bytes
Another Solution
This is, in my opinion, one of the most interesting problems on the site. I need to thank deadcode for bumping it back up to the top.

^((^|xx)(^|\3\4\4)(^|\4x{12})(^x|\1))*$

39 bytes, without any conditionals or assertions... sort of. The alternations, as they're being used (^|), are a type of conditional in a way, to select between "first iteration," and "not first iteration."
This regex can be seen to work here: http://regex101.com/r/qA5pK3/1
PCRE interprets the regex correctly, and it has also been tested in Perl up to n = 128, including n4-1, and n4+1.

Definitions
The general technique is the same as in the other solutions already posted: define a self-referencing expression which on each subsequent iteration matches a length equal to the next term of the forward difference function, Df, with an unlimited quantifier (*). A formal definition of the forward difference function:
\$D_f(n)=f(n+1)-f(n)\$
Additionally, higher order difference functions may also be defined:
\$D_f^2(n)=D_f(n+1)-D_f(n)\$
Or, more generally:
\$D_f^k(n)=D_f^{k-1}(n+1)-D_f^{k-1}(n)=\sum\limits_{i=0}^k{(-1)^i}{k\choose i}f(n+k-i)\$
The forward difference function has a lot of interesting properties; it is to sequences what the derivative is to continuous functions. For example, Df of an nth order polynomial will always be an n-1th order polynomial, and for any i, if Dfi = Dfi+1, then the function f is exponential, in much the same way that the derivative of ex is equal to itself. The simplest discrete function for which f = Df is 2n.

f(n) = n2
Before we examine the above solution, let's start with something a bit easier: a regex which matches strings whose lengths are a perfect square. Examining the forward difference function:
\$D_f=[1,3,5,7,9,\dots]=2n+1\$
Meaning, the first iteration should match a string of length 1, the second a string of length 3, the third a string of length 5, etc., and in general, each iteration should match a string two longer than the previous. The corresponding regex follows almost directly from this statement:
^(^x|\1xx)*$

It can be seen that the first iteration will match only one x, and each subsequent iteration will match a string two longer than the previous, exactly as specified. This also implies an amazingly short perfect square test in perl:
(1x$_)=~/^(^1|11\1)*$/

This regex can be further generalized to match any n-gonal length:
Triangular numbers:
^(^x|\1x{1})*$
Square numbers:
^(^x|\1x{2})*$
Pentagonal numbers:
^(^x|\1x{3})*$
Hexagonal numbers:
^(^x|\1x{4})*$
etc.

f(n) = n3
Moving on to n3, once again examining the forward difference function:
\$D_f=[1,7,19,37,61,\dots]=3n^2+3n+1\$
It might not be immediately apparent how to implement this, so we examine the second difference function as well:
\$D_f^2=[6,12,18,24,30,\dots]=6n+6\$
So, the forwards difference function does not increase by a constant, but rather a linear value. It's nice that the initial ('-1th') value of Df2 is zero, which saves an initialization on the second iteration. The resulting regex is the following:
^((^|\2x{6})(^x|\1))*$

The first iteration will match 1, as before, the second will match a string 6 longer (7), the third will match a string 12 longer (19), etc.

f(n) = n4
The forward difference function for n4:
\$D_f=[1,15,65,175,369,\dots]=4n^3-6n^2+4n-1\$
The second forward difference function:
\$D_f^2=[14,50,110,194,302,\dots]=12n^2-24n+14\$
The third forward difference function:
\$D_f^3=[36,60,84,108,132,\dots]=24n+36\$
Now that's ugly. The initial values for Df2 and Df3 are both non-zero, 2 and 12 respectively, which will need to be accounted for. You've probably figured out by now that the regex will follow this pattern:
^((^|\2\3{b})(^|\3x{a})(^x|\1))*$

Because the Df3 must match a length of 12 on the second iteration, a is necessarily 12. But because it increases by 24 each term, the next deeper nesting must use its previous value twice, implying b = 2. The final thing to do is initialize the Df2. Because Df2 influences Df directly, which is ultimately what we want to match, its value can be initialized by inserting the appropriate atom directly into the regex, in this case (^|xx). The final regex then becomes:
^((^|xx)(^|\3\4{2})(^|\4x{12})(^x|\1))*$

Higher Orders
A fifth order polynomial can be matched in with the following regex:
^((^|\2\3{c})(^|\3\4{b})(^|\4x{a})(^x|\1))*$
f(n) = n5 is a fairly easy excercise, as the initial values for both the second and fourth forward difference functions are zero:
^((^|\2\3)(^|\3\4{4})(^|\4x{30})(^x|\1))*$

For six order polynomials:
^((^|\2\3{d})(^|\3\4{c})(^|\4\5{b})(^|\5x{a})(^x|\1))*$
For seventh order polynomials:
^((^|\2\3{e})(^|\3\4{d})(^|\4\5{c})(^|\5\6{b})(^|\6x{a})(^x|\1))*$
etc.
Note that not all polynomials can be matched in exactly this way, if any of the necessary coefficients are non-integer. For example, n6 requires that a = 60, b = 8, and c = 3/2. This can be worked around, in this instance:
^((^|xx)(^|\3\6\7{2})(^|\4\5)(^|\5\6{2})(^|\6\7{6})(^|\7x{60})(^x|\1))*$

Here I've changed b to 6, and c to 2, which have the same product as the above stated values. It's important that the product doesn't change, as a·b·c·… controls the constant difference function, which for a sixth order polynomial is Df6. There are two initialization atoms present: one to initialize Df to 2, as with n4, and the other to initialize the fifth difference function to 360, while at the same time adding in the missing two from b.


Mathematica, 117 bytes

For[t=1,t<=#,t+=Length[Join@@(#~WordData~"Hyphenation"&/@StringSplit[Echo@t~IntegerName~"Words",{"‐",", "," "}])]]&

Pure function taking a nonnegative integer as input; it echoes the appropriate integers to the standard output one at a time.

There might well be a shorter implementation in Mathematica, but this is the lazy one  :)  t~IntegerName~"Words" gives the English name of the integer t; then StringSplit[...,{"‐",", "," "}] divides this name into a list of individual words. (Mathematically annoyingly uses the 3-byte character ‐ (U+2010) for the hyphen in names of integers.) #~WordData~"Hyphenation"&/@ splits each of those words into a list of its syllables, and Length[Join@@(...)] counts these syllables.

Thus the function, after initializing t=1, loops as long as t doesn't exceed the input; each time, it prints t and then augments it by the number of syllables in the English name of t. In principle, this algorithm works up to 1036–1, at which point the hyphenation dictionary doesn't have an entry for "undecillion".


05AB1E, 6 bytes

Code

Â‚D¿÷P

Uses the 05AB1E encoding. Try it online!

Explanation

Â‚        # Get the array [input, reversed(input)]
  D       # Duplicate that array
   ¿      # Calculate the GCD of the array
    ÷     # Divide each element in the array by the GCD
     P    # Product of that array


Five aligned points and some of the pairwise distances. Infer the relative positions!

R

prop <- function(num_points, first_distances, last_distances)
{
    last_point = max(last_distances)
    proposal = c(0, sort(sample(1:(last_point-1), num_points-2)), last_point)
    d = sort(dist(proposal))
    num_first_distances = length(first_distances)
    num_last_distances = length(last_distances)
    num_distances = length(d)
    if(all(d[1:num_first_distances]==first_distances)&&all(d[(num_distances-num_last_distances+1):num_distances]==last_distances))
    {
        print(proposal)
        return(TRUE)
    }
    else return(FALSE)
}

while(TRUE)
{
    if(prop(5, c(1,2,4), c(14,18,20))) break()
}

Here is the source of the problem and an algorithm with R which I used for inspiration.


Expand shorthand increasing integer sequences

Jelly, 7 bytes

DUṛ"\UḌ

Try it online! or verify all test cases.

How it works

DUṛ"\UḌ  Main link. Input: A (list of integers)

D        Convert each integer to a list of its base 10 digits.
 U       Reverse each digit list.
    \    Do a cumulative reduce, applying the dyadic link to the left:
   "       For each pair of corresponding digits:
  ṛ          Select the right one.
           Vectorization leaves digits that do not have a counterpart untouched.
     U   Reverse the resulting digit arrays.
      Ḍ  Convert from base 10 to integer.


MATL, 10 bytes
yt&y)>fYk)

This uses 1-based indexing. Try it online!
Explanation
Consider inputs [4,-2,1,-3,5], 3 as an example.
y     % Take two inputs implicitly. Duplicate 2nd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5]
t     % Duplicate top of the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5]
&y    % Duplicate 3rd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5], 3
)     % Index: select elements from first input as indicated by second input
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], 1
>     % Greater than, element-wise
      % STACK: [4,-2,1,-3,5], 3, [1,0,0,0,1]
f     % Find: gives indices of non-zero entries
      % STACK: [4,-2,1,-3,5], 3, [1,5]
Yk    % Closest element: gives closest element of each entry in second input
      % ([1,5]) to each entry in the first input (3). In case of a tie it
      % gives the left-most one
      % STACK: [4,-2,1,-3,5], 1
)     % Index: select elements from first input as indicated by second input
      % STACK: 4
      % Implicitly display


Octave, 29 bytes

@(n)accumarray((x=1:n)'+!x,1)

Try it online!


Jelly, 6 bytes

BḄ-8ƤṀ

A monadic link taking a number and returning a number.

Try it online!

How?

Uses a nice quick, Ƥ, developed by miles...

BḄ-8ƤṀ - Link: number
B      - convert to a binary list
    Ƥ  - for loop over some slices to be determined...
  -8   - this is a negative nilad, therefore: use overlapping outfixes of length 8
       -   (exactly what the specification asks us to inspect)
 Ḅ     -   convert from a binary list to an integer (vectorises)
     Ṁ - maximum


C, 402 bytes

Plenty of room for golfing, just proof of concept to begin with :P

Compiles under clang, osx.

Note: For linux you may have to change the code to use something like: "ld -shared f.o -o f.so -lm"

#include<dlfcn.h>
#include<stdio.h>
float e,r;
main(int i,char**v){
    // create and compile temporary c file for 'f(x)'
    // note: include offset within function
    FILE*s=fopen("f.c","w");
    fprintf(s,"#include<math.h>\nfloat f(float x){x+=%s;return %s;}",v[2],v[1]);
    fclose(s);
    system("cc -fPIC -c f.c;ld -bundle f.o -o f.so -lm");
    float(*f)(float)=dlsym(dlopen("f.so",0),"f");

    for(i=0;1;e=(e==0)?1e-37:e*2){
        r=f(e);
        if(isinf(r))i=1;else if(!isnan(r)){
            i?printf("%cINF\n",r>0?43:45):printf("%f\n",r);
            break;
        }
    }
}

Run as:

./a.out "sin(x)/x" 0
./a.out "1/(x*x)" 0
./a.out "(x*x-x)/(x-1)" 1
./a.out "pow(2,x)" 3

Results:

1.000000
+INF
1.000000
8.000000