title: Lemon-Limify a String

text:
# Question
Title: Lemon-Limify a String
Write a program or function that takes in a nonempty single-line string. You may assume it only contains printable ASCII excluding space.

Print or return an ASCII art lozenge shape similar to a lemon or lime made from the prefixes of the string.

Suppose the input string is **n** letters long. Then, such a shape consists of **2n − 1** columns of ASCII art stitched together, each consisting of **2n − 1** lines. Counting from 1, the **k**-th column is **f(k) = min(k, 2n − k)** characters wide, and contains **f(k)** copies of the first **f(k)** characters of input, centered vertically, with single blank lines separating the copies.

For example, if the input is `Lemon`, the output should be:

```
          Lemon
      Lemo     Lemo
   Lem    Lemon    Lem
 Le   Lemo     Lemo   Le
L  Lem    Lemon    Lem  L
 Le   Lemo     Lemo   Le
   Lem    Lemon    Lem
      Lemo     Lemo
          Lemon

```

If the input is `lime` the output should be:

```
      lime
   lim    lim
 li   lime   li
l  lim    lim  l
 li   lime   li
   lim    lim
      lime

```

And the same pattern is followed for other inputs:

```
a

a

Be

 Be
B  B
 Be

/\

 /\
/  /
 /\

cat

   cat
 ca   ca
c  cat  c
 ca   ca
   cat

|||

   |||
 ||   ||
|  |||  |
 ||   ||
   |||

.__.

      .__.
   .__    .__
 ._   .__.   ._
.  .__    .__  .
 ._   .__.   ._
   .__    .__
      .__.

$tring

               $tring
          $trin      $trin
      $tri     $tring     $tri
   $tr    $trin      $trin    $tr
 $t   $tri     $tring     $tri   $t
$  $tr    $trin      $trin    $tr  $
 $t   $tri     $tring     $tri   $t
   $tr    $trin      $trin    $tr
      $tri     $tring     $tri
          $trin      $trin
               $tring

```

Lines in the output may have trailing spaces and there may be one optional trailing newline.

**The shortest code in bytes wins.**

# Answer
# Matlab, ~~140 136 128~~ 124 bytes

Basically first starts with the middle section, and then prepends/appends the shortened/modified versions step by step.

```
a=input('');v=ones(nnz(a)*2-1,1)*a;v(2:2:end,:)=0;b=v;for k=a;v=v(2:end,1:end-1);v(end+1,:)=0;b=[v,b,v,''];end;b(~flip(b))=0

```

Thanks for 8 bytes @LuisMendo!

E.g. for `MATLAB` we get:

```
               MATLAB
          MATLA      MATLA
      MATL     MATLAB     MATL
   MAT    MATLA      MATLA    MAT
 MA   MATL     MATLAB     MATL   MA
M  MAT    MATLA      MATLA    MAT  M
 MA   MATL     MATLAB     MATL   MA
   MAT    MATLA      MATLA    MAT
      MATL     MATLAB     MATL
          MATLA      MATLA
               MATLAB

```
> 13 votes

# Answer
# MATL, 44 bytes

*I took some inspiration from @flawr's answer (although the algorithm is not the same)*

```
GtnEq:!g*2Mo*XKG"K1YS3LZ)OX@:Y(PO5MY(XKwyhhc

```

Input is a string with single quotes.

**Try it online!**
> 7 votes

# Answer
## Python 2, ~~121~~ 110 bytes

```
s=input()
n=len(s)
r=range(1,n)+range(n,0,-1)
for y in r:print''.join(s[:(x+y-n&(x+y>n))*x]or' '*x for x in r)

```

116 bytes if using `raw_input`. The program essentially does a mask based on L1-norm/Manhattan distance from the centre, as well as the parity of this distance compared to the parity of the input length.

*(Thanks to @Lynn for -9 bytes and paving the way for 2 more)*
> 7 votes

# Answer
# JavaScript (ES6), 132 bytes

```
s=>{x=' '.repeat(l=s.length);for(n=r='';n++<l;r=r?t+`
${r}
`+t:t)for(i=l,t='';i;t=t?w+t+w:w)w=(i<n|n+i&1?x:s).slice(0,i--);return r}

```

## Test

```
var solution =

s=>{
  x=' '.repeat(l=s.length);
  for(n=r='';n++<l;r=r?t+`\n${r}\n`+t:t)
    for(i=l,t='';i;t=t?w+t+w:w)
      w=(i<n|n+i&1?x:s).slice(0,i--);
  return r
}

result.textContent = solution('Lemon');
```

```
<input type="text" id="input" value="Lemon" oninput="result.textContent=solution(this.value)" /><pre id="result"></pre>
```
> 6 votes

# Answer
# Pyth, 32 bytes

```
jsMCm.[tylztsmC*\ dd*;ld+J._zt_J

```

Demonstration
> 5 votes

# Answer
# Jelly, ~~32~~ 26 bytes

```
³L_+«0ị“~ ”«³ḣ
JµṖ;Ṛç@þ`j⁷

```

Try it online!

EDIT: Dennis saved 6 bytes. Thanks!
> 5 votes

# Answer
# JavaScript, ~~187~~ 178 bytes

A bitwise approach. Function `m` defines a mask by starting at `2 ** length`, e.g. `00100` in binary, and defining `m(n) = m(n-1) << 1 | m(n-1) >> 1` for the first half. Interestingly the second half can be defined as `m(n) = m(n-1) << 1 & m(n-1) >> 1`. (though the program instead opts to define `m(n) = m(2 * length - 1)` for the second half) From here these masks can be used to determine whether a word or space should appear by checking `2 ** column & m(row)`. Of course in JavaScript it's shorter to write `2 ** something` with `1 << something`...

*note: written while tired. ~~May~~ Almost surely does have mistakes.*

```
s=>{m=n=>n?n>l?m(2*l-n):(p=m(n-1))>>1|p<<1:1<<l
for(r=0;r/2<=(l=s.length-1);r++){for(i=1,o="";i/2-1<l;i++)o+=(1<<i-1&m(r)?s:" ".repeat(i)).slice(0,i>l?2*l+2-i:i)
console.log(o)}}

```
> 2 votes

# Answer
# Haskell, 109 bytes

```
f s|n<-length s,r<-[1..n]++[n-1,n-2..1]=unlines[do x<-r;min(" ~"!!mod((x+y+n)*min(n-x-y)0)2)<$>take x s|y<-r]

```
> 2 votes

# Answer
# Brachylog, 46 bytes

```
{a₀⟨{;Ṣ}j₎l⟩}ᶠL&l;Ṣj₍ẹa₁ᶠ;Lz{czzcᵐ}ᵐ⟨kc↔⟩zcᵐ~ṇ

```

Try it online!

Terrible byte count and probably worse approach (not to mention Brachylog isn't exactly designed for ASCII art), but I wasted enough time on it to post it anyways.

```
              L    The variable L
{           }ᶠ     is a list containing every possible
 a₀                prefix of
                   the input
    {;Ṣ}           paired with a space
        j          and concatenated with itself
   ⟨     ₎l⟩       a number of times equal to its length.

```

```
          ᶠ    A list containing every possible
        a₁     suffix of
   Ṣ           a space
    j          concatenated with itself
  ;  ₍         a number of times equal to
 l             the length of
&              the input
      ẹ        then split back up into its elements
               is an important list which doesn't actually get a name.

```

```
                         That list
;Lz                      zipped with L
   {     }ᵐ              with each pair being
    c                    concatenated,
     z                   zipped with cycling,
      z                  zipped back,
        ᵐ                and subjected to each of its elements being
       c                 concatenated itself,
           ⟨kc↔⟩         then palindromized
                z        and zipped yet again
                 cᵐ      with every line concatenated once more
                   ~ṇ    and finally joined on newlines
                         is the output.

```

Just about the only clever part of any of this is the use of `a₁` to generate the vertical spaces largest-first while `a₀` generates the word prefixes smallest-first, and `zz` to expand single spaces into blocks of space matching the widths of the prefixes.
> 2 votes

# Answer
# TSQL, 259 bytes

Golfed:

```
DECLARE @ VARCHAR(30)='TSQL'

,@o VARCHAR(max),@i INT=0,@j INT,@t VARCHAR(max)SET @j=LEN(@)z:WHILE @i<LEN(@)SELECT @o=x+ISNULL(@o+x,''),@i+=1FROM(SELECT LEFT(IIF((@j-@i)%2=1,@,SPACE(99)),LEN(@)-@i)x)z SELECT @j-=1,@t=@o+ISNULL(CHAR(10)+@t+CHAR(10)+@o,''),@o=null,@i=0IF @j>0GOTO z PRINT @t

```

Ungolfed:

```
DECLARE @ VARCHAR(30)='TSQL'

,@o VARCHAR(max),@i INT=0,@j INT,@t VARCHAR(max)SET @j=LEN(@)
z:
WHILE @i<LEN(@)
  SELECT @o=x+ISNULL(@o+x,''),@i+=1
  FROM(SELECT LEFT(IIF((@j-@i)%2=1,@,SPACE(99)),LEN(@)-@i)x)z
SELECT @j-=1,@t=@o+ISNULL(CHAR(10)+@t+CHAR(10)+@o,''),@o=null,@i=0
IF @j>0 GOTO z

PRINT @t

```

**Fiddle**
> 1 votes

# Answer
# , 67 bytes

```
[:;"1@|:(#-h){.&.>"0 1]((<#)#&.>,:&''@]<@{"{~2|[)~[:+/~h=.|@i:@<:@#

```

Try it online!

I may try to improve this further tomorrow.
> 1 votes

# Answer
# PowerShell, 116 bytes

```
($r=0..($n=($a=$args).count-1)+$n..0|gu)|%{$y=$_;-join($r|%{($a[0..$_],(' '*($_+1)))[($_+$y+$n)%2-or($_+$y)-lt$n]})}

```

Try it online!

Unrolled:

```
$a=$args
$n=$a.count-1
$range=0..$n+$n..0|Get-Unique
$range|%{
    $y=$_
    $line=-join(
        $range|%{
            $word=$a[0..$_]
            $space=' '*($_+1)
            $switch=($_+$y+$n)%2-or($_+$y)-lt$n
            ($word,$space)[$switch]
        }
    )
    $line
}

```
> 1 votes

# Answer
# , 49 bytes

```
3 :';"{((]<@{.y''''&[~2&|@+<:>)"+/e&-)|i:1-e=.#y'

```

Try it online!

### How it works

```
3 :';"{((]<@{.y''''&[~2&|@+<:>)"+/e&-)|i:1-e=.#y'

3 :'...'       Explicit function definition; right arg(y) = given string
|i:1-e=.#y     e = length of y; create array of [e-1 .. 0 .. e-1]

((]<@{.y''&[~2&|@+<:>)"+/e&-)  Create boxed lemon shape:
                         e&-   Create array of [1 .. e .. 1]
 (                   )"+/      Outer product with [e-1 .. 0 .. e-1]
                               (left item = a, right item = b)
             2&|@+<:>          (a+b)%2 <= (a>b)
       y''&[~                  If above is true, use '' (empty string)
                               otherwise use y
  ]  {.                        Take first b chars from above
                               (fill with blanks if needed)
   <@                          Box it

;"{      Unbox and concatenate each row from the table (outer product)
         Result is the matrix of chars, giving the lemon shape

```
> 1 votes

# Answer
# C, 167 bytes

This program expects the input text to be passed as the first parameter to the program (via command line or however else) and will write the output to stdout.

```
int i,j,k,l,v;main(h,s)char**s;{h=strlen(s[1]);l=h*2;for(;++i<l;puts(""))for(j=0;++j<l,v=j<h?j:l-j;)for(k=0;k++<v;putchar((i+j+h%2)%2&&v>h-(i<h?i:l-i)?s[1][k-1]:32));}

```

This is my first attempt at code golf here as it seemed like a reasonable challenge, so it can probably be golfed more than I was able to just due to how I did it.

### Explanation

```
/* Static variables
   i - "Row" number
   j - "Column" number
   k - String character counter
   l - Double length of the input string
   v - Inverted column distance from center */
int i,j,k,l,v;

/* Main parameters
   h - (argc) Input string length
   s - argv */
main(h, s)
char**s;
{
  /* Assign the input string length and double length */

  h = strlen(s[1]);
  l = h * 2;

  /* Display content */

    /* Loop over rows l - 1 times and put a newline after each */
  for (; ++i < l; puts(""))
      /* Loop over columns l - 1 times and set the inverted column
         distance each time */
    for (j = 0; ++j < l, v = ((j < h) ? j : l - j);)
        /* Loop over characters up to the inverted column distance from the
           center (this generates the pattern of output lengths needed) */
      for (k = 0; k++ < v;)
        putchar(
            /* Check for if the current row + column (with an offset based on
               the input parity) parity is even or odd, creating the needed
               checkerboard pattern */
          (i + j + h % 2) % 2 &&
            /* If the inverted column distance from the center is more than the
               row distance from the center, then the cell is inside the
               circular shape */
          v > (h - ((i < h) ? i : l - i)) ?
              /* Display the requested character (minus one for 0 based) */
            s[1][k-1] :
            32 /* Otherwise display a space (ASCII 32) */
        );
}

```

It is significant enough to note the usage of `(n < m) ? n : (m * 2) - n` in the program at least twice to get the inverted distance from a center position `m` on a range of `m * 2` with the input `n`. If there is a shorter way to do that then it could be golfed down some more easily as that algorithm is important for how this program works.
> 0 votes

# Answer
# C, 137 bytes

```
x,y,w;main(l,v)char**v;{for(y=l=strlen(v[1]);-l<--y;putchar(10))for(x=l;-l<--x;printf("%*.*s",w,w,x+y+l&1&&w>abs(y)?v[1]:""))w=l-abs(x);}

```

Breakdown:

This draws every element of the 2n-1 x 2n-1 grid, with a mask function deciding whether the current element should be blank space or the input word (the mask checks for a diamond shape and checkerboard pattern).

```
x,y,w;
main(l,v)char**v;{
    for(y=l=strlen(v[1]);-l<--y;/*...*/)    // row loop (count down to save bytes)
        for(x=l;-l<--x;/*...*/)             // column loop
            w=l-abs(x);                     // calculate current word's width
            printf("%*.*s",                 // print...
                w,w,                        // ...with min & max width...
                x+y+l&1&&w>abs(y)           // Check mask:
                    ?v[1]                   //  ...word
                    :"")                    //  ...or blank space
        putchar(10)                         // Newline
}

```
> 0 votes

# Answer
# 05AB1E, ~~27~~ 26 bytes

```
ηεN>иygð×©.ýIgN-<®и.ø}ûøJ»

```

Try it online or verify all test cases.

**Explanation:**

```
η           # Get a list of prefixes of the (implicit) input-String
 ε          # Map each prefix `y` to:
  N>        #  Get the (0-based) map-index, and increase it by 1 to make it 1-based
    и       #  Repeat the current substring that many times as list
  yg        #  Push prefix `y` again, and pop and push its length
    ð×      #  Create a string of that many spaces
      ©     #  Store this spaces-string in variable `®` (without popping)
       .ý   #  Intersperse the earlier list with this spaces-string
  Ig        #  Push the input, and then pop and push its length
    N-      #  Subtract the (0-based) map-index
      <     #  And decrease it by 1 more
       ®и   #  Repeat spaces-string `®` that many times as list
         .ø #  Surround the earlier list with this list as both leading and trailing portion
 }û         # After the map: palindromize (abc → abcba) the entire list of lists
   ø        # Zip/transpose; swapping rows/columns
    J       # Join each inner list together to a single string
     »      # And join those strings by newlines
            # (after which the result is output implicitly)

```
> 0 votes

# Answer
# JavaScript (Node.js), ~~120~~ ~~118~~ ~~109~~ 105 bytes

```
x=>(l=x.length,g=(F,i=1,w=F(i))=>i<l?w+g(F,i+1)+w:w)(y=>g(a=>a+y+l&a+y>l?x.slice(0,a):" ".repeat(a))+`
`)

```

Try it online!

A bunch of bytes are shaved thanks to the similar structures of the nesting functions. I was confident that this golf could save some bytes but not that much.

```
x=>(                   // Main function:
 l=x.length,           //  l = Length of x
 g=(                   //  Nesting function:
  F,                   //   Output-generating function
  i=1,                 //   Counter (initially 1)
  w=F(i)               //   The output at that counter value
 )=>
  i<l                  //   If not the center line/block:
  ?w+g(F,i+1)+w        //    Sandwich next iteration with output
  :w                   //   Otherwise: Return the output
)(                     //  Call the nesting function with
 y=>                   //  Outer nest: Generating lines
  g(                   //   Call the nesting function with
   a=>                 //   Inner nest: Generating blocks
    a+y+l&a+y>l        //    If the position should not be space:
    ?x.slice(0,a)      //     Output the first a characters of x
    :" ".repeat(a)     //    Otherwise: Output a spaces
  )+"\n"               //   Append the line with a newline
)

```

### Original 118-byte answers:

```
F=(x,i=1,t=x.length,w=(G=(j,A,B,c=i+j+t&1&i+j>t?A:B)=>j<t?c+G(j+1,A+x[j],B+' ')+c:c)(0,'','')+`
`)=>i<t?w+F(x,i+1)+w:w

```

Try it online!

```
F=(x,i=1,t=x.length,w=(G=(j,c=i+j+t&1&i+j>t?x.slice(0,j):" ".repeat(j))=>j<t?c+G(j+1)+c:c)(1)+`
`)=>i<t?w+F(x,i+1)+w:w

```

Try it online!
> 0 votes

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


title: Generate keyboard shortcuts for a menu

text:
# Question
Title: Generate keyboard shortcuts for a menu
# Menu Shortcuts

Traditionally, user menus are accessible by keyboard shortcuts, such as `Alt + (a letter)`, or even simply hitting the letter when all textboxes are unfocused (gmail style).

# Your task

Given the menu entries as an input, your task is to grant each menu entry a proper shortcut letter.

Write a function or a program that accepts a set of words - the menu entries (as an array of strings, or your language equivalent), and returns a dictionary, or a hashmap, from a single letter to a menu entry.

You can either use a parameter and return a value, or use the STDIN and output your results to STDOUT. You are **not** allowed to assume a global/scope variable is already populated with the input.

# Algorithm to determine the proper letter

* Basically it's the first available letter of the word. See assumptions and examples below.
* In case all entry's letters are not available, the shortcut will be `(a letter) + (a number)`. Which letter you pick from the entry is arbitrary. The number should start from 0 and be incremented by 1 - such that all shortcuts are unique. See third example below.

# Assumptions

* The input will be a Set, i.e. no repetitions, every entry is unique.
* Length of the input can be any non-negative integer (up to MAX\_INT of your language).
* Case sensitivity: Input is case-sensitive, (but will stay unique when ignoring case). The results should contain the original entries with their original casing. However, the output shortcut letters are not case-sensitive.
* All input words will not end with numbers.
* No "evil input" will be tested. "Evil input" is such that you have to increment the counter of a certain letter more than 10 times.

# Examples

Examples below are in JSON, but you can use your language equivalent for an array and a Dictionary, or - in case you're using STD I/O - any readable format for your input and output (such as csv, or even space-separated values).

1.

```
Input:  ['File', 'Edit', 'View', 'Help']
Output: {f:'File', e:'Edit', v:'View', h:'Help'}

```

2.

```
Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {f:'Foo', b:'Bar', o:'FooBar', a:'FooBars'}

```

3.

```
Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {a:'a', b:'b', a0:'aa', b0:'bb', q:'bbq', b1:'bbb', b2:'ba'}

```

# Winning conditions

Shortest code wins. Only ASCII is allowed.

# Answer
# Javascript (*ES6*) 106 105 100

This function takes input as an an array and outputs a javascript object.

```
f=i=>i.map(a=>{for(b of c=a.toLowerCase(d=0)+d+123456789)d<!o[e=b>=0?c[0]+b:b]&&(o[d=e]=a)},o={})&&o

```

Results:

```
f(['File', 'Edit', 'View', 'Help']);
// {"f":"File","e":"Edit","v":"View","h":"Help"}

f(['Foo', 'Bar', 'FooBar', 'FooBars']);
// {"f":"Foo","b":"Bar","o":"FooBar","a":"FooBars"}

f(['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']);
// {"a":"a","b":"b","a0":"aa","b0":"bb","q":"bbq","b1":"bbb","b2":"ba"}

```

Ungolfed / Commented:

```
f=i=>{
  o={};                                        // initialize an object for output
  i.map(a=>                                    // loop through all values in input
    for(b of c=a.toLowerCase(d=0)+d+123456789) // loop through all characters of the string with 0123456789 appended to the end
                                               // and initialize d as 0 to be used as a flag
      e=b>=0?c[0]+b:b                          // if b is a number, set e to the first character + the number, otherwise b
      if(d<!o[e])                              // if the flag hasn't been triggered and o doesn't have a property e
        o[d=e]=a                               // then store the value at e and trigger the d flag
  )
  return o                                     // return the output object
}

```
> 4 votes

# Answer
# Python 2.x - 176 170 157 114 bytes

Very simple approach, but someone has to kick the game going.

```
r={}
for i in input():a=list(i.upper());r[([c for c in a+[a[0]+`x`for x in range(10)]if c not in r])[0]]=i
print r

```

---

```
Edit 1: Reversed the checking operation and made it set the result only once.
Edit 2: Removed branching.
Edit 3: Removed unnecessary dictionary. (thanks to the added assumption)

```

Examples:

```
Input:  ['File', 'Edit', 'View', 'Help']
Output: {'H': 'Help', 'V': 'View', 'E': 'Edit', 'F': 'File'}

Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {'A': 'FooBars', 'B': 'Bar', 'O': 'FooBar', 'F': 'Foo'}

Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {'A': 'a', 'B': 'b', 'Q': 'bbq', 'A0': 'aa', 'B0': 'bb', 'B1': 'bbb', 'B2': 'ba'}

```

I think the only required explanation is the ungolfed code. (This actually is the original version)

```
items = input() # ['File', 'Edit', 'View', 'Help']
chars = map(chr,range(65,91))
numbers = {}.fromkeys(chars,0)
result = {}
for item in items:
    try:
        key = [c for c in item.upper() if c in chars][0] # causes an exception when no items match
        result[key] = item
        chars.remove(key)
    except:
        key = item[0].upper()
        result[key+`numbers[key]`] = item
        numbers[key] += 1
print result

```
> 2 votes

# Answer
# JavaScript (ECMAScript 6) - 107 Characters

```
f=a=>(o={},p={},[o[[c for(c of l=w.toLowerCase())if(!o[c])][0]||(k=l[0])+(p[k]=p[k]+1|0)]=w for(w of a)],o)

```

**Explanation:**

```
f=a=>(
  o={},                              // The dictionary to output
  p={},                              // Stores record of numbers appended after duplicate
                                     // menu keys
  [                                  // Use array comprehension for each word w of input a
   (unmatchedCharacters
     =[c                             // Use array comprehension for each character c of
      for(c of l=w.toLowerCase())    //   the lower case of word w but only get
      if(!o[c])                      //   those characters which are not already a key in o.
     ],
    key=unmatchedCharacters[0]       // Take the first of those characters
     ||                              // Or if all characters are already in o
     (k=l[0])                        // Take the first character of the lower-case word
     +(p[k]=p[k]+1|0),               //   concatenated with the increment of the digit stored
                                     //   in p (or zero).
   o[key]=w)                         // Set o to map from this key to the word
   for(w of a)
  ],
  o)                                 // return o

```

**Tests:**

```
f(['File', 'Edit', 'View', 'Help']);
{f: "File", e: "Edit", v: "View", h: "Help"}

f(['Foo', 'Bar', 'FooBar', 'FooBars']);
{f: "Foo", b: "Bar", o: "FooBar", a: "FooBars"}

f(['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']);
{a: "a", b: "b", a0: "aa", b0: "bb", q: "bbq", b1: "bbb", b2: "ba"}

```
> 2 votes

# Answer
## PHP \>= 5.4 - 149 characters

According to PHP's standards *(insert sniggers here)*, the input isn't valid JSON as it uses `'` instead of `"`, so I've been a bit cheeky and I'm using the Input as an actual variable declaration:

```
<?
$i = ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba'];
$c=[];foreach($i as$w){foreach(str_split($w) as$j)if(!$c[$j]){$x=$j;goto f;}$n=0;do{$x=$w[0].$n++;}while($c[$x]);f:$c[$x]=$w;}echo json_encode($c);

```

Using the examples:

```
Input:  ['File', 'Edit', 'View', 'Help']
Output: {"F":"File","E":"Edit","V":"View","H":"Help"}

Input:  ['Foo', 'Bar', 'FooBar', 'FooBars']
Output: {"F":"Foo","B":"Bar","o":"FooBar","a":"FooBars"}

Input:  ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba']
Output: {"a":"a","b":"b","a0":"aa","b0":"bb","q":"bbq","b1":"bbb","b2":"ba"}

```

Un-golfified it's pretty basic:

```
<?
$i = ['a', 'b', 'aa', 'bb', 'bbq', 'bbb', 'ba'];
$c = [];
foreach($i as $w)
{
    foreach(str_split($w) as $j)
        if(!$c[$j])
        {
            $x = $j;
            goto f;
        }
    $n = 0;
    do
    {
        $x = $w[0] . $n++;
    }
    while($c[$x]);
    f: $c[$x] = $w;
}
echo json_encode($c);

```
> 1 votes

# Answer
# PowerShell, ~~91~~ 83 bytes

```
$r=@{}
$args|%{$r[($_|% *wer|% t*y|%{$c=$_;,''+0..9|%{$c+$_}|?{!$r.$_}})[0]]=$_}
$r

```

Try it online!

It throws an exception if a proper shortcut not found.

Unrolled:

```
$result=@{}
$args|%{
    $shortcuts = $_|% toLower|% toCharArray|%{
        $c=$_
        ,''+0..9|%{$c+$_}|?{!$result.$_}    # output shortcuts are not exist in the result
    }
    $properShortcut = $shortcuts[0]         # throws an exception if a proper shortcut not found
    $result[$properShortcut]=$_
}
$result

```
> 1 votes

# Answer
# PHP, 153 bytes

```
for($c=[];$w=trim(fgets(STDIN));$c[reset(array_diff(str_split($s),array_keys($c)))?:$y]=$w){$s=strtoupper($w);for($n=0;$c[$y=$s[0].$n++];);}print_r($c);

```

run with `php-r '<code>' <<EOF` \+ Enter + `<word1>`+Enter + `<word2>`+Enter + ... + `EOF`+Enter

working on argv for **155 bytes**:

```
$c=[];foreach($argv as$i=>$w)if($i){$s=strtoupper($w);for($n=0;$c[$y=$s[0].$n++];);$c[reset(array_diff(str_split($s),array_keys($c)))?:$y]=$w;}print_r($c);

```

run with `php -r '<code>' <word1> <word2> ...`

(-13 bytes with a defined global: `foreach($i as$w)` instead of `foreach($argv as$i=>$w)if($i)`)
> 0 votes

---
Tags: code-golf, string
---


title: Help Sam understand chess

text:
# Question
Title: Help Sam understand chess
For this challenge, you will be writing a program or function which outputs (or prints) (in a reasonable format, i.e single string or an array of lines) a chess board which indicates all the possible moves of a piece given an empty board.

---

There are 5 chess pieces (for this challenge a pawn may be ignored):

* **B**ishop (Moves diagonally any number of squares)
* **R**ook (Moves orthogonally any number of squares)
* **Q**ueen (Moves diagonally or orthogonally any number of squares)
* K**N**ight (Moves in an L shape, i.e. two in one dimension, and one in the other)
* **K**ing (Moves one step orthogonally or diagonally)

---

Your submission will take in three inputs: the row of the chess piece, the column of the chess piece, and the type of piece (as a character or integer).

Say we call drawBoard(4,4,'N') for the Knight using 0-indexing, the output will be as follows:

```
........
........
...M.M..
..M...M.
....N...
..M...M.
...M.M..
........

```

where the '.' and 'M' can be replaced accordingly with printable ascii characters of your choice.

Sample outputs as follows for other piece types. (Note all of these are called with input of 4,4 and are 0-indexed).

King:

```
........
........
........
...mmm..
...mKm..
...mmm..
........
........

```

Rook:

```
....m...
....m...
....m...
....m...
mmmmRmmm
....m...
....m...
....m...

```

---

Sam does not mind 1-based indexing, or even indexing following chess algebraic notation. However, your code must be as small as possible so Sam has enough space to think about his chess with the code next to him.

---

Sam has also realized that outputs will be accepted regardless of trailing or preceding whitespace (before and after input and each line)

# Answer
# Ruby, 125

anonymous function, prints to stdout.

RevB: golfed, but a bug fix brought it back to the same length as before.

```
->x,y,z{72.times{|i|v=y-i/9;u=x-i%=9
e=u*u+v*v
$><<(i<8?e<1?z:[r=0==v*u,b=u*u==v*v,b|r,3>e,5==e]["RBQKN"=~/#{z}/]??*:?.:$/)}}

```

Prints each of the 64 squares + 8 newlines = 72 characters individually. Relies on e, the square of the Euclidean distance between the current square and the given coordinates for checking king moves and knight moves (and also for printing the piece value z when the Euclidean distance is zero.)

**Ungolfed in test program**

```
f=->x,y,z{                         #x,y,character
  72.times{|i|                     #8 rows of (8 chars + newline) = 72 chars
    v=y-i/9;                       #vertical diff between y coord and current square
    u=x-i%=9                       #horizontal diff between x coord and current square. note i%=8
    e=u*u+v*v                      #square of euclidean distance
    $><<(                          #$> is stdout. send to it....
      i<8?                         #if not the newline column,
        e<1?z:                       #if the euclidean distance is 0, print the symbol for the piece, else
        [r=0==v*u,                   #TRUE if v or u is 0 (rook)
        b=u*u==v*v,                  #TRUE if abs(u)==abs(v) (bishop)
        b|r,                         #TRUE if either of the above are true (queen)
        3>e,                         #TRUE if e == 1 or 2 (king)
        5==e                         #TRUE if e == 5 (knight)
        ]["RBQKN"=~/#{z}/]??*:?.:    #select value from array corresponding to piece and print * or . accordingly
      $/                           #if newline column, print a newline
    )
  }
}

x=gets.to_i
y=gets.to_i
z=gets.chomp
f[x,y,z]

```
> 5 votes

# Answer
## JavaScript (ES6), ~~137~~ 130 bytes

```
f=
(x,y,p)=>`${1e8}`.repeat(8).replace(/./g,c=>+c?(i=x*x--,z=y,`
`):i+(j=z*z--)?`.*`[+!{K:i+j>3,N:i+j-5,R:i*j,B:b=i-j,Q:b*i*j}[p]]:p)
;
```

```
<div onchange=if(+x.value&&+y.value&&p.value)o.textContent=f(x.value,y.value,p.value)><input id=x type=number placeholder=X><input id=y type=number placeholder=Y><select id=p><option value=>Piece<option value=B>Bishop<option value=K>King<option value=N>Knight<option value=Q>Queen<option value=R>Rook</select><div><pre id=o></pre>
```

Note: Outputs one leading newline.

Explanation: Builds and scans though the string `100000000100000000100000000100000000100000000100000000100000000100000000`. Each `1` indicates a new line where the relative coordinate `x` is decremented and the relative coordinate `z` is reset. Each `0` indicates a new square where the relative coordinate `z` is decremented. (`y` is reserved to reset `z`.) Then uses the fact that many of the moves can be categorised by the squares `i` and `j` of the relative coordinates (before they were decremented):

* (initial square) `i + j == 0`
* B: `i == j`
* K: `i + j < 3`
* N: `i + j == 5`
* Q: `i == j || !i || !j`
* R: `!i || !j`

Because `-` is shorter than `==` it's golfier to compute the negation and invert it later. (This lets me use the cute `'.*'[]` expression although it's actually the same length as a boring `?:` expression.) `*` is also golfier than `&&`.
> 5 votes

# Answer
## Java 8 lambda, ~~473~~ ~~435~~ 289 characters

Looks like this:

```
(R,C,f)->{String b="";for(int r=0,c,d,D;r<8;r++){for(c=0;c<8;c++){d=R-r<0?r-R:R-r;D=C-c<0?c-C:C-c;b+=R==r&&C==c?f:((f=='R'||f=='Q')&&(R==r||C==c))||((f=='B'||f=='Q')&&d==D)||(f=='K'&&((R==r&&D==1||C==c&&d==1)||(d==D&&d==1)))||(f=='N'&&(d==2&&D==1||d==1&&D==2))?"M":".";}b+="\n";}return b;}

```

Or ungolfed into a class:

```
public class Q89429 {

    static String chessMoves(int row, int column, char figure) {
        String board = "";

        for (int r = 0, c, deltaRow, deltaColumn; r < 8; r++) {
            for (c = 0; c < 8; c++) {
                deltaRow = row - r < 0 ? r - row : row - r;
                deltaColumn = column - c < 0 ? c - column : column - c;
                board += row == r && column == c ?
                        figure :
                        ((figure == 'R' || figure == 'Q') && (row == r || column == c))
                        || ((figure == 'B' || figure == 'Q') && deltaRow == deltaColumn)
                        || (figure == 'K' && (
                                (row == r && deltaColumn == 1 || column == c && deltaRow == 1)
                                || (deltaRow == deltaColumn && deltaRow == 1)))
                        || (figure == 'N' && (deltaRow == 2 && deltaColumn == 1 || deltaRow == 1 && deltaColumn == 2))
                        ? "M" : ".";
            }
            board += "\n";
        }

        return board;
    }
}

```

This is a TriFunction. It returns the chess field as a printable String. ~~I wanted to use streams, and it looks quite good. It's like a 2D iteration, may be shorter without the streams.~~ *Switched to classic loops and saved a lot!*

~~It can definitely be shortened by using a ternary, I will do that now.~~

**Updates**

Saved 38 characters by using a ternary.

Saved 146 characters by using good old loops. We should all abandon streams ;)
> 4 votes

# Answer
# Ruby, 209 Bytes

```
->v,a,b{R=->x,y{x==a||y==b};B=->x,y{x-y==a-b||a-x==y-b};Q=->x,y{R.(x,y)||B.(x,y)};K=->x,y{((x-a).i+y-b).abs<2};N=->x,y{((a-x)*(b-y)).abs==2};(r=(0..7)).map{|x|r.map{|y|[x,y]==[a,b]?v: eval(v+".(x,y)??x:?o")}}}

```

This is a lambda that makes use of other lambdas, defined inside.
> 2 votes

# Answer
# x86 machine code, ~~114~~ 103 bytes

Input:

* AL - ASCII piece type (N/B/R/Q/K)
* BP - 0x88 index
* DI - Buffer

Output:

* DI - Last character + 1

Assembly source code:

```
    pusha
    mov di, offset disp_db - 3
    mov cx, 8
    mov bx, cx
    repne scasb
    mov dx, di
    sub dx, offset disp_db - 1
    pop si
    mov di, si

init_loop:
    mov ax, '.'
    mov cl, 8
    rep stosb
    mov al, 9
    mov cl, 7
    rep stosb
    inc ax
    stosb
    dec bx
    jnz init_loop

init_done:
    push di
    mov di, si

piece_loop:
    mov si, offset moves_knight - 2
    add si, dx
    lodsb
    add si, ax

vec_loop:
    lodsb
    cbw

sign_loop:
    mov bx, bp

dest_loop:
    add bx, ax
    test bl, 088h
    jnz vec_cont
    mov byte ptr [di + bx], '*'
    test dl, dl
    jp dest_loop

vec_cont:
    neg ax
    js sign_loop
    cmp al, 80h
    jnz vec_loop

done:
    popa
    mov [di + bp - 128], al
    ret

disp_db db "NBKRQ"

moves_knight db vec_knight - moves_knight - 1
moves_bishop db vec_bishop - moves_bishop - 1
moves_king   db vec_king   - moves_king   - 1
moves_rook   db vec_rook   - moves_rook   - 1
moves_queen  db vec_king   - moves_queen  - 1

vec_knight db 0Eh, 12h, 1Fh, 21h, 80h
vec_bishop db 0Fh, 11h, 80h
vec_king   db 0Fh, 11h
vec_rook   db 01h, 10h, 80h

```
> 2 votes

---
Tags: code-golf, chess
---


title: Draw my bar graph

text:
# Question
Title: Draw my bar graph
You have been chosen to make a program that creates some pretty ASCII bar charts. Here is the input format:

```
[List of words (they can have spaces)] [an integer >= 0]
Bar 3
This is so cool 4
IDK-Why 6

```

The input will have multiple lines in this format, each one representing one bar in the graph. The output format of a graph will be like this:

```
 _ _ _ _
|_|_|_|_|
 | | | |
 | | | + [name of 4th bar]
 | | + [name of 3rd bar]
 | + [name of 2nd bar]
 + [name of 1st bar]

```

Here are some examples:

```
In:
Cool 4
Kool 6

Out:
   _
  | |
 _| |
| | |
| | |
| | |
|_|_|
 | |
 | + Kool
 + Cool

In:
Graph 5
Bar 3

Out:
 _
| |
| |_
| | |
| | |
|_|_|
 | |
 | + Bar
 + Graph

In:
Very 4
Large 5
Bar 3
Graph 5

Out:
   _   _
 _| | | |
| | |_| |
| | | | |
| | | | |
|_|_|_|_|
 | | | |
 | | | + Graph
 | | + Bar
 | + Large
 + Very

In:
Bars can be 0 0
Large-bars_are$nice2 6
average)(@#$ 3
neato 5

Out:
   _
  | |  _
  | | | |
  | |_| |
  | | | |
  | | | |
 _|_|_|_|
 | | | |
 | | | + neato
 | | + average)(@#$
 | + Large-bars_are$nice2
 + Bars can be 0

```

Functions or full programs are allowed.

# Answer
> 17 votes
# sh + awk + tac, 173

Mostly an `awk` script that prints the graph bottom up which is then reversed by `tac`.

```
awk '{n[NR]=$NF;$NF="";$0=p" + "$0;p=" |"p}1;END{for(print p;p~/\|/;print p (k>($0=0)?"|":""))for(i=k=p="";i<NR;p=p (j>0||k>0?"|":" ")(!k||$0?"_":" ")){j=k;k=n[++i]--}}'|tac

```

### Description

**awk, first part, executed for each input line**

```
{
  n[NR]=$NF;         # store the value, here n[1]=0, n[2]=6, n[3]=3, n[4]=5
  $NF="";            # remove the value from the label
  $0=p" + "$0;       # add a prefix (initially empty) and a " + " in the front
  p=" |"p            # grow the prefix for the next string
}1;                  # implicitly print $0

```

**Output**

```
 + Bars can be 0
 | + Large-bars_are$nice2
 | | + average)(@#$
 | | | + neato

```

**awk, second part, executed once in the end**

```
END{
  for(print p;p~/\|/;print p (k>($0=0)?"|":""))
    for(i=k=p="";i<NR;p=p (j>0||k>0?"|":" ")(!k||$0?"_":" "))
      {j=k;k=n[++i]--}}

```

ungolfed:

```
END{
  print p;           # print the prefix again
  for(;p~/\|/;)      # for each line, bottom up. no more "|" -> we're done
  {
    p="";            # string to be built
    i=k=0;           # i: bar index, k: heigth of the previous bar
    for(;i<NR;)      # for each bar, left to right
    {
      j=k;           # store the previous bars heigth in j
      k=n[++i]--;    # get the current bars remaining height and decrement it
      p=p (j>0||k>0?"|":" ")(!k||$0?"_":" ");
                     # if the bar to the left or this one have some height
                       remaining, draw a border in between them, else a space
                     # if this bars remaining heigth is exactly 0, draw a top
                     # if $0 is set, draw the bottom
    }
    print p (k>0?"|":"");
                     # draw (or not) the rightmost border, finally print
    $0=0;            # unset $0, only to detect first run
  }
}

```

**Output**

```
 | | | |             # the prefix
 _|_|_|_|            # the strings built by the nested loops
  | | | |            |
  | | | |            v
  | |_| |
  | | | |
  | |  _
   _                 # no more "|" in the string, we're done

```

**tac reverses the lines**

```
   _
  | |  _
  | | | |
  | |_| |
  | | | |
  | | | |
 _|_|_|_|
 | | | |
 | | | + neato
 | | + average)(@#$
 | + Large-bars_are$nice2
 + Bars can be 0

```

# Answer
> 8 votes
# JavaScript (ES6), 270 ~~262 270 287~~

*Bug fix* added a missing row of '|' under the bars

```
l=>{t=p=o='';l=l.split`
`.map(r=>([,b,c]=r.match(/(.*) (\d+)/),[' + '+b,+c>t?t=c:c]));for(++t;t--;o+=`
`)l.map(x=>o+=x[1]<t?'y y':x[1]>t?t?'x x':'x_x':'y_y');return o.replace(/(yx)|(xy)|(xx?)/g,'|').replace(/y+/g,' ')+[...l,' '].map(x=>p+x[p+=' |',0]).reverse().join`
`}

```

**Test** Test in Firefox, as Chrome does not support ES6 Destructuring assignment

```
F=l=>{
  t=p=o='';l=l.split`\n`.map(r=>([,b,c]=r.match(/(.*) (\d+)/),[' + '+b,+c>t?t=c:c]));
  for(++t;t--;o+=`\n`)l.map(x=>o+=x[1]<t?'y y':x[1]>t?t?'x x':'x_x':'y_y');
  return o.replace(/(yx)|(xy)|(xx?)/g,'|').replace(/y+/g,' ')
  +[...l,' '].map(x=>p+x[p+=' |',0]).reverse().join`\n`
}

function test()
{
  var i=I.value
  O.textContent=F(i)
}

test()
```

```
textarea { display:block; width:50%; height:5em}
```

```
Input
<textarea id=I>Bars can be 0 0
Large-bars_are$nice2 6
average)(@#$ 3
neato 5</textarea>
<button onclick='test()'>go</button><br>
Output
<pre id=O></pre>
```

# Answer
> 2 votes
# 421 bytes - Python 2

```
import sys
l=sys.stdin.read().split('\n')
b=[(' '.join(x[:-1]),int(x[-1])) for x in map(str.split,l[:-1])]
a=len(b)
e=enumerate
m=[' '*(a+1)+'|'*x[1] for i,x in e(b)]+[' '*(len(b)+1)+'|'*b[-1][1]]
h=[' '*i+'+'+'|'*(a-i)+'_'+' '*(x[1]-1)+'_' for i,x in e(b)]
c=m+h
c[::2]=m
c[1::2]=h
c=[''.join(' ' if not x else x for x in l) for l in map(None,*c)]
for i,(n,_) in e(b):
 c[a-i-1]+='\b'*i*2+n
c='\n'.join(c[::-1])
print(c)

```

## Tests

```
a 1
b 2
c 3
     _
   _| |
 _| | |
|_|_|_|
 | | |
 | | + c
 | + b
 + a

```

# Answer
> 2 votes
# PowerShell, ~~208~~ ~~194~~ ~~190~~ ~~168~~ ~~167~~ 164 bytes

```
(($h=$args|%{$t,$n=$_-split'(?=\d+$)';$r=,"$c + $t"+$r;$c+=' |';$n})|sort)[-1]..0|%{$i=$_
&{-join($h|%{($p,($p=' |'[$i-lt$_])|sort)[-1];' _'[$i-in0,$_]})+$p}}
$c
$r

```

Try it online!

Unrolled:

```
# parse input
$heights = $args|%{
    $title,$number=$_-split'(?=\d+$)'   # the title contains a trailing space. It's allowed by the author
    $rows=,"$columns + $title"+$rows
    $columns+=' |'
    Write-Output $number
}

# draw bars
($heights|sort)[-1]..0|%{   # max($heights)..0
    $lineNum=$_
    &{                      # execute the scriptblock to reset inner variables
        -join(
            $heights|%{
                $currLeftBorder = ' |'[$lineNum -lt $_]
                Write-Output ($prev,$currLeftBorder|sort)[-1]   # max
                Write-Output ' _'[$lineNum -in 0,$_]
                $prev=$currLeftBorder
            }
        )+$prev
    }
}

# draw bottom columns and titles
Write-Output $columns
Write-Output $rows

```

# Answer
> 1 votes
## Java, 613 for the printing function

It may be possible to save a few bytes by the "usual" transformations of `for(i=0;i<n;i++)` to `for(;i++<n;)`, simplifying the ternary conditionals, or with more elegant computations of the "labels" and "heights", but it's a start.

```
package stackoverflow.codegolf.barchart;

import static java.util.stream.Stream.of;

import java.util.stream.IntStream;

public class BarChartTest
{
    public static void main(String[] args)
    {
        String input0[] = {
            "Cool 4",
            "Kool 6",
        };
        String input1[] = {
            "Graph 5",
            "Bar 3",
        };
        String input2[] = {
            "Very 4",
            "Large 5",
            "Bar 3",
            "Graph 5",
        };
        String input3[] = {
            "Bars can be 0 0",
            "Large-bars_are$nice2 6",
            "average)(@#$ 3",
            "neato 5",
        };
        runTest(input0);
        runTest(input1);
        runTest(input2);
        runTest(input3);
    }

    private static void runTest(String input[])
    {
        System.out.println("In:");
        for (String string : input)
        {
            System.out.println(string);
        }
        System.out.println("Out:");
        BarChartTest b = new BarChartTest();
        b.print(input);
    }

    void p(String a[]){int h[]=of(a).map(this::s).mapToInt(Integer::parseInt).toArray(),M=IntStream.of(h).max().getAsInt(),C=a.length,r,c,y;Object t[]=of(a).map(this::p).toArray();String s="",p=" + ",w="";char n=10,v='|',i=32,u=95,e;for(r=0;r<=M;r++){e=r==M?'_':' ';y=M-r;for(c=0; c<C; c++){s+=h[c]>y?v:c>0?h[c-1]>y?v:e:r==0?e:i;s+=h[c]==y?u:e;}s+=h[C-1]>y?v:e;s+=n;}for(r=0;r<C;r++){for(c=0;c<C-r;c++){s+=" |";}s+=r>0?p+t[C-r]:w;s+=n;}s+=p+t[0];System.out.println(s);}int b(String s){return s.lastIndexOf(" ");}String p(String s){return s.substring(0,b(s));}String s(String s){return s.substring(b(s)+1,s.length());}
}

```

# Answer
> 1 votes
## Haskell, 323 bytes

```
f x|(p,q)<-unzip$map((\l->(unwords$init l,(read$last l))).words)$lines x=unlines(reverse$init.(zip((zipWith max=<<tail)$0:q++[0])(q++[0])>>=).(!)<$>[0..maximum q])++v p++'\n':(0#p)
v=(>>" |")
_#[]=""
l#(h:t)=(l+1)#t++v[1..l]++" + "++h++"\n"
0!(0,_)=" _"
0!_="|_"
i!(j,k)|i<j=(i==k)?'|'|1<2=(i==k)?' '
i?c|i=c:"_"|1<2=c:" "

```

Usage example:

```
*Main> putStr $ f "Bars can be 0 0\nLarge-bars_are$nice2 6\naverage)(@#$ 3\nneato 5"
   _
  | |  _
  | | | |
  | |_| |
  | | | |
  | | | |
 _|_|_|_|
 | | | |
 | | | + neato
 | | + average)(@#$
 | + Large-bars_are$nice2
 + Bars can be 0

```

How it works (rough overview, details maybe later):

```
(p,q)<-unzip$map((\l->(unwords$init l,(read$last l))).words)$lines x
           -- breaks the input into a list of labels (-> p), e.g.
           -- ["Bars can be 0","Lagerge-basr_asr$niche",...] and a list of heights
           -- (-> q), e.g. [0,6,3,5]

unlines(reverse$init.(zip((zipWith max=<<tail)$0:q++[0])(q++[0])>>=).(!)<$>[0..maximum q])
           -- builds the bars
v p++"\n"
           -- builds the first row of "|" underneath the zero line
(0#p)
           -- build the label section

```

The parsing part (`(p,q)<-unlines...`) takes a lot of bytes, maybe I can it golf further down.

# Answer
> 1 votes
## Python 2, 345 bytes

```
B,H=zip(*[(a,int(b))for a,b in[x.rsplit(' ',1)for x in input().split('\n')]])
h=max(H)
L=len(B)
b=['|'*H[0]]*(L*2+1)
for i in range(L):b[2+i*2]='|'*max(H[i],H[min(i+1,L-1)]);b[1+i*2]=('_'+' '*(H[i]-1)+'_')[:H[i]+1]
b=[x.ljust(h+1)for x in b]
for l in zip(*b)[::-1]:print ''.join(l)
print' |'*L
for i in range(-1,-L-1,-1):print' |'*(L+i),'+',B[i]

```

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


# Question
Title: Divide a number by 3 without using *, /, +, -, % operators
Quoting this question on SO (Spoiler alert!):

> This question has been asked in an Oracle interview.
>
> How would you divide a number by 3 without using \*, /, +, -, %, operators?
>
> The number may be signed or unsigned.

The task is solvable, but see if you can write the shortest code.

## Rules:

* Perform the required **integer** division (`/3`)
* Do not use the non-text-based operators `*`, `/`, `+`, `-`, or `%` (or their equivalents, such as `__div__` or `add()`). This also applies to incrementing and decrementing operators, like `i++` or `i--`. Use of operators for string concatenation and formatting are OK. Using these characters for different operators, such as unary `-` operator for negative numbers, or `*` to represent a pointer in C is OK as well.
* Input value can be arbitrarily large (whatever your system can handle), both positive and negative
* Input can be on STDIN or ARGV or entered any other way
* Create the shortest code you can to do the above

# Answer
> 15 votes
# J, ~~45 44~~  10 chars

`".,&'r3'":`

Works with negatives:

```
".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99

```

`":` \- format as text

`,&'r3'` \- append `r3` to the end

`".` \- execute the string, e.g. `15r3`

# Answer
> 58 votes
# C, 167503724710

Here's my solution to the problem. I admit it is unlikely to win a strict code golf competition, but it doesn't use any tricks to indirectly call built-in division functionality, it is written in portable C (as the original Stack Overflow question asked for), it works perfectly for negative numbers, and the code is exceptionally clear and explicit.

My program is the *output* of the following script:

```
#!/usr/bin/env python3
import sys

# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')

# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))

# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')

```

Character count: 71 + 39 * 2\**32 + 95 = **167503724710**

### Benchmarks

It was asked how long this would take and how much memory it would use, so here are some benchmarks:

* Script execution time — Running `./test.py | pv --buffer-size=1M --average-rate > /dev/null` for about 30 seconds gives a rate of about 14.8 MB/s. The rate of output can reasonably be assumed to be roughly constant, so the running time to completion should be about 167503724710 B / (14.8 * 1048576 B/s) ≈ 10794 s.
* Compilation time — The TCC compiler claims to compile C code at 29.6 MB/s, which makes for a compilation time of 167503724710 B / (29.6 * 1048576 B/s) ≈ 5397 s. (Of course this can run in a pipeline with the script.)
* Size of compiled code — I tried estimating it using `./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null`, but it seems `tcc` doesn't output anything until it reads the entire source file in.
* Memory usage to run — Since the algorithm is linear (and tcc doesn't optimize across lines), the memory overhead should be only a few kilobytes (apart from the code itself, of course).

# Answer
> 40 votes
# Ruby 28

```
b=->n{n.to_s(3).chop.to_i 3}

```

To divide by 3 we just need to remove the trailing zero in base 3 number: `120 -> 11110 -> 1111 -> 40`

Works with negatives:

```
ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15
-5

```

# Ruby, ~~60~~45

Alternatively, w/o using base conversion:

~~d=-\>n{x=n.abs;r=(0..1.0/0).step(3).take(x).index x;n\>0?r:-r}~~

```
d=->n{(r=1.step(n.abs,3).to_a.size);n>0?r:-r}

```

# Answer
> 27 votes
# Mathematica, 13 chars

```
Mean@{#,0,0}&

```

# Answer
> 18 votes
## JavaScript, 56

```
alert(Array(-~prompt()).join().replace(/,,,/g,1).length)

```

Makes a string of length `n` of repeating `,`s and replaces `,,,` with `1`. Then, it measures the string's resulting length. (Hopefully unary `-` is allowed!)

# Answer
> 16 votes
## Python, 41 38

```
print"-"[x:]+`len(xrange(2,abs(x),3))`

```

`xrange` seems to be able to handle large numbers (I think the limit is the same as for a long in C) almost instantly.

```
>>> x = -72
-24

>>> x = 9223372036854775806
3074457345618258602

```

# Answer
> 11 votes
## Haskell, 90 ~~106~~

```
d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]

```

Creates an infinite (lazy) lookup list `[(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...]`, trims all elements that don't match `n` (`/=` is inequality in Haskell) and returns the first which does.

This gets much simpler if there are no negative numbers:

## 25 ~~27~~

```
(([0..]>>=replicate 3)!!)

```

simply returns the `n`th element of the list `[0,0,0,1,1,1,2, ...]`.

# Answer
> 8 votes
## C#, 232 bytes

My first code golf... And since there wasn't any C# and I wanted to try a different method not tried here, thought I would give it a shot. Like some others here, only non-negative numbers.

```
class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}

```

## Ungolfed

```
class l : System.Collections.Generic.List<int>
{ }
class p
{
    static void Main(string[] g)
    {
        int n = int.Parse(g[0]);
        l b, a = new l();
        b = new l();
        while (a.Count < n) a.Add(1);
        while (a.Count > 2)
        {
            a.RemoveRange(0, 3);
            b.Add(1);
        }
        System.Console.Write(b.Count);
    }
}

```

# Answer
> 7 votes
## Perl (~~26~~ 22)

```
$_=3x pop;say s|333||g

```

This version (ab)uses Perl's regex engine. It reads a number as the last command line argument (`pop`) and builds a string of `3`s of this length (`"3" x $number`). The regex substitution operator (`s///`, here written with different delimitiers because of the puzzle's rules and with a `g`lobal flag) substitues three characters by the empty string and returns the number of substitutions, which is the input number integer-divided by three. It could even be written without `3`, but the above version looks funnier.

```
$ perl -E '$_=3x pop;say s|333||g' 42
14

```

# Answer
> 6 votes
## JavaScript, 55

```
alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))

```

If one can't use `-1`, then here is a version replacing it with `~0` (thanks Peter Taylor!).

```
alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))

```

# Answer
> 6 votes
# Python 42

```
int(' -'[x<0]+str(len(range(2,abs(x),3))))

```

Since every solution posted here that Ive checked truncates decimals here is my solution that does that.

# Python 50 51

```
int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))

```

Since python does floor division, here is my solution that implements that.

Input integer is in the variable x.

Tested in Python 2.7 but I suspect it works in 3 as well.

# Answer
> 6 votes
## C, 160 chars

Character by character long division solution using lookup tables, i.e. without string atoi() or printf() to convert between base 10 strings and integers.

Output will sometimes include a leading zero - part of it's charm.

```
main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}

```

Note:

* abuses array access to implement addition.
* compiles with clang 4.0, other compilers may barf.

Testing:

```
./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670

```

# Answer
> 6 votes
# C 83 characters

The number to divide is passed in through stdin, and it returns it as the exit code from `main()` (%ERRORLEVEL% in CMD). This code abuses some versions of MinGW in that when optimizations aren't on, it treats the last assignment value as a return statement. It can probably be reduced a bit. Supports all numbers that can fit in to an `int`

If unary negate (-) is not permitted: (129)

```
I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}

```

If unary negate **IS** permitted: (123)

```
I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}

```

# EDIT: ugoren pointed out to me that -~ is an increment...

83 Characters if unary negate is permitted :D

```
main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}

```

# Answer
> 5 votes
# C, 139 chars

```
t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}

```

Run with number as command line argument

* Handles both negative and positive numbers

Testing:

```
 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670

```

Edits:

* saved 10 chars by shuffling addition (A) to remove local variables.

# Answer
> 5 votes
## C, 81 73 chars

Supports non-negative numbers only.

```
char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}

```

The idea is to use pointer arithemtic. The number is read into the pointer `x`, which doesn't point anywhere. `&x[~2]` = `&x[-3]` = `x-3` is used to subtract 3. This is repeated as long as the number is above 2. `i` counts the number of times this is done (`&i[1]` = `i+1`).

# Answer
> 5 votes
## ZSH — ~~31~~ 20/21

```
echo {2..x..3}|wc -w

```

For negative numbers:

```
echo {-2..x..3}|wc -w

```

### With negative numbers (ZSH + `bc`) — ~~62~~ 61

I probably shouldn't give two programs as my answer, so here's one that works for any sign of number:

```
echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc

```

This uses the same base conversion trick as Artem Ice's answer.

# Answer
> 5 votes
## Java ~~86~~ 79

Assume the integer is in y:

Converts to a string in base 3, removes the last character ( right shift "\>\>" in base 3 ), then converts back to integer.

Works for negative numbers.

If the number, y, is \< 3 or \> -3, then it gives 0.

```
System.out.print(~2<y&y<3?0:Long.valueOf(Long.toString(y,3).split(".$")[0],3));

```

First time posting on code golf. =) So can't comment yet.

Thx Kevin Cruijssen for the tips.

# Answer
> 4 votes
# Python2.6 (~~29~~)(~~71~~)(~~57~~)(~~52~~)(43)

```
z=len(range(2,abs(x),3))
print (z,-z)[x<0]

```
~~```
print len(range(2,input(),3))

```~~

Edit - Just realized that we have to handle negative integers too. Will fix that later

Edit2 - Fixed

Edit3 - Saved 5 chars by following Joel Cornett's advice

Edit4 - Since input doesn't have to be necessarily be from STDIN or ARGV, saved 9 chars by not taking any input from stdin

# Answer
> 4 votes
# Javascript, ~~47~~ 29

Uses `eval` to dynamically generate a `/`. Uses `+` only for string concatenation, not addition.

```
alert(eval(prompt()+"\57"+3))

```

EDIT: Used `"\57"` instead of `String.fromCharCode(47)`

# Answer
> 4 votes
## Ruby (~~43~~ ~~22~~ 17)

Not only golf, but elegance also :)

```
p Rational gets,3

```

Output will be like `(41/1)`. If it must be integer then we must add `.to_i` to result, and if we change `to_i` to `to_f` then we will can get output for floats also.

# Answer
> 4 votes
# TI-Basic, 8 bytes

Winner? :)

```
int(mean({Ans,0,0

```

P.S. Rounds towards infinity for negative numbers (see here for why). To round to zero instead, replace `int(` with `iPart(` for no byte change.

**Test cases**

```
-4:prgmDIVIDE
              -2
11:prgmDIVIDE
               3
109:prgmDIVIDE
              36

```

# Answer
> 3 votes
# Python 2.x, ~~54~~ ~~53~~ 51

`print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))`

Where `_` is the dividend and is entered as such.

```
>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6

```

Note: Not sure if using the interactive interpreter is allowed, but according to the OP: "Input can be on STDIN or ARGV or entered any other way"

Edit: Now for python 3 (works in 2.x, but prints a tuple). Works with negatives.

# Answer
> 3 votes
## C++, 191

With main and includes, its 246, without main and includes, it's only 178. Newlines count as 1 character. Treats all numbers as unsigned. I don't get warnings for having main return an unsigned int so its fair game.

My first ever codegolf submission.

```
#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}

```

uses shifts to divide number by 4 repeatedly, and calculates sum (which converges to 1/3)

Pseudocode:

```
// typedefs and #defines for brevity

function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.

function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).

```

As an aside, I could eliminate the main method by naming d main and making it take a char \** and using the programs return value as the output. It will return the number of command line arguments divided by three, rounded down. This brings its length to the advertised 191:

```
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}

```

# Answer
> 3 votes
## Golfscript - 13 chars

```
~3base);3base

```

# Answer
> 3 votes
## **PowerShell 57 or 46**

In 57 characters using `%` as the PowerShell foreach operator, not modulo. This solution can accept positive or negative integers.

```
(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length

```

In 46 characters if `*` is allowed as the string repetition operator, not multiply. This option requires positive integers as input values.

```
("1"*(Read-Host)-replace111,0-replace1).Length

```

# Answer
> 3 votes
# R

These only work with positive integers:

```
max(sapply(split(1:x,1:3), length))
# Gives a warning that should be ignored

```

Or:

```
min(table(rep(1:3, x)[1:x]))

```

Or:

```
length((1:x)[seq(3,x,3)])

```

Or:

```
sum(rep(1,x)[seq(3,x,3)])

```

\[\[EDIT\]\] And an ugly one:

```
trunc(sum(rep(0.3333333333, x)))

```

\[\[EDIT2\]\] Plus probably the best one - inspired by the matlab code above by Elliot G:

```
length(seq(1,x,3))

```

# Answer
> 3 votes
# SmileBASIC, ~~58~~ ~~51~~ 36 bytes (no mathematical functions!)

```
INPUT N
BGANIM.,4,-3,N
WAIT?BGROT(0)

```

Explanation:

```
INPUT N           'get input
BGANIM 0,"R",-3,N 'smoothly rotate background layer 0 by N degrees over 3 frames
WAIT              'wait 1 frame
PRINT BGROT(0)    'display angle of layer 0

```

The program moves the background layer smoothly over 3 frames, and then gets the angle after 1 frame, when it has traveled 1/3 of its total distance.

### Float division version, 38 bytes:

```
INPUT N
BGANIM.,7,-3,N
WAIT?BGVAR(0,7)

```

Explanation:

```
INPUT N           'input
BGANIM 0,"V",-3,N 'smoothly change layer 0's internal variable to N over 3 frames
WAIT              'wait 1 frame
PRINT BGVAR(0,7)  'display layer 0's internal variable

```

# Answer
> 3 votes
# Haskell ~~41~~ 39 chars

Works with the full set of positive and negative integers

```
f n=sum[sum$1:[-2|n<0]|i<-[3,6..abs n]]

```

First creates a list 1's or (-1)'s (depending on the sign of the input) for every third integer from 0 up until the input `n`. `abs(n)` for negative numbers inclusive.

e.g `n=8 -> [0,3,6]`

It then returns the sum of this list.

# Answer
> 3 votes
# Python 3, 72 bytes

```
f=lambda x:x and s(x>>1,f(x>>1))
s=lambda x,y:y and s(x^y,(~x&y)<<1)or x

```

Try it online!

A bitwise solution consisting of two recursive functions, one to calculate third, the other to subtract. Because multiplying and dividing by 2 is easy to do bitwise, we can use the fact:
\\$X/3=X/2-(X/2)/3\\$
to recursively find the third.

It does produce some weird rounding patterns for non-multiples of three.

```
0 -> 0 (0)
1 -> 0 (0.333...)
2 -> 1 (0.666...)
3 -> 1 (1)
4 -> 1 (1.333...)
5 -> 1 (1.666...)
6 -> 2 (2)
7 -> 2 (2.333...)
8 -> 3 (2.666...)
9 -> 3 (3)
10 -> 4 (3.333...)
11 -> 4 (3.666...)
12 -> 4 (4)
13 -> 4 (4.333...)
14 -> 5 (4.666...)
15 -> 5 (5)

```

# Answer
> 2 votes
# Clojure, 87; works with negatives; based on lazyseqs

```
(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))

```

Ungolfed:

```
(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))

```

# Answer
> 2 votes
# Mathematica 36 51 42 chars

This is easily achieved in base 3.

`IntegerDigits[n,3]` converts the absolute value of the number to base 3.

`Most` takes all but the rightmost digit. This "rightward shift" amounts to integer division by 3.

`FromDigits` converts back to base 10.

`Sign` restores, if necessary, the sign.

```
Sign@n*Most@IntegerDigits[n,3]~FromDigits~3

```

# Answer
> 2 votes
## Sage Notebook (21)

```
ZZ(n.digits(3)[1:],3)

```

# Answer
> 2 votes
# F# (81)

Using inclusive ranges:

```
let(^)s x=if s<0 then int("-"+string x)else x
let d m =sign m^[3..3..abs m].Length

```

Alternatively, using strings:

```
let (^) s x = if s < 0 then int("-" + string x) else x
let d m =
  let n = abs m
  [0..n]
  |> Seq.map (fun i -> i, String.replicate i "aaa")
  |> Seq.takeWhile (fun (i, s) -> s.Length <= n)
  |> Seq.last
  |> fst
  |> (^) (sign m)

```

This is verbose but it's better than being forced to use loops in many imperative languages. `String.replicate` is especially valuable.

# Answer
> 2 votes
# APL (NARS2000), 7 characters

Inspiration

```
⍎⍞,'r3'

```

evaluate

text input

`,'r3'` followed by "r3"

So "15" becomes "15r3" which is NARS2000's rational point notation and evaluates to 5.

Note that the OP states

> * Input can be on STDIN or ARGV or entered any other way
> * Create the shortest code you can to do the above

which allows me to take input as string, and count code length in characters (not bytes – as this is a fairly old challenge that predates the adoption of bytes as default code length unit).

# Answer
> 2 votes
# 05AB1E, 5 bytes

```
3B¨3ö

```

Try it online!

# Answer
> 2 votes
# C# with Linq, 51 Bytes

```
using System.Linq;(n)=>(int)new[]{n,0,0}.Average();

```

Unfortunately much longer than the Mathematica version of this approach (pesky using statement), but pretty good for C#.

Try it out here.

# Answer
> 2 votes
# C (gcc), ~~72 69 59~~ 58 bytes

```
a,q;f(x){for(a=q=0;a=-~-~-~a,a<=abs(x);)q=-~q;x=x<0?-q:q;}

```

Try it online!

Edit: Now works with negative arguments.

# Answer
> 2 votes
# Haskell, ~~62~~ ~~52~~ 41 Chars

```
f n=sum[last$1:[-1|n<0]|i<-[3,6..abs(n)]]

```

If using sum is not allowed, here's a 52 char solution:

```
f n|n>0=s|1>0=(-s)where s=length[1|i<-[3,6..abs(n)]]

```

# Answer
> 1 votes
## Scala 96

```
def d(x:Int)={val y=x.abs;val r=0.to(y).flatMap(List.fill(3)(_)).drop(y).head;if(x==y)r else -r}

```

I do realize now it is basically the same idea behind some other answers here (Haskell, Clojure and the 2nd take of this one in Ruby, to name a few)... :-/

# Answer
> 1 votes
## C++ 633 byes (including whitespace; 457 bytes excluding scaffolding)

I know this is not anywhere near the shortest code, but it does have some "advantages". First the code:

```
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;typedef int I;typedef unsigned U;U A(U l,U r){U t;while(r)t=l^r,r=(l&r)<<1,l=t;return l;}
#define N(l)A(~l,1)
#define S(l,r)A(l,N(r))
U M(U l, U r){U p=0;while(r){if(r&1)p=A(p,l);l<<=1;r>>=1;}return p;}U D(U n,U&r){U m=U(1)<<S(M(sizeof(U),CHAR_BIT),1),q=r=0,x=1;while(x){q<<=1;r<<=1;if(n&m)r|=1;if(r>=3)q|=1,r=S(r,3);n<<=1;x<<=1;}return q;}I D(I n,I&r){bool o=n<0;U p=o?N(n):n,s,t;s=D(p,t);r=o?N(t):t;return o?N(s):s;}I main(I c,char**v){I i=1,q,r;while(i<c)q=D(atoi(v[i]),r),cout<<v[i]<<" divided by 3 == "<<q<<" with a remainder of "<<r<<endl,i=A(i,1);}

```

The advantages over the other solutions, even though it can't win on a purely codegolf basis:

* It only uses the standard library to obtain the value of CHAR\_BIT, atoi, cout, and endl. Consequently, it does not depend on any math routines in the standard library beyond those to convert a string to and from a number. It most definitely does not use any part of the standard library to divide by 3.
* It at no time uses any of the operators + - * / % (binary or unary, numeric or string). Note that it does use two asterisks to declare a pointer to a pointer to char, but it only uses that to access command line parameters of number to divide.
* It uses bit manipulation and relational operators exclusively in the division process.
* If the scaffolding code (main and two of the three include files) is removed, the code that does the actual work of division by 3 is only 457 bytes.
* I'm pretty sure this code should work on any C++ compiler conforming to the standard and does not exploit any tricks that only work on a subset of compilers or platforms. One possible exception to this is it might not work on a platform that does not use twos complement signed integers, though I don't have access to any platform like that to test that theory. Another possible exception (related) is if automatic signed / unsigned conversions are not supported as they are for most (or all) platforms utilizing twos complement signed integers.

I'm sure there are other ways to make this shorter, but I've spent enough time on it. Mainly I wanted to perform the exercise without any "cheating" via use of any operations from the standard library. By defining functions and macros that perform unary negation, addition, subtraction, multiplication, and division strictly in terms of bit level operations and relational operators, signed (or unsigned) integers can be divided by three. I've hard coded the divisor to 3 to remove a few bytes of code here and there, though adding a parameter to pass in the divisor is fairly trivial.

The signed division function notes the sign of the dividend then calls the unsigned division function with the dividends absolute value. Once the unsigned division returns the unsigned quotient and remainder, the original sign is used to negate the signed quotient and remainder as needed.

Edit: Only after I wrote and submitted my solution did I go look at the original question on SO. Some interesting stuff there, and of course someone had already come up with my solution. FWIW, I did write this on my own! Not that it matters for this old of a question, especially in a codegolf exercise. :)

# Answer
> 1 votes
**OCTAVE/MATLAB 13**

Code where x is an integer. Only works for positive integers and rounds the result up.

```
length(1:3:x)

```

# Answer
> 1 votes
## Java 317

I know this is extremely long, and I know this is supposed to be code golf, but for kicks I wanted to write a version that ALSO:

* Doesn't use the characters `[0-9]`
* Doesn't branch

Enjoy :)

```
import java.util.LinkedList;class Div{int d(int a){int t=getClass().getName().length();char[]s=Integer.toString(a,t).toCharArray();StringBuilder b=new StringBuilder();LinkedList<Character>l=new LinkedList<>();for(char z:s){l.add(z);}l.removeLast();for(char z:l){b.append(z);}return Integer.valueOf(b.toString(),t);}}

```

# Answer
> 1 votes
# Perl 5, 158 characters

```
sub t{use integer;$m=unpack(J,U x 8)^(($n=pop)>0&&3);$p=0;for($t= ~0;$t;$t<<=1){$c=$p&($o=$m&1&&$n);$p=($p^$o)>>1;($p,$c)=($p^$c,($p&$c)<<1)while$c;$m>>=1}$p}

```

This is more than 7 times longer than the answer by memowe, but it runs faster when the input is large, and supports negative inputs. Now you can divide -2147483648 by 3. This defines a sub. `t(-2147483648)` returns -715827883 because it rounds *down*.

## Division is multiplication!

Division by 3 uses the formula

* n ÷ 3 = n × (2<sup>64</sup> ÷ 3) ÷ 2<sup>64</sup>

with an integer constant to approximate 2<sup>64</sup> ÷ 3. The algorithm multiplies by this constant and drops the lower 64 bits of the 128-bit product. To prevent error, n must be in range for a signed 64-bit integer, and the constant must be

* ⌊2<sup>64</sup> ÷ 3⌋ = 5555 5555 5555 5555<sub>16</sub> if n is negative, or
* ⌈2<sup>64</sup> ÷ 3⌉ = 5555 5555 5555 5556<sub>16</sub> if n is positive.

Multiplication uses an add-and-shift loop. Addition uses bitwise-xor to add and bitwise-and to carry. Shifts preserve the high 64 bits of each 65-bit sum and the final 128-bit product.

## Ungolfed code

```
use strict;
use warnings;

# t($n) is floor($n / 3) with only bitwise operations
sub t {
    use integer; # for signed right shift
    my $n = shift;

    # The formula with 64-bit integers is:
    #   $n / 3 = ($n * (1 << 64) / 3) >> 64
    # If this perl has 32-bit integers, then $m and $t get 32-bit
    # values, so the shifts are by 32.

    # $m = (1 << 64) / 3
    #    = 0x5555 5555 5555 5555 if $n < 0
    #    = 0x5555 5555 5555 5556 else
    my $m = unpack 'J', 'UUUUUUUU';  # Unpack 0x55 bytes.
    $n < 0 or $m ^= 3;               # 0x55 ^ 3 == 0x56

    # Multiplication: $p = ($n * $m) >> 64
    my $p = 0;
    for (my $t = ~0; $t; $t <<= 1) { # Loop 64 times.
    if ($m & 1) {
        # Add and shift: $p = ($p + $n) >> 1
        # Shift early to prevent 65-bit overflow.
        my $c = $p & $n;         # Carry.
        $p = ($p ^ $n) >> 1;     # Add by exclusive-or.
        while ($c) {
        ($p, $c) = ($p ^ $c, ($p & $c) << 1);
        }
    }
    else {
        $p >>= 1;
    }
    $m >>= 1;
    }
    return $p;
}

# test program: divide integers
use POSIX qw(floor);
for my $integer (@ARGV) {
    $integer = int($integer);
    my $have = t($integer);
    my $want = floor($integer / 3);
    printf("%d -> %d (%s)\n", $integer, $have,
       $have == $want ? "correct" : "OFF BY @{[$want - $have]}");
}

```

The golfed version has some differences:

* It clobbers global variables.
* It uses the other value of $m if $n is zero.
* It replaces the check `if ($m & 1)` with a new variable `$o=$m&1&&$n`.

# Answer
> 1 votes
# Julia - 29 characters

I'm assuming n as a variable assigned prior to running this line of code.

```
parseint(chop(base(3,n,2)),3)

```

Performs the truncation variant (-35 -\> -11 not -12). In the current stable release (0.2.1), this approach only works up to base 36 (for division by 36) as parseint only works for alphanumeric text, but in the 0.3 prerelease (based on the forio.com online REPL), it will work up to 62.

Note that the ",2" at the end is necessary to handle numbers less than 3 (or equivalent) in magnitude, as otherwise chop(base(3,n)) will result in either an empty string (for non-negative values) or "-" (for negative values).

# Answer
> 1 votes
# Jelly, 5 bytes

```
b3Ṗḅ3

```

Try it online!

Explanation:

```
 b3Ṗḅ3 Main link. Arguments: z
⁸      (implicit) z
  3    3
 b     Convert x to base y
   Ṗ   Trim last element off x
     3 3
    ḅ  Convert x from base y

```

# Answer
> 1 votes
## APL, 11

```
3⊥¯1↓3⊥⍣¯1⊢656
218

```

I'm converting to base 3 and back, removing the last number in the process. Try it on tryapl.org

# Answer
> 1 votes
# Python 3, ~~31~~ ~~38~~ 29 chars

```
print(eval(input()+"%c3"%47))

```

Edited to add a print statement.

Edited to avoid use of `int` call.

Kind of cheating. Eval will evaluate and return any operations passed as a string as if it were code. chr() converts an int to the character with that ASCII value, and 47=/. Pass in the / with standard string formatting.

# Answer
> 1 votes
## Clojure, ~~74~~ 57 bytes

Improved upon an earlier answer, I'm not sure if I should post this as my own answer or just comment on the original. But this is significantly different way of generating the sequence `[0 0 0 1 1 1 2 2 2 ...]`.

```
#(let[r(nth(flatten(for[i(range)][i i i]))(Math/abs %))](if(> % 0)r(- r)))

```

**Edit** after 1.5 years :D

```
#((if(> % 0)+ -)(nth(for[i(range)j[i i i]]j)(max(- %)%)))

```

# Answer
> 1 votes
# Aceto, 6 bytes

```
ri3:ip

```

```
r grabs input
i converts to integer
3 pushes 3 on the stack
: does float division
i converts to integer
p prints it
```

Try it online!

# Answer
> 1 votes
# , 19 bytes

```
mean(c(scan(),0,0))

```

Try it online!

Saw this method above in another language, and easily implemented it in R. And it gives precise answers. Works for positive and negative inputs.

# , 18 bytes

```
gl(x<-scan(),3)[x]

```

Slightly shorter solution that only works for positive numbers and performs "actual" integer division.

Try it online!

# Answer
> 1 votes
# Perl 6, 19 bytes

```
{Rat.new($_,3).Int}

```

A rational number in Perl 6 is literally defined as a numerator over a denominator. So passing it 7 creates the fraction <sup>7</sup>/<sub>3</sub> . That fraction is then coerced to an Int. This should work for all ℤ .

Try it online!

# Answer
> 1 votes
# PowerShell, ~~82~~ 74 bytes

<sup>-8 bytes thanks to mazzy</sup>

```
param($n)'-'[$n-ge0]+(-join(0..$n|?{$_}|%{1})-replace111,0-replace1|% Le*)

```

Try it online!

Bug-fix of Joseph Alcorn's answer to handle negatives correctly.

83 bytes to have 0 instead of -0

# Answer
> 0 votes
32 characters in Burlesque:

```
0\/r@{1\/.-<-2\/.-<-}{L[1.>}w!-]

```

assuming the number to divide is already on the stack. (see here in action).

How does it work? It generates a list of numbers 0..n and then removes one from the left and two from the right until only one number is left. Of course this method only works with numbers that are divisible by 3.

# Answer
> 0 votes
Perl using an eval to compute a string version of x/3.

Perl 5.8 Version

```
print eval join' ','int',$ARGV[0],map{chr}47,51

```

Perl 5.10 Version

```
say print eval join' ','int',$ARGV[0],map{chr}47,51

```

# Answer
> 0 votes
**perl 23**

```
$_=()=(1x$_)=~/(111)/g

```

usage:

```
> echo 1e4|perl -pe'$_=()=(1x$_)=~/(111)/g'
3333

```

Doesn't work with negatives.

# Answer
> 0 votes
## Mathematica (assorted)

Dividing 9 by 3 (but should work for arbitray input). The second version outputs just the number, while the first will offer additional braces (not sure about what is deemed correct, pick your count):

```
9Inverse[{{3}}]              (*15*)
9Inverse[{{3}}][[1,1]]       (*22*)

LinearSolve[{{3}},{9}]       (*22*)
LinearSolve[{{3}},{9}][[1]]  (*27*)

```

# Answer
> 0 votes
# Hexagony, 28 (Non-competing, only unsigned)

```
?$\<@'\.|!"1.(|{'&.{&.1\()\$

```

Try It Online!

Haven't got any Bitwise operators, so either can't join (like BF) or break the rules with increments and decrements. I chose the latter as I ...

...just want to share the facts that a hexagon is a polygon with 6 sides, and the number 6 has a factor 3. This is an "advantage" to Hexagons so I hope this will be interesting.

## Expanded version

```
   ? $ \ <
  @ ' \ . |
 ! " 1 . ( |
{ ' & . { & .
 1 \ ( ) \ $
  . . . . .
   . . . .

```

`?` gets the input, and `$` skips a mirror then we hit `<` the branch.

If the number is `<=0` it goes to the corner then to `{!@` which prints the "counter" (explained below) and ends the program.

(Else) If it is `>0`,

1. decrement it and increase the counter by 1 (located relatively at `{` as left neighbour and goes back with `"`).
2. Step back to the right and copy.
3. Step back to the right and copy again.
4. Goes back to the branch after a few reflections.

Anyone who wants to understand how this ends with graphics? I hope there is someone who wants to know more about Hexagony and know why keep stepping back to the right will in turn accumulates the counter. :P

I can't use the operators `+-*/%`. Can I use `:`? (The integer division) Obviously not - I'll be breaking the rules. Sadly I am already breaking the rules with increments and decrements. So I imposed myself to an unintended rule - not using `/` as an operator for reflection :) Whole program is `+-*/%`-free. May need a side length 5 hexagon to make one that can take care of the negatives...

Oh I just love hexagons.

Hexagon Edition, also 28, another way to get back into the loop.

```
?$|<@'\H|!"EX(|{'AG{&|O&N)\$

```

# Answer
> 0 votes
## Python 2, 16 bytes (Joke Answer)

```
print input()//3

```

`//` is not the same as `/`, the division operator. `//`, a token in and of itself, is the floor-division operator. Example: `4.5 // 2 == 2`. Note that this answer exploits a loophole in the question, and can be considered a joke. However, it is within the technical rules because the question says you cannot use the `/` **operator**. Although this answer uses the character "/", it never uses it as an operator.

# Answer
> 0 votes
# Python 3, 61 bytes

```
from numpy import*;f=lambda x:int(base_repr(x,base=3)[:-1],3)

```

This doesn't win, but I think it's a clever method that hasn't been used in the other Python entries, so I'm posting it here.

# Answer
> 0 votes
# Octave/MATLAB, 7 bytes

```
@(x)3\x

```

Try it online!

I'm not entirely sure whether or not this would count as cheating. It's not using one of the specifically listed operators (+-%/\*). MATLAB has a right divide operator which divides a number on the right by a number on the left.

I'll delete this answer if the consensus that it is cheating.

# Answer
> 0 votes
# Ruby, 21 bytes

```
->n{3.step(n,3).size}

```

Try it online!

# Answer
> 0 votes
# JavaScript (bitwise), 92 bytes

Because this is interview question, I assume they expected to see implementation of division using bitwise operations, not tricks with strings. So here it is. Works for negative values as well.

```
f=(a,b)=>b?f(a^b,(a&b)<<1):a
x=prompt(s=0)
while(y=x>>2)s=f(s,y),x=f(x&3,y)
alert(f(s,x==3))

```

# Answer
> 0 votes
# Python 3, 29 chars

`eval(str(x)+chr(47)*2+str(3))`

first golf, feels cheaty to me but here goes!

other one for 44:

`import numpy;print(int(numpy.mean([x,0,0])))`

# Answer
> 0 votes
# PHP, 66 bytes

```
<?='-'[$argn<=>0].intval(substr(base_convert($argn,10,3),0,-1),3);

```

Try it online!

Divides by lobbing off the least significant digit in the base 3 representation of the original number. The result is truncated (`10/3 = 3`), works with negative numbers and uses the PHP spaceship operator.

# Answer
> 0 votes
# ReRegex, 22 bytes

```
a(_*)\1\1_*/$1/a#input

```

Takes IO in the form of unary `_`s via STDIN.

Simple program, matches three chunks of \_'s as greedily as possible, and dumps out the first group. Remaining \_'s are also matched away.

Try it online!

# Answer
> -1 votes
# Scheme, 95 110 bytes

```
(define (h n)
  (length
   (let l ((a (iota n)))
     (if (> (length a) 2)
         (cons 1 (l (cdddr a)))
         '()))))

```

My original attempt using base conversion:

```
(define (g n)
  (string->number
   (list->string
    (reverse
     (cdr
      (reverse
       (string->list
        (number->string n 3))))))
   3))

```

I can't think of a better way of removing the last character from the string.

---
Tags: code-golf, math, restricted-source, division
---