title: Practical Golf - US States

text:
# Question
Title: Practical Golf - US States
My family has an e-commerce business. On our own site, we force people to choose their state from a dropdown menu when they enter their address, but through some other channels we use, customers can enter anything they want into the box.

My mom loves the invoice templates I made for her, which are automagically generated. But because they're so pretty and balanced, she can't stand it when people WRITE OUT the names of their states, or worse, write something like "new jersey." She says it ruins the look.

My dad likes code to be lightweight. So rather than using a switch-case block, he wants a leaner solution.

So the challenge is to make a short function that takes the possible inputs and returns a two letter abbreviation (capitalized, for Mom). We're going to make a (faulty) assumption that our users can spell and always put a space in the name (where needed) or pass in the correct abbreviation. The scope is the 50 US states.

* New York
* new york
* NY
* ny

are all acceptable inputs for New York, and should output NY.

If something like New Yrok is passed in, the function can return the original value.

You can use any common language. This is a popularity contest, so the one with the most votes at the end of a week wins. I assume that this will favor novelty and utility.

**EDIT:** The description is story fluff, but I was working a similar project and thought that there must be a more interesting way to do it. I can do the project myself (already did) but I thought this was a good place for a more interesting challenge. By "Any common language" I was excluding custom languages/libraries designed for this challenge - I was trying to look for novel methods, rather than free code help. I figure everyone has done this at some point, but it would be fun to do it in an unusual way. I find that the most interesting projects are the ones where you tackle everyday tasks in new and interesting ways - that's why this is a popularity contest rather than golf.

# Answer
> 28 votes
# Ruby

Thought it would be interesting to extract the state abbreviations without writing any of the names or abbrevations explicitly. This one does not take misspelling of the input into consideration, because we don't care about such thing here on codegolf.SE, *rihgt*?

```
def f(s)
  [
    /(.).* (.)/,              # two words
    /^([CDGHKLPV]).*(.)$/,    # first and last letter
    /^(.).*([ZVX])/,          # unique letter
    /^([NFOUW])(.)/,          # two first letters
    /^(.)([DNR])/,            # unique second letter
    /^(.).*(L|N)\2/,          # double letters
    /^(.).SS(A|O)/,           # double S before the one used
    /^(.).*?[SNW](.)/,        # identified by the letters before them
    /(.)(.)/                  # two first letters

  ].find { |r| r =~ s.upcase }
  $1+$2
end

```

It took a conciderable time to figure out clever patterns to match all the states. The order of the patterns is important -- each consecutive pattern applies to the remaining states that were not matched by a previous pattern:

All states with two words in them use the initial letters of the two words:
> **N**ew **H**ampshire, **N**ew **J**ersey, **N**ew **M**exico, **N**ew **Y**ork, **N**orth **C**arolina, **N**orth **D**akota, **R**hode **I**sland, **S**outh **C**arolina, **S**outh **D**akota, **W**est **V**irginia

All states beggining with any letter in {`CDGHKLPV`} use the first and last letter in the name:
> **C**aliforni**a**, **C**olorad**o**, **C**onnecticu**t**, **D**elawar**e**, **G**eorgi**a**, **H**awai**i**, **K**ansa**s**, **K**entuck**y**, **L**ouisian**a**, **P**ennsylvani**a**, **V**irgini**a**, **V**ermon**t**

Of the remaining states, the letters {`ZVX`} are unique:
> **A**ri**z**ona, **N**e**v**ada, **T**e**x**as

All remaining states beginning with {`FNOUW`} use the two first letters.
> **Fl**orida, **Ne**braska, **Oh**io, **Ok**lahoma, **Or**egon, **Ut**ah, **Wa**shington, **Wi**sconsin, **Wy**oming

Then, {`DNR`} are unique as second letters:
> **Ar**kansas, **In**diana, **Id**aho

It's really getting hard to make general patterns, but...

Only three remaining states use double `N` or `L`, and the double letter is used in the state abbreviation:
> **T**en**n**essee, **M**in**n**esota, **I**l**l**inois

`A` or `O` after double *S* is unique to
> **M**ass**a**chusetts and **M**iss**o**uri

Whenever {`SNW`} appear *before* other letters in the remaining state names, the letters *after them* are used in the abbreviations:
> **A**las**k**a, **M**arylan**d**, **M**ain**e**, **M**is**s**issippi, **M**on**t**ana, **I**ow**a**

Two left. These use the two first letters:
> **Al**abama, **Mi**chigan

---

It can be golfed of course:

# Ruby 2 – ~~191~~ ~~165~~ 154 characters

Another 26 characters off by uglifying the regexes a bit. Also, one of the original regexes turned out to be redundant!

```
gets;[/.* (.)/,/^[CDGHKLPV].*(.)$/,/.*([ZVX])/,/^[NFOUW](.)/,/^.([DNR])/,/.*(L|N)\1/,
/.*SS(A|O)/,/.*?[SNW](.)/,/.(.)/].find{|r|$_.upcase=~r}
puts $&[0]+$1

```

# Answer
> 3 votes
# C#

I used characters already in the states for the abbreviations to shorten up the state string.

```
public string GetAbbr(string state)
            {

                var states =
                    new[] {
                        "AlasKa", "ALabama", "AriZona", "ARkansas", "CAlifornia", "COlorado", "ConnecticuT",
                        "DElaware", "FLorida", "GeorgiA", "HawaiI", "IDaho", "ILlinois", "INdiana", "IowA", "KansaS",
                        "KentuckY", "LouisianA", "MainE", "MarylanD", "MAssachusetts", "MIchigan", "MinNnesota",
                        "MiSsissippi", "MissOuri", "MonTana", "NEbraska", "NeVada", "New Hampshire", "New Jersey",
                        "New Mexico", "New York", "North Carolina", "North Dakota", "OHio", "OKlahoma", "ORegon",
                        "PennsylvaniA", "Rhode Island", "South Carolina", "South Dakota", "TeNnessee", "TeXas", "UTah",
                        "VermonT", "VirginiA", "WAshington", "washington D.C.", "West Virginia", "WIsconsin", "WYoming"
                    };
                var all = states.ToDictionary(st => string.Concat(st.Where(char.IsUpper)));

                var wanted = all.FirstOrDefault(pair => state.ToUpper().Equals(pair.Value.ToUpper()) || state.ToUpper().Equals(pair.Key));

                return wanted.Key ?? state;
            }

```

# Answer
> 2 votes
# JavaScript (E6)

Here the bulk is the list of names, using the camelCase trick to shorten a bit. Golfed, 617 bytes.

```
F=i=>
  "AkAlAzArCaCoCtDeFlGaHiIdIlInIaKsKyLaMeMdMaMiMnMsMoMtNeNvNhNjNmNyNcNdOhOkOrPaRiScSdTnTxUtVtVaWaWvWiWyAlaskaAlabamaArizonaArkansasCaliforniaColoradoConnecticutDelawareFloridaGeorgiaHawaiiIdahoIllinoisIndianaIowaKansasKentuckyLouisianaMaineMarylandMassachusettsMichiganMinnesotaMississippiMissouriMontanaNebraskaNevadaNew hampshireNew jerseyNew mexicoNew yorkNorth carolinaNorth dakotaOhioOklahomaOregonPennsylvaniaRhode islandSouth carolinaSouth dakotaTennesseeTexasUtahVermontVirginiaWashingtonWest virginiaWisconsinWyoming"
  .match(/.[^A-Z]*/g).map((w,q)=>U(w,U(w)==U(i)?p=q%50:p),U=s=>s.toUpperCase(),p=-1)[p]||i

```

# Answer
> 0 votes
## Python

Decided just to do this as a code-golf challenge. Got it down to ~~906~~ ~~713~~ 694 chars with the help of daniero and hsl:

```
s='AK,AL,AZ,AR,CA,CO,CT,DE,FL,GA,HI,ID,IL,IN,IA,KS,KY,LA,ME,MD,MA,MI,MN,MS,MO,MT,NE,NV,NH,NJ,NM,NY,NC,ND,OH,OK,OR,PA,RI,SC,SD,TN,TX,UT,VT,VA,WA,WV,WI,WY,ALASKA,ALABAMA,ARIZONA,ARKANSAS,CALIFORNIA,COLORADO,CONNECTICUT,DELAWARE,FLORIDA,GEORGIA,HAWAII,IDAHO,ILLINOIS,INDIANA,IOWA,KANSAS,KENTUCKY,LOUISIANA,MAINE,MARYLAND,MASSACHUSETTS,MICHIGAN,MINNESOTA,MISSISSIPPI,MISSOURI,MONTANA,NEBRASKA,NEVADA,NEW HAMPSHIRE,NEW JERSEY,NEW MEXICO,NEW YORK,NORTH CAROLINA,NORTH DAKOTA,OHIO,OKLAHOMA,OREGON,PENNSYLVANIA,RHODE ISLAND,SOUTH CAROLINA,SOUTH DAKOTA,TENNESSEE,TEXAS,UTAH,VERMONT,VIRGINIA,WASHINGTON,WEST VIRGINIA,WISCONSIN,WYOMING'.split(",")
x=input().upper()
print(s[s.index(x)%50]if x in s else x)

```

However, if modules are allowed (like the us module), I can get it down to 130 chars:

```
import us
i=raw_input()
x=us.states.lookup(i)
print x.abbr if x else i

```

And if you didn't have to return the original value when the state doesn't exist I could get it down to 50 chars:

```
import us
print us.states.lookup(raw_input()).abbr

```

# Answer
> 0 votes
# Javascript

I know this isn't code golf, but I want to golf it anyway. :)

```
var r=new XMLHttpRequest
r.open("GET","https://gist.githubusercontent.com/mshafrir/2646763/raw/f2a89b57193e71010386a73976df92d32221d7ba/states_hash.json",0)
r.send()
var o=r.responseText,m=prompt(),a=m
o=JSON.parse(o)
for(var i in o)if(o[i].toLowerCase()==m.toLowerCase())a=i
alert(a)
```

Yay for new things! (Stack Snippets)

# Answer
> 0 votes
## Golfscript - 750 653

The bulk is in the state names and abbreviations.

```
{.96>32*-}%.,2>{"ALABAMA,AL,ALASKA,AK,ARIZONA,AZ,ARKANSAS,AR,CALIFORNIA,CA,COLORADO,CO,CONNECTICUT,CT,DELAWARE,DE,FLORIDA,FL,GEORGIA,GA,HAWAII,HI,IDAHO,ID,ILLINOIS,IL,INDIANA,IN,IOWA,IA,KANSAS,KS,KENTUCKY,KY,LOUISIANA,LA,MAINE,ME,MARYLAND,MD,MASSACHUSETTS,MA,MICHIGAN,MI,MINNESOTA,MN,MISSISSIPPI,MS,MISSOURI,MO,MONTANA,MT,NEBRASKA,NE,NEVADA,NV,NEW HAMPSHIRE,NH,NEW JERSEY,NJ,NEW MEXICO,NM,NEW YORK,NY,NORTH CAROLINA,NC,NORTH DAKOTA,ND,OHIO,OH,OKLAHOMA,OK,OREGON,OR,PENNSYLVANIA,PA,RHODE ISLAND,RI,SOUTH CAROLINA,SC,SOUTH DAKOTA,SD,TENNESSEE,TN,TEXAS,TX,UTAH,UT,VERMONT,VT,VIRGINIA,VA,WASHINGTON,WA,WEST VIRGINIA,WV,WISCONSIN,WI,WYOMING,WY"","/.@?)=}{}if

```

Explanation:

```
{        }%                         Map this to every character in the input string:
 .96>32*-                             Subtract 32 from the ASCII value if it's from "a" onwards.
                                      This turns every lowercase letter into an uppercase letter.
           .,2>                     Check if the input length is greater than 2.
               {              }     If it is, they inputted the full name.
                "..."                 Our string is in the form "STATE NAME,STATE ABBREVIATION".
                     ","/             We split the string at every comma to turn it into an array.
                         .@?          Then we see where the input string is in the array...
                            )=        ...then we return the value right next to it.
                               {}   If not, they inputted the abbreviation.
                                      ...do nothing.
                                 if EndIf
                                    (implied) Print the abbreviation

```

# Answer
> 0 votes
## bash + sed, 291 bytes

Shameless conversion of Daniero's Ruby solution to sed:

```
echo $*|tr a-z A-Z|sed -e\
"/\(.\).* \(.\).*/b1;/^\([CDGHKLPV]\).*\(.\)$/b1;/^\(.\).*\([ZVX]\).*/b1;\
/^\([NFOUW]\)\(.\).*/b1;/^\(.\)\([DNR]\).*/b1;/^\(.\).*\([LN]\)[LN].*/b1;\
/^\(.\).*SS\([AO]\).*/b1;/^\(.\).*\([ED])\)$/b1;/^\(.\).*[SNW]\(.\).*/b1;\
/\(.\)\(.\).*/b1;:1 s//\1\2/"

```

# Answer
> 0 votes
# PHP

My attempt, which was not as successful as I had hoped, uses string length and some specific character placement to extract the abbreviation from the state name. Probably some better sequencing of name elimination is possible.

```
function findAbb ($state) {
    $first = substr($state, 0, 1);
    $last = substr($state, -2,1);
    $state = strtolower($state);
    if (strlen($state) < 4) {
        return strtoupper($state);
    }
    if (strpos($state, ' ')) { //if it's a space, return the first letter of each word.
        $space_index = strpos($state, ' ');
        $state = explode(' ', $state);
        return strtoupper(substr($state[0], 0, 1) . substr($state[1], 0, 1));
    }
    if (startsWith($state, 'io')) { //iowa is annoying, get rid of it.
        return strtoupper($first . $last);
    }
    if (startsWith($state, 'w,i')) { //if it starts with a W, return the first 2.
        return strtoupper(substr($state, 0, 2));
    }
    if (strlen($state) < 7 && strpos($state, 'm')===false) { //matches texas, ohio, and utah.
        return strtoupper($first . substr($state, -4,1));
    }
    if (strlen($state) < 7 && substr($state, 0, 1) > 'j' && substr($state, 0, 1) < 'n') { //matches maine, kansas, and hawaii
        return strtoupper($first . $last);
    }
    if (startsWith($state, 'c,d,k,l,p,v,g,h')) { //some unique states
        return strtoupper($first . $last);
    }
    if (strpos($state, 'sk')) {
        return strtoupper ('ak');
    }
    if (startsWith($state, 'k,l', 1)) {
        return strtoupper(substr($state, 0, 2));
    }
    if (startsWith($state, 'n')) {
        return strtoupper($first . substr($state, 2, 1));
    }
    if (startsWith($state, 'n', 2) || startsWith($state, 'z', 3)) { //montana, tennessee, minnesota, and arizona
        return strtoupper($first . substr($state, 3, 1));
    }
    if (startsWith($state, 'm') && ($last == 's') || ($last == 'n')) {
        return strtoupper(substr($state, 0, 2));
    }
    if (strpos($state,'o')) {
        return strtoupper($first . 'o');
    }
    if (strpos($state,'y')) {
        return strtoupper($first . 'd');
    }
    if (strpos($state,'r')) {
        return strtoupper($first . 'r');
    }
    if (strpos($state,'ss')) {
        return strtoupper($first . 's');
    }

    return $state; //otherwise return the name of the state (it was mispelled).
}

function startsWith ($state, $letters, $index = 0) { //takes a comma separated array and finds contents.
    $letters = split(',',$letters);
    for ($q = 0; $q<count($letters); $q++) {
        if (strpos($state,$letters[$q]) === $index) {
            return true;
        }
    }
    return false;
}

```

Of course, it can be golfed. This is my first golfing attempt, so insight appreciated. (911)

```
function t($s){$s=u($s);$f=b($s,0,1);$l=b($s,-2,1);
if(strlen($s)<4)return $s;if(strpos($s,' '))$s=split(' ',$s);
return b($s[0],0,1).b($s[1],0,1);
if(w($s,'IO'))return $f.$l;
if(w($s,'W,I'))return b($s,0,2);
if(strlen($s)<7 && strpos($s,'M')===false)return $f.b($s,-4,1);
if(strlen($s)<7 && b($s,0,1)>'I' && b($s,0,1)<'N')return $f.$l;
if(w($s,'C,D,K,L,P,V,G,H'))return $f.$l;if(strpos($s, 'SK'))return 'AK';
if(w($s,'K,L',1))return b($s,0,2);if(w($s,'N'))return $f.b($s,2,1);
if(w($s,'N',2) || w($s,'Z',3))return $f.b($s,3,1);
if(w($s,'M') && ($l=='S') || ($l=='N'))return b($s,0,2);
if(strpos($s,'O'))return $f.'O';
if(strpos($s,'Y'))return $f.'D';if(strpos($s,'R'))return $f.'R';
if(strpos($s,'SS'))return $f.'S';return $s;}function w($s,$l,$i=0){$l=split(',',$l);
for($q=0;$q<count($l);$q++)if(strpos($s,$l[$q])===$i)return 1;return 0;}
function u($z){return strtoupper($z);}
function b($v,$x,$y){return substr($v,$x,$y);}

```

---
Tags: popularity-contest, string
---


title: Growing Manhattan Ameobas

text:
# Question
Title: Growing Manhattan Ameobas
An \***ameoba graph\**** is a type of tree whose nodes all have values from 0 to some non-negative integer N, and any particular node with value x \< N connects to x+1 *distinct* nodes with values x+1.

# Ameoba graph for N = 3: (Denoted A3)

Note that the 2's are not allowed to share any of the 3's; exactly three 3's must "belong" to each 2.

# Challenge

Your task is to inductively "grow" these ameoba graphs in a 2-dimensional grid by greedily minimizing the Manhattan distance between nodes:

* **Base case:** A0 is simply the graph `0`.
* **Inductive step:** AN+1 is generated by iteratively placing the new N+1 valued nodes as close as possible to the N values nodes in the existing AN structure. (It can only be as close as possible since the closest spots may already be filled.)

For the inductive step the general procedure you must follow is:

```
for each existing node P with value N:
    for each new N+1 valued node Q you need to connect to P: //this loops N+1 times
        find the set of vacant spots that are minimally distant from P //by Manhattan distance
        place Q in any of these vacant spots

```

(A different procedure with indistinguishable output is fine.)

# Growth example for A4:

```
A0 is always the same:

0

For A1 I happen to put the 1 to the right of the 0 (it has to go on one of the 4 open sides):

01

For A2 I happen to put the two 2's above and to the right of the 1:

 2
012

For A3 I find that one of the six 3's I must place cannot be directly next to a 2, so I put in one of the next closest places:

 3
323
0123
  33 <-- this 3 is distance two away from its 2

The process continues in A4. Note that I'm iterating over each 3 and placing four 4's next to it or as close as possible, then moving to the next 3 (the order of 3's does not matter):

 444
443444
4323444
4012344
 44334
  4444
   44

Always keep in mind that nodes cannot be "shared".

```

# Program

The program you write must take in a number from 0 to 8 (inclusive) and output a valid ameoba graph of it, using the inductive growth pattern explained above.

What happens beyond 8 does not matter.

(A8 contains 46234 nodes which is pushing it. Anything beyond A8 would be too far. Thanks to Martin Büttner for noticing this.)

The input should come from stdin or the command line and output should go to stdout or a file.

# Examples (taken directly from above)

```
Input: 0
Output:

0

Input: 1
Output:

01

Input: 2
Output:

 2
012

Input: 3
Output:

 3
323
0123
  33

Input: 4
Output:

 444
443444
4323444
4012344
 44334
  4444
   44

```

** These type of graphs might already have a name. I admit I just made them up. ;)*

# Answer
> 6 votes
## Mathematica, ~~353~~ ~~288~~ ~~285~~ 275 bytes

```
n=Input[];f@_=" ";g={z={0,0}};i=f@z=0;For[r=Range,i++<n,g=Reap[(j=i;o={};For[d=0,j>0,o=Rest@o,If[o=={},o=Join@@({e={#,d-#},-e,e={d-#,-#},-e}&/@r@++d)];If[f[c=#&@@o+#]==" ",f@c=i;Sow@c;--j]])&/@g][[2,1]]];Riffle[(x=#;ToString@f@{x,#}&/@m~r~M)&/@r[m=Min@{g,0},M=Max@g],"
"]<>""

```

Ungolfed:

```
n = Input[];
f@_ = " ";
g = {z = {0, 0}};
i = f@z = 0;
For[r = Range, i++ < n,
  g = Reap[(
        j = i;
        o = {};
        For[d = 0, j > 0, o = Rest@o,
         If[o == {},

          o = Join @@ ({e = {#, d - #}, -e, e = {d - #, -#}, -e} & /@
              r@++d)
          ];
         If[f[c = # & @@ o + #] == " ",
          f@c = i;
          Sow@c;
          --j
          ]
         ]
        ) & /@ g
     ][[2, 1]]
  ];
Riffle[(
     x = #;
     ToString@f@{x, #} & /@ m~r~M
     ) & /@ r[m = Min@{g, 0},
    M = Max@g
    ], "
  "] <> ""

```

Here is an example output for `n = 5`:

```
      5
     5555
    555555
   5555555
  555555555
 55555555555
5555554445555
5555544444555
 5555443305555
 55554432144555
 55555443234555
  5555544344555
   555554445555
    5555555555
      5555555
       55555
       55

```

Input `8` takes about 4.5 minutes.

For a quick breakdown of my algorithm:

I'm using two look-up tables, `f` and `g`. The first one is just a sparse map containing the non-empty cells. The latter is a list containing all coordinate pairs for each cell-value (I think I don't even need to keep track of old ones here). I'm iterating through the coordinates in `g` to extend every cell from the last iteration. To do that I iterate over Manhattan distances, creating all possible vectors for each distance, and checking if the resulting cell is still empty (in which case I fill it). Repeat until enough new cells have been created.

When I'm done, I find the minimum and maximum coordinate in `g` and I create an appropriate grid, which is filled by looking up the cells in `f`. The rest is just joining everything into a single string with line breaks.

# Answer
> 5 votes
# C - 309 305 301 275 bytes

Meh, too long...if only one could type `#D` or something instead of `#define`, then C would be really great. Of course `-D` compiler flags are possible but that seems like cheating to me, to have characters other than the ones in the source file.

## Running instructions:

Be careful! The first key you press after the program starts constitutes the input. Upon a character entry other than '0' through '8', who knows what undefined things will happen.

```
#define F(D,O)x=*r+O d;for(c=d;h*c--;x+=D)!g[x]?g[*w++=x]=l,--h:5;
L=400;g[1<<18];n;s;*r;*w;*m;h;l;d;x;main(c){n=getch()-32;r=w=g+L*L;for(l=g[*w++=80200]=16;l++<n;)for(m=w;r<m;r++)for(d=1,h=l-16;h;d++){F(L+1,-)F(L-1,-L*)F(-L+1,L*)F(~L,)}for(n=L*L;--n;)putch(n%L?g[n]+32:10);}

```

Ungolfed (but already thinking about future golfing) version:

```
void exit(int);

#define L 400

#define FIND(D, X0)   x = *pread X0 d; \
                for(c = d; c--; x+=D) { \
                    if(x%L == 0 || x%L == L-1 || x/L == 0 || x/L == L-1) \
                        exit(5); \
                    if(!g[x]) { \
                        g[*pwrite++ = x] = '0' + l; \
                        if(!--children) \
                            goto pnext; \
                    } \
                }

main()
{
    int n = getch() - '0';
    //char g[3] = {};
    char g[L*L] = {};
    int plist[46324];

    int *pwrite = plist, *pread = plist;
    *pwrite++ = L/2*L + L/2;
    g[*plist] = '0';
    int factorial = 1;
    int l,  c, parents, children, d, x;
    for(l = 1; l <= n; l++) {
        for(parents = factorial; parents--; pread++) {
            children = l;
            for(d = 1; ; d++) {
                FIND(L + 1, - )
                FIND(L - 1, -L* )
                FIND(-L + 1, +L* )
                FIND(-L - 1, + )
            }
            pnext:;
        }
        factorial *= l;
    }
    int i;
    for(i = L*L; i--; )
        putch(i%L ? (g[i] ? g[i] : ' ') : '\n');
}

```

Edit: I realized that since I moved the declarations outside of main(), the arrays can no longer be allocated on the stack, so I am free to use memory in a profligate manner without risk of overflow.

# Answer
> 2 votes
## Ruby - 296

```
g=[s=' ']*d=10**6
$*[g[50500]=0].to_i.times{|c|d.times{|x|g[x]==c&&(r=1;a=c;(4.times{|v|r.times{|w|g[q=x+r*(1e3*(v-1-v/2)+v%2-v/2)+w*(1e3*~0**(v/2)+~0**v)]==s&&a>~0?(g[q]=c+1;a-=1):0}};r+=1)while~0<a)}}
g=g.join.scan(/.{1000}/)
g.map{|s|s[/\d/]&&(puts s[g.map{|s|s[/\A */].size}.min..-1].rstrip)}

```

Slightly ungolfed.

```
g=[s=' ']*d=10**6 # Initialize a big 1d array as a 2d grid
$*[g[50500]=0].to_i.times{|c| # For n times
    d.times{|x| # For each index in the grid
        g[x]==c&&( # If the element at x is equal to the current growth stage, c
            r=1;   # Initial manhattan radius = 1
            a=c;   # a is number of times the ameoba must replicate
            (4.times{|v| # For each of the 4 sides of the manhattan diamond
                r.times{|w| # For each node in each side
                    # Spawn the 'c+1' ameoba's from the c ameobas...
                    # The messy formula gives the index of the space in the grid to try spawning
                    g[q=x+r*(1e3*(v-1-v/2)+v%2-v/2)+w*(1e3*~0**(v/2)+~0**v)]==s&&a>~0?(g[q]=c+1;a-=1):0
                }
            };
            r+=1 # Increase the raidus of the manhattan diamond by one
            ) while~0<a # while not enough ameoba's have been spawned
        )
    }
}
g=g.join.scan(/.{1000}/) # Join the 1d array into a huge string and slice it into rows
# Strip away the empty spaces all around the graph and print it
g.map{|s|s[/\d/]&&(puts s[g.map{|s|s[/\A */].size}.min..-1].rstrip)}

```

# Answer
> 2 votes
## APL (Dyalog) (121)

```
{0::0⋄V←,⍳⍴Z←' '⍴⍨2/M←⌈4×.5*⍨3÷⍨+/!⍳⍵⋄Z[G;G←⌈M÷2]←'0'⋄Z⊣{⍵∘{⍵∘{+((⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺])⌷Z)←⍕⍵}¨⍺/⍺}¨V/⍨,Z=⍕⍵-1}¨⍳⍵}⎕

```

Performance characteristics: it's O(n!). On my system, up to n=5 it's instantaneous; n=6 takes a second, n=7 takes a minute and n=8 takes an hour.

Non-golfed version

Test:

```
      {0::0⋄V←,⍳⍴Z←' '⍴⍨2/M←⌈4×.5*⍨3÷⍨+/!⍳⍵⋄Z[G;G←⌈M÷2]←'0'⋄Z⊣{⍵∘{⍵∘{+((⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺])⌷Z)←⍕⍵}¨⍺/⍺}¨V/⍨,Z=⍕⍵-1}¨⍳⍵}⎕
⎕:
      5

           5555
          555555
         55555555
        5555445555
       555544445555
      55554433445555
     5555444323445555
    5555544321455555
     555554430455555
     555555444555555
       555555555555
        5555555555
         55555555
          55555
           555

```

Explanation:

* `{`...`}⎕`: read a line from the keyboard, evaluate it, and pass the result to the function.
* `0::0`: if the other code raises an error, return a single `0`. This is because the math fails when trying to calculate the size for a graph with 0 nodes, which happens to be the case when the output should be `0`. (The previous version had `⍵=0:0`, (if the input is `0` return `0` otherwise make the graph), but `0::0` (just try it and return `0` if it fails) is shorter.)
* `M←⌈4×.5*⍨3÷⍨+/!⍳⍵`: assuming the output is a rough circle (this works), sum the factorials from `1` to  (= area of output), divide by 3 (close enough to pi), take the square root (giving radius of output), multiply by 4, and take the ceiling. This gives twice the diameter of the circle, so the output fits with room to spare. Store this in `M`.
* `V←,⍳⍴Z←' '⍴⍨2/M`: make an M-by-M matrix of spaces and store it in `Z`. This will hold the output. Store a list of the coordinates of all elements in `V`.
* `Z[G;G←⌈M÷2]←'0'`: set the middle element of `Z` to `0`.
* `Z⊢{`...`}¨⍳⍵`: return `Z`, after applying the following function to the numbers `1` to :
    + `⍵∘{`...`}V/,Z=⍕⍵-1`: for each element in `Z` with the value of the previous node:
        - `⍵∘{`...`}⍺/⍺`: for the current node, N times,
            * `⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]`: get the free space closest to the current node,
            * `(`...`⌷Z)←⍕⍵`: and set that space in `Z` to the value of the current node.

---
Tags: code-golf, graph-theory
---


title: Implement division using only addition

text:
# Question
Title: Implement division using only addition
There is a question on the site that asks to implement division without using division.

In my case, I am asking you to do the same, but only using addition.

What this means is basically: addition is the only operator or function allowed that operates on numbers and returns other numbers (i.e. no subtraction, multiplication, exponentiation, bitwise inversion, etc.). Stuff like if statements, assignment and comparison operators, and for loops are still allowed, provided that within those, you still only use addition.

Your task is to build a function `divide(a, b)` that takes two positive integers `a` and `b` and returns the result of `a` being divided by `b` and rounded toward zero, but using addition and no other arithmetical operators, and no other data constructs besides numbers.

The code that wins will be the one that requires the fewest addition operations to be performed over the set of inputs where `a` varies from `1` to `200` and `b` varies from `1` to `a`.

To keep track of this, you can build an alternate version of your code that replaces every instance of `a + b` with `add(a, b)` and program `add` to increment a global `add_used` variable as well as returning the sum of the two numbers.

# Answer
Writing rules is hard, these rules in particular contain incentive to avoid additions at all costs.

Is there a prize for the most ridiculous answer?

### JavaScript - 0 additions

Now with fallback method that does a hulking solution for larger `a`'s and `b`'s, and a slightly more compact structure in order not to bust the character limit. (Pfff, 30000 characters. What is this? Twitter?) Still no additions in the measured scope.

```
function divide(a,b){
    if(a<b){
        return 0
    }
    if(b==1){
        return a
    }
    if(b==2){
        if(a<4){return 1}
        if(a<6){return 2}
        if(a<8){return 3}
        if(a<10){return 4}
        if(a<12){return 5}
        if(a<14){return 6}
        if(a<16){return 7}
        if(a<18){return 8}
        if(a<20){return 9}
        if(a<22){return 10}
        if(a<24){return 11}
        if(a<26){return 12}
        if(a<28){return 13}
        if(a<30){return 14}
        if(a<32){return 15}
        if(a<34){return 16}
        if(a<36){return 17}
        if(a<38){return 18}
        if(a<40){return 19}
        if(a<42){return 20}
        if(a<44){return 21}
        if(a<46){return 22}
        if(a<48){return 23}
        if(a<50){return 24}
        if(a<52){return 25}
        if(a<54){return 26}
        if(a<56){return 27}
        if(a<58){return 28}
        if(a<60){return 29}
        if(a<62){return 30}
        if(a<64){return 31}
        if(a<66){return 32}
        if(a<68){return 33}
        if(a<70){return 34}
        if(a<72){return 35}
        if(a<74){return 36}
        if(a<76){return 37}
        if(a<78){return 38}
        if(a<80){return 39}
        if(a<82){return 40}
        if(a<84){return 41}
        if(a<86){return 42}
        if(a<88){return 43}
        if(a<90){return 44}
        if(a<92){return 45}
        if(a<94){return 46}
        if(a<96){return 47}
        if(a<98){return 48}
        if(a<100){return 49}
        if(a<102){return 50}
        if(a<104){return 51}
        if(a<106){return 52}
        if(a<108){return 53}
        if(a<110){return 54}
        if(a<112){return 55}
        if(a<114){return 56}
        if(a<116){return 57}
        if(a<118){return 58}
        if(a<120){return 59}
        if(a<122){return 60}
        if(a<124){return 61}
        if(a<126){return 62}
        if(a<128){return 63}
        if(a<130){return 64}
        if(a<132){return 65}
        if(a<134){return 66}
        if(a<136){return 67}
        if(a<138){return 68}
        if(a<140){return 69}
        if(a<142){return 70}
        if(a<144){return 71}
        if(a<146){return 72}
        if(a<148){return 73}
        if(a<150){return 74}
        if(a<152){return 75}
        if(a<154){return 76}
        if(a<156){return 77}
        if(a<158){return 78}
        if(a<160){return 79}
        if(a<162){return 80}
        if(a<164){return 81}
        if(a<166){return 82}
        if(a<168){return 83}
        if(a<170){return 84}
        if(a<172){return 85}
        if(a<174){return 86}
        if(a<176){return 87}
        if(a<178){return 88}
        if(a<180){return 89}
        if(a<182){return 90}
        if(a<184){return 91}
        if(a<186){return 92}
        if(a<188){return 93}
        if(a<190){return 94}
        if(a<192){return 95}
        if(a<194){return 96}
        if(a<196){return 97}
        if(a<198){return 98}
        if(a<200){return 99}
        if(a<202){return 100}
    }
    if(b==3){
        if(a<6){return 1}
        if(a<9){return 2}
        if(a<12){return 3}
        if(a<15){return 4}
        if(a<18){return 5}
        if(a<21){return 6}
        if(a<24){return 7}
        if(a<27){return 8}
        if(a<30){return 9}
        if(a<33){return 10}
        if(a<36){return 11}
        if(a<39){return 12}
        if(a<42){return 13}
        if(a<45){return 14}
        if(a<48){return 15}
        if(a<51){return 16}
        if(a<54){return 17}
        if(a<57){return 18}
        if(a<60){return 19}
        if(a<63){return 20}
        if(a<66){return 21}
        if(a<69){return 22}
        if(a<72){return 23}
        if(a<75){return 24}
        if(a<78){return 25}
        if(a<81){return 26}
        if(a<84){return 27}
        if(a<87){return 28}
        if(a<90){return 29}
        if(a<93){return 30}
        if(a<96){return 31}
        if(a<99){return 32}
        if(a<102){return 33}
        if(a<105){return 34}
        if(a<108){return 35}
        if(a<111){return 36}
        if(a<114){return 37}
        if(a<117){return 38}
        if(a<120){return 39}
        if(a<123){return 40}
        if(a<126){return 41}
        if(a<129){return 42}
        if(a<132){return 43}
        if(a<135){return 44}
        if(a<138){return 45}
        if(a<141){return 46}
        if(a<144){return 47}
        if(a<147){return 48}
        if(a<150){return 49}
        if(a<153){return 50}
        if(a<156){return 51}
        if(a<159){return 52}
        if(a<162){return 53}
        if(a<165){return 54}
        if(a<168){return 55}
        if(a<171){return 56}
        if(a<174){return 57}
        if(a<177){return 58}
        if(a<180){return 59}
        if(a<183){return 60}
        if(a<186){return 61}
        if(a<189){return 62}
        if(a<192){return 63}
        if(a<195){return 64}
        if(a<198){return 65}
        if(a<201){return 66}
    }
    if(b==4){
        if(a<8){return 1}
        if(a<12){return 2}
        if(a<16){return 3}
        if(a<20){return 4}
        if(a<24){return 5}
        if(a<28){return 6}
        if(a<32){return 7}
        if(a<36){return 8}
        if(a<40){return 9}
        if(a<44){return 10}
        if(a<48){return 11}
        if(a<52){return 12}
        if(a<56){return 13}
        if(a<60){return 14}
        if(a<64){return 15}
        if(a<68){return 16}
        if(a<72){return 17}
        if(a<76){return 18}
        if(a<80){return 19}
        if(a<84){return 20}
        if(a<88){return 21}
        if(a<92){return 22}
        if(a<96){return 23}
        if(a<100){return 24}
        if(a<104){return 25}
        if(a<108){return 26}
        if(a<112){return 27}
        if(a<116){return 28}
        if(a<120){return 29}
        if(a<124){return 30}
        if(a<128){return 31}
        if(a<132){return 32}
        if(a<136){return 33}
        if(a<140){return 34}
        if(a<144){return 35}
        if(a<148){return 36}
        if(a<152){return 37}
        if(a<156){return 38}
        if(a<160){return 39}
        if(a<164){return 40}
        if(a<168){return 41}
        if(a<172){return 42}
        if(a<176){return 43}
        if(a<180){return 44}
        if(a<184){return 45}
        if(a<188){return 46}
        if(a<192){return 47}
        if(a<196){return 48}
        if(a<200){return 49}
        if(a<204){return 50}
    }
    if(b==5){
        if(a<10){return 1}
        if(a<15){return 2}
        if(a<20){return 3}
        if(a<25){return 4}
        if(a<30){return 5}
        if(a<35){return 6}
        if(a<40){return 7}
        if(a<45){return 8}
        if(a<50){return 9}
        if(a<55){return 10}
        if(a<60){return 11}
        if(a<65){return 12}
        if(a<70){return 13}
        if(a<75){return 14}
        if(a<80){return 15}
        if(a<85){return 16}
        if(a<90){return 17}
        if(a<95){return 18}
        if(a<100){return 19}
        if(a<105){return 20}
        if(a<110){return 21}
        if(a<115){return 22}
        if(a<120){return 23}
        if(a<125){return 24}
        if(a<130){return 25}
        if(a<135){return 26}
        if(a<140){return 27}
        if(a<145){return 28}
        if(a<150){return 29}
        if(a<155){return 30}
        if(a<160){return 31}
        if(a<165){return 32}
        if(a<170){return 33}
        if(a<175){return 34}
        if(a<180){return 35}
        if(a<185){return 36}
        if(a<190){return 37}
        if(a<195){return 38}
        if(a<200){return 39}
        if(a<205){return 40}
    }
    if(b==6){
        if(a<12){return 1}
        if(a<18){return 2}
        if(a<24){return 3}
        if(a<30){return 4}
        if(a<36){return 5}
        if(a<42){return 6}
        if(a<48){return 7}
        if(a<54){return 8}
        if(a<60){return 9}
        if(a<66){return 10}
        if(a<72){return 11}
        if(a<78){return 12}
        if(a<84){return 13}
        if(a<90){return 14}
        if(a<96){return 15}
        if(a<102){return 16}
        if(a<108){return 17}
        if(a<114){return 18}
        if(a<120){return 19}
        if(a<126){return 20}
        if(a<132){return 21}
        if(a<138){return 22}
        if(a<144){return 23}
        if(a<150){return 24}
        if(a<156){return 25}
        if(a<162){return 26}
        if(a<168){return 27}
        if(a<174){return 28}
        if(a<180){return 29}
        if(a<186){return 30}
        if(a<192){return 31}
        if(a<198){return 32}
        if(a<204){return 33}
    }
    if(b==7){
        if(a<14){return 1}
        if(a<21){return 2}
        if(a<28){return 3}
        if(a<35){return 4}
        if(a<42){return 5}
        if(a<49){return 6}
        if(a<56){return 7}
        if(a<63){return 8}
        if(a<70){return 9}
        if(a<77){return 10}
        if(a<84){return 11}
        if(a<91){return 12}
        if(a<98){return 13}
        if(a<105){return 14}
        if(a<112){return 15}
        if(a<119){return 16}
        if(a<126){return 17}
        if(a<133){return 18}
        if(a<140){return 19}
        if(a<147){return 20}
        if(a<154){return 21}
        if(a<161){return 22}
        if(a<168){return 23}
        if(a<175){return 24}
        if(a<182){return 25}
        if(a<189){return 26}
        if(a<196){return 27}
        if(a<203){return 28}
    }
    if(b==8){
        if(a<16){return 1}
        if(a<24){return 2}
        if(a<32){return 3}
        if(a<40){return 4}
        if(a<48){return 5}
        if(a<56){return 6}
        if(a<64){return 7}
        if(a<72){return 8}
        if(a<80){return 9}
        if(a<88){return 10}
        if(a<96){return 11}
        if(a<104){return 12}
        if(a<112){return 13}
        if(a<120){return 14}
        if(a<128){return 15}
        if(a<136){return 16}
        if(a<144){return 17}
        if(a<152){return 18}
        if(a<160){return 19}
        if(a<168){return 20}
        if(a<176){return 21}
        if(a<184){return 22}
        if(a<192){return 23}
        if(a<200){return 24}
        if(a<208){return 25}
    }
    if(b==9){
        if(a<18){return 1}
        if(a<27){return 2}
        if(a<36){return 3}
        if(a<45){return 4}
        if(a<54){return 5}
        if(a<63){return 6}
        if(a<72){return 7}
        if(a<81){return 8}
        if(a<90){return 9}
        if(a<99){return 10}
        if(a<108){return 11}
        if(a<117){return 12}
        if(a<126){return 13}
        if(a<135){return 14}
        if(a<144){return 15}
        if(a<153){return 16}
        if(a<162){return 17}
        if(a<171){return 18}
        if(a<180){return 19}
        if(a<189){return 20}
        if(a<198){return 21}
        if(a<207){return 22}
    }
    if(b==10){
        if(a<20){return 1}
        if(a<30){return 2}
        if(a<40){return 3}
        if(a<50){return 4}
        if(a<60){return 5}
        if(a<70){return 6}
        if(a<80){return 7}
        if(a<90){return 8}
        if(a<100){return 9}
        if(a<110){return 10}
        if(a<120){return 11}
        if(a<130){return 12}
        if(a<140){return 13}
        if(a<150){return 14}
        if(a<160){return 15}
        if(a<170){return 16}
        if(a<180){return 17}
        if(a<190){return 18}
        if(a<200){return 19}
        if(a<210){return 20}
    }
    if(b==11){
        if(a<22){return 1}
        if(a<33){return 2}
        if(a<44){return 3}
        if(a<55){return 4}
        if(a<66){return 5}
        if(a<77){return 6}
        if(a<88){return 7}
        if(a<99){return 8}
        if(a<110){return 9}
        if(a<121){return 10}
        if(a<132){return 11}
        if(a<143){return 12}
        if(a<154){return 13}
        if(a<165){return 14}
        if(a<176){return 15}
        if(a<187){return 16}
        if(a<198){return 17}
        if(a<209){return 18}
    }
    if(b==12){
        if(a<24){return 1}
        if(a<36){return 2}
        if(a<48){return 3}
        if(a<60){return 4}
        if(a<72){return 5}
        if(a<84){return 6}
        if(a<96){return 7}
        if(a<108){return 8}
        if(a<120){return 9}
        if(a<132){return 10}
        if(a<144){return 11}
        if(a<156){return 12}
        if(a<168){return 13}
        if(a<180){return 14}
        if(a<192){return 15}
        if(a<204){return 16}
    }
    if(b==13){
        if(a<26){return 1}
        if(a<39){return 2}
        if(a<52){return 3}
        if(a<65){return 4}
        if(a<78){return 5}
        if(a<91){return 6}
        if(a<104){return 7}
        if(a<117){return 8}
        if(a<130){return 9}
        if(a<143){return 10}
        if(a<156){return 11}
        if(a<169){return 12}
        if(a<182){return 13}
        if(a<195){return 14}
        if(a<208){return 15}
    }
    if(b==14){
        if(a<28){return 1}
        if(a<42){return 2}
        if(a<56){return 3}
        if(a<70){return 4}
        if(a<84){return 5}
        if(a<98){return 6}
        if(a<112){return 7}
        if(a<126){return 8}
        if(a<140){return 9}
        if(a<154){return 10}
        if(a<168){return 11}
        if(a<182){return 12}
        if(a<196){return 13}
        if(a<210){return 14}
    }
    if(b==15){
        if(a<30){return 1}
        if(a<45){return 2}
        if(a<60){return 3}
        if(a<75){return 4}
        if(a<90){return 5}
        if(a<105){return 6}
        if(a<120){return 7}
        if(a<135){return 8}
        if(a<150){return 9}
        if(a<165){return 10}
        if(a<180){return 11}
        if(a<195){return 12}
        if(a<210){return 13}
    }
    if(b==16){
        if(a<32){return 1}
        if(a<48){return 2}
        if(a<64){return 3}
        if(a<80){return 4}
        if(a<96){return 5}
        if(a<112){return 6}
        if(a<128){return 7}
        if(a<144){return 8}
        if(a<160){return 9}
        if(a<176){return 10}
        if(a<192){return 11}
        if(a<208){return 12}
    }
    if(b==17){
        if(a<34){return 1}
        if(a<51){return 2}
        if(a<68){return 3}
        if(a<85){return 4}
        if(a<102){return 5}
        if(a<119){return 6}
        if(a<136){return 7}
        if(a<153){return 8}
        if(a<170){return 9}
        if(a<187){return 10}
        if(a<204){return 11}
    }
    if(b==18){
        if(a<36){return 1}
        if(a<54){return 2}
        if(a<72){return 3}
        if(a<90){return 4}
        if(a<108){return 5}
        if(a<126){return 6}
        if(a<144){return 7}
        if(a<162){return 8}
        if(a<180){return 9}
        if(a<198){return 10}
        if(a<216){return 11}
    }
    if(b==19){
        if(a<38){return 1}
        if(a<57){return 2}
        if(a<76){return 3}
        if(a<95){return 4}
        if(a<114){return 5}
        if(a<133){return 6}
        if(a<152){return 7}
        if(a<171){return 8}
        if(a<190){return 9}
        if(a<209){return 10}
    }
    if(b==20){
        if(a<40){return 1}
        if(a<60){return 2}
        if(a<80){return 3}
        if(a<100){return 4}
        if(a<120){return 5}
        if(a<140){return 6}
        if(a<160){return 7}
        if(a<180){return 8}
        if(a<200){return 9}
        if(a<220){return 10}
    }
    if(b==21){
        if(a<42){return 1}
        if(a<63){return 2}
        if(a<84){return 3}
        if(a<105){return 4}
        if(a<126){return 5}
        if(a<147){return 6}
        if(a<168){return 7}
        if(a<189){return 8}
        if(a<210){return 9}
    }
    if(b==22){
        if(a<44){return 1}
        if(a<66){return 2}
        if(a<88){return 3}
        if(a<110){return 4}
        if(a<132){return 5}
        if(a<154){return 6}
        if(a<176){return 7}
        if(a<198){return 8}
        if(a<220){return 9}
    }
    if(b==23){
        if(a<46){return 1}
        if(a<69){return 2}
        if(a<92){return 3}
        if(a<115){return 4}
        if(a<138){return 5}
        if(a<161){return 6}
        if(a<184){return 7}
        if(a<207){return 8}
    }
    if(b==24){
        if(a<48){return 1}
        if(a<72){return 2}
        if(a<96){return 3}
        if(a<120){return 4}
        if(a<144){return 5}
        if(a<168){return 6}
        if(a<192){return 7}
        if(a<216){return 8}
    }
    if(b==25){
        if(a<50){return 1}
        if(a<75){return 2}
        if(a<100){return 3}
        if(a<125){return 4}
        if(a<150){return 5}
        if(a<175){return 6}
        if(a<200){return 7}
        if(a<225){return 8}
    }
    if(b==26){
        if(a<52){return 1}
        if(a<78){return 2}
        if(a<104){return 3}
        if(a<130){return 4}
        if(a<156){return 5}
        if(a<182){return 6}
        if(a<208){return 7}
    }
    if(b==27){
        if(a<54){return 1}
        if(a<81){return 2}
        if(a<108){return 3}
        if(a<135){return 4}
        if(a<162){return 5}
        if(a<189){return 6}
        if(a<216){return 7}
    }
    if(b==28){
        if(a<56){return 1}
        if(a<84){return 2}
        if(a<112){return 3}
        if(a<140){return 4}
        if(a<168){return 5}
        if(a<196){return 6}
        if(a<224){return 7}
    }
    if(b==29){
        if(a<58){return 1}
        if(a<87){return 2}
        if(a<116){return 3}
        if(a<145){return 4}
        if(a<174){return 5}
        if(a<203){return 6}
    }
    if(b==30){
        if(a<60){return 1}
        if(a<90){return 2}
        if(a<120){return 3}
        if(a<150){return 4}
        if(a<180){return 5}
        if(a<210){return 6}
    }
    if(b==31){
        if(a<62){return 1}
        if(a<93){return 2}
        if(a<124){return 3}
        if(a<155){return 4}
        if(a<186){return 5}
        if(a<217){return 6}
    }
    if(b==32){
        if(a<64){return 1}
        if(a<96){return 2}
        if(a<128){return 3}
        if(a<160){return 4}
        if(a<192){return 5}
        if(a<224){return 6}
    }
    if(b==33){
        if(a<66){return 1}
        if(a<99){return 2}
        if(a<132){return 3}
        if(a<165){return 4}
        if(a<198){return 5}
        if(a<231){return 6}
    }
    if(b==34){
        if(a<68){return 1}
        if(a<102){return 2}
        if(a<136){return 3}
        if(a<170){return 4}
        if(a<204){return 5}
    }
    if(b==35){
        if(a<70){return 1}
        if(a<105){return 2}
        if(a<140){return 3}
        if(a<175){return 4}
        if(a<210){return 5}
    }
    if(b==36){
        if(a<72){return 1}
        if(a<108){return 2}
        if(a<144){return 3}
        if(a<180){return 4}
        if(a<216){return 5}
    }
    if(b==37){
        if(a<74){return 1}
        if(a<111){return 2}
        if(a<148){return 3}
        if(a<185){return 4}
        if(a<222){return 5}
    }
    if(b==38){
        if(a<76){return 1}
        if(a<114){return 2}
        if(a<152){return 3}
        if(a<190){return 4}
        if(a<228){return 5}
    }
    if(b==39){
        if(a<78){return 1}
        if(a<117){return 2}
        if(a<156){return 3}
        if(a<195){return 4}
        if(a<234){return 5}
    }
    if(b==40){
        if(a<80){return 1}
        if(a<120){return 2}
        if(a<160){return 3}
        if(a<200){return 4}
        if(a<240){return 5}
    }
    if(b==41){
        if(a<82){return 1}
        if(a<123){return 2}
        if(a<164){return 3}
        if(a<205){return 4}
    }
    if(b==42){
        if(a<84){return 1}
        if(a<126){return 2}
        if(a<168){return 3}
        if(a<210){return 4}
    }
    if(b==43){
        if(a<86){return 1}
        if(a<129){return 2}
        if(a<172){return 3}
        if(a<215){return 4}
    }
    if(b==44){
        if(a<88){return 1}
        if(a<132){return 2}
        if(a<176){return 3}
        if(a<220){return 4}
    }
    if(b==45){
        if(a<90){return 1}
        if(a<135){return 2}
        if(a<180){return 3}
        if(a<225){return 4}
    }
    if(b==46){
        if(a<92){return 1}
        if(a<138){return 2}
        if(a<184){return 3}
        if(a<230){return 4}
    }
    if(b==47){
        if(a<94){return 1}
        if(a<141){return 2}
        if(a<188){return 3}
        if(a<235){return 4}
    }
    if(b==48){
        if(a<96){return 1}
        if(a<144){return 2}
        if(a<192){return 3}
        if(a<240){return 4}
    }
    if(b==49){
        if(a<98){return 1}
        if(a<147){return 2}
        if(a<196){return 3}
        if(a<245){return 4}
    }
    if(b==50){
        if(a<100){return 1}
        if(a<150){return 2}
        if(a<200){return 3}
        if(a<250){return 4}
    }
    if(b==51){
        if(a<102){return 1}
        if(a<153){return 2}
        if(a<204){return 3}
    }
    if(b==52){
        if(a<104){return 1}
        if(a<156){return 2}
        if(a<208){return 3}
    }
    if(b==53){
        if(a<106){return 1}
        if(a<159){return 2}
        if(a<212){return 3}
    }
    if(b==54){
        if(a<108){return 1}
        if(a<162){return 2}
        if(a<216){return 3}
    }
    if(b==55){
        if(a<110){return 1}
        if(a<165){return 2}
        if(a<220){return 3}
    }
    if(b==56){
        if(a<112){return 1}
        if(a<168){return 2}
        if(a<224){return 3}
    }
    if(b==57){
        if(a<114){return 1}
        if(a<171){return 2}
        if(a<228){return 3}
    }
    if(b==58){
        if(a<116){return 1}
        if(a<174){return 2}
        if(a<232){return 3}
    }
    if(b==59){
        if(a<118){return 1}
        if(a<177){return 2}
        if(a<236){return 3}
    }
    if(b==60){
        if(a<120){return 1}
        if(a<180){return 2}
        if(a<240){return 3}
    }
    if(b==61){
        if(a<122){return 1}
        if(a<183){return 2}
        if(a<244){return 3}
    }
    if(b==62){
        if(a<124){return 1}
        if(a<186){return 2}
        if(a<248){return 3}
    }
    if(b==63){
        if(a<126){return 1}
        if(a<189){return 2}
        if(a<252){return 3}
    }
    if(b==64){
        if(a<128){return 1}
        if(a<192){return 2}
        if(a<256){return 3}
    }
    if(b==65){
        if(a<130){return 1}
        if(a<195){return 2}
        if(a<260){return 3}
    }
    if(b==66){
        if(a<132){return 1}
        if(a<198){return 2}
        if(a<264){return 3}
    }
    if(b==67){
        if(a<134){return 1}
        if(a<201){return 2}
    }
    if(b==68){
        if(a<136){return 1}
        if(a<204){return 2}
    }
    if(b==69){
        if(a<138){return 1}
        if(a<207){return 2}
    }
    if(b==70){
        if(a<140){return 1}
        if(a<210){return 2}
    }
    if(b==71){
        if(a<142){return 1}
        if(a<213){return 2}
    }
    if(b==72){
        if(a<144){return 1}
        if(a<216){return 2}
    }
    if(b==73){
        if(a<146){return 1}
        if(a<219){return 2}
    }
    if(b==74){
        if(a<148){return 1}
        if(a<222){return 2}
    }
    if(b==75){
        if(a<150){return 1}
        if(a<225){return 2}
    }
    if(b==76){
        if(a<152){return 1}
        if(a<228){return 2}
    }
    if(b==77){
        if(a<154){return 1}
        if(a<231){return 2}
    }
    if(b==78){
        if(a<156){return 1}
        if(a<234){return 2}
    }
    if(b==79){
        if(a<158){return 1}
        if(a<237){return 2}
    }
    if(b==80){
        if(a<160){return 1}
        if(a<240){return 2}
    }
    if(b==81){
        if(a<162){return 1}
        if(a<243){return 2}
    }
    if(b==82){
        if(a<164){return 1}
        if(a<246){return 2}
    }
    if(b==83){
        if(a<166){return 1}
        if(a<249){return 2}
    }
    if(b==84){
        if(a<168){return 1}
        if(a<252){return 2}
    }
    if(b==85){
        if(a<170){return 1}
        if(a<255){return 2}
    }
    if(b==86){
        if(a<172){return 1}
        if(a<258){return 2}
    }
    if(b==87){
        if(a<174){return 1}
        if(a<261){return 2}
    }
    if(b==88){
        if(a<176){return 1}
        if(a<264){return 2}
    }
    if(b==89){
        if(a<178){return 1}
        if(a<267){return 2}
    }
    if(b==90){
        if(a<180){return 1}
        if(a<270){return 2}
    }
    if(b==91){
        if(a<182){return 1}
        if(a<273){return 2}
    }
    if(b==92){
        if(a<184){return 1}
        if(a<276){return 2}
    }
    if(b==93){
        if(a<186){return 1}
        if(a<279){return 2}
    }
    if(b==94){
        if(a<188){return 1}
        if(a<282){return 2}
    }
    if(b==95){
        if(a<190){return 1}
        if(a<285){return 2}
    }
    if(b==96){
        if(a<192){return 1}
        if(a<288){return 2}
    }
    if(b==97){
        if(a<194){return 1}
        if(a<291){return 2}
    }
    if(b==98){
        if(a<196){return 1}
        if(a<294){return 2}
    }
    if(b==99){
        if(a<198){return 1}
        if(a<297){return 2}
    }
    if(b==100){
        if(a<200){return 1}
        if(a<300){return 2}
    }
    if(b<=200 && a<=200){
        return 1
    }
    var result=0
    var counter=b
    for(;a>=counter;counter=add(counter,b)){
        result=add(result,1)
    }
    return result
}

```
> 17 votes

# Answer
# Tcl, 0 additions

```
proc divide {a b} {
    set sa [string repeat . $a]
    set sb [string repeat . $b]
    set sr ""
    while 1 {
        append sc $sb
        if {[string le $sc]>[string le $sa]} break
        append sr .
    }
    return [string le $sr]
}

```

Why not use strings?
> 6 votes

# Answer
## Haskell 0 additions, 29 bytes

```
n/m=[i|i<-[0..],_<-[1..m]]!!n

```

this redefines the division operator (`/`). it works by making a list of `0` to infinity where each item is repeated `m` times, and then choosing the nth element of the list (using a 0-based index).
> 3 votes

# Answer
Use this implementation in java, 199206 additions

```
public int divide(int a, int b){
    int counter = 0;
    int c = 0;
    if(b==1){
        return a;
    }
    if(a==b){
        return 1;
    }
    else{
        boolean done = false;
        while(!done){
            c = add(c, b);
            if(a<c){
                done = true;
            }
            counter = add(counter,1);
        }
        return counter;

    }
}

```

Following are the helper functions

```
public static void main(String[] args) {
    Main main = new Main();

    for(int a = 1; a<=200; a++){
        for(int b=1;b<=a;b++){
            main.divide(a, b);
        }
    }

    System.out.println("Number of additions: "+numberOfAdds);
}

public int add(int a, int b){
    numberOfAdds++;
    return (a+b);
}

```
> 2 votes

# Answer
## Python - 0 additions

```
from itertools import repeat, count

def divide(a, b):
    i = repeat(0, a)
    try:
        for j in count():
            for k in repeat(0, b):
                next(i)
    except:
        return j

```

This uses an iterator of length `a`, and consumes it in groups of `b` until `StopIteration` is raised. At this point `j` contains the result.
> 2 votes

# Answer
My solution is C/C++ code and it makes many additions (200402), but anyway...

```
#include <iostream>

int total = 0;

int sum(int a, int b)
{
    ++total;
    return a + b;
}

int divide(int a, int b)
{
    int x = 1;
    if (a < b)
        return 0;
    else
        return sum(x, divide(sum(a, -b), b));
}

int main()
{
    for (int i = 1; i <= 200; ++i)
        for (int j = 1; j <= 200; ++j)
        {
            if (divide(i, j) != (i / j))
                std::cout << "Failure: a=" << i << " b=" << j << "\n";
        }

    std::cout << "Total additions: " << total << std::endl;
    system("pause");
}

```

And the output is:

```
Total additions: 200402
Press any key to continue . . .

```
> 2 votes

# Answer
# Python, 320703 additions

```
def divide(a, b):
    quotient = 0
    c = 0
    d = 0
    while add(d, b) <= a:
        c = add(c, 1)
        d = add(d, b)
    return c

```

As always, a last-place reference answer. This simply adds `1` to a "quotient" and `b` to a "remultiplication" variable until it hits `a`.

Here is the debugging code:

```
add_used = 0

def add(a, b):
    global add_used
    add_used += 1
    return a + b

for a in range(1, 201):
    for b in range(1, a+1):
        print "%d / %d = %d" % (a, b, divide(a, b))

print "Additions used:", add_used

```
> 1 votes

# Answer
# Tcl, 0 additions.

Well, I had to find a way that does not use other data structures but is still not what you want:

```
# coroutine counter.
proc ccnt {} {yield [info level]; ccnt}
# add implementation without add.
proc cadd {a b} {
    set last 2
    coroutine cadda ccnt
    coroutine caddb ccnt
    while {[cadda]<=$a} {}
    while {[caddb]<=$b} {set last [cadda]}
    rename cadda {}
    rename caddb {}
    return $last
}

proc divide {a b {c 0}} {
    if {$c == 0} {set c $b} {set c [cadd $b $c]}
    if {$c>$a} {tailcall info level}
    divide $a $b $c
}

```

Uses the current stack size of different green threads.
> 1 votes

# Answer
# Mathematica 100201 additions

This adds the divisor, `b`, to `c` (which is initialized at 0) as long as the running total is less than or equal to the dividend, `a`. It also appends the current value of `c` to a list, `t`, without performing any arithmetic operation.

When the `While` loop terminates the function outputs the length of `t`, which will correspond exactly to the quotient of integer division. Thus the number of additions for any given `divide[a,b]` will equal precisely the quotient.

100201 is the sum of the quotients in the 200 by 200 table. That's how many times `c` was incremented by `b`. No other additions were required. Only positive integers were used.

```
divide[a_, b_] := Module[{c = 0, t = {}}, While[c <= a, t = Append[t, c]; c += b];
Length[Rest@t]]

```

---

It's more efficient to make a lookup table, after which each search will be almost instantaneous.

```
n = 200;
d[a_, b_] := Module[{c = 0, t = {}}, While[c <= a, t = Append[t, c]; c += b];
Length[Rest@t]]
quotients = PadRight[#, n] & /@ Table[d[i, j], {i, 1, n}, {j, 1, i}];
divide[a_, b_] := quotients[[a, b]]

```

**Usage**

```
divide[97, 13]

```

> 7
> 1 votes

# Answer
C++ ,100201

```
for(int a = 1; a<=200; a++){
        for(int b=1;b<=a;b++){
    iter1 = iter2 = b;
cout<<a<<" "<<b<<endl;

c1 =0;
while(iter1 <= a)
{
    iter1 = iter1 + iter2;
    c1 ++;
    nadd++;
}
cout<<"Quotient : "<<c1;
cout<<" Remainder :"<<a - (iter1 - iter2)<<endl;
}
}
cout<<"total of add "<<nadd;

```
> 1 votes

# Answer
### R - 0 addition

```
divide<-function(a,b){
    options(warn=-1)
    A<-matrix(1:b,nrow=a,ncol=1)
    length(split(A,A)[[b]])
    }

```

Uses R vector recycling.
Second line creates a matrix of length `a` populated by a vector of length `b`which is recycled until reaching length `a`.
Third line split the matrix according to its value and return the length of the last element (hence the result of the integer division of `a` by `b`).
Populating a matrix with a vector which length is not a multiple of the length of the matrix throws a warning but if we suppress warning beforehand (line 1) it works.

To give a concrete example if we divide 5 by 3, `A` will be a vector containing 1 2 3 1 2 (i. e. 1 2 3 recycled to a length 5). The result of the splitting operation will be a list with the first element containing 1 1, the second 2 2 and the third 3 (since there is only one 3 in `A`). The result is therefore 1.
> 1 votes

# Answer
In Ruby,

```
def divide(a,b)
  n, d = 'x' * a, 'x' * b
  l = []
  (l << 'x'; d << 'x' * b) while n.size >= d.size
  l.size
end

```

I don't know TCL, but I suspect this is the same approach as @Johannes ' (first) answer.
> 1 votes

# Answer
**Java: 92 987 additions**

I use binary recursion, that `a/b == 2 * a/(2b) + maybe 1`. For that divisor *and* remainder are needed. There would normally be a subtraction a % (2b) - b, but that is resolved by holding the remainder as `(rem, remNegative)`. And `2b = b+b` of course.

```
static int add_used;

static int add(int a, int b) {
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    ++add_used;
    return a + b;
}

private static class DivRem {
    int div;
    int rem;
    int remNegative;

    DivRem(int div, int rem) {
        this.div = div;
        this.rem = rem;
    }
}

public static int divide(int a, int b) {
    add_used = 0;
    return divrem(a, b).div;
}

public static DivRem divrem(int a, int b) {
    if (b > a) {
        return new DivRem(0, a);
    }
    DivRem dr = divrem(a, add(b, b));
    dr.div = add(dr.div, dr.div);
    if (dr.rem >= add(b, dr.remNegative)) {
        dr.div = add(dr.div, 1);
        //dr.rem = add(dr.rem,  -b);
        dr.remNegative = add(dr.remNegative,  b);
    }
    return dr;
}

private static void test(int a, int b) {
    boolean okay = a/b == divide(a, b);
    System.out.printf("%d / %d = %d :: %d : #%d  %s%n", a, b, a/b,
        divide(a, b), add_used, okay);
}

public static void main(String[] args) {
   //test(2352, 324);
   int n = 0;
   for (int a = 1; a <= 200; ++a) {
       for (int b = 1; b <= a; ++b) {
           //test(a, b);
           divide(a, b);
           n += add_used;
       }
   }
   System.out.println("Additions: " + n);
}

```
> 1 votes

# Answer
```
//a lies between 1 and 200, b lies between 1 and a.

int divide(int a,int b){
int x=a,y=b;
int count=1;
while(y<x){
y+=y;
count++;
}
return count;
}

```
> 0 votes

# Answer
## C# - 0 additions

```
using System.Collections.Generic;
using System.Linq;

static int Divide(int a, int b)
{
    var ints = new List<int>(a);
    while (ints.Count < a)
        ints.AddRange(Enumerable.Range(1, b));

    return ints.Select((x, i) => x == b && i < a).Count(x => x);
}

```

Populates a list of integers with `1..b` repeated `a` times. The number of times `b` appears (except for the occurrence with an index \> `a`) is the result.

I'm not sure if the list is allowed by the rules, but I'm submitting this in the spirit of the other posts which aren't taking the rules all that seriously (after all, not using addition at all is basically bypassing the challenge altogether).
> 0 votes

# Answer
## C — 85591 Additions

Here we go. I think this might be optimal. It uses a technique of "reverse division" whereby through long multiplication it builds up the largest number `q` such that `q * b <= a`, using only `+` and `<=`. It is very, very fast.

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

// Division function.
q,u,v,z=0;s(a,b){return!a?b:!b?a:(z++,a+b);}
d(a,b,p){if((v=s(b,b))<=a)d(a,v,s(p,p));if((v=s(u,b))<=a)u=v,q=s(p,q);}
divide(a,b){u=q=0;d(a,b,1);return q;}

// Test driver.
main(){for(int a=1;a<=200;a++)for(int b=1;b<=a;b++)assert(divide(a,b)==q);
printf("%d additions\n",z);}

```

**Notes:**

1. `s(a,b)` returns the sum `a+b` and increments counter variable `z` each time an addition is performed. If either `a` or `b` is zero, the unnecessary addition is avoided.
2. `d(a,b,p)` is a recursive function to build up the internal portions for comparison and addition. It uses global variables `q`, `u`, and `v`. Maximum recursion depth is the number of bits in `a`, and the recursion is linear rather than a tree. (Note: the `b` in this function is the original `b` multiplied by a power of 2.)
3. `divide(a,b)` returns floor(a/b) as required.
4. Compiles with warnings (because code is golfed). Runs fine.
> 0 votes

# Answer
## J, 0 additions, 14 bytes

Inspired by Alexei Kopylov's answer.

```
f=:[{]#i.@>:@[

```

Uses no maths at all:

```
f=:                    NB. define function f
             [         NB. take left argument,
          >:@          NB. increment it,
       i.@             NB. generate the list [0..left arg+1)
     ]#                NB. replicate each item in the list by the right argument
                       NB. (so if ]=2, list becomes 0 0 1 1 2 2 3 3 ...)
   [{                  NB. select the ['th item from that list.

```
> 0 votes

---
Tags: code-challenge, division
---