# Question
Title: Find next multiple of 32 that follows given number without using *, / and loops
Imagine simple math problem. You have a number, say it's 1000. And you want to find the next multiple of 32 that follows 1000. You automatically make some simple calculations and get the result. Typical algorithm looks like this:

```
int number = 1000, result;
result = (1 + (number/32)) * 32; // integer division

```

It's kind of easy and obvious, right? And now the challenge. **Make this calculation without using `*`, `/` and loops.**

Rules:

* Don't use `*`, `/` and loops.
* Assume that input number is already stored in variable `n`, store result in the variable `r` (already declared).
* The shortest code wins.

*Sample input:* (already stored in `n`)

```
1000

```

*Sample output:* (value of `r`)

```
1024

```

---

*Sample input:*

```
31

```

*Sample output:*

```
32

```

---

*Sample input:*

```
32

```

*Sample output:*

```
64

```

It is assumed that `n` is a positive number.

# Answer
> 5 votes
# JavaScript (26 13 chars)

`alert((+prompt()>>5)+1<<5)`

Re-read the problem statement. Here's my amended answer:

`r=(n>>5)+1<<5`

And this seems to be the best javascript answer at 10 chars:

`r=(n|31)+1`

# Answer
> 3 votes
## GolfScript (10 chars)

```
32n+31~&:r

```

Problems this trivial aren't interesting.

# Answer
> 3 votes
# C (11 chars)

```
r=(n|31)+1;

```

# Python (10 chars)

```
r=(n|31)+1

```

Work for negative numbers also

# Answer
> 1 votes
# Mathematica - ~~15~~ 13

```
⌈##⌉&[n+1,32]

```

It's quite simple if `Ceiling` (`⌈...⌉`) isn't forbidden

# Answer
> 1 votes
**EXCEL (14 characters):**

```
=n-MOD(n;32)+32

```

n is declared name for a an input cell. put the formula in a cell declared as 'r'. No use of / and * ...

# Answer
> 1 votes
# Python (11 chars)

```
r=n+32-n%32

```

Using modulo

Alternative (10 chars), using bitwise OR like everbody else:

```
r=(n|31)+1

```

# Answer
> 1 votes
## R, 12

```
r=n+32-n%%32

```

This uses modulo `%%`, subtraction `-`, and addition `+`.

# Answer
> 1 votes
## Julia, 8

```
r=n|31+1

```

(This is based on the C solution.)

Some parentheses can be saved in Julia due to the order in which the functions are called:

```
:(r=n|31+1) # : returns the ATK
:(r = +(|(n,31),1))

```

# Answer
> 1 votes
# R (~~10~~ 16)

~~r=-n%%32+n~~
```
r=-(n=n+1)%%32+n

```

# R (recursive, long)

```
r<-(function (n) if(n%%32) Recall(n+1) else n)(n+1)

```

# Python (~~9~~ 14)

~~r=-n%32+n~~
```
n+=1
r=-n%32+n

```

# Answer
> 1 votes
# PowerShell: 14

```
$r=$n-$n%32+32

```

# Answer
> 0 votes
C (16 characters):

```
r=((n>>5)+1)<<5;

```

# Answer
> 0 votes
## Kona (21)

```
 r:{_(1+(x%32))%(%32)}

```

No `*`, `/`, nor a loop in the above.

# Answer
> 0 votes
# J - 11 characters

```
r=:2^>.2^.n

```

# Answer
> 0 votes
### C - 19 characters

not the shortest, but a different method

```
j=i%32?i+32-i%32:i;

```

# Answer
> 0 votes
## J (10)

This returns n if n is a multiple of 32. So it doesn't satisfy everything I think you want.

```
r=:n-_32|n

```

If we need to be stringent on that rule, the following works.

## (14)

```
r=:>:n-_32|>:n

```

# Answer
> 0 votes
# Perl 6 (9 bytes)

```
r=n+|31+1

```

`r` and `n` can be declared as sigilless variables (`my \variable`). In Perl 6, bitwise operators (like `+|`)'s precedence is better, so no parens are needed.

# Answer
> 0 votes
### R, 40

Just for kicks, a solution that doesn't use the modulo operator either:

```
r=tail(which(!cbind(1:n,31:0)[,2]),1)+32

```

`cbind(1:n,31:0)` creates an array with one column going from 1 to n and another from 31 to 0. That column is recycled to fit the size of the first one. `which(!cbind(1:n,31:0)[,2])` returns the indices of the elements for which the second column is 0 (`0` being FALSE, `!0` is TRUE), i.e. the multiples of 32. Finally we take the last one using `tail` and add 32.

Solution at 34 characters with `rep`:

```
r=tail(which(!rep(31:0,l=n)),1)+32

```

# Answer
> 0 votes
# Perl5 14

```
$r=($n+32)&~31

```

In Perl5 variables needs sigilia. $n gets added 32 and we strip the last 5 bits by anding by the inverse of 31.

# Answer
> 0 votes
## x86 Machine Code - 6 bytes

Assuming that the register 'ax' is 'n', and 'bx' is 'r' then

```
83C81F 40 89C3

```

Assembled from:

```
or ax, 0x1F
inc ax
mov bx, ax

```

# Answer
> 0 votes
## Game Maker Language, 8

```
r=n|31+1

```

Yes, `|` is evaluated before `+` (see here)

# Answer
> 0 votes
### GolfScript, 7 characters

```
31n|):r

```

Takes input from variable `n` and puts the result into `r`. Note that for testing it is advisable to use another variable name since `n` is also part of the `p` and `puts` built-ins.

# Answer
> -1 votes
## TI-BASIC, 12

```
32(1+N/32)→R

```

# Answer
> -2 votes
**C 45**

```
int a=32,b,c;b=31;c=b%a;c=a-c;b=b+c;return c;

```

---
Tags: code-golf
---


title: Output and sourcecode lineup

text:
# Question
Title: Output and sourcecode lineup
**General constraints**:

* Your program should not take any input.
* Your program should output words, 1 word/line.
* Only capital letters (A-Z) in the output.
* A word must be atleast 2 letters in length.
* A word can never be a palindrome. That is forbidden.

Rules for word-manipulations, **one or more** of these operations in **any individual order** for each new line:

1. Change one or more letter(-s) in the word 1 char distance (example: A-\>B, F-\>E) from the previous word. 'A' can **not** be 'Z' and 'Z' can **not** be 'A'.
2. Insert the letter "A" at any position.
3. Remove any letter at any position.

**Output validation**:

*Your program must output the following words: **OUTPUT, YOUR, SOURCECODE, TODAY** atleast (but not limited to) once each, in any order.*

**Sourcecode validation**:

The **first** and the **last** letter of all output words should also be part of your sourcecode in the same order as scopes: first and last letter for the first word has the highest scope, example pseudo-code:

```
<any or no code><first letter, first word>
<any or no code><first letter, second word>
<any or no code><,...              ...,><any or no code>
<last letter, second word><any or no code>
<last letter, first word><any or no code>

```
1. For any word # where the actual word number **is** a fibonacci-number, the first and last letters must be **lower-case** in the sourcecode.
2. For any word # where the actual word number **is not** a fibonacci-number, the first and last letters must be **upper-case** in the sourcecode.

There is no restriction of the actual letters in the sourcecode, they can be inside strings or part of a command or anything, it is only the order that counts.

**Example valid output** (only the words YOUR and TODAY in the example):

```
YOUR
XOUAS
WOAAT
VOBAU
UOCAV
TODAW
TODAX
TODAY

```

**Example valid sourcecode for the above output**:

Since words 1, 2, 3, 5 and 8 in the example output is "fibonacci words", their first and last letter-representation in the sourcecode is lower case, leaving us with this constraint on the sourcecode:

```
yxwVuTTtyXWvUtsr

```

There could be any code around or between the letters in the sourcecode as long as the representation is there somewhere in that order.

This is code-golf, smallest sourcecode size in counted bytes wins. Competition ends: 2014-02-31.

# Answer
## Golfscript, ~~211~~ 210

```
stuVwXYoOOOOoOOOOOOOoOOOOOOOUTTTTYXWVUTSRQPONmLKJIHGFeDCBB
{.2$<@@>{)}%+}:b;
'ROURCeCodeS'{95&}%
'()[]+\+); '7*';"OUSB" "A"+-3b "A"+'+'-3b '13*+'-2b '6*+';"UTOBUU" ;"TOCAV" ;"TODAW" '+'))[]++ '2*+
' '/{~n 1$}%-4<(@

```

Newlines added only for clarity, and can be removed. The last bits of the letter string are the name of the function and inside `'ROURCeCodeS'`.

Test online

Output:

```
SOURCECODE
TOURCECOD
UOURCECO
VOURCEC
WOURCE
XOURC
YOUR
OUSB
OUTCB
OUTDCB
OUTEDC
OUTFED
OUTGFE
OUTHGF
OUTIHG
OUTJIH
OUTKJI
OUTLKJ
OUTMLK
OUTNML
OUTONM
OUTPON
OUTPPO
OUTPQP
OUTPRQ
OUTPSR
OUTPTS
OUTPUT
UTOBUU
TOCAV
TODAW
TODAX
TODAY

```
> 2 votes

# Answer
# Java, 1091 1039 bytes

Probably not very good, but I'll give it a try. (Formatting worse will give less Bytes, but for now, let's leave it)

edit 1: used names for Vars to make comment shorter.

```
public class t {
public static void main(String[] V){
    StringBuilder w = new StringBuilder("SOURCECODE");
    X(w);
    for(int Y=0; Y<6; Y++){
        w.deleteCharAt(4);
        w.setCharAt(0,(char)(w.charAt(0)+1));
        X(w);
    }
    w.deleteCharAt(0);
    for(int o=0;o<2;o++){
        w.setCharAt(2,(char)(w.charAt(2)+1));
        w.append('A');
        w.append('A');
        X(w);}
    for(int O=0;O<20;O++){
        if (O<15) w.setCharAt(3,(char)(w.charAt(3)+1));
        w.setCharAt(4,(char)(w.charAt(4)+1));
        if (O<19) w.setCharAt(5,(char)(w.charAt(5)+1));
        X(w);}
    w.deleteCharAt(6);
    X(w);//o
    for(int O=0;O<6;O++){
        if (O<5) w.setCharAt(0,(char)(w.charAt(0)+1));
        w.setCharAt(1,(char)(w.charAt(1)-1));
        X(w);}
    for(int O=1;O<4;O++){
    w.deleteCharAt(2);//o
    if (O<3) w.insert(4, 'A');
    X(w);}
    for(int O=0;O<5;O++){
        if (O<3) w.setCharAt(2,(char)(w.charAt(2)+1));
        w.setCharAt(4,(char)(w.charAt(4)+1));
        X(w);}
    //OOOOPQRsTTTTTTTTTT
    //yxwVuTTtTTTTtTTAAAAAaAAAAAAAAAAAAaAAREEEEEEE
}
static void X(StringBuilder b){System.out.println(b.toString());}}

```

outputs:

```
SOURCECODE
TOURECODE
UOURCODE
VOURODE
WOURDE
XOURE
YOUR
OUSAA
OUTAAAA
OUTBBBA
OUTCCCA
OUTDDDA
OUTEEEA
OUTFFFA
OUTGGGA
OUTHHHA
OUTIIIA
OUTJJJA
OUTKKKA
OUTLLLA
OUTMMMA
OUTNNNA
OUTOOOA
OUTPPPA
OUTPQQA
OUTPRRA
OUTPSSA
OUTPTTA
OUTPUTA
OUTPUT
PTTPUT
QSTPUT
RRTPUT
SQTPUT
TPTPUT
TOTPUT
TOPUAT
TOUAAT
TOAAT
TOBAU
TOCAV
TODAW
TODAX
TODAY

```
> 2 votes

# Answer
# Mathematica ~~226~~ ~~221~~ 217

A little bit longer than GolfScript:

```
yxwV;
u:O_~T~OO_:=T[Print@FromCharacterCode@Select[O,#>64&]TSRQp;O+Sign[OO-O],u=OO]
"YOUR"
oOOOOOOOOOPQRsSSSEEDcBA(TT=ToCharacterCode)@"XOA@@S"~T~TT@"TODA@Y"~T~TT@"OUTPUT"t;
TT@"PTUQA?=T>@"~T~TT@"SOURCECODE"uVWXYyXWvUtsr;

```

Output:

```
YOUR
XOAS
WOBAT
VOCAU
UODAV
TODAW
TODAX
TODAY
TODAY
SPEBAX
RQFCBW
QRGDCV
PSHEDU
OTIFET
OUJGFT
OUKHGT
OULIHT
OUMJIT
OUNKJT
OUOLKT
OUPMLT
OUQNMT
OURONT
OUSPOT
OUTPPT
OUTPQT
OUTPRT
OUTPST
OUTPTT
OUTPUT
PTUQAT
QSURBSA
RRURCARB
SQURCBQAC
SPURCCAPBD
SOURCDBOCE
SOURCECODE

```

`ClearAll[T]` is necessary after usage.
> 2 votes

# Answer
## Windows Batch File, 557

```
::yxwVuTTtSRQPoOOOOOOOoOOOOOOOOPQRSsSSSS
::EDCBaATTTTTTTTTTTtTTTTTTTtUVXXyXWvUtsr
echo YOUR
echo XOUAS
echo WOAAT
echo VOBAU
echo UOCAV
echo TODAW
echo TODAX
echo TODAY
echo SPEBAX
echo RQFCBX
echo QRGDCV
echo PSHEDU
echo OTIFET
echo OUJGFT
echo OUKHGT
echo OULIHT
echo OUMJIT
echo OUNKJT
echo OUOLKT
echo OUPMLT
echo OUQNMT
echo OURONT
echo OUSPOT
echo OUTPPT
echo OUTPQT
echo OUTPRT
echo OUTPST
echo OUTPTT
echo OUTPUT
echo PTUQAUT
echo QSURBAUT
echo RRURCBAUT
echo SQURCCBTA
echo SPURCDCSBA
echo SOURCECRCB
echo SOURCECQDC
echo SOURCECPDD
echo SOURCECODE

```
> 1 votes

# Answer
## GTB, 403

```
]yxwVuTTtSRQPoOOOOOOOoOOOOOOOOPQRSsSSSS\EDCBaATTTTTTTTTTTtTTTTTTTtUVXXyXWvUtsr[~"YOUR~"XOUAS~"WOAAT~"VOBAU~"UOCAV~"TODAW~"TODAX~"TODAY~"SPEBAX~"RQFCBX~"QRGDCV~"PSHEDU~"OTIFET~"OUJGFT~"OUKHGT~"OULIHT~"OUMJIT~"OUNKJT~"OUOLKT~"OUPMLT~"OUQNMT~"OURONT~"OUSPOT~"OUTPPT~"OUTPQT~"OUTPRT~"OUTPST~"OUTPTT~"OUTPUT~"PTUQAUT~"QSURBAUT~"RRURCBAUT~"SQURCCBTA~"SPURCDCSBA~"SOURCECRCB~"SOURCECQDC~"SOURCECPDD~"SOURCECODE

```
> 1 votes

# Answer
**\[C/C++\] 1239 chars**

Concept solution.

```
main() {
    // yxwVuTTtSRQPoOOOOOOOoOOOOOOOOPQRSsSSSS
    // EDCBaATTTTTTTTTTTtTTTTTTTtUVXXyXWvUtsr

    printf("YOUR\n");
    printf("XOUAS\n");
    printf("WOAAT\n");
    printf("VOBAU\n");
    printf("UOCAV\n");
    printf("TODAW\n");
    printf("TODAX\n");
    printf("TODAY\n");
    printf("SPEBAX\n");
    printf("RQFCBX\n");
    printf("QRGDCV\n");
    printf("PSHEDU\n");
    printf("OTIFET\n");
    printf("OUJGFT\n");
    printf("OUKHGT\n");
    printf("OULIHT\n");
    printf("OUMJIT\n");
    printf("OUNKJT\n");
    printf("OUOLKT\n");
    printf("OUPMLT\n");
    printf("OUQNMT\n");
    printf("OURONT\n");
    printf("OUSPOT\n");
    printf("OUTPPT\n");
    printf("OUTPQT\n");
    printf("OUTPRT\n");
    printf("OUTPST\n");
    printf("OUTPTT\n");
    printf("OUTPUT\n");
    printf("PTUQAUT\n");
    printf("QSURBAUT\n");
    printf("RRURCBAUT\n");
    printf("SQURCCBTA\n");
    printf("SPURCDCSBA\n");
    printf("SOURCECRCB\n");
    printf("SOURCECQDC\n");
    printf("SOURCECPDD\n");
    printf("SOURCECODE\n");
}

```
> 0 votes

# Answer
# PHP: ~~321~~316 bytes

I can't take much credit for this; all I did was compress and base64 encode the word sequence in Timtech's answer.

```
<?php //yxwVuTTtSRQPoOOOOOOOoOOOOOOOOPQRSsSSSSEDCBaATTTTTTTTTTTtTTTTTTTtUVXXyXWvUtsr
echo gzinflate(base64_decode("Nc5JDsAgCEDRPbdStHMLInS4/0UqNd3wvokJPGQCN1mocFEICifFYGCE4QSlFK5v3t98oHKO7SFlwHhDkTHhCVynnAxI5yErkC3j4KzT6Gzz5OzL7Bzr4tC2OrxvTjl2R+hwKpOjzJ3SkU7taMcUWK2EZqkm0UPEBL+qpRVGDe3uVglrbNkWYcb25c+S8E9O6U9K+QU="));?>

```

**Edit:** Moving the comment to the end allows a few characters to be shaved off:

```
<?php echo gzinflate(base64_decode("Nc5JDsAgCEDRPbdStHMLInS4/0UqNd3wvokJPGQCN1mocFEICifFYGCE4QSlFK5v3t98oHKO7SFlwHhDkTHhCVynnAxI5yErkC3j4KzT6Gzz5OzL7Bzr4tC2OrxvTjl2R+hwKpOjzJ3SkU7taMcUWK2EZqkm0UPEBL+qpRVGDe3uVglrbNkWYcb25c+S8E9O6U9K+QU="));//TTtSRQPoOOOOOOOoOOOOOOOOPQRSsSSSSEDCBaATTTTTTTTTTTtTTTTTTTtUVXXyXWvUtsr
?>

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Generate the fewest lottery tickets to play in order to have at least N good numbers
This is a rather complex but very interesting maths subject (known as **"covering problem"**),

And I'd like your help for implementing it.

Imagine a lottery game, where each ticket must choose 5 random numbers in a set of 50 numbers (from 1 to 50).

It's quite easy to know the probability of a winning ticket, or the probability to have 1, 2, 3 or 4 good numbers.

It's also quite easy to "generate" all the tickets that have 1, 2, 3, 4 good numbers.

My question (and code challenge) is related to this, but slightly different:

I want to buy some lottery tickets (the fewest possible), such as **at least** one of my tickets has 3 good numbers.

## Challenge

Your goal is to implement a generic solution (as a program or just a function), like this, in any language:

```
// Input: 3 prameters
min_lottery_tickets(total_numbers_to_choose_from, how_many_numbers_to_choose, how_many_good_numbers_i_want)

```

For the above example, one would just have to call:

```
min_lottery_tickets(50, 5, 3)

```

and the program will generate the smallest set of tickets to play to achieve this goal.

---

Example:

```
 min_lottery_tickets(10, 5, 2)

```

would output 7 tickets, like those:

```
1   2   3   4   5
5   6   7   8   9
10  1   2   6   7
10  3   4   8   9
3   4   6   7   8
1   2   3   8   9
1   4   9   5   10

```

because such tickets are enough to cover any pair of numbers from 1 to 10.

---

## Output

Text, one line per ticket, tabulations or spaces between numbers

---

## who wins

The most efficient program wins (i.e. the program generating the fewest tickets for the above parameters):

```
min_lottery_tickets(50, 5, 3)

```

Thanks!

# Answer
> 1 votes
**I know it's not optimal**, but here is the code in node.js:

```
function min_lottery_tickets(total_numbers_to_choose_from, how_many_numbers_to_choose, how_many_good_numbers_i_want) {
    c(function(result) {
        var other = result[result.length - 1];
        while (result.length < how_many_numbers_to_choose) {
            other++;
            var already = false;
            for (var i = 0; i < result.length; i++) {
                if (other === result[i]) {
                    already = true;
                    break;
                }
            }
            if (!already) {
                result.push(other);
            }
        }
        if (other <= total_numbers_to_choose_from) {
            // Print results
            console.log(result);
        }
    }, total_numbers_to_choose_from, how_many_good_numbers_i_want);
}

function c(next, total_numbers, length, start, results) {
    if (!start) start = 1;
    if (!results) results = [];

    for (var i = start; i <= total_numbers + 1 - length; i++) {
        var resultsNew = results.slice(0);
        resultsNew.push(i);
        if (length > 1) {
            c(next, total_numbers, length - 1, i + 1, resultsNew);
        } else {
            next(resultsNew);
        }
    }
}

```

Some example results:

```
> min_lottery_tickets(5, 3, 2)
[ 1, 2, 3 ]
[ 1, 3, 4 ]
[ 1, 4, 5 ]
[ 2, 3, 4 ]
[ 2, 4, 5 ]
[ 3, 4, 5 ]

```

other:

```
> min_lottery_tickets(10, 5, 2)
[ 1, 2, 3, 4, 5 ]
[ 1, 3, 4, 5, 6 ]
[ 1, 4, 5, 6, 7 ]
[ 1, 5, 6, 7, 8 ]
[ 1, 6, 7, 8, 9 ]
[ 1, 7, 8, 9, 10 ]
[ 2, 3, 4, 5, 6 ]
[ 2, 4, 5, 6, 7 ]
[ 2, 5, 6, 7, 8 ]
[ 2, 6, 7, 8, 9 ]
[ 2, 7, 8, 9, 10 ]
[ 3, 4, 5, 6, 7 ]
[ 3, 5, 6, 7, 8 ]
[ 3, 6, 7, 8, 9 ]
[ 3, 7, 8, 9, 10 ]
[ 4, 5, 6, 7, 8 ]
[ 4, 6, 7, 8, 9 ]
[ 4, 7, 8, 9, 10 ]
[ 5, 6, 7, 8, 9 ]
[ 5, 7, 8, 9, 10 ]
[ 6, 7, 8, 9, 10 ]

```

other:

```
> min_lottery_tickets(10, 5, 3)
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 4, 5, 6 ]
[ 1, 2, 5, 6, 7 ]
[ 1, 2, 6, 7, 8 ]
[ 1, 2, 7, 8, 9 ]
[ 1, 2, 8, 9, 10 ]
[ 1, 3, 4, 5, 6 ]
[ 1, 3, 5, 6, 7 ]
[ 1, 3, 6, 7, 8 ]
[ 1, 3, 7, 8, 9 ]
[ 1, 3, 8, 9, 10 ]
[ 1, 4, 5, 6, 7 ]
[ 1, 4, 6, 7, 8 ]
[ 1, 4, 7, 8, 9 ]
[ 1, 4, 8, 9, 10 ]
[ 1, 5, 6, 7, 8 ]
[ 1, 5, 7, 8, 9 ]
[ 1, 5, 8, 9, 10 ]
[ 1, 6, 7, 8, 9 ]
[ 1, 6, 8, 9, 10 ]
[ 1, 7, 8, 9, 10 ]
[ 2, 3, 4, 5, 6 ]
[ 2, 3, 5, 6, 7 ]
[ 2, 3, 6, 7, 8 ]
[ 2, 3, 7, 8, 9 ]
[ 2, 3, 8, 9, 10 ]
[ 2, 4, 5, 6, 7 ]
[ 2, 4, 6, 7, 8 ]
[ 2, 4, 7, 8, 9 ]
[ 2, 4, 8, 9, 10 ]
[ 2, 5, 6, 7, 8 ]
[ 2, 5, 7, 8, 9 ]
[ 2, 5, 8, 9, 10 ]
[ 2, 6, 7, 8, 9 ]
[ 2, 6, 8, 9, 10 ]
[ 2, 7, 8, 9, 10 ]
[ 3, 4, 5, 6, 7 ]
[ 3, 4, 6, 7, 8 ]
[ 3, 4, 7, 8, 9 ]
[ 3, 4, 8, 9, 10 ]
[ 3, 5, 6, 7, 8 ]
[ 3, 5, 7, 8, 9 ]
[ 3, 5, 8, 9, 10 ]
[ 3, 6, 7, 8, 9 ]
[ 3, 6, 8, 9, 10 ]
[ 3, 7, 8, 9, 10 ]
[ 4, 5, 6, 7, 8 ]
[ 4, 5, 7, 8, 9 ]
[ 4, 5, 8, 9, 10 ]
[ 4, 6, 7, 8, 9 ]
[ 4, 6, 8, 9, 10 ]
[ 4, 7, 8, 9, 10 ]
[ 5, 6, 7, 8, 9 ]
[ 5, 6, 8, 9, 10 ]
[ 5, 7, 8, 9, 10 ]
[ 6, 7, 8, 9, 10 ]

```

---
Tags: code-challenge, combinatorics
---


# Question
Title: Create a programs that counts the 0's in numbers from 0 to a billion
This will be my very first post on stackexchange so bear with me.

Create a program that counts from 0 to 1,000,000,000. Now the trick is to not print all these characters but to only print how many zeroes are in that number. And keep track of the total amount of zeroes you've encountered. For example

```
10

```

Will output;

```
1
2

```

because 10 has 1 zero in it. The two represents how many 0's you've seen in total, in this case the only zero you have encountered previously is 0 itself so you've seen a total of 2 zeroes. The highest score will be given to the shortest code (no surprise here).

*I hope that this is not too easy and that I've posted enough information, given the fact that I'm completely new here I'm not entirely sure about this.*

# Answer
## Python (brute force, 80 chars)

```
def r(n):
    l=[str(i).count('0') for i in xrange(n+1)]
    return l[-1],sum(l)

```

Just to asure, i got the task right, it evaluates to:

```
r(10)
>>> (1, 2)
r(1000000000)
>>> (9, 788888899)

```
> 3 votes

# Answer
# (Oracle) SQL, ~~146~~ 144 chars / 122 chars

```
SELECT*FROM(SELECT l,SUM(REGEXP_COUNT(l,'0'))d FROM(SELECT LEVEL-1l FROM dual CONNECT BY LEVEL<=&a+1)GROUP BY ROLLUP(l))WHERE &a=l OR l IS NULL;

```

Expanded:

```
SELECT *
FROM (
   SELECT
      l,
      SUM(REGEXP_COUNT(l, '0')) d
   FROM (
      SELECT LEVEL - 1 l
      FROM dual
      CONNECT BY LEVEL <= &a + 1
   )
   GROUP BY ROLLUP(l)
)
WHERE &a = l
   OR l IS NULL;

```

Edit: no need to name the column, and `*` doesn't need spaces around it.

---

Okay, so we need it for *all* numbers from 0 to n. Let me put on my thinking cap... Try

```
SELECT c,SUM(c)OVER(ORDER BY l)FROM(SELECT l,REGEXP_COUNT(l,'0')c FROM(SELECT LEVEL-1l FROM dual CONNECT BY LEVEL<=&a+1));

```

Expanded:

```
SELECT
   c,
   SUM(c) OVER(ORDER BY l)
FROM (
   SELECT
      l,
      REGEXP_COUNT(l, '0') c
   FROM (
      SELECT LEVEL - 1 l
      FROM dual
      CONNECT BY LEVEL <= &a + 1
   )
);

```
> 3 votes

# Answer
## C, 90 bytes

```
r;i;j;main(t){for(;i<=10e8;j=++i){for(r=0;j;j/=10)j%10||r++;t+=r;}printf("%d\n%d\n",r,t);}

```

ungolfed:

```
r;i;j;main(t) {
    for (;i<=10e8;j=++i) {
        for (r=0;j;j/=10)
            j%10||r++;
        t+=r;
    }
    printf("%d\n%d\n",r,t);
}

```
> 2 votes

# Answer
## GolfScript ~~34~~ 32

```
0 10.(?,{`{48=},,}%{(.p@+.p\.}do

```

Explanation:

The initial `0` will be the counter for the number of 0s seen thus far. A billion is `10^9`, and `10.(?` generates a billion by taking `10`, copying it, decrementing, and then exponentiating. The `,` then generates an array of all numbers for 0 to a billion - 1. If we need to include one billion, add a `)` before the `,`.

The next block takes a number, converts it to a string by doing `''+`, then filtering down to the characters that equals '0' (ASCII value 48) by doing `{48=},` and then counting the length of the array by doing `,`. Map this block across all the numbers in our array with `%`.

The next block expects two elements on the stack: the total 0s seen, and then the array of 0-counts for each integer not yet printed. Each time the block is executed it pops the first element of the array with `(`, copies and then prints it with `.p`, moves the total counter to the front with `@`, adds the current number, and then rearranges the stack to be in the right order. The `do` will run this block until the array is empty.
> 2 votes

# Answer
## APL (30)

Brute-forced. There is no lazy evaluation, so it generates the whole list from `0` to `1e9` at once. So you need at least a 7GB workspace, or it will just say `WS FULL`.

In case you don't have a huge server to use, the program can be proven to work by lowering `1e9` to a saner amount.

```
(⊃⌽Z),+/¯1↓Z←{'0'+.=⍕⍵}¨0,⍳1e9

```

Explanation:

* `0,⍳1e9`: the list from `0` up to and including `1e9`
* `Z←{'0'+.=⍕⍵}¨`: count the zeroes in each number, and store the list in `Z`.
* `+/¯1↓Z`: the sum of all but the last item in `Z` (the total amount of zeroes encountered)
* `⊃⌽Z`: the last item in `Z` (the amount of zeroes in `1e9`).
> 1 votes

# Answer
**C# - 223 chars:**

```
using System.Linq;class P{static void Main() { G(10); } static void G(int i){System.Console.Write("{0},{1}",i.ToString().Count(l => l == '0'),Enumerable.Range(0, i + 1).SelectMany(b => b.ToString()).Count(l => l == '0'));}}

```

Expanded:

```
using System.Linq;
class P
{
    static void Main() { G(10); }
    static void G(int i)
    {
        System.Console.Write("{0},{1}",
            i.ToString().Count(l => l == '0'),
            Enumerable.Range(0, i + 1).SelectMany(b => b.ToString()).Count(l => l == '0'));
    }
}

```
> 0 votes

# Answer
## Python 81 chars

```
def x(y):
    o=0
    for i in xrange(y+1):
        o+=`i`.count('0')
    print `y`.count('0'),o

```
> 0 votes

# Answer
## J (33)

**Warning: uses an *ungodly* amount of memory**.

```
({:,+/@}:)(+/@('0'=":))"0 i.1e9+1

```

Explanation:

* `i.1e9+1`: generate a list of numbers from `0` up to and including `1e9`.
* `(+/@('0'=":))"0`: for each number (`"0`), convert it to a string (`#:`), and see how many zeroes there are (`'0'=`).
* `({:,+/@}:)`: display the last item in the list (`{:`), followed by the sum of all but the last item in the list (`+/@}:`)
> 0 votes

---
Tags: code-golf, counting
---


# Question
Title: An unintentional-looking but crash-causing bug
There are a range of questions revolving around this concept, but these all seem to just involve causing a crash, resulting in many answers which are very obviously designed to cause a crash. So the challenge I set you is to write some plausible code (although what the codes supposed "intention" is I leave up to you), that crashes either the entire target OS, or just itself, in a way which is not immediately obvious. (I realize that what counts as "immediately obvious" is subjective, but hopefully the challenge is still reasonably clear).

The winner is the answer with the most votes after 5 days.

# Answer
# C, linux. Crashes system if run as root

```
/* Fork child process, wait 5 seconds and kill it */
pid_t pid = fork();
if(pid =! 0) {
    /* Parent */
    sleep(5);
    kill(pid, 11);
}
else {
    /* Child process. Would contain some code */
}

```

By changing `!=` to `=!`, an innocent comparison is turned into an assignment. And given that pid 1 is `init`, and killing `init` causes a kernel panic, this is not code you would want to run as root :)
> 30 votes

# Answer
## C#

Let's just initialize a list of bytes with every byte value from 0 to 255.

```
List<byte> bytes = new List<byte>();
for (byte i = 0; i <= 255; i++)
{
    bytes.Add(i);
}

```

Out of memory? I distinctly recall having more than 256 bytes installed...

**Spoiler:**

> A byte will *always* be less than or equal to 255. Addition wraps around from 255 to 0.
> 27 votes

# Answer
# **C**

```
#include <stdio.h>

int main(void) {
   fputs(stdout, "Hello, world!\n");
   return 0;
}

```

(Compiler warnings will give it away.)
> 7 votes

# Answer
# JavaScript

```
var arr = [3,6,1,54,2,-4,8,10,3,7]
function qs(a) {
    if (a.length < 2) return a
    var part = a.shift()
    var higher = [], lower = []
    for (var i = 0; i < a.length; i ++) {
        var x = a[i] // *** THIS LINE ***
        (x < part ? lower : higher).push(x)
 }
    return qs(lower).concat([part]).concat(qs(higher))
}
alert(qs(arr))

```

Working quicksort, except for the fact that lack of semicolon on the line I marked with a comment causes it to parse wrong and crash.

Adding a semicolon at the end of that line fixes it.
> 3 votes

# Answer
# C++

Inputs names and store them in a vector. Prints names upon entry of flag value. Asks if user thought of more names; if so, inputs names.

```
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void print(const vector<string>& v) {

  for (int i = 0; i <= names.size(); i++)
    cout << v[i] << endl;
}

void input(vector<string>& v) {

  string tmp;

  cout << "Enter a list of names seperated by returns: ";

  do {
    getline(cin, tmp);

    if (tmp != "-1")
      v.push_back(tmp);

  } while (tmp != "-1");

  print(v);
}

int main() {

  vector<string> names;

  string tmp;

  do {
    input(names);

    cout << "Do you have any more names to input (y or n)? ";
    cin >> tmp;

  } while (tmp == "y");

  return 0;
}

```

For non-C++, Java, C users, the error is in `print()`s `for` statement. It should be `for (int i = 0; i < names.size(); i++)`. This is an easy error to make and overlook (until you get the compiler message) because it is only 1 character and because the \>= operator is sometimes required in `for` loops.
> 0 votes

# Answer
## GTB

```
:""→_[_+"+"→_]

```

Crashes the calculator because `[_+` should be `["_"+`, but since it isn't, the calculator runs out of memory, potentially clearing the RAM in the wrong way.
> 0 votes

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


title: Shortest unmatchable regular expression

text:
# Question
Title: Shortest unmatchable regular expression
Your mission is to write the shortest valid regular expression that no string can match, empty string included.

Submissions must have this form ("literal notation"):

```
/pattern/optional-flags

```

Shortest regexp wins. The regexp size is counted in characters. (including slashes and flags)

Please explain how your regexp works (if it's not trivial)

Thanks, and have fun!

# Answer
# **6 chars**

Following on the answers of primo and Peter Taylor, and a hint from `man perlre`:

`/(?!)/`

This perl-compatible regex matches an empty string which is not followed by another empty string.
> 65 votes

# Answer
## 8 chars

```
/(?=a)b/

```

We require a string containing a character which is both `a` and `b`, which is obviously impossible.
> 42 votes

# Answer
## 5 chars

Unlike everybody who abuses `$` and `^`... this actually works in Perl:

```
/V\A/

```

`\A` matches the beginning of the string.
> 34 votes

# Answer
# 6 chars

```
/x\by/

```

Based on Sven Hohenstein's answer.
> 30 votes

# Answer
### 8 characters

```
/\w\b\w/

```

A word boundary (`\b`) surrounded by 'word' characters (`\w` \- one of `[_a-zA-Z0-9]`). It is unmatchable since one of the characters preceding or following a word boundary must be a non-'word' character.

By the way: this is similar to the unmatchable expression

```
/\W\b\W/

```

where `\W` means non-'word' character.
> 27 votes

# Answer
# 9 chars

I'm not sure but `/[^\S\s]/` should be unmatchable since it means not any character, but at least one of them.
> 20 votes

# Answer
## 4 chars

```
/$a/

```

searches a "a" after the end of the string.

or

```
/a^/

```

searches a before the beginning of the string.
> 20 votes

# Answer
**5 characters**

`/$.^/`

`/$^/` will match an empty string, whereas requiring a character in between will not.
> 20 votes

# Answer
# 4 characters

(ECMAScript flavour only)

```
/[]/

```

In other flavours this is not a valid character class (the `]` would be considered a character *in* the class, so the expression isn't valid, because the class is never closed), but the ECMAScript standard accepts empty character classes. Since it is a class it *has* to match a character (so empty strings don't match), but since not a single character is included no actual character will match either.
> 19 votes

# Answer
# 6 characters

```
/\b\B/

```

This matches a word boundary (`\b`) that isn't a word boundary (`\B`), which is obviously impossible.
> 19 votes

# Answer
### 6 chars

```
/b++b/

```

Possessive quantifier looks for as many b's as possible, then 1 more. 6 chars but points for symmetry?
> 17 votes

# Answer
## 6 characters

```
/(\1)/

```

Not a winner, but I thought it was fun. grep and Python both barf on this one, but Perl seems okay with it.

Seems to be *very* implementation-dependent (which is hardly surprising, given its weirdness). Bob reports below that it matches *anything* in JavaScript's regex engine.
> 9 votes

# Answer
Maybe a bit of cheating, but…

```
\0

```

… is unmatchable in POSIX regex in virtually all, if not all, implementations. BASIC RE and EXTENDED RE, even.

And POSIX RE does not need those pesky slashes and flags PCRE has.
> 9 votes

# Answer
## 6 bytes

```
/(*F)/

```

An abbreviation for `(*FAIL)`, supported by perl-compatable regex engines. Thanks to @HamZa for pointing this out.

## 9 bytes

```
/(*FAIL)/

```

Should work with any regex engine that supports verbs at all. I'm not convinced this really needs to be golfed any further.
> 5 votes

# Answer
# 4 char:

```
/.^/

```

Works with GNU grep 2.5.1 and egrep.
> 5 votes

# Answer
# Perl 6 (5 characters)

```
/<!>/

```

Sorta rule abuse (because Perl 6 regexes are different, and incompatible with stardard regexes by design), but I don't care. `<!>` rule informs Perl 6 that the regex doesn't match.
> 5 votes

# Answer
# **5 chars**

```
/^.^/

```

Matches string that begin with any single character before string begin.
> 4 votes

# Answer
### 4 chars with slashes 2 without

In the TXR language's regex engine, an empty character class `[]` matches no character, and therefore no string. It behaves this way because the character class requires a character match, and when it is empty it specifies that no character can satisfy it.

Another way is to invert the "set of all strings including empty" regex `/.*/` using the complement operator: `/~.*/`. The complement of that set contains no strings at all, and so cannot match anything.

This is all documented in the man page:

```
   nomatch
          The  nomatch  regular  expression  represents  the empty set: it
          matches no strings at all, not even the empty string.  There  is
          no  dedicated  syntax  to  directly express nomatch in the regex
          language.  However, the empty character class []  is  equivalent
          to nomatch, and may be considered to be a notation for it. Other
          representations of nomatch are possible: for instance, the regex
          ~.* which is the complement of the regex that denotes the set of
          all possible strings, and thus denotes the empty set. A  nomatch
          has  uses;  for instance, it can be used to temporarily "comment
          out" regular expressions. The regex ([]abc|xyz) is equivalent to
          (xyz), since the []abc branch cannot match anything. Using [] to
          "block" a subexpression allows you to leave it  in  place,  then
          enable it later by removing the "block".

```

The slashes are not part of the regex syntax per se; they are just punctuation which delimits regexes in the S-expression notation. Witness:

```
# match line of input with x variable, and then parse that as a regex
#
$ txr -c '@x
@(do (print (regex-parse x)) (put-char #\newline))' -
ab.*c                               <- input from tty: no slashes.
(compound #\a #\b (0+ wild) #\c)    <- output: AST of regex

```
> 3 votes

# Answer
# 4 chars

```
/$./

```

Needs any character after the string ends
> 2 votes

# Answer
This is a 5 char regex.

```
/[]+/

```

It matches an empty group 1 or more times.

EDIT:

Removed my answer for other flavours:

```
/.{-1}/

```

Anything that is not a number inside {} will match the text.

This one will match ".{-1}"
> 1 votes

# Answer
**6 chars**

**(or 4, depending on how you look at it)**

```
/{,0}/

```
> 1 votes

# Answer
### 5 characters

Hope this doesnt sound stupid: `/[]+/`
> 0 votes

# Answer
```
/$^/

```

A thing that ends before it has begun...
> -3 votes

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


# Question
Title: Compute every combination of operations written in a .TXT file
Your task is to create a program that computes every combination of the operations written in a .TXT file.

**Example TXT File:**

```
1
+
2
/
3

```

**Example Output:**

```
1+2/3=1
1+3/2=2
2+1/3=1
2+3/1=5
3+2/1=5
3+1/2=2
1/2+3= //See bonuses. If your program does not feature float, leave blank result.
1/3+2= //See above.
2/1+3=5
2/3+1= //See above.
3/2+1= //See above.
3/1+2=5

```

**Specs**:

* Every line of the .TXT file must contain a number **or** an operation;
* The minimum length for the .TXT file is 5 lines;
* The operations must be computed from left to right. E.g. `4+4/2` results in `4`;
* Your program should feature `+`, `-`, `*` and `/` operations;
* Your program should work with any valid input of any valid length.

**Scoring:**

Code length is your starting score, but not the only parameter. Here's a short list of bonuses you can achieve to lower your score. The user with the lowest score wins.

* Implement `^`: **-20**;
* Implement `log` (in base *e*): **-30**;
* Implement `logn` (where *n* is any positive base): **-50** (only **-20** if you achieved the `log` bonus);
* Implement `e` (and the number in the line below is the exponent of 10. So `1e4`=`10000`): **-20**;
* Can handle negative values: **-10**;
* Can handle float values: **-20**;
* There are no digits (`0123456789`) in the code: **-10**;
* There is no call to `eval` or equivalent: **-20**;
* All of the above: **-100**.

For a total of **-250** bonus points.

Good luck!

# Answer
> 4 votes
# Mathematica (-4 = 246 - 250)

*Update:* operation `e` instead of the number representation with `e`.

*Update2:* reading from the file.

```
i = "1.txt";

w@"log"=r=Real;
e_~p~c_:=(g[x_r,w@c=c]~g~y_r:=#;p)&@e
y~Log~x~p[x+y,"+"][x-y,"-"][x/y,"/"][x*y,"*"][x*10^y,"e"][x^y,"^"]~"logn";
x_r~g~r:=Log@x
w@y_:=N@ToExpression@y
g[,x_]:=x
f@x_r:=s~Print~x
f@Fold[g,s=#<>"=";,w/@#]&/@Permutations@ReadList[i,String];

```

File:

```
1
+
2
/
3

```

Output:

```
1+2/3=1.
1+3/2=2.
1/2+3=3.5
1/3+2=2.33333
2+1/3=1.
2+3/1=5.
2/1+3=5.
2/3+1=1.66667
3+1/2=2.
3+2/1=5.
3/1+2=5.
3/2+1=2.5

```

File:

```
-1
^
2
e
3
logn
4
log

```

Output:

```
-1e2^4logn3log=2.81943
-1e2^4loglogn3=2.65196
-1e3^2logn4log=2.29916
-1e3^2loglogn4=1.89411
-1e3^4logn2log=3.68545
-1e3^4loglogn2=4.78822
-1e4^2logn3log=2.81943
-1e4^2loglogn3=2.65196
2^-1e3logn4log=1.50027
2^-1e3loglogn4=1.31783
2^-1e4logn3log=2.04804
2^-1e4loglogn3=1.94981
2^3logn4e-1log=-1.89712
2^3logn4loge-1=0.0405465
2^3loge-1logn4=-1.13287
2^3loglogn4e-1=0.0528098
2^4e-1logn3log=-0.849063
2^4e-1loglogn3=-0.687244
2^4logn3e-1log=-1.37685
2^4logn3loge-1=0.0925734
2^4loge-1logn3=-1.16766
2^4loglogn3e-1=0.0928245
2e-1logn3^4log=1.52735
2e-1log^4logn3=1.73268
2e3logn4^-1log=-1.70163
2e3logn4log^-1=0.587671
2e3log^-1logn4=-1.46309
2e3loglogn4^-1=0.683487
2e4logn3^-1log=-2.19884
2e4logn3log^-1=0.454785
2e4log^-1logn3=-2.08708
2e4loglogn3^-1=0.479139
2logn3^-1e4log=9.6709
2logn3^-1loge4=4605.61
2logn3^4e-1log=-4.14483
2logn3^4loge-1=-0.184224
2logn3e-1^4log=-11.0526
2logn3e-1log^4=58.2928
2logn3e4^-1log=-8.74978
2logn3e4log^-1=0.114289
2logn3log^-1e4=-21712.7
2logn3log^4e-1=0.00449933
2logn3loge-1^4=4.49933*10^-6
2logn3loge4^-1=-0.000217127
2logn4^-1e3log=7.6009
2logn4^-1loge3=693.147
2logn4^3e-1log=-4.38203
2logn4^3loge-1=-0.207944
2logn4e-1^3log=-8.9872
2logn4e-1log^3=-26.8849
2logn4e3^-1log=-6.21461
2logn4e3log^-1=0.160911
2logn4log^-1e3=-1442.7
2logn4log^3e-1=-0.0333025
2logn4loge-1^3=-0.000333025
2logn4loge3^-1=-0.0014427
2log^-1e3logn4=5.24728
2log^-1e4logn3=8.71723
2log^-1logn3e4=3336.14
2log^-1logn4e3=264.383
2log^3e-1logn4=-2.45411
2log^3logn4e-1=-0.079315
2log^4e-1logn3=-3.43036
2log^4logn3e-1=-0.133446
2loge-1^3logn4=-5.77604
2loge-1^4logn3=-9.71807
2loge-1logn3^4=34.8402
2loge-1logn4^3=-7.13719
2loge3^-1logn4=-4.71851
2loge3logn4^-1=0.211931
2loge4^-1logn3=-8.05
2loge4logn3^-1=0.124224
2loglogn3^-1e4=-29974.7
2loglogn3^4e-1=0.00123874
2loglogn3e-1^4=1.23874*10^-6
2loglogn3e4^-1=-0.000299747
2loglogn4^-1e3=-3782.39
2loglogn4^3e-1=-0.001848
2loglogn4e-1^3=-0.00001848
2loglogn4e3^-1=-0.00378239
3^-1e2logn4log=0.928001
3^-1e2loglogn4=0.905028
3^-1e4logn2log=2.45982
3^-1e4loglogn2=3.02001
3^2logn4e-1log=-1.84202
3^2logn4loge-1=0.0460561
3^2loge-1logn4=-1.09312
3^2loglogn4e-1=0.0567841
3^4e-1logn2log=1.10457
3^4e-1loglogn2=1.06479
3^4logn2e-1log=-0.45573
3^4logn2loge-1=0.184686
3^4loge-1logn2=-1.18625
3^4loglogn2e-1=0.213568
3e-1logn2^4log=2.20856
3e-1logn4^2log=-0.282015
3e-1log^2logn4=0.267803
3e-1log^4logn2=1.07121
3e2logn4^-1log=-1.4145
3e2logn4log^-1=0.706966
3e2log^-1logn4=-1.25596
3e2loglogn4^-1=0.796204
3e4logn2^-1log=-2.69953
3e4logn2log^-1=0.370435
3e4log^-1logn2=-3.36583
3e4loglogn2^-1=0.297104
3logn2^-1e4log=8.74978
3logn2^-1loge4=-4605.61
3logn2^4e-1log=-0.460342
3logn2^4loge-1=0.184224
3logn2e-1^4log=-7.3681
3logn2e-1log^4=11.5128
3logn2e4^-1log=-9.6709
3logn2e4log^-1=0.103403
3logn2log^-1e4=21712.7
3logn2log^4e-1=0.00449933
3logn2loge-1^4=4.49933*10^-6
3logn2loge4^-1=0.000217127
3logn4^-1e2log=4.83776
3logn4^-1loge2=23.2586
3logn4^2e-1log=-2.76776
3logn4^2loge-1=-0.0465173
3logn4e-1^2log=-5.07034
3logn4e-1log^2=6.42709
3logn4e2^-1log=-4.37258
3logn4e2log^-1=0.228698
3logn4log^-1e2=-429.948
3logn4log^2e-1=0.00540964
3logn4loge-1^2=0.000540964
3logn4loge2^-1=-0.0429948
3log^-1e2logn4=3.25409
3log^-1e4logn2=13.152
3log^-1logn2e4=-1356.82
3log^-1logn4e2=-6.78412
3log^2e-1logn4=-1.52528
3log^2logn4e-1=0.0135682
3log^4e-1logn2=-2.7792
3log^4logn2e-1=0.0542729
3loge-1^2logn4=-3.18625
3loge-1^4logn2=-12.745
3loge-1logn2^4=103.066
3loge-1logn4^2=2.53804
3loge2^-1logn4=-3.38977
3loge2logn4^-1=0.295005
3loge4^-1logn2=-13.4234
3loge4logn2^-1=0.0744968
3loglogn2^-1e4=73701.6
3loglogn2^4e-1=0.0000338917
3loglogn2e-1^4=3.38917*10^-8
3loglogn2e4^-1=0.000737016
3loglogn4^-1e2=1474.03
3loglogn4^2e-1=0.000460242
3loglogn4e-1^2=0.0000460242
3loglogn4e2^-1=0.147403
4^-1e2logn3log=1.07498
4^-1e2loglogn3=1.0641
4^-1e3logn2log=2.07516
4^-1e3loglogn2=2.46505
4^2e-1logn3log=-0.849063
4^2e-1loglogn3=-0.687244
4^2logn3e-1log=-1.37685
4^2logn3loge-1=0.0925734
4^2loge-1logn3=-1.16766
4^2loglogn3e-1=0.0928245
4^3e-1logn2log=0.985097
4^3e-1loglogn2=0.892428
4^3logn2e-1log=-0.510826
4^3logn2loge-1=0.179176
4^3loge-1logn2=-1.26573
4^3loglogn2e-1=0.20562
4e-1logn3^2log=-0.362939
4e-1log^2logn3=-0.159149
4e2logn3^-1log=-1.69629
4e2logn3log^-1=0.589523
4e2log^-1logn3=-1.62963
4e2loglogn3^-1=0.613635
4e3logn2^-1log=-2.48205
4e3logn2log^-1=0.402893
4e3log^-1logn2=-3.05208
4e3loglogn2^-1=0.327646
4logn2^-1e3log=6.21461
4logn2^-1loge3=-693.147
4logn2^3e-1log=-0.223144
4logn2^3loge-1=0.207944
4logn2e-1^3log=-4.82831
4logn2e-1log^3=-4.16891
4logn2e3^-1log=-7.6009
4logn2e3log^-1=0.131563
4logn2log^-1e3=1442.7
4logn2log^3e-1=0.0333025
4logn2loge-1^3=0.000333025
4logn2loge3^-1=0.0014427
4logn3^-1e2log=4.37258
4logn3^-1loge2=-23.2586
4logn3^2e-1log=-1.83741
4logn3^2loge-1=0.0465173
4logn3e-1^2log=-4.14
4logn3e-1log^2=4.28489
4logn3e2^-1log=-4.83776
4logn3e2log^-1=0.206707
4logn3log^-1e2=429.948
4logn3log^2e-1=0.00540964
4logn3loge-1^2=0.000540964
4logn3loge2^-1=0.0429948
4log^-1e2logn3=3.89449
4log^-1e3logn2=9.49455
4log^-1logn2e3=-471.234
4log^-1logn3e2=-29.7315
4log^2e-1logn3=-1.50127
4log^2logn3e-1=0.0594631
4log^3e-1logn2=-1.90823
4log^3logn2e-1=0.14137
4loge-1^2logn3=-3.59718
4loge-1^3logn2=-8.55208
4loge-1logn2^3=-23.1661
4loge-1logn3^2=3.23492
4loge2^-1logn3=-4.48912
4loge2logn3^-1=0.222761
4loge3^-1logn2=-10.437
4loge3logn2^-1=0.0958128
4loglogn2^-1e3=2122.09
4loglogn2^3e-1=0.0104643
4loglogn2e-1^3=0.000104643
4loglogn2e3^-1=0.00212209
4loglogn3^-1e2=336.343
4loglogn3^2e-1=0.00883964
4loglogn3e-1^2=0.000883964
4loglogn3e2^-1=0.0336343

```

Description:

* The function `w[y]` converts string `y` to the number if `y` is not an operation.
* The pattern `g[g[x,c],y]` is converted to `x+y`, `x-y`, etc depending on the operation `c`. Otherwise it stay a symbolic expression.
* `f[x]` prints `x` only if it is a number.

# Answer
> 1 votes
## GolfScript 21 (51 characters -10 for handling negatives -20 for handling ^)

```
"#{File.read('a.txt')}"'^'/'?'*"\n"/(20@2/{(}%+''++~

```

Explanation:

Suppose `a.txt` contains "2+3/1\*4" (separated by new lines).

```
"#{File.read('a.txt')}" # Read in 'a.txt' as a string
'^'/'?'* # Replace all '^' with '?' to handle exponent.  This works by splitting the string on '^' and then folding on '?'.
"\n"/ # Split on newlines, so that we have an array of characters
(20@ # Pull out the first element of the array, push a 20 (ASCII value for space) and rearrange stack

```

At this point, the stack will look like `2 20 '+3/1*4'`.

```
2/ # Group by 2

```

So the stack looks like `2 20 [['+','3'],['/','1'],['*','4']]`.

```
{(}% # Map each element of the array to the tail of the tuple followed by its head.

```

So the stack looks like `2 20 [['3'], '+', ['1'], '/', ['4'], '*']`

```
+''++ # Concatenate, stringify, and concatenate.  Note that adding '' to an array flattens it.

```

So we are left with `'2 3 + 1 / 4 *'`.

```
~ # Finally, evaluate the string, since we were left with valid GolfScript.

```

This works with negatives, but accomplishes none of the other bonuses.

# Answer
> 1 votes
### GolfScript, score 54 (104 characters, bonus for neg., ^, e)

```
n%[[]]\{n/`{`{^2$<\@^>++}+\:^,),/}+%}/.&{2/1\{0='+-*/^e'\?0<&}/},{?}:^;{10\?*}:e;{."="+[n]@+2/{~~\~}/n}/

```

The input is given on STDIN.

**Example**

For input `1 2 3 + e`:

```
3+2e1=50
3e2+1=301
2+3e1=50
2e3+1=2001
2+1e3=3000
2e1+3=23
3+1e2=400
3e1+2=32
1+3e2=400
1e3+2=1002
1+2e3=3000
1e2+3=103

```

**Commented code with basic building blocks**

```
# split input
n%

# generate all permutations of the input (I'm working on a shorter implementation)
[[]]\{n/`{`{^2$<\@^>++}+\:^,),/}+%}/

# remove any duplicates (occur if same number/operator is given more than once)
.&

# filter for those permutations where each second element is an operator
{2/1\{0='+-*/^e'\?0<&}/},

# define operators ^ and e
{?}:^;
{10\?*}:e;

# Loop over all permutations
{
  .
  # make string representation
  "="+
  # reorder expression from ltr-infix into stack order and execute operations
  [n]@+2/{~~\~}/
  # add newline
  n
}/

```

# Answer
> 0 votes
**Javascript, 338 characters**

Handles `e`, negative values, and floats, bonus -50, **score 288**.

```
function g(a,p,r){a.length<1?r.push(p):a.map(function(c){g(a.filter(function(x){return x!=c}),p.concat(c),r)})}
x=[];y=[];x.push(readline());while(n=readline()){x.push(readline());y.push(n)}k=[];l=[];g(x,[],k);g(y,[],l);
l.map(function(y){k.map(function(x){r=x[0];s=r;y.map(function(b,i){n=b+x[i+1];s=s+n;r=eval(r+n);});print(s+'='+r)})})

```

Example here.

# Answer
> 0 votes
# Ruby 177 characters

* Implemented `^`: **-20**
* Handles negative values: **-10**
* No eval: **-20**

### Total: 127

```
$<.map{|x|x=~/\d+/&&x.to_i||x.chomp}.permutation{|x|$_=x*'';a,*b=x;puts$_+"=#{b.each_slice(2).reduce(a){|m,(o,y)|[m+y,m-y,m*y,m/y,m**y]["+-*/^".index o]}}"if~/^-?\d+(\W-?\d+)*$/}

```

Run with the input file as command line argument or give input on stdin.

Chopped up for readability:

```
$<.map{|x|x=~/\d+/?x.to_i: x.chomp}
  .permutation{|x|
    $_=x*''
    a,*b=x
    puts $_+"=#{
      b.each_slice(2).reduce(a){|m,(o,y)|[m+y,m-y,m*y,m/y,m**y]["+-*/^".index o]}
    }" if ~/^-?\d+(\W-?\d+)*$/}

```

# Answer
> 0 votes
# APL, score 36

156 chars - 20 (^) - 50 (logn) - 20 (e) - 10 (negative) - 20 (float) = 36

```
{⍺←{⍵[{1≥⍴⍵:⊃,↓⍵⋄⊃⍪/⍵,∘∇¨⍵∘~¨⍵}⍳⍴⍵]}⋄e←{⍺×10*⍵}⋄⍪,(↓⍺v/⍨~d)∘.{(,⍵,⍪⍺,'='),{⍎⍕⍵,⍺}/⌽(⍎↑⍵),↓'+-×÷*⍟e'['+-*/^le'⍳∊1⌷¨⍺],⍪1↓⍵}↓⍺v/⍨d←2|⍳⍴v←('\S+'⎕S'&')⍵⎕ntie 0}

```

Without any instructions to the contrary, I made `logn` an infix operator, as you would type it on a calculator, so that log2(16) is `2` `logn` `16`.

**Source**

```
⍝ main function; ⍵ is the file to read
{
    p←{1≥⍴⍵:⊃,↓⍵⋄⊃⍪/⍵,∘∇¨⍵∘~¨⍵}   ⍝ permutation matrix (taken from "dfns")
    q←{⍵[p⍳⍴⍵]}                   ⍝ all permutations of the given vector
    e←{⍺×10*⍵}                    ⍝ 'e' function as required
    v←('\S+'⎕S'&')⍵⎕ntie 0        ⍝ read input file and split on spaces
    d←2|⍳⍴v                       ⍝ bitmap of odd indices of input vector
    n←v/⍨d                        ⍝ odd-index values: the numbers
    o←v/⍨~d                       ⍝ even-index values: the operators

    ⍝ f will be called for each permutation of operators and numbers;
    ⍝ ⍺ is the (shuffled) list of operators; ⍵ of numbers
    f←{
        ⍝ translate the operators into APL
        ⍝ a trick is used to recognize 'logn' by its first letter only
        t←'+-×÷*⍟e'['+-*/^le'⍳∊1⌷¨⍺]

        ⍝ prepare the list of operations to perform, in reverse order,
        ⍝ followed by a single scalar with the value of the first number
        m←⌽(⍎↑⍵),↓t,⍪1↓⍵

        ⍝ fold over the previous vector, executing every operation in order
        r←{⍎⍕⍵,⍺}/m

        ⍝ return the result, preceded by a representation of the operation
        (,⍵,⍪⍺,'='),r
    }
    ⍝ generate all permutations of operators and of numbers; call f on
    ⍝ every combination (outer product); ravel and tabulate the result
    ⍪,(↓q o)∘.f↓q n
}

```

**Examples**

Input file:

```
-2.5
/
3
^
4

```

Output:

```
      {paste golfed code here} 'a.txt'
-2.5  /  3  ^  4 = 0.4822530863
-2.5  /  4  ^  3 = ¯0.244140625
3  /  -2.5  ^  4 = 2.0736
3  /  4  ^  -2.5 = 2.052800957
4  /  -2.5  ^  3 = ¯4.096
4  /  3  ^  -2.5 = 0.4871392899
-2.5  ^  3  /  4 = ¯3.90625
-2.5  ^  4  /  3 = 13.02083333
3  ^  -2.5  /  4 = 0.01603750748
3  ^  4  /  -2.5 = ¯32.4
4  ^  -2.5  /  3 = 0.01041666667
4  ^  3  /  -2.5 = ¯25.6

```

Input file:

```
2.5
e
3
logn
4

```

Output:

```
      {paste golfed code here} 'b.txt'
2.5  e  3  logn  4 = 0.1771838201
2.5  e  4  logn  3 = 0.1084874404
3  e  2.5  logn  4 = 0.2022289117
3  e  4  logn  2.5 = 0.08888300898
4  e  2.5  logn  3 = 0.1538078748
4  e  3  logn  2.5 = 0.1104756749
2.5  logn  3  e  4 = 11989.77847
2.5  logn  4  e  3 = 1512.941595
3  logn  2.5  e  4 = 8340.437671
3  logn  4  e  2.5 = 399.0350129
4  logn  2.5  e  3 = 660.9640474
4  logn  3  e  2.5 = 250.6045754

```

---
Tags: code-challenge
---


title: Code Golf: Directory Tree -> Tree

text:
# Question
Title: Code Golf: Directory Tree -> Tree
Contest (!): In the language of your choice, write a program that will traverse the directory tree of a given directory and output a tree (i.e., an array of arrays) corresponding to it. Assume the directory is a predefined variable D. Smallest character count wins.

**Rules:**

* You must use recursion
* See Rules

Note: Assume that there are no recursion depth limits. In other words, your code just needs to work for sufficiently small directory trees, and in principle for larger ones.

**For instance:**

Directory tree is

```
dir1
├── dir11
│   ├── file111
│   └── file112
├── dir12
│   ├── file121
│   ├── file122
│   └── file123
├── file11
├── file12
└── file13

```

Output tree is

```
[[[],[]],[[],[],[]],[],[],[]]

```

First code golf here so lemme know if I'm doing something wrong.

Have fun :)

# Answer
# Mathematica ~~120~~ ~~21~~ 20

Explicit recursion (thanks alephalpha for saving one char):

```
f=f/@__~FileNames~#&

f["~/StackExchange/dir1"]

```

> {{{}, {}}, {{}, {}, {}}, {}, {}, {}}

```
TreeForm[%]

```

Previous overcomplicated solution:

```
d="~/StackExchange/dir1"

f@{x___,Longest@s:{y_,___}..,z___}:=f@{x,f@Drop[{s},1,1],z}
f[FileNameSplit/@FileNames[__,SetDirectory@d;"",∞]]/.f->(#&)

```
> 6 votes

# Answer
## Powershell - 182 Char

```
function A([string]$b){write-host -NoNewline '['; ls -path $b|foreach{if($_.PSIsContainer){A($_.FullName)}ELSE{write-host -NoNewline $f'[]';$f=', '}};write-host -NoNewline ']'};A($D)

```

Fairly simple. Could be reduced by 10 characters if the commas weren't required. Takes input from $D (as stated in question), returns output on STD-Out as the example in the question went.

Really wishing aliases could use options! I'm being killed by the 'write-host -NoNewline's!
> 2 votes

# Answer
## Ruby, 38 chars

If you don't mind some extra whitespace in the output:

```
f=->n{Dir[n+'/*'].map{|c|f[c]}}
p f[D]

```

Example usage:

```
D='C:/work/dir1'
f=->n{Dir[n+'/*'].map{|c|f[c]}}
p f[D]

```

Output:

```
[[[], []], [[], [], []], [], [], []]

```

If I can't have the whitespace, something like this for the second line:

```
puts"#{f[D]}".tr' ',''

```
> 1 votes

# Answer
# C# 200 chars

Outputting a string, not an actual array. Takes a path as the first argument.

```
using D=System.IO.DirectoryInfo;class P{static string R(D d){var r="[";foreach(D e in d.GetDirectories())r+=R(e);return r+"]";}static void Main(string[] a) {System.Console.WriteLine(R(new D(a[0])));}}

```

Ungolfed:

```
using D = System.IO.DirectoryInfo;

class P
{
    static string R(D d)
    {
        var r = "[";
        foreach (D e in d.GetDirectories())
            r += R(e);
        return r + "]";
    }

    static void Main(string[] a)
    {
        System.Console.WriteLine(R(new D(a[0])));
    }
}

```
> 1 votes

# Answer
# Python 2.7, 111 chars

Takes the target path from stdin.

```
import os
def R(d):return[R(f)for f in[d+'/'+e for e in os.listdir(d)]if os.path.isdir(f)]
print R(raw_input())

```
> 1 votes

# Answer
## C++, 318 bytes

```
#include <cstdio>
#include <dirent.h>
#include <string>
#define s std::string
#define n e->d_name
s l(s p){s r;dirent*e;DIR*d;if(d=opendir(p.c_str())){int c=0;while(e=readdir(d))if(s("..")!=n&s(".")!=n)r+=&",["[!c++]+(e->d_type==DT_DIR?l(p+'/'+n):"")+"]";closedir(d);}return r;}main(){puts((s("[")+l(D)+"]").c_str());}

```

Here is a slightly ungolfed version:

```
#include <cstdio>
#include <dirent.h>
#include <string>

#define s std::string
#define n e->d_name

s l(s p) {
    s r;
    dirent*e;
    DIR*d;
    if (d=opendir(p.c_str())) {
        int c=0;
        while (e=readdir(d))
            if (s("..")!=n&s(".")!=n)
                r+=&",["[!c++]+(e->d_type==DT_DIR?l(p+'/'+n):"")+"]";
        closedir(d);
    }
    return r;
}

main() {
    puts((s("[")+l(D)+"]").c_str());
}

```

Please notice that since -- per instructions -- D is assumed to be a predefined variable, the code does not build without somehow supplying D. Here is one way to build:

```
g++ -Dmain="s D=\".\";main" -o tree golfed.cpp

```
> 0 votes

# Answer
## Batch script - 146, 157, 152 127 bytes

```
set x=
:a
set x=%x%,[
cd %1
goto %errorlevel%
:0
for /f %%a in ('dir/b') do call:a %%a
cd..
:1
set x=%x:[,=[%]
cls
@echo %x:~1%

```

Run with:

```
scriptfile.cmd folderroot

```
> 0 votes

---
Tags: code-golf, file-system
---


title: Regex - Match half of the strings

text:
# Question
Title: Regex - Match half of the strings
Okay, the challenge is that you have to write a regex that matches half of all strings.

Some rules to clarify:

For ANY string length(\>0), if I permute all strings(of that length), exactly half of them should be matched. Put more lightly, if I generate a random string of that length it should have a 50% chance of being matched. (this means that you cannot just match all even-length strings)

You may assume that strings contain only A-Z, a-z, and 0-9.

0 length strings are undefined, you can choose to either match them or not.

Shortest regex wins.

# Answer
> 11 votes
## 6

```
/^[5-Z]/

```

In ASCII's order, there's 0-9 then A-Z then a-z So Half of the string begin with 5-Z, the other half doesn't.

# Answer
> 5 votes
**9 characters (not counting leaning toothpicks)**

Modified mine from the comments:

```
 /^[A-Z0-4]/

```

It will match half of all 1 character strings. Every string of length greater than one starts with a one character string, half of which will match. So half match in total.

# Answer
> 5 votes
# 6

```
/^[0-U]/

```

Ranges work for ascii values, so this matches half of the 62 combinations of first letters. Can match the empty string for one extra char:

```
/^[0-U]?/

```

For more confusion, this is also a solution:

```
/^[--U]/

```

Also this:

```
/^[-U]/

```

where the ascii 0 is right before the `-`.

# Answer
> 2 votes
## 24

You didn't ask for a max length.

So an infinity of strings can exist.

Half of infinity = infinity.

But that doesn't lead anywhere.

Anyway, I'd say that "half of this infinite number of strings" start with \[A-Z0-4\] and the other half with \[a-z5-9\]

That's why I consider this answer correct (inspired by Tim Seguine)

```
/^[A-Z0-4][A-Za-z0-9]*$/

```

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


title: One Line Aquarium

text:
# Question
Title: One Line Aquarium
My parents-in-law have a fishpond in their yard, filled with koi. It didn't really cross my mind until I noticed the following extract from my code.

`',') & '_'`

... I had fish-faces looking back at me from my screen...

Which has given me a great idea...

My quest for you, my dear golfers is to create a one-line ASCII aquarium, with the following rules:

* The size of the aquarium from side of the tank to the other side of the tank should be no smaller than 60 characters and no bigger than 80 characters. Sides of the tank need to be indicated using the pipe/bar (`|`) character.
* Fish must be able to "swim" left to right between the sides of the tank. As they will be turning, a front view is required for the transition from one direction to the other.
* The fish must look like the following:

+ `}}< }} ',')` Fish swimming right
    + `(',' {{ >{{` Fish swimming left
    + `}}('_'){{` Fish facing the front
* When a fish turns to change direction (30% chance), it must start from one direction, face the front, then face the other direction... Make sure there is ample room for the fish to turn, i.e. requires six spaces before the edge of the tank minimum...
* Unless a fish is blowing a bubble or changing direction, it will continue in the direction it is facing, if it gets within six spaces of the side of the tank, it will change direction.
* The fish (facing left or right) can on occasion (10% chance) stop to blow bubbles in succession (`.oO*`), so the fish is required to have a space available next to them in order for the bubble to exist, so a fish can only swim as close to the sides, save one space. The bubble must disappear before the fish can move on...

A series of example lines of the fish's behavior, with `-` characters indicating the spaces, as the code display feature on here is a little strict... I will expect these dashes to be replaced with spaces when you code this...

Each line here could be considered a frame in time-lapse.

```
|-}}< }} ',')----------|
|--}}< }} ',')---------|
|---}}< }} ',')--------|
|----}}< }} ',')-------|
|-----}}< }} ',')------|
|-----}}< }} ',').-----|
|-----}}< }} ',')o-----|
|-----}}< }} ',')O-----|
|-----}}< }} ',')*-----|
|---------}}('_'){{----|
|-----------(',' {{ >{{|
|----------(',' {{ >{{-|
|---------(',' {{ >{{--|
|--------.(',' {{ >{{--|
|--------o(',' {{ >{{--|
|--------O(',' {{ >{{--|
|--------*(',' {{ >{{--|
|--------(',' {{ >{{---|
|-------(',' {{ >{{----|
|------(',' {{ >{{-----|

```

etc. The above example is, as I said, small, but you get the general idea...

Shortest code wins...

I am expecting the output on the same line (if possible), if not, displaying frame after frame in succession is fine... Whether you go one line or multiple lines is up to you. If you are doing multiple lines, they must be separated by a newline.

Also a timer is imposed between frames, 2000ms . This is **mandatory**.

Let's see what you've got!

# Answer
> 12 votes
# Python 3 (278)

Previously: 334, 332, 325, 302, 300, 299, 291, 286, 284, 281

```
import random,time
r=random.random
F="}}('_'){{%s","}}< }} ',')%s","%s(',' {{ >{{"
p,d=9,1
c=b=0
while 1:
 if c:p-=c+c*3*(2*d+c==1);d=c-c*d*d;c-=d
 elif b%5:b+=1
 elif.3>r()or{p*d}<{-5,53}:c=-d
 elif.1>r():b=1
 else:p+=d
 print('|%-70s|'%(' '*p+F[d])%' .oO*'[b%5]);time.sleep(2)

```

Golfing in Python is always difficult due to the indentation requirements of statements, but despite that, this went incredibly well!

Big thanks to Volatility and DSM for helping me golf this so much further.

### Clean version

```
from random import random as r
from time import sleep as s
F = { 1: "}}< }} ',')%s", 0: "}}('_'){{%s", -1: "%s(',' {{ >{{" }

# p: position (from left)
# d: direction (-1: left, +1: right)
# c: changing direction (0: not changing, +1: to right, -1: to left)
# b: bubble (0)
p, d, c, b = 9, 1, 0, 0

while 1:
    if c:
        p -= c*[1,4][2*d+c==1]
        if d:
            d = 0
        else:
            d, c = c, 0
    elif b % 5:
        b += 1
    else:
        # change direction
        if r() < .3 or p * d in (-5,53):
            c = -d
        # start bubbling
        elif r() < .1:
            b = 1
        # move forward
        else:
            p += d

    # print fish and sleep
    print('|{:<70}|'.format(' '*p+(F[d]%' .oO*'[b%5])))
    s(2)

```

# Answer
> 7 votes
# Ruby, ~~291~~ 289

```
l="(',' {{ >{{";m="    }}('_'){{    ";r="}}< }} ',')";w=?\s;s=w*6;q="|#{r+s*9}|"
f=->*s{(puts q;sleep 2)if q.sub! *s}
loop{rand>0.1||(f[") ",")."]||f[" (",".("];f[?.,?o];f[?o,?O];f[?O,?*];f[?*,w])
q[7]==?(||q[-8]==?)||rand<0.3?f[s+l,m]&&f[m,r+s]||f[r+s,m]&&f[m,s+l]:f[w+l,l+w]||f[r+w,w+r]}

```

The fish is eleven characters long, making the aquarium 6\*9+11+2 = 67 characters wide, which fits neatly in the required tolerance.

The `f` lambda function does all the heavy lifting: it accepts a substitution as a pair of arguments, then attempts to apply the substitution on the aquarium. If it succeeds, it paints one frame of the animation. It then reports the success value as `2` (the delay taken) or `nil` (delay not executed).

Fish will not blow bubbles twice in succession. (Fix: `...while rand>0.1` \- 4 characers)

Fish may blow bubbles even before a forced turn. (Fix: rearrange the branching structure)

There is a frame where the bubble is completely gone (including the `*`) but the fish has not moved into the resulting void. This follows the letter, but not the example. (Fix: replace `f[?*,w]` with `q[?*]=w` \- free)

Does not clear the console. Fix: add ``clear`` (Unix) or `system 'cls'` (Windows console) before `puts q` to fix <sup>(Ref.)</sup> or use `print` instead of `puts` and prepend `\r` to the aquarium (suggested by @manatwork).

**Readable version:**

```
# l - left fish; m - middle fish + space; r - right fish
# w - single space character; s - six spaces; q - the aquarium
l="(',' {{ >{{"; m="    }}('_'){{    "; r="}}< }} ',')";
w=" "; s=w*6; q="|#{r+s*9}|"
f = ->k,v do
  if q.sub! k,v
    puts q
    sleep 2
    return 2
  else
    return nil
  end
end

loop do
  if rand < 0.1
    f[") ",")."] || f[" (",".("]
    f[?.,?o]; f[?o,?O]; f[?O,?*]; f[?*,' ']
  end
  if q[7] == "(" || q[-8] == ")" || rand < 0.3
    (f[s+l,m] && f[m,r+s]) || (f[r+s,m] && f[m,s+l])
  else
    f[w+l,l+w] || f[r+w,w+r]
  end
end

```

# Answer
> 3 votes
### R, 451 characters

A first attempt:

```
f=function(j,p){cat("\r|",rep("-",j),p,rep("-",50-j),"|",sep="");Sys.sleep(2)};d=F;j=5;P=c("--}}(\'_\'){{--","-}}< }} \',\')-","-(\',\' {{ >{{-");B=c("-",".","o","O","*","-");g=Vectorize(gsub,v="replacement");b=list(g("-$",B,P[2]),g("^-",B,P[3]));repeat{if(j<5 & d){d=!d;j=j+1;f(j,P[1])};if(j>44 & !d){d=!d;f(j,P[1]);j=j-1};if(runif(1)<.1){for(i in b[[d+1]])f(j,i)}else{f(j,P[d+2])};if(runif(1)<.3){d=!d;f(j,P[1]);f(j,P[d+2])};if(d){j=j-1}else{j=j+1}}

```

Indented:

```
f=function(j,p){ #Printing function (depends of buffer and kind of fish)
    cat("\r|",rep("-",j),p,rep("-",50-j),"|",sep="")
    Sys.sleep(2)
}
d=F   #Direction: if FALSE left to right, if TRUE right to left.
j=5   #Buffer from left side of tank
P=c("--}}(\'_\'){{--","-}}< }} \',\')-","-(\',\' {{ >{{-") #The fish
B=c("-",".","o","O","*","-") #The bubble sequence
g=Vectorize(gsub,v="replacement")
b=list(g("-$",B,P[2]),g("^-",B,P[3])) #Fish+bubble
repeat{
    if(j<5 & d){ #What happens if too close from left side
        d=!d
        j=j+1
        f(j,P[1])
        }
    if(j>44 & !d){ #What happens if too close from right side
        d=!d
        f(j,P[1])
        j=j-1}
    if(runif(1)<.1){ #If bubble sequence initiated
        for(i in b[[d+1]])f(j,i)
        }else{f(j,P[d+2])} #Otherwise
    if(runif(1)<.3){ #If fish decide to turn
        d=!d
        f(j,P[1])
        f(j,P[d+2])
    }
    if(d){j=j-1}else{j=j+1} #Increment or decrement j depending on direction
}

```

It prints the aquarium as stdout on a single line (then 2s break and carriage return before the aquarium at t+1 is printed).

# Answer
> 3 votes
## Perl, 281

```
@f=("s O(',' {{ >{{","s}}('_'){{s","}}< }} ',')O s");$d=1;@o=split//," *Oo. ";{$_="|".$"x$x.$f[$d+1].$"x(44-$x).'|
';s/O/$o[$b]/;s/s/    /g;print;if($b||$t){$b--if$b;if($t){$d+=$t;$t=0if$d}}else{$x+=$d;$t=($x<1)-($x>43);if(!$t){$b=5if.9<rand;if(.7<rand){$t=-$d;$b=0}}}sleep 2;redo}

```

or more clearly

```
@f = ( "s O(',' {{ >{{", "s}}('_'){{s", "}}< }} ',')O s" );
$d = 1;
@o = split //, " *Oo. ";
{
    $_ = "|" . $" x $x . $f[ $d + 1 ] . $" x ( 44 - $x ) . '|
';
    s/O/$o[$b]/;
    s/s/    /g;
    print;
    if ( $b || $t ) {
        $b-- if $b;
        if ($t) { $d += $t; $t = 0 if $d }
    }
    else {
        $x += $d;
        $t = ( $x < 1 ) - ( $x > 43 );
        if ( !$t ) {
            $b = 5 if .9 < rand;
            if ( .7 < rand ) { $t = -$d; $b = 0 }
        }
    }
    sleep 2;
    redo
}

```

Fish turning correctly. Bubbles blowing.

**285** \- if you like the real aquarium feel and not the scrolling version:

```
$|=@f=("s O(',' {{ >{{","s}}('_'){{s","}}< }} ',')O s");$d=1;@o=split//," *Oo. ";{$_="\r|".$"x$x.$f[$d+1].$"x(44-$x).'|';s/O/$o[$b]/;s/s/    /g;print;if($b||$t){$b--if$b;if($t){$d+=$t;$t=0if$d}}else{$x+=$d;$t=($x<1)-($x>43);if(!$t){$b=5if.9<rand;if(.7<rand){$t=-$d;$b=0}}}sleep 2;redo}

```

# Answer
> 2 votes
## C, 400 394 373 characters

```
#define p printf
#define a(x) l[5]=r[11]=x;d();
char *l="      (',' {{ >{{",*f="    }}('_'){{    ",*r="}}< }} ',')      ",*c,s=7,i,*T;d(){p("|");for(i=0;i<s;i++)p(" ");p(c);for(i=0;i<70-s;i++)p(" ");puts("|");sleep(2);}b(){a(46)a(111)a(79)a(42)a(32)}t(){T=c;c=f;d();c=T==r?l:r;d();}m(){c==l?s--:s++;d();s>69||s<1?t():0;}main(){c=r;for(d();;)i=rand()%10,i?i>6?t():m():b();}

```

With whitespace:

```
#define p printf
#define a(x) l[5]=r[11]=x;d();
char *l="      (',' {{ >{{",
     *f="    }}('_'){{    ",
     *r="}}< }} ',')      ",
     *c,
     s=7,
     i,
    *T;
d(){
  p("|");
  for(i=0;i<s;i++)
    p(" ");
  p(c);
  for(i=0;i<70-s;i++)
    p(" ");
  puts("|");
  sleep(2);
}
b(){
  a(46)
  a(111)
  a(79)
  a(42)
  a(32)
}
t(){
  T=c;
  c=f;
  d();
  c=T==r?l:r;
  d();
}
m(){
  c==l?s--:s++;
  d();
  s>69||s<1?t():0;
}
main(){
  c=r;
  for(d();;)
    i=rand()%10,
    i?i>6?t():m():b();
}

```

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


# Question
Title: Manipulate destiny, fake random numbers: Be Dirty Harry
```
bool doYouFeelLuckyPunk, actuallyIsLucky;
doYouFeelLuckyPunk = Harry.catchyPhrase();
actuallyIsLucky = Bandit.rollDice();
if(doYouFeelLuckyPunk) {
    Bandit.grabGun();
    if(!actuallyIsLucky)
        Harry.useMagnum()
    else {
        Harry.tisButAScratch()
    }
else
    Bandit.surrender();

```

We all know how this plays out and we like it that way.
The task:
Write functions

> bool Harry.catchyPhrase()
>
> bool Bandit.rollDice()

Design them so the situation ends either in Harry.uswMagnum() or Bandit.surrender(), at random. Challenge and key criterion: Obfuscate the fact that bandit cannot win, fake and manipulate the "randomness" in your functions. The less obvious the better of course.
Explain your manipulation in a non-spoilering way (white text etc.)
Language: Doesn't matter Forbidden moves: none

# Answer
> 3 votes
How about this? Solution at the very bottom, encoded in base64. Language is C.

```
#include <stdio.h>
int lfsr = 0xACE1u;
/*Toy LFSR implementation stolen from wikipedia.*/
int random_bit(){
    /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
    int bit  = ((lfsr >> 0) ^ (lfsr >> 1) ^ (lfsr >> 3) ^ (lfsr >> 5) )&1 ;
    lfsr =  (lfsr >> 1) | (bit << 15);
    return ((lfsr >> 14)&(lfsr >> 15))^bit;
}
int surrendered=0,scratched=0,shot =0;

void harry_tis_but_a_scratch(){scratched++;}
int harry_catchy_phrase(){return random_bit();}
void bandit_surrender(){surrendered++;}
void harry_use_magnum(){shot++;}
int bandit_roll_dice() {return random_bit();}
void bandit_grab_gun() {}

int main()
{
    int random_number=0;
    /*Test bench random bit*/
    for(int y=1;y<51;++y){
        for(int x=0;x<8*sizeof(int);++x)random_number= (random_number<<1)|random_bit();
        printf("%-15d%c",random_number,y%5?' ':'\n');
    }
    printf("\nLooks pretty random\n\n");
    /*Play the game*/
    for(int x=0;100000 >=++ x;){
        int doYouFeelLuckyPunk = harry_catchy_phrase();
        int actuallyIsLucky = bandit_roll_dice();
        if(doYouFeelLuckyPunk) {
            bandit_grab_gun();
            if(!actuallyIsLucky) harry_use_magnum();
            else harry_tis_but_a_scratch();
        }else bandit_surrender();
    }
    printf("Shot: %d Surrendered: %d  Scratched: %d\n",shot,surrendered,scratched);
    return 0;
}
/*
                               Example Output
   1414529544,  -2071427967,     89395234,    690094340,    704663586,
     41977888,  -1572861663,   1107591810,    143171844,    546578948,
  -1542942712,  -1600056768,  -1571682240,     84415044,  -2138746864,
    705971264,    302123561,    168036485,    553717833,    545294674,
     71909648,  -1994096044,   1426227848,   1218611781,    138707496,
     16810505,    553783616,  -1861155808,  -1803283192,   1111626024,

Looks pretty random

Shot: 24941 Surrendered: 75059  Scratched: 0

                                  SOLUTION

IFRoZSB3YXkgdGhpcyB3b3JrcyBpcyBxdWl0ZSBzaW1wbGUsIHRoZSBMRlNSIGlzIHJlYWwgYW5k
IGRvZXMgaW4gZmFjdCBnZW5lcmF0ZQ0KIGdvb2QgcHNldWRvLXJhbmRvbSBudW1iZXJzLkFuZCBp
dCBpcyBpbmZhY3QgYW4gZXhhY3QgaW1wbGVtZW50YXRpb24gb2YgdGhlIG9uZQ0KIGZyb20gd2lr
aXBlZGlhLCBleGNlcHQgZm9yIG9uZSBhZGRpdGlvbjoNCiANCiBUaGUgb3V0cHV0IGJpdCBpcyB4
b3InZCB3aXRoICgobGZzcj4+MTQpJihsZnNyPj4xNSkpDQogDQogTm9ybWFsbHkgdGhpcyBzaG91
bGRuJ3QgYmUgYSBwcm9ibGVtLCBhcyB0aGUgcmVzdWx0IG9mIGEgcmFuZG9tIGJpdCB4b3InZCB3
aXRoDQogYW55IGZ1bmN0aW9uIGJlc2lkZXMgaXRzZWxmIGlzIHNlbGYgaXMgc3RpbGwgYSByYW5k
b20gYml0Lg0KIA0KIEhvd2V2ZXIsICgobGZzcj4+MTQpJihsZnNyPj4xNSkpIGlzIG5vdCBhIG5v
cm1hbCBmdW5jdGlvbi4gRHVlIHRvIHRoZSBMRlNSIGFsc28NCiBiZWluZyBhIHNoaWZ0IHJlZ2lz
dGVyIHRoZSBvdXRwdXQgb2YgdGhlIHJhbmRvbSBiaXQgZnVuY3Rpb24gaXMgYWN0dWFsbHkgdGhp
czoNCiANCiByZXR1cm4gKGxhc3RfYml0JmJpdCleYml0Ow0KIA0KIFNvLCBpZiB0aGUgbGFzdCBi
aXQgd2FzIGEgMSB0aGUgYml0IHJldHVybmVkIGlzIGd1YXJhbnRlZWQgdG8gYmUgMC4NCiANCiBT
byBpdCBpcyBpbXBvc3NpYmxlIHRvIGdldCB0byB0aGUgJ3RpcyBidXQgYSBzY3JhdGNoJyBmdW5j
dGlvbiwgYXMNCiBpdCBpcyBpbXBvc3NpYmxlIGZvciBib3RoIGRvWW91RmVlbEx1Y2t5UHVuayBh
bmQgYWN0dWFsbHlJc0x1Y2t5IHRvIGJlIHRydWUu

*/

```

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


# Question
Title: Implement the Universal Machine emulator
The goal is to write a full program that emulates the Universal Machine from ICFP 2006 with the shortest code. The Universal Machine has a very simple instruction set explained here. The emulator has to read a filename from command-line argument, and run the file as the program, so your language has to support command-line arguments and stdin/out in some way. The emulator has to complete the sandmark within a reasonable time (not decades). Here's a short explanation of the instruction set:

> The machine has eight registers each holding an 32-bit unsigned integer.
> The machine holds an indexed set of arrays of 32-bit unsigned integer cells.
> Shortly speaking, the allocation instruction returns an opaque 32-bit uint which is the handle to the created array, which has a static size, and holds 32-bit uint elements.
> The 0'th array denotes the program. It is loaded from a big-endian file on startup.
> There is also an Instruction Pointer which points to a cell in the 0 array.
> On each step, an instruction is read from the cell the Pointer points to, and the Pointer is inceremented before anything is done.
> The 4 most significant bits represent the opcode.
> If the opcode is 13, then the next 3 bits represent the register, and the other 25 represent the number that is written into the said register.
> Otherwise the 9 least significant bits represent three registers, say, A, B, and C, where C is represented by the 3 least significant bits.
> Then depending on the opcode, the following happens:
> 0. A = B unless C == 0
> 1. A = B\[C\]
> 2. A\[B\] = C
> 3. A = B + C
> 4. A = B * C
> 5. A = B / C
> 6. A = ~(B & C)
> 7. The emulator exits
> 8. B = allocate(C)
> 9. deallocate(C)
> 10. output a character from C to stdout
> 11. input a character from stdin into C
> 12. copy the array B into the 0 array and set the Pointer to C

I have written a needlessly complex but totally fast implementation (ab)using x86\_64 jitted assembly (the fun starts in emit()), which would for sure help you if you misunderstand some of the Machine's aspects.

# Answer
> 6 votes
## PHP: 443 416  384 bytes

```
<?php @eval(ereg_replace('[U-Z]','$\0',strtr('for(Y=[unpack("N*",join(file($argv[1])))];;A|=0){{W=Y[V=0][++U]
C&&A=B
A=Y[B][C+1]
Y[A][B+1]=C
A=B+C
A=B*C
A=bcdiv(PB),PC))*1
A=~B|~C
die
B=++Z
unset(Y[C])
echo chr(C)
C=fgetc(STDIN);C=ord(C)-(C=="")
Y[0]=Y[B|0];U=C
X[W>>25&7]=W&33554431;}}',['
'=>';}if((W>>28&15)==V++){',A=>'X[W>>6&7]',B=>'X[W>>3&7]',C=>'X[W&7]',P=>'sprintf("%u",'])));

```

\*Revamped again\*. It's as small as I can possibly get it now. I kept some variables down the far end of the alphabet so that the regex that inserts the $ signs doesn't mangle the STDIN constant, so here's a little glossary:

* U: instruction pointer
* V: index of opcode that's currently being tested
* W: current instruction word
* X: the 8 general purpose registers
* Y: main memory (each block is 1-based, since that's how `unpack()` returns arrays)
* Z: id of next free memory block (will eventually overflow, but the sandmark only uses ~92 million)
* A,B,C are the registers of the current instruction as in the spec

Unsigned division is a subtle nuisance (the `*1` is needed to ensure that large numbers cast back to the correct int) but the rest of the arithmetic is easy to keep 32-bit by ORing the arithmetic register with 0 (`A|=0`) after each instruction.

---

I found this project really interesting but striving to minimize the character count made it slow and inelegant, so I also made a simple (not golfed) Java version, that can complete the sandmark in a few minutes instead of taking all day:

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

public class UniversalMachine {
    public static void main(String[] args) throws IOException {
        if (args.length == 0) {
            System.err.println("Program not specified.");
            System.exit(1);
        }

        int[] program;
        try (RandomAccessFile raf = new RandomAccessFile(args[0], "r")) {
            program = new int[(int)(raf.length() / 4)];
            for (int i = 0; i < program.length; i++) {
                program[i] = raf.readInt();
            }
        }

        HashMap<Integer,int[]> memory = new HashMap<>();
        memory.put(0, program);
        int nextMemKey = 1;

        int[] R = new int[8]; // Registers
        int IP = 0; // Execution Finger (Instruction Pointer)

        loop: for (;;) {
            int ins = program[IP++];
            int op = ins >>> 28;
            if (op == 13) { // Orthography
                int A = (ins >> 25) & 7;
                int num = ins & 0x01FF_FFFF;
                R[A] = num;
            } else {
                final int A = (ins >> 6) & 7;
                final int B = (ins >> 3) & 7;
                final int C = (ins >> 0) & 7;
                switch (op) {
                case 0: // Conditional Move
                    if (R[C] != 0) R[A] = R[B];
                    break;
                case 1: // Array Index
                    R[A] = memory.get(R[B])[R[C]];
                    break;
                case 2: // Array Amendment
                    memory.get(R[A])[R[B]] = R[C];
                    break;
                case 3: // Addition
                    R[A] = R[B] + R[C];
                    break;
                case 4: // Multiplication
                    R[A] = R[B] * R[C];
                    break;
                case 5: // Division
                    R[A] = (int)((R[B] & 0xFFFF_FFFFL) / (R[C] & 0xFFFF_FFFFL));
                    break;
                case 6: // Not-And
                    R[A] = ~(R[B] & R[C]);
                    break;
                case 7: // Halt
                    break loop;
                case 8: // Allocation
                    // note: must use C before setting B, as they may be the same reg
                    memory.put(nextMemKey, new int[R[C]]);
                    R[B] = nextMemKey++;
                    break;
                case 9: // Abandonment
                    memory.remove(R[C]);
                    break;
                case 10: // Output
                    System.out.print((char)R[C]);
                    break;
                case 11: // Input
                    R[C] = System.in.read();
                    break;
                case 12: // Load Program
                    IP = R[C];
                    if (R[B] != 0) {
                        memory.put(0, program = memory.get(R[B]).clone());
                    }
                    break;
                }
            }
        }
    }
}

```

# Answer
> 3 votes
# Perl, 407

It looks like the question might seem too complex, actually it's very simple.
I'm still very new to perl though, anyway here it is

```
open$f,shift;binmode$f;push@{$m[0]},unpack'N',$b while read$f,$b,4;$z=2**32;while(){$o=$m[0][$p++];$a=\$r[$o>>6&7];$b=\$r[$o>>3&7];$c=\$r[$o&7];eval qw,$$a=($$b)if$$c $$a=$m[$$b][$$c] $m[$$a][$$b]=$$c $$a=($$b+$$c)%$z $$a=$$b*$$c%$z $$a=$==$$b/$$c $$a=$$b&$$c^($z-1) exit $$b=scalar@m;$m[$$b]=[] undef$m[$$c] print(chr$$c) $$c=ord(getc) $m[0]=[@{$m[$$b]}]if$$b;$p=$$c $r[$o>>25&7]=$o&33554431,[$o>>28].";";}

```

It runs really slow, probably 800x slower than the JITed x86\_64 one.
Also, a friend of mine made a reference C implementation

# Answer
> 2 votes
# C, ~~924~~ ~~838~~ ~~825~~ ~~696~~ ~~646~~ 623

I store a "pointer" (byte-offset) in the register designated `b` in the instruction, and use whatever register designates an array in the pseudocode in the same manner (or reverse, rather, to reconstitute a pointer) to access that array later. Still need to try the test program...

*Edit:* added comments.

*Edit:* fixed instruction 12. change the pointer, not the instruction in memory. Count is with all comments, indents, and newlines removed.

*Edit:* It appears to be running now, assuming I'm interpreting the results correctly. :) The final realization was that the *0 array* is indeed referenced by the *handle* 0, which may be found in an uninitialized register. A very twisted little machine! :)

*Edit:* rewrote debugging apparatus to use `write` instead of `printf`.... The idea here is to *remove* bugs. :) *Edit:* `putchar()` and `getchar()` are also no-nos with `sbrk`. It now works, and appears quite fast.

```
#define O(_)*a=*b _*c;B
#define B break;case
#define U unsigned
U*m,r[8],*p,*z,f,x,*a,*b,*c;main(int n,char**v){U char
u[4];z=m=p=sbrk(4);f=n>1?open(v[1],0):0;\
while(read(f,u,4)){*m++=(((((*u<<8)|u[1])<<8)|u[2])<<8)|u[3];sbrk(4);}sbrk(4);\
for(;x=*p++,1;){c=r+(x&7);b=r+((x>>3)&7);a=r+((x>>6)&7);switch(x>>28){case
0:*c?*a=*b:0;B
1:*a=(*b?m+*b:z)[*c];B
2:(*a?m+*a:z)[*b]=*c;B
3:O(+)4:O(*)5:O(/)6:*a=~(*b&*c);B
7:return 0;case
8:*b=1+(U*)sbrk(4*(1+*c))-m;(m+*b)[-1]=*c;B
9:B
10:*u=*c;write(1,u,1);B
11:read(0,u,1);*c=*u;B
12:*b?memcpy(z=sbrk(4*(m+*b)[-1]),m+*b,4*(m+*b)[-1]):0;p=&z[*c];B
13:a=r+((x>>25)&7);*a=x&0x1ffffff;}}}

```

For little-endian only, there's a **611** character version.

```
#define O(_)*a=*b _*c;B
#define B break;case
#define U unsigned
U*m,r[8],*p,*z,f,x,*a,*b,*c;main(int n,char**v){U char
u[4];z=m=p=sbrk(4);f=n>1?open(v[1],0):0;while(read(f,u,4)){*m++=(((((*u<<8)|u[1])<<8)|u[2])<<8)|u[3];sbrk(4);}sbrk(4);for(;x=*p++,1;){c=r+(x&7);b=r+((x>>3)&7);a=r+((x>>6)&7);switch(x>>28){case
0:*c?*a=*b:0;B
1:*a=(*b?m+*b:z)[*c];B
2:(*a?m+*a:z)[*b]=*c;B
3:O(+)4:O(*)5:O(/)6:*a=~(*b&*c);B
7:return 0;case
8:*b=1+(U*)sbrk(4*(1+*c))-m;(m+*b)[-1]=*c;B
9:B
//10:*u=*c;write(1,u,1);B //generic
10:write(1,c,1);B //little-endian
//11:read(0,u,1);*c=*u;B //generic
11:read(0,c,1);B //little-endian
12:*b?memcpy(z=sbrk(4*(m+*b)[-1]),m+*b,4*(m+*b)[-1]):0;p=&z[*c];B
13:a=r+((x>>25)&7);*a=x&0x1ffffff;}}}

```

Indented and commented, with (extended) commented debugging apparatus.

```
//#define DEBUG 1
#include <fcntl.h> // open
#include <signal.h> // signal
#include <stdio.h> // putchar getchar
#include <string.h> // memcpy
#include <sys/types.h> // open
#include <sys/stat.h> // open
#include <unistd.h> // sbrk read
unsigned long r[8],*m,*p,*z,f,x,o,*a,*b,*c; // registers memory pointer zero file working opcode A B C
char alpha[] = "0123456789ABCDEF";
//void S(int x){signal(SIGSEGV,S);sbrk(9);} // autogrow memory while reading program
void writeword(int fd, unsigned long word){
    char buf[8];
    unsigned long m=0xF0000000;
    int off;
    for (off = 28; off >= 0; m>>=4, off-=4) {
        buf[7-(off/4)]=alpha[(word&m)>>off];
    }
    write(fd, buf, 8);
    write(fd, " ", 1);
}
int main(int n,char**v){
#ifdef DEBUG
    int fdlog;
#endif
    unsigned char u[4]; // 4-byte buffer for reading big-endian 32bit words portably
    int cnt;

#ifdef DEBUG
    fdlog = open("sandlog",O_WRONLY|O_CREAT|O_TRUNC, 0777);
#endif
    z=m=p=sbrk(4); // initialize memory and pointer
    //signal(SIGSEGV,S); // invoke autogrowing memory -- no longer needed
    f=n>1?open(v[1],O_RDONLY):0; // open program
    while(read(f,u,4)){ // read 4 bytes
        *m++=(((((*u<<8)|u[1])<<8)|u[2])<<8)|u[3]; // pack 4 bytes into 32bit unsigned in mem
        sbrk(4); // don't snip the end of the program
    }
    sbrk(4);
    for(cnt=0;x=*p++,1;cnt++){ // working = *ptr; ptr+=1
        c=r+(x&7); // interpret C register field
        b=r+((x>>3)&7); // interpret B register field
        a=r+((x>>6)&7); // interpret A register field
#ifdef DEBUG
        {int i;write(fdlog,"{",1);for(i=0;i<8;i++)writeword(fdlog, r[i]);
            write(fdlog,"} ",2);
        }
        write(fdlog, alpha+(x), 1);
        write(fdlog, alpha+(x>>28), 1);
#endif
        switch(o=x>>28){ // interpret opcode
            case 0:
#ifdef DEBUG
                write(fdlog, "if(rX)rX=rX\n", 12);
#endif
                *c?*a=*b:0;
                break; // Conditional Move A=B unless C==0
            case 1:
#ifdef DEBUG
                write(fdlog, "rX=rX[rX]\n", 10);
#endif
                *a=(*b?m+*b:z)[*c];
                break; // Array Index A=B[C]
            case 2:
#ifdef DEBUG
                write(fdlog, "rX[rX]=rX\n", 10);
#endif
                (*a?m+*a:z)[*b]=*c;
                break; // Array Amendment A[B] = C
            case 3:
#ifdef DEBUG
                write(fdlog, "rX=rX+rX\n", 9);
#endif
                *a=*b+*c;
                break; // Addition A = B + C
            case 4:
#ifdef DEBUG
                write(fdlog, "rX=rX*rX\n", 9);
#endif
                *a=*b**c;
                break; // Multiplication A = B * C
            case 5:
#ifdef DEBUG
                write(fdlog, "rX=rX/rX\n", 9);
#endif
                *a=*b/ *c;
                break; // Division A = B / C
            case 6:
#ifdef DEBUG
                write(fdlog, "rX=~(rX&rX)\n", 12);
#endif
                *a=~(*b&*c);
                break; // Not-And A = ~(B & C)
            case 7:
#ifdef DEBUG
                write(fdlog, "halt\n", 5);
#endif
                return 0; // Halt
            case 8:
#ifdef DEBUG
                write(fdlog, "rX=alloc(rX)\n", 13);
#endif
                *b=1+(unsigned long*)sbrk(4*(1+*c))-m;
                   (m+*b)[-1]=*c;

                   break; // Allocation B = allocate(C)
            case 9:
#ifdef DEBUG
                   write(fdlog, "free(rX)\n", 9);
#endif
                   break; // Abandonment deallocate(C)
            case 10:
#ifdef DEBUG
                   write(fdlog, "output(rX)\n", 11);
#endif
                   //putchar(*c);
                   //*u=u[1]=u[2]=' ';
                   u[3]=(char)*c;
                   write(fileno(stdout), u+3, 1);
                   break; // Output char from C to stdout
            case 11:
#ifdef DEBUG
                   write(fdlog, "rX=input()\n", 11);
#endif
                   //x=getchar();*c=x;
                   read(fileno(stdin), u+3, 1);
                   *c=u[3];
                   break; // Input char from stdin into C
            case 12:
#ifdef DEBUG
                   write(fdlog, "load(rX)[rX]\n", 13);
#endif
                    *b?memcpy(z=sbrk(4*(m+*b)[-1]),m+*b,4*(m+*b)[-1]):0;
                    p=&z[*c];
                    break; // Load Program copy the array B into the 0 array, Ptr=C
            case 13:
#ifdef DEBUG
                    write(fdlog, "rX=X\n", 5);
#endif
                    a=r+((x>>25)&7);*a=x&0x1ffffff; // Orthography REG=immediate-25bit
        }
    }
}

```

---
Tags: code-golf, interpreter
---


# Question
Title: Find number of rectangles in a 2D byte array
```
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000111111000000000000000000011111111111111100000000000000000
0000000000000100001000000111111000000011111111111111100000000010000000
0000000000000100001000000111111000000000000000000000011000000000000000
0000000000000111111000000111111000000000000000000000011000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000

```

Your are given a 2 dimensional array of bytes of size m x n. It is guaranteed that all the bytes are 1's or 0's. Find the number of rectangles represented by 1's when viewed in 2d, as shown above.

Only fully filled rectangles are considered for counting.
Rectangles must be surrounded by 0's unless they are on edge(1's diagonally touching rectangles are Okay though (see example.)).

For example, in above array there are 5 valid rectangles.

You can use any language.

# Answer
> 2 votes
### GolfScript, 107 characters

```
.n?):L;'1'/{,}%{1$+)}*;][]\{:A{{+}+[1L.~)-1]%&}+1$\,.@^\[[[A]]+{|}*]+}/{.{L%}{%$..&1$,1$,/*$=}:C~\{L/}C&},,

```

The input must be given on STDIN.

Examples:

```
11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5

```

---
Tags: popularity-contest, geometry
---