# Question
Title: Calculate the square of an integer with restrictions
# The Puzzle

You have to write a program or function p(n) that returns the square of what is entered into it and you may assume that the input is a non-negative integer. Put in simpler terms, return n2.

# Rules

1. You are not allowed to use `*` or `/` (or any other power or square root operator, such as `POW` or `SQRT`, if your language contains such functions)
2. You may not use a loop, or use a constructions that is similar to a loop. Example of loop like constructions are `GOTO` and recursion.

# Example

```
Function p(n)
Dim r()
ReDim r(n)
p = Len(Join(r, Space(n)))
End Function

```

Be creative and (ab)use the functions and features given to you by your language of choice.

\*edit

Loop like structures are loops that allow you to repeat 1 or more instructions

-if you could add an `stdout "1"` to your code and you would end up with repeating that output n times, it will count as a loop

# Answer
> 42 votes
# CJam, puts on his glasses

```
q~33c

(*_*)

(*_")>⌐■-■

(⌐■_■)

"]sG>4%,)

```

Input via STDIN

Try the code here

*Note that `*` in the code is not used as multiplying, but as a join operator*

*Also note that the cool part of the code is not just string, half of it is actually the code involved in finding the square. So.. DEAL WITH IT*

This will help you in dealing with it:

```
q~33c                    "Read the number and put ASCII character 33 on stack with it"
(                        "Decrease it to get ASCII code 32 character, which is a space";
 *_                      "Repeat the space input number times and make another copy";
   *                     "Put that many spaces in between each space. Now we have";
    )                    "n*n spaces string. We take out the last space out of it";
(                        "Decrement the space to get ASCII 31 character";
 *                       "Fill the n*n - 1 spaces with that to get 2*n*n - 3";
  _                      "string. Then copy it again.";
   ")>⌐■-■               "Put the sun glasses in";
(⌐■_■)                   "Wear the sun glasses. Be cool.";
"]s                      "Add everything to a single string of 4*n*n - 6 + 16"
   G>                    "length. Remove first 16 characters";
     4%                  "Take every 4th character from that string to get n*n - 1"
       ,)                "length string. Take length and increment to get n*n";

```

# Answer
> 20 votes
# Ruby

```
def square(n)
  case n
  when 0..1
    n
  when 2..36
    '100'.to_i(n)
  else
    raise RangeError, 'Integer overflow!'
  end
end

```

# Answer
> 20 votes
# APL? ∊⍵⍵

```
{+/ ∊⍵⍵ ⍴1}

```

This answer is dedicated to all those people who go "∊⍵⍵" whenever they see the APL symbols :-)

**Examples**

```
      {+/∊⍵⍵⍴1} 3
9
      {+/∊⍵⍵⍴1}¨⍳20
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400

```

**Explanation**

```
{       }   This function takes a number ⍵,
{   ⍵⍵⍴1}   builds a matrix of ⍵ by ⍵ all filled with ones,
{+/∊    }   and sums all its elements together.

```

# Answer
> 15 votes
# Abusing some functions in Mathematica

Twice the area of an isosceles right triangle

```
a =RegionMeasure@SASTriangle[n,ArcSin[1], n]
a+a

```

---

The area of a square. Of course!

```
RegionMeasure[Rectangle[{0, 0}, {n, n}]]

```

The same idea, in a different form:

```
Integrate[n, {x, 0, n}]  (* thx to DigitalTrauma *)

```

---

The number of elements in a square matrix:

```
 Length[Flatten[Normal[AdjacencyMatrix[RandomGraph[{n, RandomInteger[n]}]]]]]

```

or

```
 Plus@@Flatten[ConstantArray[1, {n, n}]]

```

or

```
 Length@Flatten[Outer[f,Range[n],Range[n]]]

```

or

```
 Length[Distribute[p[Range[n],Range[n]],List]]

```

etc...

# Answer
> 13 votes
# C

```
p(n){int a[n];return(&a)[n]-a;}

```

Note:

* Variable-length arrays are a conditionally-supported feature since C99.
* Implicit `int` is used to reduce character count and for style points.

# Answer
> 12 votes
# Python 2

Purely mathematical, avoiding any of the banned operations:

```
import cmath
n=input()
if n:
  l=complex(0, -cmath.log(n) - cmath.log(n))
  print int(round(abs(complex(cmath.cos(l),cmath.sin(l)))))
else:
  print 0

```

This is the usual `exp(ln(x)*y)` trick tailored to this problem:

* Because y is 2, then we can simply do `ln(x)+ln(x)` to get rid of the multiplication.
* I felt that `math.exp()` was a bit too close to the banned "POW" for fair play, so instead the whole thing is converted to complex and Euler's identity is used to replace the `exp()` with `cos()` and `sin()`
* To avoid the situations where explicit multiplication/division by *`i`* is needed, the `complex()` function is used instead.

# Answer
> 12 votes
# Mathematica

Another answer using some funny Mathematica features

```
n = Input[];
g = EdgeCount@CompleteGraph@n;
g + g + n

```

A complete graph with `n` vertices has `binom(n,2) = n(n-1)/2` edges (which is also the n'th triangular number). So the result is simply twice that, plus the input.

# Answer
> 8 votes
# Pure Bash

No explicit loops or arithmetic:

```
(($1))||{ echo 0;exit;}
eval a=({1..$1}{1..$1})
echo ${#a[@]}

```

Uses bash expansions to create two lists 1-n and brace-expand them and display the size of the resulting array.

---

Similar method, but making use of coreutils instead:

```
join <(seq -f "1 %g" $1) <(seq -f "1 %g" $1) | wc -l

```

# Answer
> 8 votes
# R, delicious inefficiency with Monte Carlo

The expectation `E[x]` for the shape/scale parametrization of the Gamma Distribution is `shape*scale`.

I don't see `mean` being banned, so here is the sample solution with `mean()`

```
f = function(n, k = 1e9){round((mean(rgamma(k, shape = n, scale = n))))}
f(99)

```

Without using `mean()`, it is possible to use `mode[x]`, which is equal to `(shape-1)*scale`, but this involves writing a `add.one` function to bypass `+1` then writing another `Mode` function to tabulate the mode.

```
add.one = function(x) length(c(seq(x),NA))
Mode = function(x) (u<-unique(x))[which.max(tabulate(match(x,u)))]
f.mode = function(n, k = 1e9){Mode(round(rgamma(k, shape = add.one(n), scale = n)))

```

Accuracy not guaranteed, but law of large number should kick in for 1,000,000,000 samples, which has given me the right results for all my test cases.

# Answer
> 7 votes
# **Java**

First entry, is this how it works?

```
int g(int n){
    int[] a = new int[n];
    Arrays.fill(a,n);
    return IntStream.of(a).sum();
}

```

# Answer
> 6 votes
# C#

Creates a string with n characters and then replaces each character with the n-character string. This produces a string with a length of n\*n.

```
using System;

public class Test
{
    public static void Main()
    {
        int n = Int32.Parse(Console.ReadLine());
        String s = "".PadLeft(n, 'X');
        Console.WriteLine(s.Replace("X", s).Length);
    }
}

```

Test it here: http://ideone.com/lubIFg.

# Answer
> 5 votes
# Matlab

*a warning: this is primarly math based, so do not expect fancy source code*

Note that `a = n^2` iff `log(a) = log(n)*2` iff `log(log(a)) = log(log(n))+log(2)`. So this function is just finding the zero of the function `f(a) = log(log(n))+log(2) - log(log(a))` which obviously is at `a = n^2`.

```
function s = g(n)
    f = @(a) log(log(n))+log(2)-log(log(a));
    s = fnzeros(f);
end

```

### Here some other not very creative functions:

Here the program wil sum sum the number `1+2+3+...+n = 1/2 * (n^2+n)` twice and substract `n`, so the result is always `n^2`

```
g=@(n)sum(1:n)+sum(1:n)-n

```

This function creates a `n x n` matrix of random numbers (between 0 and 1) and then returns the number of elements.

```
g=@(n)numel(rand(n));

```

The following functin creates a vandermonde matrix of the vector `(0,0,n)` and outputs the entry that consists of `n^2`

```
function s = g(n)
    a = vander([0,0,n]);
    s = a(3,1)
end

```

This function creates the inverse of a hilbert matrix of size `n` where the top left element is always `n^2`

```
function s = g(n)
    a = invhilb(n);
    s = a(1);
end

```

# Answer
> 5 votes
# C

```
sizeof(char[n][n])

```

It works up to INT\_MAX in constant time and without memory allocation.

Example:

```
#include <stdio.h>
#include <limits.h>
int main(){
    for( int n=0 ; n<10 ; n++ ){
        printf("%d: %ld\n", n, sizeof(char[n][n]));
    }
    int n = INT_MAX;
    printf("%d: %ld\n", n, sizeof(char[n][n]));
}

```

displays

```
0: 0
1: 1
2: 4
3: 9
4: 16
5: 25
6: 36
7: 49
8: 64
9: 81
2147483647: 4611686014132420609

```

# Answer
> 4 votes
# Java

This is the first answer that truly does not use loops or recursion.

```
int square(int n){
    if (n > 0){
        n = -n;
    }
    return m(n,0) + m(n,1) + m(n,2) + m(n,3) + m(n,4) + m(n,5) + m(n,6) + m(n,7) + m(n,8) + m(n,9) + m(n,10) +
            m(n,11) + m(n,12) + m(n,13) + m(n,14) + m(n,15) + m(n,16) + m(n,17) + m(n,18) + m(n,19) + m(n,20) +
            m(n,21) + m(n,22) + m(n,23) + m(n,24) + m(n,25) + m(n,26) + m(n,27) + m(n,28) + m(n,29) + m(n,30) + m(n,31);
}

int m(int number, int index){
    if (number >> index << 31 >>> 31 == 0){
        return 0;
    } else {
        return number << index;
    }
}

```

# Answer
> 3 votes
## GolfScript

Histocrat has shown one way of using base conversion: here's another.

```
{.,1base.++}:p;

```

### Dissection

```
{       # Function boilerplate
  .     # Duplicate the input. Stack: x x
  ,     # Turn the second one into an array [0 1 ... x-1]
  1base # Sum the elements of the array. Stack: x x(x-1)/2
  .+    # Double. Stack: x x(x-1)
  +     # Add. Stack: x*x
}:p;    # Question asks for the function to be called p
        # The fact that this destroys the built-in p is unfortunate, but required

```

# Answer
> 2 votes
## Emacs Lisp

```
(defmacro square-it (n)
  (cons '+ (make-list n n)))

(square-it 11) ;; => 121

```

A simple macro that expands `(square-it 5)` into `(+ 5 5 5 5 5)`. Of course, the input must be a compile time constant.

# Answer
> 2 votes
# Javascript

```
function square(i) {
    return new Array(++i).join(new Array(i).join(' ')).length;
}

```

# Answer
> 2 votes
# Haskell

There a lot of possibilities if ranges `[x..y]` are allowed, some of them are:

```
f n|x<-sum[1..n]=x+x-n
f n=sum$take n[n,n..]
f n=length$[1..n]>>[1..n]
f n=sum$[1..n]>>[1..n]>>[1]

```

The two latter ones use the Monad instance of lists. for lists `xs`, `ys` holds that `xs>>ys` is `ys` appended to itself `length xs` times.

another trick is just

```
import Data.Monoid
f x=x<>x

```

this function, when given an 'appropriate' argument (which are of course from the typeclass `Num`) return it's square. `Product 3 :: Num a => Product a` is an example of such an argument.

basically, this function when applied on `Product a`, (which in the `Num` class iff `a` is in i) `mappend`s it with itself and returns `Product (a*a)`.

if we are more strict about what is a number / what numbers should our function work on, we can define `f` as

```
import Data.Monoid
f n|x<-Product n=getProduct$x<>x

```

# Answer
> 2 votes
## Java

This is too long to put in the answer, but basically one of the lines of code occurs an amount of times roughly equal to the sqrt of `Integer.MAX_VALUE` (which is 46340). :D

With no comments or line breaks, the code typed out would be 1,112,155 characters.

```
int s(int n){
    if(n==0|n==1)return n;
    int c=2,r=n+n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
    if(n==c++)return r;r+=n;
                            //... (same line of code a total of 46336 times)
    if(n==c++)return r;r+=n;
    if(n==c++)return r;
    return n==c?r+n:r+n+n; //r = 46340^2
}

```

# Answer
> 2 votes
# R

This function is based on counting all possible combinations of two sequences ranging from 1 to `n`. The value 0 is treated separately.

```
f <- function(n) if (n) nrow(expand.grid(s <- seq(n), s)) else 0

```

# Answer
> 2 votes
# Clojure

```
(def squares (lazy-cat [0] (map (fn [sq x] (+ sq x x 1)) squares (range))))

```

Infinite sequence of all squares starting from 0. The function:

```
(defn square [n] (nth squares n))

```

# Answer
> 1 votes
# J

Some ascii art...

```
p =. ( $ @,@  ( ($*) ([-])"*/ ($*) ))

```

# Answer
> 1 votes
# Python

Uses simple math. Based on the sum of an arithmetic progression.

```
s=lambda n:(sum(range(n))<<1)+n

```

Explanation:

```
a = sum(range(n)) # sum of arithmetic progression from 1 to n-1:  n*(n-1)/2
b = a<<1          # bitshift left by 1 (multiply by 2):  n*n - n
c = b+n           # add n:  n*n

```

Although sum and range probably contains implicit loops,
but as per question spec, there's no way to insert a print statement here to make it repeat, so ... :)

# Answer
> 1 votes
perl :

```
$n=8;
$x = "$n +" x $n;
$x =~ s/\+$//;
print eval $x;

```

# Answer
> 1 votes
## SQL(PostGIS)

Making use of the area and make envelope functions in the PostGIS extension to PostGreSQL to create a square geometry and return it's area. Could be changed to return the square of floats as well.

```
CREATE FUNCTION square(n int)RETURNS int AS $$
BEGIN
    RETURN ST_Area(ST_MakeEnvelope(0,0,n,n));
END;
$$LANGUAGE plpgsql;

```

In use;

```
SELECT square(150);

Square Integer
--------------
22500

```

# Answer
> 1 votes
# Bash

```
yes|xargs -L$1|xargs -L$1|head -n1|iconv -futf16|wc -m

```

Only works if n \< 256.

# Answer
> 1 votes
# PHP

```
function square($v) {
    return array_sum(array_fill(0, $v, $v));
}

```

works with integer in the range \[0;46340\]

Edit: I've just seen @thebestone code and it is basically the same

# Answer
> 1 votes
# Perl

```
$_=<>;chop;s/./$_/g;print

```

the program expects the input number to be squared in unary form (i.e. base 1). Output is also unary. It simply replaces every digit with the whole number.

Example usage:

```
perl -e '$_=<>;chop;s/./$_/g;print'
000                                   # <- user input
000000000                             # <- output

```

# Answer
> 1 votes
# Scala:

```
scala> val q = (n:Int) =>(List.fill (n)(n)).sum
q: Int => Int = <function1>

scala> q(9)
res21: Int = 81

```

# Answer
> 1 votes
# Scala:

```
scala> val s=(n:Int)=>(("x"*(n))*n).size
s: Int => Int = <function1>

scala> s(7)
res22: Int = 49

```

# Answer
> 1 votes
# Clojure

```
(fn [n] (apply + (repeat n n)))

```

# Answer
> 0 votes
# Java 8

Makes a list n units long of n and then sums. At first I thought I would have to use bit operations or reflection to complete the task. Please comment if using `generate` is considered using "loops".

```
IntFunction square=(n)->IntStream.generate(()->n).limit(n).sum();

```

Example program:

```
import java.util.function.IntFunction;
import java.util.stream.IntStream;

class N{
    public static void main(String[]a){
        IntFunction square = (n)->IntStream.generate(()->n).limit(n).sum();
        System.out.println(square.apply(new Integer(a[0])));
    }
}

```

# Answer
> 0 votes
# Erlang

```
f(N) ->
  L=lists,
  L:sum(L:duplicate(N, N)).

```

# Answer
> 0 votes
# J

This doesn't *directly* use a divition or a power...

```
+~ &.: ^.

```

or: `double under ln`.

# Answer
> 0 votes
# Clojure:

```
(defn sq [n] (let [init (repeat n ".")] (count (flatten (map (fn [_] init) init))))

```

I'm sure it can be written shorter, but I'm out of inspiration.

Credit due to hetzi for inspiration.

# Answer
> 0 votes
# lambda calculus

```
λx.n (n x)

```

where n is a Church numeral.

By definition of Church numerals:

```
1 := λf.λx.f x
2 := λf.λx.f (f x)
3 := λf.λx.f (f (f x))

```

It happens that `m n` (apply m to n) evaluates to the Church numeral of n^m. So you can square n with:

```
2 n

```

But arguably, `2` *is* the square function, so I expanded `2`'s definition.

---
Tags: popularity-contest, number, restricted-source, arithmetic
---


title: Music: What's the name of this chord?

text:
# Question
Title: Music: What's the name of this chord?
This is the reverse of Music: what's in this chord?, which is to print the notes in a given chord. This time the input is a list of notes in a chord, and your task is to output which chord it is.

Your program should support the following triadic chords. Examples are given with root C. Chords with other roots are the same chords with all notes rotated so C will become that root note, e.g. Dmaj consists of D, F# and A.

```
        C C#D D#E F F#G G#A A#B
          Db  Eb    Gb  Ab  Bb
Cmaj    C       E     G
Cm      C     D#      G
Caug    C       E       G#
Cdim    C     D#    F#
Csus4   C         F   G
Csus2   C   D         G

```

Note that Caug is the same as Eaug and G#aug, and Csus4 is the same as Fsus2. You can output either one but there is a bonus if you output them all.

And the seventh chords for the bonus are listed in the follow table:

```
        C C#D D#E F F#G G#A A#B
          Db  Eb    Gb  Ab  Bb
C7      C       E     G     A#
Cm7     C     D#      G     A#
Cmmaj7  C     D#      G       B
Cmaj7   C       E     G       B
Caug7   C       E       G#  A#
Cdim7   C     D#    F#    A

```

## Rules

* You can write either a complete program or a function.
* The input is a list of notes, separated by a space or another convenient character. It can also be an array of strings (if it take input from function argument) or the string representation of such array.
* Input doesn't have to be in specific order.
* There may be duplicated notes in the input. They must be treated the same way as there is only one of them.
* The output is the name of the chord. In case it will output multiple names, the same rule for input applies.
* If the input isn't a supported chord, you should print the notes as-is. Your program can also support other chords not listed in the tables above (which is valid but has no bonus).
* You can use other notations listed in the Wikipedia article. But if you choose `C` for C major, you should add a human readable prefix in either case to distinguish a chord with a single note.
* You cannot use built-in functions for this task (if there is any).
* This is code-golf. Shortest code in bytes wins.

## Examples

* Input: `C D# G` Output: `Cm`.
* Input: `C Eb G` Output: `Cm`.
* Input: `C Eb F#` Output: `Cdim`.
* Input: `F A C#` Output: `Faug`, `Aaug`, `C#aug`, `Dbaug` or `Faug Aaug C#aug`, `Faug Aaug Dbaug` in any order.
* Input: `F D F F F F A A F` Output: `Dm`.
* Input: `C D` Output: `C D`.

## Bonuses

* -30 if it prints them all if there are more than one interpretations (for aug, sus4/sus2 and dim7).
* -70 if it also supports seventh chords.
* -200 if it accepts MIDI input and prints each chord it have received. Note that the notes doesn't have to begin or end at the same time. You decide what happens in the intermediate states (as long as it doesn't crash or stop working). You may assume there are no notes in percussion channels (or there is only one channel if that's convenient). It is recommended to also provide a text (or array) version for testing, especially if it is platform-dependent.

# Answer
> 3 votes
# Perl 5: 183 - 100 = 83

Edit: I managed to cut some extra characters so I also altered the chord names like in the Python solution, so I can pretend for a moment that I am leading.

```
#!perl -pa
for$z(0..11){$x=0;$x|=1<<((/#/-/b/+$z+1.61*ord)%12or$o=$_)for@F;$x-/\d+_?/-$_*4||push@r,$o.$'
for qw(36M 34- 68+ 18o 40sus2 33sus4 292_7 290-7 546-M7 548M7 324+7 146o7)}$_="@r
"if@r

```

Example:

```
$ perl chord.pl <<<"C D# G"
C-

```

# Answer
> 2 votes
# Pyth 190 character - 30 - 70 = 90

```
=Q{cQdL+x"C D EF G A B"hb&tlbt%hx" #b"eb3FZQJx[188 212 199 213 200 224 2555 2411 2412 2556 2567 2398)u+*G12hHSm%-dyZ12mykQ0IhJ+Z@c"sus2 maj dim aug m sus4 7 m7 mmaj7 maj7 aug7 dim7"dJ=T0;ITQ

```

Not really happy with it. Used hard-coded chords.

## Usage:

Try it here: Pyth Compiler/Executor. Disable debug mode and use `"C D# G"` as input.

## Explanation:

First some preparation:

```
=Q{cQd
   cQd  split chord into notes "C D# G" -> ["C", "D#", "G"]
  {     set (eliminate duplicates)
=Q      Q = ...

```

Then a function that converts notes into integer

```
L+x"C D EF G A B"hb&tlbt%hx" #b"eb3
defines a function g(b),
  returns the sum of
     index of "D" in "C D EF G A B"
     and the index of "#" in " #b"
       (if b than use -1 instead of 2)

```

Then for each note, shift the coord and look it up in a table

```
FZQJx[188 ...)u+*G12hHSm%-dyZ12mykQ0IhJ+Z@c"sus2 ..."dJ=T0;ITQ
               implicit T=10
FZQ            for note Z in chord Q:
   mykQ         map each note of Q to it's integer value
   m%-dyZ12     shift it by the integer value of Z modulo 12
   S            sort it
   u+*G12hH 0   convert it to an integer in base 12
   x[188 ...)   look it up in the list (-1 if not in list)
   J            and store the value in J

   IhJ               if J>=0:
   +Z@c"sus2 ..."dJ   print the note Z and the chord in the list
=T0                   and set T=0
;            end loop
ITQ          if T:print chord (chord not in list)

```

# Answer
> 0 votes
## Python 2, 335 bytes - 30 - 70 = 235

First attempt at a slightly longer golf, so I may be missing some obvious tricks.

```
def f(s,N="C D EF G A B",r=range,u=1):
 for i in r(12):
  for t in r(12):
   if(set((N.find(n[0])+" #".find(n[1:]))%12for n in s.split())==set(map(lambda n:(int(n,16)+i)%12,"0"+"47037048036057027047A37A37B47B48A369"[3*t:3*t+3]))):print(N[i],N[i+1]+"b")[N[i]==" "]+"M - + o sus4 sus2 7 -7 -M7 M7 +7 o7".split()[t];u=0
 if(u):print s

```

Comments:

* I used alternative chord names from the Wiki page (see the end of the long line) to save space.
* Chords are represented by 3 hex offsets each (0 is not required but included for triads to make them line up).
* " #".find(n\[1:\]) works since " #".find("b") is -1 and " #".find("") is 0.

**Sample output**

```
>>> f("C D# G")
C-
>>> f("C Eb G")
C-
>>> f("C Eb F#")
Co
>>> f("F A C#")
Db+
F+
A+
>>> f("F D F F F F A A F")
D-
>>> f("C D")
C D
>>> f("C Eb Gb A")
Co7
Ebo7
Gbo7
Ao7

```

---
Tags: code-golf, music
---


title: Auto-meta-code-golf

text:
# Question
Title: Auto-meta-code-golf
You are sick of all of the codegolf challenges. Hence you decide to write a program that will automatically golf some Python code for you. There are 3 test cases:

```
print quickSort([0,7,3,-1,8,10,57,2])
def quickSort(arr):
    less = []
    pivotList = []
    more = []
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        less = quickSort(less)
        more = quickSort(more)
        return less + pivotList + more

```

---

```
for i in xrange(1, 101):
    if i % 15 == 0:
        print "FizzBuzz"
    elif i % 3 == 0:
        print "Fizz"
    elif i % 5 == 0:
        print "Buzz"
    else:
        print i

```

---

```
from sys import argv

def randomGenerator(seed=1):
    max_int32 = (1 << 31) - 1
    seed = seed & max_int32

    while True:
        seed = (seed * 214013 + 2531011) & max_int32
        yield seed >> 16

def deal(seed):
    nc = 52
    cards = range(nc - 1, -1, -1)
    rnd = randomGenerator(seed)
    for i, r in zip(range(nc), rnd):
        j = (nc - 1) - r % (nc - i)
        cards[i], cards[j] = cards[j], cards[i]
    return cards

def show(cards):
    l = ["A23456789TJQK"[c / 4] + "CDHS"[c % 4] for c in cards]
    for i in range(0, len(cards), 8):
        print " ", " ".join(l[i : i+8])

if __name__ == '__main__':
    seed = int(argv[1]) if len(argv) == 2 else 11982
    print "Hand", seed
    deck = deal(seed)
    show(deck)

```

Rules:

1. Your program must not target the code I posted specifically, and should work with any Python 2 code. I reserve the right to change the source code being codegolfed. You may assume that there are no multi-line strings (so you don't have build a full-blown parser), and that locals() is not called.
2. The output of your program should run in an identical manner as the original source code. (Namely, it must produce the same output. Variable names and language constructs can be changed, as long as the output remains the same)
3. You may use STDIO or a File to do your input/output of the source code.

Your score will be the sum of the bytes of your program's output.

(The code listed above has been taken from http://rosettacode.org/ under the GNU Free Documentation License 1.2)

# Answer
> 4 votes
# Python 2.7, 794

I have been meaning to build a minifier for Python for a while, so this is a good opportunity to investigate the problem.

The program uses a mix of regular expression analysis, and Python parser operations. White space is minimised. Variable that are defined by the user are replaced by a single letter variable (which is not in use!). Finally the `while True` statement is put on a diet.

The three test cases all verify as running correctly. I could imagine some pathological examples which could result in errors in the generated code but the algorithm should be robust under most circumstances.

## Results

```
228 t1.py
128 t2.py
438 t3.py
794 total

```

## Output

```
def c(a):
 b=[]
 d=[]
 f=[]
 if len(a)<=1:
  return a
 else:
  e=a[0]
  for i in a:
   if i<e:
    b.append(i)
   elif i>e:
    f.append(i)
   else:
    d.append(i)
  b=c(b)
  f=c(f)
  return b+d+f
print c([0,7,3,-1,8,10,57,2])

for i in xrange(1,101):
 if i%15==0:
  print"FizzBuzz"
 elif i%3==0:
  print"Fizz"
 elif i%5==0:
  print"Buzz"
 else:
  print i

from sys import argv
def a(k=1):
 b=(1<<31)-1
 k=k&b
 while 1:
  k=(k*214013+2531011)&b
  yield k>>16
def d(k):
 f=52
 h=range(f-1,-1,-1)
 g=a(k)
 for i,r in zip(range(f),g):
  j=(f-1)-r%(f-i)
  h[i],h[j]=h[j],h[i]
 return h
def m(h):
 l=["A23456789TJQK"[c/4]+"CDHS"[c%4]for c in h]
 for i in range(0,len(h),8):
  print" "," ".join(l[i:i+8])
if __name__=='__main__':
 k=int(argv[1])if len(argv)==2 else 11982
 print"Hand",k
 e=d(k)
 m(e)

```

## Code

```
import sys
import re
from tokenize import generate_tokens
from token import tok_name
from keyword import iskeyword

wr = sys.stdout.write

def pyparse(text):
    'Return [TYPE,TOKEN] pair list'
    # Use KEYWORD,NAME,NUMBER,OP,STRING,NL,NEWLINE,COMMENT,INDENT,DEDENT
    rawtokens = generate_tokens(text.readline)
    tokens = [[tok_name[n], t] for n,t,p1,p2,dx in rawtokens]
    for tpair in tokens:
        if tpair[0] == 'NAME' and iskeyword(tpair[1]):
            tpair[0] = 'KEYWORD'
    return tokens

def finduservars(filename):
    'Return a set of user variables that we can replace with a-zA-Z'
    varset = set()
    for line in open(filename):
        line = line.strip()
        match = re.match(r'def\s+(\w+)\s*\((.*)\)\s*:', line)
        if match:
            func, args = match.groups()
            varset.add(func)
            arglist = re.findall(r'(\w+|=)', args)
            for a in arglist:
                if a == '=':
                    break  # keyword args follow - too hard to parse
                varset.add(a)
            continue
        match = re.match(r'(\w+)\s*=.+', line)
        if match:
            assigned = match.group(1)
            varset.add(assigned)
            continue
    return set(v for v in list(varset) if len(v) > 1)

filename = sys.argv[1]
tokenlist = pyparse(open(filename))

# Build map for var->char conversion:
varset = finduservars(filename)
singles = [text for tok,text in tokenlist if tok=='NAME' and len(text)==1]
allvar = [chr(n) for n in range(97,123)+range(65,91)]
charvar = [c for c in allvar if c not in singles]
varreplaced = list(varset)[:len(charvar)]
varmap = dict((v, charvar.pop(0)) for v in varreplaced)

prev = 'NONE'
indent = ['']
output = []
add = output.append
for tok, text in tokenlist:
    if tok == 'NL':
        continue
    elif tok == 'INDENT':
        indent.append( text.replace('    ', ' ') )
        output[-1] = indent[-1]
    elif tok == 'DEDENT':
        indent.pop(-1)
        output[-1] = indent[-1]
    elif tok == 'NEWLINE':
        add(text)
        add(indent[-1])
    elif tok in 'KEYWORD,NAME,NUMBER':
        if prev in 'KEYWORD,NAME,NUMBER':
            add(' ')
        if tok == 'NAME':
            if output[-2] == 'while' and text == 'True':
                add('1') # common verbose idiom
            else:
                add(varmap.get(text, text))
        else:
            add(text)
    else:
        add(text)
    prev = tok

wr(''.join(output))

```

# Answer
> 4 votes
# sed, 1074 (down from 1390)

Very mild, low-hanging-fruit type of answer, to get the ball rolling:

```
/^$/d                  # Remove empty lines
/^[ <--TAB-->]*#/d     # Remove whole-line comments
s/    /<--TAB-->/g     # Replace 4 spaces with tabs
/^[^'"]*$/s/ *([|&:,<>=*/%+-]) */\1/g  # Remove spaces before/after operators

```

Replace `<--TAB-->` with real `TAB` characters

Obvious shortcoming:

* Indents assumed to be exactly 4 spaces in input code.

Since we can assume no multi-line strings, then we only strip leading/trailing spaces from operators if there are no `'` or `"` on the given line. This could be improved, but \<mumbles something about sed regex always being greedy\>.

### Test as follows:

```
$ cat qs.py fizzbuzz.py cards.py | wc -c
1390
$ sed -rf pygolf.sed qs.py fizzbuzz.py cards.py | wc -c
1074
$ sed -rf pygolf.sed qs.py fizzbuzz.py cards.py | python
[-1, 0, 2, 3, 7, 8, 10, 57]
1
2
Fizz
...
98
Fizz
Buzz
Hand 11982
  AH AS 4H AC 2D 6S TS JS
  3D 3H QS QC 8S 7H AD KS
  KD 6H 5S 4D 9H JH 9S 3C
  JC 5D 5C 8C 9D TD KH 7C
  6C 2C TH QH 6D TC 4S 7S
  JD 7D 8H 9C 2H QD 4C 5H
  KC 8D 2S 3S
$

```

# Answer
> 3 votes
# Python 3.4, 1134

This program should work alright for most programs. Strangely, Sp3000 test case is much easier to optimize for my program than your programs. Input is accepted through the file specified in the first argument. The actual file is modified.

```
import subprocess
from sys import argv

progamtext = open(argv[1]).read()

if 'argv' in progamtext or 'input' in progamtext or 'open' in programtext:#Make sure the program always produces the same results.
    exit(0)

program = subprocess.Popen(['C:\Python27\python', argv[1]], stdout=subprocess.PIPE, stderr=subprocess.PIPE)
program.wait()
erroroutput1 = str(program.stderr.read())
output1 = str(program.stdout.read())
program = subprocess.Popen(['C:\Python27\python', argv[1]], stdout=subprocess.PIPE, stderr=subprocess.PIPE)
program.wait()
erroroutput2 = str(program.stderr.read())
output2 = str(program.stdout.read())
if erroroutput1 != erroroutput2 or output1 != output2:#Make sure the program always produces the same results.
    exit(0)

newprog = ''
if erroroutput1:
    newprog += "import sys\n" + "sys.stderr.write("+ erroroutput1 + ')'
    if output1:
        newprog += "\n"
if output1:
    newprog += 'print ' + output1

if len(newprog) > len(progamtext):
    exit(0)

open(argv[1],mode='w').write(newprog)

```

# How it works:

First, this program checks to see if your program interacts with the user at all or uses random. If it does, the program is unmodified. Next, the program is ran. The program is then replaced with `print "output"`. Finally, if the program is shorter than its output, it is unmodified.

Sp3000's program, optimized:

```
import sys
sys.stderr.write(b'')
print b'0.540377721372\r\n3\r\n1\r\n7\r\n99\r\nf\r\n[5, 5]\r\n53\r\n53\r\n53\r\n'

```

Sp3000's super bonus program, optimized:

The optimized version is only off .001% of the time.

```
import sys
sys.stderr.write(b'')
print b'B\r\n'

```

---
Tags: python, metagolf
---


title: Golf me some cash from the ATM

text:
# Question
Title: Golf me some cash from the ATM
The task is simple. Get me some `1000`, `500` and `100` notes.

How ? you might ask. Don't worry, no need of robbing a bank as there is an ATM nearby which accepts your credit card. But your credit limit is just enough for the task so you have to be careful with the withdrawals.

**Challenge**

Given the number of `1000`, `500` and `100` notes required, calculate the specific withdrawals needed to get at least those many notes. In each withdrawal, the ATM can spit out each of the note based on the following rules:

* Amount withdrawn (`A`) is less than `5000`
    + If `A%1000 == 0`, then ATM spits 1 `500` note, 5 `100` notes and rest `1000` notes
    + Else if `A%500 == 0`, the ATM spits 5 `100` notes, rest `1000` notes
    + Else if `A%1000 < 500`, the ATM spits `floor(A/1000)` `1000` notes and rest `100` notes
    + Else if `A%1000 > 500`, the ATM spits `floor(A/1000)` `1000` notes, 1 `500` and rest `100` notes
* Amount withdrawn is greater than equal to `5000`
    + If `A%1000 == 0`, then the ATM spits 2 `500` notes and rest `1000` notes
    + Else if, `A%500 == 0`, the ATM spits 1 `500` note and rest `1000` notes
    + Else if `A%1000 < 500`, the ATM spits `floor(A/1000)` `1000` notes and rest `100` notes
    + Else if `A%1000 > 500`, the ATM spits `floor(A/1000)` `1000` notes, 1 `500` and rest `100` notes

For clarification, here is a complete table of notes withdrawn for all possible amounts up to `7000` (you can withdraw more, but the pattern does not change afterwards). The order is `<1000> <500> <100>`:

```
 100 => 0 0 1                  2500 => 2 0 5                   4800 => 4 1 3
 200 => 0 0 2                  2600 => 2 1 1                   4900 => 4 1 4
 300 => 0 0 3                  2700 => 2 1 2                   5000 => 4 2 0
 400 => 0 0 4                  2800 => 2 1 3                   5100 => 5 0 1
 500 => 0 0 5                  2900 => 2 1 4                   5200 => 5 0 2
 600 => 0 1 1                  3000 => 2 1 5                   5300 => 5 0 3
 700 => 0 1 2                  3100 => 3 0 1                   5400 => 5 0 4
 800 => 0 1 3                  3200 => 3 0 2                   5500 => 5 1 0
 900 => 0 1 4                  3300 => 3 0 3                   5600 => 5 1 1
1000 => 0 1 5                  3400 => 3 0 4                   5700 => 5 1 2
1100 => 1 0 1                  3500 => 3 0 5                   5800 => 5 1 3
1200 => 1 0 2                  3600 => 3 1 1                   5900 => 5 1 4
1300 => 1 0 3                  3700 => 3 1 2                   6000 => 5 2 0
1400 => 1 0 4                  3800 => 3 1 3                   6100 => 6 0 1
1500 => 1 0 5                  3900 => 3 1 4                   6200 => 6 0 2
1600 => 1 1 1                  4000 => 3 1 5                   6300 => 6 0 3
1700 => 1 1 2                  4100 => 4 0 1                   6400 => 6 0 4
1800 => 1 1 3                  4200 => 4 0 2                   6500 => 6 1 0
1900 => 1 1 4                  4300 => 4 0 3                   6600 => 6 1 1
2000 => 1 1 5                  4400 => 4 0 4                   6700 => 6 1 2
2100 => 2 0 1                  4500 => 4 0 5                   6800 => 6 1 3
2200 => 2 0 2                  4600 => 4 1 1                   6900 => 6 1 4
2300 => 2 0 3                  4700 => 4 1 2                   7000 => 6 2 0
2400 => 2 0 4

```

*List provided by Martin*

**The Catch**

Since the credit limit in your credit card is just enough, you need to make sure that the **total amount withdrawn across the withdrawals is the minimum possible** for the given input/requirement of notes.

**Input**

Input can be in any favorable format for three numbers corresponding to the number of notes required of value `1000`, `500` and `100`. Not necessarily in that order.

**Output**

Output is the amount to be withdrawn in each transaction separated by a new line.

**Examples**

Input (format `<1000> <500> <100>`):

```
3 4 1

```

Output:

```
600
600
600
3600

```

few more:

```
7 2 5
5000
3500

1 2 3
600
1700

21 14 2
600
600
600
1600
5000
5000
5000
5000
5000

```

**Assumptions**

* You may assume that the ATM has infinite number of notes of each amount.
* You may also assume that you can make any number of transactions.
* Furthermore, the solution to some input values might not be unique, so you can output any 1 of the solution which fulfills the minimum amount possible and minimum notes required conditions.

As usual, you may write a full program reading input via STDIN/ARGV and printing output to STDOUT or a function taking input via arguments and returns either a list of integer corresponding to the amounts or a string with amounts separated by a new line.

This is code-golf so shortest code in bytes wins.

# Answer
# JavaScript, ~~184~~ 148

```
function g(a,b,c){x=[];while(a>0||b>0||c>0){i=b<3||a<4?a:4;a-=i;if(i>3&&b>1){b-=2;i++}else{i+=(c--<b&&i>4?0:.1)+(b-->0?.5:0)}x.push(i*1e3)}return x}

```

http://jsfiddle.net/vuyv4r0p/2/

returns a list of integers corresponding to the withdrawal amounts
> 8 votes

# Answer
# Perl 5: 223

## Edit

This solution was done with a wrong assumption that 7K is the ATM limit. This actually made the task more interesting as it required dynamic programming (the move pattern was quite regular, but hard-coding it would be likely longer than calculating live as I did). With any amount possible the move pattern is so regular that it is trivial to hard-code it. I don't know if the solution by @hoffmale is now correct, but it will be among these lines. So sadly it will be another task where first somebody comes with a solution and then it gets ported to a golfing language for a win.

A bit slower than the original solution (but still sub-second for parameters below 100).

```
#!perl -pa
$c{0,0}=$f=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/.(?=.$)/>($n=$c{$i-$`,$j-$'})||${$r=\$c{$i,$j}}<($x=$n+$&)&&$$r
or$f=$$r="$x $n".($'.$&+5*$`)."00
"for 204..206,105,106,11..15,110..114}}$_=$f."100
"x($c-$f+3);s/.*\b3//

```

Faster 259 solution.

```
#!perl -pa
$c{0,0}=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/\B./<($%=$c{$i-$&,$j-$'}+$`)&&(!${$r=\$c{$i,$j}}||$$r>$%)and$d{$i,$j}=$_,$$r=$%for
qw/024 025 026 015 016/,101..105,110..114}}
$d{$b,$a}=~/\B./,$c-=$`,$b-=$&,$a-=$',print$'.$`+5*$&,"00
"while$a+$b;$_="100
"x$c

```

Uses STDIN:

```
$perl atm.pl <<<"21 14 2"
5000
5000
5000
5000
5000
600
600
600
1600

```
> 1 votes

---
Tags: code-golf, combinatorics
---


# Question
Title: "Compile" a simple C program inside a different language
Your task is to take the following simple C code and make a program which will interpret this code and produce a correct output, and be able to handle small modifications to the original code. The C code is

```
int x = 4;
int y = 5;
int z;

z = x * y;

if(z>10)
{
    printf("%d is bigger than 10!",z);
}

```

Or as one line of text.

```
int x = 4; int y = 5; int z; z = x * y; if(z>10){ printf("%d is bigger than 10!",z); }

```

The program must satisfy the following conditions:

* x and y can be changed to any integer.
* "is bigger than 10!" must not be printed if z is smaller than 10.
* The value of 10 can be changed to any integer (not including the 10 in the printed text).
* The program must be able to read the c program in as one line of text.
* Adding spaces shouldn't break the program.

The winning solution is the shortest code to satisfy the criteria. Libraries are not allowed.

# Answer
# Perl 5, 76 bytes

```
$_=<>,s/ //g,s/[=>](-?\d+)/$.*=$1/ge,($./=$1)>$1&&say"$. is bigger than $1!"

```

Input must be in one line. Negative integers are allowed. Tabs may break program (but spaces are fine, even between `-` and the number).

**Ungolfed:**

```
$_ = <>; # read input
# $. = 1; $. is the number of lines read on STDIN, which should be 1.
s/ //g; # remove whitespace from $_
s/[=>](-?\d+)/ $. *= $1 /ge; # get product of all integers after = or >
$. /= $1; # divide away the last integer found (inside the if)
if($. > $1){
   say "$. is bigger than $1";
}

```

This simply extracts the integers and does the product/comparison afterwards.

**Example**:

```
$ perl -E '$_=<>,s/ //g,s/[=>](-?\d+)/$.*=$1/ge,($./=$1)>$1&&say"$. is bigger than $1!"'
> int x =4; int y = -  5 ; int f0_23; f0_23 = x* y ; if ( f0_23> -  30){ printf("%d is bigger than 10!",f0_23) ;  }
-20 is bigger than -30!

```
> 1 votes

---
Tags: code-golf
---


title: Hereditary Base Change

text:
# Question
Title: Hereditary Base Change
# Background

In this challenge, a *base-`b` representation* of an integer `n` is an expression of `n` as a sum of powers of `b`, where each term occurs at most `b-1` times. For example, the base-`4` representation of `2015` is

```
4^5 + 3*4^4 + 3*4^3 + 4^2 + 3*4 + 3

```

Now, the *hereditary* base-`b` representation of `n` is obtained by converting the exponents into their base-`b` representations, then converting their exponents, and so on recursively. Thus the hereditary base-`4` representation of `2015` is

```
4^(4 + 1) + 3*4^4 + 3*4^3 + 4^2 + 3*4 + 3

```

As a more complex example, the hereditary base-`3` representation of

```
7981676788374679859068493351144698070458

```

is

```
2*3^(3^(3 + 1) + 2) + 3 + 1

```

The *hereditary base change of `n` from `b` to `c`*, denoted `H(b, c, n)`, is the number obtained by taking the hereditary base-`b` representation of `n`, replacing every `b` by `c`, and evaluating the resulting expression. For example, the value of

```
H(3, 2, 7981676788374679859068493351144698070458)

```

is

```
2*2^(2^(2 + 1) + 2) + 2 + 1 = 2051

```

# The Challenge

You are given as input three integers `b`, `c`, `n`, for which you may assume `n >= 0` and `b, c > 1`. Your output is `H(b, c, n)`. The shortest byte count wins, and standard loopholes are disallowed. You can write either a function or a full program. You must be able to handle arbitrarily large inputs and outputs (bignums).

# Test Cases

```
4 2 3 -> 3
2 4 3 -> 5
2 4 10 -> 1028
4 4 40000 -> 40000
4 5 40000 -> 906375
5 4 40000 -> 3584
3 2 7981676788374679859068493351144698070458 -> 56761
2 3 2051 -> 35917545547686059365808220080151141317047

```

### Fun Fact

For any integer `n`, the sequence obtained by

```
n1 = n
n2 = H(2, 3, n1) - 1
n3 = H(3, 4, n2) - 1
n4 = H(4, 5, n3) - 1
....

```

eventually reaches `0`. This is known as Goodstein's theorem.

# Answer
> 6 votes
# CJam, ~~60~~ ~~58~~ ~~45~~ ~~43~~ ~~41~~ ~~38~~ 36 bytes

Thanks to Optimizer for saving two bytes.

```
l~:C;:B;{Bb)1$,,@f{1$~=C@)F#*+}~}:F~

```

Test it here.

Takes input in order `n b c`.

You can use this to test run all test cases:

```
"3 4 2
3 2 4
10 2 4
40000 4 4
40000 4 5
40000 5 4
7981676788374679859068493351144698070458 3 2
2051 2 3 "N/
{
~:C;:B;{Bb)1$,,@f{1$~=C@)F#*+}~}:F~
p}/

```

## Explanation

This is a fairly direct implementation of the process explained in the challenge, except that I interleave recursive base expansion, base substitution and computation of the final result:

```
l~:C;:B;{Bb)1$,,@f{1$~=C@)F#*+}~}:F~
l~:C;:B;                             "Read and evaluate input, store b and c in B and C.";
        {                       }:F  "Define a block F. This performs the required conversion.";
         Bb                          "Get digits of input number in base B.";
           )                         "Split off 0-power digit.";
            1$,                      "Copy remaining digits. Get their length n.";
               ,                     "Make array [0 1 ... n-1].";
                @                    "Pull up remaining digits.";
                 f{           }      "Map this block onto the range, passing in the digits
                                      as a second argument each time.";
                   1$~=              "Copy current i, bitwise complement, access digit array.
                                      This accesses the digits in reverse order.";
                       C             "Push the new base C.";
                        @)           "Pull up current i and increment to get power.";
                          F          "Apply F recursively.":
                           ~         "Raise C to the resulting power.";
                            *        "Multiply by digit.";
                             +       "Add to running total.";
                               ~     "The result will be in an array. Unwrap it.";
                                   ~ "Execute F on the input n.";

```

# Answer
> 8 votes
# Python 2, 55

```
H=lambda b,c,n,s=0:n and n%b*c**H(b,c,s)+H(b,c,n/b,s+1)

```

A recursive solution. Like the recursive algorithm to convert between bases, except it recurses on the exponent as well.

We split `n` into two parts, the current digit `n%b`, and all other digits `n/b`. The current place value is stored in the optional parameter `s`. The current digit is converted to base `c` with `c**` and the exponent `s` is converted recursively. The remainder is then converted the same way, as `+H(b,c,n/b,s+1)` but the place value `s` is one higher.

Unlike base conversion, hereditary base conversion required remembering the current place value in the recursion for it to converted.

For ease of reading, here's what it looks like when `b` and `c` are fixed global constants.

```
H=lambda n,s=0:n and n%b*c**H(s)+H(n/b,s+1)

```

---
Tags: code-golf, arithmetic, base-conversion
---


title: 0-1 Maximal Phase Counter

text:
# Question
Title: 0-1 Maximal Phase Counter
Consider an array of bits, say

```
1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0

```

We call a contiguous subarray of length ≥ 5 a **phase** if at least 85% of the bits are the same and the first/last bits are both equal to the majority bit. Furthermore, we call a phase **maximal** if it is not a strict subarray of some other phase.

Here are the maximal phases of the above example:

```
1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0
      -------------
                    -------------
                        -------------

```

As you can see, there are `3` maximal phases. On the other hand, this

```
1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0
                        ---------

```

is not a maximal phase as it is a strict subarray of at least one other phase.

## The challenge

Input is a sequence of ≥ 5 bits via STDIN, command line or function argument. The bits may come in as a string or an array.

You are to output a single integer, the number of maximal phases for the array, either printed via STDOUT or returned from a function.

## Scoring

This is code-golf so the program in the fewest bytes wins.

## Test cases

```
0 1 0 1 0 -> 0
0 0 0 0 0 -> 1
0 0 0 0 1 0 1 1 1 1 -> 0
0 0 0 0 0 1 0 1 1 1 1 1 -> 2
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 -> 1
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 -> 2
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 -> 1
0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 -> 0
1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 -> 4
0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 -> 5

```

Here's the explanation for the last case:

```
0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0
---------------------------
      -------------------------
                            -----------------
                                -----------------
                                              -------------

```

Fun fact: This challenge came about from a data mining problem with the goal of detecting change in temporal data.

# Answer
# Dyalog APL, 62 characters

`{≢∪0~⍨+/∨⍀∨\⌽∘.{((⊃=⊃∘⌽)∧(.85≤(+/⊢=⊃)÷≢)∧5≤≢)(⍺-1)↓⍵↑a}⍨⍳⍴a←⍵}`

Similar to Zgarb's solution but golfed a little further.
> 4 votes

# Answer
## Python 2, 149 bytes

```
a=input()
l=len(a)
n=p=0
for i in range(l):
 for j in range(l-1,i+3,-1):
  if(j>p)>(.15<sum(a[i:j+1])/(j+1.-i)+a[i]+a[j]<2.85):n+=1;p=j;break
print n

```

The first loop scans across the array from left to right. Each bit, indexed by `i`, is checked to see if it could be the first bit in a maximal phase.

This is done by the inner loop, which scans from right to left. If the subarray between `i` and `j` is a phase, we increase the counter and move on. Otherwise, we keep going until the subarray becomes too small *or* `j` reaches the end of the previous maximal phase.

```
1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0
i ->                               <- j

```

Example:

```
$ python phase.py
[1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]
3

```
> 8 votes

# Answer
# Python 2, 144

Enter input in the form `[0,1,0,1,0]`.

```
a=input()
o=[2];i=-1
while a[i:]:
 j=len(a);i+=1
 while j>i+4:o+=sum(j>max(o)>x==a[i]==a[j-1]for x in a[i:j])*20/(j-i)/17*[j];j-=1
print~-len(o)

```

Subsequences are checked with ordering by increasing initial element, then decreasing length. In this way, it is known that a new subsequence is not a subsequence of a previous subsequence iff the index of its last element is greater than any index of a previously found sequence's last element.
> 5 votes

# Answer
# Dyalog APL, 86 bytes\*

```
{+/∨/¨∪↓∨⍀∨\{⊃({(.5>|k-⍵)∧.35≤|.5-⍵}(+/÷⍴)⍵)∧(5≤⍴⍵)∧(⊃⌽⍵)=k←⊃⍵}¨⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵}

```

Try it here. Usage:

```
   f ← {+/∨/¨∪↓∨⍀∨\{⊃({(.5>|k-⍵)∧.35≤|.5-⍵}(+/÷⍴)⍵)∧(5≤⍴⍵)∧(⊃⌽⍵)=k←⊃⍵}¨⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵}
   f 0 0 0 0 0 1 0 1 1 1 1 1
2

```

This can probably be golfed quite a bit, especially the middle part, where the phase condition is checked.

### Explanation

I first collect the substrings of the input vector into a matrix, where the upper left corner contains the whole input, using `⌽∘.{(⍺-1)↓⍵↑t}⍨⍳⍴t←⍵`. For the input `0 0 0 0 0 1 0`, this matrix is

```
┌───────────────┬─────────────┬───────────┬─────────┬───────┬─────┬───┬─┐
│1 0 0 0 0 0 1 0│1 0 0 0 0 0 1│1 0 0 0 0 0│1 0 0 0 0│1 0 0 0│1 0 0│1 0│1│
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 0 0 0 1 0  │0 0 0 0 0 1  │0 0 0 0 0  │0 0 0 0  │0 0 0  │0 0  │0  │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 0 0 1 0    │0 0 0 0 1    │0 0 0 0    │0 0 0    │0 0    │0    │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 0 1 0      │0 0 0 1      │0 0 0      │0 0      │0      │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 0 1 0        │0 0 1        │0 0        │0        │       │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0 1 0          │0 1          │0          │         │       │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│1 0            │1            │           │         │       │     │   │ │
├───────────────┼─────────────┼───────────┼─────────┼───────┼─────┼───┼─┤
│0              │             │           │         │       │     │   │ │
└───────────────┴─────────────┴───────────┴─────────┴───────┴─────┴───┴─┘

```

Then I map the condition of being a phase over it, resulting in the 0-1-matrix

```
0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

```

To get the number of maximal phases, I flood the `1`'s to the right and down using `∨⍀∨\`,

```
0 0 0 0 0 0 0 0
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

```

collect the unique rows with `∪↓`,

```
┌───────────────┬───────────────┐
│0 0 0 0 0 0 0 0│1 1 1 1 1 1 1 1│
└───────────────┴───────────────┘

```

and count those that contain at least one `1` using `+/∨/¨`.

\*There exists a standard 1-byte encoding for APL.
> 4 votes

# Answer
# Clojure, 302

```
(defn p[v l](if(or(<(count v)5)(= 0 l))nil(if((fn[v](let[f(first v)c(apply + v)o(count v)r(/ c o)t(+ f f r)](and(= f(last v))(or(> t 2.85)(< t 0.15)))))v)0(let[r(p(vec(drop-last v))(dec l))](if r(+ r 1)r)))))(defn s[v l c](if(empty? v)c(let[n(p v l)](if n(s(vec(rest v))n(inc c))(s(vec(rest v))l c)))))

```

and the slightly ungolfed version

```
(defn is-phase [vector]
  (let [f (first vector)
        c (apply + vector)
        o (count vector)
        r (/ c o)
        t (+ f f r)]
    (and (= f (last vector))
         (or (> t 2.85) (< t 0.15)))))
(defn phase-index [vector last]
  (if (or (<(count vector)5)(= 0 last)) nil
    (if (is-phase vector) 0
      (let [r (phase-index (vec(drop-last vector)) (dec last))]
        (if r (+ r 1) r)))))
(defn phase-count [vector last count]
  (if (empty? vector) count
    (let [n (phase-index vector last)]
         (if n (phase-count (vec(rest vector)) n (inc count))
             (phase-count (vec(rest vector)) last count)))))

```

callable like this: `(s [0 1 0 1 0] 10 0)`. It requires a few extra arguments, but I could get rid of those with an extra 20 characters.
> 1 votes

# Answer
# JavaScript (ES6) 141

@grc's algorithm ported to JavaScript
Input can be a string or an array

```
F=b=>
  (l=>{
    for(c=e=i=0;i<l;++i)
      for(j=l;j>i+4&j>e;--j)
        (k=0,[for(d of b.slice(i,j))k+=d==b[i]],k<(j-i)*.85)|b[i]-b[j-1]||(++c,e=j)
  })(b.length)|c

```

**Test** In FireFox / FireBug console

```
;['01010', '00000', '0000101111',
'000001011111', '100000000000010',
'0000010000010000010', '00000100000100000100',
'010100101010001111010011000110',
'111110000011111001000000001101',
'011000000000001011111110100000'].forEach(t => console.log(t,F(t)))

```

*Output*

```
01010 0
00000 1
0000101111 0
000001011111 2
100000000000010 1
0000010000010000010 2
00000100000100000100 1
010100101010001111010011000110 0
111110000011111001000000001101 4
011000000000001011111110100000 5

```
> 0 votes

# Answer
# JavaScript (ECMAScript 6), ~~148~~ 139 Bytes

```
f=(s,l=0,e=0,p=0)=>{for(n=s.length,o=[j=0,y=0],i=l;i<n;++j>4&x==s[l]&i>e&c>=.85*j&&(e=i,y=1))c=++o[x=s[i++]];return l-n?f(s,l+1,e,p+y):p}

```

Recurses through the array and starts iteration at the last recursion index. Argument can be either an array or string.

```
f('011000000000001011111110100000'); //5

```
> 0 votes

# Answer
# CJam, ~~110~~ 103 bytes

Pretttttty long. Can be golfed a lot.

```
q~_,,\f>{_,),5>\f<{:X)\0==X1b_X,.85*<!\.15X,*>!X0=!*\X0=*+&},:,W>U):U+}%{,(},_{{_W=IW=>\1bI1b>!&!},}fI,

```

Input is like

```
[0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0]

```

Output is the number of phases.

Try it online here
> 0 votes

# Answer
# Wolfram - 131

```
{x_, X___}⊕{Y__, x_, y___}/;MemberQ[t={x, X, Y, x}, 1-x] && t~Count~x > .85 Length@t :=
  1 + {X, Y, x}⊕{y}
{_, X___}⊕y_ := {X}⊕y
{}⊕{y_, Y__} := {y}⊕{Y}
_⊕_ := 0

```

Example

```
{}⊕{1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0}
> 3
{}⊕{0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0}
> 5

```
> 0 votes

# Answer
## Java: 771 bytes

```
import java.util.*;public class A{static int[]a;static class b{int c,d,e,f,g,h;b(int i,int j){this.c=i;this.d=j;this.h=j-i+1;this.e=k();this.f=this.h-this.e;this.g=e>f?1:0;}
boolean l(b n){return this.c>=n.c&&this.d<=n.d;}
int k(){int o=0;for(int i=c;i<=d;i++){if(a[i]==1){o++;}}
return o;}
public boolean equals(Object o){b x=(b)o;return x.c==this.c&&x.d==this.d;}
float p(){if(g==0){return(float)f/h;}else{return(float)e/h;}}
boolean q(){float r=p();return a[c]==a[d]&&a[d]==g&&r>=0.85F;}}
static int s(int[]t){a=t;List<b>u=new ArrayList<>();for(int v=0;v<t.length-4;v++){int x=v+4;while(x<t.length){b y=new b(v,x);if(y.q()){u.add(y);}
x++;}}
List<b>a=new ArrayList<>();for(b c:u){for(b d:u){if(!c.equals(d)&&c.l(d)){a.add(c);break;}}}
u.removeAll(a);return u.size();}}

```

run by calling method s(int\[\] input)
> 0 votes

---
Tags: code-golf, array
---


title: Retrograde morse (d)e(n)coder

text:
# Question
Title: Retrograde morse (d)e(n)coder
This question is inspired by retrograde music. Retrograde music is a piece of music that can both be played normally (from the beginning to the end) as reversed (from the end the beginning). A similar thing exists in literature, this is called a semi-palindrome, e.g. "roma" and "amor". Your task is to write a retrograde program. If executed normally it has to encode a string with the morse code, decode it when executed reversed.

# Task

You're to write a program or function that accepts a string and outputs it's morse code encoding (STDIN and STDOUT are used in case of a program, a function receives it's input as a function argument and returns a string). However, when you run the reverse of the program, it works the same except it decodes the input. Note that you don't have to use the same programming language. The reversing of the program is done manually.

# Details

* Comments are not allowed in your program, as they would make this task very easy.
* You have to use the international morse code. This includes letters, numbers and some punctuation. See the link for a complete list. No prosigns or special characters have to be supported. There's one exception mentioned in the edit.
* You have to represent dots and dashes with `.` and `-`.
* Letters are separated with  (spaces), words are separated with `/` (slashes).
* You can choose to use either use lower or uppercase. However, you have to be consistent (if your program only uses uppercase, the reversed program must do so too).
* You can assume the program will only receive valid input.

# Example

Input of the normal program or output of the reversed program:

```
MORSE CODE?

```

Output of the normal program or input of the reversed program:

```
-- --- .-. ... . / -.-. --- -.. . ..--..

```

# Score

Because I want to reward both clever (short) algorithms and creativity, Your score will be based upon your votes and the program length. Concretely, it will be `100 * amount of votes / program length (in bytes)`

**EDIT**: The morse code site I mentioned uses the same code for opening and closing parentheses, however it's not my intention to let you implement a feature for recognizing this. So you have to use these more modern morse codes for the parentheses:

```
( = -.--.
) = -.--.-

```

# Answer
# CJam, ~~349~~ 284 bytes

This is the encoder from plaintext to International Morse code:

```
L;"q['[,65>A,841306689079511650 64b:c]s"~"*S/as/'res]c:b46 056115970986603148,A>56,['[/,'c:+f34b4i%Ws;\\";L
2750763932992480612976738964894343100372667569857057816704667471637641979761595859190213443543359288493237588430216583759463627409436875398907
L;"\\;4b43f+:c',/erS/'/*S*"~"/Sq";L

```

The reverse string of which is:

```
L;"qS/"~"*S*/'/Sre/,'c:+f34b4;\\";L
7098935786349047263649573856120348857323948829533453443120919585951679791467361747664076187507589657662730013434984698376792160842992393670572
L;"\\;sW%i4b43f+:c',/['[,65>A,841306689079511650 64b:c]ser'/sa/S*"~"s]c:b46 056115970986603148,A>56,['[q";L

```

which decodes an International Morse Code representation back to plain text.

(New lines just for show)

This supports capital alphabets `A-Z`, number `0-9` and `.,:?'-/()"` punctuation marks, where Morse Code for `(` and `)` is same.

How it works:

The trick here is simple, CJam supports evaluation of any random string as a code using the operator `~`. So if you have something like `"code in a string"~"another code in a string"`, then when running normally, the first string will be evaluated while the second one will remain a string. But when running the reverse of the code, the second string will be evaluated, while the first will remain a string.

So now you just have to make sure that you have your code in the above format along with a logic to remove the second string while running in normal fashion and the first string while running the reverse code. This gives us something like:

```
];"code for encoding to morse"~"reverse of code for decoding from morse";]

```

whose reverse will be

```
];"code for decoding from morse"~"reverse of code for encoding to morse";]

```

This works like:

```
];                                "Create an empty array and pop it from stack";
  "code 1"~                       "Put a string with code 1 and evaluate it";
           "code 2";              "Put the string for code 2 and pop it from stack";
                    ]             "Wrap everything in an array. Noop as last operation";

```

The reverse of it is just code 1 replaced by reverse of code 2 and vice-versa, so it works in a similar manner.

Now the actual code which encodes/decodes is a simple transliteration from the plaintext to morse and vice-versa.

Try it online here
> 3 votes

# Answer
# Perl 5: too long to care (740 though)

Just wanted to see if it will be possible to write this in a language with non single character statements. The result is not pretty, but works. Most of the code is used in both decoder and encoder, but the `eval+'{code}'` trick shows a loophole which could be used to write completely separate code for decoder and encoder.

Fixed all known problems. Supports both lower and upper case input with all punctuation characters mentioned on the page linked in the question.

Encoder:

;;$^;s,.*,reverse+uc,e;
tr,+?.(),+~=<>,+rt;
1while+s/E/#_/s+s/T/`_/s+s! !{_!s+elihw1;
1while+s/A/`#_/s+s/N/#`_/s+s/I/##_/s+s/M/``_/s+elihw1;
1while+s/O/```_/s+s/D/##`_/s+s/R/#`#_/s+s/S/###_/s
      +s/G/#``_/s+s/U/`##_/s+s/W/``#_/s+s/K/`#`_/s+elihw1;
1while+s/B/###`_/s+s/C/#`#`_/s+s/P/#``#_/s+s/Q/`#``_/s
      +s/F/#`##_/s+s/H/####_/s+s/V/`###_/s+s/J/```#_/s
      +s/X/`##`_/s+s/L/##`#_/s+s/Y/``#`_/s+s/Z/##``_/s+elihw1;
1while+s/1/````#_/s+s/2/```##_/s+s/3/``###_/s+s!<!#``#`_!s
      +s/4/`####_/s+s/5/#####_/s+s/6/####`_/s+s/7/###``_/s
      +s/8/##```_/s+s/9/#````_/s+s/0/`````_/s+s!/!#`##`_!s+elihw1;
1while+s/~/##``##_/s+s/=/`#`#`#_/s+s/,/``##``_/s
      +s/:/###```_/s+s/'/#````#_/s+s/"/#`##`#_/s
      +s/-/`####`_/s+s!>!`#``#`_!s+elihw1;
tr,+{`#_,+/\-\. ,+rt;
;;$^;s,.*,reverse,e;
s/ //s
</code></pre>

Decoder:

<pre><code>s// /s
;e,esrever,*.,s;^$;;
;tr+, .\-\/+,_#`{+,rt
;1while+s!_`#``#`!>!s+s/_`####`/-/s+
s/_#`##`#/"/s+s/_#````#/'/s+s/_```###/:/s+
s/_``##``/,/s+s/_#`#`#`/=/s+s/_##``##/~/s+elihw1
;1while+s!_`##`#!/!s+s/_`````/0/s+s/_````#/9/s+s/_```##/8/s+
s/_``###/7/s+s/_`####/6/s+s/_#####/5/s+s/_####`/4/s+
s!_`#``#!<!s+s/_###``/3/s+s/_##```/2/s+s/_#````/1/s+elihw1
;1while+s/_``##/Z/s+s/_`#``/Y/s+s/_#`##/L/s+s/_`##`/X/s+
s/_#```/J/s+s/_###`/V/s+s/_####/H/s+s/_##`#/F/s+
s/_``#`/Q/s+s/_#``#/P/s+s/_`#`#/C/s+s/_`###/B/s+elihw1
;1while+s/_`#`/K/s+s/_#``/W/s+s/_##`/U/s+s/_``#/G/s+
s/_###/S/s+s/_#`#/R/s+s/_`##/D/s+s/_```/O/s+elihw1
;1while+s/_``/M/s+s/_##/I/s+s/_`#/N/s+s/_#`/A/s+elihw1
;1while+s!_{! !s+s/_`/T/s+s/_#/E/s+elihw1
;tr+,><=~+,)(.?+,rt
;e,cu+esrever,*.,s;^$;;

Usage

```
$ perl -lp retr.pl <<<"(Morse) Code?"
-.--. -- --- .-. ... . -.--.- / -.-. --- -.. . ..--..
$ perl -p0e '$_=reverse' retr.pl >rter.pl
$ perl -lp rter.pl <<<"-.--. -- --- .-. ... . -.--.- / -.-. --- -.. . ..--.."
(MORSE) CODE?

```

Explanation:

```
;;$^;s,.*,reverse+uc,e; # parses as $^; s/.*/reverse uc/e
                        # and in decoder as e; cu + esrever; *.; s/^$//
                        # reverse and uppercase input, no-op in decoder
tr,+?.(),+~=<>,+rt;     # parses as tr/+?()/+=<>/ + rt
                        # in decoder as tr/,><=~/,)(.?/ , rt
                        # equivalent to y/?.()/~=<>/ and y/><=~/)(.?/ in decoder
1while+s/T/`_/s+elihw1; # parses as while(+s/T/`_/+elihw1){1}
                        #        => while(s/T/`_/s+0){}
                        # equivalent to s/T/`_/g and s/_`/T/g in decoder
s/ //s                  # remove leading space / add leading space

```
> 4 votes

# Answer
# CJam, 286 bytes, no eval

Original (Morse encoder):

```
L;"'*S/as/'res]c:b46 056115970986603148,A>56,['[/,'c:+f34b4i%Ws;\;";q['[,65>A,841306689079511650 64b:c]s'";L
2750763932992480612976738964894343100372667569857057816704667471637641979761595859190213443543359288493237588430216583759463627409436875398907
L;"'/Sq;";\;4b43f+:c',/erS/'/*S*'";L

```

Reversed (Morse decoder):

```
L;"'*S*/'/Sre/,'c:+f34b4;\;";qS/'";L
7098935786349047263649573856120348857323948829533453443120919585951679791467361747664076187507589657662730013434984698376792160842992393670572
L;"'s]c:b46 056115970986603148,A>56,['[q;";\;sW%i4b43f+:c',/['[,65>A,841306689079511650 64b:c]ser'/sa/S*'";L

```

This is just a trivial tweak of Optimizer's solution to eliminate the string eval (`~`), in response to a meta post asserting that "\[the\] use of eval statements is what makes this abuse possible". Accordingly, as it's mostly not my own code, I have marked it as Community Wiki.

Instead of Optimizer's trick of placing the eval operator `~` between two quoted strings, like this:

```
L;"encoder"~"reversed decoder";L

```

my version relies on the fact that, in CJam, *any* character following a single quote (`'`) is interpreted as a character literal:

```
L;"'reversed decoder;";encoder'";L

```

Relevant CJam speed-tutorial: `L` is an empty string, `"..."` is a double-quoted string, `'"` is a literal double quote, and `;` pops the most recent value off the stack. Thus, this code first pushes an empty string, pops it, pushes the string `'reversed decoder;`, pops it, executes `encoder`, pushes another double quote, pops it, and pushes an empty string (which has no effect on the output).

**Update:** Saved 8 bytes by a trivial (in hindsight) optimization. With the further saving from eliminating needless backslashed, this is now just two bytes longer than Optimizer's original eval-based solution.
> 2 votes

---
Tags: code-challenge, string, source-layout, palindrome, morse
---


title: Go and make it starry

text:
# Question
Title: Go and make it starry
In this contest you have to write a program, that accepts a black and white pixel image, and tries to alter it, such that the white shape forms **star domain**, with as few changes as possible.

Allowed changes are turning white pixels into black ones and turning black pixels into white ones.

The output must again consist of the same image but this time with all the changes and with a/the center marked. The pixels that were changed from white to black must be displayed in blue, the ones that were changed from black to white must be displayed in yellow, and at least one center pixel must be displayed in red. (Exact colours are up to you.) The program must ouput the specified image as well as the total number of changes that were made.

# Definitions

### Star Domain

The set of white pixels of the image represent a **star domain** if (and only if) there is (at least) one **center pixel**. The **center pixel** is one of the white pixels that can be conneced by a **straight line** to all of the other white pixels such that the line only traverses white pixels. (The **center pixel** is therefore not necessarily unique.)

### Straight line between two pixels

Given two pixel (start and end, both red in the illustration below), the **straigth line** between the two pixels consists of all the pixels, that touch the (mathematical, yellow in the illustration below) line that leads from the center of the first pixel to the center of the last pixel. A pixel is *not* touching the line if it only touches it by a corner, so for a pixel to belong to the *pixel line* the (mathematical, yellow) line has to cross the pixel in question with a nonzero length. (If it only touches the corner point this is considered as length zero). Consider the following examples:

# Example

The first image should represent an example testcase 'input' and the two other images represent two valid possible outputs for the given example:

The yellow areas (formerly black) count to the 'white' domain as well, while the blue areas (formerly white) count to the 'black' part outside of the domain, and the red dot each time represents one possible center pixel.

# Test Cases

The follwoing test cases are png's with each a size of 256 x 256 pixels.

# Scoring

Please run your program with the following test cases and include the output (image / number of changes) in your answer. I will make a leaderboard for each test case. Your score will be the sum of each ranking in the leaderboard -the lower the score the better. Standard loopholes apply. It is not allowed to make the program recognize those test cases and run a special case for them. (It is not allowed to precompute and save the optimal center pixels for each of those test cases.) The program should work for any images.

# Leaderboard

```
Name        | Score | 1     - rk | 2     - rk | 3     - rk | 4     - rk | 5     - rk | 5     - rk | Total Changes
------------+-------+------------+------------+------------+------------+------------+------------+--------------
Maltysen    |    11 | 28688 -  2 | 24208 -  2 | 24248 -  1 |  7103 -  2 | 11097 -  2 | 13019 -  2 | 108363
TheBestOne  |     7 | 0     -  1 | 13698 -  1 | 24269 -  2 |   103 -  1 |  5344 -  1 |  4456 -  1 |  47867

```

# Answer
# Java 8, 47,867 changes total.

Uses the average of the image as the center point. It then draws all possible rays to the center and gives it the best radius to color. It then colors all invalid points black.

```
import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class MakeItStarry {

    private static final int RGB_RED = Color.RED.getRGB();
    static int[][] originalImage;

    static final int WHITE = 0;
    static final int BLACK = 1;
    static final int RGB_WHITE = Color.WHITE.getRGB();
    static final int RGB_BLACK = Color.BLACK.getRGB();
    static final int RGB_BLUE = Color.BLUE.getRGB();
    static final int RGB_YELLOW = Color.YELLOW.getRGB();

    public static void main(String[] args) throws Exception{
        originalImage = convert(ImageIO.read(new File(args[0])));
        Point center = findCenter(originalImage);
        int[][] nextImage = starry(originalImage, center);
        BufferedImage result = difference(originalImage, nextImage);
        result.setRGB(center.x, center.y, RGB_RED);
        String fileType;
        String fileName;
        if (args[1].split("\\.").length > 1){
            fileType = args[1].split("\\.")[1];
            fileName = args[1];
        } else {
            fileType = "PNG";
            fileName = args[1] + ".PNG";
        }
        ImageIO.write(result, fileType, new File(fileName));
        System.out.println(cost);
    }

    static int cost;

    private static BufferedImage difference(int[][] image1, int[][] image2) {
        cost = 0;
        int height = image1[0].length;
        int width = image1.length;
        BufferedImage result = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < width; x++){
            for (int y = 0; y < width; y++){
                if (image1[x][y] == image2[x][y]){
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_WHITE);
                    } else {
                        result.setRGB(x, y, RGB_BLACK);
                    }
                } else {
                    cost++;
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_BLUE);
                    } else {
                        result.setRGB(x, y, RGB_YELLOW);
                    }
                }
            }
        }
        return result;
    }

    private static int[][] starry(int[][] image, Point center) {
        int width = image.length;
        int height = image[0].length;
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                result[x][y] = BLACK;
            }
        }
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++) {
                Point endPoint = new Point(x, y, image);
                List<Point> line = Point.lineTo(center, endPoint, image);
                List<Point> newLine = starRay(line);
                newLine.stream().filter(point -> result[point.x][point.y] == BLACK).forEach(point -> {
                    result[point.x][point.y] = point.color;
                });
            }
        }
        int distance = 0;
        while (distance < height || distance < width){//This removes pixels that can't see the center.
            for (int x = Math.max(center.x - distance,0); x < center.x + distance && x < width; x++){
                for (int y = Math.max(center.y - distance, 0); y < center.y + distance && y < height; y++){
                    Point point = new Point(x, y, result);
                    if (Point.distance(center, point) != distance){
                        continue;
                    }
                    if (point.color == WHITE){
                        List<Point> line = Point.lineTo(center, point, result);
                        for (Point p : line){
                            if (p.color == BLACK){
                                point.color = BLACK;
                                break;
                            }
                        }
                        result[point.x][point.y] = point.color;
                    }
                }
            }//All white pixels can technically see the center but only if looking from the edge.
            distance++;
        }
        return result;
    }

    private static List<Point> starRay(List<Point> line) {
        int numOfWhites = 0;
        int farthestGoodPoint = 0;
        int blackCost = 0;
        int whiteCost = 0;
        for (int i = 0; i < line.size(); i++){
            if (line.get(i).color == WHITE){
                numOfWhites++;
                whiteCost++;
                if (numOfWhites + whiteCost > blackCost){
                    blackCost = 0;
                    whiteCost = 0;
                    farthestGoodPoint = i;
                }
            } else {
                blackCost++;
                numOfWhites = 0;
            }
        }
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < line.size(); i++){
            Point p = line.get(i);
            if (i <= farthestGoodPoint){
                result.add(new Point(p.x, p.y, WHITE));
            } else {
                result.add(new Point(p.x, p.y, BLACK));
            }
        }
        return result;
    }

    private static Point findCenter(int[][] image) {
        double totalx = 0;
        double totaly = 0;
        int counter = 0;
        int width = image.length;
        int height = image[0].length;
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image[x][y] == WHITE){
                    totalx += x;
                    totaly += y;
                    counter++;
                }
            }
        }
        return new Point((int)(totalx/counter), (int)(totaly/counter), image);
    }

    private static int[][] convert(BufferedImage image) {
        int width = image.getWidth();
        int height  = image.getHeight();
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image.getRGB(x, y) == RGB_WHITE){
                    result[x][y] = WHITE;
                } else {
                    result[x][y] = BLACK;
                }
            }
        }
        return result;
    }

    private static class Point {

        public int color;
        public int y;
        public int x;

        public Point(int x, int y, int[][] image) {
            this.x = x;
            this.y = y;
            this.color = image[x][y];
        }

        public Point(int x, int y, int color) {
            this.x = x;
            this.y = y;
            this.color = color;
        }

        public static List<Point> lineTo(Point point1, Point point2, int[][] image) {
            List<Point> result = new ArrayList<>();
            boolean reversed = false;
            if (point1.x > point2.x){
                Point buffer = point1;
                point1 = point2;
                point2 = buffer;
                reversed = !reversed;
            }
            int rise = point1.y - point2.y;
            int run = point1.x - point2.x;
            if (run == 0){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int x = point1.x;
                for (int y = point1.y; y <= point2.y; y++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            if (rise == 0){
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int y = point1.y;
                for (int x = point1.x; x <= point2.x; x++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            int gcd = gcd(rise, run);
            rise /= gcd;
            run /= gcd;
            double slope = (rise + 0.0) / run;
            if (Math.abs(rise) >= Math.abs(run)){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double x = point1.x;
                for (double y = point1.y + .5; y <= point2.y; y++){
                    int px = (int) Math.round(x);
                    if (Math.abs(Math.abs(px - x) - .5) < Math.abs(1.0 / (rise * 4))){
                        x += 1/slope;
                        continue;
                    }
                    result.add(new Point(px, (int) Math.round(y - .5), image));
                    result.add(new Point(px, (int) Math.round(y + .5), image));
                    x += 1/slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            } else {
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double y = point1.y;
                for (double x = point1.x + .5; x <= point2.x; x++){
                    int py = (int) Math.round(y);
                    if (Math.abs(Math.abs(py - y) - .5) < Math.abs(1.0 / (run * 4))) {
                        y += slope;
                        continue;
                    }
                    result.add(new Point((int) Math.round(x - .5), py, image));
                    result.add(new Point((int) Math.round(x + .5), py, image));
                    y += slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
        }

        private static List<Point> reversed(List<Point> points) {
            List<Point> result = new ArrayList<>();
            for (int i = points.size() - 1; i >= 0; i--){
                result.add(points.get(i));
            }
            return result;
        }

        private static int gcd(int num1, int num2) {
            if (num1 < 0 && num2 < 0){
                return -gcd(-num1, -num2);
            }
            if (num1 < 0){
                return gcd(-num1, num2);
            }
            if (num2 < 0){
                return gcd(num1, -num2);
            }
            if (num2 > num1){
                return gcd(num2, num1);
            }
            if (num2 == 0){
                return num1;
            }
            return gcd(num2, num1 % num2);
        }

        @Override
        public String toString(){
            return x + " " + y;
        }

        public static int distance(Point point1, Point point2) {
            return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
        }
    }
}

```

# Results

## Image 1 - 0 changes, Image 2 - 13,698 changes

## Image 3 - 24,269 changes, Image 4 - 103 changes

## Image 5 - 5,344 changes, Image 6 - 4,456 changes

# Without invalid pixels removed, 42,782 changes total

Green pixels are the first layer of invalid pixels.

## Image 1 - 0 changes, Image 2- 9,889 changes

## Image 3 - 24,268 changes, Image 4 - 103 changes

## Image 5 - 4,471 changes, Image 6- 4,050 changes

All white pixels in all the pictures can have a line drawn to them from the center pixel if the line does not have to originate/end at the centers but rather anywhere on the pixel.

`args[0]` contains input file name.

`args[1]` contains output file name.

Prints to `stdout` number of changes.
> 4 votes

# Answer
# Python - PIL - 216,228 108,363 changes total

Whoo! Cut it in half thanks to @AJMansfield! This algorithm skips all the worrying about with calculating lines and optimization and what not. It just changes all whites to black except for one. If there are no whites, it makes one black a white. It check if there are more whites or black and changes every single one of the other kind to it except for one. If there are no black it makes (0, 0) the center.

```
import Image
from itertools import product

img = Image.open(raw_input())
img = img.convert("RGB")

pixdata = img.load()
changed=0

m=False
count=0
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y]==(0, 0, 0):
        count+=1

colors=[(0, 0, 0), (255, 255, 0)] if img.size[0]*img.size[1]-count>count else [(255, 255, 255), (0, 0, 255)]
m=False
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y] == colors[0]:
        if m:
            pixdata[x, y] = colors[1]
        else:
            pixdata[x, y] = (255, 0, 0)
            m=True
        changed+=1

if not m:
    pixdata[0, 0]==(255, 0, 0)
    changed+=1
if colors[0]==(255, 255, 255):
    changed-=1

print changed
img.save("out.png", "PNG")

```

# Results

## Image 1 - 28688 changes, Image 2 - 24208 changes

## Image 3 - 24248 changes, Image 4 - 7103 changes

## Image 5 - 11097 changes, Image 6 - 13019 changes

Takes file name from raw\_input and writes to out.png and prints number of changes.
> 3 votes

---
Tags: code-challenge, graphical-output, optimization, image-processing
---


# Question
Title: Make any number by repeatedly adding 2 numbers
You are given a machine with two 16-bit registers, `x` and `y`. The registers are initialized `x=1` and `y=0`. The only operation the machine can do is addition modulo 65536. That is:

* `x+=y` \- `x` is replaced by `(x + y) mod 65536`; `y` is unchanged
* `y+=x` \- similarly for `y`
* `x+=x` \- `x` is replaced by `2x mod 65536`; legal only if `x` is even
* `y+=y` \- similarly for `y`

The goal is to get a predetermined number in one of the registers (either `x` or `y`).

Write a program or a subroutine that receives a number (in `stdin`, `argv`, function parameter, top of stack or any other conventional place), and outputs a program to get this number. The output should go to `stdout`, or (if your language has no `stdout`) to any other conventional output device.

The output program can be up to 100% plus 2 steps far from optimal. That is, if the shortest program to get the target number has `n` steps, your solution cannot be longer than `2n+2`. This restriction is to avoid "too easy" solutions (e.g. counting 1, 2, 3, ...) but not require full optimization; I expect that the shortest program is easiest to find, but cannot be sure...

For example: Input = 25. Output:

```
y+=x
x+=y
x+=y
x+=x
x+=x
x+=x
y+=x

```

Another example: For any fibonacci number, the output has this alternating pattern. For Input = 21, output is

```
y+=x
x+=y
y+=x
x+=y
y+=x
x+=y
y+=x

```

Shortest code (measured in bytes) wins.

(this puzzle was inspired by some code for a 16-bit processor I had to generate recently)

P.S. I wonder - for which number the optimal program is longest?

# Answer
# CJam, 31

Like **@Tobia**'s answer, my algorithm is also shamelessly ~~stolen~~ inspired by **@CChak**'s answer. But, wielding the black magic that is CJam, I managed to make an even smaller implementation of the algorithm.

Try it here.

**Golfed:**

```
qi{_4%!:X)/X!-'xX+"
y+="@}h;]W%`

```

**Ungolfed:**

```
qi          "Read input and convert to integer.";
{           "Do...";
  _4%!:X    "Assign (value mod 4 == 0) to X.";
  )/X!-     "If X, divide value by 2. If not X, decrement value.";
  'xX+      "If X, put 'y' on the stack. If not X, put 'x' on the stack.";
  "
y+="        "Put '\ny+=' on the stack.";
  @         "Rotate top 3 elements of stack left so the value is on top.";
}h          "... while value is not zero.";
;           "Discard zero value on stack.";
]W%         "Collect stack into array and reverse.";

```

Please correct me if I'm wrong, but I believed that the modulo 65536 operation used in answers with a similar algorithm is unnecessary. I interpreted the question such that we can assume that the input will be a valid unsigned 16-bit integer, and any intermediate values or results of this algorithm will be as well.
> 2 votes

# Answer
# Perl 107 97

First post, so here goes.

```
sub h{($i)=@_;return if(($i%=65536)==0);($i%4==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

```

Which fits all of the register addition criteria, but I didn't run an exhaustive check to see if my answer was always within 2n+2 of the optimal number of steps. It is well inside the limit for every Fibonacci number, though.

Here is a more detailed breakdown

```
sub h{                           # Declare the subroutine, it should be called referencing an integer value
   ($i)=@_;                      # Assign the i variable to the integer used in the call
   return if(($i%=65536)==0);    # Check for base condition of called by 0, and enforce modulo from the start.
   ($i%4==0) ?                   # If the value passed is even, and will result in an even number if we halve it
   do{h($i/2);say"y+=y";}        # Then do so and recurse
   :do{h($i-1);say"y+=x";}       # Otherwise "subtract one" and recurse
}                                # Note that the print statements get called in reverse order as we exit.

```

As I mentioned, this is my first attempt at golfing, so I'm sure this can be improved upon. Also, I'm not sure if the initial subroutine call has to be counted in a recursive call or not, which could drive us up a few chars.

Interestingly we can reduce the code by 11 bytes\* and improve our "efficiency" in terms of the number of register operations, by relaxing the requirement that only even values can be "doubled". I've included that for fun here:

```
sub h{($i)=@_;return if(($i%=65536)==0);($i%2==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

```

Begin addendum:

Really liked this problem, and I've been fiddling with it off and on for the last couple weeks. Thought I would post my results.

Some numbers:

Using a BFS algorithm to find an optimal solution, in the first 2^16 numbers there are only 18 numbers that require 23 steps. They are: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Using the recursive algorithm described above, The "most difficult" number to reach is 65535, at 45 operations. ( 65534 takes 44, and there are 14 numbers that take 43 steps) 65535 is also the largest departure from optimal, 45 vs 22. The 23 step difference is 2n+1. (Only three numbers hit 2n: 65534, 32767, 32751.) Excepting the trivial (zero-step) cases, over the defined range, the recursive method averages approximately 1.4 times the optimal solution.

Bottom line: For the numbers 1-2^16, the recursive algorithm never crosses the defined threshold of 2n+2, so the answer is valid. I suspect that it would begin to depart too far from the optimal solution for larger registers/more bits, however.

The code I used to create the BFS was sloppy, memory intensive, not commented, and quite deliberately not included. So... you don't have to trust my results, but I'm pretty confident in them.
> 8 votes

# Answer
# Python 3, 202 bytes

```
def S(n):
 q=[(1,0,"")];k=65536
 while q:
  x,y,z=q.pop(0)
  if n in{x,y}:print(z);return
  q+=[((x+y)%k,y,z+"x+=y\n"),(x,(x+y)%k,z+"y+=x\n")]+[(2*x%k,y,z+"x+=x\n")]*(~x&1)+[(x,2*y%k,z+"y+=y\n")]*(~y&1)

```

*(Thanks to @rationalis for a few bytes)*

Here's an extremely basic solution. I wish I could golf the last line better, but I'm currently out of ideas. Call with `S(25)`.

The program just does a simple BFS with no caching, so is very slow. Here is `S(97)`, for some sample output:

```
y+=x
x+=y
x+=x
x+=x
x+=x
x+=x
y+=x
y+=x
x+=y

```
> 7 votes

# Answer
# Dyalog APL, 49 chars / bytes\*

```
{0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1}

```

Algorithm shamelessly inspired by **@CChak**'s answer.

**Example:**

```
    {0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1} 25
y+=x
y+=x
y+=y
y+=x
y+=x
y+=y
y+=y
y+=x

```

**Ungolfed:**

```
{
    N←(2*16)|⍵                 # assign the argument modulo 65536 to N
    0=N: ⍬                     # if N = 0, return an empty value (that's a Zilde, not a 0)
    0=4|N: ⎕←'y+=y' ⊣ ∇N÷2     # if N mod 4 = 0, recurse with N÷2 and *then* print 'y+=y'
    ⎕←'y+=x' ⊣ ∇N-1            # otherwise, recurse with N-1 and *then* print 'y+=x'
}

```

<sub>* Dyalog APL supports a legacy charset which has the APL symbols mapped to the upper 128 byte values. Therefore an APL program that only uses ASCII characters and APL symbols can be considered to be bytes == chars.</sub>
> 5 votes

# Answer
# Python, 183

```
def S(n):
 b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
 if n<2:return
 while~n&1:n>>=1;a+=1
 while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
 while a:s+=[c,c*b+e*2][i];i=0;a-=1
 print(s)

```

I can't guarantee this stays within 2x the optimal program for even numbers, but it is efficient. For all valid inputs `0 <= n < 65536`, it's essentially instantaneous, and generates a program of at most 33 instructions. For an arbitrary register size `n` (after fixing that constant), it would take `O(n)` time with at most `2n+1` instructions.

### Some Binary Logic

Any odd number `n` can be reached within 31 steps: do `y+=x`, getting `x,y = 1,1`, and then keep doubling `x` with `x+=x` (for the first doubling do `x+=y`, since `x` is odd to begin with). `x` will reach every power of 2 this way (it's just a left-shift), and so you can set any bit of `y` to be 1 by adding the corresponding power of 2. Since we're using 16-bit registers, and each bit except for the first takes one doubling to reach and one `y+=x` to set, we get a maximum of 31 ops.

Any even number `n` is just some power of 2, call it `a`, times an odd number, call it `m`; i.e. `n = 2^a * m`, or equivalently, `n = m << a`. Use the above process to get `m`, then reset `x` by left-shifting it until it's 0. Do a `x+=y` to set `x = m`, and then continue to double `x`, the first time using `x+=y` and subsequently using `x+=x`.

Whatever `a` is, it takes `16-a` shifts of `x` to get `y=m` and an additional `a` shifts to reset `x=0`. Another `a` shifts of `x` will occur after `x=m`. So a total of `16+a` shifts is used. There are up to `16-a` bits that need to be set to get `m`, and each of those will take one `y+=x`. Finally we need an extra step when `x=0` to set it to m, `x+=y`. So it takes at most 33 steps to get any even number.

You can, of course, generalize this to any size register, in which case it always takes at most `2n-1` and `2n+1` ops for odd and even `n`-bit integers, respectively.

### Optimality

This algorithm produces a program that is near-optimal (i.e. within `2n+2` if `n` is the minimum number of steps) for odd numbers. For a given odd number `n`, if the `m`th bit is the leading 1, then any program takes at least `m` steps to get to `x=n` or `y=n`, since the operation which increases the registers' values fastest is `x+=x` or `y+=y` (i.e. doublings) and it takes `m` doublings to get to the `m`th bit from 1. Since this algorithm takes at most `2m` steps (at most two per doubling, one for the shift and one `y+=x`), any odd number is represented near-optimally.

Even numbers are not quite so good, since it always uses 16 ops to reset `x` before anything else, and 8, for example, can be reached within 5 steps.

Interestingly, the above algorithm never uses `y+=y` at all, since `y` is always kept odd. In which case, it may actually find the shortest program for the restricted set of only 3 operations.

### Testing

```
# Do an exhaustive breadth-first search to find the shortest program for
# each valid input
def bfs():
    d = {(0,1):0}
    k = 0xFFFF
    s = set(range(k+1))
    current = [(0,1)]
    nexts = []
    def add(pt, dist, n):
        if pt in d: return
        d[pt] = dist
        s.difference_update(pt)
        n.append(pt)
    i = 0
    while len(s) > 0:
        i += 1
        for p in current:
            x,y = p
            add((x,x+y&k), i, nexts)
            add((y,x+y&k), i, nexts)
            if y%2 == 0: add(tuple(sorted((x,y+y&k))), i, nexts)
            if x%2 == 0: add(tuple(sorted((x+x&k,y))), i, nexts)
        current = nexts
        nexts = []
        print(len(d),len(s))

# Mine (@rationalis)
def S(n):
    b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
    if n<2:return ''
    while~n&1:n>>=1;a+=1
    while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
    while a:s+=[c,c*b+e*2][i];i=0;a-=1
    return s

# @CChak's approach
def U(i):
    if i<1:return ''
    return U(i//2)+'y+=y\n' if i%4==0 else U(i-1)+'y+=x\n'

# Use mine on odd numbers and @CChak's on even numbers
def V(i):
    return S(i) if i % 2 == 1 else U(i)

# Simulate a program in the hypothetical machine language
def T(s):
    x,y = 1,0
    for l in s.split():
        if l == 'x+=x':
            if x % 2 == 1: return 1,0
            x += x
        elif l == 'y+=y':
            if y % 2 == 1: return 1,0
            y += y
        elif l == 'x+=y': x += y
        elif l == 'y+=x': y += x
        x %= 1<<16
        y %= 1<<16
    return x,y

# Test a solution on all values 0 to 65535 inclusive
# Max op limit only for my own solution
def test(f):
    max_ops = 33 if f==S else 1000
    for i in range(1<<16):
        s = f(i); t = T(s)
        if i not in t or len(s)//5 > max_ops:
            print(s,i,t)
            break

# Compare two solutions
def test2(f,g):
    lf = [len(f(i)) for i in range(2,1<<16)]
    lg = [len(g(i)) for i in range(2,1<<16)]
    l = [lf[i]/lg[i] for i in range(len(lf))]
    print(sum(l)/len(l))
    print(sum(lf)/sum(lg))

# Test by default if script is executed
def main():
    test()

if __name__ == '__main__':
    main()

```

I wrote a simple test to check that my solution indeed produces correct results, and never goes over 33 steps, for all valid inputs (`0 <= n < 65536`).

In addition, I attempted to do an empirical analysis to compare my solution's output against the optimal outputs -- however, it turns out that breadth-first search is too inefficient to obtain the minimum output length for every valid input `n`. For example, using BFS to find the output for `n = 65535` does not terminate in a reasonable amount of time. Nonetheless I've left in `bfs()` and am open to suggestions.

I did, however, test my own solution against @CChak's (implemented in Python here as `U`). I expected mine would do worse, since it is drastically inefficient for smaller even numbers, but averaged across the whole range in two ways, mine produced output of length on average 10.8% to 12.3% shorter. I thought maybe this was due to better efficiency from my own solution on odd numbers, so `V` uses mine on odd numbers and @CChak's on even numbers, but `V` is in between (about 10% shorter than `U`, 3% longer than `S`).
> 3 votes

---
Tags: code-golf, arithmetic, code-generation
---