# Question
Title: Multiply two numbers without using any numbers
You are given as input two strings representing positive integers in base 10, such as `"12345"` and `"42"`. Your task is to output a string containing their product, `"518490"` in this case.

The twist is that you may not use any numerical types in your code. No `ints`, `float`s, `unsigned long`s, etc., no built-in complex number types or arbitrary precision integers, or anything along those lines. You many not use literals of those types, nor any function, method, operator etc. that returns them.

You *can* use strings, booleans, arrays, or anything else that wouldn't normally be used to represent a number. (But note that neither indexing into an array nor getting its length are likely to be possible without invoking a numeric type.) `char`s are permitted, but you may not perform any arithmetic or bitwise operations on them or otherwise treat them as anything else other than a token representing part of a string. (Lexicographical comparison of `char`s is allowed.)

You may not work around the restriction. This includes (but is not limited to) using numeric types inside an `eval` type function, implicit type conversions into numerical types, using numeric or bitwise operators on non-numeric types that support them, using numerical types stored inside container types, or calling functions or external programs that return numerical results in string form. (I reserve the right to add to this list if other workarounds appear in the answers.) You must implement the multiplication yourself using only non-numeric types.

Input and output may be by any convenient method, as long as the data enters and exits your code in the form of a string. You may assume each of the two input arguments contains only the ASCII characters `[0-9]` and will not start with `0`. Your output shouldn't have leading zeroes either.

One more thing: your code **must** correctly handle inputs up to **at least 10 characters in length**, and **must** run in under a minute on a modern computer for **all** inputs in that range. Before posting, please check that when given inputs `9999999999` and `9999999999`, your program gives an output of `99999999980000000001`, in less than a minute. This restriction exists specifically to prevent answers that work by allocating an array of size `a*b` and then iterating over it, so please bear in mind that answers of that form will not be eligible to win.

This is , so the shortest valid solution (in bytes) wins.

# Answer
> 6 votes
# Haskell - 180 ~~206 214~~

```
r=reverse
f=filter
z=['0'..'9']
a?f|f="1"!a
a?_=a
(a:b)!(c:d)=e:b!d?(e<a)where e=fst$last$zip(f(>=c)z++z)$f(<=a)z
a!c=a++c
a%(b:c)=foldr(!)('0':a%c)$f(<b)z>>[a]
_%b=b
a#b=r$r a%r b

```

Implements multiplication via repeated addition, and all kinds of digit magic are handled by shifting and filtering the `['0'..'9']` list. Defines an operator `#` of the type `String -> String -> String`:

```
*> :set +s
*> "9990123456789"#"9999876543210"
"99900001219316321126352690"
(0.02 secs, 9862288 bytes)

```

# Answer
> 16 votes
# sed, 339 338 bytes

I know this is an old one, but I was browsing and this piqued my interest. Enough to actually register as a user! I guess I was swayed by "*I would quite like to see a full sed solution – Nathaniel*"...

```
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g
:o
s/\( .*\)0$/0\1/
/x$/{
x
G
s/ .*/\n/
:a
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
ta
s/\n//g
:c
s/^x/0x/
s/0xxxxxxxxxx/x0/
tc
x
s/x$//
}
/ 0/bo
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

```

This sed script expects two decimal numbers as input, separated by one space

tests:

```
time test 518490 = $(./40297.sed <<<)"12345 42" || echo fail
time test 99999999980000000001 = $(./40297.sed <<<"9999999999 9999999999") || echo fail
time test 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = $(./40297.sed <<<"37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061") || echo fail
time test 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 = $(./40297.sed <<<"33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917") || echo fail

```

You might recognise last two as RSA-100 (50 x 50 digits) and RSA-768 (116 x 116 digits).

Using GNU sed on a not-very-modern (2007-era Intel Core 2), the last of those takes over a minute, but it comes faster on a newer processor:

* Q6600: \>1 minute
* i7-3770: 26 seconds
* i7-6700: 22 seconds

The puny 10-digit multiply specified in the question takes well under a second on any of these (despite being full of pathological nines).

I believe it's standard sed, with no extensions. POSIX guarantees hold space of 8192 bytes only, which limits us to multiplying 400x400 digit numbers, but implementations can provide more. GNU sed is limited only by available memory, so could manage something much bigger, if you're willing to wait.

And I'm confident that I have complied with the rules - that's almost a given in a language that has no numbers. :-)

## Explanation

I use a unary/decimal hybrid, converting decimal numbers into a sequence of unary:

```
 42 => _xxxx_xx

```

In unary decimal, addition is easy. We iterate from least-significant to most-significant digit, concatenating the x's:

```
   X=965                   Y=106                                 SUM
   _xxxxxxxxx_xxxxxx_xxxxx _x__xxxxxx
   _xxxxxxxxx_xxxxxx       _x_                          _xxxxxxxxxxx
   _xxxxxxxxx              _x                    _xxxxxx_xxxxxxxxxxx
                                      _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx

```

We then remove whitespace, and deal with carry by converting 10 consecutive x's to one of the next unit:

```
 _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx       10.6.11
 _xxxxxxxxxx_xxxxxxx_x                10.7.1
 _x__xxxxxxx_x                        1.0.7.1

```

Once we have addition, multiplication is possible. We multiply x\*y by considering the last digit of y. Add x to the accumulator that many times, then move to the next digit and shift x one decimal place to the left. Repeat until y is zero.

## Expanded code

```
#!/bin/sed -f

# Convert to unary decimal.  We save two or three bytes of code by
# reusing 0 as the digit separator.
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g

# until y==0

:one

# y ends in zero => x *= 10 and y /= 10
s/\( .*\)0$/0\1/

# while y%10, acc += x, y -= 1
/x$/{
x
G
s/ .*/\n/
# Add x
:add
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
tadd
s/\n//g
:carry
s/^x/0x/
s/0xxxxxxxxxx/x0/
tcarry

# repeat for each unit of y
x
s/x$//
}

# y?
/ 0/bone

# convert hold space to decimal
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

```

# Answer
> 9 votes
# Python – ~~312~~ ~~286~~ 273

```
D={}
e=t=""
N=[e]
for c in"0123456789":D[c]=t;D[t]=c;t+="I";N+=N
B=lambda s:[D[c]for c in reversed(s)]
Y=B(input())+N
for a in B(input())+N:
 for c in a:
    s=[];o=e
    for a,b in zip(N,Y):i=a+b+o;o=t<=i and"I"or e;s+=i.replace(t,e),;N=s
 Y=[e]+Y
print e.join(B(N)).lstrip("0")

```

If (lots of) leading zeroes are allowed, the last 12 characters are not needed.

This essentially performs the standard multiplication by hand. Digits are represented as strings of repeated `I`s (like primitive Roman numerals). Numbers are represented as lists of digits in reverse order. Addition of single digits is performed by cocatenating strings and removing ten `I`s if necessary.

Here is an ungolfed version:

```
N = [""] # zero object: list with a lot of empty strings
D = {}   # dictionary for conversion from and to digits
i = ""   # iterates over digits
for c in "0123456789":
    D[c] = i  # map digit to Roman digit
    D[i] = c  # and vice versa
    i += "I"  # increments Roman digit
    N += N    # add leading zeros to zero

ten = "IIIIIIIIII" # Roman digit ten

# Conversion function
B = lambda s: [D[c] for c in reversed(s)]

def Add(x,y):
    Sum = []
    carryover = ""
    for a,b in zip(x,y):
        increment = a+b+carryover
        carryover = "I" if ten in increment else ""
        increment = increment.replace(ten,"") # take increment modulo ten
        Sum += [increment]
    return Sum

def M(x,y):
    Sum = N[:] # Initiate Sum as zero
    X = B(x)+N # Convert and add leading zeros
    Y = B(y)+N
    for a in X:
        for c in a:
            Sum = Add(Sum,p+Y)
        Y = [""] + Y # multiply Y by 10
    return "".join(B(Sum)).lstrip("0") # Convert back and to string, remove leading zeros.

M(input(),input())

```

# Answer
> 7 votes
# Brainfuck (1328 bytes)

Considerations at first:

* Not sure if brainfuck is a valid answer to this questions since I'm not sure whether you consider the cell values as 'numerical types' or not. I don't think so since bf doesn't know types, but that's my own opinion, please correct me if I'm wrong.
* An implementation supporting (nearly) unlimited values is necessary.
* It might be far too slow, based on the implementation.

I only tested the program with my own interpreter, you can find it here.

Input must be both numbers separated by a single ASCII space.

**Golfed:**

```
,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

```

**Ungolfed:**

```
,
>++++++[<----->-]<--
[                                           # read input until space
    >,
    >++++++[<----->-]<--                    # decrease cell by 32 to check if it's a space
]
>>>+<<<<                                    # set multiplier to 1

[

    >>++++[<<---->>-]<<                     # decrease by 16 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<                                    # delete old multiplier

,[>,]                                       # read second number until end of input
>>>+<<<<                                    # set new multiplier

[

    >>+++++++[<<------->>-]<<+              # decrease by 48 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<<<<<                                # delete multiplier

[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>          # multiply both values

# magical algorithm for printing cell value as number taken from Cedric Mamo's code from a previous question
[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

```

I've taken the code for the output of the value from this answer, thanks to the author for that!

The program *might* not be valid, but in either way I wanted to share it with you ^^

**Update:** You can now test it (only for small multiplications) here, thanks to @Sp3000's answer to this contest and SE's new Stack Snippets!

```
var NUM_CELLS = 30000;var ITERS_PER_SEC = 100000;var TIMEOUT_MILLISECS = 5000;function clear_output(){document.getElementById("output").value="";document.getElementById("stderr").innerHTML=""}function stop(){running=false;document.getElementById("run").disabled=false;document.getElementById("stop").disabled=true;document.getElementById("clear").disabled=false;document.getElementById("wrap").disabled=false;document.getElementById("timeout").disabled=false;document.getElementById("eof").disabled=false}function interrupt(){error(ERROR_INTERRUPT)}function error(e){document.getElementById("stderr").innerHTML=e;stop()}function run(){clear_output();document.getElementById("run").disabled=true;document.getElementById("stop").disabled=false;document.getElementById("clear").disabled=true;document.getElementById("wrap").disabled=true;document.getElementById("timeout").disabled=true;document.getElementById("eof").disabled=true;code=document.getElementById("code").value;input=document.getElementById("input").value;wrap=document.getElementById("wrap").value;timeout=document.getElementById("timeout").checked;eof=document.getElementById("eof").value;loop_stack=[];loop_map={};for(var e=0;e<code.length;++e){if(code[e]=="["){loop_stack.push(e)}else if(code[e]=="]"){if(loop_stack.length==0){error(ERROR_BRACKET);return}else{var t=loop_stack.pop();loop_map[t]=e;loop_map[e]=t}}}if(loop_stack.length>0){error(ERROR_BRACKET);return}running=true;start_time=Date.now();code_ptr=0;input_ptr=0;cell_ptr=Math.floor(NUM_CELLS/2);cells={};iterations=0;bf_iter(1)}function bf_iter(e){if(code_ptr>=code.length||!running){stop();return}var t=Date.now();for(var n=0;n<e;++n){if(cells[cell_ptr]==undefined){cells[cell_ptr]=0}switch(code[code_ptr]){case"+":if(wrap=="8"&&cells[cell_ptr]==255||wrap=="16"&&cells[cell_ptr]==65535||wrap=="32"&&cells[cell_ptr]==2147483647){cells[cell_ptr]=0}else{cells[cell_ptr]++}break;case"-":if(cells[cell_ptr]==0){if(wrap=="8"){cells[cell_ptr]=255}if(wrap=="16"){cells[cell_ptr]=65535}if(wrap=="32"){cells[cell_ptr]=2147483647}}else{cells[cell_ptr]--}break;case"<":cell_ptr--;break;case">":cell_ptr++;break;case".":document.getElementById("output").value+=String.fromCharCode(cells[cell_ptr]);break;case",":if(input_ptr>=input.length){if(eof!="nochange"){cells[cell_ptr]=parseInt(eof)}}else{cells[cell_ptr]=input.charCodeAt(input_ptr);input_ptr++}break;case"[":if(cells[cell_ptr]==0){code_ptr=loop_map[code_ptr]}break;case"]":if(cells[cell_ptr]!=0){code_ptr=loop_map[code_ptr]}break}code_ptr++;iterations++;if(timeout&&Date.now()-start_time>TIMEOUT_MILLISECS){error(ERROR_TIMEOUT);return}}setTimeout(function(){bf_iter(ITERS_PER_SEC*(Date.now()-t)/1e3)},0)}var ERROR_BRACKET="Mismatched brackets";var ERROR_TIMEOUT="Timeout";var ERROR_INTERRUPT="Interrupted by user";var code,input,wrap,timeout,eof,loop_stack,loop_map;var running,start_time,code_ptr,input_ptr,cell_ptr,cells,iterations
```

```
<div style="font-size:12px;font-family:Verdana, Geneva, sans-serif;"> <div style="float:left; width:50%;"> Code: <br> <textarea id="code" rows="4" style="overflow:scroll;overflow-x:hidden;width:90%;">,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]</textarea> <br>Input: <br> <textarea id="input" rows="2" style="overflow:scroll;overflow-x:hidden;width:90%;">7 6</textarea> <p> Wrap: <select id="wrap"> <option value="8">8-bit</option> <option value="16">16-bit</option> <option value="32" selected="selected">32-bit</option> </select>   Timeout: <input id="timeout" type="checkbox"></input>  EOF: <select id="eof"> <option value="nochange">Same</option> <option value="0" selected="selected">0</option> <option value="-1">-1</option> </select> </p> </div> <div style="float:left; width:50%;"> Output: <br> <textarea id="output" rows="6" style="overflow:scroll;width:90%;"></textarea> <p> <input id="run" type="button" value="Run" onclick="run()"></input> <input id="stop" type="button" value="Stop" onclick="interrupt()" disabled="true"></input> <input id="clear" type="button" value="Clear" onclick="clear_output()"></input>   <span id="stderr" style="color:red"></span></p></div></div>
```

# Answer
> 7 votes
## Ruby: ~~752~~ 698

This is just to get an answer out there, just done out of curiosity. Edited: now golfed a bit.

```
$F='0123456789'
$G="#{$F}abcdefghij"
def x(a,b);p(a=~/[13579]$/?b:"",a==""?"":x(Hash[*%w(b0 5 b1 6 b2 7 b3 8 b4 9)].to_a.inject(a.tr($F,'0011223344').chars.zip(a.tr($F,'ababababab').chars).flatten.join("")){|n,q|k,v=q;n.gsub(k,v)}.gsub(/[ab]/,'').sub(/^0*/,''),p(b,b)));end
def p(a,b);j,k=["0#{a}","0#{b}"].map{|c|c.gsub(/./,'0')};c="#{k}#{a}".chars.zip("#{j}#{b}".chars).drop_while{|z|z==%w(0 0)}.map{|m|$G.sub(/#{m.map{|n|"122333444455555666666777777788888888999999999".chars.select{|c|c==n}}.flatten.map{|c|'.'}.join("")}/,"").chars.first}.flatten.join("");d=nil;
while c!=d
 d=c;c="0#{d}".gsub(/[0-9][a-j]/) {|m| m.tr($G,"123456789a#{$F}")}.sub(/^0/,'')
end;c;end
puts x(ARGV.shift,ARGV.shift)

```

Usage: I had this in a file called peasant.rb:

```
$ time ruby peasant.rb 9999999999 9999999999
99999999980000000001

real    0m0.129s
user    0m0.096s
sys 0m0.027s

```

Explanation: it's peasant multiplication, so I repeatedly halve&double. Halving is done by halving digits & marking remainders like so: 1234 -\> 0b1a1b2a; then find and replace on the b's: 06a17a; then cleaning up -\> 617.

Addition is done like so... first of all, I pad both strings to the same length and make pairs from the digits. Then I add the digits by constructing a string that has the length of each digit and concatenating; I remove a string of that length from the start of '0123456789abcdefghij', and then keep the first char. So, eg, "9"+"9"-\>"i". NB I avoid actually using length functions here to avoid number types entirely; removing the prefix is done with a regexp instead.

So now I have a string containing a mix of digits and letters. The letters represent numbers with a carry digit; I prepend 0 to the number, then repeatedly replace digit-letter patterns with the result of the carry until the addition is complete.

# Answer
> 6 votes
## Python, 394 349 340 chars

```
D='0123456789'
R=reversed
U=lambda x:[R for y in D if y<x]
T=U(':')
def A(a,b,r='',c=[]):
 for x,y in map(None,R(a),R(b)):
    d=U(x)+U(y)+c;t=T;c=[R]
    if d<T:t=c=[]
    r=min(k for k in D if U(k)+t>=d)+r
 if c:r='1'+r
 return r
a,b=input()
m=''
while b:
 if list(b).pop()in'13579':m=A(m,a)
 b=list(A(b,A(b,A(b,A(b,b)))));b.pop();a=A(a,a)
print m

```

Run like:

```
echo '"9999999999","9999999999"' | ./mulstr.py

```

Takes 50 milliseconds.

Uses Russian Peasant multiplication. When adding digits, we convert them to unary ('5' =\> \[R,R,R,R,R\]), concatenate the lists, then convert back. `U` converts to unary, using `R` as the unary digit. We compute `b/=2` as `b=b*5/10`.

# Answer
> 6 votes
# Haskell, 231 bytes

This defines an operator # which multiplies two string representations of natural numbers. It works by defining an elementary increment/decrement operation on strings, then uses it to build up addition and multiplication. A little extra magic gives some exponential speedups that make it all possible..

```
r=reverse
n="9876543210"
t=True
c&(x:y)|c==x=head y|t=c&y
m%[]="1";m%(c:s)|c==last m=head m:m%s|t=c&m:s
[]!y=y;x![]=x;(x:a)!('0':b)=x:a!b;x!y=(r n%x)!(n%y)
"0"?_="0";x?('0':y)|all(=='0')y="0"|t=('0':x)?y;x?y=x?(n%y)!x
x#y=r$r x?r y

```

This approach is fast enough that even on a 2008 laptop in the unoptimized ghci REPL, the test case takes just a fraction of a second:

```
λ> :set +s
λ> let test = replicate 10 '9'
(0.00 secs, 0 bytes)
λ> test
"9999999999"
(0.00 secs, 1069784 bytes)
λ> test # test
"99999999980000000001"
(0.06 secs, 13451288 bytes)

```

Here's a check that all of the two-digit products are correct:

```
λ> and [ show (x * y) == (show x # show y) | x <- [0..100], y <- [0..100] ]
True

```

# Answer
> 5 votes
# JavaScript (E6) 375 ~~395 411 449~~

**Edit** Golfed
**Edit** Bug fixed: missing clearing a carry flag

It can be done with just symbol manipulation in near 0 time.
In this version you could use any char instead of the digits, as long as the symbol are in ascending order.

Notes: using strings, hashmap with string key, arrays used as list. No indexing, the arrays are traversed using 'map' or rotated using push & shift.
All '+' are string concatenation.

```
M=(x,y,S=a=>a.shift()||z,R=a=>[...a].reverse(),e=R('9876543210'),d=[...e])=>
  R(y)[T='map'](b=>
     R(x)[T](a=>(
       u=R[e[a+=b]+v],
       v=R[S[a]+(u<v?'1':z)],
       p[P](t=R[S(o)+u]),
       t<u?v=R[v+'1']:v
     ),o=p,p=[])
    +(v>z&&p[P](v),x+=v=z),
    d[T](a=>d[T](b=>e[P='push'](R[a+b]=S(e)))+e[P](S(e))),
    d[T](a=>d[T](b=>e[d[T](c=>v=c<a?(u=R[u+b])<b?R[v+'1']:v:v,v=u=z='0'),S[a+b]=v,a+b]=u)),
    p=[v=z]
  )&&R(p).join(o)

```

**Less Golfed** (maybe I'll add an explanation tomorrow)

```
M=(x,y)=>(
  R=a=>[...a].reverse(),
  // Addition table s
  s={},
  e=[...'9012345678'],
  [for(a of(d='0123456789'))for(b of(e.push(e.shift()),d))e.push(s[a+b]=c=e.shift())],
  // Multiplication table m,n
  m={},n={},
  [for(a of d)for(b of d)(
     [for(c of(z=u=v='0',d))
     c<a&&(t=s[u+b],t<u?v=s[v+'1']:v,u=t)
     ],m[a+b]=u,n[a+b]=v
  )],
  x=R(x),v=z,o=[],p=[],
  [for(b of R(y))(
     [for(a of x)(
       u=s[m[a+b]+v],v=s[n[a+b]+(u<v?'1':z)],
       p.push(t=s[(o.shift()||z)+u]),
       t<u?v=s[v+'1']:v
     )],
     v>z?p.push(v):o,o=p,p=[],x.unshift(v=z)
  )],
  R(o).join('')
)

```

**Test** In FireFox/FireBug console

```
t0=-new Date
r=M('9999999999','9999999999')
t1=-new Date
console.log("Result",r, "time ms", t0-t1)

```

*Output*

```
Result 99999999980000000001 time ms 14

```

# Answer
> 3 votes
**JavaScript: ~~3710~~ 3604 bytes**

* Using string lookup tables with 1 digit multiplication and add with carry.
* The multiplication is done by digit x digit instead of digit x line.

Golf:

```
var M={
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};
var A={
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
}
Array.prototype.e=function(){return(''+this)==='';}
String.prototype.s=function(){return this.split('').reverse();}
function B(a,b,c) {
var r='',s='';
a=a.s();
b=b.s();
while (!a.e()||!b.e()||c!=='0') {
x=a.e()?'0':a.shift();
y=b.e()?'0':b.shift();
s=A[c+x+y];
s=s.s();
r=s.shift()+r;
c=s.e()?'0':'1';
}
return r;
}
function m(a,b) {
var s='0',m='';
b.split('').reverse().forEach(function(e){
var z=m;
a.split('').reverse().forEach(function(f){s=B(s,M[e+f]+z,'0');z+='0';});
m+='0';
});
return s;
}

```

Ungolfed with tests:

```
var mul = {
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};

var adc = {
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
}

Array.prototype.isEmpty = function() {
  return (''+this) === '';
}

function add(a, b, c) {
  var r = '', s = '';
  a = a.split("").reverse();
  b = b.split("").reverse();
  while (!a.isEmpty() || !b.isEmpty() || c !== '0') {
    x = a.isEmpty() ? '0' : a.shift();
    y = b.isEmpty() ? '0' : b.shift();
    s = adc[c + x + y];
    s = s.split("").reverse();
    r = (s.shift()) + r;
    c = (s.isEmpty()) ? '0' : '1';
  }
  return r;
}

function mult(a, b) {
  var s = '0';
  var m = '';
  b.split('').reverse().forEach(function(e) {
    var z = m;
    a.split('').reverse().forEach(function(f) {
      s = add(s, mul[e + f] + z, '0');
      z = z + '0';
    });
    m = m + '0';
  } );
  return s;
}

function test(a, b) {
  var t0 = (new Date()).getTime();
  var r = mult(a,b);
  var t1 = (new Date()).getTime();
  var e = t1 - t0;
  console.log('mult ' + a + ' * ' + b + ' = ' + r + " (" + e + " ms)");
}

test('12345', '42');
test('9999999999', '9999999999');

```

This outputs:

```
mult 12345 * 42 = 518490 (3 ms)
mult 9999999999 * 9999999999 = 99999999980000000001 (47 ms)

```

# Answer
> 2 votes
## Python 2 (555)

I wouldn't normally answer my own challenge so quickly (or at all), but I wanted to prove it could be done. (Luckily some other answers did that before this one, but I couldn't help wanting to finish it.) There's some more golfing that could be done, but I think this is reasonable. It handles the `9999999999x9999999999` case in under 0.03s on my machine.

```
d="123456789";I=dict(zip('0'+d,d+'0'))
def r(x):return reversed(x)
def s(x):return''.join(x)
def i(x):
    try:
        h=I[x.next()]
        if h!='0':h+=s(x)
        else:h+=i(x)
        return h
    except:return'1'
def b(x,y):
    for c in'0'+d:
        if c==y:break
        x=iter(i(x))
    return x
def a(x,y):
    z=''
    for c in y:
        x=b(x,c)
        try:z+=x.next()
        except:z+='0'
    return z+s(x)
def n(x,y):
    z='0'
    for c in'0'+d:
        if c==y:break
        z=a(iter(z),x)
    return z
def o(x,y):
    x=s(x)
    l='';z=''
    for c in y:
        z=a(iter(z),l+s(n(x,c)))
        l+='0'
    return z
def m(x,y):
    return s(r(o(r(x),r(y))))

```

Example use: `m("12345","42")`

It works by doing long multiplication using string manipulations. Sometimes the variables are strings and sometimes they're iterators over strings, which makes it possible to get the first element without using an integer literal. Everything's stored with the digits reversed, so that the first element is the least significant digit.

Here's a function-by-function explanation:

* `r` and `s` are bookkeeping functions. (`r` is just an alias for `reversed`, which makes a reverse iterator, and `s` converts iterators into strings.)
* `i` increments the number in a string by 1, including cases like `39+1=40` and `99+1=100`.
* `b` adds `x` and `y`, but `y` must be only one digit. It works by incrementing `x` `y` times.
* `a` adds two numbers together that can both have multiple digits, by calling `b` for each digit in `y`.
* `n` multiplies `x` and `y`, but `y` must be only one digit. It works by adding `x` to itself `y` times.
* `o` multiplies `x` and `y`, where both arguments can have multiple digits. It uses classic long-multiplication
* `m` just converts its string inputs into reverse iterators and hands them to `o`, then reverses the result and converts it into a string.

# Answer
> 2 votes
## Scala, 470 characters

(the  are standard scala but can equivalently be replaced with `=>` if we're counting bytes)

```
def p(a: String,b: String)={type D=List[Char]
val d="0123456789".toList
def v(s: String)=s.toList.map{c⇒d.takeWhile(c.!=)}
def u(l:D, a:D):(Char,D)=l match {
case _::_::_::_::_::_::_::_::_::_::m⇒u(m,'a'::a)
case _⇒(('a'::l).zip(d).last._2,a)}
val o=(("", List[Char]())/:v(a).tails.toList.init.map{l⇒(v(b) map {_.flatMap(_⇒l.head)})++l.tail.map(_⇒Nil) reverse}.reduce(_.zipAll(_, Nil, Nil).map{t⇒t._1++t._2}))({(t,e)⇒val s=u(t._2++e,Nil);(s._1+t._1,s._2)})
u(o._2, Nil)._1+o._1}

```

Here we're emulating digits using the length of lists, being careful not to use any numeric operations - only folds, maps, zips and the like. A number is a list of these digits (order strategically reversed halfway through the computation); we multiply individual digits with `flatMap` and our rows up with `reduce`. `u` handles figuring out the carry (by directly matching against a list of \>10 elements, and recursing) and converting digits back to characters, and we use a `/:` to work our way through the stack with that. The required example completes in less than a second.

# Answer
> 2 votes
# Haskell ~~507~~ 496

This works for arbitrarily large integers. I define custom representations for the natural numbers from 0 to 18 (the largest natural number equal to the sum of two digits), and define little-endian multiplication in terms of digit\*number multiplication, which I define in terms of number+number addition, which I define in terms of digit+digit addition. I have a reduction function that expands 10--18 values into their digital decomposition. This then just reads and reverses the two strings, translates to the custom bindings, multiplies, and translates back, reversing to get the right result.

## Edit 2

I saved a few characters by creating short local aliases for multi-character commands I use more than once, as well as removing spaces and parentheses, and by replacing `(`-`)` pairs with `$` when possible.

```
data S=Z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R deriving(Enum, Ord, Eq)
p Z=id
p x=succ.p(pred x)
s Z=id
s x=pred.s(pred x)
z=s J
r[]=[]
r(x:y)|x<J=x:r y
r(x:[])=z x:[A]
r(x:y)=z x:(r$p A a:b)where(a:b)=r y
a x y=r$w(r x)(r y)
m Z _=[]
m _[]=[]
m x y=r$a y(m(pred x)y)
t[]_=[Z]
t _[]=[Z]
t(x:z)y=r$a(m x y)(Z:r(t z y))
i '0'=Z
i x=succ.i.pred$x
b Z='0'
b x=succ.b.pred$x
w[]y=y
w x[]=x
w(x:c)(y:d)=p x y:(w c d)
o=map
v=reverse
f=(o i).v
g=v.o b
main=getLine>>=putStrLn.(\[x,y]->g$t(f x)(f y)).words

```

For reference, S is the custom integer-like data type, `p` is 'plus' (digit+digit addition), `s` is subtract (for reduction), `r` is reduce (expand into digital decomposition), `a` is addition (number+number addition), `m` is multiply (digit\*number multiplication), `t` is times (number\*number multiplication), `i` is 'interpret' (convert string to list of `S`), `b` is 'back' (list of S to string), and f and g are just shortenings for golfing purposes. I didn't use numbers, even implicitly; the closest I got was using successors and predecessors, which are much higher level mathematical concepts than addition and multiplication of natural numbers.

## Edit

Forgot to include the time profile.

```
> time echo "9999999999 9999999999" | runhaskell multnonum.hs
99999999980000000001

real    0m0.246s
user    0m0.228s
sys     0m0.012s

```

Just for good measure:

```
> time echo "99999999980000000001 99999999980000000001" | runhaskell multnonum.hs
9999999996000000000599999999960000000001

real    0m0.244s
user    0m0.224s
sys     0m0.016s

```

Let's go insane!

```
> time echo "9999999996000000000599999999960000000001 9999999996000000000599999999960000000001" | runhaskell multnonum.hs
99999999920000000027999999994400000000699999999944000000002799999999920000000001

real    0m0.433s
user    0m0.424s
sys     0m0.004s

```

confirmation

# Answer
> 1 votes
# Python 2 - ~~1165, 712, 668~~ 664

```
I,T,V,N,X,J=raw_input,dict,reversed,None,zip,''.join
D='0123456789'
z,o='01'
A,B=I(),I()
r=i=""
K=map(J,X('666622222222911111551111555884444447773333333','678945672389954132987698765898967457989837654'))
P=T(X(K,map(J,X('344501110011800000440000332673322124652202211','628480244668154132507698505422648609367491852'))))
S=T(X(K,'cdef678945abi65243ed87a9cbaghcdab89egfcb6a987'))
for d in D:P[z+d]=z;S[z+d]=d
def Z(A,B,R=r):
 for a,b in V(map(N,V(z+A),V(z+B))):c=(a or z)+(b or z);s=S[min(c)+max(c)];R=Z(R,o)+T(X('abcdefghi',D))[s]if s>"?"else R+s
 return R
for a in V(A):
 j=""
 for b in V(B):r=Z(r,P[min(a+b)+max(a+b)]+i+j).lstrip(z);j+=z
 i+=z
print r if r else z

```

Note that I'm not using logical indexing like `Z = [X, Y][N == "0"]`, because this could be interpreted as a boolean casted to a numeric index.

**Ungolfed:**

```
A = raw_input()
B = raw_input()

P = {'00':'00','01':'00','02':'00','03':'00','04':'00','05':'00','06':'00','07':'00','08':'00','09':'00',
     '10':'00','11':'01','12':'02','13':'03','14':'04','15':'05','16':'06','17':'07','18':'08','19':'09',
     '20':'00','21':'02','22':'04','23':'06','24':'08','25':'10','26':'12','27':'14','28':'16','29':'18',
     '30':'00','31':'03','32':'06','33':'09','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
     '40':'00','41':'04','42':'08','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
     '50':'00','51':'05','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
     '60':'00','61':'06','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
     '70':'00','71':'07','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
     '80':'00','81':'08','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
     '90':'00','91':'09','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81',
     }
S = {'00':'0','01':'1','02':'2','03':'3','04':'4','05':'5','06':'6','07':'7','08':'8','09':'9',
     '10':'1','11':'2','12':'3','13':'4','14':'5','15':'6','16':'7','17':'8','18':'9','19':'a',
     '20':'2','21':'3','22':'4','23':'5','24':'6','25':'7','26':'8','27':'9','28':'a','29':'b',
     '30':'3','31':'4','32':'5','33':'6','34':'7','35':'8','36':'9','37':'a','38':'b','39':'c',
     '40':'4','41':'5','42':'6','43':'7','44':'8','45':'9','46':'a','47':'b','48':'c','49':'d',
     '50':'5','51':'6','52':'7','53':'8','54':'9','55':'a','56':'b','57':'c','58':'d','59':'e',
     '60':'6','61':'7','62':'8','63':'9','64':'a','65':'b','66':'c','67':'d','68':'e','69':'f',
     '70':'7','71':'8','72':'9','73':'a','74':'b','75':'c','76':'d','77':'e','78':'f','79':'g',
     '80':'8','81':'9','82':'a','83':'b','84':'c','85':'d','86':'e','87':'f','88':'g','89':'h',
     '90':'9','91':'a','92':'b','93':'c','94':'d','95':'e','96':'f','97':'g','98':'h','99':'i',
     }
L = {'a':'0','b':'1','c':'2','d':'3','e':'4','f':'5','g':'6','h':'7','i':'8'}

def strSum(A, B):
    R = ""
    for a, b in reversed(map(None, reversed("0" + A), reversed("0" + B))):
        if a == None: a = '0'
        if b == None: b = '0'
        s = S[a + b]
        if s.isdigit():
            R += s
        else:
            R = strSum(R, "1") + L[s]
    return R

i = ""
r = "0"
for a in reversed(A):
    j = ""
    for b in reversed(B):
        p = P[a + b] + i + j
        r = strSum(r, p)
        j += "0"
    i += "0"

r = r.lstrip("0")
if r == "":
    r = "0"

print r

```

---
Tags: code-golf, arithmetic, restricted-source, restricted-time
---


title: Theseus' New Ship

text:
# Question
Title: Theseus' New Ship
The *Ship of Theseus* is an old question that goes something like:

> If a ship has had all of its original parts replaced, is it still the same ship?

For this golf, we're going to slowly replace "parts" on a "ship", and see how long it takes to get a whole new ship.

### Task

A ship is comprised of at least two parts. The parts are given as an array of positive (non-zero) integers, representing the part's condition.

On each cycle, randomly choose one part from the list in a uniform fashion. That part's condition will be reduced by one. When a part's condition reaches zero, it is replaced by a new part. The new part starts with the same condition value as the original did.

On the first cycle where all parts have been replaced (at least) once, stop and output the number of cycles it took.

For example (assume I'm choosing parts randomly here):

```
2 2 3  <- starting part conditions (input)
2 1 3  <- second part reduced
2 1 2  ...
2 1 1
2 2 1  <- second part reduced to zero, replaced
1 2 1
1 2 3  <- third part replaced
1 1 3
2 1 3  <- first part replaced

```

Output for this example would be `8`, since it took eight cycles for all parts to be replaced. Exact output should differ for each run.

### I/O

The only input is the list/array of integers for part condition. The only output is a number of cycles. You can take/give these values in any of the usual ways: STDIO, function arguments/returns, etc.

### Test Cases

Since output is not fixed, you could use whatever you want to test, but here's a couple for standardization purposes:

```
1 2 3 4

617 734 248 546 780 809 917 168 130 418

19384 74801 37917 81706 67361 50163 22708 78574 39406 4051 78099 7260 2241 45333 92463 45166 68932 54318 17365 36432 71329 4258 22026 23615 44939 74894 19257 49875 39764 62550 23750 4731 54121 8386 45639 54604 77456 58661 34476 49875 35689 5311 19954 80976 9299 59229 95748 42368 13721 49790

```

# Answer
> 4 votes
# Pyth, 12 bytes

```
f!eSXOUQQtZ1

```

Demonstration.

How it works:

This is based around Pyth's infinite filter, which tests an expression with increasing inputs until it returns something truthy, then returns the input which caused this to happen. However, the expression that will be tested will not use the input value.

Instead, the expression will modify the input list by decrementing a random entry. This is accomplished via the expression `XOUQQtZ`. This means increase the index `OUQ` in the list `Q` by `tZ`. `OUQ` is a random index in the length of `Q`, and `tZ` is -1. `Q` is initialized to the input list.

After modifying `Q` in this fashion, we take its current value, which `X` returns, take its maximum entry with `eS`, and take the logical not of that value with `!`. This returns a truthy value for the first time when every element of `Q` has been reduced to `0` or below for the first time.

To ensure that the number returned will be exactly the number of times that `Q` was modified, we will start the count at `1`, indicating the the first time this is called, there has been 1 modification. To see what `Q` looks like after each iteration of the code, check out the version here.

# Answer
> 5 votes
## GolfScript (26 24 bytes) / CJam (20 18 bytes)

GolfScript:

```
~{$)*}{.,rand{(+}*((+}/,

```

Online demo

CJam (same idea but slightly different implementation):

```
q~{_mr((+_$)*}g;],

```

Online demo

Input is on stdin in the form `[2 2 3]`.

This is one of those rare occasions where GolfScript's *unfold* operator is useful. It allows us to accumulate the states which the ship passes through, and then count them at the end. Note that the array which is counted includes the initial (input) state but not the final state in which the last element has been reduced to 0.

However, although CJam doesn't have *unfold* its ability to shuffle an array uniformly for only 2 chars counts for a lot and allows it to come out on top.

# Answer
> 3 votes
# Python 3, ~~91~~ 71 bytes

20(!) bytes saved thanks to @xnor.

```
from random import*
def f(p):shuffle(p);p[0]-=1;return max(p)<1or-~f(p)

```

Recursive function calling itself with smaller piece-values until all piece-values are 0 or negative and every function returns the return value of its child + 1 and the lastly called one returns 1.

# Answer
> 1 votes
# Python 3, 175 bytes

```
import random
p,t=input().split(),0;f,r=[int(i)for i in p],[0]*len(p)
while 0 in r:
 f[random.randint(0,len(f)-1)]-=1;t+=1
 for x in range(len(f)):
  r[x]=int(f[x]<1)
print(t)

```

*Not especially well golfed*.

Try it online here

---
Tags: code-golf, random
---


title: Tallest tower from a set of digits

text:
# Question
Title: Tallest tower from a set of digits
> **Edit:** Bounty puzzle at the end of the question.

Given a set of 1-digit numbers, you should determine how tall a tower they can construct.

The digits live on a horizontal plane with a ground level where they can stand. No digit wants to be confused with a multi-digit number, so they always have an empty space on both of their sides.

```
4 2  1 9  6  8

```

A digit can be on top of another one:

```
2
6

```

or can be supported by two other diagonally below it:

```
 9
5 8

```

The bottom one(s) have to support the weight the upper one supports (if there is any), plus the upper one's weight **which is always 1**. If there are two supporters, they split the upper one's total weight evenly (50%-50%).

*The weight of every digit is 1 independent of it's value.*

If one digit supports two others it has to be able to support the sum of their corresponding weight. **A digit can support at most its numerical value.**

Some valid towers (with heights `4`, `3` and `5`):

```
            0
7           1
5    1     1 1         9 supports a total weight of 1.5 = (1+1/2)/2 + (1+1/2)/2
2   5 4    5 5
3  5 9 5  5 6 3        6 supports a total weight of 3 =  1.5 + 1.5 = (2*1+(2*1/2))/2 + (2*1+(2*1/2))/2

```

Some invalid towers:

```
1         5           The problems with the towers are (from left to right):
1  12    2 3     8      1 can't support 1+1; no space between 1 and 2;
1  5 6  1 1 1   9       1 can't support 1.5 = (1+1/2)/2 + (1+1/2)/2; 8 isn't properly supported (digits at both bottom diagonals or exactly below the 8)

```

You should write a program or function which given a list of digits as input outputs or returns the height of the highest tower constructable by using some (maybe all) of those digit.

## Input

* A list of non-negative single-digit numbers with at least one element.

## Output

* A single positive integer, the height of the highest constructable tower.
* Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

## Examples

Format is `Input list => Output number` with a possible tower on the next lines which is not part of the output.

```
[0]  =>  1

0

[0, 1, 1, 1, 1, 1]  =>  3

  0
  1
 1 1

[1, 1, 1, 1, 1, 2, 2]  =>  4

   1
   1
  1 1
 1 2 2

[0, 0, 2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9]  =>  9

0
2
2
5
5
5
7
7
9

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]  =>  9

   1
   2
   2
   3
   4
   5
  3 3
 4 4 4
5 5 5 5

[0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9]  =>  11

   0
   1
   2
   3
   4
   5
  3 3
  4 5
  5 5
 3 7 3
2 7 9 2

[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]  =>  12

 0
 1
 2
 3
 4
 5
 6
 7
4 5
6 7
8 8
9 9

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]  =>  18

      0
      1
      2
      3
      4
      5
      6
      7
      8
      9
     5 5
     6 6
     7 7
    4 8 4
   3 7 7 3
  2 6 8 6 2
 2 5 8 8 5 2
 3 9 9 9 9 3

```

This is code-golf, so the shortest entry wins.

## Bounty

I will award **100 reputation bounty** (unrelated to the already awarded one) for solving the extended problem below in polynomial time (in regard to the length of the input list) or proving that it isn't possible (assuming P!=NP). Details of the extended problem:

* input numbers can be any non-negative integers not just digits
* multi-digit numbers take up take same place as single-digit numbers
* multi-digit numbers can support they numerical value e.g. `24` can support `24`

The bounty offer has no expiry date. I will add and reward the bounty if a proof appears.

# Answer
# Python 2 - 326

Runs easily under the time limit for all the examples given, though I did sacrifice some efficiency for size, which would probably be noticeable given much larger inputs. Now that I think about it though, since only single digits numbers are allowed the largest possible tower may not be very big, and I wonder what the maximum is.

```
def S(u,c=0,w=[]):
 for(s,e)in[(len(w),lambda w,i:w[i]),(len(w)+1,lambda w,i:.5*sum(([0]+w+[0])[i:i+2]))]:
    m=u[:];l=[-1]*s
    for n in u:
     for i in range(s):
        if 0>l[i]and n>=e(w,i):m.remove(n);l[i]=n;break
    if([]==l or-1in l)==0:
     for r in S(m,c+1,[1+e(w,i)for i in range(s)]):yield r
 yield c
print max(S(sorted(input())))

```
> 10 votes

---
Tags: code-golf
---


title: Calculate digits of Pi

text:
# Question
Title: Calculate digits of Pi
This is a somewhat different task. Calculate 1024 hexadecimal digits of π, beginning at the 1024th hexadecimal place.

Formally: Your program should complete in less then 1 minute and produce the following output:

> 25d479d8f6e8def7e3fe501ab6794c3b976ce0bd04c006bac1a94fb6409f60c45e5c9ec2196a246368fb6faf3e6c53b51339b2eb3b52ec6f6dfc511f9b30952ccc814544af5ebd09bee3d004de334afd660f2807192e4bb3c0cba85745c8740fd20b5f39b9d3fbdb5579c0bd1a60320ad6a100c6402c7279679f25fefb1fa3cc8ea5e9f8db3222f83c7516dffd616b152f501ec8ad0552ab323db5fafd23876053317b483e00df829e5c57bbca6f8ca01a87562edf1769dbd542a8f6287effc3ac6732c68c4f5573695b27b0bbca58c8e1ffa35db8f011a010fa3d98fd2183b84afcb56c2dd1d35b9a53e479b6f84565d28e49bc4bfb9790e1ddf2daa4cb7e3362fb1341cee4c6e8ef20cada36774c01d07e9efe2bf11fb495dbda4dae909198eaad8e716b93d5a0d08ed1d0afc725e08e3c5b2f8e7594b78ff6e2fbf2122b648888b812900df01c4fad5ea0688fc31cd1cff191b3a8c1ad2f2f2218be0e1777ea752dfe8b021fa1e5a0cc0fb56f74e818acf3d6ce89e299b4a84fe0fd13e0b77cc43b81d2ada8d9165fa2668095770593cc7314211a1477e6ad206577b5fa86c75442f5fb9d35cfebcdaf0c7b3e89a0d6411bd3ae1e7e4900250e2d2071b35e226800bb57b8e0af2464369bf009b91e5563911d59dfa6aa78c14389d95a537f207d5ba202e5b9c5832603766295cfa911c819684e734a41b3472dca7b14a94a

The program with the shortest length wins. You have to calculate all the digits at runtime. You do not have to implement the algorithm that computes π; if your language already provides that functionality, you can use it.

# Answer
> 13 votes
**Sage, 29 char**

This isn't technically cheating, since the digits are computed at runtime. That said, it's still cheap as hell.

```
hex(floor(pi*2^8192))[1025:]

```

# Answer
> 13 votes
# Shell Utilities: 48

`curl -sL ow.ly/5u3hc|grep -Eom 1 '[a-f0-9]{1024}'`

* All output is "calculated" at runtime. (thanks to OP posting the solution)
* Runs in under a minute. (may be dependent on your internet connection speed)

# Answer
> 5 votes
## JavaScript, 536

(Linebreaks and indentation for legibility only)

```
var d='0123456789abcdef',p='',o='',l=3e3,c=0,e='length';d=d+d;
function $(n,r){return n[e]<=r?0:d.indexOf(n[r])}
function g(a,b){for(i=0,t='',s=16;i<l;i++,t+=d[~~(s/b)],s=(s%b)*16);
for(;a--;t=_(t,t,1));return t}
function _(a,b,s){for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i>=0;r=(s?
  function(k){c=k>15;return d[k]}($(a,i)+$(b,i)+c):
  function(k){c=k<0;return d[k+16]}($(a,i)-$(b,i)-c))+r,i--);return r}
for(i=0;i<l;i++,p+='2');
for(j=1;j<l;p=_(p,(o+='0')+_(_(_(g(2,8*j+1),g(1,8*j+4)),g(0,8*j+5)),g(0,8*j+6)),1),j++);
console.log(p.slice(1024,2048))

```

It takes about 25 seconds, on Google Chrome 14 on my lap-top using Intel i5 core. Can someone else golf this code? I can't golf well.. :(

Below is non-golfed. I just remove all comments and changed for loop to golfing.

Don't mention about `for(;s>=b;s-=b);s*=16;`. I changed it to `s=(s%b)*16`. :P

```
/**
Calculate PI-3 to 3000 (3e3) digits.
a : a
b : b
c : carry
d : digits
e : length
f : get from d
g : calculate (2^a)/b.
i,j, : for looping
l : length to calculate
p : pi
r,t : return value
*/
var d='0123456789abcdef',p='',o='',l=3e3,c=0,e='length';
d=d+d;//for carring

function $(n,r){return n[e]<=r?0:d.indexOf(n[r])}
/*
Calculate (2^a)/b. Assume that 2^a < b.
*/
function g(a,b){
    for(i=0,t='',s=16;i<l;i++){t+=d[~~(s/b)];for(;s>=b;s-=b);s*=16;}
    for(;a--;t=_(t,t,1));return t}
/*
Calculate a±b. (+ when s=1, - when s=0) When calculating minus, assume that 1>b>a>0.
*/
function _(a,b,s){
    for(i=(a[e]>b[e]?a[e]:b[e])-1,r='',c=0;i>=0;
        r=(s?function(k){c=k>15;return d[k]}($(a,i)+$(b,i)+c):
            function(k){c=k<0;return d[k+16]}($(a,i)-$(b,i)-c))+r,i--);return r;
}
/*
Using BBP formula. Calc when j=0...
4/1 - 2/4 - 1/5 - 1/6 = 3.22222222.... (b16)
*/
for(i=0;i<l;i++,p+='2');
//Calc when j>0
for(j=1;j<l;p=_(p,(o+='0')+_(_(_(g(2,8*j+1),g(1,8*j+4)),g(0,8*j+5)),g(0,8*j+6)),1),j++);
console.log(p.slice(1024,2048));

```

EDIT : Removed totally unused function. (Why did I keep that? :/ )

PS. First 100 digits of PI

`243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89452821e638d01377be5466cf34e90c6cc0ab`

# Answer
> 4 votes
## PHP ~~116~~ 114 bytes

```
<?for(;$g?$d=0|($$g=$g--/2*$d+($$g?:2)%$g*$f)/$g--:4613^printf($i++>257?'%04x':'',$e+$d/$f=4*$g=16384)^$e=$d%$f;);

```

This solution calculates all of pi up to 2048 hex digits, four hex digits at a time, and outputs the last half of them. Execution time is less than 5 seconds. The formula used for the calculation is the following:

```
pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + 6/13*(2 + 7/15*(2 + ... )))))))

```

The precision is obtained storing the remainders in an array, and continuing each of the 2^14 divisions incrementally.

## Python 64 bytes

```
x=p=16385
while~-p:x=p/2*x/p+2*2**8192;p-=2
print('%x'%x)[1025:]

```

Same method as above. Runs in about 0.2s.

Or as a one-liner in **73 bytes**:

```
print('%x'%reduce(lambda x,p:p/2*x/p+2*2**8192,range(16387,1,-2)))[1025:]

```

# Answer
> 3 votes
## PARI/GP-2.4, 141

```
forstep(d=1024,2047,8,y=frac(apply(x->sum(k=0,d+30,16^(d-k)/(8*k+x)),[1,4,5,6])*[4,-2,-1,-1]~);for(i=0,7,y=16*frac(y);printf("%X",floor(y))))

```

Using the Bailey–Borwein–Plouffe formula (of course).

Runs in well under a minute.

# Answer
> 3 votes
C code:

```
long ki,k,e,d=1024;
int  dig,tD=0,c,Co=0,j,js[4]  ={1,4,5,6};
double res=0.0,tres=0.0,gT,ans[4] ={0.0};
while(tD < 1024)
{while(Co<4){ j= js[Co],gT=0.0,ki= 0;
 for(; ki < d+1;ki++){ k = 8*ki+j,e= d-ki,c=1; while(e--) c = 16*c % k; gT+=((double)(c)/(double)k);}
 ans[Co] = (gT - (int)gT),++Co;}
 double gA = 4*ans[0]-2*ans[1]-ans[2]-ans[3];
 gA = (gA<0) ? gA + -1*(int)gA +1 : gA -(int)gA;
 dig=0;while(dig++ < 6 && tD++ < 1024) gA *=16, printf("%X",gA),gA -= (int)gA;
 d+=6,Co = 0;}

```

runtime = 8.06 seconds on a intel Quad core

# Answer
> 1 votes
## PARI/GP - 40 bytes

This version 'cheats' by using `\x` to display the hexadecimal digits of the result.

```
\p8197
x=Pi<<4^6;x-=x\1;x=(x<<4^6)\1
\xx

```

This version takes 87 bytes to convert to hexadecimal in the usual way.

```
\p8197
x=Pi<<4^6;x-=x\1;concat([Vec("0123456789abcdef")[n+1]|n<-digits((x<<4^6)\1,16)])

```

Both versions run in a small fraction of a second.

# Answer
> 1 votes
# Perl - 59

```
use ntheory"Pi";say substr int(Pi(3000)<<8192)->as_hex,1027

```

Less than 0.1s.

# Answer
> 0 votes
## Shell 68

### tools: bc -l, tr, cut

```
echo "scale=2468;obase=16;4*a(1)"|bc -l|tr -d '\\\n'|cut -c1027-2051

```

### Shell 64, tools: bc -l, tr, tail, differs in the rounding of the last place

```
echo "scale=2466;obase=16;4*a(1)"|bc -l|tr -d '\\\n'|tail -c1024

```

Might be considered cheating, since the knowledge how to compute PI is in 4\*a(1), and that 1 have to use scale=2466 was iteratively investigated.

Thanks to breadbox for the idea to use cut.

---
Tags: code-golf, kolmogorov-complexity, pi, restricted-time
---


title: Finding Pairs for Letters

text:
# Question
Title: Finding Pairs for Letters
You should write a program or function which given a string as input outputs or returns a string or list of the lowercase letters in the order they find their uppercase pair.

The input is a string consisting of the characters `[a-zA-Z] space` and `newline` representing a torus (rectangular grid with wrap around for rows and columns) with some of the letters `a-z` and for every lowercase letter exactly one of its uppercase equal.

Every lowercase letter has a field of view equal to `ord(letter)-97` grid steps i.e. `a=0, b=1, ... , z=25` where `0` means you can only see your own cell. Steps (and field of view) are possible in all 8 directions. At every step:

* if a lowercase letter sees its uppercase pair (e.g. `C` for `c`) it will go straight to it
* if a lowercase letter doesn't see its uppercase pair it will move to the bottom right neighbor cell wrapping around if necessary.

There can be multiple letters at the same position. They don't block each other.

You should output or return the lowercase letters in the same order they reach their uppercase pair. If multiple letters reach their pair at the same step they should be outputted in alphabetical order. If a letter newer reaches its pair it shouldn't be outputted at all.

## Input

* A string received in any reasonable way.
* Contains only letters `[a-zA-Z]` (at most one from each character; at least one pair of letters), spaces and newlines.
* Input will form a proper rectangle, i.e. there will be the same number of characters between every newline.
* Trailing newline is optional.

## Output

* A list of lowercase letters in the order they reach their pair.
* Output can be in any reasonable data-structure (string, list, array etc.) and can be outputted or returned.
* Trailing newline is optional.

## Examples

Input is all the rows between `Input:` and `Visualization:`. In visualization `*` marks all cells visited by letters. Other valid visualizations are possible as when a letter sees its pair often multiple shortest paths are possible. *Space only lines are empty below. Check correct inputs here.*

```
Input:

D
  d Aa

Visualization:
  *
D* *
  d Aa
*
 *
Output: da
Step numbers: 2 5

Input:

W      B
    A
  b

      a
  w

Visualization:
**     *
W *    B
   *A
  b *
   * *
    * a
  w  * *
**    *
Output: wb
Step numbers: 3 6

Input:

     A

      a

Visualization:
*  *****
**  ****
***  A**
****   *
*****
 *****a
  ******
Output: a
Step numbers: 39

Input:

   i
  f     d

    DI  F
Visualization:

   i
  f *   d
   * *   *
*   **
 ***DI**F
Output: idf
Step numbers: 4 6 6

Input:

  g                 a

        G               W

                    j
             w

                                         A      J

Visualization:
       *         *         * *       *         *
        *         *         * *       *         *
         *         *         * *       *         *
* g       *         a         * *       *
 * *       *         *         * *       *
  * *       *         *         * *       *
   * ***G    *     *****W        * *       *
    *         *   *     *         * *       *
     *         * *       *         * *       *
      *         *         *         * *       *
       *       * *         *         * *       *
        *     *   * j       *         * *       *
         *   w     * *       *         * *       *
*         *         * *       *         * *
 *         *         * *       *         * *
  *         *         * *       *         * *
   *         *         * *       *       A * ***J
    *         *         * *       *         *
     *         *         * *       *         *
      *         *         * *       *         *
Output: gwj
Step numbers: 6 11 28

```

This is code-golf so the shortest entry wins.

# Answer
> 1 votes
# Ruby ~~319 313 310 304 287~~ 283

```
F=->s{l=s.split ?\n
b=[]
t={}
[*0...m=l.size].product([*0...n=l[0].size]).map{|y,x|c=l[y][x]
c!=' '&&c>?Z?b<<[c,y,x]:t[c.downcase]=[y,x]}
b.map{|q|c,y,x=q
u,i=t[c]
(m*n).times{|w|e=([u-(y+w)%m,i-(x+w)%n].map &:abs).max
e>c.ord-97||q<<w+e}
q[3]&&[q[3],q[0]]}.compact.sort.map{|a,b|b}}

```

This is a function that takes as input a string (without trailing newline) and returns an array of the lowercase letters in the correct order.

Here's a version you can run online with tests: http://ideone.com/5jiwLq

I've made a lot of modifications to the code. The history of modifications is available here.

Here's the indented and annotated version to make it easier to see what's going on (also available online):

```
F=->s{
  l=s.split ?\n
  m=l.size
  n=l[0].size

  # Make an array with lowercase letters and their coords (`b`)
  # Make a hash that for each target (uppercase letter) holds
  # its coordinates
  b=[]
  t={}
  [*0...m].product([*0...n]).map{|y,x|
    c=l[y][x]
    c!=' '&&(c>?Z?b<<[c,y,x]:t[c.downcase]=[y,x])
  }

  # `l` is a function that, given an array of the form
  # [lowercase_letter, y-coord, x-coord] will append to that array
  # the number of steps required for the letter to reach its
  # uppercase correspondent
  l=->q{
    c,y,x=q
    u,i=t[c]
    d=c.ord-97
    (m*n).times{|w|
      e=([u-y,i-x].map &:abs).max
      e<=d&&q<<w+e
      y=(y+1)%m
      x=(x+1)%n
    }
  }

  # apply function `l` to each of the lowercase letters...
  b.map &l

  # ...then sort accordingly and return the array
  b.map{|x|[x[3],x[0]]}.select{|a,b|a}.sort.map{|a,b|b}
}

```

---
Tags: code-golf, grid, simulation
---


title: Almost Equilaterial Heronian Triangles

text:
# Question
Title: Almost Equilaterial Heronian Triangles
An *Almost Equilateral Heronian Triangle* is a triangle with integer lengths of the form `n-1`, `n`, and `n+1` and also has integer area. The first few are:

```
 3,  4,  5 ->    6
13, 14, 15 ->   84
51, 52, 53 -> 1170

```

**Quest**: Generate the shortest program that outputs the `n`th such triple. (Hint: this is a known sequence).

Winner will be selected on May 2, 2014.

# Answer
### APL, 15 14 charaters

```
0 1 2+⌊⎕*⍨2+√3

```

Same approach as alephalpha's solution but uses floor instead of the correction term.

Thank you to algorithmshark for pointing out that the commute operator saves one char.
> 6 votes

# Answer
# Mathematica, ~~26, 22, 16~~ 18 chars

```
{0,1,2}+⌊(2+√3)^n⌋

```
> 8 votes

# Answer
## GolfScript (24 21 chars)

```
2 4@~{.4*@-}*;.(\.)]p

```

Takes input on stdin, gives output to stdout in the form

```
[3 4 5]

```

Online demo

Note that I've assumed that the 0th element of the sequence is `[1 2 3]` (with area 0), which I think is consistent with OEIS A003500.

With thanks to Howard for a 3-char saving.
> 5 votes

# Answer
# GNU dc, 30 19 bytes

```
9k3v2+?^0k1/p1+p1+p

```

This uses the same trick as @Howard's APL answer so only one term has to be calculated. Takes input for n from stdin.

Output:

```
$ dc -e '9k3v2+?^0k1/p1+p1+p' <<< 1
3
4
5
$ dc -e '9k3v2+?^0k1/p1+p1+p' <<< 2
13
14
15
$ dc -e '9k3v2+?^0k1/p1+p1+p' <<< 3
51
52
53
$

```
> 2 votes

# Answer
## Python 77

Quite a verbose implementation in Python

```
[(a-1,a,a+1)for a in(int((2+3**.5)**t+(2-3**.5)**t+.1)for t in range(N))][-1]

```
> 1 votes

# Answer
# Python 3, 83 characters

```
f=lambda t:4*f(t-1)-f(t-2)if t>2 else(4,14)[t-1];n=f(int(input()));print(n-1,n,n+1)

```

This uses a recursive solution, taking advantage of the fact that (quote from Wikipedia):

> Subsequent values of n can be found by multiplying the previous value by 4, then subtracting the value prior to that one (52 = 4 × 14 − 4, 194 = 4 × 52 − 14, etc.)
> 1 votes

# Answer
# JavaScript (ECMAScript 6) - 52 Characters

```
f=x=>x?--x?4*f(x)-f(x-1):4:2
g=x=>[a=f(x)-1,a+1,a+2]

```

Defines a recursive function `f` which returns the nth term and a function `g` which returns an array containing the corresponding triple.

# JavaScript - 41 Characters

```
for(a=2,b=4;--x;)b=-a+4*(a=b);[a-1,a,a+1]

```

Expects the term to be calculated to be stored in the global variable `x` and outputs the triple to the console.
> 1 votes

# Answer
# CJam, 13 bytes

```
3,3mq))ri#if+p

```

The first version of CJam is 10 days older than this challenge, but I don't know if all of the features I'm using have been present back then. The challenge is officially closed anyway though, so...

Test it here.

## Explanation

```
3mq            e# Push √3.
   ))          e# Increment twice.
     ri        e# Read input and convert to integer.
       #       e# Raise 2+√3 to that power.
        i      e# Convert to integer, truncating the result.
         3,    e# Push [0 1 2]
           f+  e# Add the previous number to each of these.
             p e# Pretty-print the result.

```
> 1 votes

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


title: Determine length of bitstring

text:
# Question
Title: Determine length of bitstring
Optimize the following function for **number of tokens**:

```
int length(int x)
{
    switch (x)
    {
    case 1: return 1;
    case 3: return 2;
    case 7: return 3;
    case 15: return 4;
    case 31: return 5;
    case 63: return 6;
    case 127: return 7;
    case 255: return 8;
    case 511: return 9;
    case 1023: return 10;
    case 2047: return 11;
    default: return 0;
    }
}

```

No additional cases besides the 11 shown above need to be handled. The default case will never occur (but Java needs one, or else it does not compile). Any programming language is allowed. Whole programs are also allowed.

If you embed another language inside strings, the tokens in the embedded language count as well.

**The baseline is 53 tokens**, since separators don't seem to count in . Have fun!

# Answer
# Pyth, 4 tokens

```
slhQ

```

Exact same algorithm as my CJam solution.

Tokens:

```
s            int(
 l               log2(
  h                   1 +
   Q                  eval(raw_input()) ))

```

Try it online here
> 2 votes

# Answer
# gcc, 4 tokens

```
# define length __builtin_popcount

```
> 2 votes

# Answer
# J, 3 tokens

```
#@:#:

```
* `#:`: binary array (`5 -> 1 0 1`)
* `@:`: Atop: (`f@:g x -> f(g(x))`)
* `#`: Lenght (`# 1 0 1 -> 3`)
> 2 votes

# Answer
# CJam, 5 tokens

This is a simple equation, where y = log2(x + 1)

```
ri)2mL

```

Tokens:

```
r           e# Read input token as string
 i          e# Convert to integer
  )         e# Increment it by 1
   2        e# This serves as the base of the log
    mL      e# Log the first number in the base of the second number. i.e. ri) log 2

```

Try it here
> 1 votes

# Answer
# Java, 5 tokens

```
x -> +" \1 \2   \3       \4               \5                               \6                                                               \7                                                                                \10                                                                                \11                                                                                \12                                                                                \13".charAt(x)

```
1. x
2. +
3. string
4. charAt
5. x
> 1 votes

# Answer
# Python 2, 7 tokens

This function passes the tests, but is not a reliable substitute for log2.

```
lambda x: len(bin(x))-2

```
> 0 votes

# Answer
# Clip 10, 4 tokens

```
lb2n

```

## Explanation

```
   n  .- the numeric value of the input -.
 b2   .- convert to binary              -.
l     .- length; i.e., number of digits -.

```
> 0 votes

---
Tags: number, atomic-code-golf
---


title: Is that word Feminine or Masculine?

text:
# Question
Title: Is that word Feminine or Masculine?
Write a program or function that takes in a single string containing only lowercase a-z, and prints or returns a **truthy** value if the word is the **feminine** version of the thing it represents and a **falsy** value if it is the **masculine** version. For example, `hen` is the feminine version for chicken and `rooster` is the masculine version, so `hen` might produce `1` and `rooster` might produce `0`.

Doing this for *all* English words that reflect gender would of course be way too unwieldy. Your program/function only needs to support 20 masculine/feminine pairs. Below are five sets of 10 masculine/feminine pairs, categorized by topic. **Choose any two of the sets; the 20 total pairs in these two sets are the 40 words your program/function must work for.**

(format is `masculine_version feminine_version`)

1. General

```
he she
him her
man woman
boy girl
male female
masculine feminine
guy gal
lad lass
mister miss
sir madam

```
2. Familial

```
father mother
dad mom
pa ma
son daughter
brother sister
husband wife
grandfather grandmother
grandpa grandma
uncle aunt
nephew niece

```
3. Animal

```
lion lioness
rooster hen
stallion mare
bull cow
drake duck
boar sow
buck doe
ram ewe
gander goose
billy nanny

```
4. Royal

```
king queen
prince princess
emperor empress
duke duchess
marquess marchioness
earl countess
baron baroness
baronet baronetess
lord lady
knight dame

```
5. Fantastical

```
wizard witch
giant giantess
incubus succubus
nidorino nidorina
nidoking nidoqueen
ents entwives
hanuvoite inimeite
centaur centaurides
merman mermaid
khal khaleesi

```

So, for example, you might choose the General and Familial categories. Then any input from `he` to `sir` or `father` to `nephew` would produce a falsy value, and any input from `she` to `madam` or `mother` to `niece` would produce a truthy value.

The values don't all have to be the same truthy/falsy type, e.g. `he` might produce `0` but `sir` might produce `false`. You may assume only the 40 specific lowercase a-z words from your two selected categories are ever input.

**The shortest answer in bytes wins. Tiebreaker is earlier post.**

(This challenge is not meant to correlate with or make statements about any current gender-based social issues.)

# Answer
> 9 votes
# Retina, 26 bytes (sets 4, 5)

```
[^u]es|ee|m.i|y|^...c|d.*a

```

Retina is @MartinBüttner's regex language. I haven't used anything specific to .NET regexes, so you can test the regex at Regex101 here. Alternatively you can use Retina's grep `G` mode like so:

```
G`[^u]es|ee|m.i|y|^...c|d.*a

```

and pipe in a file with one word per line for batch testing.

Retina outputs the number of matches by default, giving us our truthy/falsy value. The rule "the values don't all have to be the same truthy/falsy type" is pretty important though since `marchioness` matches twice, giving an output of 2.

(Using the mod-chaining method from the previous male/female question seems to be shorter in CJam, but I'll let someone else do that)

# Answer
> 3 votes
# Retina, ~~39~~ 32 bytes (sets 2, 4)

Accounting for `marquess` was annoying, since using `ma` was the best way to get some of the feminines.

```
[^u]es|ma$|mo|y|[mie]e|wi|ter|au

```

Try it here

Thanks to Sp3000 for his golf suggestion.

# Answer
> 2 votes
# Retina, 28 bytes (sets 3,4)

```
w|[mhorse]e|[^u]es|duc|[dn]y

```

Retina uses .NET regex, but any flavor should work. Test it at Regex101.

---
Tags: code-golf, string, decision-problem, regular-expression
---


# Question
Title: Convert a fraction to a repeated decimal
Almost the polar opposite if this challenge, and I suspect it will be slightly easier.

Your task is to take two integers in the format `a/b` (Forming a rational number) then output the number in decimal exactly.

For example, if you were to input `1/3`, it would output:

```
0.33333333333333333

```

And would keep on printing 3s until the end of time, with an optional leading 0. (You could also print *one* character per line if and *only if* your language does not allow printing on the same line.)

The behaviour for `x/0` will be undefined. For a number that looks like it doesn't repeat (Like, say `5/4`) it actually does repeat. Either of the following two forms would be acceptable for `5/4`:

```
1.25000000000000000
1.24999999999999999

```

(The same with whole numbers, `1.9999999` or `2.000000`)

The fraction may not be in its simplest form, and `a` or `b` may be negative (Note `-a/b = -(a/b)`, `-a/-b = a/b`, `a/-b = -a/b`, and `-.6249999` is invalid, but `-0.6249999` is acceptable, but you still can use.

# Answer
> 2 votes
# CJam, ~~38~~ 37 bytes

```
l'/%:i2*~*0<'-*o:Dmd\zo'.{oA*Dmd\z1}g

```

### How it works

```
l     e# Read line from STDIN.            STACK '17/-13'
'/%   e# Split at '/'.                    STACK ['17' '-13']
:i    e# Cast each element to int.        STACK [17 -13]
2*~   e# Duplicate and dump the array.    STACK 17 -13 17 -13
*     e# Multiply.                        STACK 17 -13 -221
0<    e# Compare with zero.               STACK 17 -13 1
'-*o  e# Print '-' that many times.       STACK 17 -13
:D    e# Save the topmost integer in D.   STACK 17 -13
md    e# Perform modular division.        STACK -1 4
\z    e# Swap and take absolute value.    STACK 4 1
o'.   e# Print and push '.'.              STACK 4 '.'
{     e# do:
  o   e#   Print.                         STACK 4
  A*  e#   Multiply by 10.                STACK 40
  Dmd e#   Divide modulo D.               STACK -3 1
  \z  e#   Swap and take absolute value.  STACK 1 3
  o   e#   Print.                         STACK 1
1}g   e# while(1)

```

# Answer
> 6 votes
# C, 108 ~~79~~

**Edit** Modified to work with negative numbers.

Input from stdin. Old K&R style.

```
main(a,b){char*s="-%d.";scanf("%d/%d",&a,&b);for(a*b<0?(a<0?a=-a:(b=-b)):++s;printf(s,a/b);s="%d")a=a%b*10;}

```

# Answer
> 4 votes
# Ruby, ~~83~~ ~~69~~ ~~102~~ ~~91~~ 89 bytes

```
->s{a,b=s.scan(/\d+/).map &:to_i
eval(s+?r)<0&&$><<?-
$><<a/b<<?.
loop{a=a%b*10
$><<a/b}}

```

Simple implementation of manual integer division based on the computer's integer division.

Thanks to @blutorange for the help in golfing.

Edit: Fixed the solution to include negative numbers.

# Answer
> 2 votes
# Java, ~~177~~ ~~176~~ 170

```
s->{try{int x=new Integer(s.split("/")[0]),y=new Integer(s.split("/")[1]),z=1;for(;;x=x%y*10,Thread.sleep(999))System.out.print(x/y+(z-->0?".":""));}catch(Exception e){}}

```

The algorithm is straightforward; the tricky part was getting the printing to work. In the end, I had the computer sleep for a second between each step so it could print.

## Expanded, runnable version

```
public class RepeatedDecimal {
    public static void main(String[] args) {
        java.util.function.Consumer<String> f = s -> {
                try {
                    int x = new Integer(s.split("/")[0]),
                        y = new Integer(s.split("/")[1]),
                        z = 1;
                    for (;; x = x % y * 10, Thread.sleep(999)) {
                        System.out.print(x / y + (z-- > 0 ? "." : ""));
                    }
                } catch (Exception e) { }
                };

        f.accept("5/7");
    }
}

```

# Answer
> 2 votes
# R, ~~103~~ ~~137~~ ~~109~~ 103

Bit happier with this now. Using scan with a separator save a lot of bytes. May still have some room for improvement. Replaced `<-` with `=`. Haven't always had the best of luck with this, but it worked this time.

```
cat(if(prod(i=scan(sep='/'))<0)'-',(n=(i=abs(i))[1])%/%(d=i[2]),'.',sep='');repeat cat((n=n%%d*10)%/%d)

```

Test runs

```
> cat(if(prod(i=scan(sep='/'))<0)'-',(n=(i=abs(i))[1])%/%(d=i[2]),'.',sep='');repeat cat((n=n%%d*10)%/%d)
1: -1/3
3:
Read 2 items
-0.33333333333333333333...
> cat(if(prod(i=scan(sep='/'))<0)'-',(n=(i=abs(i))[1])%/%(d=i[2]),'.',sep='');repeat cat((n=n%%d*10)%/%d)
1: -5/-4
3:
Read 2 items
1.250000000000000000000...

```

# Answer
> 1 votes
# Python 3, ~~107~~ 115 bytes

```
a,b=map(int,input().split("/"))
print(("%.1f"%(a/b))[:-1],end="")
b=abs(b)
while 1:a=abs(a)%b*10;print(a//b,end="")

```

Pretty straightforward:

* Input the numerator and denominator
* Output the the quotient with 1 digit after the decimal point, then take off the last digit (e.g. `-1/3` -\> `-0.`)
* Take absolute values\*
* Loop:
    + Numerator is remainder after dividing out denominator
    + Multiply numerator by 10
    + Output integer quotient as next digit

* (Though the calculation for `a` was moved inside the loop to save a few bytes.)

**Edit:** Fixed bug with negative fractions \> -1.

# Answer
> 0 votes
# Python 2.7, 209 bytes

```
from sys import*;m,o=1,lambda x:stdout.write(str(x));a,b=[int(x)for x in argv[1].split('/')]
o(str(a*b)[0]);a,b=abs(a),abs(b);o('0'*(b>a))
while 1:
 while not((m*a)/b):o('0.'[m==1]);m*=10
 o((m*a)/b);a=(m*a)%b

```

## edit:

Now outputs all characters on the same line, as asked.

## edit2:

Now reads the fraction from commandline argument, as requested :)

---
Tags: code-golf, rational-numbers
---


title: Maze Generation

text:
# Question
Title: Maze Generation
I know there is an (old) thread similar to this (here), but I'd like to reboot it with some modifications.

The goal: generate a random-*looking* maze using an algorithm of your choice, then output the maze graphically (printing counts).

* The width and height are determined by you.
* There should be at least one path from at least one entrance to at least one exit.
* The format of the maze (how you display it, mark entrance(s) or exit(s)) is up to you as well.
* The prettier, the better.
* Trivial mazes (e.g. blank mazes, lattice mazes, mazes of size 1x1) are discouraged.
* Cycles in the maze are allowed and, are encouraged, if the result is reasonable.
* Language abuse encouraged.
* The maze should look reasonably random (but a completely deterministic (e.g. chaotic) algorithm that generates this is fine too).

Edit: the main focus here is on making the smallest possible implementation. However, I want to allow some leeway within that constraint to encourage shininess. I have deliberately left exactly what "features" the maze has open-ended, but as a rough guideline you should try to pack the most amount of bang into the least lexical buck.

# Answer
# C: 265 253 Bytes

```
#define f(v)for(v=0;v<k;++v)
#define d(q,n)case q:r(c+n,c+2*n);
z[4225],i,j,k=65;r(p,c){if(!z[c]){z[p]=z[c]=1;f(p)switch(rand()%4){d(0,-k)d(1,k)d(2,-1)d(3,1)}}}main(){f(i)z[i]=z[i+4160]=z[i*k]=z[i*k+64]=z[4157]=1;r(67,132);f(i)f(j)putchar(33-z[i*k+j]);}

```

(Requires 65-character terminal) Generates a relatively random 31x31 maze with one guaranteed path from the entrance to exit.

Example output (with simulated 65-character terminal):

```
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !     !       !   !       !     !           !             !   !
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! !
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! !
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! !
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! !
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! !
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! !
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! !
 !           !   !       ! !             !   !     !     !     !
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!!
 ! !     ! !   !     !   ! !           !   !       ! !         !
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! !
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! !
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! !
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! !
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! !
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! !
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! !
 !             !   ! !   !       ! !     !   ! !             ! !
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! !
 !               !   !   !       !         !   !     !   !     !
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! !
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! !
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!!
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   !
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! !
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! !
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! !
 !         ! !           !   !       ! ! !     !   ! !       ! !
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! !
 !         !     !     ! ! !       !   !     ! !     !         !
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!!
 ! !     !     !   ! !   !       ! !       ! !       !         !
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! !
 !     !     ! !   !   ! !     ! !       !   ! !     !         !
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! !
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   !
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!!
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! !
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! !
 !       !         !     ! ! ! !   !   !     ! !   !       !   !
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!!
 !   !         ! !   !       ! !           ! !   !             !
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! !
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               !
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! !
 ! !   !   ! !   !       !   !   !   !         ! !         !   !
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!!
 !     !   !   !   !       !       !       !   !     !       ! !
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! !
 !           !     ! !   !   !   !           !   !   !     !   !
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! !
 ! !     !       ! !     !     !     !         ! !       !   ! !
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! !
 !   !     !   !   !   ! !       ! !         !   ! !         ! !
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! !
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! !
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! !
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! !
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! !
 ! !                     !         !               !           !
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !

```
> 10 votes

# Answer
## Mathematica, ~~144~~ 132 bytes

Since Inception, we all know the most efficient way to draw a maze.

```
c=0;Graphics@Most[Join@@{Circle[{0,0},i,{a=c-(r=Random[](d=2Pi-1/i)&)[],a+d}],Line[{{i},{i+1}}.{{Cos[c=a+r[]],Sin@c}}]}~Table~{i,9}]

```

Ungolfed and example output:

Of course, the lines are the walls. You're the minotaur who starts in the centre and needs to get out.
> 34 votes

# Answer
# C: 364 Bytes

```
#define I int
m[1600],i=0,r;f(I x,I y,I l){m[80*y+x]|=l;I d[]={x-1,y,2,1,x+1,y,1,2,x,y-1,8,4,x,y+1,4,8},
s[]={5,5,5,5},j=0;for(;j<4;){L:r=rand()%4;for(I k=0;k<4;)if(s[k++]==r)goto L;s[j]=r;I*p=d+
4*s[j++],X=p[0],Y=p[1];if(!(X<0|X>79|Y<0|Y>19|m[80*Y+X])){f(X,Y,p[2]);m[80*y+x]|=p[3];}}}
main(){f(0,0,4);m[9]|=4;for(;i<1600;)putchar("#5FMP<HJR;IK:9LN"[m[i++]]+128);}

```

Note: in the above, I added newlines to make it fit on the page. Expected output (on 80-character terminal) (note start and end at top left):
> 33 votes

# Answer
# Mathematica, ~~134~~ 130 chars

```
Graph[Range@273,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=GridGraph@{13,21},c@#=#]}]&@1][[2,1]],Options@g]

```

---

In fact, we can use this algorithm to generate a maze from any (undirected) graph.

For example, generate a maze from the 8\*8 knight's tour graph (`KnightTourGraph[8,8]`):

```
Graph[Range@64,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=KnightTourGraph[8,8],c@#=#]}]&@1][[2,1]],Options@g]

```
> 24 votes

# Answer
# Bash, 53 50 bytes

```
w=(╱ ╲);while :;do echo -n ${w[RANDOM%2]};done

```

Similar idea to the C64 code. Uses Unicode characters as the slashes because they look much nicer in a terminal that supports Unicode. Sample output on OS X Terminal (Menlo font):
> 13 votes

# Answer
# JavaScript (ES6), 174

This is the maze builder I used in this other challenge, just golfed. It's a function with 2 parameters: rows and columns. The maze is totally connected with no loops, so any location can be the starting or ending point.

```
(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}

```

*Example*

```
f(7,10)

```

*Output*

```
,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
,8, , , ,8, , , , , ,8, , , , , , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8,8,8,8,8,8,8, ,8, ,8,
,8, , , ,8, , , ,8, , , ,8, , , , , ,8, ,8,
,8, ,8,8,8, ,8,8,8,8,8, ,8, ,8,8,8,8,8, ,8,
,8, ,8, , , , , ,8, ,8, ,8, ,8, , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8, ,8, ,8, ,8,8,8,8,8,
,8, ,8, ,8, , , ,8, , , , , ,8, ,8, , , ,8,
,8, ,8, ,8, ,8,8,8,8,8,8,8,8,8, ,8, ,8,8,8,
,8, ,8, ,8, , , , , , , ,8, , , ,8, , , ,8,
,8, ,8, ,8,8,8,8,8,8,8, ,8,8,8, ,8,8,8, ,8,
,8, ,8, , , , , , , ,8, , , ,8, , , , , ,8,
,8, ,8,8,8,8,8,8,8,8,8,8,8, ,8,8,8,8,8, ,8,
,8, , , , , , , , , , , , , ,8, , , , , ,8,
,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8

```

**Test**

```
f=
(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}

function update() {
  O.textContent='';
  [r,c]=I.value.match(/\d+/g)
  O.textContent=f(r,c)
}

update()
```

```
pre { line-height: 0.8em }
```

```
Rows,Columns <input id=I oninput='update()' value='8,12'>
<pre id=O></pre>
```
> 9 votes

# Answer
# ZX Basic - 54 characters

```
a$="/\":for i=1 to 24*32:print a$(1+int(rnd*2));:next

```

Here is the maze showing a route through it (spaces between lines)

and a small snippet from when I first did this (several years ago), and spent a bit of time doing better graphics.
> 8 votes

# Answer
# BBC BASIC, 18 Bytes

An improvement in length on the 23-byte C64 infinite loop version by @nneonneo. VDU sends a single character to the VDU controller: either 2+1\*45=ASCII 47 `/` or 2+2\*45=ASCII 92 `\`

```
  VDU2+RND(2)*45:RUN

```

# BBC BASIC, 35 Bytes /  ~~107~~ 95 Bytes

35 bytes is just for the last line, which gives a 25 row maze in 40 column layout. MODE1 ensures that no extra space is left between lines. The remainder of the program is optional and improves the formatting. The VDU23 statements redefine the font for characters 47 and 92 (8 bytes forming an 8x8 bitmap.) I include a light pixel in all four corners to stop straight runs from getting pinched off. The side effect of this is that a dot appears in the empty diamonds. 107 bytes total including 2 newlines.

```
  VDU23,47,131,7,14,28,56,112,224,193
  VDU23,92,193,224,112,56,28,14,7,131
  MODE9FORa=0TO999VDU2+RND(2)*45:NEXT

```

**Edit** this program can be shortened to 95 bytes by encoding some of the 8 bit VDU codes into 16 bit small endian values (denoted by a semicolon after them instead of a comma) and representing the MODE statement as a pair of VDU codes, as follows.

```
VDU23,47,1923;7182;28728;49632;23,92,57537;14448;3612;33543;22,9:FORa=0TO999VDU2+RND(2)*45:NEXT

```

**Output**

Using BBC Basic for Windows from bbcbasic.co.uk

**Last line only, 35 bytes**

**Whole program, ~~107~~ 95 bytes**

As I commented on @Brian's answer, the slash splits the square into 2 dark triangles, each of which has exactly 2 entrances/exits. This guarantees a (trivial, unbranched) path from any point on the edge of the maze to some other point on the edge of the maze. Many of these are very short, but there always seem to be a few long ones. Of course, in the middle of the maze there are also some loops.

As other answers have not mentioned it, I'd like to take a good look at the light areas. These are bounded by dark areas, therefore as a corollary to the statement made above, a light area bounded externally by N dark areas touches the edge of the field at N (exactly as many) points. Therefore some fairly large light areas occur, and these form interesting, branched mazes.

In the example below, you can see the raw output (monochrome) from my program. Below that (using Windows Paint) I have coloured the two longest dark areas in blue. Then I coloured the largest light area in yellow, and the two areas bounded by blue in red and green. The yellow, green (and even the red) mazes are quite interesting and nontrivial.

# EDIT - Automatic picking of mazes and selection of starts/ends

For one more line (59 characters) the program can automatically pick out up to 6 mazes by choosing squares at random and flood filling in colours red,green,yellow,blue,magenta and cyan. It does not always find a full 6, because if it picks a random square that has already been coloured it does nothing.

The rest of the code below picks out a start for each colour by scanning each column from top to bottom and left to right, and picking the first square it encounters. It picks an end by scanning in the opposite direction.

This produces a set of colourful, intertwined mazes. Sometimes they are so intertwined it looks like the mazes must cross somewhere. But of course, they don't!

**Additional code and output 59+187=246 additional characters to be added to the end of the original program (for enhancement beyond question spec.)**

```
  GCOL135FORa=1TO6GCOLa FILLRND(40)*32-16,RND(25)*32+208:NEXT   :REM set background to grey so fill can identify. For each colour 1 to 6, pick a point in the centre of a character and flood fill (characters are logically 32x32 although they are physically only 8x8 pixels.)
  f=126:g=126                                                   :REM flags 1111110 to indicate which starts and ends have not been allocated yet
  FORx=0TO39FORy=0TO24                                          :REM maze is 40x25. There is some blank space at the bottom of the screen (32 rows total)
  p=POINT(x*32+16,1008-y*32)                                    :REM check start point. Text origin is at top of screen, Graphics origin is at bottom, 1280x1024 logical. therefore y offset is 1024-32/2=1008.
  IFf AND2^p f=f-2^p:VDU31,x,y,17,p,79                          :REM if start for colour P has not been allocated yet, allocate it now. VDU31,X,Y go to that square. VDU 17,p select text colour. VDU 79 print an "O"
  p=POINT(1264-x*32,240+y*32)                                   :REM check end point
  IFg AND2^p g=g-2^p:VDU31,39-x,24-y,17,p,79                    :REM if end for colour P has not been allocated yet, allocate it now.
  NEXT:NEXT
  VDU31;26                                                      :REM get the cursor off the board. Move to (0,26). Semicolon used instead of comma here indicating that 31 is a 16 bit small endian value, equivalent to VDU31,0,26 or PRINTTAB(0,26)

```
> 8 votes

# Answer
# C: 235 Bytes

```
#define P(X,Y)M[(Y+40)*80+X+40]=rand()%49/6;
#define B(X,Y)P(X,Y)P(Y,X)
M[6400],r,i;main(){for(i=0;i<40;i+=2){int x=i,y=0,e=1-x;while(x>=y)
{B(x,y)B(-x,y)B(-x,-y)B(x,-y)++y;e+=e<0?2*y+1:2*(y-x--);}}for(i=0;
i<6400;)putchar(64>>!M[i++]);}

```

Note: in the above, I added newlines to make it fit on the page. Expected output (on 80-character terminal):

I regret this isn't a very hard maze (in fact, no backtracking to inner rings is required (and you should be able to find a path from the perimeter to the center trivially). However, it has a nice implementation of Bresenham's circle drawing algorithm at its core.
> 7 votes

# Answer
I helped my kid to do this, to learn a bit of programming: http://jsfiddle.net/fs2000/4KLUC/34/ how do you like it?
> 6 votes

# Answer
# Commodore 64 BASIC - 38 bytes

```
10 PRINT CHR$(205.5+RND(1)); : GOTO 10

```

This is not my invention, I am simply repeating a very beautiful and short program from days gone past. In fact, there is an entire book named `10 PRINT CHR$(205.5+RND(1)); : GOTO 10` celebrating this piece of code!

You can see the output on this YouTube video; here's a screencap:

Here at this StackOverflow question are more implementations of this maze-generator program. The shortest implementation of the program is the following 23-byte C64 BASIC program posted by that question's author:

```
1?cH(109.5+rN(1));:gO1

```

where lowercase letters are entered as-is, and uppercase letters are entered using the Shift key (these have different appearances on an actual C64 screen).
> 6 votes

# Answer
## Java : 700

Here's a recursive wall adder. The algorithm is outlined on this site:

```
public class Z{int i,j,u=20,v=u,g[][]=new int[v][u];public static void main(String[]a){new Z().d(0,0,20,20,0).p();}int q(int m){return(int)(Math.random()*m);}<T>void z(T m){System.out.print(m);}void p(){for(i=0;i++<u*2;z("_"));for(i=0;i<v;i++){z("\n|");for(j=0;j<u;j++){boolean b=i+2>v,s=g[i][j]%2>0||b;z(s?"_":" ");z(g[i][j]>1||j+2>u?"|":s&(j+1<u&&g[i][j+1]%2>0||b)?"_":" ");}}}Z d(int x,int y,int w,int h,int o){int a=x,b=y,c=a,d=b,e,f;boolean t=o<1;if(t){b+=q(h-2);c+=q(w);}else{a+=q(w-2);d+=q(h);}for(i=t?w:h;i-->0;j=t?a++:b++)if(a!=c&&b!=d)g[b][a]|=t?1:2;e=t?w:a-x+1;f=t?b-y+1:h;if(e>2&&f>2)d(x,y,e,f,e<f?0:1);e=t?w:x+w-a-1;f=t?y+h-b-1:h;if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);return this;}}

```

Basically, it splits each rectangle in two with a wall (and passage), then splits those in two, etc. It generates a "perfect" maze - one with no cycles - that has a path from every point to every other point. Plenty of dead ends, so it's not "trivial" in any sense for larger mazes.

So, the entrance and exit can be decided arbitrarily. If I have to choose one, It'll just say top/left and bottom/right.

It's drawn in double-width ascii, so it's a good idea to pipe output to a file if you're doing one of any size. Here's a 20x20 in console:

And a 100x100 in notepad++ (I had to zoom out to get ti all, so it's somewhat... *small*):

Code with line breaks:

```
public class Z{
    int i,j,u=20,v=u,g[][]=new int[v][u];
    public static void main(String[]a){
        new Z().d(0,0,20,20,0).p();
    }

    int q(int m){return(int)(Math.random()*m);}
    <T>void z(T m){System.out.print(m);}

    void p(){
        for(i=0;i++<u*2;z("_"));
        for(i=0;i<v;i++){
            z("\n|");
            for(j=0;j<u;j++){
                boolean b=i+2>v,s=g[i][j]%2>0||b;
                z(s?"_":" ");
                z(g[i][j]>1||j+2>u?"|":s&(j+1<u&&g[i][j+1]%2>0||b)?"_":" ");
            }
        }
    }

    Z d(int x,int y,int w,int h,int o){
        int a=x,b=y,c=a,d=b,e,f;
        boolean t=o<1;
        if(t){
            b+=q(h-2);
            c+=q(w);
            }
        else{
            a+=q(w-2);
            d+=q(h);
        }

        for(i=t?w:h;i-->0;j=t?a++:b++)
            if(a!=c&&b!=d)
                g[b][a]|=t?1:2;

        e=t?w:a-x+1;f=t?b-y+1:h;
        if(e>2&&f>2)d(x,y,e,f,e<f?0:1);
        e=t?w:x+w-a-1;f=t?y+h-b-1:h;
        if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);
        return this;
    }
}

```
> 5 votes

# Answer
# ZX Basic - 281 characters

This is more of a "proper" maze, less golfier, but more mazier. So called Binary maze algorithm, each cell can have an exit going down or right, but not both. (Now includes marked Start "S" and End "E", to prevent just going straight along one side).

The "::" is ZXB's way of entering Spectrum graphic characters into a text file, equates to a sold block character.

```
randomize:border 1:paper 1:ink 6:cls
for x=0 to 30 step 2
 for y=0 to 20 step 2
  r=1+int(rnd*2)
  if x=30 and r=1 then
   r=2
  end if
  if y=20 and r=2 then
   r=1
  end if
  print at y,x;"\::"
  print at y+(r=2),x+(r=1);"\::"
 next
next
print inverse 1;at 0,0;"S";at 20,31;"E"

```
> 2 votes

# Answer
# C- 244

```
#include <unistd.h>
#include <windows.h>
int main(i,j,rv,rs){srand( time(0));for (i = 0; i < 80; i++)for (j = 0; j <50 ; j++){rv = rand() %10;rs = rand() %100;if(rs < 10 || rs  > 90)continue;if(rv<4){gotoxy(i,j);printf("%c", '#');}}return 0;}

```

Here is how it looks like:

Note: this solution is inspired by the untrusted game level 8:into the woods.
> 1 votes

---
Tags: code-golf, popularity-contest, maze
---