title: Create the shortest BitShift

text:
# Question
Title: Create the shortest BitShift
# Introduction

BitShift is an esolang, created by me, to output strings. Sounds boring, is boring. However, the only instructions available to BitShift are `0` and `1`. Therefore it can be challenging to golf in it. To make matters even more interesting, the language only supports 4 bitshifting instructions, a clear, a print and an input instruction.

# How it works

BitShift is written by alternating `0` and `1` characters. Once the interpreter finds 2 of the same characters in a row, it will perform an instruction based on the amount of non-alternating characters preceding it.

`010010110001010` will perform the operations `3 4 2 1 5`
`010 0101 10 0 01010` here, the non-alternating characters are seperated by a spacebar for readability.

The interpreter can be found here

# Operations

All operations are performed on one single value. BitShift does not know of a stack.
BitShift programs initially start with a value of 0. This value can range from 0-255 and overflows at -1 and 256

```
1   Shift the value 1 bit to the left (0000 0001 > 0000 0010)
2   Shift the value 1 bit to the right (0000 0010 > 0000 0001)
3   XOR the value with 1 (0000 0000 > 0000 0001)
4   XOR the value with 128 (0000 0000 > 1000 0000)
5   Set the value to 0
6   Convert the value to a character and print it
7   Read a character from user input and set the value to it

```

# Challenge

Your task is to create a program which can convert an input string to the shortest possible BitShift program which will output that string when run.

# Rules

* You are not allowed to use the `7` operation
* Your program takes only one input argument, which is the string to convert
* Your program will output the translated BitShift program to STDOUT
* You can use any kind of built-in function in your preffered language
* You can use any kind of language, as long as it's created before this date

# Scoring

This is a .

The person who can create the shortest BitShift program will win this challenge. In case of a tie, the lowest byte count will win.

The input string (ISO 8859-1) you should base your answer on is:
`This is a string, meant to test the effectiveness of your program. Here are some special characters to make matters interesting: Æ Ø ß. How meta! :D`

The special characters used are `Æ Ø ß`

Please post the output of your program in your answer, so that it can be tested for validation.

The following is an example solution. Obviously, this is a terrible solution.

# Javascript, 594 bytes, 4275 characters

```
var flag = true;
var input = prompt();
var output = ""
for (n in input) {
    var c = input.charCodeAt(n).toString(2);
    while (c.length < 8) {
        c = "0" + c;
    }
    for (var i = 0; i < 8; i++) {
        if (c[i] == "1") {
            output += flag ? "010" : "101";
        }
        if (i < 7) output += flag ? "0" : "1";
    }
    for (var z = 0; z < 6; z++) {
        output += flag ? "0" : "1";
        flag = !flag;
    }
    flag = !flag;
    for (var z = 0; z < 5; z++) {
        output += flag ? "0": "1";
        flag = !flag;
    }
    flag = !flag;
}
console.log(output);

```

# Answer
> 6 votes
# Mathematica, 343 bytes, 2573 characters

```
B=BitXor;t[a_]:={Mod[2a,256],⌊a/2⌋,a~B~1,a~B~128,0};w[a_,b_]:=Position[t@a,b][[1,1]];f=FindShortestPath[Graph[0~Range~255,e=Join@@Table[a#&/@({}⋃t@a),{a,m=c=0,255}],EdgeWeight(w@@#&/@e)],All,All];o="";u[a_,b_]:=(Do[o=o<>ToString[m=1-m],{If[a==b,6,a~w~f[a,b][[2]]]}];m=1-m);While[c~u~y;c!=y,c=f[c,y][[2]]]~Do~{y,ToCharacterCode@i};o

```

This is my first code competition. This program should generate the shortest possible program for any string. It effectively calculates a lookup table given the current state of the accumulator and the goal byte to find the shortest sequence of the five operations to get from any one to another, carrying the accumulator over characters and taking advantage of the size difference between instructions. Uses Mathematica 8's `Graph` infrastructure for calculating shortest paths (alternatives being to roll one's own or just embed the `256 x 256` table of instructions).

Ungolfed version (the first `i = "..."` line is also present, but not counted in the golfed version since it is the input):

```
i = "This is a string, meant to test the effectiveness of your program. Here are some special characters to make matters interesting: Æ Ø ß. How meta! :D";
B = BitXor;
t[a_] := {Mod[2 a, 256], Quotient[a, 2], B[a, 1], B[a, 128], 0}
w[a_, b_] := Position[t[a], b][[1, 1]]
g = Graph[Range[0, 255],
  e = Join @@ Table[DirectedEdge[a, #] & /@ Union@t@a, {a, 0, 255}],
  EdgeWeight -> (w @@ # & /@ e)];
f = FindShortestPath[g, All, All]; c = m = 0; o = "";
u[a_, b_] := (Do[
   o = o <> ToString[m = 1 - m], {If[a == b, 6, w[a, f[a, b][[2]]]]}];
   m = 1 - m);
Do[While[u[c, y]; c != y, c = f[c, y][[2]]], {y, ToCharacterCode[i]}];
o

```

Output:

```
10111101111011110101000010110010101101101010000010110010110010010101101111110101001011001011001001010111110100110100110110101001000000101011101001101101010000000101011011101110111110111011010100110010000101011001101110111010100100001000001001010110011011101110101000010001000011011010100110100110010101111111001101010010001000010001000010010101101110111101101010011001000010010101100110010001000100010101110111101010000001101010010110010110010110010101100100010000110110101000000000110010101101001101001101001101010001000001011001001010110100110110101001100100001010111111001010110100110100110100110101000011010100100000101100100101011011111010100110100110100110110101001101110101001010110010001001010111011111101110110101000100001000010101111001001010110100110010001010111101111011010100010001000010110010101111011111001001010110100110110101001010110111111010100100010000100010001000100101011111011101111001010110010000001010110111011101110111110110101001101001101001101010010001000010010101100110111011101010000001010111010011010011010100110111010100110100110100110110101000001000100001101101010000010001010110111111101101010011010011010011011010100110111110011010100000000110010101100101100101011010011011010100101100101011110010010101101111101010001011001001010110100110010001010111100100101011011111010100100010001000001000100101011001011001011001001010110010001001010110111011110110101001000001010110111011101111101110110101001101110101001101111100100101011101111110111011010100001000001001010111011111110110101001101001101001101010000000110010101100100001011001001010111101111101010000010110010010101101001100100010101101111111011010100110111011010100010000100001010111011111010011011010100101100101011011010100100000010101101001101001101001101010011011101111001001010111111111001101010010001000010001000010010101101111101101010011001101111011101101010000010000100101011011111010100100010000100010000100101011011111011010100101100110010000101011010100010000010110010010101101001101010010010101101111110101001011001011001001010110011011101110101000100001010111011111010011011010100101100101011110010010101101001101101010011001000010101111001001010110011011101110101000010001000011011010100001000101011111110010101100100010001011010100110111111010100010110011010011010010101111110011010100100001000100010001000100101101010001100100101011111111001101010011010011010100110111011101111010011011010100101100101011111111100110101001000100001000100001001010110111011110110101001011001100100001010111111010011011010100001100101011011010100100010001000010001010111110111101010

```

# Answer
> 1 votes
# D, 472 bytes, 4275 characters

```
import std.stdio;import std.conv;import std.file;import std.format;import core.stdc.stdio;void main(char[][]a){bool f=true;char[] o;int i;char[64000]b;size_t j;FILE* g=core.stdc.stdio.fopen("i", "r");j=fread(cast(void*)b, 1, 64000, g);foreach(dchar n;b[0..j]){string c=format("%b",n);while(c.length<8)c='0'~c;for(i=0;i<8;i++){if(c[i]=='1')o~=f?"010":"101";if(i<7)o~=f?'0':'1';}for(i=0;i<6;i++){o~=f?'0':'1';f=!f;}f=!f;for(i=0;i<5;i++){o~=f?'0':'1';f=!f;}f=!f;}writeln(o);}

```

Loads input from a file called `i` in the same directory as the program. Tons of bytes waisted on the UTF input.

Output:

```
[encoded data, 4275 characters]
```

---
Tags: metagolf
---


title: Packing Circles

text:
# Question
Title: Packing Circles
Take a look at this image. Specifically, at how the holes on the ends are arranged.

<sup>(Image source)</sup>

Notice how the pipes in this image are packed in a hexagonal pattern. It is known that in 2D, a hexagonal lattice is the densest packing of circles. In this challenge, we will be focusing on minimizing the perimeter of a packing of circles. One useful way to visualize the perimeter is to imagine putting a rubber band around the collection of circles.

## The Task

Given a positive integer `n` as input, show a collection of `n` circles packed as tightly as possible.

## Rules and Clarifications

* Assume circles have a diameter of 1 unit.
* The variable to be minimized is the length of the perimeter, which is defined to be the convex hull of the *centers* of the circles in the group. Take a look at this image:

The three circles in a straight line have a perimeter of 4 (the convex hull is a 2x0 rectangle, and the 2 is counted twice), those arranged in a 120-degree angle have a perimeter of about 3.85, and the triangle has a perimeter of only 3 units. Note that I am ignoring the additional pi units that the actual perimeter would be because I'm only looking at the circles' centers, not their edges.

* There may (and almost certainly will be) multiple solutions for any given `n`. You may output any of these at your discretion. Orientation does not matter.
* The circles must be on a hexagonal lattice.
* The circles must be at least 10 pixels in diameter, and may be filled or not.
* You may write either a program or a function.
* Input may be taken through STDIN, as a function argument, or closest equivalent.
* The output may be displayed or output to a file.

## Examples

Below I have example valid *and* invalid outputs for n from 1 to 10 (valid examples only for the first five). The valid examples are on the left; every example on the right has a greater perimeter than the corresponding valid example.

**Much thanks to steveverrill for help with writing this challenge. Happy packing!**

# Answer
> 4 votes
# Mathematica ~~295~~ 950 bytes

Note: This still-to-be-golfed version addresses issues raised by Steve Merrill regarding my earlier attempts.

Although it is an improvement over the first version, it will not find the densest handle configuration where one would seek a circular, rather than hexagonal, overall shape.

It finds solutions by building a complete inner hexagon (for n\>=6, and then examines all of the configurations for completing the outer shell with the remaining circles.

Interestingly, as Steve Merrill noted in the comments, the solution for `n+1` circles does not always consist of the solution for n circles with another circle added on. Compare the given solution for 30 circles to the given solution for 31 circles. (Note: there is a unique solution for 30 circles.)

```
m[pts_]:={Show[ConvexHullMesh[pts],Graphics[{Point/@pts,Circle[#,1/2]&/@ pts}],
ImageSize->Tiny,PlotLabel->qRow[{Length[pts],"  circles"}]],
RegionMeasure[RegionBoundary[ConvexHullMesh[pts]]]};
nPoints = ((#+1)^3-#^3)&;pointsAtLevelJ[0] = {{0,0}};
pointsAtLevelJ[j_]:=RotateLeft@DeleteDuplicates@Flatten[Subdivide[#1, #2, j] &@@@
Partition[Append[(w=Table[j{Cos[k Pi/3],Sin[k Pi/3]},{k,0,5}]),
w[[1]]], 2, 1], 1];nPointsAtLevelJ[j_] := Length[pointsAtLevelJ[j]]
getNPoints[n_] := Module[{level = 0, pts = {}},While[nPoints[level]<=n,
pts=Join[pointsAtLevelJ[level],pts];level++];Join[Take[pointsAtLevelJ[level],n-Length[pts]],
pts]];ns={1,7,19,37,61,91};getLevel[n_]:=Position[Union@Append[ns,n],n][[1, 1]]-1;
getBaseN[n_] := ns[[getLevel[n]]];pack[1]=Graphics[{Point[{0,0}], Circle[{0, 0}, 1/2]},
ImageSize->Tiny];pack[n_]:=Quiet@Module[{base = getNPoints[getBaseN[n]],
outerRing = pointsAtLevelJ[getLevel[n]], ss},ss=Subsets[outerRing,{n-getBaseN[n]}];
SortBy[m[Join[base,#]]&/@ss,Last][[1]]]

```

Some of the checks entailed comparisons of over one hundred thousand cases for a single value of n (including symmetries). It took approximately 5 minutes to run the total 34 test cases. Needless to say, with larger `n's` this brute-force approach would soon prove impractical. More efficient approaches are certain to exist.

The numbers to the right of each packing are the perimeters of the respective blue convex hulls. Below is the output for `3 < n < 35`. The red circles are those added around a regular hexagon.

---

---
Tags: code-golf, graphical-output, hexagonal-grid, packing
---


title: Define map in the fewest tokens

text:
# Question
Title: Define map in the fewest tokens
`map` is a very basic yet important function in functional programming.

All FP programming languages have it built-in but it is always fun to see how shortly you can define it yourself.

This will be scored in **AST nodes**, not bytes.

A token is the second-smallest building block of a program, over characters.

A token is:

> anything that would be a distinct node if you drew a tree representing the source code

This scoring gives no benefit to single letter AST nodes names, and values succinctness as Paul Graham likes (this definition of AST nodes is his).

Haskell has this super cool definition:

```
zipWith ($) . repeat

```

And my lisp-ish AST of it (not required in your answer, just to show it visually)

```
   Apply (Apply (Var ".") (Apply (Var "zipWith") (Var "$"))) (Var "repeat")

```

That is 7 tokens. (`Var x` counts as 1)

I did not write it, so I do not post it as an answer.

Example:

```
(zipWith ($) . repeat) (* 3) [1, 2, 3] -- [3, 6, 9]

```

`map` should be defined as a (named or unnamed) function taking two arguments, the function and the list.

May the most AST nodes-succint code win!

# Answer
> 2 votes
# Mathematica, ~~36~~ 11 nodes

```
Thread@#@#2&

```

The `FullForm` of this program is:

```
Function[Thread[Slot[1][Slot[2]]]]

```

which has 4 symbols, 2 numbers, and 5 function applications.

# Answer
> 1 votes
# Python 3, 19 nodes.

```
lambda f, x: [f(y) for y in x]

```

Fairly self-explanatory. Applies `f` to each element of `x` and then returns the resulting list.

Interestingly, this code also uses only 19 AST nodes:

```
def map(f, x):
    for y in x:
        yield f(y)

```

I'm not totally sure if I'm counting the nodes correctly, because this is the first time I've worked with an AST. But this is what I used to count:

```
import ast
code = '''
lambda f, x: [f(y) for y in x]
'''
print sum(1 for node in ast.walk(ast.parse(code)))

```

# Answer
> 0 votes
## Haskell, 11(?) nodes

```
flip foldr ([]).((:).)

```

Not sure about the node count (6 symbols plus 5 function applications?).

---
Tags: atomic-code-golf, functional-programming
---


title: Negate a condition if a bool is FALSE

text:
# Question
Title: Negate a condition if a bool is FALSE
Let's say I have a condition expression `x` and that I want to check if it is TRUE or FALSE depending on the value of a boolean `y`:

```
y ? x : !x

```

Is there a way to express it without repeating `x` expression? Something like how we can get a number or its opposite depending on a bool, without repeating the number in the expression:

```
number * (opposite ? -1 : 1)

```

Example, note the repetition of `date.hour < 12` that I want to avoid:

```
tellTheThruth = FALSE; // or TRUE
if (tellTheThruth && date.hour < 12 || !tellTheThruth && !(date.hour < 12) {
    print "It's AM"
} else {
    print "It's PM"
}

```

Is it possible in all common languages (I was thinking in Javascript and I can't find a solution)? If not, is there some language in which you can?

# Answer
for two booleans x and y, `y ? x : !x` can be rewritten as `y ^ !x` (y XOR NOT x) or similar in most languages.
> 6 votes

# Answer
## Haskell

```
import Data.Bool.Extras
bool=<<not

```

`bool` from `Data.Bool.Extras` is similar to the `?` operator in other languages. It takes 3 arguments, a False case, a True case and a boolean to decide which one to use. `=<<` works here in function context ( i.e. `(f=<<g) x` is `f (g x) x`), so we can use it as `(bool=<<not) <x> <y>` which is `bool (not <x>) <x> <y>`.

Example: `(bool=<<not) True False` -\> `False`.
> 1 votes

---
Tags: code-golf, tips
---