title: C without the braces

text:
# Question
Title: C without the braces
My challenge is language-specific, but needs a lot of creativity: write a valid C program with only one pair of braces `{}` and none of the keywords `if`, `for`, `while` (all checked after preprocessing, and after substituting trigraphs). I'm looking for preprocessor abuse (but other methods are also welcome) to define a new pseudo-language which supports at least `if`/`else`, then use that language to do something cool.

That's pretty easy, and I'll just score this by upvotes since any scoring would be rather arbitrary, but here are some things which would be impressive:

* function calls (also arguments, return values);
* `else if`;
* `switch`/`case` (also `default`, fall-through);
* `for` or `while` (super-impressive. Also `break`, `continue`);
* having only one semicolon `;` (This one makes the challenge a bit different);
* an interesting program;
* full portability (portable in practice is good, portable in theory is even better).

This isn't about obfuscation. The preprocessor statements will probably be a bit hairy, but the actual code should be very easy to follow.

`goto` is allowed, but I believe it won't help much.

# Answer
> 6 votes
Doesn't seem too hard....

```
#include <stdio.h>

int main(void) {
  printf("I only used one pair of braces!\n");
  printf("This is easy...\n");
  printf("Lalalalala\n");
  getchar();
  return 0;
}

```

> having only one semicolon `;` (This one makes the challenge a bit different);

Oh, also easy:

```
int main(void) {
  return 0;
}

```

> `else if`;

How about `goto` and ternary operator abuse?

```
#include <stdio.h>

int main(void) {
  int testNum = 5;
  void *whichSection = testNum < 0 ? &&ifSection :
                       (testNum == 0 ? &&elseIfSection : &&elseSection);
  goto *whichSection;
  ifSection:
    printf("Number is negative\n");
    goto end;
  elseIfSection:
    printf("Number is zero\n");
    goto end;
  elseSection:
    printf("Number is positive and nonzero\n");
    goto end;
  end:
    return 0;
}

```

> `switch/case` *(kinda)* (also `default` *(kinda)*, fall-through *(yes)*)
>
> `for` *(no)* or `while` *(no)* (super-impressive. Also `break` *(yes)*, `continue` *(no)*);

My above solution is a bit like that - the `goto` is `break`, the `elseSection` is `default`, fall-through works, etc.

> full portability (portable in practice is good, portable in theory is even better).

All of my solutions have this.

---

*we code golfers are infamous for bending the rules :D*

# Answer
> 5 votes
## No braces

Doesn't answer the question, but does answer its title - C without braces

```
main=195;

```

Works on x86 (32bit and 64bit). Does nothing exciting, but starts and terminates without error.

# Answer
> 4 votes
We can simulate a conditional branch in this manner:

```
int condition = /* insert some condition here, like a == b */ ;

void* if_branch[2];
if_branch[1] = &&ifcode;
if_branch[0] = &&elsecode;

goto if_branch[!!condition];

ifcode:
    /* code if (condition) is met */
    goto afterif;
elsecode:
    /* code if (condition) is not met */
afterif:

```

While convoluted, this shows that you can implement conditional branching without using if statements, ternary statements, or any other form of abuse other than goto pointers.

With conditional branching and goto (and all that other good stuff that doesn't require braces like addition, subtraction, etc.), you can build a machine language, and thereby implement all that other stuff that requires braces or "implied" braces, and could (theoretically, anyway) create any C program in this form without using more than one set of braces.

---
Tags: code-challenge, c
---


title: Generate a right triangle

text:
# Question
Title: Generate a right triangle
In this challenge, you must take two numbers (separated by a space) as input and output an ASCII right triangle, made up of `x`s.

The first number will be the width and height of the triangle you should output. The second number will be which corner the right angle will be in. The corners are numbered 1 to 4, starting in the top left and going in English reading order:

```
1    2

3    4

```

For example (inputs and their respective triangle outputs):

```
INPUT | 3 1 | 3 2 | 3 3 | 3 4
------+-----+-----+-----+----
 OUT- | xxx | xxx | x   |   x
 PUT  | xx  |  xx | xx  |  xx
      | x   |   x | xxx | xxx

```

Your program's output must match these examples exactly for their respective inputs.

The input will always be valid: the first number will be an integer ≥1, and the second number will be 1, 2, 3, or 4.

This is ; shortest code (in character count) wins.

# Answer
## APL (30)

```
{' x'[1+(⍎⍵⌷'⌽+⍉⊖')≤/¨⍳2⍴⍺]}/⎕

```

Explanation:

* `{`...`}/⎕`: reduce given function over the input (so if the input has 2 numbers, just calls the function with those two numbers,  being the left number and  the right number)
* `≤/¨⍳2⍴⍺`: Make an -by- coordinate matrix and set those positions where the X coordinate is not greater than the Y coordinate, giving a bitfield.
* `(⍎⍵⌷'⌽+⍉⊖')`: select a transformation function given by  to put the triangle right-side-up.
* `' x'[1+`...`]`: add one to the bitfield, and use the result as an index into the string `' x'`, so putting space for 0 and `x` for 1.
> 9 votes

# Answer
## Ruby, ~~116~~ ~~115~~ ~~109~~ 96

I shall start with my own solution.

```
i=gets.split
s=i[0].to_i
(i[1]<?3?s.downto(1):1..s).map{|x|t=?x*x
puts /2|4/=~i[1]?t.rjust(s):t}

```

I just know that I'll get beat by a 30 character GolfScript solution almost instantly :P

Thanks to minitech for shaving off 19 characters (wow)!
> 6 votes

# Answer
## GolfScript (34 33 chars)

```
~\:^,{)' x'^*$>^<0(2$?%}%\(2&(%n*

```

It's a shame that the corners aren't numbered in rotation, because that would allow a more elegant approach of building one array and then rotating it `n` times:

```
~\:^,{)' x'^*$>^<}%{-1%zip}@)*n*

```
> 4 votes

# Answer
## C# - 195

```
using System;class P{static void Main(string[]a){int G=int.Parse(
a[0]),O=int.Parse(a[1]),L=O<3?0:G+1,F=O<3?-G:1;G=O%2>0?-G:G;for(;
F<L;F++)Console.Write("{0,"+G+"}\n","".PadRight(F<0?-F:F,'x'));}}

```

Formatted:

```
using System;
class P
{
    static void Main(string[] a)
    {
        int G = int.Parse(a[0]),
            O = int.Parse(a[1]),
            L = O < 3 ? 0 : G + 1,
            F = O < 3 ? -G : 1;

        G = O % 2 > 0 ? -G : G;

        for(; F < L; F++)
            Console.Write("{0," + G + "}\n", "".PadRight(F < 0 ? -F : F, 'x'));
    }
}

```
> 3 votes

# Answer
# Mathematica 122 (104?)

```
g@s_ := ({w, p} = ToExpression@StringSplit@s;
   Array[If[Switch[p, 1, # <= (w + 1 - #2), 2, # <= #2, 3, # >= #2, 4, # > (w - #2)],
   "X", ""] &, {w, w}]) // Grid

```

---

```
GraphicsGrid[{{g["12 1"], g["12 3"]}}]

```

---

Under a liberal interpretation of "output", the following (104 chars) will work.

```
f@s_ := ({w, p} = ToExpression@StringSplit@s;
  Graphics[Polygon@Delete[{{w, 0}, {0, 0}, {w, w}, {0, w}}, p], Axes -> True])

f["50 4"]

```

---

If input in the form of a list were permitted, the following (75 chars) would suffice:

```
f[{w_, p_}] :=
 Graphics[Polygon@Delete[{{w, 0}, {0, 0}, {w, w}, {0, w}}, p], Axes -> True]

```

---
> 2 votes

# Answer
# Golfscript, ~~39 36~~ 35 characters

```
~\:y,{' '*'x'y*+y<0~2$?%}%-1@2>?%n*

```

live demo: http://golfscript.apphb.com/?c=OyczIDInCn5cOnkseycgJyoneCd5Kit5PC0xIDIkPyV9JS0xQDI%2BPyVuKgo%3D

too bad it's not 30 characters as requested
> 2 votes

# Answer
## J, 59 55 42 38 37 36 characters

If it's permitted to have the input at the end of the program:

```
(|:@|.@]^:([:|[+_7*2<[)[:[\'x'$~])~/

```

If not (for an extra 3 characters):

```
t=.(|:@|.@]^:([:|[+_7*2<[)[:[\'x'$~])~/

```

Usage:

```
   (|:@|.@]^:([:|[+_7*2<[)[:[\'x'$~])~/3 4
  x
 xx
xxx

```

or

```
   t 3 4
  x
 xx
xxx

```

I think this could be a fair bit shorter since most of the characters are brackets and caps to keep it in an implicit style.

**Edit**
Using a gerund and the agenda verb has chopped off a few characters, but there's still too many caps in there for my liking.

**Edit 2**
That's a bit more like it. Dumping the agenda for a list of how many rotations are required gets rid of most of the extra brackets and a few caps.

**Edit 3**
Got rid of the last extraneous cap and a pair of brackets in the process. Need to find a cheaper way of encoding the number of rotations required.

**Edit 4** Use prefix instead of suffix to chop off a character. Enables a different way of creating the list which doesn't save any characters. Bugger.

**Edit 5**
Using a formula to chop off another character. Still feel this bit could be shorter.
> 2 votes

# Answer
Python 106 Characters

```
w,d=map(int,raw_input().split())
for e in range(1,w+1)[::d/3*2-1]:print('%'+'-+'[d%2]+str(w)+'s')%('*'*e)

```
> 1 votes

# Answer
## Python 3, 91

Based on Abhijit's answer.

Modified the creation of the output string to avoid the sum of strings and the ugly `1`s in the `range`. Python 3 gets rid of the `raw_` in `raw_input`, but makes necessary to use `//` for integer divison and to add parantheses for `print`, so that saves only one character.

```
w,d=map(int,input().split())
for e in range(w)[::d//3*2-1]:print('%*s'%(w-d%2*2*w,'x'*-~e))

```
> 1 votes

# Answer
# Kitten, 140

```
def s{><replicate}
getLine{' 'neChar}span{readInt fromSome}toBoth->{w n}
w 0 if(n 2>){><}..
{<>w>< -{'X's}{' 's}both if(n 2%0=){><}cat say}each

```

Ungolfed:

```
getLine
{' ' neChar} span
{readInt fromSome} toBoth
->{ width corner }

width 0
if (corner 2 >):
  swap
..

{ ->index
  'X' index replicate
  ' ' (width index -) replicate
  if (corner 2 % 0 =):
    swap
  cat say
} each

```

Evidence that I need to implement overloading and flesh out the standard library.
> 0 votes

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


# Question
Title: Create sets with a Goldbach-like property
Goldbach's conjecture states that every even number \> 4 is the sum of two prime numbers. Although this conjecture is not yet proven, similar results have been proven for other series of numbers. For example, every even number can be written as the sum of two practical numbers.

# The Challenge

Given a number N, return a set of positive integers such that every even number in the interval \[4,N\] can be written as the sum of two numbers in the set. Furthermore, the set generated must contain as few elements as possible, otherwise this challenge would be trivial.

Shortest answer wins.

# Detailed Example

For N=24, one possible output is {2,4,8,10,12}. This is because it contains the fewest number of elements possible (5). Also, every even number {4,6,8,... 24} can be written as the sum of exactly two of the members of the set.

```
4=2+2
6=2+4
...
12=8+4
14=10+4
...
24=12+12

```

# Examples

Here are some examples. There may be many valid outputs for each input, but only a few are listed.

```
4:{2}
6:{2,4} or {1,3}
9:{2,4}  #pay attention to how the odd number is handled
10:{2,4,6} or {2,3,5}
12:{2,4,6}
24:{2,4,8,10,12}
26:{1,3,7,11,13}

```

# Answer
> 4 votes
## GolfScript (53 chars)

```
~2/),3>[2][1 3]]({2*:x;{:S{x<},{x\-S+.&}/}%}/{,}$0=n*

```

A major speed optimisation results from a bit of duplicate-trimming, at a cost of 3 chars:

```
~2/),3>[2][1 3]]({2*:x;{:S{x<},{x\-S+.&$}/}%.&}/{,}$0=n*

```

---

NB Let `f(2n)` be the size of the optimal set for `[4..2n]`. Then `f(2n) <= f(2n+2) <= f(2n) + 1`. The first inequality is obvious from the definition; the second is easily seen by taking any optimal set `S_{2n}` for `[4..2n]` and taking the union with `{n+1}`, or indeed with `{2n+2-x}` for any `x in S_{2n}`.

This suggests a greedy algorithm, which the first revision of this answer implements. However, that greedy algorithm turns out to be incorrect. The unique optimal set for `[4..20]` is `{2,4,8,10}`, which is not a subset of either of the two optimal sets for `[4..26]`: `{1,3,7,11,13}` and `{2,4,8,12,14}`.

My current solution assumes that every optimal set will contain only odd numbers or only even numbers. I haven't proven this, but given that `odd + even = odd` a set which mixes parities is wasting possible pairs.

# Answer
> 3 votes
# J block, 106 characters

```
f=.3 :0
n=.0
while.1
do.for_z.>,{n#<>:i.y
do.if.0=$(+:2+i.<:<.-:y)-.+/~z
do.z
return.end.end.n=.>:n
end.
)

```

As usual for J programs, very memory hungry. The algorithm is as simple as can be: for each length n, for each combination z of n values, if that combination covers the whole set, return that combination.

# Ruby, ~~116~~ 112 characters

```
f=->x{0.upto(x){|n|(1..x).to_a.combination(n){|z|return z if
[]==4.step(x,2).to_a-z.flat_map{|i|z.map{|j|i+j}}}}}

```

(whitespace insignificant)

Ruby version of the algorithm, built-in deduplication, much more memory-efficient due to the use of enumerators in place of arrays (though J seems to optimise this somewhat), surprisingly not much larger than the J version.

results:

```
 4-5 :[2]
 6-9 :[2, 4]
10-13:[2, 4, 6]
14-21:[2, 4, 8, 10]
22-29:[2, 4, 8, 12, 14]
30-39:[2, 4, 8, 12, 16, 18]
40-45:[2, 4, 6, 12, 18, 20, 22]

```

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


# Question
Title: Find a set of 10 numbers such that all pairs have a different GCF
The set of ten numbers below:

```
223092870
17237308840522
1075474925835771
12574206406402195
79458974087499419
265057843710517649
466012798920390527
926434345611831877
1390237791335182649
2336970054109245767

```

has the property that no two pairs of numbers have the same greatest common factor. (In this case, the greatest common factor of each pair of numbers is actually a distinct prime.)

Your task is to find the set of 10 positive integers with the smallest sum that satisfy this property.

For reference, the sum of the above ten numbers is 5 477 838 726 638 839 246 (≈5.48×1018).

# Answer
## Sum: 11835

```
[1920, 1792, 1440, 1344, 1280, 1080, 1008, 810, 756, 405]

```

To verify, a table of the *gcd* values for each pair:

```
     | 1920 | 1792 | 1440 | 1344 | 1280 | 1080 | 1008 |  810 |  756
-----+------+------+------+------+------+------+------+------+-----
 405 |   15 |    1 |   45 |    3 |    5 |  135 |    9 |  405 |   27
 756 |   12 |   28 |   36 |   84 |    4 |  108 |  252 |   54 |
 810 |   30 |    2 |   90 |    6 |   10 |  270 |   18 |
1008 |   48 |  112 |  144 |  336 |   16 |   72 |
1080 |  120 |    8 |  360 |   24 |   40 |
1280 |  640 |  256 |  160 |   64 |
1344 |  192 |  448 |   96 |
1440 |  480 |   32 |
1792 |  128 |

```

---

### Implementation Details

**Update:** Massive performance gain c/o @PeterTaylor, as is so often the case.

* For a set *S* of length *n* matching the problem description, each element of *S* must have at least *n-1* divisors (including *1* and the value itself), as each must participate in exactly *n-1* unique *gcd*. Only values with this property are considered.
* The algorithm for the number of divisors takes the following form:
If *i* is a positive integer with the prime factorization *p0e0·p1e1…pnen*, then the number of divisors of *i* is equal to *(e0+1)·(e1+1)…(en+1)*. When counting divisors, only primes of the set *\[2, 3, 5, 7\]* are used; i.e. only those divisors which are *7-smooth* are counted.
* The search algorithm begins with the largest value of the set, and then searches recursively for each next smaller value. When the current search space has been exhausted, the next larger value with enough divisors is added to the list.
**Note:** while this is guaranteed to find the set with the smallest maximum value, it is not necessarily the optimal solution to this problem. A counter-example for *n=6*:
*\[120, 112, 90, 84, 80, 45\]* (*531*) vs. *\[162, 108, 81, 72, 48, 16\]* (*487*).
* The memoization of the *gcd* function results in a significant performance gain. By the time the third or fourth term is reached, most of the *gcd*s have already been calculated, and need only to be looked up. Additionally, the first iteration is performed outside of the *gcd* function itself, which increases look-up collision.
* `for ... else` is something of a Python oddity. The `else` block will only be evaluated if the `for` loop terminates properly, i.e. not by `break`. I use this for short-circuiting upon duplicate *gcd*s.
* The length of the set, *n*, is provided as input via `stdin`.

---

### Implementation

```
from time import time

num_vals = input()

def memoize(func):
  class memodict(dict):
    def __call__(self, *args):
      return self[args]
    def __missing__(self, key):
      ret = self[key] = func(*key)
      return ret
  return memodict()

@memoize
def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

def divisors(n):
  divs = 1
  for i in 2,3,5,7:
    exp = 1
    while n%i == 0:
      n /= i
      exp += 1
    divs *= exp
  return divs

def next_val(n):
  while True:
    n += 1
    d = divisors(n)
    if d >= num_vals-1: return n

vals = []

def f(n, end, nums, factors):
  if n<1:
    return nums
  index = n-1
  for i in vals[n-1:end]:
    index += 1
    new_factors = set()
    for j in nums:
      v = gcd(i, j%i)
      if v in factors or v in new_factors:
        break
      new_factors.add(v)
    else:
      ret = f(n-1, index, nums + [i], factors | new_factors)
      if ret: return ret

def g(n):
  global vals
  val = 0
  while len(vals) < n:
    val = next_val(val)
    vals += [val]
  index = n-1
  while True:
    ret = f(n-1, index, [val], set())
    if ret: return ret
    val = next_val(val)
    vals += [val]
    index += 1

t1 = time()
v = g(num_vals)
print sum(v), v
print time() - t1

```

---

Solutions and approximate runtime for *n* ∈ \[2, 10\]:

```
3 [2, 1]
0.00s

11 [6, 3, 2]
0.00s

43 [18, 12, 9, 4]
0.00s

149 [54, 36, 27, 24, 8]
0.05s

531 [120, 112, 90, 84, 80, 45]
0.07s

1143 [240, 224, 180, 168, 160, 126, 45]
0.34s

2601 [480, 448, 360, 336, 320, 270, 252, 135]
2.32s

5445 [960, 896, 720, 672, 640, 540, 504, 378, 135]
2m 2.4s

11835 [1920, 1792, 1440, 1344, 1280, 1080, 1008, 810, 756, 405]
36m 6s

```
> 8 votes

# Answer
## Sum: 58025

(ruby)

```
(0..9).map{|i|(2**i)*(3**(9-i))}

```

Gives

```
[19683, 13122, 8748, 5832, 3888, 2592, 1728, 1152, 768, 512]

```
> 9 votes

# Answer
# Sum: 132251618166478572 (≈1.32×1017)

As a reference last-place answer, I will post the Python code I used to generate the initial set of numbers in the question:

```
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
          67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
          139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197]

numbers = [1] * 10

primefactor = 0

for a in range(10):
    for b in range(a+1, 10):
        numbers[a] *= primes[primefactor]
        numbers[b] *= primes[primefactor]
        primefactor = primefactor + 1

# can't use "sum" because it produces weird values.
numbertotal = 0
for i in numbers:
    numbertotal += i

print numbers, numbertotal

```

Essentially what this does is take every prime number from 2 to 197 (the first 10C2 = 45 primes), and multiplies them to a unique pair of numbers. That way, any pair of numbers will only have that one prime that was assigned to it as a common factor.

This was done mostly as a proof that there do exist sets of numbers with the property required in the question - as you can see, the value it generated is far from optimal.

Modifying this code to shuffle the primes around randomly before multiplying them results in smaller numbers being created. With multiple trials, I found the following set of numbers:

```
1268193027813141
2224904691135063
4714631150921614
7005966291691742
9288794198034215
9315429894689005
12630588322608113
13006064536029667
23545741081119313
49251304972436699

```

whose sum is 132251618166478572, as above.
> 1 votes

---
Tags: code-challenge
---


title: Manage a pie shop!

text:
# Question
Title: Manage a pie shop!
# Summary

Code golf is good. Pie is good. When you put the two together, only good stuff can happen.

# Specifications

In this challenge you will manage a pie shop. The user will be able to input five different commands: `list`, `count`, `buy`, `sell`, and `exit`. Here are the specifications for each:

* `list`

+ Print a list of all the pies owned, and how many. Separate with `|` and pad with a space on either side. `|`s must be aligned. Pie amount may be negative (that means you owe pie to someone `:(`). For example:

    ```
    | apple     | 500 |
    | blueberry | 2   |
    | cherry    | -30 |

    ```
* `count [type]`

+ Print how many `{{type}}` pies there are. Print "There is no `{{type}}` pie!" if there is none. `{{type}}` will always match the regex `\w+` (i.e, it will always be a single word). For example, if I had the amount of pies shown in the above example list, then

    ```
    > count apple
    500
    > count peach
    There is no peach pie!

    ```
* `buy [n] [type]`

+ Add `{{n}}` to the count of `{{type}}` pie, and print it. Create `{{type}}` pie if it does not exist. `{{n}}` will always match the regex `[0-9]+` (i.e, it will always be a number). Here's another example (with the same pie inventory as the previous examples):

    ```
    > count blueberry
    2
    > buy 8 blueberry
    10

    ```
* `sell [n] [type]`

+ Subtract `{{n}}` from the count of `{{type}}` pie, and print it. Create `{{type}}` pie if it does not exist. Pie can be negative (oh no, that would mean you owe someone pie!).

    ```
    > sell 15 blueberry
    -5
    > buy 5 blueberry
    0

    ```
* `exit`

+ Print "The pie store has closed!" and exit the program.

    ```
    > exit
    The pie store has closed!

    ```

# Further clarifications

* If a non-existing function is called (the first word), then print "That's not a valid command."
* If an existing function is called with invalid arguments (the words after the first word), how your program behaves doesn't matter. "Invalid arguments" includes too many arguments, too little arguments, `{{n}}` not being a number, etc.
* Pie is good.
* Your input must be distinguished from your output. If you are running the program on the command line/terminal/shell/other text-based thing, you must prefix input with "`> "` (a "greater than" sign and a space) or some other shell input prefix thing.
* Pie is good.
* If all of these clarifications are not good enough, here's some sample output:

```
> list
> buy 10 apple
10
> sell 10 blueberry
-10
> list
| apple     | 10  |
| blueberry | -10 |
> count apple
10
> count peach
There is no peach pie!
> exit
The pie store has closed!

```
* If you buy/sell pie and the net count becomes `0`, you can **either** keep it in the `list` or not, and you can **either** return `0` or `There is no {{type}} pie!` when you `count` it.
* This is ; shortest code wins.
* Did I mention that pie is good?

# Answer
> 4 votes
### Ruby, ~~335~~ 330

```
h=Hash.new 0
loop{$><<"> "
puts case gets when/^list/
h.map{|x|?|+" %%%ds |"%h.flatten.map{|e|e.to_s.size}.max*2%x}when/^count (.*)/
h[$1]!=0?h[$1]:"There is no #{$1} pie!"when/^buy#{m=" (.*)"*2}/
h[$2]+=$1.to_i when/^sell#{m}/
h[$2]-=$1.to_i when/^exit/
puts"The pie store has closed!"
break else"That's not a valid command."end}

```

Some tricks here:

```
?|+" %%%ds |"%[*h].flatten.map{|e|e.to_s.size}.max*2%x

```

Doorknob's idea to use a formatter is taken a step further here, literally. First, the longest string in the hash among all keys and values is formatted using `" %%%ds |"` to produce a string like `" %6s |"`. Yep, no shrinkwrapping each column separately. There was never the requirement to. One size fits all. Then this string is duplicated and used as a formatting string for the two-element array containing the current row. Finally, the `+` near the start gets its word and prepends a single leading pipe. Oh, and `puts` has a nice handling of arrays.

Ruby has interpolation in regex literals. It's a tight save, but it does save a little.

Ruby requires semicolons after the `when` expression, but not before the keyword. This leads to a weird rendering artifact when the semicolon is replaced with a newline.

And, of course, perlism known as magic globals and automatic matching of regex literals against them.

Also, most statements including `case` are expressions.

# Answer
> 3 votes
# Ruby, ~~427~~ 384 characters

```
alias x puts
p={}
loop{
print'> '
case(u=gets.chop.split)[0]when'exit'
x'The pie store has closed!'
exit
when'list'
p.each{|k,v|printf"| %-#{p.keys.map(&:size).max}s | %-#{p.map{|e,a|a.to_s.size}.max}s |\n",k,v}
when'count'
x p[t=u[1]]||"There is no #{t} pie!"
when/sell|buy/
m=(u[0]<?s?1:-1)*u[1].to_i
if p[t=u[2]]
x p[t]+=m
else
x p[t]=m
end
else x"That's not a valid command."
end}

```

Thanks to Jan Dvorak of huge improvement from 427 to 384 (!)

# Answer
> 3 votes
# ~~Python~~ *Pie*-thon 437

I'm sure there is some slack on the second last line, but the requirement to align the bars for both the pie type and number is a doozy.

```
p,C,l={},"count",len
while 1:
 a=raw_input("> ").split();c=a.pop(0)
 if"exit"==c:print"The pie store has closed!";break
 if"sell"==c:a[0]=int(a[0])*-1
 if c in[C,"buy","sell"]:
  y=a[-1]
  if c!=C:p[y]=p.get(y,0)+int(a[0])
  print p.get(y,"There is no %s pie!"%y)
 elif"list"==c:
  for i in p:print"| %s | %s |"%(i.ljust(l(max(p.keys(),l))),str(p[i]).rjust(max([l(str(x)) for x in p.values()])))
 else:print"That's not a valid command."

```

As per Igby Largeman's comment the rules are unclear around what to do if there **was** a pie of a specific type, but there are `0` now. So I've interpreted it in my favour.

Sample output:

```
> buy 10 apple
10
> sell 1 blueberry
-1
> buy 1 keylime
1
> sell 3 apple
7
> buy 5 blueberry
4
> list
| keylime   | 1 |
| apple     | 7 |
| blueberry | 4 |
> sell 1 keylime
0
> count keylime
0

```

# Answer
> 3 votes
## C# - 571 568 559

Bringing up the rear as usual with the hopelessly verbose C#.

```
using C=System.Console;class Z{static void Main(){var P=new
System.Collections.Generic.Dictionary<string,int>();int i=0,n;a:C.Write
("> ");var I=C.ReadLine().Split(' ');var c=I[0];object s=c=="exit"?
"The pie store has closed!":"That's not a valid command.";if(c==
"count")try{s=P[c=I[1]];}catch{s="There is no "+c+" pie!";}if(c==
"buy"||c=="sell"){n=int.Parse(I[1]);n=c=="sell"?-n:n;try{n+=P[c=
I[2]];}catch{}s=P[c]=n;i=(n=c.Length)>i?n:i;}if(c=="list")foreach(
var p in P.Keys)C.Write("| {0,"+-i+"} | {1,11} |\n",p,P[p]);else C.
WriteLine(s);if(c!="exit")goto a;}}

```

I took some liberty with the rule about list output. To save some characters I hardcoded the width of the count column to the maximum width of an integer value. (The rules didn't say extra spaces weren't allowed.)

Formatted:

```
using C = System.Console;
class Z
{
    static void Main()
    {
        var P = new System.Collections.Generic.Dictionary<string, int>();
        int i = 0, n;
    a:
        C.Write("> ");
        var I = C.ReadLine().Split(' ');
        var c = I[0];
        object s = c == "exit" ? "The pie store has closed!"
                               : "That's not a valid command.";

        // allow Dictionary to throw exceptions; cheaper than using ContainsKey()
        if (c == "count")
            try { s = P[c = I[1]]; }
            catch { s = "There is no " + c + " pie!"; }

        if (c == "buy" || c == "sell")
        {
            n = int.Parse(I[1]);
            n = c == "sell" ? -n : n;

            try { n += P[c = I[2]]; }
            catch { }

            s = P[c] = n;
            i = (n = c.Length) > i ? n : i;
        }

        if (c == "list")
            foreach (var p in P.Keys)
                C.Write("| {0," + -i + "} | {1,11} |\n", p, P[p]);
        else
            C.WriteLine(s);

        if (c != "exit") goto a; // goto is cheaper than a loop
    }
}

```

# Answer
> 1 votes
# Java - ~~772~~ ~~751~~ ~~739~~ ~~713~~ ~~666~~ 619

I know it's not winning the contest, but just for fun!

```
import java.util.*;class a{static<T>void p(T p){System.out.print(p);}public static
 void main(String[]s){z:for(Map<String,Long>m=new HashMap();;){p("> ");s=new
 Scanner(System.in).nextLine().split(" ");switch(s[0]){case"list":for(Map.Entry
e:m.entrySet())System.out.printf("|%12s|%6s|\n",e.getKey(),e.getValue());break;
case"count":p(m.get(s[1])!=null?m.get(s[1]):"There is no "+s[1]+" pie!\n");break;
case"buy":case"sell":long r=(s[0].length()==3?1:-1)*new Long(s[1])+(m.get(s[2])!=null?
m.get(s[2]):0);p(r+"\n");m.put(s[2],r);break;case"exit":p("The pie store has
 closed!");break z;default:p("That's not a valid command.\n");}}}}

```

With line breaks and tabs:

```
import java.util.*;

class a{

    static<T>void p(T p){
        System.out.print(p);
    }

    public static void main(String[]s){
        z:for(Map<String,Long>m=new HashMap();;){
            p("\n> ");
            s=new Scanner(System.in).nextLine().split(" ");
            switch(s[0]){
            case"list":
                for(Map.Entry e:m.entrySet())
                    System.out.printf("|%12s|%6s|\n",e.getKey(),e.getValue());
                break;
            case"count":
                p(m.get(s[1])!=null?m.get(s[1]):"There is no "+s[1]+" pie!");
                break;
            case"buy":
            case"sell":
                long r=(s[0].length()==3?1:-1)*new Long(s[1])+(m.get(s[2])!=null?m.get(s[2]):0);
                p(r);
                m.put(s[2],r);
                break;
            case"exit":
                p("The pie store has closed!");
                break z;
            default:
                p("That's not a valid command.");
            }
        }
    }

}

```

# Answer
> 1 votes
## Python 3, 310

```
p={}
c=G=p.get
while c:
 l=("exit list buy count sell "+input("> ")).split();c=l.index(l[5]);*_,n=l
 if~-c%2*c:p[n]=(3-c)*int(l[6])+G(n,0)
 print(["The pie store has closed!","\n".join("| %*s | %9s |"%(max(map(len,p)),k,p[k])for k in p),G(n),G(n,"There is no %s pie!"%n),G(n),"That's not a valid command."][c])

```

---
Tags: code-golf
---


# Question
Title: Build a solver for the cow and chicken problem
The cow and chicken problem is a traditional problem for introducing young students to the concept of systems of equations. It goes as follows:

> A farmer raises cows and chickens on his farm. His animals have a total of 24 heads and 68 legs. How many cows and how many chickens does he have?

The numbers of heads `h` and legs `l` can vary, but the idea of the problem is the same. This problem can't be solved by plugging in a one-variable formula; both variables (the number of cows `k`, and the number of chickens `x`) will always be involved in each formula that you can derive directly.

That being said, for this version of the problem, there is a formula `k = l/2 - h` that you can readily use to obtain the solution of `10` cows and `14` chickens, so it's not *too* interesting.

Here's a slightly different problem, this time involving cows and chickens who can have a different number of heads and legs.

Your task is to build a program that takes the following inputs (all positive integers):

* hk, the number of heads a cow has.
* lk, the number of legs a cow has.
* hx, the number of heads a chicken has.
* lx, the number of legs a chicken has.
* h, the total number of heads.
* l, the total number of legs.

: and output `k` and `x`, how many cows and chickens the farmer has.

However, depending on the input given, the problem has several states of solvability:

1. There is a solution in the nonnegative integers. The input `1 4 1 2 24 68` (which is the problem above) has the solution `10 14`.
2. There is no solution in the nonnegative integers, but there is one in the nonnegative fractional numbers. The input `1 4 1 2 24 67` is an example of this, with a solution of `9.5 14.5`.
3. There is no solution in the nonnegative numbers, but one in the integers in general. The input `1 4 1 2 24 36` is an example of this, with a solution of `-6 30`.
4. There is no solution in either the nonnegative fractional numbers or the integers in general, but one in the real numbers in general. The input `1 4 1 2 24 97` is an example of this, with a solution of `24.5 -0.5`.
5. There is no solution at all. The input `2 4 1 2 24 68` is an example of this.
6. There are multiple solutions in the positive integers (and therefore infinitely many solutions in the real numbers). The input `2 4 1 2 24 48` is an example of this. If there is exactly one solution in the positive integers but infinitely many solutions in the real numbers (as is the case with the input `6 9 4 6 10 15` with a solution of `1 1`), your solution can treat it as a case of this state.

Your program, given the inputs, must first output which state of solvability the problem has. Only if the problem is in the *first* state of solvability should you output how many cows and chickens there are, as any other solution is considered an "invalid problem".

The shortest code to do all of the above in any language wins.

# Answer
> 1 votes
### GolfScript, 105 101 characters

```
{](=}+1360222640 6base%4/{~*@@*-}%.2=0<{{~)}%}*).{1${1$%0>}%~|2${0<}%~|.++.)p!{{/}+%p}*;;}{;~|!5+p}if

```

A first (and rather clumsy) approach using GolfScript.

The test cases (see online):

```
> 1 4 1 2 24 68
1
[10 14]

> 1 4 1 2 24 67
2

> 1 4 1 2 24 36
3

> 1 4 1 2 24 97
4

> 2 4 1 2 24 68
5

> 2 4 1 2 24 48
6

```

# Answer
> 2 votes
# Mathematica ~~359~~ 314

About 200 characters went into determining which condition applies.

```
f@{a_, b_, c_, d_, i_, l_} :=
 Module[{s, t, z = "invalid problem", y = IntegerQ},
  t@n_ := y@n \[And] (n > 0);
  p@n_ := n \[Element] Rationals \[And] n > 0;
  q@n_ := n \[Element] Reals;
  w = Flatten@Quiet@Solve[{d*x + b*k == l, c*x + a*k == i}, {k, x}];
  s = {k, x} /. w;
  Which[w == {}, {5, z},
   Length[w] != 2, {6, z},
   True, If[And @@ (t /@ s), {1, s},
    Which[
     And @@ (p /@ s), {2, z},
     And @@ (y /@ s), {3, z},
     And @@ (q /@ s), {4, z},
     3 == 3, {7, z}]]]]

f[{1, 4, 1, 2, 24, 68}]
f[{7, 14, 9, 6, 25, 18}]
f[{1, 4, 1, 2, 24, 67}]
f[{1, 4, 1, 2, 24, 36}]
f[{1, 4, 1, 2, 24, 97}]
f[{2, 4, 1, 2, 24, 68}]
f[{2, 4, 1, 2, 24, 48}]
f[{1, 4, 1, 2, -23, (3 + I)^2/(5 - I)}]
f[{6, 9, 4, 6, 10, 15}]

```

> {1, {10, 14}}
> {2, "invalid problem"}
> {2, "invalid problem"}
> {3, "invalid problem"}
> {4, "invalid problem"}
> {5, "invalid problem"}
> {6, "invalid problem"}
> {7, "invalid problem"}
> {6, "invalid problem"}

**How it works**

The equations `d*x+b*k==l`and `c*x+a*k==i` express the constraints in the general cow and chickens problem,where

> a is "the number of heads per cow"
> b is "the number of legs per cow"
> c is "the number of heads per chicken"
> d is "the number of legs per chicken"
> i is "the number of heads"
> l is "the number of legs"
> k is "the number of cows"
> x is "the number of chickens".

`Solve` returns the real - valued solutions, if any exist, for the cows and chickens, as a list of 2 substitution rules, e.g. `{k->10, x-> 14}`

If no solutions exist, an empty list is returned.

If the data cannot be processed, Solve will return a different number of elements.

The tests are performed in the following order.

* If there are 0 solutions, condition 5 is satisfied
* If the list of "solution"s has anything other than 2 elements, then condition 6 is satisfied .
* If there are 2 solutions, then

+ if function t yields True, the solution is a pair of non-negative integers, and condition 1 is satisfied.
    + if function p yields True, the solution is a pair of non negative rationals and condition 2 is satisfied.
    + if function q yields True, the solution is a pair of non negative rationals and condition 3 is satisfied.
    + if function y yields True, the solution is a pair of integers and condition 4 is satisfied.
    + Otherwise, condition 7 is satisfied.

**Minor Variant of f**

```
g@{a_, b_, c_, d_, i_, l_} :=
 Module[{s, t, z = "invalid problem", y = IntegerQ},
  t@n_ := y@n \[And] (n > 0);
  p@n_ := n \[Element] Rationals \[And] n > 0;
  q@n_ := n \[Element] Reals;
  w = Flatten@Quiet@Solve[{d*x + b*k == l, c*x + a*k == i}, {k, x}];
  s = {k, x} /. w;
  Which[w == {}, {5, z, w}, Length[w] != 2, {6, z, w}, True,
   If[And @@ (t /@ s), {1, s, w},
    Which[And @@ (p /@ s), {2, z, w}, And @@ (y /@ s), {3, z, w},
     And @@ (q /@ s), {4, z, w}, 3 == 3, {7, z, w}]]]]

```

`g` is f\` with the additional property that it returns the output of Solve.

```
g[{1, 4, 1, 2, 24, 68}]
g[{7, 14, 9, 6, 25, 18}]
g[{1, 4, 1, 2, 24, 67}]
g[{1, 4, 1, 2, 24, 36}]
g[{1, 4, 1, 2, 24, 97}]
g[{2, 4, 1, 2, 24, 68}]
g[{2, 4, 1, 2, 24, 48}]
g[{1, 4, 1, 2, -23, (3 + I)^2/(5 - I)}]
g[{6, 9, 4, 6, 10, 15}]

```

> {1, {10, 14}, {k -\> 10, x -\> 14}}
> {2, "invalid problem", {k -\> 1/7, x -\> 8/3}}
> {2, "invalid problem", {k -\> 19/2, x -\> 29/2}}
> {3, "invalid problem", {k -\> -6, x -\> 30}}
> {4, "invalid problem", {k -\> 49/2, x -\> -(1/2)}}
> {5, "invalid problem", {}}
> {6, "invalid problem", {x -\> 24 - 2 k}}
> {7, "invalid problem", {k -\> 615/26 + (19 I)/26, x -\> -(1213/26) - (19 I)/26}}
> {6, "invalid problem", {x -\> 5/2 - (3 k)/2}}

Problems falling under condition 6 have multiple solutions, as evidence by the equations. The problem that falls under condition 5 returns an empty set (no solutions).

Note: `element` and `and` are single characters in Mathematica.

# Answer
> 2 votes
## Python 2, 138

```
a,A,b,B,h,l=input()
d=a*B-b*A
k=B*h-b*l
c=a*l-A*h
if d:K=k/d;C=c/d;z=K>=0<=C;print[[3,[1,K,C]][z],4-2*z][k%d+c%d!=0]
else:print(0==c==k)+5

```

Expects comma seperated input. The inputs

```
1, 4, 1, 2, 24, 68
7, 14, 9, 6, 25, 18
1, 4, 1, 2, 24, 67
1, 4, 1, 2, 24, 36
1, 4, 1, 2, 24, 97
2, 4, 1, 2, 24, 68
2, 4, 1, 2, 24, 48

```

yield the (admittedly not very nicely formatted) answers

```
[1, 10, 14]
2
2
3
4
5
6

```

# Answer
> 0 votes
# J - 124 characters

(excluding the assignment) Reduced the "invalid problem reporting" clutter (154 -\> 124).

```
chico =: ((>:@],(#"1~-.@*))#.@(0&>,&(>./)(~:<.)) ::({&0 4 5@#))~@(({:%.}:)@; ::(":@(11-#@~.@;@:(%/&.>))))@(((0 2,:1 3);4 5)&({&.>;~))

```

tests:

```
t =: ,. 1 4 1 2 24 68;1 4 1 2 24 67;1 4 1 2 24 36 ;1 4 1 2 24 97;2 4 1 2 24 68;2 4 1 2 24 48
chico &.> t
NB. outputs:
+-----------------+
|1 10 14          |
+-----------------+
|2                |
+-----------------+
|3                |
+-----------------+
|4                |
+-----------------+
|5                |
+-----------------+
|6                |
+-----------------+

```

un-golfed version + comments

```
NB. Print case and the solution if the state is 0.
print  =: (>:@],(#"1~-.@*))

NB. 0 1 2 3 considering binary coding based on positivity and fractionality of
NB. all (>./) elements of the solution. If error caused by a string, then choose 4
NB. or 5 based on length of the string passed.
case   =: #.@(0&> ,&(>./) (~:<.)) :: ({&0 4 5@#)

NB. Solve, if error, determine whether multiple solutions exist, then output
NB. '10' else output '9' (just for having length 1 or 2 strings)
solve  =: ({:%.}:)@; ::(":@(11-#@~.@;@:(%/&.>)))

NB. Parse input list to obtain matrix and rhs of the system to solve.
format =: (((0 2,:1 3);4 5)&({&.>;~))

NB. Piece the bricks together:
chico_ng =: (print case)~ @ solve @ format

NB. testcases and solutions:
t=: (,.1 4 1 2 24 68;1 4 1 2 24 67;1 4 1 2 24 36;1 4 1 2 24 97;2 4 1 2 24 68;2 4 1 2 24 48)
sols =: ,. 1 10 14 ; (1$2) ; (1$3) ;(1$4) ;(1$5);(1$6)
(sols -: chico_ng each t) # 'fail','pass'
+----+
|pass|
+----+

```

# Answer
> 0 votes
# C - ~~181~~ 177 characters

```
a,b,c,d,e,f,g,j;main(){scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);g=b*c-a*d;a=b*e-a*f;b=c*f-d*e;j=g?2*(b*g<0||a*g<0)+(b%g&&a%g):b||a?4:5;putchar(j+49);j||printf(" %d %d",b/g,a/g);}

```

Just a rough sketch, I should be able to get it down to around 150 characters with some massage.

---
Tags: code-golf, arithmetic, puzzle-solver
---


title: Simultaneous equations

text:
# Question
Title: Simultaneous equations
With equations that have more than one unknown, simultaneous equations can be used in solving for them. This challenge will only deal with linear equations with two unknowns, to make things as elementary as possible.

The program should take two lines of input from stdin, each containing a linear equation with two unknowns (`x` and `y`). Output should be in the form `x=<x-value>, y=<y-value>`, where the angled bracketed text should be replaced by the appropriate value. Non-integer values can be outputted in either decimal point form rounded to at least 3 decimal places or until the fraction terminates (eg. `1/2` would be `0.5` not `0.500`), or simplest (improper, not mixed) fraction form (as all results will be rational). If the equations are unsolvable (ie are parallel but not equivalent), output `Unsolvable`. If the equations are equivalent and would therefore have an infinite number of solutions, output `Degenerate`.

The use of external modules is not allowed. Also, any library functions that solve equations (this applies especially to Mathematica) are not allowed.

Each equation in the input will be in general form, with no whitespace. If a coefficent or the constant term is 0, the whole term will not appear, and if a coefficient is ±1, only the pronumeral will appear.

Test cases:

```
Input:                 Input:                 Input:                 Input:
7x+4y-8=0              4x+3y+32=0             x-y=0                  2x+5y-1=0
x-8y+1=0               x-4=0                  x-y+5=0                2x+5y-1=0
Output:                Output:                Output:                Output:
x=1, y=1/4 (or 0.25)   x=4, y=-16             Unsolvable             Degenerate

```

This is once again , so shortest code wins.

# Answer
## Python 3, 250

I reuse the code for parsing the input for each of the "coefficients" of x, y, and "=" by putting it into a string and multiplying it the right number of times.

For the "coefficient of =" case to work (absence means 0, not 1, like for x and y), the last "0" of the input has to be thrown away (and then magic takes over...). Makes heavy use of short circuiting in logic expressions, and of `False==0`.

Uses Python's feature of leaving off trailing zeros of floats (finding out if the solution is an integer is still necessary).

```
exec((("R=input()[:-1];"+"*_,R=I,*_=R.split(%r);%s=R!=I and int(I in'+-'and I+'1'or I);"*3)*2)%tuple("xXyY=Cxxyy=c"))
d,u,v=X*y-Y*x,C*y-c*Y,X*c-x*C
print(d and"x=%s, y=%s"%(u%d and-u/d or-u//d,v%d and-v/d or-v//d)or"UDnesgoelnvearbaltee"[u==v==0::2])

```
> 2 votes

# Answer
## Python 2 - 497

```
def i(x):return-1 if x=="-"else int(x)if x else 1
def g(a,b):return g(b,a%b) if b else a
r=raw_input
u=r()[:-2]
v=r()[:-2]
t=u==v
a=u.find("x")
a,u=0 if a<0 else i(u[:a]),u[a+1:]
b=u.find("y")
b,u=0 if b<0 else i(u[:b]),u[b+1:]
e=-i(u) if u else 0
c=v.find("x")
c,v=0 if c<0 else i(v[:c]),v[c+1:]
d=v.find("y")
d,v=0 if d<0 else i(v[:d]),v[d+1:]
f=-i(v) if v else 0
x,y,z=e*d-f*b,a*f-c*e,a*d-b*c
m,n=g(x,z),g(y,z)
print"Degenerate"if t else"x=%d/%d, y=%d/%d"%(x/m,z/m,y/n,z/n)if z else"Unsolvable"

```
> 0 votes

# Answer
## Python 2, 244 chars

```
import re
def P():e=re.sub(r'(\d)(x|y)',r'\1*\2',raw_input()[:-2]);x=y=0.;c=eval(e);x=1;a=eval(e)-c;x,y=y,x;return a,eval(e)-c,c
a,b,c=P()
d,e,f=P()
D=a*e-d*b
X=b*f-c*e
print'x=%g, y=%g'%(X/D,(c*d-a*f)/D)if D else'UDnesgoelnvearbaltee'[X==0::2]

```

Throws some `*` characters in the right place, then evaluates the LHS on various combinations of x,y in {0,1} to derive the coefficients. Then it does the standard determinant computations to find the solution.
> 0 votes

---
Tags: code-golf, math, arithmetic
---


title: Implement DES key expansion

text:
# Question
Title: Implement DES key expansion
I wanted to make a challenge to do the full DES encryption algorithm, but that may be a bit too involved to get a ton of participation. This challenge is to simply generate the 16 48-bit subkeys used to encrypt data:

The algorithm is described well enough on wikipedia, and all relevant shift tables and such data are on this page.

Your task is to write a program or function that accepts 64 bits of input, and outputs the 16 48-bit keys. I am not picky about input or output formats, but hex coded is fairly standard.

You can check your results against the examples on this page, or this page

Shortest code wins.

# Answer
## Perl - 384 314 chars

input is in decimal (from STDIN), output in binary. includes all necessary tables. feel free to improve anything

```
use Math'BaseConvert b10;
@_=sprintf("%064b",<>)=~/./g;
$s=b10 cG4xqQ8GMvUpZSqYtTAVVCZyBjrZs7FkNdowNTFBipcmG28UIKQKyfLYHWWjdq;
$s=~s/../$_[$&-1]/g;
map{
  $n=28-$_;
  $s=~s/(.{$_})(.{$n})(.{$_})(.+)/$2$1$4$3/;
  $_=b10"G._NqruyC5whI_KjAHzrS3ZgLTX7BzGp0.zML.AaubJCuwPtzPomq";
  s|..|($s=~/./g)[$&-1]|eg;
  say$_
}b10("3_AUuKOqD")=~/./g

```
> 3 votes

# Answer
## GolfScript (175 chars)

I assume input and output in MSB-first upper-case hex.

For want of good test cases, I don't guarantee that this implementation is correct. I've worked to a test case which I derived from Rivest's simple test for implementations of DES: given his test input of `9474B8E8C73BCA7D` I think that the expected output is

```
BE23F4265E76
63FD57CA5952
6DEDC3C5E33C
73E5BBF11EC8
FD8593D8923F
778A9F177EAC
3FB0963839F1
3E0CFEA3E837
41FFD1A34BCB
55FDE796B313
F3E5C3F70764
79C7A758ABCA
F1919F74F41D
3582F76B34EA
B758B6ACF92B
44FF4B3F4D29

```

To that caveat I must add another, which is that I use a lot of base conversion including some of strings with non-printable characters. As usual, I'll give the program in a couple of ASCII-safe formats. xxd output:

```
0000000: 312f 7b31 302c 2727 2a37 312c 3635 3e2b  1/{10,''*71,65>+
0000010: 3a5e 5c3f 3136 2b32 7b62 6173 657d 3a42  :^\?16+2{base}:B
0000020: 7e28 3b7e 7d25 607b 3d7d 2b5b 3536 5b5b  ~(;~}%`{=}+[56[[
0000030: 2d38 5d32 342a 372f 2e2b 2739 3939 1b37  -8]24*7/.+'999.7
0000040: 3717 275d 7a69 705b 5d2a 5b5d 2a7b 3124  7.']zip[]*[]*{1$
0000050: 2b7d 2f5d 2534 3932 3831 2032 427b 2129  +}/]%49281 2B{!)
0000060: 7b32 382f 7b28 2b7d 257e 2b7d 2a27 1d3c  {28/{(+}%~+}*'.<
0000070: f9df 2a9b 7079 2030 dea2 83df 3bca a82f  ..*.py 0....;../
0000080: 50ec 11f8 e55c 74d2 f104 b2ae 130e ac5c  P....\t........\
0000090: d627 27ff 3827 7b42 7d2f 7b31 243d 7d25  .''.8'{B}/{1$=}%
00000a0: 342f 7b32 425e 3d7d 256e 2b5c 7d2f 3b    4/{2B^=}%n+\}/;

```

Base-64 encoded:

```
MS97MTAsJycqNzEsNjU+KzpeXD8xNisye2Jhc2V9OkJ+KDt+fSVgez19K1s1NltbLThdMjQqNy8u
Kyc5OTkbNzcXJ116aXBbXSpbXSp7MSQrfS9dJTQ5MjgxIDJCeyEpezI4L3soK30lfit9KicdPPnf
KptweSAw3qKD3zvKqC9Q7BH45Vx00vEEsq4TDqxc1icn/zgne0J9L3sxJD19JTQvezJCXj19JW4r
XH0vOw==

```

And with the magic strings substituted with a printable (but longer) version using escape characters and some unnecessary line-breaks:

```
1/{10,''*71,65>+:^\?16+2{base}:B~(;~}%`{=}+
[56[[-8]24*7/.+'999\e77\027']zip[]*[]*{1$+}/]
%49281 2B{!){28/{(+}%~+}*
'\035<\371\337*\233py 0\336\242\203\337;\312\250/P\354\021\370\345\\t\322\361\004\262\256\023\016\254\\\326'
'\3778'{B}/{1$=}%4/{2B^=}%n+\}/;

```

This is a pretty literal translation. The vaguely interesting bits are:

1. Permutation PC1 turns out to have a lot of structure. If you take first differences, all but 6 of them are `-8`. The second line of the reformatted version reconstructs it from these differences in 39 characters. For comparison, representing it by base conversion would require 44 characters for the string literal; and representing a generic permutation of numbers 1 to 63 requires 36 base-256 digits (i.e. a 38-character string literal plus code to convert it).
2. `49281 2B{!) ... }` encodes the shift lengths. This is the most obvious place to attempt further optimisation.
3. Permutation PC2 doesn't seem to have any usable structure, so that's a straight double base conversion. (Not to be confused with a double bass conversion).
> 5 votes

---
Tags: code-golf, cryptography
---


# Question
Title: Build the busiest beaver in x86 machine code in 32 bytes or less
Your task is to write a program in x86 machine language (any version you like) that will run through as many instructions as possible and then halt, using a maximum of 32 bytes of code and starting with zeroed-out registers.

You can assume anything about the random-access memory you like, as long as it's in a usable format for the x86 machine.

# Answer
> 8 votes
## 2524224 instructions

My program:

```
_start:
        mov     bl, _end
        stc
iloop:  adc     [bx], al
        inc     bx
        jnz     iloop
        jnc     _start
        a32
        loop    _start
        hlt
_end:

```

(Technical note: this is written for nasm. The `a32` is nasm's syntax for the alternate address-size prefix byte. For masm, you would replace the `a32` with `defb 0x67`.)

For clarity, here's the listing output:

```
 1                  _start:
 2 0000 B310                mov     bl, _end
 3 0002 F9                  stc
 4 0003 1007        iloop:  adc     [bx], al
 5 0005 43                  inc     bx
 6 0006 75F9                jnz     iloop
 7 0008 73F4                jnc     _start
 8 000A 67                  a32
 9 000B E2F1                loop    _start
10 000D F4                  hlt
11                  _end:

```

The program assumes that the processor is in real mode, and that the program is located at the bottom of a 64k segment of memory which is otherwise initialized to all-bits-zero. Its design is simple: treat the memory as a single giant unsigned integer, and increment it through all possible values, until it rolls back around to all-zeroes. Repeat this 232 times. Then halt.

The innermost loop (lines 4‒6) is responsible for incrementing the huge integer. Each iteration adds zero or one to a single byte, depending on whether there was a carry out of the previous byte. Note that every byte in the huge integer is accessed, whether or not it has changed, so this loop always iterates 216 \- 14 times.

By the way, in case you were wondering, this code illustrates the reason why the x86 `inc`/`dec` instructions don't affect the carry flag: just to simplify this sort of multi-byte carry pattern. (This pattern came up more often back in the days of 8-bit microprocessors, when the original 8080 instruction set was defined.)

Line 7 causes the incrementing process to repeat until a one is carried out of the last byte, indicating that the huge integer has been reset to all-bits-zero. This takes a long time.

Lines 8‒9 mark the outermost loop, and causes this process to repeat 232 times, until the `ecx` register rolls around to zero. This is effectively equivalent to adding another 32 bits to the giant integer.

It would be possible to add another outer loop and do this again using (say) the `edx` register, and then maybe using `esi` and `edi` for even more repetitions. However, it's not worth doing. The instructions to increment and loop require four bytes. Those four bytes are taken away from the giant integer. So we lose 32 bits on the RAM counter, just to add 32 bits via a register: it ends up being a wash. The only reason `ecx` is an exception is that it has a specialized `loop` instruction that fits into only three bytes. Thus the program trades 24 bits for 32, a tiny but still positive gain of 8 bits.

It's not too hard to directly calculate the number of instructions that the program executes before it halts. However, there's a much simpler way to estimate this number. The program modifies all of its memory, less the 14 bytes that contain the program, and the `bx` and `ecx` registers. This adds up to 216 \- 14 + 2 + 4 = 65528 bytes, for a total of 524224 bits. The shortcut involves realizing that, in the process of running, every single possible pattern of 524224 bits appears exactly once. For the RAM and the `ecx` register this is easy to see, since the program increments through every single value. For `bx` this is a little less obvious, since it's being changed at the same time as the value in memory is being updated. However, one can show that, given the program's structure, if a complete bit pattern were to actually appear twice, then the program would have to be in an infinite loop. Since this is not the case, each bit pattern must ultimately be visited only once. (The complete proof is left as an exercise to the reader, naturally.)

Since every possible bit pattern appears in the course of the program, the program must execute at least 2524224 instructions, which is approximately equal to 1.4 × 10157807. (The acutal number is very slightly higher, because of the jump instructions, but the difference at this magnitude is negligible.)

Obviously, this could be significantly improved by using more than 64k of RAM. I'm holding off on the next version of the code until I figure out exactly how much RAM can be accessed.

# Answer
> 4 votes
## ~2^(2^67) instructions

(at&t syntax)

```
start:
    movq    $0x1a,%rax
    stc
loop:
    adcb    %cl,(%rax)
    incq    %rax
    jnz     loop
    jnc     start
    hlt

```

Disassembled, 26 bytes:

```
start:
0000000000000000    movq    $0x0000001a,%rax
0000000000000007    stc
loop:
0000000000000008    adcb    %cl,(%rax)
000000000000000a    incq    %rax
000000000000000d    jne loop
0000000000000013    jae start
0000000000000019    hlt

```

Similar to breadbox's solution, but there's no reason to stop at 16 bits of address. My code uses x86-64 and assumes we have 2^64 bytes of memory and we use all but the memory holding the code as a giant counter.

---
Tags: code-challenge, busy-beaver, machine-code, x86-family
---


title: Basic Calculator with GUI

text:
# Question
Title: Basic Calculator with GUI
I recently had to add a small basic calculator to a project. I wrote a quick dirty one, but it seemed small enough to check with you people out here ;)

Just out of curiosity & an appetite to get surprised for some real hacky solutions, try and beat this one :

**CODE (JS/JQUERY):**

```
function scalcy() {
    var b="", p=parseFloat,t,i;
    return $("<div>").append("789/456*123-.0=+".split("").map(function(i){
        return $("<button/>").text(i).width(32).height(32).click(function(){
        b = (!p(i=$(this).text())? b.replace(/\D+$/,""): b) + i;
        t.val(((!(i.match(/[.\d]/))? (b=eval(b.slice(0,-1))+i+"").slice(0,-1):
                p(b.match(/[.\d]+/g).pop()) || 0) + "").slice(0,8));
    })})).prepend(t=$("<input/>").width(123).click(function(){
        this.value=b="0";})).width(130);
}

```

**Screenshot (in chrome):** (**DEMO**)

**Considerations:** Better the UI & lesser the bugs, the better.

**Minimum Functionalities:**

* Supports floating point arithmetic (/\*-+),
* Reset feature,
* Continuous Operation (like working on with the last result)

**Note:**

* Use any language & library, but please not a library call like *new calculator()*.
* Forking the above code itself is most welcome.

---

**Additional Notes:**

* A graphical UI is obviously considered better than not having any at all.
* I'd suggest to have a look at this challenge (for inspiration): Create a GUI Piano.

# Answer
## Tcl/Tk, 100

```
pack [entry .e -textv e] -f both -e 1
bind . <Return> {catch {expr $e} e}
bind . <Escape> {set e {}}

```

Buttons are not required, so leave them alone.
The GUI is great. So simple that you can finally focus on the task that you try to do.
> 10 votes

---
Tags: code-challenge, arithmetic
---


title: Preferential Voting

text:
# Question
Title: Preferential Voting
Australia (and many countries) has a perferential voting system, where voters, number the candidates from 1 - n, where n is the number of candidates, in order of preference. Until a candidate gets a absolute majority of votes, the number 1 votes for the candidate with minimum count of number 1 votes, are redistributed to their next preference. Full detail can be found at http://www.eca.gov.au/systems/single/by\_category/preferential.htm, under the **The Full Preferential Count**

Implement a system that takes in a array of voting slips. where a voting slip is a array, where each index is a candidate ID, and the element at that index is the voters preference number for that candidate.

Eg: for a 3 candidates with, 7 voting slips, input could be:

```
    votes =
   2   1   3
   1   2   3
   3   2   1
   1   3   2
   1   2   3
   2   3   1
   3   2   1

```

You may take this input in your languages preferred 2D array like data structure.

Example function: (matlab)

```
function winningParty = countVotes (votes)
    [nVotes, nParties] = size(votes)

    cut = zeros(1,nParties) % no one is cut at the start
    while(max(sum(votes==1))<=0.5*nVotes) %while no  one has absolute majority
        [minVotes, cutParty] = min(sum(votes==1) .+ cut*nVotes*2)                           %make sure not cut twice, by adding extra votes to cut party

        votes(votes(:,cutParty)==1,:)--; % reassign there votes

        cut(cutParty) = true;
        votes

    end
    [winnersVotes, winningParty] = max(sum(votes==1))

```

Output:

```
octave:135> countVotes(votes)
nVotes =  7
nParties =  3
cut =

   0   0   0

minVotes =  1
cutParty =  2
votes =

   1   0   2
   1   2   3
   3   2   1
   1   3   2
   1   2   3
   2   3   1
   3   2   1

winnersVotes =  4
winningParty =  1
ans =  1 %This is the only line i care about

```

---

EDIT: In cases of tie for lowest portion of primary share, either can be removed. There can be no tie for winning candidate. Winner must have strictly greater than 50% of votes.

# Answer
## ~~Python 3,~~ ~~173~~ ~~146~~ Python 2, 125(see below)

**Original version, 173:**

```
C=sorted(S[0]);C[-1]=0
while C:
 v={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C};c=max(C,key=v.get);C.remove(min(C,key=v.get))
 if v[c]*2>len(S):C=print(v[c],c+1)

```

Expects input in this form:

```
S=[
   [2,   1,   3],
   [1,   2,   3],
   [3,   2,   1],
   [1,   3,   2],
   [1,   2,   3],
   [2,   3,   1],
   [3,   2,   1],
   ]

```

and prints number of votes and the winning candidate:

```
4 1

```

**Commented version:**

```
# create a list of the (still available) candidates;
# these will be used as indexes and therefore have to start at 0 instead of 1
C=sorted(S[0]);C[-1]=0
# start a loop with some condition that's easily stoppable later
while C:
    # for each slip s, find the (still available) candidate with the best vote; count these for each (still available) candidate
    v={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C}
    # find the candidate with the highest number of votes
    c=max(C,key=v.get)
    # remove the candidate with the lowest number of votest
    C.remove(min(C,key=v.get))
    # somebody with more than 50 % of the votes (=slips) already?
    if v[c]*2>len(S):
        # if yes, then print votes and candidate number
        # (the print function returns None, which makes the condition of the loop fail)
        C=print(v[c],c+1)

```

**EDIT After clarification of output by OP:**

```
C=sorted(S[0]);C[-1]=0
while C:v={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C};c=max(C,key=v.get);C.remove(min(C,key=v.get))
print(c+1)

```

(The loop runs to exhaustion of candidates, which is no problem, because the number of votes is not neeeded.)

**EDIT 2, newest version, Python 2, 125:**

Python 2 `range` yields a list, which is shorter than the construction I had to use for Python 3.

Also, `c` need not at all times be the candidate with tho most votes -- it's only important at the end. At the end, there is only one candidate left, so `c` just has to be *some* candidate (I use `C[0]`), because that must be the right one at the end.

That means that the name `v` is use only once. Replacing that usage with the definition of `v` saves some more characters.

```
C=range(len(S[0]))
while C:c=C[0];C.remove(min(C,key={i:sum(i==min(C,key=s.__getitem__)for s in S)for i in C}.get))
print c+1

```
> 1 votes

# Answer
### GolfScript, 37 characters

```
.0=,({.0={`{\0==}+1$\,,}$1>`{&}+%}*0=

```

Input (on stack) is a list of votes where elements can be e.g. numbers or strings. Example:

```
[
  ["Bernard" "Archibald" "Chris"]
  ["Archibald" "Bernard" "Chris"]
  ["Chris" "Bernard" "Archibald"]
  ["Archibald" "Chris" "Bernard"]
  ["Archibald" "Bernard" "Chris"]
  ["Bernard" "Chris" "Archibald"]
  ["Chris" "Bernard" "Archibald"]
]

.0=,({.0={`{\0==}+1$\,,}$1>`{&}+%}*0=

# => either Archibald or Bernard (because of tie)

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Build a solver for the monks and buns problem
An old Chinese poem goes:

> 一百饅頭一百僧，
> 大僧三個更無爭，
> 小僧三人分一個，
> 大小和尚得幾丁？

When translated into English, this math problem reads:

> 100 buns and 100 monks,
> Big monks eat 3 buns with no shortage,
> Little monks share one bun among three,
> Big and little monks, how many are there?

Once again, like in the cow and chicken problem, there is no simple calculation you can perform. You need the power of systems of equations.

Your task is to build a program that takes the following inputs, all positive integers:

* b, the number of buns.
* m, the number of monks.
* bl, the number of buns a big monk can eat.
* ms, the number of small monks who share one bun.

and output `l` and `s`, the number of big monks and small monks respectively. ("L" stands for "large").

Again, this problem has various states of solvability, but this time around, only output something if there is a unique solution in the nonnegative integers.

The shortest code to do all of the above in any language wins.

---

The problem input of the poem is `100 100 3 3`, and the solution is `25 75`.

# Answer
### R: 81 characters

```
i=scan();p=combn(0:i[2],2);cat(p[,p[1,]+p[2,]==i[2]&i[3]*p[1,]+p[2,]/i[4]==i[1]])

```

A brute force solver which takes all possible combinations of non-negative integers and subset the one corresponding to criteria.
> 0 votes

# Answer
## F#: 125 characters

```
printf"%O"(Console.ReadLine().Split()|>Seq.map Int32.Parse|>Seq.toArray|>fun[|b;m;x;y|]->((m-b*y)/(1-x*y),m-(m-b*y)/(1-x*y)))

```

This is my first attempt at code golf (here anyway), so I'm sure this could be improved. It simply reads the input, parses it, then does a little number crunching to get the correct results.

The result will be formatted like this:

```
(25, 75)

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Build an evaluator for nontrivial resistance diagrams
There is already a problem on here about calculating the total resistance of a resistor diagram. However, that problem deals only with series-parallel diagrams, which are trivially reducible. Here I present the question that includes nontrivial bridges and the like, and uses a slightly more convenient representation.

Your task is to build a program that, given a graph where each edge has a value representing the resistance of a resistor between the vertices of that edge, will calculate the resistance between two specified vertices.

Your program will take input in two parts:

* The resistor graph. This can be in one of two forms, depending on which one is more convenient:

+ An `N`-by-`N` adjacency matrix, where `N` is the number of points in the resistor graph. The `m`th entry of the `n`th row is the resistance of the resistor between points `m` and `n`, in ohms. (The `m`th entry of the `n`th row and the `n`th entry of the `m`th row will always be equal.) The way this adjacency matrix is represented in data is your choice.
    + A number `N`, denoting the number of vertices in the graph, followed by a list of entries, each entry containing three numbers: `p1`, `p2`, and `r`, which are the numbers of the two points and the resistance of the resistor placed between those points. There will never be more than one resistor connecting two points. Again, the way this list is represented in data is your choice.
* Two numbers `v1` and `v2`, representing the vertices between which the resistance is to be calculated.

All resistors will have a resistance of a positive integer of ohms. A value of `0` will refer to a resistor-less wire (i.e. zero resistance), and a value of `-1` or `infinity` (you can choose which one to accept) will refer to the absence of a wire (i.e. infinite resistance).

Your program will return `R`, the resistance between `v1` and `v2` in ohms, as a floating-point number (to at least four significant digits). If the resistance is infinite, return either `-1` or your language's representation of `infinity`.

Your solution must not make use of any libraries that are specifically built for solving linear equations or calculating the resistance of a resistor diagram.

Since any winning criteria I could come up with will take too long to judge properly (except for "first submitted code that actually works", but that one is unacceptable for obvious reasons), this will also be code golf. The shortest code in any language that can do the above will win. However, if you have an idea for a different winning criterion, I would be glad to hear it.

---

## Example inputs

### 1. Series diagram

The following matrix:

```
-1  2 -1 -1
 2 -1  3 -1
-1  3 -1  4
-1 -1  4 -1

```

is a diagram representing resistors of 2 ohms, 3 ohms, and 4 ohms, put in series in that order. An input of `1 3` as the vertices would return `5.0`, and an input of `1 4` would return `9.0`.

### 2. Parallel diagram

The following matrix:

```
-1  0  0  0 -1
 0 -1 -1 -1  2
 0 -1 -1 -1  3
 0 -1 -1 -1  4
-1  2  3  4 -1

```

is a diagram representing resistors of 2 ohms, 3 ohms, and 4 ohms, put in parallel in that order. An input of `1 5` as the vertices would return `0.9230769230769231`.

### 3. Infinite-resistance diagram

The following matrix:

```
-1  2 -1 -1
 2 -1 -1 -1
-1 -1 -1  4
-1 -1  4 -1

```

is a diagram representing two disconnected graphs of resistors. The input `1 2` would return `2.0`, but the input `1 4` would return `-1` or `infinity`, as there is no path between the vertices.

### 4. Zero-resistance diagram

The following matrix:

```
-1  0  0  0 -1
 0 -1 -1 -1  2
 0 -1 -1 -1  0
 0 -1 -1 -1  4
-1  2  0  4 -1

```

is a diagram representing resistors of 2 ohms and 4 ohms, and a plain wire, put in parallel. An input of `1 5` as the vertices would return `0.0`, as there is a wire with zero resistance running from point 1 to point 5 via point 3.

### 5. Bridge

The following matrix:

```
-1  2  1 -1
 2 -1  3  5
 1  3 -1  4
-1  5  4 -1

```

represents the smallest diagram of resistors that cannot be represented as a series-parallel diagram for a specific set of points, namely 1 and 4. An input of `1 4` has a result of `2.9`.

### 6. Cube

The following matrix:

```
-1  1  1 -1  1 -1 -1 -1
 1 -1 -1  1 -1  1 -1 -1
 1 -1 -1  1 -1 -1  1 -1
-1  1  1 -1 -1 -1 -1  1
 1 -1 -1 -1 -1  1  1 -1
-1  1 -1 -1  1 -1 -1  1
-1 -1  1 -1  1 -1 -1  1
-1 -1 -1  1 -1  1  1 -1

```

is a diagram representing a cube of one-ohm resistors. According to Wikipedia, the input `1 8` will return `0.8333333333333333`.

# Answer
# J, 50 characters

```
(3 :'0 a}1 b}y+1e_5*c=:+/(-/~y)%r+1e_4')^:_[0
%a{c

```

Assumes the input is already stored in a set of global variables as:

* `r` is a 2D matrix of single-precision numbers
* `a`, `b` are 0-based indices of the two nodes

### Usage:

```
r=:   _ 2 _ _
r=:r,.2 _ 3 _
r=:r,._ 3 _ 4
r=:r,._ _ 4 _

a=:0
b=:3

(3 :'0 a}1 b}y+1e_4*c=:+/(-/~y)%r+1e_3')^:_<./r
%a{c

```

### Explanation:

* `(3 :'...')^:_=/r` \- Repeat the explicit verb passed as a string until it converges (infinite power), starting with the scalar zero. It becomes a 1D array after the first iteration.
    + `r+1e_4` \- Add 100 μΩ parasitic resistance to each pair of resistor leads. We don't like wires. **Lower values increase precision, but also limit the time step. If there are no wires, parasitic resistance is not needed.**
    + `(-/~y)%` \- Create the table of self-differences of the node voltage list (the table of voltage differences) (The table of self-differences of a scalar is a scalar zero). Divide this by the resistances. You get a list of resistor currents.
    + `c=:+/` \- Compute the sum of each column - the current flowing into each node - and tuck that away into a global variable.
    + `y+1e_5*` \- Multiply that by the time step and add that to the node voltage of each node. **The time step** (divided by the parasitic capacitance of each node) **must be lower than the lowest resistance, otherwise the simulation will not converge. Lower value = slower convergence. Without wires, we can increase this value to 1/2** and save three chars (and also speed up the convergence immensely). With wires, this won't converge at 1/2 Ω.
    + `0 a}1 b}` \- Pin the probe voltages to 0 volts and 1 volt respectively.
* `%a{c` \- Take the current flowing into the ground, and return its inverse.
> 3 votes

---
Tags: code-golf, electrical-engineering
---


# Question
Title: I'd like a homework pizza with everything on it, but no loops
So there was a "please do my homework question" on StackOverflow that lead to an idea. As everyone knows loops are quite expensive, in some places they can get as high as $12.99 an iterations, so to save money there shouldn't be any loops.

So, lets do the homework, but in the least intuitive way.

> Write a program that decides, among competing candidate pizzas, which is the best deal, in the sense of the smallest cost per unit area. Pizzas come in three shapes: round, square, and oval (elliptical). The area of an oval is `pi*ab/4`, where: `a` and `b` are the longer and shorter dimensions of the oval.

~~The rest of the specifications are in the linked PDF, which I can add in if needed. The input and output should conform to the assignment.~~

As per breadboxes suggestion the I/O has changed a bit to be more golfy.

* Your program must accept input for each pizza (lower case is a literal, uppercase is an argument):
    + **In all of the below**: `C` is the cost for that pizza in drachma (a float), and all units of length are in attoparsecs (~3cm).
    + `C s L` \- a *square* pizza, with a size length L
    + `C r D` \- a *round* pizza, with **diameter D**
    + `C o L S` \- an *oval* pizza, with long side L and short side R, all ovals have an area of `pi*L*S/4` (for some reason).
    + An empty string denotes that there are no more pizzas.
* For each pizza, print out the area in attoparsecs, a literal `@` and the cost in Drachma per square attoparsecs (just numbers, units not required).
* After the user indicates there are no more pizzas, print the index of cheapest pizza (starting at 1).
* Pi may be approximated to 3.1415

An example run would be (`>` indicates input, `<` is output, but these don't need to be printed to screen):

```
> 13.59 r 14.2
< 158.37 @ 0.086
> 14.04 s 12.3
< 151.29 @ 0.093
> 12.39 o 14.1 8.3
< 91.92 @ 0.135
>
< 1

```

Spaces are optional in output, but the `@` symbol must be in the output of the pizza

**However, you can't use any *traditional* loops.** Recursion, `goto`s or list comprehension are all fine, but any thing that is syntactically a loop like a `for`, `while` or `do ... while` are all strictly forbidden.

**Shortest code wins.**

# Answer
> 3 votes
# HTML/JavaScript, 160 bytes

(linebreaks/indentation only added here do prevent scrolling)

```
<input onchange='window.n++||(n=1,L=1e9);s=this.value.split(" ");d=s[2];
        a=[5.5/7*d*(s[3]||d),d*d][1*(s[1]=="s")];c=s[0]/a;alert(a!=a?m:a+"@"+c);
        L<c||(L=c,m=n)'>

```

The input is a text box (press Enter to submit); the output is an alert box.

A few caveats (or cheats, if you will):

* Pi/4 is 5.5/7
* in some cases, it assumes that the pizzas have non-zero areas
* it's not possible to enter the same pizza twice in a row (because that won't trigger a `change` event)
* note that defocusing the input also counts as "enter"
* assumes that at least one pizza costs less than a billion Drachmas per square attoparsecs
* no fault tolerance for the input whatsoever
* you could argue that it's not qualified because it uses the browser's event loop

# Answer
> 1 votes
EDIT: Should note that I wrote this in response to prompting in the original stackoverflow question's comments. So it attempts to exactly follow the homework assignment (which was supposed to be done in Python and produce specified output). As such, it does not follow the updated golf-like rules.

So its absolutely not the shortest (repeats a lot of code), but it doesn't do any loops and it does some stupid things

```
def pizza(list,n):
    n = n + 1
    print 'Pizza Number ' + str(n) + ':'
    shape = raw_input('Pizza shape (round, square, oval):')
    if shape == 'oval':
        longer = float(raw_input('Pizza longer dimension:'))
        shorter = float(raw_input('Pizza shorter dimension:'))
        price = float(raw_input('Pizza price:'))
        area = (3.1415 * longer * shorter)/4
        print 'Pizza area is %.2f square inches' % area
        cost = price/area
        print 'Cost per square inch is $%.2f' % cost
        listing = '%d (OVAL %.2f x %.2f)' % (n,longer,shorter)
    elif shape == 'square':
        side = float(raw_input('Pizza side length:'))
        price = float(raw_input('Pizza price:'))
        area = side**2
        print 'Pizza area is %.2f square inches' % area
        cost = price/area
        print 'Cost per square inch is $%.2f' % cost
        listing = '%d (SQUARE %.2f x %.2f)' % (n,side,side)
    else:
        shape = 'round'
        diameter = float(raw_input('Pizza diameter:'))
        price = float(raw_input('Pizza price:'))
        area = 3.1415 * (diameter / 2)**2
        print 'Pizza area is %.2f square inches' % area
        cost = price/area
        print 'Cost per square inch is $%.3f' % cost
        listing = '%d (ROUND %.2f)' % (n,diameter)
    list[listing]=cost
    another = raw_input('Enter Another? (Y/N):')
    if another == 'Y':
        pizza(list,n)
        return list
    else:
        return list
dict=pizza({},0)
print 'The best deal is pizza number ' + min(dict, key=dict.get)

```

-Validates shape entry by assuming you want round if you enter anything else.

-Uses 3.1415 to avoid importing a library

-Assumes you are done if you enter anything besides 'Y'

-Every pizza is stored as a unique dictionary key.

Other than the things I intentionally did in a stupid way or to avoid a traditional loop, I'm open to any criticisms as I am not an accomplished python programmer.

# Answer
> 1 votes
# Python - 251

Definitely not the shortest, but a good indication of whats required.

```
def p():
 i = raw_input().split(' ')
 if['']==i:return
 f=float;C=f(i.pop(0));S=i.pop(0);P=3.1416;a=f(i[0])
 if's'==S:A=a**2
 elif'r'==S:A=P*(a/2)**2
 elif'o'==S:A=P*a*f(i[1])/4
 c=C/A;print A,'@',c
 return[c,p()]
P=p()[:-1];print P,P.index(min(P))+1

```

# Answer
> 1 votes
## Python 167 bytes

```
def p():
 try:return[eval("{2}*dict(s={2},r={2}*.7854,o={3}*.7854)['{1}']/{0}".format(*(raw_input()+' 1').split()))]+p()
 except:return[]
v=p()
print v.index(max(v))+1

```

Using the constant *0.7854* to approximate *π/4*.

Sample usage:

```
$ more in.dat
13.59 r 14.2
14.04 s 12.3
12.39 o 14.1 8.3

$ python homework-pizza.py < in.dat
1

```

# Answer
> 1 votes
# Ruby, ~~128~~ ~~132~~ 141 characters

```
b,j,i=1/0.0,1
$<.map{|s|j+=1
c,s,x,y=[*z=s.split,0].map &:to_f
b,i=c,j if b>c
p"#{a={?s=>x*x,?r=>x*x*=0.7854,?o=>x*y}[z[1]]}@#{c/a}"}
p"#{i}"

```

Borrowed `0.7854` from Primo. It's more precise than `3.1415/4` anyways.

User indicates there are no more pizzas by closing the STDIN stream. Yes, CTRL+D works in the jRuby interactive console. Yes, you have to restart the console to reopen the stream.

---

Cool facts about Ruby:

Destructuring assignment: you can assign an array to a list of variables. If you try to pass a non-array, it will be converted to an array first. In case of non-array-likes, that's a single-element array containing that element. If the array is too short, extra variables are set to `nil`. If the array is too long, some elements are discarded. Here we assign `nil` to `i` for scoping reasons only.

Ruby's selling points are iterators and methods with callbacks in general. To be enumerable, all you have to do is to implement `each` and inherit the right methods. This challenge forbids traditional loops, but it allows array comprehensions. STDIN is an input stream, and as such it is enumerable. As a bonus, input stream comprehension sets the globals `$_` (last line) and `$.` (line number) for us. Line 3 demonstrates the pretzel colon operator which constructs a block for the iterator.

Some find modifiers (`do_something until it_is_done`) confusing. I like them. Be careful that the order of evaluation (and of side-effects) is reversed, however. String interpolation - if overdone (like here) - can get messy at times (like here), and syntax highlighters can choke on nested interpolation (or give up completely, like here). Literal dereference. Just write a literal, and read from it immediately. Any decent language can do that (I owe an apology to PHP 5.3 at this point).

Of course, subexpression caching. As soon as an expression is long enough long or occurs frequently enough, stuff its value into a variable. Ruby's assignment has a low priority from the right, but high priority from the left. Thus, `a*b=c*d` assigns `c*d` to `b`. Also, carefully rearranging computation can let us alias variables. While normally a horrible thing, it can save characters when golfing because it lets one (ab)use the compound assignment operators. Unfortunately, it only works with operators.

---
Tags: code-golf
---


title: No branching please

text:
# Question
Title: No branching please
Anyone who is moderately into low level code optimization know about the perils of branching, be it implemented as if-statements, loops or select-statements the possibility of a branch misprediction is a terrible clock-wasting thing.

Simple problems can be solved much better with simple arithmetic, so let's do that.

For the following problems all variables are 32 bit unsigned integers and the only allowed code is plain set statements involving only the following operators:

```
+ addition
- subtraction
* multiplication
/ integer division, rounds down, division by 0 not allowed
% modulo
& binary and
| binary or
^ binary exclusive or
>> bitshift right
<< bitshift left

Logic operators, return 1 if the expression is true and 0 if it is false.
== equal
!= not equal
< less than
<= less than or equal
> greater than
>= greater than or equal

Set operator
=

```

Every line must consist of a variable identifier followed by a set operator, followed by an expression.

An expression may not contain additional set operators, but may contain variable identifiers, literal numbers and parentheses.

The golfing score shall only count the number of operators.

Example:

```
myvar = ( ( ( foo + 5 ) * bar ) % 7 ) == 3

```

Has a score of 5 operators.

A solution may include as many variables as the author see fit.
Variables that have not been set have value `0`.
Overflow and underflow is allowed, all negative numbers underflow, so `3 - 5` is `4294967294`, even as part of a larger statement.

### Task 1: Max

Two values, `A` and `B`, exist in the scope, make the `RESULT` variable contain the largest of those values when the program terminates.

### Task 2: Median

Three values, `A`, `B` and `C`, exist in the scope, make the `RESULT` variable contain the median of those values when the program terminates.

### Task 3: Square root

One value, `A`, exist in the scope, make the `RESULT` variable contain the square root of `A`, rounded down, when the program terminates.

It is ok to post an answer to only one or two of the questions, to some of you just finding valid solutions will be a challenge.

# Answer
## Task 3, 23 ops

```
x = (A >> 16) + A / ((A >> 13) + 511) + 15
x = (x + A/x) >> 1
x = (x + A/x) >> 1
x = (x + A/x) >> 1
RESULT = x - (x > A/x)

```

Using Newton's method, as the other solutions do, with a more tactfully chosen seed. The first bit `A >> 16` keeps the top of the range happy, the second bit `A / ((A >> 13) + 511)` keeps the middle of the range happy, and the last bit `15` the bottom, and also prevents division by zero errors (15 is the largest value possible which allows `0` to converge correctly - halved three times minus correction equals zero). For the input values `225, 275625, 82137969, 2908768489` (and nearby values) the initial seed is exact. All edge cases (perfect squares, perfect squares + 1, and perfect squares - 1) on the range `0 .. 2**32-1` have been tested and are correct.

A few comments about the rules:
*Overflow and underflow is allowed, all negative numbers underflow, so 3 - 5 is 4294967294, **even as part of a larger statement**.*

That last bit turns out to be something of an innovation killer. I initially attempted a solution using a generalized form of Halley's method, but realized that it was invalid given the above restriction. The iteration (as applied to square roots) is this:

```
x = x * (3*A + x*x) / (A + 3*x*x)

```

This iteration has nice qualities that Newton's does not. It converges cubically (rather than quadratically), it converges from above or below (rather than only from above), and it is not as sensitive to a poorly chosen seed (if Newton's iteration is provided a seed which is far too low, it will greatly over-shoot the convergence point, and then need to work its way back down).

Newton's method also has the problem (at least when dealing with integers) that it will quite often reach an *x* such that *A / x - x = 2* \- in this case, it will converge to a value one larger than the proper integer root, which needs to be corrected for; Halley's method needs no such correction. But unfortunately, the value of `3*A + x*x` will quite often be larger than the allowed 32-bit integer space.

There are a number of other generalized nth root algorithms, but they all share this same characteristic:

```
x = x + x*(v - x**n)/(v*n)
x = (x*(n+1) - x**(n+1)/v)/n
x = ((n-2)*x + (4*v*x)/(v + x**n))/n
x = x*((n+2)*v + (n-2)*x**n)/(v + x**n)/n
x = ((n-2)*x + (n*x*v)/(v + (n-1)*x**n))/(n-1)
x = ((n-2)*x + x*((n*2-1)*v + x**n)/(v + (n*2-1)*x**n))/(n-1)

x = x + 2*x*(v - x**n)/(v + x**n)/n
x = x + x*31*(v - x**n)/(10*v + 21*x**n)/n
x = x + x*561*(v - x**n)/(181*v + 380*x**n)/n
x = x + x*1153*(v - x**n)/(372*v + 781*x**n)/n

```

etc. Most of these display either cubic or quadratic convergence. The last four are part of a series of iterations which converges on quartic convergence. But in praxis, Newton's method will get you what you need with fewer operations, unless you need to calculate many hundreds of digits.
> 5 votes

# Answer
## Task 3, 39 Operations

**EDIT:** Changed last line; see comments.

This is an implementation of the Newthon method. Tested with all positive squares, and also with the positive squares minus one, and also one million random numbers in the range from 0 to 2^32-1. The seemingly funny starting value is short for `(1022 + A/1022) / 2`, which needs the least number of iterations (I think), and also makes the `RESULT` for `A=0` right (which would not be the case for `1024` instead of `1022`).

```
r = (511 + A/2044)
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
RESULT = r - (r > A/r)

```
> 5 votes

# Answer
# 65(61) operations (5 + 13 + 47(43))

**Task 1** -- Max(A,B)

```
RESULT = A + (B - A) * (A <= B)

```

This is the obvious solution. You need the assignment, you need comparison, you need to multiply the comparison with something, the multiplicand cannot be one of the variables and the product cannot be the result.

**Task 2** -- Mid(A,B,C)

```
RESULT = A                               \
       + (B - A) * (A > B) ^ (B <= C)    \
       + (C - A) * (A > C) ^ (C <  B)

```

This is an improvement over my previous 15-op solution, which conditioned all three variables - this saved two subtractions, but it introduced another centrality test. The test itself is simple: an element is in the middle iff exactly one other of the two is above.

**Task 3** -- sqrt(A)

```
X1     = 1024 + A / 2048
X2     = (X1  + A / X1 ) / 2
...
X10    = (X9 + A / X9 ) / 2
RESULT = X16 - (X16 * X16 > A)

```

Eleven rounds of newton approximation. The magic constant of 1024 is already beaten by WolframW (and 512 causes division by zero for a=0 before a=2\**32 converges), but if we can define 0/0 as zero, ten iterations will work with the starting value of 512. I do admit that my claim of ten iterations is not entirely clean, but I still claim them in parentheses.  ~~I'll have to investigate if nine is possible, however.~~ WolframH's solution *is* nine iterations.
> 5 votes

# Answer
### 1: 5 operators

```
RESULT = B ^ (A ^ B)*(A > B)

```

### 2: 13 operators

```
RESULT = B ^ (A ^ B)*(A > B) ^ (A ^ C)*(A > C) ^ (B ^ C)*(B > C)

```

### 3: 27 operators

```
g = 47|((0x00ffffff & A)>>10)|(A>>14)
r = (g + A/g)/3
r = (r + A/r)>>1
r = (r + A/r)>>1
r = (r + A/r)>>1
RESULT = r - (r*r-1>=A)

```
> 5 votes

---
Tags: arithmetic, atomic-code-golf, multiple-holes
---


title: How many pairs?

text:
# Question
Title: How many pairs?
<sup>*Inspired by this question*</sup>

Your challenge is very simple: take input in the form of `lookupString string1 string2 ... stringN` and output how many pairs of strings there are.

But there's a catch! There are two ways of interpreting "pairs." The first way is combinations. For example,

```
       1      2     3      4
orange orange apple orange orange

```

(the first `orange` is the lookup string) has 3 pairs of oranges, since there is #1 and #3, #3 and #4, and #1 and #4.

The second way of interpreting it is adjacent pairs. For example, the same input would have a result of 1 with this interpretation, since there's only one pair in which both oranges are next to each other. (#3 and #4)

You must write two programs, one with the first interpretation and another with the second. Your score is the sum of the length of the two programs. This is . Shortest score wins.

# Answer
> 7 votes
# J, 24 characters

### Anywhere - ~~14~~ 11

```
2!+/}.{.=;:

```

is 2 choose (`2!`) sum (`+/`) of the beheading (`}.`) of the first row (head) (`{.`) of the self-classification (`=`) of the words (`;:`) of its argument

beheading means "drop the first element and return the rest".

### Adjanced - 13

```
+/2*/\}.{.=;:

```

is the sum (`+/`) of products (ANDs) within each two-element prefix (`2*/\`) of the beheading (`}.`) of the head (`{.`) of the self-classification (`=`) of the words (`;:`) of its argument

ex:

```
   s=.'pear pear apple pear pear'
   +/#\2}.#~{.=;:s
3
   +/2*/\}.{.=;:s
1

```

# Answer
> 4 votes
# Python 3, 48 + 59 = 107

## Anywhere – 48

```
s,*L=input().split()
c=L.count(s)
print(c*~-c/2)

```

## Adjacent – 59

```
s,*L=input().split()
print(list(zip(L,L[1:])).count((s,s)))

```

# Answer
> 2 votes
# Ruby, 38 + 45 = 83

### Anywhere: 38

* -2 chars: Two statements was shorter than one.

```
l,*a=gets.split
p (n=a.count(l))*~-n/2

```

### Adjacent: 45

* -2 chars: Borrowed `x==[l,l]` from Doorknob.
* -2 chars: `find_all` =\> `select`
* -12 chars: `select` =\> `count`

```
l,*a=gets.split
p a.each_cons(2).count([l,l])

```

# Answer
> 2 votes
# Mathematica ~~33+42 = 75~~ 31+40 = 71

**Program 1**

```
Binomial[Count[Rest@#, #〚1〛, 2] &

```

Example

```
Binomial[Count[Rest@#, #〚1〛, 2] &[{"orange", "orange", "apple", "orange", "orange"}]

```

> 3

---

**Program 2**

```
Count[Partition[Rest@d, 2, 1], {e = #〚1〛, e}] &

```

Example

```
Count[Partition[Rest@d,2,1],{e=#〚1〛,e}] &[{"orange","orange","apple","orange", "orange"}]

```

> 1

# Answer
> 1 votes
## Ruby, 46 + 58 = 104

Posting my own solution first as I always do:

**Anywhere - ~~49~~ 46**

```
l,*a=gets.split;p ((1..a.count(l)).inject:*)/2

```

**Adjacent - ~~65~~ 58**

```
l,*a=gets.split;c=0;a.each_cons(2){|x|c+=1if x==[l,l]};p c

```

`l,*a` stolen from daniero :P

# Answer
> 1 votes
# R : 82

### Anywhere: 38 characters

```
a=scan(,"")
choose(sum(a[-1]==a[1]),2)

```

`sum(a[-1]==a[1])` returns the number of corresponding item and `choose` computes the corresponding binomial coefficient.

### Adjacent: 44 characters

```
a=scan(,"")
sum(diff(which(a[-1]==a[1]))==1)

```

`which(a[-1]==a[1])` returns the indices of the matching items, `diff` computes the difference between those indices and `sum(...==1)` returns the number of differences being 1 (i. e. the number of pairs of adjacent matching items).

# Answer
> 0 votes
# K, 20 + 44 = 64

### Anywhere: 20

```
{-1++/a~\:*a:" "\:x}

```

### Adjacent: 44

```
{+/min'(*h)~/:/:(2*!-_-(#a)%2)_a:1_h:" "\:x}

```

.

```
k){-1++/a~\:*a:" "\:x}"orange orange apple orange orange"
3
k){+/min'(*h)~/:/:(2*!-_-(#a)%2)_a:1_h:" "\:x}"orange orange apple orange orange"
1

```

# Answer
> 0 votes
# JavaScript - 166 chars

```
F=function(A){return A.match(RegExp(A.split(' ')[0], 'g')).length-1}

G=function(A){C=0;R=A.split(' ').splice(1);for(i=0;i<R.length-1;i++)R[i]==R[i+1]?C++:0;return C}

```

Edited to be separate functions.

---
Tags: code-golf
---


# Question
Title: javascript: smallest code to convert seconds to time
Given seconds like 11728, write the smallest javascript function that returns a string like `3hrs. 15min. 28sec.`

`signature textTime([int] t,[bool] z,[bool] m)`

`t` is the time like 11728 and you can assume `int`
`z` is optional and true means drop zero times, so `3hrs. 0min. 28sec.` becomes `3hrs. 28sec.`
`m` is optional and true means show only up to minutes, so `3hrs. 16min. 48sec.` is `3hrs. 16min.`

For 1 hour, `1hrs.` is fine (vs `1hr.`)

Example:

```
textTime(11728) returns "3hrs. 0min. 28sec."
textTime(11728,true) returns "3hrs. 28sec."
textTime(11728,true,true) returns "3hrs."

```

Regex is fine, speed is inconsequential.

**Shortest code wins.**

# Answer
# Javascript,  ~~194~~  192

```
function T(a,c,e){d=60;s=["sec","min","hrs"];alert(t=[a,(0|a/d)*d,(0|a/d/d)*d*d].map(function(a,b,f){p=(a-(0|f[b+1]))/Math.pow(d,b);return e&&1>b?"":c&&!p?"":p+s[b]+". "}).reverse().join(""))}

```

Run it e.g. with

`T(7215,true,false) //2hrs. 15sec.`

*Could probably be golfed a bit more*
<sub>Edit Notes:
Added function name for the cost of 1 character\* Renamed the function to `T`. I'm assigning `t` in the function hence i was overwriting the function itself. Changed (a/(d\*d)) -\> (a/d/d) </sub>
> 1 votes

# Answer
~~155~~ 147 characters.

```
textTime=(t,z,m,x)=>(x=[t/3600,t/60%60,t%60].map((t,i)=>(!z||t|0)&&~~t+["hrs","min","sec"][i]+"."||0).slice(0,2+!m),(z?x.filter(x=>x):x).join(" "))

```

If the parameters made a little more sense, yes, it would be fewer.

Non-ES6, changing the name and using globals like @C5H8NNaO4 did, at 183 characters:

```
function t(t,z,m){return(x=[t/3600,t/60%60,t%60].map(function(t,i){return(!z||t|0)&&~~t+["hrs","min","sec"][i]+"."||0}).slice(0,2+!m),(z?x.filter(function(x){return x}):x).join(" "))}

```
> 1 votes

# Answer
# 165 chars

```
function x(T, Z, M){
f=Math.round;h=T/3600;m=h%1*60;s=m%1*60;
r=f(h)+'hrs '+f(m)+'min '+f(s)+'sec'
Z?r=r.replace(/0\w+/g,''):0
M?r=r.replace(/\d+sec/,''):0
return r}

```

I just realized that this solution doesn't work for T\<60, so I added a few characters and that fixed it (see below):

## 167 chars

```
function x(T, Z, M){
f=Math.round;h=T/3600;m=h%1*60;s=m%1*60;
r=f(h)+'hrs '+f(~~m)+'min '+f(s)+'sec'
Z?r=r.replace(/0\w+/g,''):0
M?r=r.replace(/\d+sec/,''):0
return r}

```

If you don't care about getting the rounding quite right:

## 149 chars

```
function x(T, Z, M){
h=T/3600;m=h%1*60;s=m%1*60;
r=~~h+'hrs '+~~m+'min '+~~s+'sec'
Z?r=r.replace(/0\w+/g,''):0
M?r=r.replace(/\d+sec/,''):0
return r}

```
> 1 votes

---
Tags: code-golf, string, arithmetic, javascript
---


title: BrainF***-optimize a series of numbers

text:
# Question
Title: BrainF***-optimize a series of numbers
An often-used trick in BF-golfing is something I call "multiply then add." Let's say that you want to initialize the memory to contain a series of numbers, like `87 75 68 96`. The simplest way to do this is to simply write out a long series of 326 `+` signs. A better method, however is below.

```
++++++++++[>+++++++++>+++++++>+++++++>++++++++++<<<<-]>--->+++++>-->----

```

(I write this by hand, I hope it works correctly)

The basic idea is that you create a series of numbers (9,7,7,10), multiply them by a constant (10), and then add another series of numbers (-3,5,-2,-4). My invented form of notation writes this as (10;9,7,7,10;-3,5,-2,-4) which directly corresponds to the BF code.

There is a lot of importance placed in how the numbers are divided. If I were to pick a larger constant, then the first series of numbers would be much smaller, yet there will tend to be larger remainders after the multiplication. If I were to pick a smaller constant, then the first series would be larger, but the second series smaller.

Your goal is to write the shortest program to find the best possible way to write a series of numbers in BF using the multiply-then-add strategy.

Your program will recieve a series of non-negative integers. It should find the best way to generate these numbers.

For example, lets say that it receives the series (3,16,8,4), as an easy example. The best way to represent this is by the set of numbers (4;1,4,2,1;-1,0,0,0), which is what your program is expected to output (the exact formatting isn't as important). This corresponds to the following program:

```
++++[>+>++++>++>+<<<<-]>->>>

```

# Answer
> 1 votes
**Python, 205 characters**

```
def o(l):
    d=lambda l,a:[(d+1,m-a)if m>a/2 else(d,m) for d,m in(divmod(x,a)for x in l)]
    a,x=min((a+sum(abs(x)+abs(y)for x,y in d(l,a)),a,d(l,a))for a in range(1,max(l)+1))[1:]
    return [a]+zip(*x)

```

Examples:

```
>>> o([3,16,8,4])
[4, (1, 4, 2, 1), (-1, 0, 0, 0)]
>>> o([87,75,68,96])
[11, (8, 7, 6, 9), (-1, -2, 2, -3)]
>>> o([4,4,4])
[4, (1, 1, 1), (0, 0, 0)]
>>> o([1,2,3,4,5,6,7,8])
[4, (0, 0, 1, 1, 1, 1, 2, 2), (1, 2, -1, 0, 1, 2, -1, 0)]

```

As a bonus for a very long solution, the BF formater:

```
def bf(l):
    N,f,s=o(l)
    return ('%s[%s%s-]%s'%(N*'+',
                           ''.join('>' + x*'+' for x in f),
                           ''.join('<' for _ in f),
                           ''.join('>' + abs(x)*('+' if x>0 else '-')for x in s)))

>>> bf([3,16,8,4])
'++++[>+>++++>++>+<<<<-]>->>>'

```

# Answer
> 0 votes
### GolfScript, 74 65 characters

```
:f$-1=),{[..{1${\2$*-.abs 2$+[@@]}++\),%$0=}+f%{(@+\}%@\+]}%$0=1=

```

A quite long golfscript solution which simply tries lots of combinations of numbers and takes the shortest representation.

Input is the list of numbers on the stack and output a list of the final numbers (grouped differently compared with the question - constant, tuples of \[factor, addon\])

Examples:

```
{
  :f$-1=),{[..{1${\2$*-.abs 2$+[@@]}++\),%$0=}+f%{(@+\}%@\+]}%$0=1=
}:C;

[3 16 8 4] C p             # -> [4 [1 -1] [4 0] [2 0] [1 0]]
[87 75 68 96] C p          # -> [11 [8 -1] [7 -2] [6 2] [9 -3]]
[1 2 3 4 5 6 7 8] C p      # -> [4 [0 1] [0 2] [1 -1] [1 0] [1 1] [1 2] [2 -1] [2 0]]
[5 5 5] C p                # -> [5 [1 0] [1 0] [1 0]]

```

# Answer
> 0 votes
## Javascript 244 characters

```
function b(c){function e(f,c){n=m.abs;return n(f)+n(c)}a=0;m=Math;for(i=1;i<m.max.apply(null,c);i++)x=[],y=c.map(function(c){r=c/i|0;d=c%i;d=d>i/2?(r++,d-i):d;x.push(d);return r}),l=i+y.reduce(e)+x.reduce(e),a=!a||l<a[0]?[l,i,y,x]:a;return a};

```

Examples (first digit in output is total program length):

```
> b([3,16,8,4])
[13, 4, [1, 4, 2, 1], [-1, 0 0 0]]

> b([87,75,68,96])
[49, 11, [8, 7, 6, 9], [-1, 2, 2, -3]]

```

I think with "=\>" syntax coming soon, I could likely condense further. I wish I was better at BF, I think a solution in BF would be interesting as well.

Solution before condensed:

```
function b(s){
    a = 0;
    m = Math;
    for(i=1; i<m.max.apply(null, s); i++) {
        x = [];
        y = s.map(function(n) {
            r = n/i|0;
            d = n%i;

            d = d > i/2 ? (r++, d-i) : d;
            x.push(d);
            return r;
        });

        l=i+y.reduce(c)+x.reduce(c);
        a = !a || l < a[0] ? [l,i,y,x] : a;
    }
    function c(g, h) {
        n = m.abs;
        return n(g)+n(h);
    }

    return a;
}

```

Then ran through google closure compiler to condense to a single line.

---
Tags: code-golf, brainfuck
---