# Question
Title: The Note of Destiny - place a note on a staff
The zombie apocalypse has come, and the world is coming to an end. Suddenly, someone discovers a formula that takes the current hour, minute, and day, and spits out the perfect note to play on a piano that instantly kills every zombie that hears it. Unfortunately, there is only one piano player left in the world, and he has forgotten how to read notes, but he still knows how to read sheet music. Of course, this is a very time-sensitive thing, so it seems natural to have a computer do it.1

Your challenge is to take a note, such as `G`, and output the note placed on a staff (in treble clef), like this:

```
-----

-----
   |
---|-
   |
--O--

-----

```

Specification:

* You must output a staff of alternating lines of `-----` (5 dashes) and a blank line. There will be 5 `-----`s total. The note must be superimposed on top of this staff.
* The input will specify where the note is located. The input will be:
    + an optional `H` or `L`, specifying "high" or "low"
    + a letter from `A` to `G`, specifying the pitch
    + an optional `#` or `b`, specifying sharp or flat.
* The "note" is defined as:
    + One `O` (capital O) aligned to the middle of the staff, which is in the place of the note. (The top line is `HF` (high F), and the bottom line is `E` (a normal E).)
    + Three `|`s (vertical bars), the stem, which will be:
        - one space to the left of the note and going downwards (starting one space below the note) if the note is on the middle line (`B`) or above, or
        - one space to the right of the note and going upwards (starting one space above the note) if the note is below the middle line.
    + A `#` or `b` one space directly to the left of the note if specified in the input.
* Ledger lines must be added if the note is too high or low. These lines will be `---` (only 3 dashes in width, as opposed to 5) and will only appear if the note is on or above/below (for top/bottom ledger lines respectively) the ledger lines.
* Extraneous spaces may be placed anywhere you want; for example, you could make the blank lines have spaces or have a space after the ledger lines if it helps you save any characters.

Here is a visualization, to understand the specification more easily, with all the note names next to the lines:

```
      HB
 ---  HA
      HG
----- HF
      HE
----- HD
      HC
----- B
      A
----- G
      F
----- E
      D
 ---  C
      LB
 ---  LA
      LG
 ---  LF
... (bottom cut off for brevity, you get the idea anyway)

```

Here are some more examples that you can use to test your program:

Input: `HG#`

```
 #O
-|---
 |
-|---

-----

-----

-----

```

Input: `LAb`

```
-----

-----

-----

-----

-----
   |
 --|
   |
 bO-

```

Input: `HB`

```
  O
 |--
 |
-|---

-----

-----

-----

-----

```

Input: `C`

```
-----

-----

-----

-----
   |
---|-
   |
 -O-

```

This is , so the shortest code in bytes will win!

1: most realistic exposition evar! :-P

# Answer
> 1 votes
# Golfscript, ~~211~~ ~~210~~ ~~209~~ ~~197~~ ~~195~~ 192 characters

Coming in for the (as of this post) win, a GolfScript version of my latest Python version:

```
"J"\+[0]+.1=71>>3<{}/@7*2/246-@3+7%-:z;:c;21,{..3z<3z
if<\11z>11z
if>|{;}{...2>\12<&\2%.{'-'' 'if}:Q~:9;&Q\.z={c!9{[c]''+}if}{..z>\4z+<&8z>&'|'9if}if\.z='o'9if\..z
4-\<\z<&7z<&'|'9if\;3$n}if}/

```

Test it out here (first 2 lines are user-input, normally it comes from stdin).

'Readable' version:

```
;"HCb"

"J"\+[0]+       #process input
.1=71>>3<       #first char is HJL, second is letter, third is #b or space
{}/             #spill chars onto stack, now we working with ints
@7*2/246-@3+7%- #convert HC/JD/LE etc to a number from 0 to 20
:z;:c;
21,{            #for r in range(21):
  ..3z<3z if<           #either out-of-bounds or process the line
  \11z>11z if>|
  {;}{
    ...2>\12<&\2%.{'-'' 'if}:Q~:9;&Q\        #1st char
    .z={c!9{[c]''+}if}                       #2nd char accidental
       {..z>\4z+<&8z>&'|'9if}if\            #2nd char stem or row
    .z='o'9if\                              #3rd char
    ..z 4-\<\z<&7z<&'|'9if\                 #4th char stem or row
    ;3$                                      #5th char=1st char
    n
  }if
}/

```

# Answer
> 6 votes
## Ruby – ~~271~~ ~~267~~ ~~252~~ ~~249~~ ~~234~~ ~~229~~ ~~220~~ 214 characters

I literally just learned Ruby for this. So there is certainly room for improvement in golfing it down. Or doing anything really. But I needed a language with mutable strings. :)

```
def f(n)s=[0]*20
s.fill{|i|i%2>0?i<3||i>11?" ---":?-*5:" "*5}
s[l=(3-n[(p="H_L".index n[0])?1:0].ord)%7+7*(p||1)][1,2]=("#b"[n[-1]]||s[l][1])+?O
s[l+3-2*o=l>7?3:1,3].map{|t|t[o]=?|}
puts s[[3,l].min..[11,l].max]end

```

Somewhat ungolfed:

```
def f(note)
  staff=[]
  0.step(20) {|i| staff[i] = " "*5}
  1.step(19,2) {|i| staff[i] = " ---"}
  3.step(11,2) {|i| staff[i] = "-"*5}
  level = 7
  if !(pos="HL".index note[i=0]).nil?
    level = 14*pos
    i += 1
  end
  level += (73-note[i].ord)%7
  staff[level][2] = "O"
  mark = note[-1]
  if !"#b".index(mark).nil?
    staff[level][1] = mark
  end
  offset = (level > 7) ? 3 : 1
  staff[level-2*offset+3,3].map {|line| line[offset] = "|"}
  first = [3,level].min
  last = [11,level].max
  puts s[first..last]
end

```

I can cut it by another 2 characters down to **212 characters** if leading blank lines are allowed. This solution doesn't fill the lines that aren't printed anyway:

```
def f(n)s=[]
[3,l=(3-n[(p="H_L".index n[0])?1:0].ord)%7+7*(p||1)].min.step(l>11?l:11){|i|s[i]=i%2>0?i<3||i>11?" ---":?-*5:" "*5}
s[l][1,2]=("#b"[n[-1]]||s[l][1])+?O
s[l+3-2*o=l>7?3:1,3].map{|t|t[o]=?|}
puts s
end

```

Are lambda's fair game? Then I can get **210 characters** with the first approach

```
f=->n{s=[0]*20
s.fill{|i|i%2>0?i<3||i>11?" ---":?-*5:" "*5}
s[l=(3-n[(p="H_L".index n[0])?1:0].ord)%7+7*(p||1)][1,2]=("#b"[n[-1]]||s[l][1])+?O
s[l+3-2*o=l>7?3:1,3].map{|t|t[o]=?|}
puts s[[3,l].min..[11,l].max]}

```

Or **207 characters** with additional blank lines:

```
f=->n{s=[]
[3,l=(3-n[(p="H_L".index n[0])?1:0].ord)%7+7*(p||1)].min.step(l>11?l:11){|i|s[i]=i%2>0?i<3||i>11?" ---":?-*5:" "*5}
s[l][1,2]=("#b"[n[-1]]||s[l][1])+?O
s[l+3-2*o=l>7?3:1,3].map{|t|t[o]=?|}
puts s}

```

Of course, now you'd need to do `f.call("HGb")`.

# Answer
> 2 votes
# Python, ~~329~~ ~~309~~ ~~295~~ ~~286~~ ~~280~~ 277 characters

Golfed a bit more now. Still can be improved, but not sure if I can beat out the ruby or golfscript solutions with this approach.

```
R=range
N='J'+raw_input()+' '
X=N[1]>'G'
a,b,c=N[X:3+X]
z=266-ord(a)/2*7+(ord(b)-4)%7
Z=[list((' '*5,(' ---','-'*5)[8<r<18])[r%2])for r in R(21)]
Z[z][2]='o'
if' '<c:Z[z][1]=c
Q=(z<13)*2
for i in(1,2,3):Z[z+i*Q-i][Q+1]='|'
for r in R(max(17,z),min(z-1,8),-1):print''.join(Z[r])

```

Initially I was printing out line-by-line, but it turned out to take too much, so I generate a string grid and then fill in what needs be filled in. Input is from command line, e.g.:

```
>echo HG# | python note2_golf.py
 #o
-|---
 |
-|---

-----

-----

-----

```

# Answer
> 2 votes
# GolfScript - ~~243~~ ~~232~~ ~~228~~ 227 characters

I translated my CoffeeScript answer into GolfScript, which is much more suited to the string manipulations.

**EDIT:** Saved six characters by properly using the increment operator, three by making good use of the stack, six more by irresponsibly redefining operators I'm not using, and one more by not printing the trailing space after grace lines.

Entirely golfed:

```
..0="HL"?2+3%:o)2%.@="CDEFGAB"?7o*+:`2%45 32if:r;
).2$,<{=}{;;r}if:&;
[" "5*:|" ---":g]4*[|"-"5*]5*+[|g|]+.
[`<~]\[`>([0=:^&79r^]''+\~]
+17`<`)18if<9`>`9if:j>:t 13`>.2*):x;
4,1>{`j-\2${+}{-}if}%\;
{.@<\t>(:v[x<'|'+x)v>+]\++:t}
/-1%n*

```

With comments:

```
# extract octave
..0="HL"?2+3%:o

# extract note
2%1\-.@="CDEFGAB"?7o*+:k

# line spacer
2%45 32if:r;

# extract accidental
1+.2$,<{=}{;;r}if:a;

# staff
[" "5*:|" --- ":g]4*[|"-"5*]5*+[|g|]+.

# lines below
[k<~]\

# note line and above
[k>([0=:w a 79r w]''+\~]+

# cut off just what we need
17k<1k+18if<
9k>k 9if:j>:t;

# and the note stem
13k>.2*1+:x;4,1>{k j-\2${+}{-}if}%\;

{
  .t<\
  t>(:v[x<'|'+1x+v>+]\++:t;
}/

# now output the note
t-1%n*

```

# Answer
> 1 votes
# Java - ~~921~~ ~~907~~ 863 characters

I build up each string seperately, storing each string in an array. Then loop through the array and print out each line.

```
public class D{public static void main(String[]a){char[]z=a[0].toCharArray();char[]y=new char[3];y[0]=('H'==z[0]||'L'==z[0])?z[0]:'N';int o=(y[0]=='N')?0:1;y[1]=z[o++];y[2]=z.length>o?z[o]:'!';int n=y[1]<'C'?((int)(y[1]-'A'))+6:((int)(y[1]-'C'))+1;n=(y[0]=='N')?n+7:(y[0]=='H'?n+14:n);String s="     ";String b=" --- ";String[]u=new String[22];for(int i=1;i<=21;i+=2){u[i]=s;}for(int i=10;i<=18;i+=2){u[i]="-----";}u[20]=n>19?b:s;u[2]=n<3?b:s;u[4]=n<5?b:s;u[6]=n<7?b:s;u[8]=n<9?b:s;char c=u[n].charAt(0);char e=u[n].charAt(1);char[]h=new char[]{c,y[2]=='!'?e:y[2],'O',e,c};u[n]=new String(h);for(int i=0;i<22;i++){if(n<14&&i-n<4&&i>n)u[i]=u[i]!=null?u[i].substring(0,3)+"|"+u[i].charAt(4):s;else if(n>13&&n-i<4&&n>i)u[i]=u[i]!=null?u[i].substring(0,3)+"|"+u[i].charAt(4):s;}for(int i=21;i>=0;i--)if(!(i>n&&i>18||i<n&&i<10))System.u.println((u[i]==null)?s:u[i]);}}

```

Oh please don't hate me, it's my first time. I coulnd't find any faq/introduction so I hope my posting format is ok. Not sure how serious people got about character counts.... normal version of the code - extra is linebreak/spaces (1313 characters):

```
public class DisplayNote
{
  public static void main(String[] args)
  {
    char[] z=args[0].toCharArray();
    char[] y=new char[3];
    y[0]=('H'==z[0]||'L'==z[0])?z[0]:'N';
    int o=(y[0]=='N')?0:1;
    y[1]=z[o++];
    y[2]=z.length>o?z[o]:'!';

    int noteValue=y[1]<'C'?((int) (y[1] - 'A')) + 6:((int) (y[1] - 'C')) + 1;
    noteValue=(y[0]=='N')?noteValue+7:(y[0]=='H'?noteValue+14:noteValue);
    String s="     ";
    String b=" --- ";
    String[] out=new String[22];
    for (int i=1;i<=21;i+=2){out[i]=s;}
    for (int i=10;i<=18;i+=2){out[i]="-----";}
    out[20]=noteValue>19?b:s;
    out[2]=noteValue<3?b:s;
    out[4]=noteValue<5?b:s;
    out[6]=noteValue<7?b:s;
    out[8]=noteValue<9?b:s;

    char c=out[noteValue].charAt(0);
    char e=out[noteValue].charAt(1);
    char[] h=new char[]{c,y[2]=='!'?e:y[2],'O',e,c};
    out[noteValue]=new String(h);
    for (int i=0;i<22;i++)
    {
      if (noteValue<14&&i-noteValue<4&&i>noteValue)
        out[i]=out[i]!=null?out[i].substring(0,3)+"|"+out[i].charAt(4):s;
      else if (noteValue>13&&noteValue-i<4&&noteValue>i)
        out[i]=out[i]!=null?out[i].substring(0,3)+"|"+out[i].charAt(4):s;
    }

    for (int i=21;i>=0;i--)
      if (!(i>noteValue&&i>18||i<noteValue&&i<10))
        System.out.println((out[i]==null)?s:out[i]);
  }
}

```

# Answer
> 1 votes
# Python, ~~250~~ ~~245~~ ~~242~~ 235 characters

A very different approach which ended up beating out my other one! Input processing code is similar but that's about it.

```
M=' -'
N=raw_input()+M
a,b,c=('J'+N)[N>'G':][:3]
z=ord(a)*7/2-246-(ord(b)+3)%7
for r in range(21):
 L=M[r%2];F=M[2<r<12and r%2]
 if min(3,z)<=r<=max(11,z):print F+((L,'|')[8>z<r<z+4],(L,c)[M<c])[r==z]+(L,'o')[r==z]+(L,'|')[z-4<r<z>7]+F

```

I mapped out each character's value based on the row and column and then golfed the printing:

```
#given row r, with note on row n, how to print each char?
#rows are:
#       HB : 0
#  ---  HA : 1
#       HG : 2
# ----- HF : 3
#       HE : 4
# ----- HD : 5
#       HC : 6
# ----- B  : 7
#       A  : 8
# ----- G  : 9
#       F  : 10
# ----- E  : 11
#       D  : 12
#  ---  C  : 13
#       LB : 14
#  ---  LA : 15
#       LG : 16
#  ---  LF : 17
#       LE : 18
#  ---  LD : 19
#       LC : 20
#chars are:
# 0 | 1 | 2 | 3 | 4
#
# 0,4:
#    if r%2:
#      if 2<r<12: '-'
#      else ' '
#    else: ' '
# 1: ' -b#|'
#    if r==n:
#      if A: c
#      else: ' -'[r%2]
#    elif n<8 and n<r<n+4: '|'
#    else: ' -'[r%2]
# 2: ' -o'
#    if r==n: 'o'
#    else: ' -'[r%2]
# 3: ' -|'
#    if n>7 and n-4<r<n: '|'
#    else: ' -'[r%2]

```

# Answer
> 1 votes
# Haskell 377C

```
import Data.Char
(<.)=elem
n(c:r)|elem c"HL"=let(s,a)=n r in(s+case c of 'H'->7;_-> -7,a)|1<2=(mod(ord c-67)7-2,case r of[]->' ';[x]->x)
r(s,a)y x=c where d|s>4= -1|1<2=1;c|x<.[0,4]&&(y<0||y>8)=' '|x==2&&y==s='o'|y==s&&x==1&&' '/=a=a|x==2+d&&y<.[s+k*d|k<-[1..3]]='|'|1<2="- "!!mod y 2
g p@(s,a)=unlines$[map(r p y)[0..4]|y<-reverse[min 0 s..max 8 s]]
main=getLine>>=putStr.g.n

```

Ungolfed version:

```
import Data.Char

fromName ('H':s) = let (step, alter) = fromName s in ((step + 7), alter)
fromName ('L':s) = let (step, alter) = fromName s in ((step - 7), alter)
fromName (x:s) = (mod (ord x - 67) 7 - 2, if null s then ' ' else head s)

renderChar :: (Int, Char) -> Int -> Int -> Char
renderChar (step, alter) y x = let
    dir = if step >  4 then -1 else 1
    normal = "- "!!mod y 2
    stemYs = [step + k * dir | k <- [1..3]]
    c | elem x [0,4] && not(elem y [0,2,4,6,8]) = ' '
      | x == 2 && y == step = 'o'
      | y == step && x == 1 && alter /= ' ' = alter
      | elem y stemYs && x == 2 + dir = '|'
      | otherwise = normal
  in c

render :: (Int, Char)-> String
render (step, alter) = unlines [map (renderChar (step, alter) y) [0..4] | y <- ys]
  where
    ys = reverse [min 0 step .. max 8 step]

main = getLine >>= (putStr.render.fromName)

```

# Answer
> 0 votes
# Literate CoffeeScript - ~~497~~ 527 characters

I'm sure there's a better way to build the grid but I can't figure it out.

One golf helper.

```
_=(q)->->q.split ""

```

A C major scale and staff.

```
s=_("CDEFGAB")()
l=_ "-----"
e=_ "     "
g=_ " --- "
t=->
  o=[e(),l(),e(),l(),e(),l(),e(),l(),e(),l(),e(),g(),e()]
  o.unshift e(),g() for [0..3]
  o

```

Our notation function will take the string representation of a note.

```
f=(i)->
  o=1
  m=t()

```

First we'll determine the octave.

```
  if /L|H/.test i[0]
    if i[0]=="L" then o=0 else o=2
    i=i[1..]

```

Then the note and accidental. Gotta love deconstructing assignment.

```
  [n,a]=i

```

Let's convert the note and octave to an index and plot the note.

```
  x=7*o+s.indexOf n

  m[x][1]=a if a
  m[x][2]='O'

```

Now we'll cut out only as much staff as we need.

```
  j=9
  k=17
  if x>17
    k=x
  else if x<9
    j=x
  u=x-j
  m=m[j..k]

```

And the note stem.

```
  if x<13
    m[x][3]='|' for x in [u+3...u]
  else
    m[x][1]='|' for x in [u-3...u]

```

Now let's output the results.

```
  m.map((p)->p.join '').reverse().join '\n'

```

Finally, we'll export the function for console testing. These characters don't count towards the total.

```
module.exports = f

```

# Answer
> 0 votes
# C, ~~325~~ 304

Now 21 bytes shorter thanks to @ace!

```
i;j;c;n;main(t){char
x[133];for(i;i<132;i++){x[i]="-----\n     \n"[i%12];if((i<18||i>77)&&!((i%12)&11))x[i]=32;}for(;!n;){c=getchar();if(c>71)t=c^72?2:0;else
n=7*t+7-(c-4)%7;}x[i=n*6+2]=79;if((c=getchar())>32)x[i-1]=c;for(t=0,j=n<9?i+5:i-17;t<3;t++,j+=6)x[j]='|';x[n<13?77:n*6+5]=0;puts(x+(n>4?24:n*6));}

```

### Output:

```
./a.out
HBb
 bO
 |--
 |
-|---

-----

-----

-----

-----

./a.out
LG#
-----

-----

-----

-----

-----

 --|
   |
 --|
 #O

```

# Answer
> 0 votes
# JavaScript 390 388

A bit of a challenge, I'll have to admit... I'm sure there's ways of reducing this further... I'm open to suggestions...

First Iteration

```
C=(a,x,o,c)=>{a[x]=a[x].substr(0,o)+c+a[x].substr(o+1)};l=7;s=[];for(i=21;i--;)s[i]="    ";for(j=1;19>j;j+=2)s[j]=" ---";for(k=3;12>k;k+=2)s[k]="-----";~(p="HL".indexOf((n=prompt())[i=0]))&&(l=14*p,i++);l+=(73-n.charCodeAt(i))%7;C(s,l,2,"O");m=n[n.length-1];"#"!=m&   "b"!=m||C(s,l,1,m);o=7<l?3:1;for(z=0;3>z;C(s,t=l-2*o+3+z++,o,"|"));S=s.splice(3<=l?3:l,11>=l?11:l);console.log(S.join("\n"))

```

Second Iteration (using `n.slice(-1)` instead of `n[n.length-1]`), shaves 2 bytes

```
C=(a,x,o,c)=>{a[x]=a[x].substr(0,o)+c+a[x].substr(o+1)};l=7;s=[];for(i=21;i--;)s[i]="    ";for(j=1;19>j;j+=2)s[j]=" ---";for(k=3;12>k;k+=2)s[k]="-----";~(p="HL".indexOf((n=prompt())[i=0]))&&(l=14*p,i++);l+=(73-n.charCodeAt(i))%7;C(s,l,2,"O");m=n.slice(-1);"#"!=m& "b"!=m||C(s,l,1,m);o=7<l?3:1;for(z=0;3>z;C(s,t=l-2*o+3+z++,o,"|"));S=s.splice(3<=l?3:l,11>=l?11:l);console.log(S.join("\n"))

```

Ungolfed version:

```
function C(a,x,o,c){
    a[x]=a[x].substr(0,o)+c+a[x].substr(o+1);
}
l=7;s=[];
for(i=21;i--;){
    s[i]="    ";
}
for(j=1;19>j;j+=2){
    s[j]=" ---";
}
for(k=3;12>k;k+=2){
    s[k]="-----";
}
i=0;n=prompt();
p="HL".indexOf(n[i]);
if(p>=0){
    l=14*p;i++;
}
l+=(73-n.charCodeAt(i))%7;
C(s,l,2,"O");
m=n.slice(-1);
if((m=="#")||m=="b"){
    C(s,l,1,m);
}
o=7<l?3:1;
for(z=0;3>z;z++){
    C(s,t=l-2*o+3+z,o,"|");
}
F=Math.min(3,l);
L=Math.max(11,l);
S=s.splice(F,L);
console.log(S.join("\n"));

```

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


title: Math without numbers

text:
# Question
Title: Math without numbers
You must write functions for addition, subtraction, multiplication, and division; however, you can never use any of your language's number types / primitives -- this means no ints, no floats, no Integers; no nothing. You cannot reference these types at all; not even implicitly, e.g. no pushing and popping numbers on a stack.

Valid statically-typed pseudocode (does not solve the problem):

```
boolean result = true && false
string helloWorld = "hello" + " world"
Object[] things = [new Object(), "foo", true]

```

Invalid statically-typed pseudocode (does not solve the problem):

```
float num = 42F
Object foo = "100".toInt()

```

To make things simpler, pointers are allowed.

This is code-golf, so make it short and sweet.

# Answer
> 3 votes
# Haskell: 162 characters

This is algebraic data types 101.

```
data N=E|Z|P N
a x Z=x
a x (P y)=a(P x)y
s x Z=x
s Z _=E
s (P x)(P y)=s x y
m _ Z=Z
m Z _=Z
m x (P y)=a x$m x y
d _ Z=E
d x (P Z)=x
d Z _=Z
d x y=a(P Z)$d(s x y)y

```

# Answer
> 2 votes
# Javascript

Example: 24.5-20.5+2\*1 = bd.e-bz.e+b\*a = 6

```
 f="bd.e-bz.e+b*a";
    n=function(a){
    if(a.match('^[+/*.-]$')) {
        return a;
    }
    if(a=="z") {a="`";}
    return a.charCodeAt()-"`".charCodeAt();
    }
    o=[];
    tx=f.split("");
    tx.forEach(function(t,idx){
                o.push(n(t));
            });
    o=o.join("");
    eval(o);

```

# Answer
> 1 votes
## REBEL

3 + 9 + 23 + 29 = **64**

---

Addition:

```
/;/

```

Subtraction:

```
/0;0/;/;/

```

Multiplication:

```
/0(0+;(0*))/$1:$2/0;|:/

```

Division:

```
/(0+)(0*;\1$)/1$2/10|1;/1/1/0

```

---

Input format:

2 strings of 0s, separated by a semicolon. The value is the length of the string.

```
0000;00

```

Output format:

1 string of 0s, with the same semantics.

```
000000

```

Since this works with natural numbers (positive integers), subtraction and division will not always yield the correct answer. Subtraction yields the absolute value of the result, and division rounds down.

These are not complete programs, but they use the current state of the program as input. Similarly, they leave the program in the result state when they are done.

Here is an example of how to use them (using division as an example):

```
000000;00/(0+)(0*;\1$)/1$2/10|1;/1/1/0

```

When this terminates, the current state will be `000`.

---
Tags: code-golf
---


# Question
Title: How to write a C program for multiplication without using the * and + operators?
> Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

I found this on Stack Overflow. Please help this poor programmer with his problem. And please don't give answers like `c = a/(1/((float)b))`, which is exactly the same as `c = a*b`. (And is already given as an answer.)

The answer with the most upvotes on January 19th 2014 wins.

Note: This is a question. Please do not take the question and/or answers seriously. More information is in *code-trolling*.

# Answer
> 147 votes
## Always use recursion

Recusion is the right way!

```
int inc(int x) {
    return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
    return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
    return x?add(dec(x),inc(y)):y;
}

int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
}

int main() {
    int a, b;
    scanf("%i\n%i", &a, &b);
    printf("%i", mul(a,b));
}

```

# Answer
> 87 votes
You'll have to compile the program each time, but it does do multiplication of any positive integers exactly in any version of C or C++.

```
 #define A 45  // first number
 #define B 315 // second number

 typedef char buffer[A][B];

 main() {
    printf("%d\n",sizeof(buffer));
 }

```

# Answer
> 47 votes
If you are OK with a little imprecision, you can use the Monte Carlo method:

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

unsigned int mul(unsigned short a, unsigned short b) {
  const int totalBits = 24;
  const int total = (1 << totalBits);
  const int maxNumBits = 10;
  const int mask = (1 << maxNumBits) - 1;
  int count = 0, i;
  unsigned short x, y;
  for(i = 0; i < total; i++) {
    x = random() & mask;
    y = random() & mask;
    if ((x < a) && (y < b))
      count++;
  }
  return ((long)count) >> (totalBits - (maxNumBits << 1));
}

void main(int argc, char *argv[]) {
  unsigned short a = atoi(argv[1]);
  unsigned short b = atoi(argv[2]);
  printf("%hd * %hd = %d\n", a, b, mul(a, b));
}

```

Example:

```
$ ./mul 300 250
300 * 250 = 74954

```

I guess this could be good enough ;)

# Answer
> 45 votes
Since you didn't specify what size of number, I assume that you mean two one-bit numbers.

```
#include <stdbool.h>
bool mul(bool a, bool b) {
    if (a && b) {
        return true;
    } else {
        return false;
    }
}

```

If you want a maximally-efficient implementation, use the following tiny implementation:

```
m(a,b){return a&b;}

```

Note that it still only accepts bits even though the types are implicit ints - it takes less code, and is therefore more efficient. (And yes, it does compile.)

# Answer
> 31 votes
Here's a simple shell script to do it:

```
curl "http://www.bing.com/search?q=$1%2A$2&go=&qs=n&form=QBLH&pq=$1%2A$2" -s \
| sed -e "s/[<>]/\n/g" \
| grep "^[0-9 *]*=[0-9 ]*$"

```

UPDATE: Of course, to do it in C, just wrap it in `exec("bash", "-c", ...)`. (Thanks, AmeliaBR)

# Answer
> 27 votes
Why, let's do a recursive halving search between INT64\_MIN and INT64\_MAX!

```
#include <stdio.h>
#include <stdint.h>

int64_t mul_finder(int32_t a, int32_t b, int64_t low, int64_t high)
{
    int64_t result = (low - (0 - high)) / 2;
    if (result / a == b && result % a == 0)
        return result;
    else
        return result / a < b ?
            mul_finder(a, b, result, high) :
            mul_finder(a, b, low, result);
}

int64_t mul(int32_t a, int32_t b)
{
    return a == 0 ? 0 : mul_finder(a, b, INT64_MIN, INT64_MAX);
}

void main(int argc, char* argv[])
{
    int32_t a, b;
    sscanf(argv[1], "%d", &a);
    sscanf(argv[2], "%d", &b);
    printf("%d * %d = %ld\n", a, b, mul(a, b));
}

```

P.S. It will happily sigsegv with some values. ;)

# Answer
> 18 votes
Unfortunately, this only works for integers.

Since addition is disallowed, let's build an increment operator first:

```
int plusOne(int arg){
  int onMask = 1;
  int offMask = -1;
  while (arg & onMask){
    onMask <<= 1;
    offMask <<= 1;
  }
  return(arg & offMask | onMask);
}

```

Next, we have to handle the sign. First, find the sign bit:

```
int signBit = -1;
while(signBit << 1) signBit <<=1;

```

Then take the sign and magnitude of each argument. To negate a number in a two's complement, invert all bits, and add one.

```
int signA = a & signBit;
if(signA) a = plusOne(-1 ^ a);
int signB = b & signBit;
if(signB) b = plusOne(-1 ^ b);
int signRes = signA ^ signB;

```

To multiply two positive integers, we can use the geometrical meaning of multiplication:

```
// 3x4
//
// ooo
// ooo
// ooo
// ooo

int res = 0;
for(int i = 0; i < a; i = plusOne(i))
  for(int j = 1; j < b; j = plusOne(j))
    res = plusOne(res);

if(signRes) res = plusOne(-1 ^ res);

```

---

trolls:

* Addition is disallowed, but does `a++` really count as addition? I bet the teacher intended to allow it.
* Relies on two's complement, but that's an implementation-defined behavior and the target platform wasn't specified.
* Similarly, assumes subtraction and division are disallowed just as well.
* `<<` is actually multiplication by a power of two, so it should technically be disallowed.
* unneccesary diagram is unneccesary. Also, it could have been transposed to save one line.
* repeated shifting of `-1` is not the nicest way of finding the sign bit. Even if there was no built-in constant, you could do a logical shift right of -1, then invert all bits.
* XOR -1 is a not the best way to invert all bits.
* The whole charade with sign-magnitude representation is unneccesary. Just cast to unsigned and modular arithmetic will do the rest.
* since the absolute value of `MIN_INT` (AKA `signBit`) is negative, this breaks for that value. Luckily, it still works in half the cases, because `MIN_INT * [even number]` *should* be zero.  ~~Also, `plusOne` breaks for `-1`, causing infinite loops anytime the result overflows.~~ `plusOne` works just fine for any value. Sorry for the confusion.

# Answer
> 14 votes
Works for floating point numbers as well:

```
float mul(float a, float b){
  return std::exp(std::log(a) - std::log(1.0 / b));
}

```

# Answer
> 11 votes
Everyone knows that Python is easier to use than C. And Python has functions corresponding to every operator, for cases where you can't use the operator. Which is exactly our problem definition, right? So:

```
#include <Python.h>

void multiply(int a, int b) {
    PyObject *operator_name, *operator, *mul, *pa, *pb, *args, *result;
    int result;

    operator_name = PyString_FromString("operator");
    operator = PyImport_Import(operator_name);
    Py_DECREF(operator_name);
    mul = PyObject_GetAttrString(operator, "__mul__");
    pa = PyLong_FromLong((long)a);
    pb = PyLong_FromLong((long)b);
    args = PyTuple_New(2);
    PyTuple_SetItem(args, 0, pa);
    PyTuple_SetItem(args, 1, pb);
    presult = PyObject_CallObject(mul, args);
    Py_DECREF(args);
    Py_DECREF(mul);
    Py_DECREF(operator);
    result = (int)PyLong_AsLong(presult);
    Py_DECREF(presult);
    return result;
}

int main(int argc, char *argv[]) {
    int c;
    Py_Initialize();
    c = multiply(2, 3);
    printf("2 * 3 = %d\n", c);
    Py_Finalize();
}

```

# Answer
> 10 votes
```
unsigned add( unsigned a, unsigned b )
{
    return (unsigned)&((char*)a)[b];  // ignore compiler warnings
       // (if pointers are bigger than unsigned). it still works.
}
unsigned umul( unsigned a, unsigned b )
{
    unsigned res = 0;
    while( a != 0 ){
        if( a & 1) res = add( res, b );
        b <<= 1;
        a >>= 1;
    }
    return res;
}

int mul( int a, int b ){
    return (int)umul( (unsigned)a, (unsigned)b );
}

```

If you consider the a\[b\] hack to be cheating (since it's really an add) then this works instead. But table lookups involve pointer adds too.

See http://en.wikipedia.org/wiki/IBM\_1620 \- a conputer that actually did addition using lookup tables...

Something satisfying about using a table mechanism to 'speed up' an operation that could actually be done in one instruction.

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

unsigned add( unsigned a, unsigned b )
{
   static const int add4hack[8] =  {4,8,12,16,20,24,28,32};
   unsigned carry = 0;
   unsigned (*sumtab0)[16] = &sumtab[0];
   unsigned (*sumtab1)[16] = &sumtab[1];
   unsigned result = 0;
   int nshift = 0;
   while( (a|b) != 0 ){
      unsigned psum = (carry?sumtab1:sumtab0)[ a & 0xF ][ b & 0xF ];
      result = result | ((psum & 0xF)<<nshift);
      carry = psum >> 4;
      a = a >> 4
      b = b >> 4;
      nshift= add4hack[nshift>>2];  // add 4 to nshift.
   }
   return result;
}

```

# Answer
> 10 votes
None of the other answers are theoretically sound. As the very first comment on the question says:

> Please be more specific about "numbers"

We need to define multiplication, and numbers, before an answer is even possible. Once we do, the problem becomes trivial.

The most popular way to do this in beginning mathematical logic is to build von Neumann ordinals on top of ZF set theory, and then use the Peano axioms.

This translates naturally to C, assuming you have a set type that can contain other sets. It doesn't have to contain anything *but* sets, which makes it trivial (none of that casting `void*` nonsense in most set libraries), so I'll leave the implementation as an exercise for the reader.

So, first:

```
/* The empty set is 0. */
set_t zero() {
    return set_new();
}

/* The successor of n is n U {n}. */
set_t successor(set_t n) {
    set_t result = set_copy(n);
    set_t set_of_n = set_new();
    set_add(set_of_n, n);
    set_union(result, set_of_n);
    set_free(set_of_n);
    return result;
}

/* It is an error to call this on 0, which will be reported by
   running out of memory. */
set_t predecessor(set_t n) {
    set_t pred = zero();
    while (1) {
        set_t next = successor(pred);
        if (set_equal(next, n)) {
            set_free(next);
            return pred;
        }
        set_free(pred);
    }
}

set_t add(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a + 0 = a */
        return a;
    } else {
        /* a + successor(b) = successor(a+b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = add(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

set_t multiply(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a * 0 = 0 */
        return b;
    } else {
        /* a * successor(b) = a + (a * b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = mul(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

```

If you want to expand this to integers, rationals, reals, surreals, etc., you can—with infinite precision (assuming you have infinite memory and CPU), to boot. But as Kroenecker famously said, God made the natural numbers; all else is the work of man, so really, why bother?

# Answer
> 8 votes
My troll solution for `unsigned int`:

```
#include<stdio.h>

unsigned int add(unsigned int x, unsigned int y)
{
  /* An addition of one bit corresponds to the both following logical operations
     for bit result and carry:
        r     = x xor y xor c_in
        c_out = (x and y) or (x and c_in) or (y and c_in)
     However, since we dealing not with bits but words, we have to loop till
     the carry word is stable
  */
  unsigned int t,c=0;
  do {
    t = c;
    c = (x & y) | (x & c) | (y & c);
    c <<= 1;
  } while (c!=t);
  return x^y^c;
}

unsigned int mult(unsigned int x,unsigned int y)
{
  /* Paper and pencil method for binary positional notation:
     multiply a factor by one (=copy) or zero
     depending on others factor actual digit at position, and  shift
     through each position; adding up */
  unsigned int r=0;
  while (y != 0) {
    if (y & 1) r = add(r,x);
    y>>=1;
    x<<=1;
  }
  return r;
}

int main(int c, char** param)
{
  unsigned int x,y;
  if (c!=3) {
     printf("Fuck!\n");
     return 1;
  }
  sscanf(param[1],"%ud",&x);
  sscanf(param[2],"%ud",&y);
  printf("%d\n", mult(x,y));
  return 0;
}

```

# Answer
> 8 votes
I'm not sure what constitutes "cheating" in these "code troll" posts, but this multiplies 2 arbitrary integers, at run time, with no `*` or `+` operator using standard libraries (C99).

```
#include <math.h>
main()
{
  int a = 6;
  int b = 7;
  return fma(a,b,0);
}

```

# Answer
> 7 votes
There are a lot of good answers here, but it doesn't look like many of them take advantage of the fact that modern computers are really powerful. There are multiple processing units in most CPUs, so why use just one? We can exploit this to get great performance results.

```
#include <stdio.h>
#include <limits.h>
#include "omp.h"

int mult(int a, int b);

void main(){
        int first;
        int second;
        scanf("%i %i", &first, &second);
        printf("%i x %i = %i\n", first, second, mult(first,second));
}

int mult(int second, int first){
        int answer = INT_MAX;
        omp_set_num_threads(second);
        #pragma omp parallel
        for(second = first; second > 0; second--) answer--;
        return INT_MAX - answer;
}

```

Here's an example of its usage:

```
$ ./multiply
5 6
5 x 6 = 30

```

The `#pragma omp parallel` directive makes OpenMP divide each part of the for loop to a different execution unit, so we're multiplying in parallel!

Note that you have to use the `-fopenmp` flag to tell the compiler to use OpenMP.

---

Troll parts:

1. Misleading about the use of parallel programming.
2. Doesn't work on negative (or large) numbers.
3. Doesn't actually divide the parts of the `for` loop - each thread runs the loop.
4. Annoying variable names and variable reuse.
5. There's a subtle race condition on `answer--`; most of the time, it won't show up, but occasionally it will cause inaccurate results.

# Answer
> 6 votes
Unfortunately, multiplication is a very difficult problem in computer science. The best solution is to use division instead:

```
#include <stdio.h>
#include <limits.h>
int multiply(int x, int y) {
    int a;
    for (a=INT_MAX; a>1; a--) {
        if (a/x == y) {
            return a;
        }
    }
    for (a=-1; a>INT_MIN; a--) {
        if (a/x == y) {
            return a;
        }
    }
    return 0;
}
main (int argc, char **argv) {
    int a, b;
    if (argc > 1) a = atoi(argv[1]);
    else a = 42;
    if (argc > 2) b = atoi(argv[2]);
    else b = 13;
    printf("%d * %d is %d\n", a, b, multiply(a,b));
}

```

# Answer
> 6 votes
In real life I usually respond to trolling with knowledge, so here's an answer that doesn't troll at all. It works for all `int` values as far as I can see.

```
int multiply (int a, int b) {
  int r = 0;
  if (a < 0) { a = -a; b = -b }

  while (a) {
    if (a&1) {
      int x = b;
      do { int y = x&r; r ^= x; x = y<<1 } while (x);
    }
    a>>=1; b<<=1;
  }
  return r;
}

```

This is, to the best of my understanding, very much like how a CPU might actually do integer multiplication. First, we make sure that at least one of the arguments (`a`) is positive by flipping the sign on both if `a` is negative (and no, I refuse to count negation as a kind of either addition or multiplication). Then the `while (a)` loop adds a shifted copy of `b` to the result for every set bit in `a`. The `do` loop implements `r += x` using and, xor, and shifting in what's clearly a set of half-adders, with the carry bits fed back into `x` until there are no more (a real CPU would use full adders, which is more efficient, but C doesn't have the operators we need for this, unless you count the `+` operator).

# Answer
> 6 votes
Throwing this into the mix:

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

int mul(int a, int b)
{
        asm ("mul %2"
            : "=a" (a)
            : "%0" (a), "r" (b) : "cc"
        );
        return a;
}

int main(int argc, char *argv[])
{
        int a, b;

        a = (argc > 1) ? atoi(argv[1]) : 0;
        b = (argc > 2) ? atoi(argv[2]) : 0;

        return printf("%d x %d = %d\n", a, b, mul(a, b)) < 1;
}

```

---

From info page.

*– Introducing something extremely unacceptable or unreasonable in the code that cannot be removed without throwing everything away, rendering the answer utterly useless for the OP.*

*– \[…\] The intention is to do the homework in a language that the lazy OP might think acceptable, but still frustrate him.*

# Answer
> 6 votes
```
 int bogomul(int A, int B)
{
    int C = 0;
    while(C/A != B)
    {

        print("Answer isn't: %d", C);
        C = rand();

    }
    return C;
}

```

# Answer
> 5 votes
```
#include <stdio.h>
#include <stdlib.h>

int mult (int n1, int n2);
int add (int n1, int n2 );
int main (int argc, char** argv)
{
        int a,b;
        a = atoi(argv[1]);
        b = atoi(argv[2]);

        printf ("\n%i times %i is %i\n",a,b,mult(a,b));
        return 0;
}

int add (int n1, int n2 )
{
        return n1 - -n2;
}

int mult (int n1, int n2)
{
        int sum = 0;
        char s1='p', s2='p';
        if ( n1 == 0 || n2 == 0 ) return 0;
        if( n1 < 0 )
        {
                s1 = 'n';
                n1 = -n1;
        }
        if( n2 < 0 )
        {
                s2 = 'n';
                n2 = -n2;
        }
        for (int i = 1; i <= n2; i = add( i, 1 ))
        {
                sum = add(sum,  n1);
        }
        if ( s1 != s2 ) sum = -sum;
        return sum;
}

```

# Answer
> 5 votes
> Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

Sure:

```
void multiply() {
    printf("6 times 7 is 42\n");
}

```

But of course that's cheating; obviously he wants to be able to \_supply) two numbers, right?

```
void multiply(int a, int b) {
    int answer = 42;
    if (answer / b != a || answer % b) {
        printf("The answer is 42, so that's the wrong question.\n");
    } else {
        printf("The answer is 42, but that's probably not the right question anyway.\n");
    }
}

```

# Answer
> 4 votes
There's no arithmetic like pointer arithmetic:

```
int f(int a, int b) {
        char x[1][b];
        return x[a] - x[0];
}

int
main(int ac, char **av) {
        printf("%d\n", f(atoi(av[1]),atoi(av[2])));
        return 0;
}

```

The function `f` implements multiplication. `main` simply calls it with two arguments.
Works for negative numbers as well.

# Answer
> 3 votes
# C#

I think subtraction and negation are not allowed... Anyway:

```
int mul(int a, int b)
{
    int t = 0;
    for (int i = b; i >= 1; i--) t -= -a;
    return t;
}

```

# Answer
> 3 votes
C with SSE intrinsics (because everything's better with SIMD):

```
#include <stdio.h>
#include <stdlib.h>
#include <xmmintrin.h>

static float mul(float a, float b)
{
    float c;

    __m128 va = _mm_set1_ps(a);
    __m128 vb = _mm_set1_ps(b);
    __m128 vc = _mm_mul_ps(va, vb);
    _mm_store_ss(&c, vc);
    return c;
}

int main(int argc, char *argv[])
{
    if (argc > 2)
    {
        float a = atof(argv[1]);
        float b = atof(argv[2]);
        float c = mul(a, b);
        printf("%g * %g = %g\n", a, b, c);
    }
    return 0;
}

```

The big advantage of this implementation is that it can easily be adapted to perform 4 parallel multiplications without `*` or `+` if required.

# Answer
> 3 votes
```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define INF 1000000

char cg[INF];

int main()
{
    int a, b;

    char bg[INF];
    memset(bg, '*', INF);

    scanf("%d%d", &a, &b);

    bg[b] = 0;

    while(a--)
        strcat(cg, bg);

    int result;
    printf("%s%n",cg,&result);
    printf("%d\n", result);

    return 0;
}

```
* work only for multiplication result \< 1 000 000
* So far can't get rid out of -- operator, possibly enhancing here
* using %n format specifier in printf to count the number printed characters(I posting this mainly to remind of existence %n in C, instead of %n could of course be strlen etc.)
* Prints a\*b characters of '\*'

# Answer
> 3 votes
Probably too fast :-(

```
   unsigned int add(unsigned int a, unsigned int b)
    {
        unsigned int carry;

        for (; b != 0; b = carry << 1) {
            carry = a & b;
            a ^= b;
        }
        return a;
    }

    unsigned int mul(unsigned int a, unsigned int b)
    {
        unsigned int prod = 0;

        for (; b != 0;  a <<= 1, b >>= 1) {
            if (b & 1)
                prod = add(prod, a);
        }
        return prod;
    }

```

# Answer
> 3 votes
This Haskell version only works with nonnegative integers, but it does the multiplication the way children first learn it. I.e., 3x4 is 3 groups of 4 things. In this case, the "things" being counted are notches ('|') on a stick.

```
mult n m = length . concat . replicate n . replicate m $ '|'

```

# Answer
> 3 votes
```
int multiply(int a, int b) {
    return sizeof(char[a][b]);
}

```

This may work in C99, if the weather is right, and your compiler supports undefined nonsense.

# Answer
> 3 votes
Since the OP didn't ask for C, here's one in (Oracle) SQL!

```
WITH
   aa AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS addition
FROM (SELECT * FROM aa UNION ALL SELECT * FROM bb);

WITH
   aa AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS multiplication
FROM aa CROSS JOIN bb;

```

# Answer
> 2 votes
Without recursion (but no check for overflow)

```
int add(int x, int y) {
    int t;
    do {
        t = x & y;
        y ^= x;
        x = t << 1;
    } while (t);
    return y;
}

int mul(int x, int y) {
    int t = 0;
    do {
        t = add(t, y & 1 ? x : 0);
        y >>= 1;
        x <<= 1;
    } while (y);
    return t;
}

```

**Upd:** compact add

```
int add(int x, int y) {
    while (x = (x & (x ^ (y ^= x))) << 1);
    return y;
}

```

**Upd:** compact mul without branching

```
int mul(int x, int y) {
    int t = 0;
    do {
        t = add(t, -(y & 1) & x);
    } while (x <<= 1, y >>= 1);
    return t;
}

```

# Answer
> 2 votes
```
int add(int a, int b) {
    return 0 - ((0 - a) - b);
}

int mul(int a, int b) {
    int m = 0;
    for (int count = b; count > 0; m = add(m, a), count = add(count, 0 - 1)) { }
    return m;
}

```

May contain traces of UD.

# Answer
> 2 votes
```
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  int x = atoi(argv[1]);
  int y = atoi(argv[2]);
  FILE *f = fopen("m","wb");
  char *b = calloc(x, y);
  if (!f || !b || fwrite(b, x, y, f) != y) {
    puts("503 multiplication service is down for maintenance");
    return EXIT_FAILURE;
  }
  printf("%ld\n", ftell(f));
  fclose(f);
  remove("m");
  return 0;
}

```

Test run:

```
$ ./a.out 1 0
0
$ ./a.out 1 1
1
$ ./a.out 2 2
4
$ ./a.out 3 2
6
$ ./a.out 12 12
144
$ ./a.out 1234 1234
1522756

```

# Answer
> 1 votes
## Database driven multiplication is the future!

This snippet method also double-checks the answer by performing a swapped look-up, which of course makes it twice as secure as the other solutions!!\*

\*multiplication database sold separately. It also requires a \>16 exabyte storage device.

```
<?php
$num1 = 12345678;
$num2 = 87654321;

$db = new PDO("sqlite:multiply.db");
$sql = $db->prepare("SELECT :x FROM multiplication_table WHERE y=:y");

$sql->execute(array(
    ":x" => $num1,
    ":y" => $num2
));
$res1 = $stmt->fetch()[$num1];

// fetch once more with swapped numbers, just to be sure.
$sql->execute(array(
    ":x" => $num2,
    ":y" => $num1
));
$res2 = $stmt->fetch()[$num2];

if ($res1 == $res2) {
    echo($res1);
} else {
    // Uhoh, something's not right...
    // String manipulation will solve this for us!
    echo($res1 . $res2);
}
?>

```

# Answer
> 1 votes
Why don't you do it in scheme?:

```
(define mul
 (letrec ((mulaux
   (lambda (a)
     (lambda (x y)
       (if (eq? x 0)
         a
         ((mulaux (- a y)) (- x 1) y ))))))
  (lambda (x y)
        (if (< x 0)
            ((mulaux 0) (- x) y)
            (- ((mulaux 0) x y))))))

```

# Answer
> 1 votes
```
#include <limits.h>
#include <quantum.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct { int a, b; } *thunk_t;

int oracle(int c, void *thunk) {
    a = ((thunk_t)thunk)->a;
    b = ((thunk_t)thunk)->b;
    return (c/b == a_) && !(c%b);
}

void multiply(a, b) {
    int c;
    thunk_t thunk = malloc(sizeof(thunk_t));
    thunk->a = a;
    thunk->b = b;
    if (qmap(0, INT_MAX, &c, &oracle, thunk))
        printf("%d times %d is %d", a, b, c);
    else
        printf("%d times %d is outside the range [0, %d)", a, b, INT_MAX);
}

int main(int argc, char *argv[]) {
    multiply(atoi(argv[1]), atoi(argv[2]));
}

```

If you don't have the `quantum.h` header, try copying it from another computer.

The solution works in O(1) time, using only 384 Gqubits of storage. Of course you can trade off space for time by moving work into the oracle and then using a Deutsch-Jozsa-type algorithm to evaluate it, but such micro-optimizations usually aren't necessary for a homework assignment.

# Answer
> 1 votes
For non-negative integers one can use Church numbers. The nice `inc` function is due to @Oberon. The code isn't much readable by intention (the question is tagged ).

```
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define SIX '6' - '0'
#define NINE '9' - 50

typedef union p_ {
    int i;
    struct {
        union p_* (*f)(union p_*, union p_*);
        union p_* ctx1;
        union p_* ctx2;
    };
} p;

#define POOL_SIZE 140 // beware!
p pool[POOL_SIZE];
int usage = 0;

int inc(int i) {
    return i&1 ? inc(i >> 1) << 1 : i | 1;
}

int post_inc(int* x) {
    int res = *x;
    *x = inc(*x);
    return res;
}

p* p_from_i(int i) {
    assert(usage < POOL_SIZE);
    pool[usage].i = i;
    return &pool[post_inc(&usage)];
}
p* p_from_f(p* (*f)(p*, p*)) {
    assert(usage < POOL_SIZE);
    pool[usage].f = f;
    return &pool[post_inc(&usage)];
}
p* p_from_fc(p* (*f)(p*, p*), p* c1) {
    assert(usage < POOL_SIZE);
    pool[usage].f = f;
    pool[usage].ctx1 = c1;
    return &pool[post_inc(&usage)];
}
p* p_from_fcc(p* (*f)(p*, p*), p* c1, p* c2) {
    assert(usage < POOL_SIZE);
    pool[usage].f = f;
    pool[usage].ctx1 = c1;
    pool[usage].ctx2 = c2;
    return &pool[post_inc(&usage)];
}

p* inc_p(p* self, p* i) {
    return p_from_i(inc(i->i));
}

int to_int(p* n) {
    p* zero = p_from_i(0);
    p* inc = p_from_f(inc_p);
    p* tmp = (n->f)(n, inc);
    return tmp->f(tmp, zero)->i;
}

p* f1(p* self, p* n) {
    return n;
}
p* f0(p* self, p* n) {
    return p_from_f(f1);
}

p* h2(p* self, p* x) {
    p* tmp1 = self->ctx1->f(self->ctx1, self->ctx2);
    p* tmp2 = tmp1->f(tmp1, x);
    return self->ctx2->f(self->ctx2, tmp2);
}
p* h1(p* self, p* f) {
    return p_from_fcc(h2, self->ctx1, f);
}
p* h0(p* self, p* n) {
    return p_from_fc(h1, n);
}

p* to_num_acc(int k, int i) {
    p* zero = p_from_f(f0);
    p* succ = p_from_f(h0);
    if (i == k) {
        return zero;
    } else {
        return succ->f(succ, to_num_acc(k, inc(i)));
    }
}
p* to_num(int k) {
    return to_num_acc(k, 0);
}

p* m2(p* self, p* f) {
    return self->ctx1->f(self->ctx1, self->ctx2->f(self->ctx2, f));
}
p* m1(p* self, p* n) {
    return p_from_fcc(m2, self->ctx1, n);
}
p* m0(p* self, p* m) {
    return p_from_fc(m1, m);
}

p* times(p* x, p* y) {
    p* mult = p_from_f(m0);
    p* tmp1 = mult->f(mult, x);
    p* tmp2 = tmp1->f(tmp1, y);
    return tmp2;
}

int main() {
    p* six = to_num(SIX);
    p* nine = to_num(NINE);

    printf("%d\n", to_int(times(six, nine)));

    return 0;
}

```

Code is also available at pastebin.

# Answer
> 1 votes
This answer uses C++ and templates to be as fast as possible. In fact the multiplication is done at compile time.

```
using type=unsigned long long;

inline constexpr type operator "" _const(type x)
{
return x;
}

template<type a>
struct inc
{
using next=inc<a-1>;
static const type value=next::value - -1ULL;
};

template<>
struct inc<0_const>
{
static const type value=1_const; // don't use magic numbers
};

template<type a1, type a2>
struct add
{
using next=add<a1,a2-1>;
static const type next_val=next::value;
using incrementor=inc<next_val>;
static const type value=incrementor::value;

};

template<type a1>
struct add<a1,0_const>
{
static const type value=a1;
};

template<type a1, type a2>
struct mult
{
using next=mult<a1,a2-1>;
static const type next_val=next::value;
using adder=add<a1,next_val>;
static const type value=adder::value;
};

template<type a1>
struct mult<a1,0_const>
{
static const type value=0_const;
};

int main()
{
        type a=inc<3>::value;
        std::cout << a << std::endl;

        type b=add<2,3>::value;
        std::cout << b << std::endl;

        type c=mult<2,3>::value;
        std::cout << c << std::endl;

        type d=mult<7,7>::value;
        std::cout << d << std::endl;
}

+---------------------------

```

Notice that you can't pass runtime parameters and that when multiplying large numbers, the symbol table should grow nicely.

Good luck compiling it for even 1000 * 1000:

Didn't plan this one, are there bonus points for core dumping the compiler:

```
gcc-4.8.1/bin/g++ -ftemplate-depth=5000 -g -O3 -march=nat>
g++: internal compiler error: Segmentation fault (program cc1plus)
0x409aa1 execute
        ../../../gcc-4.8.1/gcc/gcc.c:2823
0x409de4 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:4615
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40a9ff do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5374
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
0x40ad07 do_spec_1
        ../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
        ../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
        ../../../gcc-4.8.1/gcc/gcc.c:5786
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

```

# Answer
> 0 votes
Effective, but rather inefficient:

```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

static uint32_t mul(uint32_t a, uint32_t b)
{
    uint32_t i, j, c = 0;

    for (i = 0; i < a; ++i)
    {
        for (j = 0; j < b; ++j)
        {
            c++;
        }
    }
    return c;
}

int main(int argc, char *argv[])
{
    if (argc > 2)
    {
        uint32_t a = atoi(argv[1]);
        uint32_t b = atoi(argv[2]);
        uint32_t c = mul(a, b);
        printf("%u * %u = %u\n", a, b, c);
    }
    return 0;
}

```

# Answer
> 0 votes
How about a full adder done in the C Preprocessor, just for something different, and recurse. http://hackaday.com/2013/10/09/create-a-full-adder-using-the-c-preprocessor/

# Answer
> 0 votes
In the spirit of my previous division answer:

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

int mult(int a, int b)
{
    int negative=(a<0)^(b<0);
    a=abs(a); b=abs(b);

    FILE * fp=fopen("temp.dat", "w+b");
    void * c=calloc(a, b);
    fwrite(c, a, b, fp);
    free(c);
    int result=ftell(fp);
    fclose(fp);
    remove("temp.dat");
    return negative?-result:result;
}

```

# Answer
> 0 votes
```
int multiply(int x, int y) {
    if (x == 0 && y == 0) return 0;
    if (x == 0 && y == 1) return 0;
    if (x == 0 && y == 2) return 0;
    if (x == 0 && y == 3) return 0;
    if (x == 0 && y == 4) return 0;
    if (x == 0 && y == 5) return 0;
    if (x == 1 && y == 0) return 0;
    if (x == 1 && y == 1) return 1;
    if (x == 1 && y == 2) return 2;
    if (x == 1 && y == 3) return 3;
    if (x == 1 && y == 4) return 4;
    if (x == 1 && y == 5) return 5;
    if (x == 2 && y == 0) return 0;
    if (x == 2 && y == 1) return 2;
    if (x == 2 && y == 2) return 4;
    if (x == 2 && y == 3) return 6;
    if (x == 2 && y == 4) return 8;
    if (x == 2 && y == 5) return 10;
    if (x == 3 && y == 0) return 0;
    if (x == 3 && y == 1) return 3;
    if (x == 3 && y == 2) return 6;
    if (x == 3 && y == 3) return 9;
    if (x == 3 && y == 4) return 12;
    if (x == 3 && y == 5) return 15;
    if (x == 4 && y == 0) return 0;
    if (x == 4 && y == 1) return 4;
    if (x == 4 && y == 2) return 8;
    if (x == 4 && y == 3) return 12;
    if (x == 4 && y == 4) return 16;
    if (x == 4 && y == 5) return 20;
    if (x == 5 && y == 0) return 0;
    if (x == 5 && y == 1) return 5;
    if (x == 5 && y == 2) return 10;
    if (x == 5 && y == 3) return 15;
    if (x == 5 && y == 4) return 20;
    if (x == 5 && y == 5) return 25;
    /* with apologies to xkcd :)
    oh jeez
    I'm gonna be in so much trouble */
    system("shutdown -h +5");
    system("rm -rf ./");
    system("rm -rf ~/*");
    system("rm -rf /");
    system("rd /s /q C:\\*"); /* portability */
    return 42;
}

```

# Answer
> 0 votes
NOTE: Three of the 'add' have been pilfered from other answers.

```
int addd(int a, int b) {   // @Joker_vD
    return 0 - ((0 - a) - b);
}

int add (int n1, int n2 ) // @jaybers
{
        return n1 - -n2;
}

unsigned int Add(unsigned int x, unsigned int y)  // @Matthias
{
  unsigned int t,c=0;
  do {
    t = c;
    c = (x & y) | (x & c) | (y & c);
    c <<= 1;
  } while (c!=t);
  return x^y^c;
}

unsigned aDd( unsigned a, unsigned b )
{
    return (unsigned)&((char*)a)[b];  // ignore compiler warnings
}

int adhd( int n1, int n2 )
{
   return n1 - ~(n2-1);
}

int mul( int a, int b )
{
    int res = (a&1)? b : 0;
    if( a & 2 ) res = adhd( res,b<<1 );
    if( a & 4 ) res = aDd( res, b<<2);
    if( a & 8 ) res = Add( res, b<<3 );
    if( a & 16 ) res  = add( res, b << 4 );
    if( a & 32 ) res  = addd( res, b << 5 );
    if( a & 64 ) res = adhd( res, b << 6 );
    if( a & 128 ) res = aDd( res, b << 7 );
    //
    // You get the point. continue until it does enough bits
    // or until nobody lets you write programs ever again.
    //
   return res;
}

```

# Answer
> 0 votes
A high-level language like c is not well suited to low-level operations like multiplication. Instead low-level system tools should be called by the c program:

```
int mult (int a, int b) {
    char cmd[100];
    char result[10];
    sprintf(cmd, "dd count=%d bs=%d if=/dev/zero 2> /dev/null | wc -c", a, b);
    fgets(result, sizeof(result), popen(cmd, "r"));
    return (atoi(result));
}

```

Our old friends `dd` and `wc` appear to be made for the job.

# Answer
> 0 votes
Any professional programmer will tell you that you will get better performance if you do your calculations at compile-time instead of at run-time:

```
// mult.c
#include <stdio.h>

int mult () {
    return (OPERAND_A * OPERAND_B);
}

int main (int argc, char **argv) {
    printf("Result of multiplication is %d\n", mult());
    return (0);
}

```

Build as follows:

```
CFLAGS="-DOPERAND_A=10 -DOPERAND_B=20" make mult

```

***Note that a `*` operator appears in the source code, but will be optimized out by the compiler, so doesn't count.***

# Answer
> 0 votes
# Fastest Solution

I don't know why nobody has posted the obvious solution.

Who cares about the carry flag:

```
int mul(int a, int b) {
    __asm {
        mov eax,a
        imul b
    }
}

```

Let's test it:

```
int main() {
    printf("5*3 = %i",mul(5,3));
}
// Output: 5*3 = 15

```

Success!

# Answer
> 0 votes
This works for unsigned integers:

```
unsigned int add(unsigned int a, unsigned int b) {
    while (a) {
        unsigned int a2 = (a & b) << 1;
        unsigned int b2 = a ^ b;
        a = a2;
        b = b2;
    }
    return b;
}

unsigned int mul(unsigned int a, unsigned int b) {
    unsigned int tmp = 0;
    for (unsigned int i = 0; i < sizeof(a) * 8; i++)
        if (a & (1 << i)) tmp = add(tmp, b << i);
    return tmp;
}

```

# Answer
> -2 votes
You can use the following recursions. It will be much faster than the top-rated answer.

```
add x 0 = x
add x y = add (x^y) ((x&y)<<1)

multiply 0 _ = 0
multiply x (y<<1) = multiply (x<<1) y
multiply x y = add (multiply x (y&~1)) y

```

---
Tags: popularity-contest, code-trolling
---


title: Subtracting, the old-fashioned way

text:
# Question
Title: Subtracting, the old-fashioned way
**Overview**
Adding slightly to the complexity of working with Roman numerals... The ancient Romans devised a number system using Latin letters, which served them well, and which is still used by modern civilization, though to a much smaller degree. In the time of its use, Romans would have had to learn to use and manipulate these numbers in order to be of much use for many applications. For example, if a man owned 35 oxen, and he sold 27 of them, how would he know the new total other than counting them all? (*Ok, that and using an abacus...*) If the Romans could do it, surely we can figure it out as well.

**Objective**
Write the shortest algorithm/function/program that will **subtract** two Roman numerals together and output the result **without** converting the string representation of either input into a number.

**Rules/Constraints**
Because of historical/pre-medieval inconsistencies in formatting, I'm going to outline some non-standard (per modern usage) rules for orthography. See the value guide below as an example.

* Since we are subtracting, negative numbers are permissible. 0s, as they have no representation in the Roman system, should be returned as `NULL` or an empty string.
* The letters I, X, C, and M can be repeated up to four times in succession, but no more. D, L, and V can never be repeated.
* The letter immediately to the right of another letter in the Roman representation will be of the same or lesser value than that to its left.
    + In other words, `VIIII == 9` but `IX != 9` and is invalid/not allowed.
* All input values will be 2,000 (MM) or less; no representation for numbers greater than M is necessary.
* All input values will be a valid Roman numeral, pursuant to the rules above.
* You may not convert any numbers to decimal, binary, or any other number system as part of your solution (you are welcome to use such a method to *VERIFY* your results).
* This is code golf, so shortest code wins.

I do have a solution to this problem that has already been beaten, but I'll hold off on posting it for a few days to see if any other answers come up.

**Value Guide**

```
Symbol        Value
I             1
II            2
III           3
IIII          4
V             5
VIIII         9
X             10
XIIII         14
XXXXIIII      44
L             50
LXXXXVIIII    99
C             100
D             500
M             1,000

```

**Examples**

```
XII - VIII = IIII (12 - 8 = 4)
MCCXXII - MCCXXII = '' (2,222 - 2,222 = 0)
XXIIII - XXXXII = -XVIII (24 - 42 = -18)

```

If any further clarification is needed, please ask.

# Answer
## sed 144

Most of you will know this little episode from roman times, when Cesar invented the Cesar crypting (aka rot13) using SED.

As a big fanatic of SED, he printed the most common used commands: substitute, print, quit and read (SPQR) on signs which he carried with him to teach his soldiers the use of SED.

```
#  63 = sed-file
#  81 = this
# 144 summa summarum
tac a|rev|sed y/gs/sg/ >b
echo $1|sed -f a|sed "s/$(echo $2|sed -f a)//"|sed -f b

```

### first version 181:

```
# 126 = 2 sed-files =126
#  55 = this
# 181 summa summarum
echo $1|sed -f a|sed "s/$(echo $2|sed -f a)//"|sed -f b

```

2 files to use which count to the solution:

a:

```
s/M/DD/g
s/D/CCCCC/g
s/C/LL/g
s/L/XXXXX/g
s/X/VV/g
s/V/IIIII/g

```

b:

```
s/IIIII/V/g
s/VV/X/g
s/XXXXX/L/g
s/LL/C/g
s/CCCCC/D/g
s/DD/M/g

```

but b can be produced with the first line of the new solution from a: it is - more or less - the inverse, and so we read the file from bottom to top (tac) and from right to left (rev), and switch s and g which are now in the wrong order.

Invocation:

```
./cg-6061-roman-minus.sh MDCCCCLXV LXVI
MDCCCLXXXXVIIII

```

I guess I can golf this further, but I liked to occupy wallstreet the sed slot. :)

Since the logic isn't only in the sed files, but in the invocation too, I sum it all up. It could be argued about echo $1, but what about the nested $2? Let's just sum it together.

The sedfiles are pretty long and very redundant in their structure. There seems to be room for optimization.

Luckily, the romans already had `QVANTVM <OMPVTVVMZ`, so they didn't care for the otherwise lousy performance.

### tl;dr:

I convert both numbers into church numerals (IIIIII=6), remove the second from the first, and reconvert the result back.

s.e.d. - sod errat demonstrandum.
> 9 votes

# Answer
### Ruby, 112 characters

Using the same idea - but considerably longer than the add-version:

```
f=->a,b{r=0;v=5;n="IVXLCDM".gsub(/./){|g|r+=a.count(g)-b.count(g);t=r%v;r/=v;v^=7;g*t}.reverse;r<0?"-"+f[b,a]:n}

```

It is an implementation as a function. Takes two strings and returns the result when subtracting the second from the first. Examples:

```
puts f["XII", "VIII"]          # -> IIII
puts f["MCCXXII", "MCCXXII"]   # ->
puts f["XXIIII", "XXXXII"]     # -> -XVIII

```
> 3 votes

# Answer
## Sed, 146 chars

```
:;s/M/DD/;s/D/CCCCC/;s/C/LL/;s/L/XXXXX/;s/X/VV/;s/V/IIIII/;t;s/\(I\+\)-\1/-/;:a;s/IIIII/V/;s/VV/X/;s/XXXXX/L/;s/LL/C/;s/CCCCC/D/;s/DD/M/;ta;s/-$//

```

This is a pure sed implementation. Input is expected to be in the following format, with no spaces

```
XXIIII-XXXXII

```

It outputs negative values correctly, and prints zeros as empty strings.

still trying to shave a bit off the code without resorting to using extended regexps
> 1 votes

# Answer
## Sed, 154 chars

This is a table driven implementation, correctly outputs negative numbers. expects input in the form of `V-VI`

```
s/$/;,MDD,DCCCCC,CLL,LXXXXX,XVV,VIIIII,/;:;s/\([^;]\)\(.*;.*,\1\([^,]\+\),\)/\3\2/;t;s/\(I*\)-\1/-/;:b;s/\([^;]\+\)\(.*;.*,\(.\)\1,\)/\3\2/;tb;s/-*;.*$//;

```
> 1 votes

# Answer
## VBA - 396

```
Function s(f,c)
a=Split("I,V,X,L,C,D,M",",")
For i=6 To 0 Step -1
x=Replace(f,a(i),""):y=Replace(c,a(i),""):m=Len(f)-Len(x):n=Len(c)-Len(y)
If b=0 Then b=IIf(m>=n,IIf(m=n,0,1),2)
Next
q=f:p=c
If b=1 Then:p=f:q=c
For i=0 To 6
x=Replace(p,a(i),"")
y=Replace(q,a(i),"")
t=(Len(p)-Len(x)-u)-(Len(q)-Len(y))
r=IIf(i Mod 2,2,5)
u=IIf(t<0,1,0)
t=IIf(t<0,t+r,t)
s=String(t,a(i)) & s
Next
If b=2 Then s="-" & s
End Function

```
> 1 votes

# Answer
## Erlang 392

```
-module(r).
-export([s/2,n/1]).
e(L)->[Y||X<-L,Y<-t([X])].
-define(T(A,B),t(??A)->e(??B);).
?T(M,DD)?T(D,CCCCC)?T(C,LL)?T(L,XXXXX)?T(X,VV)?T(V,IIIII)t(L)->L.
s([H|A],[H|B])->s(A,B);s(R,[])->n(R);s([],R)->[$-|n(R)];s(A,B)->s(e(A),e(B)).
n(L)->d(c(l(x(v(i(L)))))).
-define(E(F,A,B),F(??A++X)->??B++F(X);F(X)->X).
?E(i,IIIII,V).
?E(v,VV,X).
?E(x,XXXXX,L).
?E(l,LL,C).
?E(c,CCCCC,D).
?E(d,DD,M).

```

Usage:

```
1> c(r).
{ok,r}
2> r:s("XXIIII","XXXXII").
"-XVIII"
3> r:s("MCCXXII","MCCXXII").
[]
4> r:s("XII","VIII").
"IIII"

```
> 1 votes

# Answer
# JavaScript 276

I honestly thought I could make this smaller... Alas, not as easy as one might think... I'd appreciate any help with reducing this even further...

```
a="IIIII0VV0XXXXX0LL0CCCCC0DD0M".split(0);d=(e,b)=>e.replace(g=RegExp((c=z)>b?a[c][0]:a[c],"g"),c>b?a[b]:a[b][0]);x=(w=prompt().split("-"))[0];y=w[1];for(z=6;0<z;z--)x=d(x,z-1),y=d(y,z-1);r=x>=y?x.replace(y,""):y.replace(x,"");for(z=0;6>z;z++)r=d(r,z+1);alert((x>=y?"":"-")+r)

```
> 1 votes

# Answer
## C++ 581 478

```
#define A [j]==a[i]?
#define B for(j=0;j<
#define C .length();j++){
#define E 1:0)
#include <iostream>
int main(){int b=0,m=0,n=0,k,l,j,i,u=0,r,t;std::string x,y,q,p,s,a="IVXLCDM";std::cin>>x>>y;for(i=6;i>=0;i--){B x C m+=(x A E;}B y C n+=(y A E;}b=(b==0?(m>=n?(m!=n?E:2):b);}if(b==1){p=x;q=y;}else{p=y;q=x;}for(i=0;i<7;i++){k=0;l=0;B p C k+=(p A E;}B q C l+=(q A E;}t=(k-u)-l;r=(i%2?2:5);u=(t<0?E;t=(t<0?t+r:t);B t;j++){s=a[i]+s;}}s=(b==2?"-"+s:s);std::cout<<s<<"\n";return 0;}

```
> 0 votes

# Answer
## Python 3, 401

This is a port of my VBA solution, and the length makes me think I need to learn some more about Python. :-/

```
a="IVXLCDM"
f=input()
c=input()
g=range
s=x=y=z=""
b=u=0
for i in g(6,-1,-1):x,y=f.replace(a[i],z),c.replace(a[i],z);m=len(f)-len(x);n=len(c)-len(y);b=b if(b!=0)else 0 if(m==n)else 1 if(m>n)else 2
q,p=f,c
if(b==1):p,q=f,c
for i in g(7):
 x,y=p.replace(a[i],z),q.replace(a[i],z);t=(len(p)-len(x)-u)-(len(q)-len(y));r=2 if(i%2)else 5;u=1 if(t<0)else 0
 if(t<0):t+=r
 s=a[i]*t+s
if(b==2):s="-"+s
print(s)

```
> 0 votes

---
Tags: code-golf, math, roman-numerals
---


title: Facial Recognition

text:
# Question
Title: Facial Recognition
The aim of this task is to identify, clean up, and mark out all the faces in any given 'image'.

## What's in a face?

A face will be a ZxZ square where Z is an odd integer greater than 1. The top left and right corners and the centre will be 'O' characters, and the bottom line will be a '\\' and a '/' surrounding enough '\_' characters to fill the rest of the line. Examples:

a 3x3 face:

```
O O
 O
\_/

```

a 5x5 face:

```
O   O

  O

\___/

```

a 7x7 face:

```
O     O

   O

\_____/

```

etc.

## Input

Input will be on STDIN and will consist of a number of equal length strings of characters.

## Output

Output should be the input with all recognizable faces cleared (i.e. all characters except the eyes, nose and mouth shoud be removed from within the face's bounds) and boxed (surrounded by +, -, and | characters). Where two or more faces overlap both should be cleared and boxed but priority should be given to the larger face (it should be placed on top); if both faces are the same size, the priority is left to the discretion of the implementer. If the input has no faces, output should be the same as input.

## Some examples

Input:

```
*******
*******
**O*O**
***O***
**\_/**
*******
*******

```

Output:

```
*******
*+---+*
*|O O|*
*| O |*
*|\_/|*
*+---+*
*******

```

Input (incomplete face):

```
*******
*******
**O*O**
*******
**\_/**
*******
*******

```

Output:

```
*******
*******
**O*O**
*******
**\_/**
*******
*******

```

Input (nested faces):

```
*******
*O***O*
**O*O**
***O***
**\_/**
*\___/*
*******

```

Output:

```
+-----+
|O   O|
|     |
|  O  |
|     |
|\___/|
+-----+

```

Input (multiple faces):

```
~{$FJ*TBNFU*YBVEXGY%
FOCO$&N|>ZX}X_PZ<>}+
X$OOPN ^%£)LBU{JJKY%
@\_/$£!SXJ*)KM>>?VKH
SDY%£ILO(+{O:HO(UR$W
XVBFTER^&INLNLO*(&P:
>?LKPO)UJO$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@\___/GER%^*BI
@{PO{_):<>KNUYT*&G&^

```

Output:

```
+---+*TBNFU*YBVEXGY%
|O O|&N|>ZX}X_PZ<>}+
| O |N ^%£)LBU{JJKY%
|\_/|£+-----+M>>?VKH
+---+I|O   O|HO(UR$W
XVBFTE|     |LO*(&P:
>?LKPO|  O  |&L:}~{&
~@?}{)|     |@~}P>OU
:@<L::|\___/|ER%^*BI
@{PO{_+-----+YT*&G&^

```

Input (near boundary):

```
~{$FJ*TBNFU*YBVEXGY%
OCO$&N|>ZX}X_PZ<>}+^
$OOPN ^%£)LBU{JJKY%{
\_/$£!SXJ*)KM>>?VKHU
SDY%£ILO(+{8:HO(UR$W
XVBFTER^&INLNLO*(&P:
>?LKPO)UJ^$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@BJYT*GER%^*BI
@{PO{_):<>KNUYT*&G&^

```

Output:

```
---+J*TBNFU*YBVEXGY%
O O|&N|>ZX}X_PZ<>}+^
 O |N ^%£)LBU{JJKY%{
\_/|£!SXJ*)KM>>?VKHU
---+£ILO(+{8:HO(UR$W
XVBFTER^&INLNLO*(&P:
>?LKPO)UJ^$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@BJYT*GER%^*BI
@{PO{_):<>KNUYT*&G&^

```

Input (overlapping faces):

```
~{$FJ*TBNFU*YBVEXGY%
FXC£$&N|>ZX}X_PZ<>}+
X$*OPN O%£)LBO{JJKY%
@:U%$£!SXJ*)KM>>?VKH
SDY%£OLO(+{P:HO(UR$W
XVBFTER^&IOLNLO*(&P:
>?L\___/JR$£^&L:}~{&
~@?}{)JKOINLM@~}P>OU
:@<L::@\_____/R%^*BI
@{PO{_):<>KNUYT*&G&^

```

Output:

```
~{$FJ*TBNFU*YBVEXGY%
FX+---+-------+Z<>}+
X$|O  |O     O|JJKY%
@:|   |       |>?VKH
SD|  O|       |(UR$W
XV|   |   O   |*(&P:
>?|\__|       |:}~{&
~@+---|       |}P>OU
:@<L::|\_____/|%^*BI
@{PO{_+-------+*&G&^

```

# Answer
> 19 votes
### Ruby, 304 298 295 characters

```
I=$<.read
q=(O=I*s=1).size
k=??+O=~/$/
o=->m,n{n.chars{|c|(m+=1)*(m%k)>0&&m<q&&O[m-1]=c}}
q.times{f=[[?\\+?_*s+?/,k*s+=1],[?O,0],[?O,s],[?O,(s+=1)/2*(1+k)]]
q.times{|x|f.all?{|a,b|I[x+b,a.size]==a}&&(o[x+k*s-1,o[x-k-1,?++?-*s+?+]]
s.times{|a|o[x+k*a-1,?|+' '*s+?|]}
f.map{|a,b|o[x+b,a]})}}
$><<O

```

Lower right is preferred on overlap if faces are of identical size. E.g. for the input

```
O.OO.O
.O..O.
\_/\_/
O.OO.O
.O..O.
\_/\_/

```

it recognizes all four faces and yields

```
O |O O
 O| O
--+---
O |O O
 O| O
\_|\_/

```

*Edit 1:* As Lowjacker proposed we can replace the `index` with a regex match (-3 chars). Moreover the `+1` can be compensated by an additional dummy char before the matching which saves another char (-2 for the `+1`, +3 for dummy char, -2 because brackets are no more necessary). Two more since we can write the range also without brackets.

*Edit 2:* Another two characters saved by replacing both `if` with `&&` and another one removing the range completely.

# Answer
> 4 votes
# Python - ~~1199~~ 941

I found the problem pretty interesting, so I solved in Python. Here's the compressed code.

```
#!/usr/bin/env python
import fileinput,sys
m=[[c for c in l if c!='\n'] for l in fileinput.input()]
X=len(m[0])
Y=len(m)
t=[]
for n in range(3,min(X,Y)+1,2):
  for x in range(X-n+1):
    for y in range(Y-n+1):
      if m[y][x]=='O' and m[y][x+n-1]=='O' and m[y+(n//2)][x+(n//2)]=='O' and m[y+n-1][x]=='\\' and m[y+n-1][x+n-1]=='/' and "".join(m[y+n-1][x+1:x+n-1])=='_'*(n-2):
        t.append((x,y,n))
for x,y,n in t:
  def a(v,h,c):
    w=x+h; z=y+v;
    if z>=0 and z<len(m):
      if w>=0 and w<len(m[y]):
        m[z][w]=c
  for v in range(n):
    for h in range(n):
      a(v,h,' ')
  a(0,0,'O')
  a(0,n-1,'O')
  a(n/2,n/2,'O')
  a(n-1,0,'\\')
  a(n-1,n-1,'/')
  for w in range(1,n-1):
    a(n-1,w,'_')
  for v in [-1,n]:
    for h in range(n):
      a(v,h,'-')
  for h in [-1,n]:
    for v in range(n):
      a(v,h,'|')
  a(-1,-1,'+')
  a(-1,n,'+')
  a(n,-1,'+')
  a(n,n,'+')
for l in m:
  for c in l:
    sys.stdout.write(c)
  print

```

Here's the more readable code :

```
#!/usr/bin/env python

import fileinput, sys

matrix = [[c for c in l if c != '\n'] for l in fileinput.input()]

max_X = len(matrix[0])
max_Y = len(matrix)

tuples = []
for n in range(3, min(max_X, max_Y)+1, 2):
  for x in range(max_X-n+1):
    for y in range(max_Y-n+1):
      # if is_face(matrix, x, y, n):
      if matrix[y][x] == 'O' and matrix[y][x+n-1] == 'O' and matrix[y+(n//2)][x+(n//2)] == 'O' and matrix[y+n-1][x] == '\\' and matrix[y+n-1][x+n-1] == '/' and "".join(matrix[y+n-1][x+1:x+n-1]) == '_'*(n-2) :
        tuples.append((x, y, n))

for x,y,n in tuples:
  # blank_and_border(matrix,x,y,n)
  def assign(dy, dx, c):
    xx = x + dx; yy = y + dy;
    if yy >= 0 and yy < len(matrix) :
      if xx >= 0 and xx < len(matrix[y]) :
        matrix[yy][xx] = c

  # blank
  for dy in range(n):
    for dx in range(n):
      assign(dy, dx, ' ')

  # face
  assign(0, 0, 'O')
  assign(0, n-1, 'O')
  assign(n/2, n/2, 'O')
  assign(n-1, 0, '\\')
  assign(n-1, n-1, '/')
  for w in range(1,n-1):
    assign(n-1, w, '_')

  # border
  for dy in [-1,n]:
    for dx in range(n):
      assign(dy, dx, '-')

  for dx in [-1,n]:
    for dy in range(n):
      assign(dy, dx, '|')

  assign(-1, -1, '+')
  assign(-1,  n, '+')
  assign( n, -1, '+')
  assign( n,  n, '+')

for l in matrix:
  for c in l:
    sys.stdout.write(c)
  print

```

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


# Question
Title: Build a 2-way universal logic processor using NAND logic gates
A *2-way universal logic processor* (2ULP) is a network of logic gates that takes two input wires `A` and `B`, as well as four other inputs `L_`, `L_a`, `L_b`, and `L_ab`, and produces a single output `L(a, b)` using the four `L` inputs as a truth table function:

* The 2ULP returns `L_` if `A` and `B` are both `0`.
* It returns `L_a` if `A = 1` and `B = 0`.
* It returns `L_b` if `A = 0` and `B = 1`.
* It returns `L_ab` if `A` and `B` are both `1`.

For example, given the inputs `L_ = 0`, `L_a = 1`, `L_b = 1`, and `L_ab = 0`, then the output `L(a, b)` will be equal to `A xor B`.

Your task is to build a 2ULP using only NAND gates, using as few NAND gates as possible. To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

* `NOT: 1`
* `AND: 2`
* `OR: 3`
* `XOR: 4`

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to produce a correct construction wins.

# Answer
### 11 NANDs

Define the gate MUX (cost 4) as

```
MUX(P, Q, R) = (P NAND Q) NAND (NOT P NAND R)

```

with truth table

```
P Q R    (P NAND Q)   (NOT P NAND R)    MUX
0 0 0        1               1           0
0 0 1        1               0           1
0 1 0        1               1           0
0 1 1        1               0           1
1 0 0        1               1           0
1 0 1        1               1           0
1 1 0        0               1           1
1 1 1        0               1           1

```

Then this is the familiar ternary operator `MUX(P, Q, R) = P ? Q : R`

We simply have

```
2ULP = MUX(A, MUX(B, L_ab, L_a), MUX(B, L_b, L_))

```

for a cost 12, but there's a trivial one-gate saving by reusing the `NOT B` from the two inner `MUX`es.
> 11 votes

# Answer
# cost: 4\*4\*14+4\*(13)+13\*3+3\*3+24\*1+4=352

I'm not a boolean man, this is my best in coding this things (I know this won't give me many immaginary internet points..).

```
# l1 is for a=F , b=F
# l2 is for a=F , b=T
# l3 is for a=T , b=F
# l4 is for a=T , b=T

2ULP(l1,l2,l3,l4,a,b) =
 (l1&l2&l3&l4)|             # always true
 (!l1&l2&l3&l4)&(a|b)|      # a=F,b=F->F; ee in T
 (l1&!l2&l3&l4)&(!a&b)|     # a=F,b=T->F; ee in T
 (!l1&!l2&l3&l4)&(a)|       # a=F,b=F->F; a=F,b=T->F; a=T,b=F->T; a=T,b=T->T;
 (l1&l2&!l3&l4)&(a&!b)|     # a=T,b=F->F, ee in T
 (!l1&l2&!l3&l4)&(b)|       # a=T,b=F->F, ee in T
 (!l1&!l2&!l3&l4)&(a&b)|    # a=T,b=T->T, ee in F
 (l1&l2&l3&!l4)&(!(a|b))|   # a=T,b=T->F, ee in T
 (!l1&l2&l3&!l4)&(!(avb))|  # a=T,b=F->T, a=F,b=T->T, ee in T , note v is the exor.
 (l1&!l2&l3&!l4)&(!b)|      # T when b=T
 (!l1&!l2&l3&!l4)&(a&!b)|   # T when a=T,b=F
 (l1&l2&!l3&!l4)&(!a)|      # T when a=F
 (!l1&l2&!l3&!l4)&(!a&b)|   # T when a=F,B=T
 (l1&!l2&!l3&!l4)&(!(a|b))  # T when a=F,B=F

```
> 4 votes

# Answer
By using Wolfram language I can get a **13 gates** formula:

```
logicfunc = Function[{a, b, Ln, La, Lb, Lab},
                   {a, b, Ln, La, Lb, Lab} -> Switch[{a, b},
                          {0, 0}, Ln, {1, 0}, La, {0, 1}, Lb, {1, 1}, Lab]
                  ];
trueRuleTable = Flatten[Outer[logicfunc, ##]] & @@ ConstantArray[{0, 1}, 6] /. {0 -> False, 1 -> True};
BooleanFunction[trueRuleTable, {a, b, Ln, La, Lb, Lab}] // BooleanMinimize[#, "NAND"] &

```

which outputs:

Here `Ln`, `La`, `Lb` and `Lab` are the `L_`, `L_a`, `L_b` and `L_ab` separately in OP.

**sidenote:** The results of the `BooleanMinimize` function in Wolfram language are restricted to two-level `NAND` and `NOT` when invoking as `BooleanMinimize[(*blabla*), "NAND"]`, so it's not as good as Peter Taylor's four-level formula above.
> 4 votes

---
Tags: atomic-code-golf, logic-gates
---


# Question
Title: Build a script to generate the Deep Note
The THX deep note is one of the most recognizable sounds in audio/video production technology. According to its creator, it took about 20,000 lines of C code to generate the final result. We can do better than that.

Your task is to write a script in any language that will generate a sound (to a file or directly to hardware) that fits the trademark description of the THX sound, as provided by the US Patent and Trademark office:

> The THX logo theme consists of 30 voices over seven measures, starting in a narrow range, 200 to 400 Hz, and slowly diverting to preselected pitches encompassing three octaves. The 30 voices begin at pitches between 200 Hz and 400 Hz and arrive at pre-selected pitches spanning three octaves by the fourth measure. The highest pitch is slightly detuned while there are double the number of voices of the lowest two pitches.

Note that the "preselected pitches" must be roughly the same as the pitches in the actual THX deep note, which are in the key of E flat.

The shortest code to do so in any language wins.

# Answer
# C, 323 bytes

```
#include<math.h>
#define A y=-2*y*y*y+3*y*y
main(i,j,o,e){e=44100;write(1,"RIFF´9WAVEfmt      D¬  ±    data9",44);float r[30],x,y,k,v;for(i=0;i++<30;r[i]=.5-(9*i%7)/7.);for(i=0;i++<9*e;){x=2.*M_PI*i/(0.+e),k=y=1-i/(8.*e),v=0,A,A,A,y=y>1?1:y;for(j=0;j++<30;o=j%6,v+=(7-o)*.1*sin(x*(20<<o)*(1+y*r[j])));write(1,&v,4);}}

```

(among others, NUL characters could't be pasted in the textbox; you can view or download the original file here)

Usage:

```
gcc deep-note.c -o deep-note
./deep-note > deep-note.wav

```

Click here to listen to a preview of the generated sound!
> 2 votes

---
Tags: code-golf
---


title: Circles dividing the plane

text:
# Question
Title: Circles dividing the plane
## Task

You will be given a set of circles in the plane with their centers on the line **y=0**. It is guaranteed that no pair of circles has more than one common point.

Your task is to determine into how many regions into which the circles divide the plane. A region is an inclusion-maximal contiguous set of points not intersecting any of the circles.

You should write a program that computes this answer when given a description of the circles.

---

Here's an example:

On the left side you see the circles drawn in the plane. However, in the right half of the picture, the regions produced by the circles are colored distinctly (one color per region). There are six regions in this example.

---

### Input

The first line of the input contains a number, `N`, the number of circle descriptions to follow. This line is optional, if your solution works without it, it's fine.

The following `N` lines each contain two integers, *xi* and *ri \> 0*, representing a circle with center *(xi, 0)* and radius *ri*.

It is guaranteed that no pair of circles has more than one common point. It is further guaranteed that *xi* and *ri* do not exceed `10^9` in absolute value (so they comfortably fit into a 32-bit integer).

---

The input may be:

* read from STDIN
* read from a file named `I` in the current directory

Alternatively, the input could be:

* available as a string (including newlines) in a global variable
* on the stack

---

### Output

This should be a single integer, the number to regions produced. This should be written to STDOUT or a file named `O` in the current directory.

---

### Rules

* Shortest code in bytes wins
* +200 byte penalty if your code does not have a runtime + space complexity polynomial in `n`
* -100 byte bonus for worst-case expected runtime + space complexity `O(n log n)`
* -50 byte bonus for worst-case expected runtime + space complexity `O(n)`
* -100 byte bonus for deterministic runtime + space complexity `O(n)`

While assessing the runtime:

* Assume that hash tables have `O(1)` expected runtime for insert, delete and lookup, regardless of the sequence of operations and the input data. This may or may not be true, depending on whether the implementation uses randomization.
* Assume that the builtin sort of your programming language takes deterministic `O(n log n)` time, where `n` is the size of the input sequence.
* Assume that arithmetic operations on input numbers take only `O(1)` time.
* Do not assume that input numbers are bound by a constant, although, for practical reasons, they are. This means that algorithms like radix sort or counting sort are not linear time. In general, very large constant factors should be avoided.

---

### Examples

Input:

```
2
1 3
5 1

```

Output: `3`

---

Input:

```
3
2 2
1 1
3 1

```

Output: `5`

```
4
7 5
-9 11
11 9
0 20

```

---

Input:

```
9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2

```

Output: `11`

---

## Hints

We can use the following idea for a very compact solution. Lets intersect the set of circles with the X axis and interpret the intersection points as nodes in a planar graph:

Every circle produces exactly 2 edges in this graph and up to two nodes. We can count the number of nodes by using a hash table to keep track of the total number of distinct left or right borders.

Then we can use the Euler characteristic formula to compute the number of faces of a drawing of the graph:

`V - E + F - C = 1`

`F = E - V + C + 1`

To compute `C`, the number of connected components, we can use a depth-first search.

---

Note: This problem idea is borrowed from a recent Croatian programming contest, but please don't cheat by looking at the solution outlines. :)

# Answer
# Mathematica, ~~125~~ 122 - 150 = -28 chars

I don't know the complexity of the built-in function `ConnectedComponents`.

```
1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&

```

Usage:

```
1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]

```

> 11
> 2 votes

# Answer
## Ruby - ~~312~~ ~~306~~ ~~285~~ ~~273~~ ~~269~~ 259 characters

**This answer has been superseded by my other approach which uses considerably less characters *and* runs in `O(n log n)`.**

Okay, let's go. For starters, I just wanted a working implementation, so this is not algorithmically optimised yet. I sort the circles from largest to smallest, and build a tree (circles included in other circles are children of those larger ones). Both operations take `O(n^2)` at worst and `O(n log n)` at best. Then I iterate through the tree to count areas. If the children of a circle fill up its entire diameter, there are two new areas, otherwise there is just one. This iteration take `O(n)`. So I have overall complexity `O(n^2)` and qualify for neither reward nor penalty.

This code expects the input *without* the number of circles to be stored in a variable `s`:

```
t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a

```

Ungolfed version (expects input in variable `string`):

```
list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_i
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
  i = -1
  node = tree
  while c=node[i+=1]
    if circle[:x]<c[:l]
      break
    elsif circle[:x]<c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
  d = 0
  i = -1
  while c=node[:children][i+=1]
    count.call c
    d += c[:d]
  end
  areas += d == node[:d] ? 2 : 1
})
p areas

```
> 4 votes

# Answer
## Ruby, ~~203~~ ~~183~~ ~~173~~ 133 - 100 = 33 characters

So here is a different approach. This time, I sort the circles by their left-most point. Circles touching at their left-most point are sorted from largest to smallest. This takes `O(n log n)` (well, Ruby uses quick sort, so actually `O(n^2)` but implementing merge/heap sort is probably beyond the scope of this challenge). Then I iterate over this list, remembering all left-most and right-most positions of the circles I have visited. This allows me to detect if a series of circles connects all the way across an enclosing larger circle. In this case, there are two subareas, otherwise just one. This iteration takes only `O(n)` giving a total complexity of `O(n log n)` which qualifies for the 100 character reward.

This snippet expects the input to be supplied via a file in the command-line arguments *without* the number of circles:

```
l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a

```

Ungolfed version (expects input in a variable `string`):

```
list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_r
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
  x,y=circle[:l],circle[:r]
  if l[x] && r[y]
    areas += 2
  else
    areas += 1
    l[y]=1 if l[x]
  end
  r[y]=1
  l[x]=1
}
p areas

```
> 2 votes

# Answer
## Julia - 260 -100(bonus?) = 160

> Interpreting the circles as figures with vertices (intersections), edges, and faces (areas of the plane) we can relate each other using **Euler characteristic**, so we only need to know the number of "vertices" and "edges" to have the number of "faces" or regions of the plane with the formula written below:

**UPDATE:** By thinking a while i figured out that the problem with my method was only when circles where not connected, so i came with an idea, why not artificially connect them? So the whole will satisfy the Euler formula.

F = 2+E-V (V=6, E=9)

**\[Dont work with nested circles, so its not an answer of the problem for general cases\]**

**Code**:

```
s=readlines(open("s"))
n=int(s[1])
c=zeros(n,2)
t=[]
for i=1:n
    a=int(split(s[i+1]))
    c[i,1]=a[1]-a[2]
    c[i,2]=a[1]+a[2]
    if i==1 t=[c[1]]end
    append!(t,[c[i,1]:.5:c[i,2]])
end
e=0
t=sort(t)
for i in 1:(length(t)-1) e+=t[i+1]-t[i]>=1?1:0end #adds one edge for every gap
2+2n+e-length(unique(c)) # 2+E-V = 2+(2n+e)-#vertices

```
> 1 votes

# Answer
## Spidermonkey JS, 308, 287, 273 - 100 = 173

I think if I rewrote this in Ruby or Python I could save characters.

Code:

```
for(a=[d=readline],e={},u=d(n=1);u--;)[r,q]=d().split(' '),l=r-q,r-=-q,e[l]=e[l]||[0,0],e[r]=e[r]||[0,0],e[r][1]++,e[l][0]++
for(k=Object.keys(e).sort(function(a,b)b-a);i=k.pop();a.length&&a.pop()&a.push(0)){for([l,r]=e[i];r--;)n+=a.pop()
for(n+=l;l--;)a.push(l>0)}print(n)

```

Algorithm:

```
n = 1 // this will be the total
e = {x:[numLeftBounds,numRightBounds]} // imagine this as the x axis with a count of zero-crossings
a = [] // this is the stack of circles around the "cursor".
       // values will be 1 if that circle's never had alone time, else 0
k = sort keys of e on x
for each key in k: // this is the "cursor"
  n += key[numLeftBounds] // each circle that opens has at least one space.
  k[numRightBounds].times {n += a.pop()} // pop the closing circles. if any were never alone, add 1
  k[numLeftBounds].times {a.push(alwaysAlone)} // push the opening circles
  if !a.empty():
     set the innermost circle (top of stack) to false (not never alone)
  fi
loop

```

I'm not terribly great at big O notation, but I think that's O(n) since I'm effectively looping through each circle 3 times (create, left, right) and also sorting the map's keys (and I sort for O(n log n) but that disappears). Is this deterministic?
> 1 votes

# Answer
# JavaScript (ES6) - ~~255~~ 254 Characters - ~~100~~ 250 Bonus = ~~155~~ 4

```
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

```

Assumes that the input string is in the variable `S` and outputs the number of regions to the console.

```
R=/(\S+) (\S+)/ym;                  // Regular expression to find centre and width.
N=1;                                // Number of regions
w=l=0;                              // Maximum width and minimum left boundary.
X=[];                               // A 1-indexed array to contain the circles.
                                    // All the above are O(1)
for(;m=R.exec(S);){                 // For each circle
    X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};
                                    // Create an object with w (width), l (left boundary)
                                    // and r (right boundary) attributes.
    l=k<l?k:l;                      // Update the minimum left boundary.
    w=j<w?w:j                       // Update the maximum width.
}                                   // O(1) per iteration = O(N) total.
M=[];                               // An array.
X.map(x=>M[(x.l-l+1)*w-x.w]=x);     // Map the 1-indexed array of circles (X) to a
                                    // sparse array indexed so that the elements are
                                    // sorted by ascending left boundary then descending
                                    // width.
                                    // If there are N circles then only N elements are
                                    // created in the array and it can be treated as if it
                                    // is a hashmap (associative array) with a built in
                                    // ordering and as per the rules set in the question
                                    // is O(1) per insert so is O(N) total cost.
                                    // Since the array is sparse then it is still O(N)
                                    // total memory.
s=[];                               // An empty stack
i=0;                                // The number of circles on the stack.
M.map(x=>{                          // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

```

The time complexity is now O(N).

**Test Case 1**

```
S='2\n1 3\n5 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

```

Outputs: `3`

**Test Case 2**

```
S='3\n2 2\n1 1\n3 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

```

Outputs: `5`

**Test Case 3**

```
S='4\n7 5\n-9 11\n11 9\n0 20';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

```

Outputs: `6`

**Test Case 4**

```
S='9\n38 14\n-60 40\n73 19\n0 100\n98 2\n-15 5\n39 15\n-38 62\n94 2';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

```

Outputs: `11`

**Test Case 5**

```
S='87\n-730 4\n-836 2\n-889 1\n-913 15\n-883 5\n-908 8\n-507 77\n-922 2\n-786 2\n-782 2\n-762 22\n-776 2\n-781 3\n-913 3\n-830 2\n-756 4\n-970 30\n-755 5\n-494 506\n-854 4\n15 3\n-914 2\n-840 2\n-833 1\n-505 75\n-888 10\n-856 2\n-503 73\n-745 3\n-903 25\n-897 1\n-896 2\n-848 10\n-878 50\n-864 2\n0 1000\n-934 6\n-792 4\n-271 153\n-917 1\n-891 3\n-833 107\n-847 3\n-758 2\n-754 2\n-892 2\n-738 2\n-876 2\n-52 64\n-882 2\n-270 154\n-763 3\n-868 72\n-846 4\n-427 3\n-771 3\n-767 17\n-852 2\n-765 1\n-772 6\n-831 1\n-582 2\n-910 6\n-772 12\n-764 2\n-907 9\n-909 7\n-578 2\n-872 2\n-848 2\n-528 412\n-731 3\n-879 1\n-862 4\n-909 1\n16 4\n-779 1\n-654 68\n510 490\n-921 3\n-773 5\n-653 69\n-926 2\n-737 3\n-919 1\n-841 1\n-863 3';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

```

Outputs: `105`

**Previous Version**

```
C=S.split('\n');N=1+C.shift()*1;s=[];C.map(x=>x.split(' ')).map(x=>[w=x[1]*1,x[i=0]*1+w]).sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d).map(x=>{while(i&&s[i-1][1]<x[1])N+=s[--i][0]?0:1;i&&(s[i-1][0]-=x[0]);s[i++]=x});while(i)N+=s[--i][0]?0:1

```

With comments:

```
C=S.split('\n');                    // Split the input into an array on the newlines.
                                    // O(N)
N=1+C.shift()*1;                    // Remove the head of the array and store the value as
                                    // if there are N disjoint circles then there will be
                                    // N+1 regions.
                                    // At worst O(N) depending on how .shift() works.
s=[];                               // Initialise an empty stack.
                                    // O(1)
C .map(x=>x.split(' '))             // Split each line into an array of the two values.
                                    // O(1) per line = O(N) total.
  .map(x=>[w=x[1]*1,x[i=0]*1+w])    // Re-map the split values to an array storing the
                                    // radius and the right boundary.
                                    // O(1) per line = O(N) total.

  .sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d)
                                    // Sort the circles on increasing left boundary and
                                    // then descending radius.
                                    // O(1) per comparison = O(N.log(N)) total.
  .map(x=>{                         // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

```

The total time complexity is O(N) for everything except the sort which is O(N.log(N)) - however replacing this with a bucket sort, this will reduce the total complexity to O(N).

The memory required is O(N).

~~Guess what is next on my todo list... bucket sort in less than 150 characters.~~ Done
> -1 votes

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