title: Phone Multi-tap Spelling

text:
# Question
Title: Phone Multi-tap Spelling
Inspired by the Google Code Challenge:

> The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ' ' should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.
>
> Each message will consist of only lowercase characters a-z and space characters ' '. Pressing zero emits a space.

Your challenge is to write the smallest function which takes the input string, and returns the sequence of keypresses necessary to produce the input as string or output it to stdout. The function which is the least amount of bytes wins.

**Example Input/Output**

```
phone("hi")
44 444
phone("hello world")
4433555 555666096667775553

```

**Other clarifications**

* Pauses **must** only be added when necessary and must be a space ' '.
* Each message will consist of only **lowercase** characters a-z and space characters ' '. Print `0` to signify spaces.
* No external libraries.
* Only the input string may be passed to your function.
* To make other languages competitive, the primary function declaration doesn't count, and nor does importing other standard libraries. `#include`s, `import`s, and `using`s don't count. Everything else does. This does include `#define`s and helper functions. See rule 2 in this question if you are confused.
* Multiple spaces can be denoted as `00` or `0 0` since you don't really have to pause between a space

# Answer
> 8 votes
# Ruby, ~~129~~ ~~122~~ ~~115~~ ~~111~~ ~~108~~ ~~107~~ 105

Done with golfing...

Oops, completely forgot to remove unnecessary spaces - fixed...

Saved 2 chars thanks to Peter Taylor.

Online version

```
def t9(t)
(t.tr(" ",?`).bytes.map{|c|"09998887777666555444333222"[96-c..-1][/(.)\1*/]}*' ').gsub /(\d) (?!\1)/,'\1'
end

```

Explanation:

space is translated to the char with the ordinal 96

```
(t.tr(" ",?`).bytes

```

characters are first mapped to series of numbers: \- a to 2 \- b to 22 \- d to 3222 \- h to 444333222

a regex expression then matches the first group of equal digits

```
map{|c|"09998887777666555444333222"[96-c..-1][/(.)\1*/]}

```

the array is joined

```
*' ')

```

all spaces in the occurences of "digit space different\_digit" are removed

```
gsub /(\d) (?!\1)/,'\1'

```

# Answer
> 6 votes
## REBEL \- 154 110 103

```
;0 2abc3def4ghi5jkl6mno7pqrs8tuv9wxyz/^;/$<;/([^\d-])(?=\D.*(\d)(\w)*\1)/$2$3-/(\d)-+\1/$1 $1/-//;/$>$`

```

This 'function' accepts input from stdin and sends results to stdout.

Test runs (so you don't have to install the interpreter):

```
hi
44 444

hello world
4433555 555666096667775553

yes
999337777

kthxbai
558449922 2444

```

# Answer
> 4 votes
# JavaScript (124)

Run in Firefox.

```
t9=s=>s.replace(/./g,c=>'099998887777666555444333222'.slice(36-parseInt(c,36)).match(/(.)\1*/)[0]+' ').replace(/(.) (?!\1)/g,'$1')

```

# Answer
> 4 votes
## GolfScript, 46 chars

```
{).," adgjmptw"&.,.1>*`@@)\;-*}/]{.2$^!" "*\}*

```

As usual, reads input from stdin, prints to stdout. See online demo (with canned input).

Note that this code relies on a very strict interpretation of the input spec (only lowercase letters and spaces): in particular, any newlines in the input will crash it! This issue can be fixed, at the cost of two extra chars, by prepending `n-` to the code to filter any newlines out.

# Answer
> 3 votes
## VBA 220 253/258/219

Not counting `Function` lines here:

With `String`, **253**:

```
Function t(s)
For Each c In Split(StrConv(s,64),Chr(0))
If c<>""Then If c=" "Then t=t & 0 Else b=Asc(c)-91:n=String(IIf(b>27,(b-4)Mod 4+1,IIf(b>23,(b-1)Mod 4+1,b Mod 3+1)),Trim(Str(Int(b/3)-IIf(b=24Or b=27Or b>29,1,0)))):t=t &IIf(Right(t,1)=Left(n,1)," " &n,n)
Next
End Function

```

With a `For` loop **258**:

Added corrections for 7/9 key (thanks, Danny), which added a lot of chars.

```
Function t(s)
For Each c In Split(StrConv(s,64),Chr(0))
If c<>""Then
n=""
b=Asc(c)-91
For i=1To IIf(b>27,(b-4)Mod 4+1,IIf(b>23,(b-1)Mod 4+1,b Mod 3+1))
n=n &Int(b/3)-IIf(b=24Or b=27Or b>29,1,0)
Next
t=t &IIf(c=" ",0,IIf(Right(t,1)=Left(n,1)," " &n,n))
End If
Next
End Function

```

Using `Choose` **219**:

I didn't want to run with this one, since is more basic in functionality, but it *is* the shorter code...

```
Function t(s)
For Each c In Split(StrConv(s,64),Chr(0))
If c<>"" Then:b=Asc(c)-96:n=Choose(b,2,22,222,3,33,333,4,44,444,5,55,555,6,66,666,7,77,777,7777,8,88,888,9,99,999,9999):t=t &IIf(c=" ",0,IIf(Right(t,1)=Left(n,1)," " &n,n))
Next
End Function

```

# Answer
> 3 votes
# C++ - 365 characters without `int main(){}`

```
#include<iostream>
#include<string>
#include<cmath>
#define o std::cout<<
int main(){std::string s;getline(std::cin,s);for(int i=0;i<s.size();i++){if(s[i]==32)o 0;int j=s[i]-97;if(i>0&&j/3==(s[i-1]-97)/3)o ' ';if(-1<j&j<15){for(int k=j-j%3-1;k<j;k++)o 2+j/3;}if(14<j&j<19){for(int k=14;k<j;k++)o 7;}if(18<j&j<22){for(int k=18;k<j;k++)o 8;}if(21<j&j<26){for(int k=21;k<j;k++)o 9;}}}

```

Uses the same reasoning as my answer here, only using `for` loops to output each letter the appropriate number of times.

# Answer
> 3 votes
# Perl - 107 ~~110~~

```
$_=<>;y/ /0/;$z='a';$==2;for$l((3)x5,4,3,4){for$q(1..$l){s/$z/$=x$q.$"/ge,$z++}$=++}s/(.) (?!\1)/\1/g;print

```

Here's my previous solution in 120 ~~128 130 155~~:

```
$_=<>;s//_/g;y/sz/79/;for$x(cfilorvy,behknqux,adgjmptw){s/(\d)_/\1\1_/g,eval"y/$x/2-9/"}y/ _/0 /;s/(.) (?!\1)/\1/g;print

```

Tests:

```
hi
 44 444

hello world
 4433555 555666096667775553

jackdaws loves my big sphinx
 52 222553297777055566688833777706999022444 407777 744 4446699

```

# Answer
> 3 votes
# C, 165 163 153 149 138 chars

```
k(char*s){char*m="`cfilosvz",l=0,i,c;while(*s^0){for(i=0;*s>m[i];i++);c=*s-m[i-1];i==0?i=-1,c=1:i==l?putchar(32):1;while(c--)putchar(i+49);l=i;s++;}}

```

My first attempt at code golfing, any suggestions are appreciated.

# Answer
> 2 votes
# Java - 243

Pretty naive java solution. Thanks to commenters for suggestions.

Fixed a bug that sometimes inserted unnecessary spaces, e.g. for the input "hello worlds sup".

```
    private static void t9(String s) {
        String[]t=",,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(",");String o="";int i,j,k,l=0;for(char c:s.toCharArray()){if(c==32){o+='0';l=0;}else for(j=0;j<10;j++){int n=t[j].indexOf(c);if(n>=0){if(j==l)o+=' ';for(k=0;k<n+1;k++)o+=j;l=j;}}}return o;
    }

```

# Answer
> 2 votes
# C++ - 170 168 160

**Golfed:**

```
#define t std::cout<<
void g(char*s){char v,p,b,l=1;while(*s){v=*s++-97;p=(v==18)+(v==25)+(v-=v/18+v/25)%3;b=v<0?48:v/3+50;if(l==b)t' ';while(p--+1){t(l=b);}}}

```

**Ungolfed**

```
void numpresses(char* s)
{
char lastbutton = 1;
const char asciiOffset = 97;

while(*s)
{
    char val = *s++ - asciiOffset;

    char presses =
        (val == 18) + (val == 25)           //Z and S are special cases. Check for their ascii codes.
        + (val -= val / 18 + val / 25) % 3; //Simple mod 3 for number of presses. Also apply offset for characters above s and z.

    char button =
        val < 0                             //If the character is a space...
        ? '0'                               //The button character needs to be 0
        : val / 3 + '2';                    //Buttons are offset by the ascii code for the number 2

    if (lastbutton == button)               //Add a space if we need to pause
    {
        std::cout << ' ';
    }

    while (presses-- + 1)                   //Print the button once for each press required
    {
        std::cout << button;
        lastbutton = button;
    }
}
}

```

# Answer
> 2 votes
# C: 136 characters

```
p(char*s){int i,c,l=1;while(c=*s%32,*s++)for(i=l!=(l=(c+149-c/18-c/25)/3-!c);i++<(c-!!c-c/18-c/25)%3+(c==19)+c/26+2;putchar(i^1?l:32));}

```

And slightly ungolfed (yes, that is how it was written):

```
p(char*s){
        int i,c,l=1;
        while(c=*s%32,*s++)for(
                i=l!=(l=(c+149-c/18-c/25)/3-!c);
                i++<(c-!!c-c/18-c/25)%3+(c==19)+c/26+2;
                putchar(i^1?l:32)
        );
}

```

I might be able to cut it down a little by applying some recursion, black magic and a fair amount of chili powder.

# Answer
> 1 votes
# CoffeeScript - 202 (210 - 8)

```
t9=(s)->
    t=[3,3,3,3,3,4,3,4];l=-1;r=""
    for c in s
        n="";d=c.charCodeAt(0)-96
        if c is ' '
            n=0
        else((n+=k+2 for x in[0...d];break)if d<=v;d-=v)for v,k in t
        r+=if n[0]is l[0] then " "+n else n
        l=n
    r

```

# Answer
> 1 votes
# Python ~~155~~ 150

I wish i was better at this XD. Function definition not counted. First indentation level is a space, second is a tab, and third 2 tabs.

```
def p(s,l=None):
 for c in s:
    for i,g in enumerate(" ,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(",")):
        if c in g:print"\b"+[""," "][l==i]+str(i)*(g.index(c)+1),;l=i

```

# Answer
> 1 votes
# APL, 77 chars

```
{{⍵,⍨⍺,''↑⍨=/↑¨⍺⍵}/('0',⍨(⌈3.1×y-⌊y)/¨⍕¨2+⌊y←7.99,⍨.315×⍳25)[⍵⍳⍨⎕UCS 96+⍳26]}

```

**Explanation**

* `2+⌊y←7.99,⍨.315×⍳25` or, ungolfed, `y←(0.315×⍳25),7.99 ◇ 2+⌊y` samples a suitably tilted line (y = 0.315 x) on the points from 1 to 25; the line is tilted in such a way that the floor of these y values follows the repeating pattern 000111...777 except for the sixth group of digits 5555; a number is appended at the end to get the fourth 7, so that the final array plus 2 is 22233344455566677778889999;
* `⌈3.1×y-⌊y` amplifies the difference between those y values and their floors, so that the ceilings of the differences give the pattern 123123... with a 4 on the last digits of the two groups of 4 digits;
* `'0',⍨( ... )/¨⍕¨ ...` or `(( ... ) /¨ ⍕¨ ...),'0'` uses the latter result to duplicate digits from the former, so that the output is the array of strings "2" "22" "222" "3" "33" "333"... with the correct "7777" and "9999" in place, and a "0" appended to the end;
* `⍵⍳⍨⎕UCS 96+⍳26` or `(⎕UCS 96+⍳26)⍳⍵` computes the index of each input char, where "a" is 1, "z" is 26, and space (and every other char) is 27;
* `{ ... }/( ... )[ ... ]` takes the latter result, the index for each input char, to translate each char into the respective string of digits, then concatenates the strings using the function in braces;
* `{⍵,⍨⍺,''↑⍨=/↑¨⍺⍵}` or `{(⍺,(=/↑¨⍺,⍵)↑''),⍵}` appends each new string ⍺ to the accumulator ⍵, interposing a single space only if both arguments start with the same char.

**Examples**

```
      {{⍵,⍨⍺,''↑⍨=/↑¨⍺⍵}/('0',⍨(⌈3.1×y-⌊y)/¨⍕¨2+⌊y←7.99,⍨.315×⍳25)[⍵⍳⍨⎕UCS 96+⍳26]} 'hello world'
 4433555 555666096667775553
      {{⍵,⍨⍺,''↑⍨=/↑¨⍺⍵}/('0',⍨(⌈3.1×y-⌊y)/¨⍕¨2+⌊y←7.99,⍨.315×⍳25)[⍵⍳⍨⎕UCS 96+⍳26]} 'the quick brown fox jumped over the lazy dog'
 84433077884442225502277766696603336669905886733 3066688833777084433055529999 999036664

```

# Answer
> 0 votes
# JavaScript 234

`for(l=-1,r="",I=0,y=(s=prompt()).length;I<y;I++){c=s[I];n="";d=c.charCodeAt(0)-96;if(0>d)n=0;else for(k=J=0;J<8;k=++J){v="33333434"[k];if(d<=v){for(x=K=0;0<=d?K<d:K>d;x=0<=d?++K:--K)n+=k+2;break}d-=v}r+=n[0]==l[0]?" "+n:n;l=n}alert(r)`

# Answer
> 0 votes
## R 224

I'm sure there's a better way to do this, so I'm going to keep working on it.

```
a=strtoi(charToRaw(scan(,'',sep='\n')),16L)-95;a[a<0]=1;b=c(0,2,22,222,3,33,333,4,44,444,5,55,555,6,66,666,7,77,777,7777,8,88,888,9,99,999,9999)[a];c=append(b[-1],0)%%10;d=b%%10;b[c==d]=paste(b[c==d],'');paste(b,collapse='')

```

---
Tags: code-golf
---


title: Predictable unpredictability

text:
# Question
Title: Predictable unpredictability
Ever programmer knows, that programs need to be predictable. Any code that is not predictable will do something undefined and therefore most likely crash or worse. But when I tried to figure out what Java's `lazySet()` method does, I came up with the idea

**Is it possible to write a program that is unpredictable, yet works fine and does something useful/interesting?**

So that will be your task. Do not avoid chaos, but utilize it. Whether you use the actual lazySet, thread timing, random or uninitialized variables is up to you. The following rules apply:

1. The code-path must be unpredictable. That is: if I would debug it, the program would take a "random" path each time.
2. The program must do something useful/interesting and handle all possible (unpredictable) states somehow. No crashes! (Core dumps are neither useful nor interesting!)
3. You are not allowed to check something in a loop till it has the desired value. You must work with whatever is stored in there and do something with it.
4. You can use any language, except those specifically optimized for this contest.

This is a **creative question** so the one with the most votes wins. Please note that programs doing common stuff like gambling, printing random numbers or generating RPG loot are too well-known to be considered interesting. Please surprise us.

Bonus points should be given for:

* The creativity of the choice/design of unpredictability (Math.random isn't that creative).
* The creativity in management of unpredictability.
* Everything genius. ;)

# Answer
# Ruby

This works only on Windows.

```
if aTerribleErrorOccurredAndWeNeedToKillTheScriptNow
    c = ($$ % 94 + 33).chr
    puts "#{c * 50}\n#{c + "KILLING SCRIPT".center(48) + c}\n#{c * 50}"
    `taskkill /PID #{$$} /F`
end

```

The process ID, `$$`, is unpredictable. However, this will always kill the currently running script, while printing an error message bordered by an unpredictable character like this:

```
##################################################
#                 KILLING SCRIPT                 #
##################################################

```

Of course, `exit` or `quit` do the same thing, but this one kills Ruby forcefully with the OS! And it also bypasses `at_exit` handlers.
> 2 votes

---
Tags: popularity-contest
---


title: ASCII-art logic gate diagram

text:
# Question
Title: ASCII-art logic gate diagram
I challenge you to write a code to make an (extended) ASCII-art logic gate diagram for the sum of products form of an equation.

Use the following notation to represent gates:

AND
```
    INPUT───|&&
            |&&───OUTPUT
    INPUT───|&&

```
OR
```
    INPUT───|OR
            |OR───OUTPUT
    INPUT───|OR

```
Gates with more than 2 inputs
```
    INPUT───|OR
            |OR
    INPUT───|OR───OUTPUT
            |OR
    INPUT───|OR

```
NOT
```
    INPUT───│>o───OUTPUT

```

### Character set

Note that  is not an ASCII pipe sign but a box-drawing character. Use box-drawing characters such as `─ │ ┌ ┐ └ ┘` for connections.

### Example

Input
```
    A'*B'+B*C

```
Output
```
    A────│>o────│&&
                │&&─────┐
    B────│>o────│&&     └│OR
                         │OR─────A*B+B*C
    B───────────│&&     ┌│OR
                │&&─────┘
    C───────────│&&

```

### Winner

The winner is the answer with the most up-votes in 5 days

# Answer
> 16 votes
# C++11

*Done at last.* And it only took me most of the day.

Before I list the code and sample output, some quick notes:

### Things this program does support

* Any number of terms, each with any number of inputs
* Reusing inputs
* Omitting AND/OR gate representation when only one input would be present
* Use of both codepage 437 line-drawing characters and 7-bit ASCII-friendly characters (use -DCP437 or whatever your compiler's equivalent is for codepage 437 support)

### Things this program does not support

* Grouping with parentheses (because, seriously?)
* Multiple NOTing
* Any whitespace that isn't a plain ASCII space
* Proper golfification (although I did remove all the comments in spirit)
* Sane coding practices
* Making eye contact with the input parsing code
* Portable, Unicode line-drawing characters. I couldn't support Unicode because the rendering logic relies on being able to draw "down" a two-dimensional `char` buffer.

## Code

```
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <stdexcept>
#include <set>
#include <map>
#include <valarray>
#include <cmath>

using namespace std;

vector<string> split(const string str, const string delim)
{
    vector<string> v;

    set<char> d;
    for (char c : delim) d.insert(c);

    string current {};
    for (char c : str)
    {
        if (d.find(c) != d.end())
        {
            v.push_back(current);
            current = "";
        }
        else
        {
            current += c;
        }
    }
    v.push_back(current);

    return v;
}

using Input = string;
struct TermInput
{
    Input name;
    int ypos;
    bool neg;
};
using Term = vector<TermInput>;
using Expr = vector<Term>;

#ifdef CP437
constexpr char VERT    = '\xB3';
constexpr char HORIZ   = '\xC4';
constexpr char RBRANCH = '\xC3';
constexpr char LUP     = '\xD9';
constexpr char LDOWN   = '\xBF';
constexpr char RUP     = '\xC0';
constexpr char RDOWN   = '\xDA';
#else
constexpr char VERT    = '|';
constexpr char HORIZ   = '-';
constexpr char RBRANCH = '}';
constexpr char LUP     = '\'';
constexpr char LDOWN   = '.';
constexpr char RUP     = '`';
constexpr char RDOWN   = ',';
#endif

string repeat(string s, int n)
{
    stringstream ss;
    for (int i = 0; i < n; i++)
    {
        ss << s;
    }

    return ss.str();
}
string repeat(char c, int n)
{
    stringstream ss;
    for (int i = 0; i < n; i++)
    {
        ss << c;
    }

    return ss.str();
}

enum class Direction
{
    RIGHT,
    DOWN
};

void matrixPut(char *matrix, int h, int w, int x, int y, const string s, Direction dir)
{
    if (x >= w || y >= h)
    {
        stringstream ss;
        ss << "matrixPut: point (" << x << ", " << y << ") out of matrix bounds!";
        throw new out_of_range(ss.str());
    }

    char *ins = matrix + (y * w) + x;
    char *end = matrix + (h * w);
    for (char c : s)
    {
        if (ins >= end) break;
        *ins = c;

        if (dir==Direction::RIGHT)
        {
            ins++;
        }
        else
        {
            ins += w;
        }
    }
}

void matrixPrint(char *matrix, int h, int w)
{
    for (int i = 0; i < (h * w); i++)
    {
        cout << matrix[i];
        if ((i+1)%w == 0) cout << endl;
    }
}

int main (int argc, char *argv[])
{
    string expression;

    if (argc == 1)
    {
        cout << "Enter expression:" << endl;
        getline(cin, expression);
    }
    else
    {
        expression = argv[1];
    }

    expression.erase(remove(expression.begin(), expression.end(), ' '), expression.end());

    Expr expr {};
    auto inputs = set<Input>();
    auto termInputs = multimap<Input, TermInput>();

    int inputYPos = 0;

    auto e = split(expression, "+");
    for (string term : e)
    {
        Term currTerm {};

        auto t = split(term, "*");
        for (string in : t)
        {
            bool neg = false;
            if (in.back() == '\'')
            {
                in.pop_back();
                neg = true;
            }

            Input currInput {in};
            inputs.insert(currInput);

            TermInput ti {currInput, inputYPos, neg};
            currTerm.push_back(ti);

            termInputs.insert(pair<Input, TermInput>{in, ti});
            inputYPos++;
        }

        expr.push_back(currTerm);
        inputYPos++;
    }

    int height = inputs.size() + termInputs.size() + expr.size() - 1;

    int width = 0;

    width += max_element(inputs.begin(), inputs.end(), [](Input a, Input b){ return a.length() < b.length(); })->length() + 2;
    int inputWidth = width;
    width += inputs.size()*2;

    int notAndStart = width;

    width += 7;
    width += expr.size()+1;

    int orStart = width;

    width += 4;

    width += 4;

    width += expression.length();

    char matrix[height * width];
    for (int i = 0; i < height*width; i++) matrix[i] = ' ';

    int  baseY = inputs.size();

    {
        int x = width - 4 - expression.length();
        int y = baseY + ((height-baseY) / 2);
        matrixPut(matrix, height, width, x, y, repeat(HORIZ, 4) + expression, Direction::RIGHT);
    }

    {
        int x = orStart;
        int y = baseY + (height-baseY)/2 - expr.size()/2;

        if (expr.size() == 1)
        {
            matrixPut(matrix, height, width, x, y, repeat(HORIZ, 4), Direction::RIGHT);
        }
        else {
            matrixPut(matrix, height, width, x  , y, repeat(HORIZ, expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+1, y, repeat(VERT , expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+2, y, repeat('O'  , expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+3, y, repeat('R'  , expr.size()), Direction::DOWN);
        }
    }

    {
        int x = notAndStart;
        int y = baseY;
        for (Term t : expr)
        {
            string layer[7];
            for (TermInput ti : t)
            {
                layer[0] += HORIZ;
                layer[1] += (ti.neg ? '>' : HORIZ);
                layer[2] += (ti.neg ? 'o' : HORIZ);
                layer[3] += HORIZ;
                layer[4] += (t.size() > 1 ? VERT : HORIZ);
                layer[5] += (t.size() > 1 ? '&' : HORIZ);
                layer[6] += (t.size() > 1 ? '&' : HORIZ);
            }

            for (int i = 0; i < 7; i++)
            {
                matrixPut(matrix, height, width, x+i, y, layer[i], Direction::DOWN);
            }

            y += t.size() + 1;
        }
    }

    {
        int x = 0;
        int y = 0;

        for (Input i : inputs)
        {
            string str = i + ": ";
            str += repeat(HORIZ, inputWidth - str.length());

            matrixPut(matrix, height, width, x, y, str, Direction::RIGHT);

            y++;
        }
    }

    {
        int x = inputWidth;
        int num = 0;
        int offset = inputs.size() * 2 - 1;

        for (Input in : inputs)
        {
            int y = 0;
            int len = inputs.size() * 2 - 1;
            auto it = inputs.find(in);
            while (it != inputs.begin())
            {
                it--;
                y++;
                len -= 2;
            }
            matrixPut(matrix, height, width, x, y, repeat(HORIZ, len) + LDOWN, Direction::RIGHT);
        }

        for (Input in : inputs)
        {
            auto yBreakRange = termInputs.equal_range(in);
            valarray<int> yBreaks(termInputs.count(in));
            int idx = 0;
            for (auto ti = yBreakRange.first; ti != yBreakRange.second; ti++)
            {
                yBreaks[idx++] = baseY + ti->second.ypos;
            }

            for (int y : yBreaks)
            {
                matrixPut(matrix, height, width, x+offset, y, repeat(HORIZ, inputs.size()*2 - offset), Direction::RIGHT);
            }

            int y = num + 1;
            int maxBreak = yBreaks.max();
            string branch = repeat(VERT, maxBreak - y + 1);

            for (int i : yBreaks)
            {
                branch[i-y] = RBRANCH;
            }
            branch.back() = RUP;

            matrixPut(matrix, height, width, x+offset, y, branch, Direction::DOWN);

            offset -= 2;
            num++;
        }
    }

    {
        int x = notAndStart + 7;
        int outY = baseY + (height-baseY)/2 - expr.size()/2;
        int breakx = expr.size()/2;

        for (Term t : expr)
        {
            int inY = baseY + (t.front().ypos + t.back().ypos) / 2;

            matrixPut(matrix, height, width, x, inY, repeat(HORIZ, abs(breakx)+1), Direction::RIGHT);

            matrixPut(matrix, height, width, x+abs(breakx)+1, outY, repeat(HORIZ, expr.size()-abs(breakx)), Direction::RIGHT);

            if (inY < outY)
            {
                string branch = LDOWN + repeat(VERT, outY-inY-1) + RUP;
                matrixPut(matrix, height, width, x+abs(breakx)+1, inY, branch, Direction::DOWN);
            }
            else if (inY > outY)
            {
                string branch = RDOWN + repeat(VERT, inY-outY-1) + LUP;
                matrixPut(matrix, height, width, x+abs(breakx)+1, outY, branch, Direction::DOWN);
            }

            outY++;
            breakx--;
        }
    }

    cout << endl;
    matrixPrint(matrix, height, width);
    cout << endl;
}
```

## Sample output

```
$ ./gates "A'*B'+B*C"

A: -----.
B: ---. |
C: -. | |
    | | `->o-|&&--.
    | }--->o-|&&  `-|OR
    | |          ,--|OR----A'*B'+B*C
    | `------|&&-'
    `--------|&&

$ ./gates "A*B'*C+B*D'+F*C'*D+G*E*A'+F"

A: -------------.
B: -----------. |
C: ---------. | |
D: -------. | | |
E: -----. | | | |
F: ---. | | | | |
G: -. | | | | | |
    | | | | | | }----|&&
    | | | | | }--->o-|&&---.
    | | | | }--------|&&   |
    | | | | | | |          |
    | | | | | `------|&&--.|
    | | | }------->o-|&&  ||
    | | | | |   |         |`---|OR
    | }--------------|&&  `----|OR
    | | | | `----->o-|&&-------|OR----A*B'*C+B*D'+F*C'*D+G*E*A'+F
    | | | `----------|&&  ,----|OR
    | | |       |         |,---|OR
    `----------------|&&  ||
      | `------------|&&--'|
      |         `->o-|&&   |
      |                    |
      `--------------------'
```

## Sample output (with CP437 enabled)

```
A: ─────────────┐
B: ───────────┐ │
C: ─────────┐ │ │
D: ───────┐ │ │ │
E: ─────┐ │ │ │ │
F: ───┐ │ │ │ │ │
G: ─┐ │ │ │ │ │ │
    │ │ │ │ │ │ ├────│&&
    │ │ │ │ │ ├───>o─│&&───┐
    │ │ │ │ ├────────│&&   │
    │ │ │ │ │ │ │          │
    │ │ │ │ │ └──────│&&──┐│
    │ │ │ ├───────>o─│&&  ││
    │ │ │ │ │   │         │└───│OR
    │ ├──────────────│&&  └────│OR
    │ │ │ │ └─────>o─│&&───────│OR────A*B'*C+B*D'+F*C'*D+G*E*A'+F
    │ │ │ └──────────│&&  ┌────│OR
    │ │ │       │         │┌───│OR
    └────────────────│&&  ││
      │ └────────────│&&──┘│
      │         └─>o─│&&   │
      │                    │
      └────────────────────┘
```

# Answer
> 5 votes
# C++

Whew ! Done in 1 day 12 hrs!!!
This code handles array only

## INPUT (TYPES)

* Only SOP(sum of products) form.
* Only addition of terms with two variables multiplying

```
EXAMPLES :-

    A*B'+B*A+C*D

    X*Y+Z'*A'*V*D+B*G+C'*A'

```
* Can handle any number of terms,variables.

### **CODE :-**

```
#include<iostream>
using namespace std;
int main()
{
int i,j,k,l,m=0;
char arr[80][80],expr[45];
cout<<"enter the SOP(Sum Of products) expression : ";
cin>>expr;
cout<<"\n\n";
for(i=0;expr[i]!='\0';i++)
if(expr[i]=='*')m++;
for(i=0;i<80;i++)
    for(j=0;j<80;j++)
        arr[i][j]=' ';
for(i=0,j=0;i<80,expr[j]!='\0';j++)
{
    if(expr[j]<=90&&expr[j]>=65||expr[j]<=122&&expr[j]>=97)
    {
        arr[i][0]=expr[j];
        i+=2;
    }
}
for(i=0,j=1;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j-1]<=90&&arr[i][j-1]>=65||arr[i][j-1]<=122&&arr[i][j-1]>=97)
    {
        for(k=0;k<7;k++)
            arr[i][j+k]=196;
        arr[i][j+k]=180;
    }
}
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j]==(char)180&&arr[i][j+1]==' ')
    {
        arr[i][j+1]=38;
    }
}
for(i=0,j=0,k=1;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i-1][j]==(char)180&&arr[i+1][j]==(char)180)
    {
        if(arr[i-1][j+1]==(char)38&&arr[i+1][j+1]==(char)38&&k)
        {
            arr[i][j]=179;arr[i][j+1]=38;
            for(l=2;l<4;l++)
            {
                arr[i][j+l]=196;
            }
            k--;
        }
        else if(k==0)
        {
            k=1;
        }
    }
}
l=m;
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j-1]==(char)196&&arr[i][j+1]==' '&&arr[i][j-2]==(char)38)
        {
        if(arr[i+3][j-2]==(char)38)
        {
            for(k=0;k<l;k++)
                arr[i][j+k]=(char)196;
            arr[i][j+k-1]=(char)191;

            l--;
        }
        else
        {
            for(k=0;k<m;k++)
            arr[i][j+k]=(char)196;
        }
    }
}
for(i=0,j=0,k=1;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j]==(char)191&&arr[i][j-1]==(char)196)
    {
        for(;arr[i+k][j]==' ';k++)
        {
            arr[i+k][j]=(char)179;
        }
    k=1;
    }
}
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j]==(char)179&&arr[i][j-3]==(char)38&&arr[i+1][j]==(char)196)
    {
        arr[i][j]=(char)192;
        for(k=1;arr[i-k][j+k]==(char)179;k++)
        {
            arr[i-k][j+k]=(char)192;
        }
    }
}
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j-1]==(char)192)
    {
        for(k=0;arr[i][j+k]!=' ';k++)
            arr[i][j+k]=(char)196;
    }
}
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j-1]==(char)192&&arr[i][j]==' '||arr[i][j-1]==(char)196&&arr[i][j]==' ')
    {
        arr[i][j]=(char)180;
        arr[i][j+1]='O';
        arr[i][j+2]='R';
    }
}
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j-1]=='R'&&arr[i+1][j-1]==' ')
    {
        for(k=0;k<3;k++)
            arr[i][j+k]=(char)196;
        j+=k;
        for(k=0;expr[k]!='\0';k++)
        {
            arr[i][j+k]=expr[k];
        }
    }
}
for(i=0,k=0;i<80,expr[k]!='\0';k++)
{
    if((expr[k]<='z'&&expr[k]>='a'||expr[k]<='Z'&&expr[k]>='A'))
    {
        if(expr[k+1]=='\'')
            arr[i][1]='\'';
        i+=2;
    }
}
for(i=0,j=0;i<80;j++)
{
    if(j==80){i++;j=0;}
    if(arr[i][j]=='\''&&arr[i][j+1]==(char)196)
    {
        arr[i][j+3]=(char)180;
        arr[i][j+4]=(char)62;
        arr[i][j+5]='o';
    }
}
for(i=0;i<35;i++)
{
    for(j=0;j<80;j++)
        cout<<arr[i][j];
    cout<<'\n';
}
return 0;
}

```

## OUTPUT

---
Tags: popularity-contest, ascii-art
---


# Question
Title: POSIX reg. exp to test the divisibility by 9
Write the shortest POSIX-form regular expression that matches only non-negative integers divisible by 9. The non-negative integer should be given in base 10.

# Answer
> 1 votes
# 202,071 bytes

Obviously, the solution is too large to be included in this post.

I use JFLAP to draw the DFA, then generate regex from it. The output is then processed in a text editor to replace `(0+9)` with `[09]` and `+` with `|`.

Here is the whole gist, with some testing code in Java.

---
Tags: code-golf, regular-expression
---


title: Every 2^n times

text:
# Question
Title: Every 2^n times
Let `n` be the number of times your program has been executed. If `n` is a power of 2, then print `2^x` where `n = 2^x`; otherwise, simply output the number. Example run:

```
[1st time] 2^0
[2nd time] 2^1
[3rd time] 3
[4th time] 2^2
[5th time] 5

```

and so on. This is a popularity contest, so the answer with the most upvotes wins..

# Answer
## Java - API Abuse

There are plenty of computers online that can count, so why store the count myself?

Full-on abuse of the Stack API to get quota and remaining quota to see how many times it's been run today:

```
public static void main(String[] args) throws Exception {
    URLConnection c = new URL("http://api.stackexchange.com/2.2/info?site=stackoverflow").openConnection();
    c.setRequestProperty("Accept-Encoding", "gzip");
    GZIPInputStream gz = new GZIPInputStream(c.getInputStream());
    BufferedReader r = new BufferedReader(new InputStreamReader(gz));
    String reply = r.readLine();
    r.close();

    reply = reply.substring(reply.indexOf("quota_max"), reply.length()-1);
    String[] t = reply.split("[:,]");
    int runs = Integer.parseInt(t[1]) - Integer.parseInt(t[3]);
    if((runs & (runs -1)) == 0){
        int exp = 0;
        while(runs % 2 == 0){
            runs = runs >> 1;
            exp++;
        }
        System.out.println("2^" + exp);
    } else {
        System.out.println("" + runs);
    }
}

```

Obviously this only works with a fresh daily quota for your IP, and only *up to* the quota. If you want support for higher numbers, post a \[feature-request\] to raise `quota_max` to `MAX_INT`.
> 9 votes

# Answer
# JavaScript

`alert((n=Math.log((l=localStorage).m=~~l.m+1)/Math.log(2))==(n|0)?"2^"+n:l.m)`

Successive alerts are as follows:

```
2^0
2^1
3
2^2
5
6
7
2^3
9
...and so on.

```
> 7 votes

# Answer
## C – writing to the executable

This C code updates the string `data` in the executable, so essentially this is self-modifying code. If you run it over 9,999,999 times, you get interesting stuff.

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

int main(int argc,char **argv){
    //               'abcdefghijklmnopqrstuvwxyz1' << that's 27 characters inside the quotes
    const char *data="Da best marker in da world 1\0\0\0\0\0\0";
    FILE *f;
    int i,n,m;
    char c;
    long int pos;
    m=n=strtol(data+27,NULL,10);
    i=0;
    while(1){
        if(n==0){
            printf("This code should never have been reached... Unless you've messed with my executable.\n");
            return 1;
        }
        if(n==1){
            printf("2^%d\n",i);
            break;
        }
        if(n&1){
            printf("%d\n",m);
            break;
        }
        i++;
        n>>=1;
    }
    f=fopen(argv[0],"r+b");
    i=0;
    c=fgetc(f);
    while(!feof(f)){
        if(data[i]==c){
            i++;
            if(i==27)break;
        } else i=0;
        c=fgetc(f);
    }
    if(i!=27)return 1;
    n=0;
    pos=ftell(f);
    c=fgetc(f);
    while(c!='\0'){
        n=10*n+c-'0';
        c=fgetc(f);
    }
    n++; //The big increment!
    fseek(f,pos,SEEK_SET);
    fprintf(f,"%d",n);
    fflush(f);
    fclose(f);
    return 0;
}

```
> 7 votes

# Answer
# Java

The following code modifies it's own class file to store the new run count. This was especially fun when you had no idea how the byte code looks, but after countless hours of Googling and Testing it finally works! :)

Demo (using 7 as starting value for demo purposes):

```
[timwolla@/data/workspace/java]javac Runs.java
[timwolla@/data/workspace/java]java Runs
7
[timwolla@/data/workspace/java]java Runs
2^3
[timwolla@/data/workspace/java]java Runs
9
[timwolla@/data/workspace/java]java Runs
10

```

Code:

```
import java.io.*;
import java.util.*;

class Runs {

    public static void main(String[] args) throws Exception {
        // RUN-- makes the string easy to find in the byte code
        String runString = "RUN--1";

        // extract the number
        int runs = Integer.parseInt(runString.substring(5));

        // output the number properly
        int power = 0;
        boolean outputted = false;
        while (Math.pow(2, power) <= runs) {
            if (Math.pow(2, power) == runs) {
                outputted = true;
                System.out.println("2^"+power);
            }
            power++;
        }
        if (!outputted) System.out.println(runs);

        // increase run count
        runs++;

        // build new string
        String newRunString = runString.substring(0, 5) + runs;

        // get folder of class file
        String folder = Runs.class.getProtectionDomain().getCodeSource().getLocation().getFile();
        // append class file name
        String me = folder + "/Runs.class";

        // and open it up
        RandomAccessFile in = new RandomAccessFile(me, "rw");

        int read;
        int state = 0;
        while ((read = in.read()) != -1) {
            char c = (char) read;

            // state machine to find the RUN--
            switch (state) {
                case 0:
                    // 2 bytes before: upper byte of the two byte length
                    if (c == ((runString.length() >> 8) & 0xFF)) state++;
                break;
                case 1:
                    // 1 byte before: lower byte of the two byte length
                    if (c == (runString.length() & 0xFF)) state++;
                    else state = 0;
                break;
                case 2:
                    if (c == 'R') state++;
                    else state = 0;
                break;
                case 3:
                    if (c == 'U') state++;
                    else state = 0;
                break;
                case 4:
                    if (c == 'N') state++;
                    else state = 0;
                break;
                case 5:
                case 6:
                    if (c == '-') state++;
                    else state = 0;
                break;
                case 7:
                    // we found run, now: Modify byte code

                    // back to the bytes that determine the length
                    in.seek(in.getFilePointer() - 8);

                    // expand the file if neccessary
                    int lengthChange = (newRunString.length() - runString.length());
                    in.setLength(in.length() + lengthChange);

                    // write new length
                    in.writeByte(((newRunString.length() >> 8) & 0xFF));
                    in.writeByte((newRunString.length() & 0xFF));

                    // length changed, shift all the following bytes by one
                    if (lengthChange > 0) {
                        long target = in.getFilePointer();
                        in.seek(in.length() - 1 - lengthChange);
                        while (in.getFilePointer() > target) {
                            in.write(in.read());
                            in.seek(in.getFilePointer() - 3);
                        }
                        in.seek(target);
                    }

                    // write new string
                    in.writeBytes(newRunString);

                    return;
                case 8:
            }
        }
    }
}

```
> 7 votes

# Answer
# perl

Here's a short bit of perl to do it. Where should the data be stored? Why in the program file itself, of course! =)

```
$b = sprintf '%b', $x=x();
print $b=~/^10*$/ ? "2^".(length($b)-1) : $x, "\n";
open F, "+<", $0;
seek F, -3-length $x, 2;
print F $x+1, " }\n";
sub x { 1 }

```

Originally I had used the magic DATA file handle like so, but I feel the above is "purer":

```
$b = sprintf '%b', $x = <DATA>;
print $b =~ /^10*$/ ? "2^".(length($b)-1)."\n" : $x;
open F, "+<", $0;
seek F, -length $x, 2;
print F $x+1, "\n";
__DATA__
1

```
> 6 votes

# Answer
**Sinatra-based Ruby Example**

This server-based solution stores a personal counter for each user in a cookie.

Try it at http://every-2-to-the-n-times.herokuapp.com/

```
require 'sinatra'
require 'sinatra/cookies'

# https://github.com/sinatra/sinatra-contrib/issues/113
set :cookie_options, :domain => nil

get '/' do
   x = cookies[:x].to_i || 1
   cookies[:x] = x + 1

   # power of 2 test from http://grosser.it/2010/03/06/check-if-a-numer-is-a-power-of-2-in-ruby/
   return (x & (x - 1) == 0) ? "2^#{Math.log2(x).to_i}" : x.to_s
end

```
> 5 votes

# Answer
# dg

Here I present you a portable code! At every run a `#` is added at the end, making a progress bar! Also, you can move the code to another machine and resume from where you were.

```
import '/math'

with fd = open __file__ 'r' =>
  code = fd.read!
  times = code.count('#') - 2
with fd = open __file__ 'w' =>
  fd.write $ code.rstrip! + '#'
exp = math.log2 times
if exp.is_integer! => print $ '2^{}'.format $ int exp
   otherwise => print times

#

```

After 18 times:

```
import '/math'

with fd = open __file__ 'r' =>
  code = fd.read!
  times = code.count('#') - 2
with fd = open __file__ 'w' =>
  fd.write $ code.rstrip! + '#'
exp = math.log2 times
if exp.is_integer! => print $ '2^{}'.format $ int exp
   otherwise => print times

###################

```
> 5 votes

# Answer
## Bash

Simple self-editing shell script.

```
n=1;e=0;p=1
sed -i s/"n=$n"/"n=`expr $n + 1`"/g $0
if [[ $n -eq $p ]];then
    echo 2^$e
    sed -i s/"p=$p"/"p=`expr $p \* 2`"/g $0
    sed -i s/"e=$e"/"e=`expr $e + 1`"/g $0
else
    echo $n
fi

```
> 3 votes

# Answer
# Bash

I like dfernig's Bash solution, but I would like to post mine as well:

```
n=$(expr `cat $0|wc -c` - 170)
if [ $(echo "obase=2;$n"|bc|grep -o 1|wc -l) == 1 ]
then echo -n "2^"; echo "obase=2;$n"|bc|grep -o 0|wc -l;
else echo $n; fi
echo "" >> $0

```

I think the solution can be considered different, because

* the code actually executed doesn't change
* the program dinamically calculates if **n** is a power of 2

The "memory" is the script size (initially 171 bytes), which is increased by 1 with the append of a newline at each execution.
Powers of 2 are recognized by converting the program size (minus 170, of course) to binary, and then counting the ones: if there is exactly one one, then **n** is a power of 2. The exponent is the number of zeros in binary.
> 2 votes

# Answer
## Javascript

I chose to not use the obvious `log2` solution but work with bitwise operators to find the single bit position in the binary representation of power of 2 numbers.

```
Number.prototype.singleBitPosition = function() {
  var r=1, k;
  if (this==0) return -1;
  while(this==(k=this>>r<<r)) r++; //set r last bits to zero and compare
  return k?-1:r; //if k is zero, there is one single bit to 1 in number representation ie power of 2
};

var n;
if (n === undefined) n=0;
n++;

var e = n.singleBitPosition();
if (e > 0) {
  console.log('2^'+(e-1));
} else {
  console.log(n);
}

```
> 1 votes

# Answer
# Java solution

Uing the java preferences API to store the run amount; and precalculated the powers of 2 for a hashmap to compare

```
import java.util.HashMap;
import java.util.prefs.Preferences;
class Pow
{
    public static void main(String[]a)
    {
        int rt = Integer.valueOf(Preferences.userRoot().get("Pow.run", "1"));
        HashMap<String,Integer> powof2 = new HashMap<>();
        //pregenerating the powers of 2;
        for (int i = 0; i < 46340; i++)//highest power of 2 before int overflow
        {
            powof2.put(((int)Math.pow(2, i))+"",i);
        }
        if(powof2.containsKey(rt+""))
        {System.out.println("2^"+powof2.get(rt+""));}
        else
        {
            System.out.println(rt);
        }
        rt++;
        Preferences.userRoot().put("Pow.run", ""+(rt));
    }
}

```
> 1 votes

# Answer
# Fortran 77

**Code:**

```
      program twok
      rewind 1
      read(1,'(I20,I3)',end=10,err=30)n,k
      go to 20
10    n=-1
      k=0
20    n=n+1
      if (n .eq. 2**k) then
        if (k.le.9) then
          write(*,'(A3,i1)')' 2^',k
        else
          write(*,'(A3,i2)')' 2^',k
        endif
        k=k+1
      else
        write(*,*)n
      endif
      if (n .lt. 0) then
         n=-1
         k=0
      endif
      rewind 1
      write(1,'(I20,I3)')n,k
30    continue
      end

```

**Result:**

```
$ ./a.out       !       $ ./a.out
 2^0            !        2^1
$ ./a.out       !
 2^1            !       $ while true
$ ./a.out       !       > do
 3              !       > ./a.out | grep "2^"
$ ./a.out       !       > done
 2^2            !        2^2
$ ./a.out       !        2^3
 5              !        2^4
$ ./a.out       !        2^5
 6              !        ...
...             !        2^12
$ ./a.out       !        2^13
 2147483647     !       ^C # (after about 5 minutes)
$ ./a.out       !       $ ./a.out
 2^31           !        14718
$ ./a.out       !       $ ./a.out
 0              !        14719
$ ./a.out       !       $
 2^0            !

```
> 1 votes

# Answer
## Ruby

Alright, I think I'll try this now. It searches itself for the definition of `n`.

```
def p2 n
  n == 1 ? 0 : p2(n >> 1) + 1
end
n = 1
if (n != 0) & (n & (n - 1) == 0) || n == 1
  puts("2^" + (p2(n).to_s))
else
  puts n
end

contents = File.read(__FILE__)
newContents = contents.gsub(/(?<=n \= )[0-9]+/) {|n| (n.to_i + 1).to_s}
File.write(__FILE__, newContents)

```

(tested in Ruby 1.9.3)
> 1 votes

# Answer
# C

One of the "proper" ways to do it (without using files, that is).

You can give it `reset` on the command line to set it back to zero. You can also move or copy the executable around. Moving the executable resets it, and multiple copies of the executable are independent.

```
#include <stdio.h>
#include <sys/msg.h>
#include <sys/shm.h>

int main(int argc, char **argv) {
   // get a shared memory segment associated with our program
   long key = ftok(argv[0], 1);
   long id = shmget(key, sizeof(long), 0666 | IPC_CREAT);
   long *num = (long*) shmat(id, NULL, 0);

   // reset parameter
   if (argc == 2 && !strcmp(argv[1], "reset")) {
      *num = 0;
   }

   if (*num & *num-1) {
      // not a power of two
      printf("%li\n", *num);
   } else {
      // power of two
      int exp = 0;
      int n=*num;
      while (n >>= 1) exp++;
      printf("2^%d\n", exp);
   }

   ++*num;

   // detach from shared memory
   shmdt(num);
   return 0;
}

```
> 1 votes

# Answer
Sparkling, 423 characters (yet another self-modifying code). Save it as `count.spn` then run `spn count.spn`:

```
var n =
19
;

var l = log2(n);
if l == floor(l) {
    printf("2 ^ %d\n", floor(l));
} else {
    printf("%.0f\n", n);
}

var f = fopen("count.spn", "rb");
var g = fopen("count.spn.2", "wb");
var line = fgetline(f);
fprintf(g, "%s", line);
fprintf(g, "%d\n", n + 1);
fgetline(f);

while (line = fgetline(f)) != nil {
    fprintf(g, "%s", line);
}

fclose(f);
fclose(g);

```
> 1 votes

# Answer
Here's a quick Python 3 solution, which uses a data file to store `n` and `x` between runs:

```
try:
    with open("count.txt") as f:
        n, x = map(int, f.readline().split())
except FileNotFoundError:
    n = x = 0

n += 1
if n == 2**x:
    print("2^{}".format(x))
    x += 1
else:
    print(n)

with open("count.txt", "w") as f:
    f.write("{} {}".format(n, x))

```

The output of running it 16 times:

```
2^0
2^1
3
2^2
5
6
7
2^3
9
10
11
12
13
14
15
2^4

```
> 0 votes

# Answer
# Python 2

```
import inspect
import math

file_name = inspect.getfile(inspect.currentframe())

n = int(open(file_name).readlines()[-1].strip())

l = math.log(n, 2)
if int(l) == l:
    print '2^%d' % (l)
else:
    print n

with open(file_name, 'a') as f:
    f.write('%d\n' % (n + 1))

1

```
> 0 votes

# Answer
# C#

```
static void Main()
{
  ulong cnt         = ++Properties.Settings.Default.NumberOfExecutions ;
  int?  log2        = Log2( cnt ) ;
  Console.WriteLine( log2.HasValue ? "2^{0}" : "{1}" , log2 , cnt ) ;
  Properties.Settings.Default.Save() ;
  return ;
}

static int? Log2( ulong m )
{
  int? n = null ;
  if ( m > 0 )
  {
    n = 0 ;

    // find the first set bit
    ulong mask = 0x0000000000000001ul ;
    while ( mask != 0 && 0ul == (m&mask) )
    {
      mask <<= 1 ;
      ++n ;
    } ;

    // if the mask is identical to m,
    // we've got a power of 2: return n, otherwise null
    n = mask == m ? n : null ;

  }
  return n ;
}

```

This does, though, require that you define a settings property in your Visual Studio project:
> 0 votes

# Answer
# C/POSIX

This program uses the number of hard links to its own executable as counter of how often it was called. It creates the new hard links in the directory it was started from (because that way it's guaranteed to be on the same file system), which therefore needs write permission. I've omitted error handling.

You better make sure that you have no important file with the same name as one of the created hard links on that directory, or it will be overwritten. If e.g. the executable is named `counter`, the hard links will be named `counter_1`, `counter_2` etc.

```
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[])
{
  /* get persistent counter */
  struct stat selfstat;
  stat(argv[0], &selfstat);
  int counter = selfstat.st_nlink;

  /* determine digits of counter */
  int countercopy = counter;
  int digits = 1;
  while (countercopy /= 10)
    ++digits;

  /* increment persistent counter */
  char* newname = malloc(strlen(argv[0]) + digits + 2);
  sprintf(newname, "%s_%d", argv[0], counter);
  link(argv[0], newname);

  /* output the counter */
  if (counter & (counter-1)) // this is zero iff counter is a power of two
    printf("%d\n", counter);
  else
  {
    /* determine which power of 2 it is */
    int power = 0;
    while (counter/=2)
      ++power;
    printf("2^%d\n", power);
  }
  return 0;
}

```

Example run (the first line resets the counter, in case the executable has already been run):

```
$ rm counter_*
$ ./counter
2^0
$ ./counter
2^1
$ ./counter
3
$ ./counter
2^2
$ ./counter
5
$ ./counter
6
$ ./counter
7
$ ./counter
2^3
$ ./counter
9
$ ls counter*
counter    counter_2  counter_4  counter_6  counter_8  counter.c
counter_1  counter_3  counter_5  counter_7  counter_9  counter.c~

```
> 0 votes

# Answer
# Fortran 95

A file named "a" (without extension) keeps track of the run of the program.

```
logical::l
inquire(file="a",exist=l)
open(unit=11,file="a")
if (l) then
  read(11,*)n
  close(unit=11,status="delete")
  open(unit=11,file="a")
  n=n+1
  write(11,*)n
  do i=1,n
    if (2**i==n) then
      write(*,"(A2,I1)")"2^",i
      goto 1
    endif
  enddo
  print*,n
  else
    print*,"2^0"
    write(11,*)1
endif
1 end

```
> 0 votes

---
Tags: popularity-contest
---


title: Ascii art pie chart

text:
# Question
Title: Ascii art pie chart
Your goal is to output an ASCII art pie chart. This is code-golf, so the shortest program (counting the bytes of the source code, not the characters) wins.

No external softwares or APIs are allowed. Only the native ones of each language.

The starting angle and the direction (clockwise/anticlockwise) of the circle are not important. The output can look oval because the height of a character is always superior to its width.

The "background" (characters at the left or the right of the pie) must be spaces.

As input, you have three variables (please post the code for initializing it. The initialization of these variables is not counted in your score) :

* `k` : Array of characters. Each character is the one which has to be used on the pie chart
* `v` : Array of floats. It's the percentage of each character. The length of `v` is equal to the length of `k`. The sum of it's elements is always 1.0
* `r` : Integer \> 1. It's the radius of the pie chart.

Bonus : Subtract 20% of your score if your can output an incomplete pie (in case the \\$(\sum\_{i=1}^{|v|} v\_i)\<1\\$).

# Answer
# Python: 255 chars - 20% = 204

```
from math import*
def s(k,v,a):
 if not v:return ' '
 if a<v[0]:return k[0]
 return s(k[1:],v[1:],a-v[0])
def p(k,v,r):
 d=range(-r,r)
 for y in d:
  t=""
  for x in d:
   if x*x+y*y<r*r:
    a=atan2(y,x)/pi/2+.5
    t=t+s(k,v,a)
   else:t=t+" "
  print t

```

Examples:

```
>>> pie.p("ABCD", [0.25,0.125,0.125,0.125],8)

     AAABBBB
   AAAAABBBBBB
  AAAAAABBBBBCC
  AAAAAABBBBCCC
 AAAAAAABBBCCCCC
 AAAAAAABBCCCCCC
 AAAAAAABCCCCCCC
        DDDDDDDD
          DDDDDD
           DDDDD
            DDDD
             DD
              D

>>>

>>> pie.p(".$!@", [0.3,0.3,0.3,0.1],6)

   .....$$
  ......$$$
 ......$$$$$
 ......$$$$$
 ......$$$$$
 @@@@@$$$$$$
 @@@@!!!$$$$
 @@@!!!!!$$$
 @!!!!!!!!!$
  !!!!!!!!!
   !!!!!!!
>>>

```
> 6 votes

# Answer
## JavaScript, 259

```
d=r*2;M=Math;R=M.round;p=[];for(y=0;y<d;y++){p[y]=[];for(x=0;x<d;x++)p[y][x]=" "}t=0;i=-1;for(f=0;f<1;f+=1/(r*20)){if(f>t)t+=v[++i];a=M.PI*2*f;for(j=0;j<r;j++)p[R(M.sin(a)*j)+r][R(M.cos(a)*j)+r]=k[i]}s="";for(y=0;y<d;y++){for(x=0;x<d;x++)s+=p[y][x];s+="\n";}s

```

Works in Firefox scratchpad.

## First example

Input :

```
var k = ["#", "+",  "$",  "X"];
var v = [0.2, 0.4, 0.15, 0.25];
var r = 10;

```

Output :

```
       $$$XXXX
     $$$$$XXXXXX
    $$$$$$XXXXXXX
   $$$$$$$XXXXXXXX
  +$$$$$$$XXXXXXXXX
  ++$$$$$$XXXXXXXXX
 +++++$$$$XXXXXXXXXX
 ++++++$$$XXXXXXXXXX
 +++++++$$XXXXXXXXXX
 +++++++++XXXXXXXXXX
 ++++++++++#########
 +++++++++++########
 +++++++++++########
  ++++++++++#######
  +++++++++++######
   ++++++++++#####
    +++++++++####
     ++++++++###
       +++++++

```

## Second example :

Input :

```
var k = ["A",  "B", "C" ];
var v = [0.5, 0.25, 0.25];
var r = 5;

```

Output :

```
   BBCCC
  BBBCCCC
 BBBBCCCCC
 BBBBCCCCC
 BBBBCCCCC
 AAAAAAAAA
 AAAAAAAAA
  AAAAAAA
   AAAAA

```
> 7 votes

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


# Question
Title: Determine which of two ImageMagick .TXT images is more saturated
You have two images (64x64 pixels each):

Your program must take the file names of each of them as command line arguments and determine which has more average saturation among their pixels.

The images are in ImageMagick .txt format. You can download and convert these images using `convert pic.png pic.txt` or download the raw text (saturated, desaturated)

Ignore the first line of the file (required).

Solutions in Assembly get 50% of their characters for free. Brainfuck, whitespace, and close variants, get 25% of their characters for free. (e.g. if it takes 200 characters in Brainfuck; mark it as 200-50=150.)

Describe your output. It could be the name of the more saturated image; the index of it (0 for first, 1 for second); true for the first, false for the second, etc. Just let us know.

It should be able to take either the saturated or desaturated image first, and accurately report the more saturated (test both ways). The filenames shouldn't be considered when evaluating saturation (e.g. no `if filename contains 'desaturated'...`)

Shortest answer wins. Happy coding :-)

# Answer
## J (~~96~~ ~~94~~ 92)

```
echo/:(+/@:(m%(m=.>./)-<./)"1@:>@:(".&.>)@:((': (\(.*?\))';,1)&rxall)@:(1!:1)@:<)&.>2}.ARGV

```

Takes input from the command line as .txt files. It can take any number of files, and outputs a list of indices from saturated to unsaturated, i.e.:

```
$ jconsole saturated.j saturated.txt desaturated.txt
0 1
$ jconsole saturated.j desaturated.txt saturated.txt
1 0

```

I've simplified the normal formula a bit: it does not bother to normalize the RGB values to \[0..1\], it uses the sum of the saturation per pixel rather than the average, and it actually calculates the inverse of the saturation and then sorts up. As long as the images are the same size (which they are), this does not affect the sort order which is what it's about.

Explanation:

* `2}.ARGV`: the command line minus its first two elements
* `&.>`: for each of these, do:
* `(1!:1)@:<`: read file
* `((': (\(.*?\))';,1)&rxall)`: use a regex to match the pixel values
* `(".&.>)`: execute each match as J code. `(1,2,3)` becomes the list `1 2 3` so now we have the pixel values.
* `>`: make a matrix from the list of lists
* `"1`: operate on the rows of the matrix
* `(m%(m=.>./)-<./)`: `MAX / (MAX - MIN)`, the inverse of the saturation
* `+/`: sum
* `/:`: sort up, so that the images are sorted in `S^(-1)` ascending, which gives the same order as `S` descending.
* `echo`: output the list
> 2 votes

# Answer
## bash etc. and Image Magick (136 chars)

```
for x in "$@";do convert "$x" -colorspace HSL -channel G -separate -scale 1x1 t.txt
echo `sed "1d;s%.*#\(..\).*%\1%" t.txt` $x;done|sort

```

The way I see it, the easiest way to deal with the complexities of the Image Magick file format is to let Image Magick do it. `t.txt` seems to be the shortest possible filename which guarantees the correct output file format. The first 4 `"` could arguably be removed, but that would decrease robustness in the face of filenames with spaces in.

Sample output:

```
$ ./cmpsat.sh img-sat.txt img-desat.txt rose:
24 img-desat.txt
69 rose:
FE img-sat.txt

```
> 6 votes

# Answer
## Mathematica 92 215

**Edit**

To work directly with the Magick files I had to make substantial revisions to my first try.

---

**Filenames**

Stored as variables, *x*, *y*.

```
x = "http://pastebin.com/raw.php?i=5f3B4uxP";
y = "http://pastebin.com/raw.php?i=VdjDm9HK";

```

---

The following routine sorts image files by average saturation (least to greatest). (Spaces added for readability.)

```
i = Image; d = DigitCharacter;
f[t_] := {Mean[Flatten[ImageData[ColorConvert[i[i[Partition[(StringCases[URLFetch[t],
   "rgb(" ~~ a : d .. ~~ "," ~~ b : d .. ~~ "," ~~c : d .. ~~ ")" :> ToExpression
   /@ {a, b, c}])/255., 64]]], "RGB" -> "HSB"]], 1][[All, 2]]], t}

```

**Usage**

```
Sort@{f[x], f[y]}

```

**Output** (saturation value, followed by filename).

> {{0.229977, "http://pastebin.com/raw.php?i=VdjDm9HK"},
> {0.958346, "http://pastebin.com/raw.php?i=5f3B4uxP"}}

---

**Explanation**

`URLFetch[x]` fetches the Magick textfile, the name of which is stored in `x`

`StringCases[URLFetch[t],
 "rgb(" ~~ a : d .. ~~ "," ~~ b : d .. ~~ "," ~~c : d .. ~~ ")" :> ToExpression
 /@ {a, b, c}])/255., 64]]], "RGB" -> "HSB"]` finds the RGB values and, along with `Partition` converts them to the format Mathematica expects to find RGB files in.

`ColorConvert` converts to `Hue-Saturation-Brightness` values. `Mean` and `[[All,2]]` find the mean saturation values for the file.
> 1 votes

# Answer
## Brainf\**k, 117 - 25% = 87.75

Requires an interpreter with 8-bit wrapping cells (this is the most common type).

```
>+[,<++++[->--------<]>[>+<]++++[->++++++++<]>]>>
>+[,<++++[->--------<]>[>+<]++++[->++++++++<]>]>
[-<<<[-]>>>]<<<[.]

```

Just input the text render of the first image and the second image. Make sure the files end with the `NUL` character (ASCII value 0). If the first image is larger, it will output how much larger it is than the second one (in the ASCII value). If the second image is larger, nothing will be printed.
> 0 votes

---
Tags: code-golf, image-processing
---


title: king + rook vs king

text:
# Question
Title: king + rook vs king
It's the ending of another well played chess game. You're the white player, and you still have a rook and your king. Your opponent only has his king left.

Since you're white, it's your turn. Create a program to play this chess match. Its output can be a sequence of moves, a gif animation, ASCII art or whatever you like.

It seems quite obvious, but I'll state it explicitly: you have to win the game (in a finite number of moves). It's always possible to win from this position. DO NOT LOSE THAT ROOK. DO NOT STALEMATE.

Your program may or may not accept a human input for the starting position and for each black move (you can safely assume this is a legal position, i.e. the kings are not touching each other). If it doesn't, a random starting position and random movements for the black king will suffice.

## Score

Your score will be length in byte of your code + bonus. Any language is allowed, lowest score wins.

### Bonus

-50 if your program allows both a human defined starting position and a random one. Humans can enter it via stdin, file, GUI...

-100 if your program allows both a human and a random player to move the black king

+12345 if you rely on an external chess solver or a built-in chess library

Good luck!

# Update!

Extra rule: The match must be played until checkmate. Black does not resign, doesn't jump outside the chessboard and doesn't get kidnapped by aliens.

## Hint

You can probably get help from this question on chess.se.

# Answer
# Haskell 1463-100=1363

Just getting an answer in. This finds the solution the retrograde way, working back from checkmate to the position we're in. It differs from the description of retrograde analysis on chessprogramming \- instead of starting with an initial set and expanding it with backwards moves until no squares moved to haven't been seen, it starts with all unused squares and reduces that set by trying forward moves. This is going to be less time-efficient than the traditional way, but the memory usage exploded for me when I tried it.

Compile with `ghc -O2` for acceptable performance for the endgame table calculation; play is instant after the first move. Supply white king, rook, black king squares as arguments. For a move, it just wants a square, and will pick one for you if you press return. Example session:

```
$ time  printf "\n\n\n\n\n\n\n\n"|./rook8 e1 a1 e8
("e1","a7","e8")[d8]?
("d2","a7","d8")[c8]?
("d2","h7","c8")[b8]?
("c3","h7","b8")[a8]?
("b4","h7","a8")[b8]?
("c5","h7","b8")[a8]?
("b6","h7","a8")[b8]?
("b6","h8","b8") mate

real    0m8.885s
user    0m8.817s
sys 0m0.067s

```

Code:

```
import System.Environment
import qualified Data.Set as S
sp=S.partition
sf=S.fromList
fl=['a'..'h']
rk=[0..7]
lf=filter
m=map
ln=notElem
lh=head
pl=putStrLn
pa[a,b]=(lh[i|(i,x)<-zip[0..]fl,a==x],read[b]-1)
pr(r,c)=fl!!r:show(c+1)
t f(w,r,b)=(f w,f r,f b)
km(a,b)=[(c,d)|c<-[a-1..a+1],d<-[b-1..b+1],0<=c,c<=7,0<=d,d<=7]
vd (w,r,b)=b`ln`km w&&w/=r&&b/=w&&b/=r
vw p@(_,r,b)=vd p&&r`ln`km b&&(ck p||[]/=bm p)
vb p=vd p&&(not.ck)p
rm (w@(c,d),(j,k),b@(u,x))=[(w,(j,z),b)|z<-rk,z/=k,j/=c||(k<d&&z<d)||(d<k&&d<z),j/=u||(k<x&&z<x)||(x<k&&x<z)]
kw(w,r,b)=m(\q->(q,r,b))$km w
xb(w,r,_)b=(w,r,b)
wm p=lf(\q->q/=p&&vw q)$rm p++(m(t f)$rm$t f p)++kw p
bm p@(_,_,b)=lf(\q->q/=p&&vb q)$m(xb p)$km b
c1((c,d),(j,k),(u,x))=j==u&&(c/=j||(k<x&&d<k)||(k>x&&d>k))
ck p=c1 p||(c1$t f p)
mt p=ck p&&[]==bm p
h(x,y)=(7-x,y)
v=f.h.f
f(x,y)=(y,x)
n p@((c,d),_,_)|c>3=n$t h p|d>3=n$t v p|c>d=n$t f p|True=p
ap=[((c,d),(j,k),(u,x))|c<-[0..3],d<-[c..3],j<-rk,k<-rk,u<-rk,x<-rk]
fr s p=S.member(n p)s
eg p=ef(sp mt$sf$lf vw ap)(sf$lf vb ap)
ps w mv b0=sp(\r->any(fr b0)$mv r)w
ef(b0,b1)w=let(w1,w2)=ps w wm b0 in(w1,b0):(if S.null w2 then[]else ef(f$ps b1 bm w2)w2)
lu((w1,b0):xs)p=if fr w1 p then lh$lf(fr b0)$wm p else lu xs p
th(_,_,b)=b
cd tb q=do{let{p=lu tb q};putStr$show$t pr p;if mt p then do{pl" mate";return()}else do{let{b1=pr$th$lh$bm p};pl("["++b1++"]?");mv<-getLine;cd tb$xb p (pa$if""==mv then b1 else mv)}}
main=do{p1<-getArgs;let{p2=m pa p1;p=(p2!!0,p2!!1,p2!!2)};cd(eg p)p}

```

Edited: Fixed code to remember endgame table and use arguments, so much less painful to test repeatedly.
> 12 votes

# Answer
# C, Currently 2552 noncomment nonwhitespace characters

The count indicates to me that I could golf it down below 2552 total chars, but given there is already a smaller answer (which will be tough to beat) I will consider that carefully before bothering to do it. It's true there's about 200 chars for displaying the board and another 200 each for checking user input of both start position and move (which i need for testing, but could eliminate.)

No game tree here, just hardcoded algorithm, so it moves instantly.

Start positions are entered as row (1-8) column (1-8) numbered from top right and the program works on the same scheme. So if you turned your screen 90 degrees anticlockwise, it would follow the standard Correspondence Chess numeric square notation. Positions where the black king is already in check are rejected as illegal.

Black moves are entered as a number from 0 to 7, with 0 being a move to the north, 1 to the northeast and so on in a clockwise sense.

It doesn't follow the commonly known algorithm that exclusively uses the rook under the protection of the white king to restrict the black king. The rook only restricts the black king in a vertical sense (and will run away horizontally if chased.) The white king restricts the black king in horizontal movement. This means the two white pieces do not get in each others' way.

I seem to have ironed out most of the bugs and possible infinite loops, it's running pretty well now. I will play with it again tomorrow and see if there is anything else that needs fixing.

```
#include "stdafx.h"
#include "stdlib.h"
#include "string.h"

int b[2], w[2], r[2], n[2],s,t,i,nomate;
int v[2][8] = { {-1,-1,0,1,1,1,0,-1}, {0,1,1,1,0,-1,-1,-1} };
int u[5] = { 0, 1, -1, 2, -2 };
char empty[82] = "        \n--------\n--------\n--------\n--------\n--------\n--------\n--------\n--------\n";
char board[82];

int distance(int p[2], int q[2]){
    return __max(abs(p[0]-q[0]),abs(p[1]-q[1]));
}

int sign(int n){
    return (n>0)-(0>n);
}

// from parameters p for white king and q for rook, determines if rook is/will be safe
int rsafe(int p[2],int q[2]){
    return  distance(p, q)<2 | distance(q,b)>1;
}

void umove(){
    t=0;
    while (t != 100){
        printf("Enter number 0 to 7 \n");
        scanf_s("%d", &t); t %= 8;
        n[0] = b[0] + v[0][t];
        n[1] = b[1] + v[1][t];
        if (distance(w, n) < 2 | (n[0] == r[0] & (n[1]-w[1])*(r[1]-w[1])>0)
            | ((n[1] == r[1]) & (n[0]-w[0])*(r[0]-w[0])>0) | n[0] % 9 == 0 | n[1] % 9 == 0)
            printf("illegal move");
        else{ b[0] = n[0]; b[1] = n[1]; t = 100; };
    }
}

void imove(){
    t=0;
    // mate if possible
    if (distance(b, w) == 2 & b[0] == w[0] & (b[1] == 1 | b[1] == 8) & r[0]!=w[0]){
        n[0] = r[0]; n[1] = b[1];
        if (rsafe(w, n)){
            r[1] = n[1];
            printf("R to %d %d mate!\n", r[0], r[1]);
            nomate=0;
            return;
        }
    }

    //avoid stalemate
    if ((b[0] == 1 | b[0] == 8) & (b[1] == 1 | b[1] == 8) & abs(b[0] - r[0]) < 2 & abs(b[0]-w[0])<2){
        r[0] = b[0]==1? 3:6;
        printf("R to %d %d \n", r[0], r[1]);
        return;
    }

    // dont let the rook be captured.
    if(!rsafe(w,r))
    {
        if (w[0] == r[0]) r[1] = w[1] + sign(r[1]-w[1]);
        else r[1] = r[1]>3? 2:7;
        printf("R to %d %d \n", r[0], r[1]);
        return;
    }

    // if there's a gap between the kings and the rook, move rook towards them. we only want to do this when kings on same side of rook, and not if the black king is already on last row.
    if (abs(w[0]-r[0])>1 & abs(b[0] - r[0]) > 1 & (b[0]-r[0])*(w[0]-r[0])>0 & b[0]!=1 & b[0]!=8){
        n[0] = r[0] + sign(b[0] - r[0]); n[1] = r[1];
        if (rsafe(w, n)) r[0] = n[0];
        else r[1] = r[1]>3? 2:7;
        printf("R to %d %d \n", r[0], r[1]);
        return;

    }
    // if kings are far apart, or if they not on the same row (except if b 1 row from r and w 2 rows from r), move king
    if ((w[0]-r[0])!=2*(b[0]-r[0]) | abs(b[0]-w[0])>1 | distance(w,b)>2){
        for (i = 0; i<8; i++) if (v[0][i] == sign(b[0] - w[0]) & v[1][i] == sign(b[1] - w[1])) t = i;
        s = 1 - 2 * (w[0]>3 ^ w[1] > 3);
        for (i = 0; i < 5; i++){
            n[0] = w[0] + v[0][(t + s*u[i] + 8) % 8];
            n[1] = w[1] + v[1][(t + s*u[i] + 8) % 8] *(1-2*(abs(w[0]-b[0])==2));
            if (distance (n,b)>1 & distance(n, r)>0 & rsafe(n,r) & n[0]%9!=0 & n[1]%9!=0
                & !(n[0]==r[0] & (w[0]-r[0])*(b[0]-r[0])>0)) i = 5;
        }
        if (i == 6) {
            w[0] = n[0]; w[1] = n[1]; printf("K to %d %d \n", w[0], w[1]); return;
        }
    }

    //if nothing else to do, perform a waiting move with the rook. Black is forced to move his king.
    t = r[1]>3? -1:1;
    for (i = 1; i < 5; i++){
        n[0] = r[0]; n[1] = r[1] + t*i;
        if (rsafe(w, n)){ r[1] = n[1]; i=5; }
    }
    printf("R to %d %d \n", r[0], r[1]);
}

int _tmain(){

    do{
        t=0;
        printf("enter the row and col of the black king ");
        scanf_s("%d%d", &b[0], &b[1]);
        printf("enter the row and col of the white king ");
        scanf_s("%d%d", &w[0], &w[1]);
        printf("enter the row and col of the rook");
        scanf_s("%d%d", &r[0], &r[1]);
        for (i = 0; i < 2; i++) if (b[i]<1 | b[i]>8 | w[i]<1 | w[i]>8 | w[i]<1 | w[i]>8)t=1;
        if (distance(b,w)<2)t+=2;
        if ((b[0] == r[0] & (b[1]-w[1])*(r[1]-w[1])>0) | ((b[1] == r[1]) & (b[0]-w[0])*(r[0]-w[0])>0)) t+=4;
        printf("error code (0 if OK) %d \n",t);
    } while(t);

    nomate=1;
    while (nomate){
        imove();
        strncpy_s(board, empty, 82);
        board[b[0] * 9 + b[1] - 1] = 'B'; board[w[0] * 9 + w[1] - 1] = 'W'; board[r[0] * 9 + r[1] - 1] = 'R'; printf("%s", board);
        if(nomate)umove();
    }
    getchar(); getchar();

}

```

Here's a typical finish (mate can sometimes occur anywhere on the right or left edge of the board.)
> 7 votes

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


# Question
Title: Validate input according to flags and input masks
This challenge challenges you to write a function that will take as its argument an array that specifies the types of input, an optional prompt, and a verification key; inputs and validates the values; and returns them.

Input types:

> b - Boolean values.
> c - Characters.
> i - Integer values, rejects floating point values.
> f - Floating point values, accepts integers.
> n - Strings that only contain the characters a-z and A-Z, suitable for names.
> s - Strings with any character type.
> d - Dates in the form of dd/mm/yyyy, leap years and dates previous to 01/01/1900 can be rejected.

Examples:

> b - Takes input as specified values, validates it, and returns "0" (false) or "1" (true).
> c - Accepts any character.
> i - Accepts any integer or number that, when the decimal is dropped, the resulting number is identical to the original number, such as 3 or 90.0. Rejects all other floating point values, such as 4.2 and 5.009.
> f - Accepts any floating point or integer values. Floating point values include any number with a decimal value between .1 and .9. Numbers with .0 can count as a integer.
> n - Accepts any string that contains only the characters a-z and A-Z. This input will accept "Name," but reject "Name1" and "My name."
> s - Accepts any type of string.
> d - Accepts any valid date of the form dd/mm/yyyy, such as 03/01/2014.

The function will take an array, vector, or other variable length type as an argument. Each element of the array will contain sub-elements of the input type request input type, an optional prompt, and for the input types `s`, `i`, and `f`, an optional validation format. Input type `b` must include a validation format in the form of "True/False". The array must be formatted as {type, prompt, validation}.

If no prompt is given, the function will use "\> " as a prompt.

If a validation format for input type `s` is given, it can contain any character that must be matched exactly and a request for any number of characters matching certain criterion. To request the string to have a specific number alphabetic characters (a-z and A-Z), use the format `%(number of characters)(c)`, as in `%6c`, which requests 6 characters. To request that the input be a certain number of single-digit integers, use `%(number of digits)(i)`, as in `%6i`, which requests six digits. Any other character given must be matched directly, where `i` equals `i` and `-` equals `-`". Use `%%` to signify `%` because `%` alone is used to represent a command, as above. These rules can be combined, where `i%6c-%%%2ixx` represents an input matching `i` \+ 6 characters + `-%` \+ 2 digits + `xx`, where `ifizlwi-%62xx` is a valid example.

Input validation formats for types `i` and `f` must be the in the form `lowest/highest`, where `lowest` is the lowest acceptable number and `highest` is the highest acceptable number. Example: `6/50` would require a number between 6 and 50 (inclusive) to be input.

The function will return an array of strings that can be parsed by your program.

Return formatting:

> b - Returns "0" (false) or "1" (true).
> c, i, f, n, s, l, and d - returns input formatted as string.

Example call:

```
String s[][] = {{"n", "First name: "}
           {"n", "Last name: "}
           {"i", "Age: "}
           {"d", "Date (dd/mm/yyyy): "}
           {"s", "ISBN: ", "%1i-%6i-%2i-%1i"}
           {"b", "Check out: ", "Yes/No"}};

String[] response = input(s);

```

The Boolean input will give the options as part of the prompt by displaying the input request as "(True/False)" after the prompt. The above example will display as

> "Check out: (Yes/No)"

The function must continue requesting input until a valid input for each request is given.

No internet resources are allowed.

Any input-functions in any language that input and validate any type must not be used. E.g. if a language contains a function to input and validate an integer besides the traditional input function (`System.in`, `cin>>`, `input()`, etc.), that function must not be used. You must do the validation yourself.

No trolling-style answers allowed. There are plenty of trolling questions for you to have fun with.

Shortest code that correctly inputs each of the specified types wins.

# Answer
# C++, 4011 characters

This is the function:

```
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<string>i(int a,const string s[][3]){vector<string>q;for(int i=0;i<a;i++){string t,r,f;cout<<(s[i][1]!=""?s[i][1]:"> ");if(s[i][0]=="b"){bool b=1;for(int j=0;j<s[i][2].size();j++){if(b&s[i][2][j]==47){b=0;continue;}b?r+=s[i][2][j]:f+=s[i][2][j];if(b&j==s[i][2].size()-1|!b&s[i][2][j]==47){b=1;q.push_back("0");}}if(s[i][2].size()==0||s[i][2][s[i][2].size()-1]==47||s[i][2][0]==47){b=1;q.push_back("0");}if(b)cin.putback('\n');while(!b){cout<<"("<<s[i][2]<<") ";cin>>t;if(t==r|t==f){q.push_back(t==r?"1":"0");break;}cout<<"Please enter "<<r<<" or "<<f<<".\n"<<(s[i][1]==""?"> ":s[i][1]);}}if(s[i][0]=="c"){while(t.size()!=1){cin>>t;if(t.size()>1)cout<<"Please enter a character.\n"<<(s[i][1]==""?"> ":s[i][1]);}q.push_back(t);}if(s[i][0]=="i"){double d;int j,l=0,b=0;bool x=1;if(s[i][2].size()>2){for(int j=0;j<s[i][2].size();j++){int k=s[i][2][j];if((k<47|k>57)&k!=45){b=0;break;}if(k==45){if(j==0||s[i][2][j-1]==47)l++;else{b=0;break;}}if(k==47){if(j==0||s[i][2][j-1]==45||j==s[i][2].size()-1){b=0;break;}else{b++;x=0;continue;}}x?r+=s[i][2][j]:f+=s[i][2][j];}}if(b==1){x=1;l=stoi(r);b=stoi(f);}else x=0;l>b?x=0:"";while(1){cin>>r;for(int k=0;k<r.size();k++){if(!isdigit(r[k])&r[k]!=45){d=.5;break;}else d=stod(r);}j=d;if(!cin|j!=d|(x&&(j<l|j>b))){cin.clear();getline(cin,t);cout<<"Please enter an integer";if(!x)cout<<".\n";else cout<<" in the range of "<<l<<" and "<<b<<endl<<(s[i][1]==""?"> ":s[i][1]);}else break;}q.push_back(to_string(j));}if(s[i][0]=="f"){double d,l=0,b=0;bool x=1;if(s[i][2].size()>2){for(int j=0;j<s[i][2].size();j++){int k=s[i][2][j];if(k<45|k>57){b=0;break;}if(k==45){if(j==0||s[i][2][j-1]==47)l++;else{b=0;break;}}if(k==47){if(j==0|s[i][2][j-1]==45|j==s[i][2].size()-1){b=0;break;}else{b++;x=0;continue;}}if(x)r+=s[i][2][j];else f+=s[i][2][j];}}if(b==1){x=1;l=stod(r);b=stod(f);}else x=0;l>b?x=0:"";while(1){cin>>r;for(int k=0;k<r.size();k++){if(r[k]<45|r[k]>57|r[k]==47){cin.putback('k');cin>>d;break;}else d=stod(r);}if(!cin||(x&&(d<l|d>b))){cin.clear();getline(cin,t);cout<<"Please enter a floating point number";if(!x)cout<<".\n";else cout<<" in the range of "<<l<<" and "<<b<<endl<<(s[i][1]==""?"> ":s[i][1]);}else break;}q.push_back(to_string(d));}if(s[i][0]=="n"){bool b=1;while(b){cin>>t;for(int j=0;j<t.size();j++){if(!isalpha(t[j])){cout<<"Please enter a string with only letters.\n"<<(s[i][1]==""?"> ":s[i][1]);break;}if(j==t.size()-1)b=0;}}q.push_back(t);}if(s[i][0]=="s"){for(int j=0;j<s[i][2].size();j++){if(s[i][2][j]==37){if(s[i][2][j+1]>47&s[i][2][j+1]<58){int n=s[i][2][j+1]-48;if(s[i][2][j+2]!=99&s[i][2][j+2]!=105){r="";break;}for(int k=0;k<n;k++){r+='%';r+=s[i][2][j+2];}j+=2;}else if(s[i][2][j+1]==37){r+="%%";j+=1;}else{r="";break;}}else r+=s[i][2][j];}while(1){getline(cin,t);if(r.size()!=0){int j=0,k=0;for(;j<r.size();j++){if(r[j]==37){j++;if(r[j]==105){if(t[k]<48|t[k]>57){j=-1;break;}else{k++;continue;}}if(r[j]==99){if(!(t[k]>64&t[k]<91|t[k]>96&t[k]<123)){j=-1;break;}else{k++;continue;}}}if(r[j]==t[k])k++;else{j=-1;break;}if(j==r.size()-1^k==t.size()){j=-1;break;}}if(j!=-1)break;cout<<"Please enter a string in the format "<<r<<"\nThe % signs indicating special characters.\nIf the symbol after the % sign is %, enter %;\nif it is i, enter any digit between 0 and 9 (inclusive);\notherwise, enter any alphabetical charater a-z or A-Z.\n"<<(s[i][1]==""?"> ":s[i][1]);}else break;}q.push_back(t);}if(s[i][0]=="d"){bool x=1;while(1){string d,m,y;int a,b,c;cin>>t;if(t.size()==10&&t[2]==47&t[5]==47){for(int j=0;j<10;j++)if(t[j]<47|t[j]>57){x=0;break;}if(x){d+=t[0];d+=t[1];a=stoi(d);m+=t[3];m+=t[4];b=stoi(m);y+=t[6];y+=t[7];y+=t[8];y+=t[9];c=stoi(y);if(c>1900&a>0){if((b==1|b==3|b==5|b==7|b==8|b==10|b==12)&a<32)break;if((b==4|b==6|b==9|b==11)&a<31)break;if(b==2&((c%4==0&c%100!=0&a<30)|(c%400==0&a<30)|a<29))break;}}}cout<<"Please enter a date after 01/01/1900 in the form dd/mm/yyyy.\n"<<(s[i][1]==""?"> ":s[i][1]);}q.push_back(t);}if(s[i][0]!="s")getline(cin,t);}return q;}

```

Run it with this as `main()`:

```
int main() try{

    const int args = 10;
    string s[args][3];

    s[0][0]="b",s[0][1]="",s[0][2]="yes/no";
    s[1][0]="c",s[1][1]="Enter a character: ";
    s[2][0]="i";
    s[3][0]="i",s[3][1]="",s[3][2]="4/6";
    s[4][0]="f";
    s[5][0]="f",s[5][1]="",s[5][2]="-2.4/6.3";
    s[6][0]="n",s[6][1]="";
    s[7][0]="s",s[7][1]="",s[7][2]="rt%%%1c%2id";
    s[8][0]="s",s[8][1]="";
    s[9][0]="d",s[9][1]="Enter a date: ";

    vector<string>v=i(args,s);

    for(int i=0;i<args;i++)cout<<v[i]<<endl;
}
catch(exception&e){cerr<<"Error: "<<e.what()<<endl;}
catch(...){cerr<<"Unknown error.\n";}

```
> 2 votes

---
Tags: code-golf
---


title: These are my lucky dice

text:
# Question
Title: These are my lucky dice
Implement a program or function which simulates common dice for role playing games. It should handle at least the d6 and d20, the two most common dice.

***However, it should work as stereotypical gamers expect them to work, and not as real dice work.***

It is an in-joke between gamers, that one can have a specially lucky die for a very very important roll, by previously throwing a lot of dice, selecting those which resulted in a "1", then throwing them again, until you get a few which rolled a "1" multiple times. You then carefully preserve them, because they rolled a 1 multiple times in sequence, so the probability to roll a 1 next time should be extremely low.

Of course, this is not how dice work in real life, because the rolls are statistically independent.

Your simulated dice have to take previous rolls into account, and work similarly to how the gambler in the gambler's fallacy expects it to work. For example, if a lot of low numbers were rolled, the probability of rolling a higher number should be increased.

However, as this is cheating, **you have to hide it well**. This means, a casual glance upon the program should not reveal that you cheated. This means, explicitly saving the previous results and reading them on every throw would be too suspicious. You have to hide this "property" of your dice, and bonus points if you make it plausible deniable and disguise it as an honest mistake. (for example, you make your own RNG with an "unintentional" flaw)

Voters, please take into account how well hidden this "flaw" is.

The programs should be clear, and not obfuscated. It's too easy to hide evil code in an obfuscated program.

# Answer
## Java

```
public class GamerDie {
    private final java.util.Random rnd;
    private final int sides;

    public GamerDie(int sides) {
        this.sides = sides;
        this.rnd = new java.util.Random();
    }

    public int throw() {
        return rnd.nextInt(sides) + 1;
    }
}

```

It's so simple that it's obviously not hiding anything: but `java.util.Random` is a straightforward linear congruential generator, and it uses a discard technique to ensure uniformity, so it guarantees that in any run of the largest multiple of `size` smaller than 2^48 samples it will distribute the numbers evenly, satisfying the requirement.
> 3 votes

# Answer
# Ruby

Currently only supports d6, will add d20 support later on...

Lo and behold - those dices are nasty!

```
# first idea was to create 6 super cool dices just by copy&paste
# -> each dice holds its number at the beginning of the array
# -> we don't need all of them now, so we comment them out
dice0 = %w[[[[[[[[[ 0 . : :. :: ::. ::: ]]]]]]]]
#dice1 = %w[[[[[[[ 1 : . :. ::. :: ::: ]]]]]]]
#dice2 = %w[[[[[[ 2 . : :. :: ::. ::: ]]]]]]
#dice3 = %w[[[[[[ 3 : . :. ::. :: ::: ]]]]]]]
#dice4 = %w[[[[[[[ 4 . : :. :: ::: ::. ]]]]]]]
#dice5 = %w[[[[[[[[ 5 . : :. :: ::. ::: ]]]]]]]]]

# and hey, those dices are almost ascii art ;)

# well, let's just create a standard dice
# -> get rid of the number at the beginning
# -> then sort (maybe we need that later due to the
#    currently unused dices being unsorted)
dice = dice0.select!{|e| /[:.]+/ === e}.sort

def roll(d)
  # rolling is easy
  # -> use size instead of hardcoded number,
  #   maybe we'll have other dices later
  d.slice!(rand(d.size - 1))
end

# and here you have 8 very underhanded dices!
dices = [dice]*8

# roll like a champion
roll(dices[0])
...

```
> 0 votes

# Answer
# Haskell

Use one random thing to make another random thing: in this case, shuffle cards to generate dice throws.

```
import System.Environment
import System.Random
import Data.Array.IO
import Control.Monad
-- make random dice from random cards
suit c=map (\(a,b)->[a,b])$zip "A23456789TJQK" (repeat c)
deck=concatMap(\s->suit s) "♠♥♦♣"
-- just like casinos, use more decks for extra randomness
decks=concat$take 8$repeat deck
-- shuffle the cards
shuffle :: [a] -> IO [a]
shuffle xs = do
        ar <- newArray n xs
        forM [1..n] $ \i -> do
            j <- randomRIO (i,n)
            vi <- readArray ar i
            vj <- readArray ar j
            writeArray ar j vi
            return vj
  where
    n = length xs
    newArray :: Int -> [a] -> IO (IOArray Int a)
    newArray n xs =  newListArray (1,n) xs
-- convert a card to a die, by counting along the original deck
-- then taking mod (faces). If we don't have enough cards to make
-- a full set of faces, assign the 'extra' cards a value of 0
card2die faces card=
  let index=(head[i|(i,c)<-zip[0..]deck,c==card]) in
  if (index > (length deck-(length deck`mod`faces)))
  then 0
  else (index`mod`faces)+1
main=
  do
    args <- getArgs
    let faces = read (args!!0)
    -- throw away cards we can't map to die faces
    cards<-shuffle$filter (\card->card2die faces card/=0) decks
    mapM_ (\card->putStrLn (card++" -> "++(show (card2die faces card)))) cards

```

Takes one argument, the number of faces on the die. Output is like this:

```
./cards 20|head
2♦ -> 8
7♥ -> 20
J♦ -> 17
6♥ -> 19
9♥ -> 2
8♥ -> 1
5♥ -> 18
4♠ -> 4
Q♥ -> 5
2♣ -> 1

```

... and so on for all cards (discards are not printed). Too obvious?
> 0 votes

---
Tags: popularity-contest, underhanded
---


title: Shortest Pong, AI vs AI

text:
# Question
Title: Shortest Pong, AI vs AI
Your task is to write the shortest possible Pong game without human interaction, so AI plays vs AI. I assume all of you know Pong, just to make sure, this is the target (just as running code):
http://www.youtube.com/watch?v=xeEFMhdnR6c

**The following game rules apply:**

1. No ASCII "graphics".
2. You must actually have code to count the scores, even if the AI never scores.
3. It must be possible to adjust the size of the output window/area in some way to any (reasonable) size. Which means you must include some form of output scaling.
4. No need for a menu or other features of the game, just what's in the video.

**The following play fair rules apply as well:**

* No language specifically designed for code golfing.
* You may only use standard libraries offered by the language of your choice. No external library downloading, no jQuery, no full-sized game-libraries.
Exception: if no library for graphical output is available with the default offering of the language of your choice, you are allowed to use a library that offers basic graphical output similar to what other languages include in their basic library set.
* `import` statements (or however they are called in your language) can be skipped in the character count.
* Doorknob-rule: The paddles may not be bigger than 15% of the game area.

**Bonus points:**

* -50 if you include sound. External sound sources (e.g. wav) do not need to be added to the char count and may be downloaded during execution. If you choose to copy & paste the data into the code, only the actual data is allowed to be skipped for character count.
* Another -150 (for -200 total) if you do not use external sounds but generate it. Generate means: you have some form of sound synthesizing, copy & pasting e.g. wav data does not count.

# Answer
# Pure HTML and CSS, 355 characters

```
<div class=p></div><div style="height:300px"></div><div class=p></div><div id=b></div>0-0<style>.p{width:99px;height:20px;background:#000}*{margin:0}#b{position:absolute;background:#F00;width:20px;height:20px;animation-name:b;animation-duration:3s;animation-iteration-count:infinite;left:40px}@keyframes b{from{top:20px}50%{top:300px}to{top:20px}}</style>

```

You may need an up-to-date or beta browser for the CSS `animation` properties.

Here is a fiddle, with `-webkit-` vendor prefixes added so that it works in latest Chrome.

The ball just bounces back and forth. The AIs are extremely smart and know not to move.

The `0-0` at the bottom is the score, and you can resize the window.
> 10 votes

# Answer
# Scratch, 1605 – 50 = 1555

~~I don't know how to count the score here and~~ it doesn't meet the "resizing the window" rule... I just thought it was fun. Some unrealistic speed though, and one known bug: if the ball hit the bar at an almost vertical angle, it will somehow get trapped.

Edit: updated score as per community consensus.

The bars will only move if the ball is moving towards its direction. I could make it always move, but I think that would be too boring.

Sprite1: the "ball"

Sprite2: the right vertical "bar" (don't know what it's called)

Sprite3: the left vertical "bar": essentially the same as Sprite2, except the first `if` condition, which is changed to `direction of Sprite1 < 0`

Note: you can change the "intelligence" of the AI by changing the glide speed. They will move slower, so higher chance of missing the ball.

Sprite4 and Sprite5 are two white vertical bars placed on either side of the "field". They have no scripts.

Code used for byte counting: (Using snippet to hide code)

```
when green flag clicked
set [score1 v] to [0]
set [score2 v] to [0]
forever
  go to x: (0) y: (0)
  wait (1) secs
  point in direction (pick random (70) to (290))
  repeat until <<touching [Sprite4 v] ?> or <touching [Sprite5 v] ?>>
    move (10) steps
    if <touching color [#000] ?> then
      play sound [pop v]
      point in direction (((360) - (direction)) + (pick random (-5) to (5)))
    end
    if <touching [edge v] ?> then
      if on edge, bounce
      point in direction ((direction) + (pick random (-5) to (5)))
    end
  end
  play sound [216090__richerlandtv__bad-beep-incorrect v]
  if <touching [Sprite4 v] ?> then
    change [score1 v] by (1)
  end
  if <touching [Sprite5 v] ?> then
    change [score2 v] by (1)
  end
end

when green flag clicked
forever
  if <[0] < ([direction v] of [Sprite1 v])> then
    if <([y position v] of [Sprite1 v]) > [140]> then
      glide (.1) secs to x: (x position) y: (140)
    else
      if <([y position v] of [Sprite1 v]) < [-140]> then
        glide (.1) secs to x: (x position) y: (-140)
      else
        glide (.1) secs to x: (x position) y: ([y position v] of [Sprite1 v])
      end
    end
  end
end

when green flag clicked
forever
  if <([direction v] of [Sprite1 v]) < [0]> then
    if <([y position v] of [Sprite1 v]) > [140]> then
      glide (.1) secs to x: (x position) y: (140)
    else
      if <([y position v] of [Sprite1 v]) < [-140]> then
        glide (.1) secs to x: (x position) y: (-140)
      else
        glide (.1) secs to x: (x position) y: ([y position v] of [Sprite1 v])
      end
    end
  end
end
```

Note: Code automatically generated using scratchblocks generator, modified as somehow the generator doesn't correctly handle decimal numbers (treating .1 as 0).

See it run online here.

Old version (the bars move randomly).

A screenshot:
> 5 votes

# Answer
# HTML / JavaScript, 476

```
<body onload="for(p in r=c.getClientRects()[0])top[p[0]]=c[p]=r[p];t=c.getContext('2d');t.T=t.fillText;t.R=t.fillRect;A=B=0;a=b=h/2;H=h/9|0;x=w/2;y=h/2;v=w/550;z=h/250;setInterval('x<w/3&&(a+=a<y?3:-3);x>2*w/3&&(b+=b<y?3:-3);y<0|y>h?z=-z:0;x<8&&y>a&&y<a+H||x>w-8&&y>b&&y<b+H?v=-v:0;x+=v;y+=z;(x<0?++A:x>w?++B:0)&&(x=w/2,y=h/2);with(t)clearRect(0,0,w,h),R(x,y,5,5),R(2,a,6,H),R(w-8,b,6,H),T(A,H,9),T(B,w-H,9)',16)"><style>*{margin:0;width:100%;height:100%}</style><canvas id=c>

```

**Un-golfed:**

```
<body>
<style>*{margin:0;width:100%;height:100%;}</style>
<canvas id="c"></canvas>
<script>
// Resize canvas
for(p in r=c.getClientRects()[0])top[p[0]]=c[p]=r[p];

// Get drawing context
t = c.getContext('2d');

// Shorter names
t.T=t.fillText;t.R=t.fillRect;

// Scores
A=B=0;

// Paddles position
a=b=h/2;
H=h/9|0;

// Ball position
x=w/2;
y=h/2;

// Ball velocity
dx=w/550;
dy=h/250;

setInterval(function() {
  // Process AI
  x<w/3&&(a+=a<y?3:-3);
  x>2*w/3&&(b+=b<y?3:-3);

  // Wall collisions
  y<0|y>h?dy=-dy:0;

  // Paddle collisions
  x<8&&y>a&&y<a+H||x>w-8&&y>b&&y<b+H?dx=-dx:0;

  // Update ball position
  x+=dx;
  y+=dy;

  // Update score if the ball is behind the paddle.
  // If so, reset the ball position
  (x<0?++A:x>w?++B:0)&&(x=w/2,y=h/2);

  with(t){
    // Clear screen
    clearRect(0,0,w,h);

    // Draw ball
    R(x,y,5,5);

    // Draw paddles
    R(2,a,6,H);
    R(w-8,b,6,H);

    // Draw scores
    T(A,H,9);
    T(B,w-H,9);
  }
},16);
</script>
</body>

```
> 2 votes

---
Tags: code-golf
---