title: Self-compiling compiler

text:
# Question
Title: Self-compiling compiler
This is based on a talk on compilers I listened to a while back, but I, unfortunately, can't remember when or where.

Create the shortest compiler in any language that can compile itself. Target any reasonable ISA (68K, x86, MIPS, ARM, SPARC, IBM BAL, etc.) that doesn't have a "compile-program" instruction (this may exclude some versions of VAX). Read source programs from `stdin` and print generated code to `stdout`. You may use the standard C library for I/O and string processing (e.g., `_printf`). You don't need to compile the whole language, *just any subset that contains the compiler (i.e., just printing an assembly language quine, while impressive, does not count as a solution.)*

# Answer
> 33 votes
## 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"

```

# Answer
> 16 votes
# Custom Language → C - (7979)

Since the question doesn't preclude creating my own language, I thought I'd give that a try.

## The Environment

The language has access to two stacks, The Call Stack, and The Data Stack. The Call Stack is used for the jumping instructions `{` and `}`, while The Data Stack is used by most other instructions. The Call Stack is opaque to applications.

The Data Stack can hold three different types of values: integer, text, and empty. Integers are of type intptr\_t, while text is stored as C-style strings.

The `^` instruction has access to The Array. The Array is a constant array of length 17 of text items. You should probably see the source for the indexing scheme since it's a little wonky.

## The Language

```
#   -   Begin number    - Marks the beginning of a number, for example: #42.
.   -   End number      - Marks the end of a number and pushes it to the data stack.
^   -   Translate       - Pops a number, and pushes the corresponding text from The Array.
<   -   Write           - Pops a value, and prints it to stdout.
>   -   Read            - Reads a character from stdin and pushes it as a number. If EOF,
                          exit.
{   -   Start Loop      - Pushes the current location in the program to the call stack.
}   -   End Loop        - Go to the position specified by the top of the call stack.
+   -   Add             - Pop two numbers from the data stack, add them, push the result.
-   -   Subtract        - Pop into A, pop into B, push B - A. Both B & A must be numbers.
!   -   Duplicate       - Pop from The Data Stack, push that value twice.
_   -   Discard         - Pop from The Data Stack.
=   -   Skip if Equal   - Pop two values, if they are equal skip the next instruction
                          and pop one item from the call stack.
?   -   Loop            - Pop one number, subtract one, if it's less than one, pop one
                          item from the call stack and skip the next instruction.
@   -   Array Separator - Marks the end of an array item.
$   -   Program End     - Marks the end of the program.

```

## The Compiler

This is the compiler. It isn't golfed, and I expect it could be cut down considerably. It should be possible to use machine code directly and output a dos COM file, but I haven't gotten around to that yet. I know this looks like a C program, but the actual compiler implementation is down at the end.

Currently the compiler generates a lot of debugging information on stderr.

```
#include <string.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <setjmp.h>
#include <stdbool.h>

const char* position;
const char* array[] = {"@"};

void die(const char* reason)
{
    fprintf(stderr, "%s\n", reason);
    exit(1);
}

//
// Stack Functions
//

#define T_EMPTY     (0)
#define T_NUMBER    (1)
#define T_TEXT      (2)

typedef struct {
    unsigned char type;
    union {
        const char* text;
        intptr_t number;
    };
} stack_entry;

#define STACK_MAX   (1024)
stack_entry stack[STACK_MAX];
size_t stack_position = 0;

stack_entry* _push()
{
    if (stack_position >= STACK_MAX) {
        die("out of stack space");
    }
    return &stack[stack_position++];
}

void push(stack_entry v)
{
    if (v.type == T_EMPTY) {
        fprintf(stderr, "\tpushed: None\n");
    } else if (v.type == T_TEXT) {
        fprintf(stderr, "\tpushed: %s\n", v.text);
    } else {
        fprintf(stderr, "\tpushed: %d\n", v.number);
    }
    stack_entry* entry = _push();
    *entry = v;
}

void push_empty()
{
    fprintf(stderr, "\tpushed: None\n");
    stack_entry* entry = _push();
    entry->type = T_EMPTY;
    entry->number = 0;
}

void push_number(intptr_t number)
{
    fprintf(stderr, "\tpushed: %d\n", number);
    stack_entry* entry = _push();
    entry->type = T_NUMBER;
    entry->number = number;
}

void push_text(const char* text)
{
    fprintf(stderr, "\tpushed: %s\n", text);
    stack_entry* entry = _push();
    entry->type = T_TEXT;
    entry->text = text;
}

// Polymorphic Push (for literals)
#define PUSH0()     do { fprintf(stderr, "literal:\n"); push_empty(); } while (0)
#define PUSH1(a)    do { fprintf(stderr, "literal:\n"); push_number(a); } while (0)

#define GET_MACRO(_0, _1, NAME, ...) NAME
#define PUSH(...) GET_MACRO(_0, ##__VA_ARGS__, PUSH1, PUSH0)(__VA_ARGS__)

stack_entry pop()
{
    if (stack_position <= 0) {
        fprintf(stderr, "\tpopped: None\n");
        return (stack_entry) {.type = T_EMPTY, .number = 0};
    }

    stack_entry v = stack[--stack_position];
    if (v.type == T_EMPTY) {
        fprintf(stderr, "\tpopped: None\n");
    } else if (v.type == T_TEXT) {
        fprintf(stderr, "\tpopped: %s\n", v.text);
    } else {
        fprintf(stderr, "\tpopped: %d\n", v.number);
    }
    return v;
}

stack_entry peek()
{
    if (stack_position <= 0) {
        return (stack_entry) {.type = T_EMPTY, .number = 0};
    }

    return stack[stack_position-1];
}

//
// Jump Functions
//

#define JUMP_MAX    (1024)
jmp_buf jump[JUMP_MAX];
size_t jump_position = 0;

#define start()                                     \
    do {                                            \
    if (jump_position >= JUMP_MAX) {                \
        die("out of jump space");                   \
    }                                               \
    fprintf(stderr, "start: %d\n", jump_position);  \
    setjmp(jump[jump_position++]);                  \
    } while (0)

void pop_jump() {
    if (jump_position <= 0) {
        die("empty jump stack");
    }
    jump_position -= 1;
}

#define end()                                       \
    do {                                            \
    if (jump_position <= 0) {                       \
        die("empty jump stack");                    \
    }                                               \
    fprintf(stderr, "end: %d\n", jump_position-1);  \
    longjmp(jump[jump_position-1],1);               \
    } while (0)

//
// Program functions
//

void translate()
{
    fprintf(stderr, "translate:\n");
    stack_entry entry = pop();
    if (entry.type == T_TEXT) {
        die("translating text");
    } else if (entry.type == T_EMPTY) {
        push_empty();
    } else {
        switch (entry.number) {
            case 0:
            case 1:
                push_text(array[entry.number]);
                break;
            case 64:
                push_text(array[2]);
                break;
            case 94:
                push_text(array[3]);
                break;
            case 45:
                push_text(array[4]);
                break;
            case 43:
                push_text(array[5]);
                break;
            case 62:
                push_text(array[6]);
                break;
            case 60:
                push_text(array[7]);
                break;
            case 33:
                push_text(array[8]);
                break;
            case 95:
                push_text(array[9]);
                break;
            case 61:
                push_text(array[10]);
                break;
            case 63:
                push_text(array[11]);
                break;
            case 123:
                push_text(array[12]);
                break;
            case 125:
                push_text(array[13]);
                break;
            case 35:
                push_text(array[14]);
                break;
            case 46:
                push_text(array[15]);
                break;
            case 36:
                push_text(array[16]);
                break;
            default:
                push_empty();
                break;
        }
    }
}

void subtract()
{
    fprintf(stderr, "subtract:\n");
    stack_entry v1 = pop();
    stack_entry v2 = pop();

    if (v1.type != T_NUMBER || v2.type != T_NUMBER) {
        die("not a number");
    }

    push_number(v2.number - v1.number);
}

void add()
{
    fprintf(stderr, "add:\n");
    stack_entry v1 = pop();
    stack_entry v2 = pop();

    if (v1.type != T_NUMBER || v2.type != T_NUMBER) {
        die("not a number");
    }

    push_number(v2.number + v1.number);
}

void read()
{
    fprintf(stderr, "read:\n");
    int in = getchar();

    if (in >= 0) {
        push_number(in);
    } else {
        die("end of input");
    }
}

void write()
{
    fprintf(stderr, "write:\n");
    stack_entry v = pop();

    if (v.type == T_NUMBER) {
        putchar(v.number);
    } else if (v.type == T_TEXT) {
        const char* x = v.text;
        char y;
        while (0 != (y=*(x++))) {
            y -= 128;
            putchar(y);
        }
    }
}

void duplicate()
{
    fprintf(stderr, "duplicate:\n");
    stack_entry v = pop();
    push(v);
    push(v);
}

void discard()
{
    fprintf(stderr, "discard:\n");
    pop();
}

bool equals()
{
    fprintf(stderr, "equals:\n");
    stack_entry x = pop();
    stack_entry y = pop();

    bool skip;

    if (x.type != y.type) {
        skip = false;
    } else if (x.type == T_EMPTY) {
        skip = true;
    } else if (x.type == T_NUMBER) {
        skip = x.number == y.number;
    } else {
        skip = strcmp(x.text, y.text) == 0;
    }

    if (skip) {
        pop_jump();
    }

    return !skip;
}

bool question()
{
    fprintf(stderr, "question:\n");
    stack_entry x = pop();

    intptr_t value;

    if (x.type == T_EMPTY) {
        value = 0;
    } else if (x.type == T_NUMBER) {
        value = x.number;
    } else {
        die("it is bad form to question text");
    }

    value -= 1;

    if (value < 1) {
        pop_jump();
        return false;
    } else {
        push_number(value);
        return true;
    }
}

int main()
{
@","@translate();@subtract();@add();@read();@write();@duplicate();@discard();@if(equals())@if(question())@start();@end();@PUSH(@);@return 0;}@

#0.^<                           Emit the preface

#17.{                           Loop for as many array slots exist
    #.{<>#128.+!#192.=}         Copy characters, adding 128 until reaching an at sign
    #128.-
    ^<                          Emit the code between array items
?}                              Return to start

#1.^<                           Emit the prologue

{{
>!^<                            Read character, translate it, and print it
!#35.=}                         Check if we have a literal
#.{<>!#46.=}^<                  If so, verbatim copy characters until a period
}                               Continue executing
$

```

To compile the generated C code:

```
gcc -finput-charset=CP437 -fexec-charset=CP437 -std=gnu11

```

The charset is required because the compiler escapes special characters by adding 128.

## The Bootstrap

To compile the first compiler, I wrote a python interpreter for the language.

```
import sys
from collections import defaultdict
KEYS = [0,1] + map(ord, ['@','^','-','+','>','<','!','_','=','?','{','}','#','.','$'])

# Read the source file
with file(sys.argv[1]) as f:
    data = f.read()
pos = 0

# Initialize the environment
array = defaultdict(str)
jmp = []
stk = []

def log(x):
    sys.stderr.write(x + '\n')

def read():
    global pos,data
    pos += 1
    return data[pos-1]

def pop():
    global stk
    try:
        x = stk.pop()
    except IndexError:
        x = None
    log('\tpopped ' + repr(x))
    return x

def push(value):
    global stk
    log('\tpushing ' + repr(value))
    stk.append(value)

# Read the array initialization section
for key in KEYS:
    while True:
        c = read()
        if c == '@':
            break
        array[key] += c

# Execute the program
while pos < len(data):
    c = read()
    if c == '^':
        log('translate:')
        push(array.get(pop(), None))
    elif c == '-':
        log('subtract:')
        x = pop()
        y = pop()
        push(y - x)
    elif c == '+':
        log('add:')
        x = pop()
        y = pop()
        push(y + x)
    elif c == '>':
        log('read:')
        push(ord(sys.stdin.read(1)))
    elif c == '<':
        log('write:')
        v = pop()
        if isinstance(v, int):
            sys.stdout.write(chr(v))
        elif v is not None:
            sys.stdout.write(v)
    elif c == '!':
        log('duplicate:')
        x = pop()
        push(x)
        push(x)
    elif c == '_':
        log('discard:')
        pop()
    elif c == '=':
        log('skip if equal:')
        x,y = pop(),pop()
        if x == y:
            pos += 1
            jmp.pop()
    elif c == '?':
        log('loop:')
        x = pop()
        x -= 1
        if x < 1:
            pos += 1
            jmp.pop()
        else:
            push(x)
    elif c == '{':
        log('start: ' + repr(pos))
        jmp.append(pos)
    elif c == '}':
        log('end:')
        pos = jmp[-1]
    elif c == '#':
        literal = ''
        while True:
            c = read()
            if c == '.':
                log('literal: ' + repr(literal))
                if literal == '':
                    push(None)
                else:
                    push(int(literal))
                break
            else:
                literal += c

```

## Putting It All Together

Assuming you've saved the compiler as `compiler.cmp` and the bootstrap as `bootstrap.py`, here's how to build the compiler, and then use it to compile itself:

```
$ cat compiler.cmp |
  python bootstrap.py compiler.cmp 2> trace-bootstrap |
  gcc -finput-charset=CP437 -fexec-charset=CP437 -std=gnu11 -o result -xc -
$ cat compiler.cmp | ./result 2> trace-final

```

So I'm not much of a C programmer, nor am I much of a language designer, so any suggestions on improving this are quite welcome!

## Example Programs

### Hello, World!

```
Hello, World!@@@@@@@@@@@@@@@@@#0.^<$

```

# Answer
> 15 votes
# Extended Brainfuck v0.9: 618 bytes (not counting the uneccesary linefeeds)

```
:c:n:z:g:i:t:w:a:p++++++++[->++++++++<]>[->>>>>>>[>>>>>>>>]+[<<<<<<<<]>]>>>>>>>[->>>>>>>>]@i
$i,[[-$t+$w+$i]$t[-$i+$t]+$a+++[-$w-----------$a]$w---[$a++[-$w-----------$a]$w[--[--[--[$i.
$t+++++++[-$w++++++++$t]$w[-]]$t[-$p[-]$i.$n,.[-<[<<]+[>>]<]@n$c[<<]>[-<<<+>>>>[>>]@z$p+$c[<
<]>]<<<[->>>+<<<]>>>>[->>]@z$t]$w]$t[-$i.$p+$t]$w]$t[-$i.$p-$t]$w]$t[$i.$n,.[-<[<<]+[>>]<]@n
$g[-$t+$c[<<]>+>[>>]@z>]$c[<<]>>[->>]@z$t[-$g+$t]$t]$w]$t[-$i.[-]$n,.[-<[<<]+[>>]<]@n$c[<<]>
[-<<<+>>>>[>>]@z$i+$a+$c[<<]>]<<<[->>>+<<<]>>>>[->>]@z<++++++[->++++++++++<]$w+$p[$a[-$w-]<[
@w-$p[-$z.$p]+$t]$w+$p-]$z++$w-$a[-$z.$a]$z[-]$i[-$p+$i]$t]$w$i,]

```

This is a golfed version of my very first version of EBF with removed support for comments and dead code to support removing of variables.

So basically it's BrainFuck with variables. `:x` creates variables x. The compiler knows where you are so `$y` will produce \<'s and \>'s to get to that position. Sometimes you need asymmetric loops and then you need to tell the compiler where you are with `@x`. As current EBF it compiles to Brainfuck.

This first version had only one char variable names, but I have used this version to compile the next version and so on until the current version that has an impressive feature set. When compiling from github source it actually downloads the handcompiled binary to bootstrap 6 intermediate ebf versions in order to create the current version.

To bootstrap it you may use this first and only binary in the EBF git repository which was compiled by hand successfully after a couple of tries.

```
wget -nv https://raw.githubusercontent.com/westerp/ebf-compiler/34c378c8347aafa5dbf37f4973461d42c8120ea4/ebf-handcompiled.bf
beef ebf-handcompiled.bf < ebf09.ebf > ebf09a.bf
beef ebf09a.bf < ebf09.ebf > ebf09b.bf
diff -s ebf09a.bf ebf09b.bf # Files ebf09a.bf and ebf09b.bf are identical

```

Brainfuck has a few hardware implementations, eg. this, this and this to mention a few. But mostly it's so easy to implement you can practically implement an interpreter on any system at all. I use to joke that Zozotez LISP, which is written in EBF, probably is the most portable LISP ever.

# Answer
> 8 votes
## Hex, 550 bytes

This specifically targets x86\_64 systems running Linux.

```
7f454c4602010100000000000000000002003e0001000000780040000000000040000000000000000000000000000000000000004000380001004000000000000100000005000000000000000000000000004000000000000000400000000000130100000000000013010000000000000000200000000000e81700000085c07c0b31ff01c7e879000000ebec31c089c7b03c0f05e84c0000004885c07c203c2178f2741b89c7e825000000c0e00450e83100000089c7e8150000005900c8c3e8210000003c0d7ff774ca3c0a75f1ebc489f831c93c400f9cc148ffc980e12780c13028c8c36a004889e631c089c2fec289c70f0531c985c0580f95c148ffc94809c8c3574889e631c0fec089c289c70f0558c3

```

In this language, source code consists of bytes represented as two lowercase hexadecimal digits, `[0-9a-f][0-9a-f]`. These bytes may have any amount of surrounding whitespace, but nothing may occur between the digits that form a single byte. Further, `'!'` is a line-comment character: it is ignored, as well as everything between it and the next `'\n'` character.

If you understand x86 assembly, here's a much more readable version of the source code:

```
! ELF Header !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
7f 45 4c 46                !e_ident[EI_MAG0] (0x7F "ELF")
02                         !e_ident[EI_CLASS] (64-bit)
01                         !e_ident[EI_DATA] (little-endian)
01                         !e_ident[EI_VERSION] (ELF v1)
00                         !e_ident[EI_OSABI] (System V ABI)
00                         !e_ident[EI_ABIVERSION] (version 0)
00 00 00 00 00 00 00       !e_ident [EI_PAD]
02 00                      !e_type (executable)
3e 00                      !e_machine (x86_64)
01 00 00 00                !e_version (ELF v1)
78 00 40 00 00 00 00 00    !e_entry (0x40078)
40 00 00 00 00 00 00 00    !e_phoff (0x   40)
00 00 00 00 00 00 00 00    !e_shoff (0x    0)
00 00 00 00                !e_flags
40 00                      !e_ehsize (ELF header size = 64 bytes)
38 00                      !e_phentsize (Program headers = 56 bytes)
01 00                      !e_phnum (1 program header)
40 00                      !e_shentsize (Section headers = 64 bytes)
00 00                      !e_shnum (no section headers)
00 00                      !e_shstrndx (section names, not useful here)

! Program Headers !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
01 00 00 00                !p_type (LOAD)
05 00 00 00                !p_flags (R+E)
00 00 00 00 00 00 00 00    !p_offset (file-loc 0)
00 00 40 00 00 00 00 00    !p_vaddr (vmem-loc 0x40000)
00 00 40 00 00 00 00 00    !p_paddr (pmem-loc 0x40000)
13 01 00 00 00 00 00 00    !p_filesz (length 0x113 bytes)
13 01 00 00 00 00 00 00    !p_memsz (allocate 0x113 bytes)
00 00 20 00 00 00 00 00    !p_align (align pages in 0x20000 increments)

! Program Code !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!! _start: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      e8 17 00 00 00 ! callq _gethx
               85 c0 ! test %eax,%eax
               7c 0b ! jl .+11
               31 ff ! xor %edi,%edi
               01 c7 ! add %eax,%eax
      e8 79 00 00 00 ! callq _putch
               eb ec ! jmp .-20
               31 c0 ! xor %eax,%eax
               89 c7 ! mov %eax,%edi
               b0 3c ! mov $0x3c,%al
               0f 05 ! syscall

!! _gethx: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      e8 4c 00 00 00 ! callq _getch
            48 85 c0 ! test %rax,%rax
               7c 20 ! jl _gethx+42
               3c 21 ! cmp $0x21,al
               78 f2 ! js _gethx
               74 1b ! je _gethx+43
               89 c7 ! mov %eax,%edi
      e8 25 00 00 00 ! callq _h2d
            c0 e0 04 ! sal $4,%al
                  50 ! push %rax
      e8 31 00 00 00 ! callq _getch
               89 c7 ! mov %eax,%edi
      e8 15 00 00 00 ! callq _h2d
                  59 ! pop %rcx
               00 c8 ! add %cl,%al
                  c3 ! retq
      e8 21 00 00 00 ! callq _getch
               3c 0d ! cmp $0xd,%al
               7f f7 ! jg _gethx+43
               74 ca ! je _gethx
               3c 0a ! cmp $0xa,%al
               75 f1 ! jne _gethx+43
               eb c4 ! jmp _gethx

!! _h2d: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
               89 f8 ! mov %edi,%eax
               31 c9 ! xor %ecx,%ecx
               3c 40 ! cmp $0x40,%al
            0f 9c c1 ! setl %cl
            48 ff c9 ! dec %rcx
            80 e1 27 ! and $0x27,%cl
            80 c1 30 ! add $0x30,%cl
               28 c8 ! sub %cl,%al
                  c3 ! retq

!! _getch: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
               6a 00 ! push $0
            48 89 e6 ! mov %rsp,%rsi
               31 c0 ! xor %eax,%eax
               89 c2 ! mov %eax,%edx
               fe c2 ! inc %dl
               89 c7 ! mov %eax,%edi
               0f 05 ! syscall
               31 c9 ! xor %ecx,%ecx
               85 c0 ! test %eax,%eax
                  58 ! pop %rax
            0f 95 c1 ! setne %cl
            48 ff c9 ! dec %rcx
            48 09 c8 ! or %rcx,%rax
                  c3 ! retq

!! _putch: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                  57 ! push %rdi
            48 89 e6 ! mov %rsp,%rsi
               31 c0 ! xor %eax,%eax
               fe c0 ! inc %al
               89 c2 ! mov %eax,%edx
               89 c7 ! mov %eax,%edi
               0f 05 ! syscall
                  58 ! pop %rax
                  c3 ! retq

```

If you extract the assembly language from the comments below `! Program Code`, you can assemble and run the Hex compiler. Input and output use stdin and stdout.

# Answer
> 2 votes
# 05AB1E, 2 bytes (possibly non-competing)

```
.V

```

Try it online!

Code on the first line of input, inputs on subsequent lines.

# Answer
> 1 votes
# Nil, 0 bytes

> Incredibly, despite not being Turing-complete, the Nil language is expressive enough to implement an interpreter for itself, much more concisely than many 'proper' languages can. The example presented here is a simple implementation, but using advanced compression techniques Nil developers have been able to produce working interpreters in as little as 0 lines of code.

# Answer
> -1 votes
## Lumber, 0 bytes

Lumber is a complete esoteric programming language invented by Unrelated String written in just 10 lines of Prolog code.

Can't believe it? These programs had comments removed and makes the interpreter source more concise.

lumber\_corefuncs.pl:

```
:- use_module(lumber_types).

```

lumber\_types.pl

```
:- module(lumber_types,
          []).

```

lumber\_corefuncs.pl takes in the library lumber\_types; and in turn, this library defines a module with nothing in it. Therefore, Lumber does nothing on arbitary inputs, which is in turn a self-compiler.

---
Tags: code-golf, compiler
---


# Question
Title: Return the nth element of an array even if its out of bound
# The challenge

Write a function that returns the `n`th element of an array even if its out of bound.

```
function safeGet(index, arr) {
  const safeIndex = ???
  return arr[safeIndex]
}

const arr = ["a", "b", "c"];

safeGet(0, arr) // "a"
safeGet(1, arr) // "b"
safeGet(2, arr) // "c"

safeGet(3, arr) // "a" go back to the beginning
safeGet(4, arr) // "b" all over again
safeGet(5, arr) // "c"

safeGet(30, arr) // "a"
safeGet(400, arr) // "b"
safeGet(5000, arr) // "c"

```

Negative indices works exactly the same way, but beginning from the end:

```
safeGet(-1, arr) // "c" begin from the end
safeGet(-2, arr) // "b"
safeGet(-3, arr) // "a"

safeGet(-4, arr) // "c" go back to the end again
safeGet(-20, arr) // "b"
safeGet(-300, arr) // "a"

```

Visually it looks like this:

```
// (For 1-element sized arrays, any natural number is a valid index)
//   2
//   1
//   0
// ["a"]
//  -1
//  -2
//  -3

//   6    7    8
//   3    4    5
//   0    1    2
// ["a", "b", "c"]
//  -3   -2   -1
//  -6   -5   -4
//  -9   -8   -7

//   6    7    8    9   10   11
//   0    1    2    3    4    5
// ["a", "b", "c", "d", "e", "f"]
//  -6   -5   -4   -3   -2   -1
// -12  -11  -10   -9   -8   -7

```

# Rules

* You can't **mutate** the array.
* You can't even **traverse** the array.
* Any programming languages will be accepted.
* It's a CodeGolf, meaning the smallest answer wins.

# Answer
> 5 votes
# Python, ~~22~~ 21 bytes

-1 byte thanks to ovs
This does not mutate the given array. Rather, it makes a n^2 larger copy of it. There's also no explicit iteration being done here.

```
lambda a,n:(n*n*a)[n]

```

TIO (updated test array)

# Answer
> 4 votes
# Stax, 1 bytes

```
@

```

Run and debug it

`@` is the array indexing instruction in stax. It works exactly as specified.

# Answer
> 2 votes
# Perl 6, 17 9 bytes

```
{*[$_%*]}

```

Explanation

```
{*[$_%*]}($idx)(@arr)     # curried input
*[$idx % *](@arr)         # $_ takes the $index
@arr[$idx % *]            # first * takes @array
@arr[$idx % @arr.elems]   # * in [] is number of elems

```

Try it online!

# Answer
> 2 votes
# Perl 6, 12 bytes

```
*[0]o&rotate

```

Try it online!

Works differently from guifa's answer in that it first rotates the array by the given amount, then takes the first element.

# Answer
> 1 votes
# Zsh, ~~27~~ 24 bytes

```
<<<${@[(`<&0`%#+#)%#+1]}

```

Turned out a bit more interesting than I thought. Takes array as arguments, index on stdin.

~~Try it online!~~ Try it online!

Arrays in zsh are one-indexed, and `$a[0]` is empty. Negative indexing works as expected for `-1, -2, ..., -n`.

New strategy: While negative indexing seems useful, the empty zero-index makes it less so. So, we just "mod n, add n, mod n" to make everything in the range \[0,n-1\], then add one.

---

Old strategy:

* take the index % length, leaving us something in the range \[-n+1,n-1\].
* if that is non-negative, add 1.

# Answer
> 1 votes
# C (gcc), ~~53~~ ~~32~~ 31 bytes

```
a(b,c,d)int*b;{b=b[(d%c+c)%c];}

```

Thanks to wastl for 31 bytes

Try it online!

# Answer
> 1 votes
# Charcoal, 1 byte

```
§

```

Try it online! This is Charcoal's `AtIndex` operator, but as a full program, it automatically accepts array and integer parameter inputs.

# Answer
> 1 votes
# Japt, 2 bytes

0-indexed. Input order is irrelevant.

```
gV

```

Try it

# Answer
> 0 votes
# Javascript, 28 bytes

```
a=>i=>a[(i<0?-i:i)%a.length]

```

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 28 bytes

```
a=>b=>b[(a%(a=b.Count)+a)%a]

```

Try it online!

# Answer
> 0 votes
# PHP, 53 bytes

```
function($i,$a){return$a[(($c=count($a))+$i%$c)%$c];}

```

Try it online!

* `$i` is the requested index.
* `$a` is the array.
* `$c` is count of array items.

PHP doesn't support negative array indexes to get items from the end (as you can actually have negative indexes in PHP arrays like this: `[-1 => 'X', -2 => 'Y']`).

So I'm always returning the array item at this position: `(($i % $c) + $c) % $c`

* The above formula for `$i=0` is always 0.
* For `$i>0` (positive index) it is same as `$i % $c`, since we add the `$c` to the result once and then get mod of it by `$c` again. For example, for `$c=3` and `$i=5` the resulting position will be 2.
* For `$i<0` (negative index) it will get the reversed position as a positive number (which is like getting the position from the end of the array). For example, for `$c=3` and `$i=-5` it will be `((-5%3)+3)%3 = (-2+3)%3 = 1%3 = 1`.

If we change `$i` from `-5` to `-6`, the resulting position should be reduced by 1, it will be `((-6%3)+3)%3 = (0+3)%3 = 3%3 = 0`

If we change `$i` from `-5` to `-4`, the resulting position should be added by 1, it will be `((-4%3)+3)%3 = (-1+3)%3 = 2%3 = 2`

---
Tags: code-golf, array
---


title: 43 quintillion permutations

text:
# Question
Title: 43 quintillion permutations
We can represent a Rubik's Cube as a net as follows (when solved):

```
   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

```

Each letter represents the corresponding colour (`W` is white, `G` green etc.)

It has been shown that there are exactly \\$43,252,003,274,489,856,000\\$ (~\\$43\\$ quintillion) different permutations that a Rubik's Cube can be in.

Your task is to take an integer between \\$1\\$ and \\$43,252,003,274,489,856,000\\$ and output the corresponding permutation, in the manner shown above. You may choose how the permutations are ordered, but the algorithm you use must be shown to generate a unique, and correct, permutation for each possible input.

**Invalid permutation rules**

Taken from this page

To start with, the centre of each 3x3 face must stay the same, as the centre square on a Rubik's Cube cannot be rotated. The entire cube can be rotated, changing where a face appears to be, but this doesn't affect the net of the cube.

If we say each permutation has a parity, based on the parity of the number of swaps to reach that permutation, we can say

* Each corner piece has three possible orientations. It can be oriented correctly (0), clockwise (1) or counterclockwise (2). The sum of corner orientations always remain divisible by 3
* Each legal rotation on the Rubik's Cube always flips an even number of edges so there can't be only one piece oriented wrong.
* Considering the permutation of all the corners and edges, the overall parity must be even which means that each legal move always performs the equivalent of an even number of swaps (ignoring orientation)

For example the following three net are invalid outputs:

```
   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
   YYY
   YYY
   YYB

(The yellow/orange/blue corner is rotated into an impossible permutation)

```

## Rules

* You must prove, however way you wish, that the algorithm is valid. You do not have to enumerate every single permutation, as long as you prove the validity of your algorithm.
* As long as your program will work *theoretically* for all integers between \\$1\\$ and \\$43,252,003,274,489,856,000\\$, you don't have to worry about the practicalities of actually taking in inputs greater than your language can handle
    + This means that, if your language/type/whatever can only handle numbers up to \\$2^{53}-1\\$, the *program* itself can fail if the input is greater than \\$2^{53}-1\\$, but the algorithm that you use should not.
    + For example, if your Javascript program fails for an input of \\$27,946,105,037,114,827,095\\$ purely because that number is out of bounds, that's fine. However, if your algorithm were ported to a language with arbitrary sized integers and failed for that input, your program would not be valid.
* You *must* include some sort of proof of validity in your answer. This proof can prove the validity in any accepted proof method, except for enumerating all possibilities.
* You may choose to use an alternate input method if you wish, so long as:
    + The input is bounded
    + Each input corresponds to a unique output
    + You clearly explain the input format and how it corresponds to each output
* You may change the characters used to use 6 different ASCII characters, between 33 (`!`) and 126 (`~`), instead of `WGRBOY`
* You may output in any manner you wish, so long as it forms a clear representation of a cube where all 6 faces are able to be shown, including any valid cube net, a single lined string or a 3D rendering. If you are unsure about a specific format, don't hesitate to ask in the comments.

This is a so the shortest code, in bytes, in each language wins.

## Example valid outputs

```
   YYY
   YYY
   YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   WWW
   WWW
   WWW

(The `W` and `Y` faces have been swapped)

   ZZZ
   +++
   +}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
   7bb
   [7Z
   [7Z

(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
 Then, the moves L, R, U and F' have been applied, in that order.
 Notice that each centre square is different, and corresponds to the same colour as in the mapping)

```

# Answer
> 13 votes
# Charcoal, ~~334~~ 297 bytes

```
Ｎθ≔×³﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘ε³¦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘η²¦²η≧÷²⁰⁴⁸θＦ⪪”B"↷:μêKＯ″ＫW#})”³«Ｊ⌕α§ι⁰Ｉ§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔Ｗ⊞≦≦⧴!O×➙⟧ï!Ｙ9⁺`↙1δQ1ξzＴ”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δＦ²«Ｆδ«≔§υ⎇⁼Ｌυ⊗ιωζδ≧÷Ｌυζ≧⁺⌕υδω≔Φυ¬⁼λδυＦＬκ«Ｊ⌕α§δ⊗⁺λεＩ§δ⊕⊗⁺λε§κλ»≧÷Ｌκε»≔⪪”A‽}R›Ｋ<≡^μ≡⟦σＤ⎚+πη±t¿e∧Ｌ⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input the integer into variable `q`.

```
≔×³﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘ε³¦³ε≧÷²¹⁸⁷θ

```

Divide `q` by 3⁷, putting the remainder in `e`. Then, considering `e` as a number in base 3, suffix a digit to `e` so that its digits (in base 3) add up to a multiple of 3. This allows `e` to define the rotations of the corners.

```
≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ

```

Divide `q` by 8!, putting the remainder in `z`. (8! is temporarily stored in `d` to save a byte.) This allows `z` to define the positions of the corners.

```
≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘η²¦²η≧÷²⁰⁴⁸θ

```

Divide `q` by 2¹¹, putting the remainder in `h`. Then, considering `h` as a number in base 2, suffix a digit to `h` so that its digits (in base 2) add up to a multiple of 2. This allows `h` to define the flips of the edges.

```
Ｆ⪪”B"↷:μêKＯ″ＫW#})”³

```

Loop over a string representation of the centres.

```
«Ｊ⌕α§ι⁰Ｉ§ι¹§ι²»

```

Jump to the position of each centre and print it.

```
≔⁰ω

```

Keep track of the parity of the corner positions in variable `w`.

```
≔⪪”A‽}y≔Ｗ⊞≦≦⧴!O×➙⟧ï!Ｙ9⁺`↙1δQ1ξzＴ”⁶υ

```

Create an array of corner positions.

```
≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δ

```

Create an array of corner colours.

```
Ｆ²«

```

Loop twice, once for corners, once for edges, hereinafter referred to as "cubes".

```
Ｆδ«

```

Loop over the array of cube colours.

```
≔§υ⎇⁼Ｌυ⊗ιωζδ≧÷Ｌυζ≧⁺⌕υδω≔Φυ¬⁼λδυ

```

Extract the next cube position from `z`, updating the parity in `w`. Use this parity for the last but one edge. This ensures that the sum of parity of the edges and corners is even.

```
ＦＬκ«Ｊ⌕α§δ⊗⁺λεＩ§δ⊕⊗⁺λε§κλ»

```

Print the cube at that position, adjusted for the next rotation or flip as appropriate.

```
≧÷Ｌκε»

```

Remove the rotation or flip from `e`.

```
≔⪪”A‽}R›Ｋ<≡^μ≡⟦σＤ⎚+πη±t¿e∧Ｌ⸿~↑�w”⁴υ

```

Create an array of edge positions. This will be used the second time through the loop.

```
≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ

```

Create an array of edge colours.

```
≔θζ≔ηε

```

Overwrite the corner variables `z` and `e` with the corresponding edge variables `q` and `h` so that the edges are permuted and flipped during the second pass of the loop.

# Answer
> 8 votes
# Ruby, ~~570~~ 408 bytes

```
->g,h{z=[]
c=a="\x19)!$'%\x177\x1F495.)@7g~yp"
20.times{|i|z<<a[k=g%r=12+i/12*8-i];a[k]="";g/=r}
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18,2])
h+=h+("%b"%(h%2048)).sum%2
j=0
b="023451"
20.times{|i|b<<("%0*o"%[r=2+i/12,z[i].ord-20]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s["<QTWZo;MP[ngD@RS^k=GVUpaJ8XYdsAFE?CN7LK9IHl_`jh]reftbc"[i].ord-55]=b[i]}
s}

```

Try it online!

**Original version, with arrays of magic numbers instead of magic strings**

```
->g,h{z=[]
a=[05,025,015,020,023,021,03,043,013,040,045,041,   032,025,054,043,0123,0152,0145,0134]
#PERMUTE
20.times{|i|r=12+i/12*8-i;z<<a.delete_at(g%r);g/=r}
c=1
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18],z[19])
#ROTATE
h+=h+(h%2048).to_s(2).sum%2
j=0
b="023451"
20.times{|i|r=2+i/12;b<<("%0*o"%[r,z[i]]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
#DISPLAY
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s[
[5,26,29,32,35,56,
4,22,25,36,55,48,
13,9,27,28,39,52,
6,16,31,30,57,42,
19,1,33,34,45,60,
10,15,14,8,12,23,0,21,20,2,18,17,
53,40,41,51,49,38,59,46,47,61,43,44][i]]=b[i]}
s}

```

Try it online!

An anonymous function which in its current form takes an input of two integers, which seems to be allowed: "you may choose an alternate input method." The first is the permutation in the range 0 to `12!*8!/2 - 1` and the second is the orientation of the pieces in the range 0 to `2**11 * 3*7 - 1`. The output in the solved state is the following string:

```
000
000
000
222333444555
222333444555
222333444555
111
111
111

```

**Further golfing**

There are approximately 10 more characters to be saved by adjusting the output format to the following shape. But this would reduce the readability, so I will not be doing it at present

```
      #########
      #########
      #########
#########
#########
#########

```

**Explanation**

**Permutation**

Internally, the solved state is represented by the series of octal numbers in the array `a`. The input `g` is divided by the numbers `12..1` with the modulus being used to pick and remove an edge from `a` and place it in `z`. Once this is done, only the corners remain in `a`, so `g` is divided by the numbers `8..1` with the modulus being used to remove a corner from `a` and place it in `z`.

As there is insufficient info to determine the order of the last two corners, the value of `g` will have been divided down to zero by the time it reaches them, so they will always be added to `z` in there original order. A check is then made to determine if the overall permutation is even or odd, and if necessary the last two corners are swapped to make the permutation even.

**Orientation**

There are various different ways of deciding if a corner or edge is in the correct orientation if it is not in its solved location. For the purpose of this answer, a corner is considered in its correct orientation if it shows `0` or `1` on the top or bottom face. Therefore rotating the top or bottom face does not change the corner orientation. Rotating the other faces does change the orientation, but in such a way that the overall parity sum remains unchanged. The edges are considered in the correct orientation if they show a `2` or `4` to the front / back or a `3` or `5` to the left / right. This means that rotation of the top or bottom by a quarter turn flips the four edges but rotation of the other faces leaves the flip status unchanged.

The input contains explicit information for all but the first edge and the last corner. The 11 least significant bits `h%2048` are summed and the modulus used to determine the orientation of the first edge. `h` is multiplied by 2 by adding it to itself and the value for the orientation of the first edge is added as the least significant bit. The orientation of the last corner is found by progressively subtracting the orientation of the other corners from `j`. For the very last corner (where `i/19` = `1`) the value of `j%3` is added to `h` (which will have been reduced to zero) and this determines the orientation of the last corner.

The string `b` comes preinitialized with the text for the centres of the faces. `h` is divided by `2` twelve times then by `3` eight times, with the modulos being used to determine the orientation of the pieces. In each case, the number in `z` is converted to a string with the appropriate number of digits (2 or 3) and the string is then duplicated. This allows the correct rotation of the digits as found by the modulo to be extracted from the string by indexing and appended to `b`

**Display**

Finally, the raw stickers are copied from `b` into a more human readable format in `s` using the magic numbers in the index table.

---
Tags: code-golf, rubiks-cube
---


title: ASCII Maze Rendering 3000

text:
# Question
Title: ASCII Maze Rendering 3000
I don't like typing, so I draw my mazes in a very simple format:

```
# #####
#     #
# ### #
# # # #
#   # #
##### #

```

Isn't it a-*maze*-ing? Of course, I think all mazes should look 3d, similar but not he same as this challenge, for maximum a-*maze*-ingness, so I (grudgingly) manually updated the maze to look like this:

```
+-----+     +-----------------------------+
|\     \    |\                             \
+ \     \   + \                             \
 \ \     \   \ +-----------------------+     \
  \ \     \   \|                       |\     \
   \ \     \   +-----------------------+ \     \
    \ \     \     +-----------------+   \ \     \
     \ \     \    |\                 \   \ \     \
      \ \     \   + \                 \   \ \     \
       \ \     \   \ \     +-----+     \   \ \     \
        \ \     \   \ \     \    |\     \   \ \     \
         \ \     \   \ \     \---+ \     \   \ \     \
          \ \     \   \ +-----+   \ \     \   \ \     \
           \ \     \   \|     |    \ \     \   \ \     \
            \ \     \   +-----+     \ \     \   \ \     \
             \ \     +-----------------+     \   \ \     \
              \ \                             \   \ \     \
               \ \                             \   \ \     \
                \ +-----------------------------+   \ +-----+
                 \|                             |    \|     |
                  +-----------------------------+     +-----+

```

Unfortunately, it's difficult to work with mazes in that format, and after all that manual typing, I don't want to just retype the original, so I need you to write a program to do the reversal for me.

## Rules

* Input will be a multiline string or character matrix consisting only of `" "`, `"|"`, `"\"`, `"+"`, `"-"`, and newlines.
* Output consists of `" "` and `"#"`, in the pattern described by the maze.
* Due to my amazing maze designing skills, you can assume nothing about the structure of the maze, other than that is has a valid deconstruction.
* In the 3d-ification, (the process you must now undo,) each `#` was converted to this 3x4x7 character block:
```
+-----+
|\     \
+ \     \
 \ +-----+
  \|     |
   +-----+

```
* Adjacent blocks were joined together, like this:
```
+-----+-----+
|\     \     \
+ \     \     \
 \ +-----+-----+
  \|\     \     \
   + \     \     \
    \ +-----+-----+
     \|     |     |
      +-----+-----+

```
but without joining lines, so it actually looks like this:
```
+-----------+
|\           \
+ \           \
 \ \           \
  \ \           \
   \ \           \
    \ +-----------+
     \|           |
      +-----------+

```
* Concave spaces sometimes block parts of other walls.
```
+-----------+
|\           \
+ \           \
 \ \     +-----+
  \ \     \    |
   \ \     \---+
    \ +-----+
     \|     |
      +-----+

```
* Trailing whitespace in the input or output is acceptable. (You must specify if your answer *requires* trailing whitespace in the input.)
* Leading whitespace must correspond to empty spaces in the input.
* I still don't like typing, so shortest code wins

### Test cases:

```
Input:
+-----+     +-----------------------------+
|\     \    |\                             \
+ \     \   + \                             \
 \ \     \   \ +-----------------------+     \
  \ \     \   \|                       |\     \
   \ \     \   +-----------------------+ \     \
    \ \     \     +-----------------+   \ \     \
     \ \     \    |\                 \   \ \     \
      \ \     \   + \                 \   \ \     \
       \ \     \   \ \     +-----+     \   \ \     \
        \ \     \   \ \     \    |\     \   \ \     \
         \ \     \   \ \     \---+ \     \   \ \     \
          \ \     \   \ +-----+   \ \     \   \ \     \
           \ \     \   \|     |    \ \     \   \ \     \
            \ \     \   +-----+     \ \     \   \ \     \
             \ \     +-----------------+     \   \ \     \
              \ \                             \   \ \     \
               \ \                             \   \ \     \
                \ +-----------------------------+   \ +-----+
                 \|                             |    \|     |
                  +-----------------------------+     +-----+

Output:
# #####
#     #
# ### #
# # # #
#   # #
##### #

Input:
+-----+
|\     \
+ \     \
 \ +-----+
  \|     |
   +-----+

Output:
#

Input:
      +-----------------+
      |\                 \
      + \                 \
   +-----+     +-----+     +-----+
   |\           \    |\           \
   + \           \---+ \           \
    \ \     +-----+   \ +-----+     \
     \ \     \    |    \|     |\     \
      \ \     \---+     +-----+ \     \
       \ \     +-----+     +-----+     \
        \ \           \    |\           \
         \ \           \   + \           \
          \ +-----+     +-----+     +-----+
           \|     |\                 \    |
            +-----+ \                 \---+
                   \ +-----------------+
                    \|                 |
                     +-----------------+

Output:
 ###
## ##
#   #
## ##
 ###

Input:
+-----------------------------------------------------------------------------------------------------+
|\                                                                                \
+ \                                                                                \
 \ +-----------------------------------------------+     +-----------------------------------------+     \
  \|                                               |\     \                                        |\     \
   +-----------------------------------------------+ \     \---------------------------------------+ \     \
      +-----+     +-----------------------------+   \ \     \     +-----------------------------+   \ \     \
      |\     \    |\                             \   \ \     \    |\                             \   \ \     \
      + \     \   + \                             \   \ \     \   + \                             \   \ \     \
       \ \     \   \ +-----------+     +-----+     \   \ \     \   \ +-----------------------+     \   \ \     \
        \ \     \   \|           |\     \    |\     \   \ \     \   \|                       |\     \   \ \     \
         \ \     \   +-----------+ \     \---+ \     \   \ \     \   +-----------------------+ \     \   \ \     \
          \ \     \     +-----+   \ \     \   \ \     \   \ \     +-----------------------+   \ \     \   \ \     \
           \ \     \    |\     \   \ \     \   \ \     \   \ \                             \   \ \     \   \ \     \
            \ \     \   + \     \   \ \     \   \ \     \   \ \                             \   \ \     \   \ \     \
             \ \     \   \ +-----+   \ \     \   \ \     \   \ +-----------------------------+   \ \     \   \ \     \
              \ \     \   \|     |    \ \     \   \ \     \   \|                             |    \ \     \   \ \     \
               \ \     \   +-----+     \ \     \   \ \     \   +-----------------------------+     \ \     \   \ \     \
                \ \     +-----------+   \ \     \   \ \     +-----------------------------------+   \ \     \   \ \     \
                 \ \                 \   \ \     \   \ \                                         \   \ \     \   \ \     \
                  \ \                 \   \ \     \   \ \                                         \   \ \     \   \ \     \
                   \ \     +-----------+   \ \     \   \ \     +-----------------------+     +-----+   \ \     \   \ \     \
                    \ \     \          |    \ \     \   \ \     \                      |\     \    |    \ \     \   \ \     \
                     \ \     \---------+     \ \     \   \ \     \---------------------+ \     \---+     \ \     \   \ \     \
                      \ \     \     +-----------+     \   \ \     \     +-----------+   \ \     \     +-----+     \   \ +-----+
                       \ \     \    |\                 \   \ \     \    |\           \   \ \     \    |\           \   \|     |
                        \ \     \   + \                 \   \ \     \   + \           \   \ \     \   + \           \   +-----+
                         \ \     \   \ +-----------------+   \ \     \   \ \           \   \ +-----+   \ +-----+     \
                          \ \     \   \|                 |    \ \     \   \ \           \   \|     |    \|     |\     \
                           \ \     \   +-----------------+     \ \     \   \ \           \   +-----+     +-----+ \     \
                            \ \     +-----------------------------+     +-----+           +-----------------------+     +-----------+
                             \ \                                                                                \
                              \ \                                                                                \
                               \ +-----------------------------------------------------------------------------------------------------+
                                \|                                                                                |
                                 +-----------------------------------------------------------------------------------------------------+

Output:
#################
        #       #
# ##### # ##### #
#   # # #     # #
# # # # ##### # #
#   # #       # #
### # ####### # #
#   # #    #  # #
# ### # ## # ##
#     # ##    #
#################

Input:
+-----------------+
|\                 \
+ \                 \
 \ \                 \
  \ \                 \
   \ \                 \
    \ \                 \
     \ \                 \
      \ \                 \
       \ +-----------------+
        \|                 |
         +-----------------+

Output:
###
###
###

Input: (Note leading whitespace)
      +-----+     +-----+
      |\     \    |\     \
      + \     \   + \     \
   +-----+-----+-----+-----+
   |\     \    |\     \    |
   + \     \---+ \     \---+
    \ +-----+-----+-----+-----+
     \|     |\     \    |\     \
      +-----+ \     \---+ \     \
         +-----+-----+-----+-----+
         |\     \    |\     \    |
         + \     \---+ \     \---+
          \ +-----+   \ +-----+
           \|     |    \|     |
            +-----+     +-----+

Output:
 # #
# #
 # #
# #

```

# Answer
# Python 2, 81 bytes

```
def f(M,k=1,r='',b=0):
 for c in M[k][k::6]:b^=c>' ';r+=' #'[b]
 print r;f(M,k+3)

```

Try it online!

Takes input as a list of strings (or a list of lists of characters). Prints the output, terminating with error.

The idea is similar to tsh's. We look at the characters marked as `?` below to see which are spaces and which are `\`:

```
+-----------+
|?     ?     ?
+ \           \
 \ \     +-----+
  \ ?     ?    |?
   \ \     \---+
    \ +-----+
     \|?    |?
      +-----+

```

Within each row with `?`'s, a `\` marks a vertical ridge between a filled cell and an empty cell of the maze. Because these ridges are in top layer of the maze, their `\` characters are never obscured by another maze element.

To look at the `?` positions, the code iterates through rows `k=1,4,7,...` (zero-indexed), and in each row looks at every 6th position starting with position `k`. It tracks whether we're in an empty or full cell in the bit `b`, and flips that bit whenever a `\` is encountered. After each character read, it appends the character for empty () or full (`#`) according to `b`, and prints the resulting string after the row is complete.
> 31 votes

# Answer
# JavaScript (Node.js), 85 bytes

```
a=>a.flatMap(u=(l,y)=>y%3?[]:[l.flatMap((c,x)=>x<y|(x-=y+3)%6?[]:' #'[u[x]^=c+1<0])])

```

Try it online!

Basic idea is: we only care about the characters on \\$ (6x+3y+3,3y) \\$. If it is a dash (`-`), current cell has the different value with the one on its top, and if it is a space (), current cell has the same value.

Thanks @Arnauld, saved 7 bytes
> 19 votes

# Answer
# Jelly, ~~22~~ 20 bytes

```
ṫ"J‘$m3n⁶m€6Ż^\ị⁾# Ḋ

```

Try it online!

A monadic link taking a Jelly string as input and returning the processed maze as a Jelly string including one row of trailing whitespace.

1 byte  could be saved if a single line of leading whitespace were acceptable.

Took some inspiration from @tsh’s formula, so be sure to upvote that one too!

## Explanation

```
ṫ"  $                | Tail each string using a paired member of the following:
  J                  | - Sequence along the list of strings
   ‘                 | - Incremented by 1
     m3              | Take every 3rd string (1st, 4th, 7th, ...)
       n⁶            | Not equal to space character
         m€6         | Within each list take every 6th item (1st, 7th, ...)
            Ż        | Prepend a zero to the list
             ^\      | Reduce using xor, collecting up results; vectorised across lists (so starts with 0 xor first list, then output of that xor second list, and so on)
               ị⁾#   | Index into "#", " "
                   Ḋ | Remove first list

```
> 5 votes

# Answer
# 05AB1E, ~~25~~ 22 bytes

*-1 byte thanks to Kevin Cruijssen*

```
εN3%iN.$6ιнηðÊO„ #sèJ,

```

Try it online!

Port of xnor's Python answer. Takes input as a character matrix. The TIO link shows input as a multiline string for readability, with the `|€S` header converting that to the character matrix format.
> 5 votes

# Answer
# Retina 0.8.2, 72 bytes

```
¶(?<=(.|(¶))+)(?<-2>.)+
¶
-4G`
.+¶(.+)¶.+
$1
T` `#`\\  +\\
.(.)....|.
$1

```

Try it online! Explanation:

```
¶(?<=(.|(¶))+)(?<-2>.)+
¶

```

De-skew all of the lines.

```
-4G`

```

Delete the last three lines as I don't need them.

```
.+¶(.+)¶.+
$1

```

Keep only the middle of each group of three lines. (In Retina 1, I believe the above two stages can be done in a single stage: `,G1,3,-5``.)

```
T` `#`\\  +\\

```

Fill in the faces of the blocks.

```
.(.)....|.
$1

```

Keep only the second character of each block.
> 3 votes

# Answer
# C (clang), ~~120~~ 117 bytes

```
o,c,t,s,r;f(char*m){for(s=o=0;*m;!r?t^=*m!=32,s=t?35:46:0)*++m==10?m-=~++o,c=t=0,s=10:0,r||printf(&s),r=c++%6|o%3-1;}

```

Try it online!

Inspired by the others answers.

```
'\'=92   ' '=32=>46='.'  '#'=35   '\n'=10
// o offset == // l line
// c line counter
// t toggle
// r => ? test, point to inspect
for(o=s=0;*m;
!r?t=*m-32?!t:t,s=t?35:46:0) // t^=*m!=32 @ceilingcat
// if test(r) is enabled: toggle(t) and sets (s)

*++m==10?m-=~++o,c=t=0,s=10:0,
// next char => if it's \n overwrites (s)
// and increments offset(o) and move pointer(m)

r || printf (&s)
// r or print! Thanks to @ceilingcat
// instead of
    *++m-10?0:(m-=~++o,c=t=0,s=10),
    !r*s?putchar(s):0,
 Saved 5 !

r=c++%6|o%3-1;// enable test every 6 x 3+1 positions

```
> 2 votes

---
Tags: code-golf, ascii-art, maze
---


# Question
Title: I multiply the source, you (probably) multiply the output!
## Task

The task is to write a program that outputs a consistent but otherwise arbitrary positive integer \\$x\\$ (so strictly greater than 0). Here's the catch: when the source is repeated \\$N\\$ times (the code is appended/concatenated \\$N-1\\$ to itself), the program should have a \\$\dfrac{1}{N}\\$ probability of outputting \\$N\cdot x\\$ and the remaining probability of \\$\dfrac{N-1}{N}\\$ of outputting \\$x\\$ unchanged.

## Example

Let's assume that your initial source is `XYZ` and produces the integer `3`. Then:

* For \\$N=2\\$: `XYZXYZ` should output \\$3\\$ with a probability of \\$\frac{1}{2}\\$ (50% of the time) and \\$2\cdot 3=6\\$ with a probability of \\$\frac{1}{2}\\$ as well (50% of the time).
* For \\$N=3\\$: `XYZXYZXYZ` should output \\$3\\$ with a probability of \\$\frac{2}{3}\\$ (66.666% of the time) and \\$3\cdot 3=9\\$ with a probability of \\$\frac{1}{3}\\$ (33.333% of the time)
* For \\$N=4\\$: `XYZXYZXYZXYZ` should output \\$3\\$ with a probability of \\$\frac{3}{4}\\$ (75% of the time) and \\$4\cdot 3=12\\$ with a probability of \\$\frac{1}{4}\\$ (25% of the time)

and so on....

## Rules

Note: This challenge is a (much) harder version of this one.

# Answer
# , ~~66~~ 35 bytes

-29 bytes thanks to digEmAll.

-2 bytes thanks to Giuseppe.

```
+0->A
x=!0:F
F=F+1
sample(F*x+!x,1)

```

Try it online!

Check the distribution for N=4.

The key is the rightwards assignment `->`. When the code is multiplied \\$N\\$ times, the first \\$N-1\\$ calls to `sample` will be assigned to `A`, and only the last call will be printed.

Original, more convoluted solution:

# , 66 bytes

```
T->TT
F=F+1
TT=0
`?`=function(x)if(x)sample(c(1,F),1,,c(1,F-1))
?T

```

Try it online!

Try it online (repeated 3 times)!

Uses two tricks: 1) call the main function of interest `?`, so that we can call it without ending the program with a bracket, and 2) use variables `T` and `TT`, with code which starts with `T` and ends with `?T`.

`F` is the iteration counter. `?` is redefined as a function which takes a boolean argument: if the input of `?` is `TRUE` (or `T`), it does the required random sampling; if the input is `FALSE` (or `0`), it does nothing. The value of `TT` is defined as `0`, so that `?T` does the sampling but `?TT` does nothing.

When the source is repeated, it looks like this:

```
T->TT
F=F+1
TT=0
`?`=function(x)if(x)sample(c(1,F),1,,c(1,F-1))
?TT->TT
F=F+1
TT=0
`?`=function(x)if(x)sample(c(1,F),1,,c(1,F-1))
?T

```

so the middle call `?TT` outputs nothing but the final call `?T` outputs the random result.
> 16 votes

# Answer
# Bash, 31 bytes

```
trap echo\ $[RANDOM%++n?1:n] 0;

```

Try it online!

`trap ... 0` will run the code contained on exit. Repeated `trap`s will overwrite old ones. The unquoted `$[arithmetic expansion]` gets run every time a new trap is set.

---

Zsh can save one byte with `<<<`:

```
trap "<<<$[RANDOM%++n?1:n]" 0;

```
> 11 votes

# Answer
# Python 3, ~~81~~ 79 bytes

```
+0if[]else 1
from random import*
try:n+=1
except:n=1
print([1,n][random()*n<1])

```

Try it online!

*-1 byte thanks to @Nishioka*

This is one Python 3 solution that does not access the program source directly. Doing this in Python 3 is more challenging than Python 2 because normal printing statements end with a closing parenthesis so there aren't many choices to change its behavior in the next block of initial source. It would be interesting to see more creative solutions in Python 3.
> 11 votes

# Answer
# Jelly, 7 bytes

```
‘ɼḷXỊ®*

```

Try it online!
> 6 votes

# Answer
# 05AB1E, 7 bytes

```
¾Å1¼¾ªΩ

```

Try it online!
> 4 votes

# Answer
# Python 3, 78 76 75 bytes

Using the same trick as in the link that was posted, here is a Python one (with x=1).

```
from random import*;n=len(*open(__file__))//75;print(1+~-n*(random()<1/n))#

```

Try it online!

-2 bytes thanks to Mr. Xcoder for his `(n-1)` formula with `~-n` which has higher precedence than `*`
-1 byte thanks to Nishioka
> 4 votes

# Answer
# Dyalog APL, ~~25~~ ~~24~~ ~~23~~ ~~22~~ 21 bytes

```
0{×⍺:1+⍵⋄⎕←1⌈⍵×1=?⍵}1

```

Try it online!
> 4 votes

# Answer
# Perl 5, ~~28~~ 26 bytes

-2 bytes thanks to @Grimy

```
1 if!++$x;say 1<rand$x||$x

```

TIO
> 3 votes

# Answer
# Gaia, ~~17~~ ~~15~~ ~~14~~ 13 bytes

```
Øgl13÷:(1w&+ṛ

```

Try it online!

I randomly noticed the behavior of `Øg` yesterday when looking through the docs, which helped immensely.
> 3 votes

# Answer
# Ruby, 40 bytes

```
1
n||=@x=0
n+=1
puts 1>rand(n)?n:1 if @x

```

Try it online!

Try it online (copied 3 times)!

A ruby port of this Python answer.

# Ruby, 38 bytes

2 bytes saved by reading the file:

```
n=File.size($0)/38;puts 1>rand(n)?n:1#

```

Try it online!
> 3 votes

# Answer
# Runic Enchantments, 31 bytes

```
UwR'10<;$\
I+:'RA0)?/1$;
1
l;
y

```

Try it online!

Uses the same structure as this answer to count how many times the source has been duplicated:

Just instead of outputting the nth number in a list, we use that value to randomly generate a number, if the result is not 0, print 1, else print that number.
> 2 votes

# Answer
# Japt, ~~9~~ 8 bytes

```
(°Tö)ÎªT

```

Test it | Doubled | Tripled
Verify distribution of 10000 runs after 10 repetitions

```
(°Tö)ÎªT
(            :Prevent the operator that follows from being implicitly applied to the first input variable, U
 °T          :Increment T (initially 0) by 1
   ö         :Random element in the range [0,T)
    )        :Closing the parentheses here instead of after the T saves a byte as there would need to be a space here to close the random method
     Î       :Sign - 0 (falsey) or 1 (truthy)
      ªT     :Logical OR with current value of T

```

---

## Original, ~~13~~ ~~11~~ ~~10~~ 9 bytes

Note the trailing space.

```
NoÎp°T ö

```

Test it | Doubled | Tripled
Verify distribution of 10000 runs after 10 repetitions

```
NoÎp°T ö
N             :Initially, the (empty) array of inputs
 o            :Replace the last element with
  Î           :  Its sign (always 1)
   p          :Push
    °T        :  T (initially 0) incremented
       ö      :Random element of N

```
> 2 votes

# Answer
# JavaScript (JavaScript shell 71), 78 bytes

```
(async x=>x)().then(x=>f((''+f).length/78));f=x=>print(1-~x*Math.random()|0)//

```

No tio link, spidermonkey on tio is too old...

Firefox (Spidermonkey) consider the comment as a part of function `f`. As the result, `(''+f).length` will be `b+79n` where b \< 78, and (n + 1) is the times of source code repeated.

This buggy (? I'm not sure. I would prefer it is a bug of JavaScript specification rather than any interpreter) behavior had been submit to BMO by someone else just after this answer posted: https://bugzilla.mozilla.org/show\_bug.cgi?id=1579792 . (Neither of the bmo thread nor the tweet is posted by me.)
> 2 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~133~~ ~~114~~ 112 bytes

This is the first (and hopefully last) time I have ever used C# preprocessor directives.

```
#if!I
#define I
static int i;
class p{~p()=>Console.Write(new Random().Next(i)<1?i:1);}p s=new p();
#endif
i++;

```

Try it online!
> 1 votes

# Answer
# Charcoal, 12 bytes

```
⎚Ｉ⎇‽Ｌ⊞Ｏυω¹Ｌυ

```

Try it online! Based on my answer to the linked question. Outputs `n` with probability `¹/ₙ`, otherwise `1`. Explanation:

```
⎚               Remove output from previous iterations
       υ        Initially empty list
        ω       Empty string
     ⊞Ｏ         Push
    Ｌ           Length
   ‽            Random integer [0..length)
  ⎇             Ternary
         ¹      If nonzero then literal 1
          Ｌυ    If zero then the new length
 Ｉ              Cast to string for implicit print

```
> 1 votes

---
Tags: code-golf, random, source-layout
---


title: Do these squares overlap?

text:
# Question
Title: Do these squares overlap?
Given the coordinates of the upper left corners of two squares and their side lengths, determine whether the squares overlap. A square includes the top and left lines, but not the bottom and right lines. That is, a point `(a,b)` is inside a square with side length `k` that starts at `(x,y)` if and only if `x <= a < x+k` and `y <= b < y+k`. A square with side length 0 is degenerate and will not be considered here, thus, `k` will be positive.

As usual, all standard rules apply. Input and output may be in whatever form is convenient, so long as it's human readable and there is no precomputation. Be sure to specify what input format you use. Your code should take six numbers and output truthy if the squares overlap and falsy otherwise.

## Test Cases

```
x1 y1 k1  x2 y2 k2  overlap?
 1  1  1   0  1  1  false
 0  0  3   1  1  1  true
 1  1  1   0  0  3  true
 0  0  3   2  1  2  true
 0  0  2   1  1  2  true
 1  1  2   0  0  2  true
 0  1  2   1  0  2  true
 1  0  2   0  1  2  true
 2  0  2   0  2  2  false
 1  0  3   0  1  1  false
 0  2  3   0  0  2  false

```

All inputs will be non-negative integers. That said, I expect that many or most solutions will also be able to handle negatives and floats.

# Answer
## Python, 33 bytes

```
lambda x,y,k,X,Y,K:k>X-x>-K<Y-y<k

```

Python supports chains of inequalities even when they point opposite directions.

The x-coordinate intervals `[x,x+k)` and `[X,X+K)` overlap as long as neither one is fully to the right of the other, which means that each interval's left endpoint is left of the other interval's right endpoint.

```
x<X+K
X<x+k

```

The can be combined into a joint inequality `-K<X-x<k`. Writing the same for y-coordinates and splicing them at `-K` gives the expression

```
k>X-x>-K<Y-y<k

```
> 23 votes

# Answer
# MATL, ~~14~~ ~~11~~ ~~10~~ ~~5~~ 4 bytes

```
tP->

```

This solution accepts input in the form of two arrays:

1. A 2 x 2 matrix that contains the coordinates of the corners `[x1, y1; x2, y2]`
2. A 2 x 1 array containing the square dimensions `[k2; k1]`

**Try it Online**

**Slightly modified version to run all test cases**

**Explanation**

```
        % Implicitly grab the first input
t       % Duplicate the input
P       % Flip along the first dimension (columns)
-       % Subtract the two to yield [x1-x2, y1-y2; x2-x1, y2-y1]
        % Implicitly grab the second input
>       % Compare with [k2, k1] (automatically broadcasts)
        % Implicitly display the truthy/falsey result

```
> 10 votes

# Answer
# MATLAB, ~~36~~ 21 bytes

```
@(a,b)a-flip(a)<[b,b]

```

Creates an anonymous function which can be evaluated as `ans(a,b)`. Accepts two inputs of the following format:

1. 2 x 2 matrix containing the corner of each square as a row: `[x1, y1; x2, y2]`.
2. 2 x 1 array containing the size of the two squares: `[k2; k1]`

All test cases here.

**Explanation**

Here is a commented un-golfed solution

```
%// Example input
a = [1 1;
     0 1];

b = [1; 1];

%// Flip a along the first dimension and subtract from a to yield:
%//
%// [x1-x2   y1-y2]
%// [x2-x1   y2-y1]
d = a - flip(a);

%// Compare this matrix element-wise with two horizontally concatenated copies
%// of the second input [k2; k1]
result = d < [b,b];

%// Truthy values have all ones in the result and falsey values have at
%// least one 0 in the result.

```
> 5 votes

# Answer
## JavaScript (ES6), 38 bytes

```
(a,b,c,d,e,f)=>d-a<c&a-d<f&e-b<c&b-e<f

```

If *d* \- *a**c* then the second square is to the right of the first. Similarly the other conditions check that it is not to the left, below or above.
> 4 votes

# Answer
# Jelly, 8 bytes

```
Ṫṗ2+µ€f/

```

Input is the nested list **\[\[x1, y1, k1\], \[x2, y2, k2\]\]**, output is the list of all incremented coordinates of points with integer coordinates that are common to both squares (falsy if empty, truthy if not).

Try it online! or verify all test cases.

### How it works

```
Ṫṗ2+µ€f/  Main link. Argument: [[x1, y1, k1], [x2, y2, k2]]

    µ     Combine the chain to the left into a link.
     €    Apply it to each list [xi, yi, ki].
Ṫ           Tail; pop and yield ki.
 ṗ2         Second Cartesian power; yield the list of all pairs [a, b] such that
            1 ≤ a ≤ ki and 1 ≤ b ≤ ki.
   +        Add [xi, yi] to each pair, yielding the list of all pairs [c, d] such
            that xi + 1 ≤ c ≤ xi + ki and yi + 1 ≤ d ≤ yi + ki.
      f/  Reduce by filter, intersecting the resulting lists of pairs.

```
> 3 votes

# Answer
# TI Basic, 36 bytes

```
Prompt X,Y,K,Z,θ,L:Z-X<K and X-Z<L and θ-Y<K and Y-θ<L

```
> 2 votes

# Answer
# Java, 78 bytes

```
Object o(int a,int b,int c,int d,int e,int f){return d-a<c&a-d<f&e-b<c&b-e<f;}

```
> 1 votes

# Answer
# Octave, 17 bytes

```
@(a,b)a-flip(a)<b

```

Same logic as my MATLAB answer above, except that Octave supports automatic broadcasting of dimensions so we can replace `[b,b]` with simply `b`.

All test cases here
> 1 votes

# Answer
# SmileBASIC, ~~76~~ 57 bytes

```
INPUT X,Y,W,S,T,U
SPSET.,X,Y,W,W
SPCOL.?!SPHITRC(S,T,U,U)

```

Creates a sprite with the size/position of the first square, then checks if it collides with the second square.
> 1 votes

# Answer
# x86-64 Machine code, Windows 22 bytes

C++ signature:

```
extern "C" uint32_t __vectorcall squareOverlap(__m128i x, __m128i y, __m128i k);

```

Returns 0 if the squares don't overlap and -1 (0xFFFFFFFF) otherwise. Inputs are vectors of 2 64-bit integers for x, y and k(`_mm_set_epi64x(x1, x2)` etc.).

```
squareOverlap@@48 proc
66 0F FB C8          psubq       xmm1,xmm0
0F 16 D2             movlhps     xmm2,xmm2
66 0F 38 37 D1       pcmpgtq     xmm2,xmm1
0F 12 CA             movhlps     xmm1,xmm2
0F 54 CA             andps       xmm1,xmm2
66 0F 7E C8          movd        eax,xmm1
C3                   ret
squareOverlap@@48 endp

```
> 1 votes

# Answer
# 05AB1E, 5 bytes

```
Â-›˜P

```

Port of *@Suever*'s MATL answer, with additional conversion to a truthy/falsey result. The input-format is therefore also the same:
First input as `[[x1,y1],[x2,y2]]` and second input as `[k2,k1]`.

Try it online or verify all test cases.

**Explanation:**

```
Â       # Bifurcate (short for Duplicate & Reverse copy) the (implicit) input-matrix
 -      # Subtract each value (vectorized) from the input-matrix we duplicated
  ›     # Check for both values (vectorized) if it's larger than the (implicit) input-list
        # (We now have the same result as the MATL answer. In MATL a matrix/list consisting
        #  of only 1s is truthy. In 05AB1E this isn't the case however, so:)
    ˜   # Flatten the matrix to a single list
     P  # And take the product to check if all are truthy
        # (after which the result is output implicitly)

```
> 1 votes

---
Tags: code-golf, math, geometry
---