title: Frogger Champion

text:
# Question
Title: Frogger Champion
# The Game

Most of us know about Frogger, the 80's era arcade game where the objective is to hop a frog safely across a busy highway and a hazard-filled pond to arrive safely at home.

A challenge was issued some months ago to develop a Frogger clone. But why *clone* Frogger when you can *play* Frogger? :)

Consider the following simplified playing grid:

```
 XXXXXXXXXXXXXXXXXXXXXXX  North Safe Zone
 -----------------------
|                       | <<<<       Express Lane West        (Lane 1)
|                       |     >      Gridlock East            (Lane 2)
|                       |   <<       Freeflowing Traffic West (Lane 3)
|                       |    <       Gridlock West            (Lane 4)
|                       |     >>>>   Express Lane East        (Lane 5)
 -----------------------
 XXXXXXXXXXX@XXXXXXXXXXX  South Safe Zone
 \__________ __________/
            '
  23 cells horizontally

```

We have five lanes of traffic, each 23 cells wide, and two safe zones (where the frog can move safely left and right), also 23 cells wide. You may ignore the right and left borders as these are for pictorial clarity.

Our frog starts in the southern safe zone, on the center (12th) cell, as indicated by a `@` in the above figure.

Time in the game is divided into discrete steps called frames. Froggy is a fast frog and can hop one cell in any direction (up, down, right, left) per frame. He may also choose to remain stationary for any frame. The traffic in the five lanes moves at constant speeds as follows:

* the traffic in the express lane west (lane 1) moves 2 cells left every frame
* the traffic in the gridlock east lane (lane 2) moves 1 cell right every second frame
* the traffic in the freeflowing traffic west lane (lane 3) moves 1 cell left every frame
* the traffic in the gridlock west lane (lane 4) moves 1 cell left every second frame
* the traffic in the express lane east (lane 5) moves 2 cells right every frame

The traffic itself is uniquely defined for approx. 3,000 timesteps in this text file. 'Traffic' consists of vehicles and spaces between the vehicles. Any character that is not a space is part of a vehicle. The text file contains five lines, corresponding to the five lanes of traffic (with the same order).

For the westbound lanes, at the start of frame 0 (the start of the game), we consider the first vehicle in the lane to be just beyond the right edge of the playing grid.

For eastbound lanes, the traffic string should be considered "backwards" in the sense that the vehicles appear starting at the *end* of the string. At the start of frame 0, we consider the first vehicle in these lanes to be just beyond the left edge of the playing field.

Consider as an Example:

```
Traffic Lane 1:  [|==|  =
Traffic Lane 2:  |) =  o
Traffic Lane 3:  (|[]-[]:
Traffic Lane 4:  <| (oo|
Traffic Lane 5:  |==|] :=)

```

Then the playing grid will appear as follows:

```
Start of Frame 0       XXXXXXXXXXXXXXXXXXXXXXX
                                              [|==|  =
                |) =  o
                                              (|[]-[]:
                                              <| (oo|
              |==|] :=)
                       XXXXXXXXXXXXXXXXXXXXXXX

Start of Frame 1       XXXXXXXXXXXXXXXXXXXXXXX
                                            [|==|  =
                |) =  o
                                             (|[]-[]:
                                              <| (oo|
                |==|] :=)
                       XXXXXXXXXXXXXXXXXXXXXXX

Start of Frame 2       XXXXXXXXXXXXXXXXXXXXXXX
                                          [|==|  =
                 |) =  o
                                            (|[]-[]:
                                             <| (oo|
                  |==|] :=)
                       XXXXXXXXXXXXXXXXXXXXXXX

Start of Frame 3       XXXXXXXXXXXXXXXXXXXXXXX
                                        [|==|  =
                 |) =  o
                                           (|[]-[]:
                                             <| (oo|
                    |==|] :=)
                       XXXXXXXXXXXXXXXXXXXXXXX

```

After all the traffic in a lane is "depleted" (i.e. the string runs out), we consider all characters in the string to be spaces.

Our frog is *squished* if any of the following occurs:

* the frog occupies a cell occupied by a vehicle, on any frame
* the frog remains stationary in an express lane and a vehicle of 1 cell width passes over him in that frame
* the frog jumps east "through" a vehicle heading west, or jumps west through a vehicle heading east
* the frog jumps outside of the 7 (line) by 23 (cell) playing grid, on any frame

Note that these are the *only* conditions under which a frog is squished. In particular, a frog hopping along "with" traffic is permissible, as is a frog jumping into or out of a cell in an express lane that is passed over by a width-1 vehicle in the same frame.

# Objective and Scoring

The objective of the programming challenge is to get the frog across the road as many times as possible before *the last vehicle exits the playing grid*. That is, the program terminates immediately after the completion of frame *X*, where frame *X* is the first frame that takes the grid to a state where no more vehicles are present.

The output of your program should be a string (or text file) containing the sequence of moves for the frog using the following encoding:

```
<   frog moves left
>   frog moves right
^   frog moves up
v   frog moves down
.   frog remains stationary

```

For example, the string `<<^.^` indicates that the frog moves left twice, then up, then pauses for one frame, then moves up again.

One point is scored whenever the frog crosses from the south safe zone to the north safe zone, and one point is scored whenever the frog crosses from the north safe zone to the south safe zone.

Some important rules:

1. **The frog must not be squished.**
2. Please post your solution (sequence of moves) along with your program code, either inline or as a text file (e.g. using pastebin.com).
3. Our frog is prescient and precognizant, hence your program may make use *any and all traffic data* in any frame while seeking out solutions. This includes data for traffic that hasn't yet reached the playing grid.
4. The grid does not wrap around. Exiting the grid will cause the frog to be squished and hence is not permitted.
5. At no point does traffic "reset" or the frog "teleport". The simulation is continuous.
6. The frog may return to the south safe zone after exiting it, but this is not counted as a point. Likewise for the north safe zone.
7. **The contest winner is the program that generates the move sequence yielding the highest number of crossings.**
8. For any additional questions or concerns, please feel free to ask in the comments section.

For some added incentive, I'll add a bounty of **+100 rep** to the winning program when I'm able to do so.

# Bonuses

**+2.5%** to the base score\* (up to +10%) for every corner of the playing grid the frog touches. The four corners of the grid are the leftmost and rightmost cells of the two safe zones.

**+25%** to the base score\* if your sequence of moves keeps the frog confined to within +/- 4 cells left or right of his starting cell for the entire simulation (he can of course move freely vertically).

No scoring bonus, but special props in the OP will go to anyone who posts a quick n' dirty solution validator so that I don't have to program one. ;) A validator would simply accept a sequence of moves, ensure its legality (per the rules and the traffic file), and report its score (i.e. the total number of crossings).

\*Total score is equal to base score plus the bonus, rounded down to the nearest integer.

### Good luck frogging!

# Answer
> 6 votes
# C++: 176

Output:

```
176
^^^^^^>vvvvvv>^^^^>^^>>>>>>><<<.vv>v<<<.vvv<<<<<<^.^.^.^.>.>^^<.>>>>>>v>v>.>v<<<<v.<.vv<<<<<^^.<^<<<<<<^.^^>>>>vv>.>.v<v.vv>>^>>^<^<<<<<<<^>.>^^<<<.>>>>>vv>v<vvv<<<<<^^.<^^^^.....vv>.>.>.>v<<vvv<<>>>>^>^<.<.^^>^^>>>>vv.>v<vv.v^>^<.<.<^<^>.>^^>>>>vv.v<<<<<<.vvv<<<<^^^<<v^^.>.^^..>>>>>>vv>.>.v.vvv>>>^>^^<<<<<<<<<^>.>^^>>>>vvv<<v.<.vv<<<<<<>>>>>^^^<<<^^^<<>>vv>.v<<>vvv<<><>>>>>>>^>^^<^^^<.>>>>>>>>vv>.>v<<<vvv<<<<<^^^<<v.<.<^<<^.^<<^...>>>>>>>>>>>>>vv>v<vvv<<<<<<<<^>^.<.^^>.>^^<<<<<<<..>>>>vv>.vvvv<<<<>^.v>>>^^.^^>^<^<>>>>>>>>>vv>vvvv<<<<^^^<^>^<<^.>>vv>v<vvv<<<<<<<>>>>>>>^>^^^.^^>>>>>vvv<<vvv<<<^^^^^^<vvv<<<<<<<vvv<<<>>>>>>>>^^.<.<.^.^.^<^<>>>>>>>>>>vvv<<.vvv<<<^^<^<<^^<<^<<<>>>>vv>.vvvv>>^>>^<.<.<^<<<<<.^^<<^.......>vv.>.>.>v<vvv>>>>>>^>^.<.<^<.^^^<.>>>>>>>vvv<<<v.<vv<<<^^<.<.<.<^<<<^>^^..........v<vvvv>v>>>>>^>>^^^>^^>>>vv>v<vvv<<<<<<<<>^^.<.<^<^^^<.........>vv.>.vvvv>>>>^^<.<.<^^^<^<<.v<v>.>.>.>.>.>.>.vvv.v<<<<<^^<^<^>.>.>.>.^<^.>>>>>>>>vv>v<<vvv<<>>>>>^^^.^.>^<^<<<<<<<<.vv.>.v<<<.vvv<>>>>>^>^.<.<.<.<^^.^<<^<.....>>vvv<.>>vvv<<<>>>>>>>>^^^<<<.^.>.>^^.>>>>>vv.>v<vvv<<<>>>>>>^>^<^<<^.^^<vvv<<<<<vv.v<>>>>>>>>>>^>^.^^>^^<<<<.>vv.>.vvvv>^>>^.<.<.<^<<<^>^^>>>vv>v<<<<<vvv<<<>>>>>^^<.<.<.<.<^<^>.^^.>>>>>vv>v<>vvv<<<<<<<^>^.<^<<<<<<<^^^.>>>>>vv>v<>vvv>>>^^<.<^<<<^>^^.>>>>vv>.v<<vvv<<<<<^^^<<<<<^>.^^<>>>>>>>vv>.>v<<vvv<<<<<<<>>>^>>.>^^^.>^^<>>>>>>vv>vv.<.<.vv>>>>^^<.<.<.<^<<^.>^^.>>>>>vv.>.>v<<vvv<<>>>>>^^<.<.<.^^>.>.>^^<<<<<<<<.>>>>>>vv>v<<v.<.<vv<<<<^^.<^<<<.^^^<.vv.>v<vvv<<<>>>>>>^>^<^<<^.^<^<<.>>vv>.>.>.>vvvv>>>>>>^>^^^^^<<<.vvv<<<<<<vvv>>>>>^>^<.<^<<^.>.>.^^>>>>vv>.>v<<<<<<vvv<<<<^^^<.^.>^^>>>>vvv<<v.vv<<<^>>^^<<<.^^<<^>>>>>>>>>vvv.v.vv<>>>>>^>^^<<<<<<<<<<<<<<<<^^^..>>>>>vv>.>.>.>v<<v.<.<.vv<<<<<^^^<^>.^^...>>>>>>>>vv.v<.vvv>>>^>^<.<^^^^>>>vv>v<<<vvv<<<<>>>>>>^>^.<.<^<^>.>^^.>>>>>vv.v<<<<<<<<vvv<<<<^^<^<<<<<><^>.>^^>>>>vv.>.>.vvv.v>>>>>>>^^<.<^<<^^^>>>vv>.>.>.>.>v<<v.<.<vv>>>>^^^<<<<<.^.>^^>>>vv>.>v<vvv<<<<^^<.<.<.^^>^^>>>vv>.>.v<<<v.<vv<<<<^^.<^<<<^^^>>>>vvvvvv<<<<<<<<>^^.^>>^^^<>>>>>>>vvv<<<v.vv>>>>>^>>^^<<<<<^>.^^>>>>vv>.>v<<<<vvv<<<^^<.<.<.<^<<<<<^>^^>>>>vv.>vv.v.v<^>.>^.<.^^^^>>>>vv>.>.>.v<<<<<<vvv>>>>^^<.<.<^<<^^<^>>>>>>vv>v<<.vvv^>^^<<<^>^^<<<<<<.vvv<<vv>.v>>>>>>^>.>^^<<<<<^>.>.>.>.>.^^>>>>vv>.>.>v<<<<<vvv<<<<^^<^<<^.^^>>>>vv>.>.>.>v<vvv<<<<<^^.<.<^<<^^^>>>>>>>>>>>vv>.>.>.>.>vvvv<<<<^^.<.<^<^^^<<<<<<vvv<v.<vv<<<<^v>>>>>>>>>>^^^<.^.>.>.^^>>>>vvv<<<<<<<vvv<<<<<<<>^^.<^<.^^^.>>>>vv>v<vvv<>>>>^^.<.^.^.>.^<^>>>>>>>>vvvv.<.<vv<<<<^^^<<<<<^>.^^<.vv>.v<<vvv<<><>>>>>^>>^.<^<^^^<<<.>>vv>.>v<<<<v.vv>^>>^.<^^.^^.>>>>>vv>.>.>.v<v.<vv<<<<<^.^^^.>^^<>>>>>>vv>.v<<<v.<vv<<<<>>>>>>>>>>>^^<.<.<.<.<^<<^^<^<<<>>>>>>>vv>v<<<vv.v>>>>>>>>^>^<.<^<<<<<<<<<<<.^.>^^<<<vvv.v.<vv<<<^.>>^.<^^.>.>^^<<......vv.v>vvv>>>^.v^>>^^<<^^^<.>>>>>>>vvv<v.<.<.vv<<<<^^<.<.<.^^^^<.>>>>>>>>vvv<v.<vv^.>^^<<^^^vv>vvvv^>>>>>>>^^^^^vvvvvv^^^^^^vvvvvv>>>>

```

There are under 8 million states combinations of position X time X set of visited corners, so they can be exhaustively searched in less than 1 second. If the code has no bugs, it should be impossible to beat. The optimal strategy was to use the whole board, as that allows froggy to cross the road 160 times, versus about 120 when confined to the center. Visiting the corners didn't cost any crossings since the traffic was so heavy.

```
/* feersum  2014/9
 https://codegolf.stackexchange.com/questions/37975/frogger-champion */

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstring>

#define B(F, CST, X, Y) best[ ((F)*NCST + (CST)) * BS + (Xmax-Xmin+1) * ((Y)-Ymin) + (X)-Xmin]
#define TL(i) ((int)t[i].length())
#define ABSPEED(I) (speed[i]<0?-speed[i]:speed[i])
#define errr(X) { cout<<"ERROR!!!!!!!!"; return X; }

#define DRAW 0
#if DRAW
    #include <unistd.h>
#endif

using namespace std;

int bc(int cs) {
    int c = 0;
    while(cs) {
        c += cs&1;
        cs >>= 1;
    }
    return c;
}

int main()
{
    const bool bonusTwentyfive = false;
    const int COLS = 23, T_ROWS = 5, YGS = T_ROWS + 2, XGS = COLS + 2;
    string t[5];
    int speed[] = {-4, 1, -2, -1, 4};
    ifstream f("t.txt");
    for(int i = 0; i < T_ROWS; i++)
        getline(f, t[i]);
    if(f.fail())
        return 1;
    f.close();
//for(int i = 0; i < 5; i ++)t[i]="xxx";

    char g[XGS][YGS];

    int mov[][3] = { {-1,  0, '<'},
                     {+1,  0, '>'},
                     { 0, -1, '^'},
                     { 0, +1, 'v'},
                     { 0,  0, '.'} };

    int Ymin = 0, Ymax = YGS-1;

    const int Xstart = 11, Xmaxmove = bonusTwentyfive ? 4 : 10;
    const int Xmin = Xstart - Xmaxmove, Xmax = Xstart + Xmaxmove;

    const int NCST = bonusTwentyfive ? 1 : 1<<4;

    int maxfr = 0;
    for(int i = 0; i < T_ROWS; i++) {
        if(speed[i] < 0) {
            for(int m = 0, n = t[i].length()-1; m < n; ++m,--n)
                swap(t[i][m], t[i][n]);
        }
        int carslen = TL(i);
        for(char*c = &t[i][speed[i]>0?TL(i)-1:0]; carslen; carslen--, speed[i]>0?--c:++c)
            if(*c != ' ')
                break;
        if(carslen)
            maxfr = max(maxfr, ( (carslen + COLS) * 2 + ABSPEED(i)-1 ) / ABSPEED(i));
    }
    const int BS = (Xmax-Xmin+1)*(Ymax-Ymin+1);
    int *best = new int[(maxfr+1)*NCST*BS];
    memset(best, 0xFF, (maxfr+1)*NCST*BS*sizeof(int));
    memset(g, ' ', sizeof(g));
    B(0, 0, Xstart, Ymax) = 0;

    for(int fr = 0; fr < maxfr; fr++) {
        for(int r = 0; r < T_ROWS; r++) {
            for(int x = 0; x < XGS; x++) {
                int ind = speed[r] > 0 ? TL(r)-1 + x - fr*speed[r]/2 : x - (XGS-1) - fr*speed[r]/2;
                g[x][r+1] = ind >= 0 && ind < TL(r) ? t[r][ind] : ' ';
            }
        }
        for(int x = Xmin; x <= Xmax; x++) {
            for(int y = Ymin; y <= Ymax; y++) {
                if(g[x][y] != ' ')
                    continue;
                for(unsigned m = 0; m < sizeof(mov)/sizeof(mov[0]); m++) {
                    int X = x + mov[m][0], Y = y + mov[m][1];
                    if(X < Xmin || X > Xmax || Y < Ymin || Y > Ymax)
                        continue;
                    if(!(mov[m][0]|mov[m][1]) && y > 0 && y > T_ROWS && g[x][y-speed[y-1]/4] != ' ')
                        continue;

                    int csor = ((X==Xmin|X==Xmax)&(Y==Ymin|Y==Ymax)&!bonusTwentyfive) << ((X==Xmax) + 2*(Y==Ymax));

                    for(int cs = 0; cs < NCST; cs++) {
                        int N = B(fr, cs, x, y);
                        if(!~N)
                            continue;
                        if((!(N&1) && y == 1 && Y == 0) ||
                              (N&1 && y == T_ROWS && Y == T_ROWS+1))
                            ++N;
                        if(N > B(fr+1, cs|csor, X, Y))
                            B(fr+1, cs|csor, X, Y) = N;
                    }

                }
            }
        }
    }

    int score = 0, xb, yb, cb, nb;
    for(int x = Xmin; x <= Xmax; x++) {
        for(int y = Ymin; y <= Ymax; y++) {
            for(int cs = 0; cs < NCST; cs++) {
                if(B(maxfr, cs, x, y) * (40 + bc(cs)) / 40 >= score) {
                    score = B(maxfr, cs, x, y) * (40 + bc(cs)) / 40;
                    xb = x, yb = y, cb = cs, nb = B(maxfr, cs, x, y);
                }
            }
        }
    }
    char *mvs = new char[maxfr+1];
    mvs[maxfr] = 0;

    for(int fr = maxfr-1; fr >= 0; --fr) {
        for(int r = 0; r < T_ROWS; r++) {
            for(int x = 0; x < XGS; x++) {
                int ind = speed[r] > 0 ? TL(r)-1 + x - fr*speed[r]/2 : x - (XGS-1) - fr*speed[r]/2;
                g[x][r+1] = ind >= 0 && ind < TL(r) ? t[r][ind] : ' ';
            }
        }
        for(int x = Xmin; x <= Xmax; x++) {
            for(int y = Ymin; y <= Ymax; y++) {
                if(g[x][y] != ' ')
                    continue;

                for(unsigned m = 0; m < sizeof(mov)/sizeof(mov[0]); m++) {
                    int X = x + mov[m][0], Y = y + mov[m][1];
                    if(X < Xmin || X > Xmax || Y < Ymin || Y > Ymax)
                        continue;
                    if(!(mov[m][0]|mov[m][1]) && y > 0 && y > T_ROWS && g[x][y-speed[y-1]/4] != ' ')
                        continue;

                    int csor = ((X==Xmin|X==Xmax)&(Y==Ymin|Y==Ymax)&!bonusTwentyfive) << ((X==Xmax) + 2*(Y==Ymax));

                    for(int cs = 0; cs < NCST; cs++) {
                        int N = B(fr, cs, x, y);
                        if(!~N)
                            continue;
                        if((!(N&1) && y == 1 && Y == 0) ||
                              (N&1 && y == T_ROWS && Y == T_ROWS+1))
                            ++N;
                        if(X==xb && Y==yb && N == nb && (cs|csor) == cb) {
                            mvs[fr] = mov[m][2];
                            xb = x, yb = y, nb = B(fr, cs, x, y), cb = cs;
                            goto fr_next;
                        }
                    }
                }
            }
        }
        errr(3623);
        fr_next:;
    }

    if((xb-Xstart)|(yb-Ymax)|nb)
        errr(789);
    #if DRAW

        for(int fr = 0; fr <= maxfr; ++fr) {
            memset(g, ' ', sizeof(g));
            for(int r = 0; r < T_ROWS; r++) {
                for(int x = 0; x < XGS; x++) {
                    int ind = speed[r] > 0 ? TL(r)-1 + x - fr*speed[r]/2 : x - (XGS-1) - fr*speed[r]/2;
                    ind >= 0 && ind < TL(r) ? g[x][r+1] = t[r][ind] : ' ';
                }
            }
            g[xb][yb] = 'F';
            for(int y = 0; y < YGS; y++) {
                for(int x = 0; x < XGS; x++)
                    cout<<g[x][y];
                cout<<endl;
            }
            cout<<string(XGS,'-')<<endl;
            usleep(55*1000);
            for(int i = 0; i < 5; i++) {
                if(mvs[fr] == mov[i][2]) {
                    xb += mov[i][0];
                    yb += mov[i][1];
                    break;
                }
            }
        }

    #endif
    cout<<score<<endl;
    cout<<mvs<<endl;
}

```

---
Tags: code-challenge, game, optimization
---


title: Compute the CRC32 table at compile-time

text:
# Question
Title: Compute the CRC32 table at compile-time
The reference implementation of CRC32 computes a lookup table at runtime:

```
/* Table of CRCs of all 8-bit messages. */
unsigned long crc_table[256];

/* Flag: has the table been computed? Initially false. */
int crc_table_computed = 0;

/* Make the table for a fast CRC. */
void make_crc_table(void)
{
    unsigned long c;

    int n, k;
    for (n = 0; n < 256; n++) {
        c = (unsigned long) n;
        for (k = 0; k < 8; k++) {
            if (c & 1) {
                c = 0xedb88320L ^ (c >> 1);
            } else {
                c = c >> 1;
            }
        }
        crc_table[n] = c;
    }
    crc_table_computed = 1;
}

```

Can you compute the table at compile-time, thus getting rid of the function and the status flag?

# Answer
Here's a plain C solution:

**crc32table.c**

```
#if __COUNTER__ == 0

    /* Initial setup */
    #define STEP(c) ((c)>>1 ^ ((c)&1 ? 0xedb88320L : 0))
    #define CRC(n) STEP(STEP(STEP(STEP(STEP(STEP(STEP(STEP((unsigned long)(n)))))))))
    #define CRC4(n) CRC(n), CRC(n+1), CRC(n+2), CRC(n+3)

    /* Open up crc_table; subsequent iterations will fill its members. */
    const unsigned long crc_table[256] = {

    /* Include recursively for next iteration. */
    #include "crc32table.c"

#elif __COUNTER__ < 256 * 3 / 4

    /* Fill the next four CRC entries. */
    CRC4((__COUNTER__ - 3) / 3 * 4),

    /* Include recursively for next iteration. */
    #include "crc32table.c"

#else

    /* Close crc_table. */
    };

#endif

```

It relies on the nonstandard `__COUNTER__` macro, as well as an evaluation semantics where `__COUNTER__` is evaluated before it is passed as an argument to a macro.

Note that, since `STEP` evaluates its argument twice, and `CRC` uses eight nested invocations of it, there is a small combinatorial explosion in the code size:

```
$ cpp crc32table.c | wc -c
4563276

```

I tested this in GCC 4.6.0 and Clang 2.8 on 32-bit Linux, and both produce the correct table.
> 13 votes

# Answer
The core loop

```
for (k = 0; k < 8; k++) {
    if (c & 1) {
        c = 0xedb88320L ^ (c >> 1);
    } else {
        c = c >> 1;
    }
}

```

can be converted into a meta-function:

```
template <unsigned c, int k = 8>
struct f : f<((c & 1) ? 0xedb88320 : 0) ^ (c >> 1), k - 1> {};

template <unsigned c>
struct f<c, 0>
{
    enum { value = c };
};

```

Then, 256 calls to this meta-function (for the array initializer) are generated by the preprocessor:

```
#define A(x) B(x) B(x + 128)
#define B(x) C(x) C(x +  64)
#define C(x) D(x) D(x +  32)
#define D(x) E(x) E(x +  16)
#define E(x) F(x) F(x +   8)
#define F(x) G(x) G(x +   4)
#define G(x) H(x) H(x +   2)
#define H(x) I(x) I(x +   1)
#define I(x) f<x>::value ,

unsigned crc_table[] = { A(0) };

```

If you have Boost installed, generating the array initializer is a bit simpler:

```
#include <boost/preprocessor/repetition/enum.hpp>

#define F(Z, N, _) f<N>::value

unsigned crc_table[] = { BOOST_PP_ENUM(256, F, _) };

```

Finally, the following test driver simply prints all array elements to the console:

```
#include <cstdio>

int main()
{
    for (int i = 0; i < 256; ++i)
    {
        printf("%08x  ", crc_table[i]);
    }
}

```
> 9 votes

# Answer
A C++0x solution

```
template<unsigned long C, int K = 0>
struct computek {
  static unsigned long const value =
    computek<(C & 1) ? (0xedb88320L ^ (C >> 1)) : (C >> 1), K+1>::value;
};

template<unsigned long C>
struct computek<C, 8> {
  static unsigned long const value = C;
};

template<int N = 0, unsigned long ...D>
struct compute : compute<N+1, D..., computek<N>::value>
{ };

template<unsigned long ...D>
struct compute<256, D...> {
  static unsigned long const crc_table[sizeof...(D)];
};

template<unsigned long...D>
unsigned long const compute<256, D...>::crc_table[sizeof...(D)] = {
  D...
};

/* print it */
#include <iostream>

int main() {
  for(int i = 0; i < 256; i++)
    std::cout << compute<>::crc_table[i] << std::endl;
}

```

Works on GCC (4.6.1) and Clang (trunk 134121).
> 6 votes

# Answer
C++0x with `constexpr`. Works on GCC4.6.1

```
constexpr unsigned long computek(unsigned long c, int k = 0) {
  return k < 8 ? computek((c & 1) ? (0xedb88320L ^ (c >> 1)) : (c >> 1), k+1) : c;
}

struct table {
  unsigned long data[256];
};

template<bool> struct sfinae { typedef table type; };
template<> struct sfinae<false> { };

template<typename ...T>
constexpr typename sfinae<sizeof...(T) == 256>::type compute(int n, T... t) {
  return table {{ t... }};
}

template<typename ...T>
constexpr typename sfinae<sizeof...(T) <= 255>::type compute(int n, T... t) {
  return compute(n+1, t..., computek(n));
}

constexpr table crc_table = compute(0);

#include <iostream>

int main() {
  for(int i = 0; i < 256; i++)
    std::cout << crc_table.data[i] << std::endl;
}

```

You can then use `crc_table.data[X]` at compile time because `crc_table` is `constexpr`.
> 5 votes

# Answer
This is my first metaprogram:

```
#include <cassert>
#include <cstddef>

template <std::size_t N, template <unsigned long> class T, unsigned long In>
struct times : public T<times<N-1,T,In>::value> {};

template <unsigned long In, template <unsigned long> class T>
struct times<1,T,In> : public T<In> {};

template <unsigned long C>
struct iter {
    enum { value = C & 1 ? 0xedb88320L ^ (C >> 1) : (C >> 1) };
};

template <std::size_t N>
struct compute : public times<8,iter,N> {};

unsigned long crc_table[] = {
    compute<0>::value,
    compute<1>::value,
    compute<2>::value,
    // .
    // .
    // .
    compute<254>::value,
    compute<255>::value,
};

/* Reference Table of CRCs of all 8-bit messages. */
unsigned long reference_table[256];

/* Flag: has the table been computed? Initially false. */
int reference_table_computed = 0;

/* Make the table for a fast CRC. */
void make_reference_table(void)
{
    unsigned long c;

    int n, k;
    for (n = 0; n < 256; n++) {
        c = (unsigned long) n;
        for (k = 0; k < 8; k++) {
            if (c & 1) {
                c = 0xedb88320L ^ (c >> 1);
            } else {
                c = c >> 1;
            }
        }
        reference_table[n] = c;
    }
    reference_table_computed = 1;
}

int main() {
    make_reference_table();
    for(int i = 0; i < 256; ++i) {
        assert(crc_table[i] == reference_table[i]);
    }
}

```

I "hardcoded" the calls to the template that does the computation :)
> 4 votes

# Answer
# D

```
import std.stdio, std.conv;

string makeCRC32Table(string name){

  string result = "immutable uint[256]"~name~" = [ ";

  for(uint n; n < 256; n++){
    uint c = n;
    for(int k; k < 8; k++)
      c = (c & 1) ? 0xedb88320L ^ (c >> 1) : c >>1;
    result ~= to!string(c) ~ ", ";
  }
  return result ~ "];";
}

void main(){

  /* fill table during compilation */
  mixin(makeCRC32Table("crc_table"));

  /* print the table */
  foreach(c; crc_table)
    writeln(c);
}

```

It really puts C++ to shame, doesn't it?
> 3 votes

# Answer
# C/C++, 306 295 bytes

```
#define C(c)((c)>>1^((c)&1?0xEDB88320L:0))
#define K(c)(C(C(C(C(C(C(C(C(c))))))))),
#define F(h,l)K((h)|(l+0))K((h)|(l+1))K((h)|(l+2))K((h)|(l+3))
#define R(h)F(h<<4,0)F(h<<4,4)F(h<<4,8)F(h<<4,12)
unsigned long crc_table[]={R(0)R(1)R(2)R(3)R(4)R(5)R(6)R(7)R(8)R(9)R(10)R(11)R(12)R(13)R(14)R(15)};

```

Working in reverse, we wind up with an unsigned long array named crc\_table. We can omit the size of the array as the macros will ensure there are exactly 256 elements in the array. We initialize the array with 16 'rows' of data by using 16 invocations of the macro R.

Each invocation of R expands into four fragments (macro F) of four constants (macro K) for a total of 16 'columns' of data.

The macro K is the unrolled loop indexed by k in the code from the original question. It updates the value c eight times by invoking the macro C.

This preprocessor based solution uses quite a bit of memory during macro expansion. I tried to make it a little shorter by having an extra level of macro expansion and my compiler puked. The code above compiles (slowly) with both Visual C++ 2012 and g++ 4.5.3 under Cygwin (Windows 7 64 bit 8GB RAM).

Edit:

The fragment above is 295 bytes including white space. After expanding all of the macros except for C it grows to 9,918 bytes. As each level of C macro is expanded the size grows quickly:

1. 25,182
2. 54,174
3. 109,086
4. 212,766
5. 407,838
6. 773,406
7. 1,455,390
8. 2,721,054

So by the time all the macros have been expanded, that little 295 byte file expands into over 2.7 megabytes of code that must be compiled to generate the original 1024 byte array (assuming 32 bit unsigned long values)!

Another edit:

I modified the C macro based on a macro from another answer to squeeze an extra 11 bytes out, and greatly reduced the full expanded macro size. While 2.7 MB isn't as bad as 54 MB (the previous final size of all macro expansion), it is still significant.
> 3 votes

# Answer
I would modify the previous answer by replacing the last three lines with:

```
#define crc4( x)    crcByte(x), crcByte(x+1), crcByte(x+2), crcByte(x+3)
#define crc16( x)   crc4(x), crc4(x+4), crc4(x+8), crc4(x+12)
#define crc64( x)   crc16(x), crc16(x+16), crc16(x+32), crc16(x+48)
#define crc256( x)  crc64(x), crc64(x+64), crc64(x+128), crc64(x+192)

```

Where crcByte is his K macro without the trailing comma. Then build the table itself with:

```
static const unsigned long crc32Table[256] = { crc256( 0)};

```

And never leave out the size of the array as the compiler will then verify that you have the correct amount of elements.
> 3 votes

---
Tags: code-challenge, c++, compile-time
---


title: Find the next number in the pattern

text:
# Question
Title: Find the next number in the pattern
Write a program, that takes 5 numbers as input and outputs the next number in the pattern.

Heres a text file with 1835 test patterns, containing 6 numbers separated by commas each line. Using the first 5 numbers calculate the 6th number and then check if it matches. You must get all the test cases correct.

There are 3 types of patterns:

1. xn = xn-1+k
2. xn = xn-1\*k
3. xn = xn-1^2

The first x value and k were chosen randomly between a set range to create the pattern sample file.

This is code-golf, lowest number of bytes to get all of the test cases correct wins.

# Answer
## Python 2: 55 bytes

```
f=lambda a,b,c,d,e:e+c-d*2and e*e/d**(d*d==e*c)or e*2-d

```

We check for the three cases as follows:

1. Check for arithmetic sequence: If `e+c==d+d`, output `e+e-d`
2. Check for geometric sequence: If `e*c==d*d`, output `e*e/d`
3. Otherwise, squared sequence: Output `e*e`.

Case 3 is used as the else-case to avoid the more-lengthy checking for successive squaring.

Case 1 is checked first, with Boolean short-circuiting to avoid checking Case 2 after a success, as this causes an error when `d=0`. There's a test case of all zeroes, so we can't cheat this by picking another position in place of `d`.

Afterwards, we can treat both Cases 2 and 3, since there's no risk of a divide-by-0 error. Noting that the choices are similar (`e*e` vs `e*e/d`), we combine them with an arithmetic expression by dividing by either `d**1` for Case 3 or `d**0` for Case 2. Although this division produces an integer value, we must use Python 2 (or `//`) to avoid float errors that case the largest-output test case to fail.

Thanks to @Will for inspiration on the code structure and a very-helpful test framework.
> 4 votes

# Answer
## Python all right, 72 ~~74~~ ~~75~~ chars

```
p=lambda i,j,k,l,m:j-i!=k-j and(k==j*j==j*i*i and m*m or m*l/k)or m+j-i

```

Thx to **xnor** for showing me the `if`/`else` to `and`/`or` trick and golfing off a char :)

Thx to **flornquake** for fixing the `k==j*j==j*i*i` and saving another two chars :)

Actually, it gets one wrong... but that's a bug in the test patterns which was acknowledged yesterday but still not fixed.

Testing code, hopefully useful for all competitors to test with:

```
def check(func,title):
    right = 0
    print "===", title, "==="
    for i,test in enumerate(open('patterns.txt')):
        test = map(int,test.split(','))
        try:
            got, expected = func(*test[:5]), test[5]
        except Exception as e:
            got = e
        if got != expected:
            print "ERROR on line %d: %s != %d" % (i, got, expected)
            print " test :", ", ".join(map(str,test))
            plus = multi = cube = str(test[0])
            for i in range(1, 6):
                plus += ", %d" % (test[i-1]+(test[1]-test[0]))
                multi += ", %s" % ((test[i-1]*(test[1]/test[0])) if test[0] else "DivZero")
                cube += ", %d" % (test[i-1]**2)
            print " as + :", plus
            print " as * :", multi
            print " as ^2:", cube
        else:
            right += 1
    print right, "out of", i+1, "right!"

```

says:

```
ERROR on line 19: 23283064365386962890625 != 3273344365508751233
 test : 5, 25, 625, 390625, 152587890625, 3273344365508751233
 as + : 5, 25, 45, 645, 390645, 152587890645
 as * : 5, 25, 125, 3125, 1953125, 762939453125
 as ^2: 5, 25, 625, 390625, 152587890625, 23283064365386962890625
1834 out of 1835 right!

```
> 3 votes

# Answer
# Python 3 -1833

## Length 198 chars

Now updated to conform to the rules.

```
m=0
for i in open('s'):
 if','in i:
  i,j,k,l=list(map(int,i.split(',')[2:]))
  if j-i==k-j:
   if k+(j-i)==l:m+=1
  elif j/i==k/j:
   if k*(j/i)==l:m+=1
  elif i**2==j:
   if k**2==l:m+=1
print(m)

```
> 2 votes

# Answer
## C# - 1835

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace pattern
{
    class Program
    {
         static void Main(string[] args)
         {
            string[] lines = File.ReadAllLines("in.txt");
            int matches = 0;
            for(int i = 0; i < lines.Length; i++)
            {
                long[] numbers = lines[i].Split(',').Select(a=>long.Parse(a)).ToArray();

                long nextnum = 0;
                if(numbers[1]-numbers[0]==numbers[2]-numbers[1])
                nextnum = numbers[numbers.Length-2]+(numbers[1]-numbers[0]);
            else if(numbers[1]/numbers[0]==numbers[2]/numbers[1])
                nextnum = numbers[numbers.Length-2]*(numbers[1]/numbers[0]);
            else if(numbers[1] == numbers[0]*numbers[0])
                nextnum = numbers[numbers.Length-2]*numbers[numbers.Length-2];
            if(nextnum == numbers[numbers.Length-1])
                matches++;
        }
        Console.WriteLine(matches + " matches found!");
        Console.ReadLine();
    }
}
}

```

This is obviously not golfed at all, but it finds all numbers eventually. It just prints how many matches it found, but you could potentially display all found numbers, only non-matches, etc...

*(This is conceptually very similar to Beta Decay's answer, just a little bit more complicated)*
> 2 votes

# Answer
# TI-BASIC, ~~120~~ ~~117~~ 136

Prompts for input and returns the output.

```
Input L1:0:If not(L1(5:Stop
If L1(5)-L1(4)=L1(4)-L1(3:L1(5)+(L1(5)-L1(4
If L1(5)/L1(4)=L1(4)/L1(3:L1(5)(L1(5)/L1(4
If L1(4)²=L1(5:L1(5)²

```

**Edit:** Fixed divide by zero error.
> 1 votes

---
Tags: code-golf
---


title: Anagramming Code

text:
# Question
Title: Anagramming Code
Let's try this again.

The object of this contest is to make two pieces of code that are anagrams of each other (the two must contain the same bytes in a different order), and they will do the following tasks:

* One must test if an inputted number is happy or prime, and output if the number is either (for example, `7` must output `happy prime` and `4` must output `sad non-prime`).
* The other must output its code size in bytes as a word (a 60-byte program would output `sixty`, a 39-byte program would output `thirty-nine`).

If any clarification is needed on the rules, don't hesitate to tell me.

This is a code golf competition, so shortest program wins!

# Answer
> 6 votes
## CJam, ~~80~~ ~~49~~ 48 characters

**UPDATE** : Inspired by Dennis' implementation to calculate sum of squares of digits, here is a shorter version

Happy/Sad Prime/Non-prime:

```
ri:T{Ab2f#:+}G*X="happy""sad"?STmp4*"non-prime">

```

How it works:

```
ri:T                                "Read input as integer and store it in T"
    {       }G*                     "Run this code block 16 times"
     Ab                             "Convert the number into base 10"
       2f#                          "Calculate square of each digit"
          :+                        "Sum all the squared digits and put the sum on stack"
X=                                  "Compare the sum after 16th iteration to 1"
  "happy""sad"?                     "If sum is 1, put `happy` to stack, otherwise `sad`"
               ST                   "Put space on stack then put the value of T on stack"
                 mp4*               "Put 4 to stack if input is prime, otherwise 0"
                     "non-prime">   "Put `non-prime` to stack and slice out first four characters if the input number is prime"

```

*forTy-eiGhT*

```
""A"forTy-eiGhT""ri:{b2#:+}*X=appsadSmp4*nnpm>"?

```

How this works:

```
""                                  "Push empty string to stack"
  A                                 "Push 10 to stack"
   "forTy-eiGhT"                    "Push `forTy-eiGhT` to stack"
                "ri:....pm>"        "Push this string to stack too"
                            ?       "Keep `forTy-eiGhT` on stack and pop the other string"

```

Try it online

The first program reads the number from STDIN

---

My original 80 character solution

Happy/Sad Prime/Non-prime:

```
r:N{1/~]{i_*T+:T;}/T_s\1=:H!X):XK<&0:T;}g;H"happy""sad"?SNimp"prime"_"non-"\+?:Y

```

*eigHTY*

```
"eigHTY""r:N{1/~]{i_*T+:T}/_s\1=:H!X):XK<&0:T}happysad?SNmp";"prim_";"non-\?:+";

```

# Answer
> 4 votes
# CJam, ~~50~~ 49 bytes

**Happiness and primality test**

```
li_{Ab2f#:+}30*(T="happy""sad"?S@mp4*"non-prime">

```

Reads a number from STDIN. Both tests work only for 64-bit integers.

Try it online.

**Own length**

```
A"forTy-nine""l_{b2#:+}30*(=happsadS@mp4*pim>"?""

```

Prints *forTy-nine*.

# Answer
> 3 votes
## Golfscript - 81

This program tests if a number is happy and/or prime.

```
~.:a;0.{).a\%!@+\}a*;2="""non-"if"prime"@ {`0\{48-.*+}/}9*("sad ""happy "if@@#get

```

This program, an anagram of the last, outputs "eighty-one" (its bytesize as a word).

```
;"eighty-one"#   !""""""""%()***++-..../002489:;=@@@@\\\`aaaaadffiimnppprs{{{}}}~

```

This should serve as an example.

# Answer
> 1 votes
# J - 87 char

A naive attempt at this in J. No use of the standard library, though I doubt it would get any shorter by using that.

```
((sad`happy{~1 e.(,[:+/@:*:,.&.":@{:)^:(1-{:e.}:)^:_);@,' ';'gtv]non-prime'}.~4+4*1&p:)
'((ad`app{~1 .(,[:+/@:*:,.&.":@{:)^:(1-{:.}:)^:_);@, ;onprm}.~4+4*1&p:)']'eighty-seven'
('(ad`app{~1 .(,[:+/@:*:,.&.:@{:)^:(1-{:.}:)^:);@, ;onprm}.~4+4*1&p:']'eighty-seven'"_)

```

The line on the top is a verb taking an integer and diagnosing its happiness and primality as an output string. The second line is an expression returning the string `eighty-seven`, while the third is a constant function doing the same. I included both because they were both possible and because I don't know what the ruling will be on function answers as opposed to program ones, and J doesn't have such a thing as no-argument functions—you just give a function a dummy argument.

We lose most of the chars checking for happiness. `(,[:+/@:*:,.&.":@{:)` is the main body that sums the squares of the digits of a number, and `(1-{:e.}:)` is the test of whether that number has occurred yet. `sad`happy{~1 e.` turns this into a word result, and we attach that to the front of the string `non-prime`, potentially snipping off four characters if the number was actually prime.

In the anagram we just hide all the bits that aren't `'eighty-seven'` in a string that we ignore. I could do better if J had more letters to reuse, but it doesn't, so oh well.

---
Tags: code-golf, math, primes, source-layout
---


# Question
Title: String Bit Manipulation- There and Back Again
Your job is to encrypt a string using a number key.

Your program will receive 2 strings: one containing a sequence of characters to encrypt, and another one containing an even amount of digits (`1`-`9`, never `0`).

The encrypting will work like this:

1. take the string to be encrypt and decode it to binary (ISO-8859-1)
2. for every pair of numbers `x` and `y` in the number string do: for every character in the string of zeroes and ones, starting from the first one, if the bit is `0` toggle the `x`th bit in front of the bit you are reading right now. If the bit is `1`, toggle the `y`th bit in front of the bit you are reading right now. If the bit to be toggled is out of bounds, do not toggle anything.

Other than that:

This is a code golf challenge, shortest code wins. Standard Loopholes apply.

Here's a more graphic explanation of what happens:

```
inputs: "a", "23"
"a" =BIN> "01100001"
"01100001" //first bit is a 0, get the first number in the key, 2.
 - ^       //toggle the bit 2 steps in front
"01000001" //next bit is 1, get second number in the key, 3.
  -  ^     //toggle the bit 3 steps in front
"01001001" //0 bit, toggle the bit that is 2 steps in front.
   - ^
"01000001" //etc
    - ^
"01000101"
     - ^
"01000111"
      -  ^ //no change, out of bounds.
"01000111"
       -  ^
"01000111"
        -  ^
"01000111" =ASCII> "G"

```

So: `a`, `23` = `G`. ~~Then, running `G`, `23` should be `a` because this process is perfectly reversible.~~ To decrypt a string encrypted using key `12438135`, reverse the ordering of the pairs, `35814312` and run the encrypted string through a similar program that performs the operations in reverse order (starting at the end, approaching the beginning) using that key. (thanks to Martin Büttner for pointing that out)

Good luck and have fun! (My first challenge, tell me if i missed anything :))

# Answer
# CJam, 53 bytes

```
SSl++256b2bl2/{Em<_,E-{_0=P=~_2$=!t1m<}*}fPE>2b256b:c

```

Reads two lines of input: the string, followed by the key.

Try it online.

For decryption, this code can be used:

```
SSl++256b2bl2/W%{1m>_,E-{_0=P=~_2$=!t1m>}*Dm>}fPE>2b256b:c

```

### Example run

```
$ LANG=en_US cjam enc.cjam # First two lines are input.
codegolf
345678
q¼M³)6¯J

```

### How it works

CJam's built-in base conversion discards leading zeros, so we start by prepending two spaces to the input string. Since a space character is `[0 0 1 0 0 0 0 0]`, this prepends 14 zeros to the bit encoding for the input string.

After each transformation, we rotate the array to the left to avoid adding indexes, skipping the extra 14 bytes from the spaces. This way, toggling bits "out of bounds" affects only those 14 bits, which are discarded after the last toggle.

```
SSl++       " Read one line of input (plaintext) and prepend two spaces. ";
256b2b      " String ↦ byte array ↦ bit array. ";
l2/         " Read one line of input (key) and split it in chunks of length 2. ";
{           " For each digit pair P: ";
  Em<       " Rotate the array 14 places to the left. ";
  _,E-      " Push the arrays length minus 14. ";
  {         " Do the following that many times: ";
    _0=P=~  " Push the digit of P that corresponds to the first bit of the array. ";
    _2$=    " Retrieve the corresponding bit from the array. ";
    !t      " Compute its logical NOT and modify the array at the given position. ";
    1m<     " Rotate the array one place to the left. ";
  }*        " ";
}fP         " ";
E>          " Discard the first 14 bits of the array. ";
2b256b:c    " Bit array ↦ byte array ↦ string. ";

```
> 1 votes

# Answer
## Ruby, ~~230~~ ~~191~~ ~~181~~ ~~178~~ ~~175~~ ~~173~~ ~~171~~ 159 bytes

```
i,n=$*
s=i.gsub(/./){|c|"%08b"%c.ord}
n.scan(/(.)(.)/){s.size.times{|i|s[j=i+(s[i]==?0?$1:$2).to_i]&&s[j]=s[j]==?0??1:?0}}
$><<s.gsub(/.{8}/){|c|c.to_i(2).chr}

```

It's just a very naive implementation of the spec. Input via command-line arguments, output to STDOUT.

```
# Read ARGV into i and n
i,n = $*
# Turn each character into a string of eight 0s and 1s using a format string.
s = i.gsub(/./){|c|"%08b"%c.ord}
# For each pair of characters in n
n.scan(/(.)(.)/){
    # For each index into s
    s.size.times{|i|
        # Determine the index that is to be toggled. $1 and $2 refer to the captures
        # of /(.)(.)/.
        j=i+(s[i]==?0?$1:$2).to_i
        # Using short-circuiting, toggle s[j] if it isn't nil.
        s[j]&&s[j]=s[j]==?0??1:?0
    }
}
# Convert each group of 8 characters back to a single character and print
$><<s.gsub(/.{8}/){|c|c.to_i(2).chr}

```
> 3 votes

# Answer
# GolfScript, 45

```
~2/{\{8{(..2\?3$&!!4$=48-- 2\?@\^\.}do;}%\;}/

```

This takes arguments from stdin in the form of two strings (e.g. "a""23") and outputs to stdout.

Test it online here
> 0 votes

# Answer
# JavaScript 243

```
function E(s,k,d){for (var o="",a=0,b=0;a<s.length;a++,b%=k.length){
var j,i=8,z,n=s.charCodeAt(a),x=parseInt(k.charAt(b++)),y=parseInt(k.charAt(b++))
for (;i--;)j=d?7-i:i,z=j-(n&(1<<j)?y:x),n=z>0?n^=1<<z:n
o+=String.fromCharCode(n)
}return o}

```

Example:

```
var s0 = "codegolf";
var k = "5556";
var s1 = E(s0,k);
var s2 = E(s1,k,true);
console.log(s0+"\n"+s1+"\n"+s2)

```

Output:

```
codegolf
ekbaakjb
codegolf

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Rosetta Stone Challenge: Run-Length Encoding v2.0
The goal of a Rosetta Stone Challenge is to write solutions in as many languages as possible. Show off your programming multilingualism!

## The Challenge

We've done run-length encoding before but only considered runs of a single character. Of course, we can sometimes make even greater savings if we consider runs of multiple characters.

Take `aaaxyzxyzxyzdddd` for instance. This can be compressed to `3a3{xyz}4d`. Your task is to write a program of function which, given a case-sensitive string of letters and spaces, compresses it *optimally* using run-length encoding for multi-character runs.

You may take input via function argument, STDIN or ARGV and return the result or print it to STDOUT.

Runs must not be nested, so `aaabbbaaabbb` must be `3a3b3a3b`, *not* `2{3a3b}`. I.e. the string should be encoded (or decoded) in a single pass.

### Consequences of Optimal Compression

Some examples where naive application of run-length encoding might lead to suboptimal results:

* `abab` must not be "compressed" to `2{ab}`
* `aaaabcdeabcde` must not be compressed to `4abcdeabcde` but `3a2{abcde}` instead.

If there are two optimal versions (e.g. `aa` and `2a` or `abcabc` and `2{abc}`) either result is fine.

### Examples

```
Input              Output

aa                 aa -or- 2a
aaaaaAAAAA         5a5A
ababa              ababa
abababa            a3{ba} -or- 3{ab}a
foo foo bar        2{foo }bar
aaaabcdeabcde      3a2{abcde}
xYzxYz             xYzxYz -or- 2{xYz}
abcabcdefcdef      abcab2{cdef}
pppqqqpppqqq       3p3q3p3q
pppqqqpppqqqpppqqq 3{pppqqq}

```

## Scoring

Each language is a separate competition as to who can write the shortest entry, but the overall winner would be the person who wins the most of these sub-competitions. This means that a person who answers in many uncommon languages can gain an advantage. Code golf is mostly a tiebreaker for when there is more than one solution in a language: the person with the shortest program gets credit for that language.

If there is a tie, the winner would be the person with the most second-place submissions (and so on).

## Rules, Restrictions, and Notes

Please keep all of your different submissions contained within a single answer.

Also, no shenanigans with basically the same answer in slightly different language dialects. I will be the judge as to what submissions are different enough.

## Current Leaderboard

This section will be periodically updated to show the number of languages and who is leading in each.

* C# (265) — edc65
* JavaScript (206) — edc65
* Python (214) — Will
* VB.NET (346) — edc65

## Current User Rankings

1. edc65 (3)
2. Will (1)

# Answer
> 1 votes
# JavaScript (E6) 206

Almost sure it is optimal. I start trying to encode the longest string with the max gain, and recursively encode what remains at left and right. After each try I keep the shortest result.

Golf notes (JS specific)

* Pseudo arguments instead of locals (for recursion)
* Compare lengths using out of bounds index that gives 'undefined'

```
R=(s,n=s,d=s.length>>1,w,i,j,c)=>{
  for(;d;--d){
    for(i=-1;s[d+d+i++];){
      w=s.slice(i,j=i+d);
      for(r=1;w==s.substr(j,d);j+=d)++r;
      c=d>1?r+'{'+w+'}':r+w,
      // c[d*r-1]|| /* uncomment this line (+10 bytes) to have faster response
      n[(c=R(s.slice(0,i))+c+R(s.slice(j))).length]&&(n=c)
    }
  }
  return n
}

```

**Test** In FireFox/FireBug console

```
;['aa','aaaaaAAAAA','ababa','abababa','foo foo bar', 'aaaabcdeabcde',
  'xYzxYz', 'abcabcdefcdef', 'pppqqqpppqqq','pppqqqpppqqqpppqqq']
.forEach(x=>console.log(x+' -> '+R(x)))

```

*Output*

```
aa -> aa
aaaaaAAAAA -> 5a5A
ababa -> ababa
abababa -> 3{ab}a
foo foo bar -> 2{foo }bar
aaaabcdeabcde -> 3a2{abcde}
xYzxYz -> xYzxYz
abcabcdefcdef -> abcab2{cdef}
pppqqqpppqqq -> 3p3q3p3q
pppqqqpppqqqpppqqq -> 3{pppqqq}

```

# C# (.NET 4.0) 265

Exactly the same algorithm

```
string R(string s)
{
  string n=s,c,w;
  int l=s.Length,d=l/2,i,j,r;
  for(;d>0;--d)
  {
    for(i=0;d+d+i<=l;i++)
    {
      w=s.Substring(i,d);
      for(j=i+d,r=1;j+d<=l&&w==s.Substring(j,d);j+=d)++r;
      c=d>1?r+"{"+w+"}":r+w;
      // if(c.Length<d*r){ // uncomment this line for faster execution
        c=R(s.Substring(0,i))+c+R(s.Substring(j));
        n=c.Length<n.Length?c:n;
      //} // and this one of course
    }
  }
  return n;
}

```

**Test** in LinqPad, mode 'C# program', add a main after the R function

```
void Main()
{
  string[] test = {"aa","aaaaaAAAAA","ababa","abababa","foo foo bar","aaaabcdeabcde",
  "xYzxYz","abcabcdefcdef","pppqqqpppqqq","pppqqqpppqqqpppqqq"};
  test.Select(x => new { x, r=R(x) }).Dump("Result");
}

```

Same Output

# VB.Net (.NET 4) 346 (probably)

Same algorithm and same library, but the language is different enough

I can't be sure about byte count, as Visual Studio keep reformatting the code and adding spaces.

Golf notes: better use something else

```
function R(s as string)

  dim n=s,c,w
  dim l=s.Length,i,j,d
  for d=l\2 to 1 step-1
    for i=0 to l-d-d
      w=s.Substring(i,d)
      j=i+d
      r=1
      do while (j+d<=l andalso w=s.Substring(j,d))
        r=r+1
        j=j+d
      loop
      c=if(d>1,r & "{" & w & "}",r & w)
      if(c.Length<d*r) then
        c=R(s.Substring(0,i))+c+R(s.Substring(j))
        if c.Length<n.Length then n=c
      end if
    next
  next
  return n

end function

```

# Answer
> 3 votes
## Python 214

```
def t(s):
 b=s;l=len;r=range(1,l(s))
 for i in r:
  p=s[:i];b=min(b,p+t(s[i:]),key=l);x=1
  for j in r:k=i*j+i;x*=p==s[i*j:k];b=min(b,(b,''.join((`j+1`,"{"[i<2:],p,"}"[i<2:],t(s[k:]))))[x],key=l)
 return b

```

(second level indent is tab)

As this is , this is the naive recursive approach without early-exit, so its really really slow.

---
Tags: code-golf, string, compression, rosetta-stone
---


title: False Positives on an Integer Lattice

text:
# Question
Title: False Positives on an Integer Lattice
## Leaderboard

```
 User            Language      Score
 =========================================
 Ell             C++11         293,619,555
 feersum         C++11         100,993,667
 Ell             C++11          78,824,732
 Geobits         Java           27,817,255
 Ell             Python         27,797,402
 Peter Taylor    Java                2,468
 <reference>     Julia                 530

```

## Background

When working on a 2-D grid of integer coordinates, you sometimes want to know whether two vectors (with integer components) have the same magnitude. Of course, in Euclidean geometry the magnitude of a vector `(x,y)` is given by

```
√(x² + y²)

```

So a naive implementation might compute this value for both vectors and compare the results. Not only does that incur an unnecessary square root computation, it also causes trouble with floating point inaccuracies, which might yield false positives: vectors whose magnitudes are different, but where the significant digits in the floating point representation are all identical.

For the purposes of this challenge, we define a **false positive** as a pair of coordinate pairs `(a,b)` and `(c,d)` for which:

* Their squared magnitude is different when represented as 64-bit unsigned integers.
* Their magnitude is identical when represented as 64-bit binary floating point number and computed via a 64-bit square root (as per IEEE 754).

As an example, using 16-bit representations (instead of 64), the smallest1 pair of vectors which yields a false positive is

```
(25,20) and (32,0)

```

Their squared squared magnitudes are `1025` and `1024`. Taking the square root yields

```
32.01562118716424 and 32.0

```

But in 16-bit floats both of these get truncated to `32.0`.

Likewise, the smallest2 pair yielding a false positive for 32-bit representations is

```
(1659,1220) and (1951,659)

```

 1"Smallest" as measured by their 16-bit floating point magnitude.
2"Smallest" as measured by their 32-bit floating point magnitude.

Lastly, here are a handful of valid 64-bit cases:

```
 (51594363,51594339) and (54792160,48184783)
 (54356775,54353746) and (54620742,54088476)
 (54197313,46971217) and (51758889,49645356)
 (67102042,  956863) and (67108864,       6) *

```

`*` The last case is one of several with the smallest possible magnitude for 64-bit false positives.

## The Challenge

In less than 10,000 bytes of code, using a single thread, you're to find as many false positives for **64-bit (binary) floating point numbers** in the coordinate range `0 ≤ y ≤ x` (that is, only within the first octant of the Euclidian plane) such that `x² + y² ≤ 2<sup>53</sup>` within **10 minutes**. If two submissions tie for the same number of pairs, the tie breaker is the actual time taken to find the last of those pairs.

Your program must not use more than **4 GB** of memory at any time (for practical reasons).

It must be possible to run your program in two modes: one which outputs every pair as it finds it, and one which only outputs the number of found pairs at the end. The first will be used to verify the validity of your pairs (by looking at some sample of outputs) and the second will be used for actually timing your submission. Note that the printing must be the *only* difference. In particular, the counting program may not hardcode the number of pairs it *could* find. It must still perform the same loop that would be used to print all the numbers, and only omit the printing itself!

I will test all submissions on my Windows 8 laptop, so please ask in the comments if you want to use some not-too-common language.

Note that pairs must *not* be counted twice under switching of the first and second coordinate pair.

Note also that I will run your process via a Ruby controller, which will kill your process if it hasn't finished after 10 minutes. Make sure to output the number of pairs found by then. You can either keep track of time yourself and print the result just before the 10 minutes elapse, or you just output the number of pairs found sporadically, and I will take the last such number as your score.

# Answer
## C++, 275,000,000+

We'll refer to pairs whose magnitude is accurately representable, such as *(x, 0)*, as *honest pairs* and to all other pairs as *dishonest pairs* of magnitude *m*, where *m* is the pair's wrongly-reported magnitude. The first program in the previous post used a set of tightly related couples of honest- and dishonest-pairs:
*(x, 0)* and *(x, 1)*, respectively, for large enough *x*. The second program used the same set of dishonest pairs but extended the set of honest pairs by looking for all honest pairs of integral magnitude. The program doesn't terminate within ten minutes, but it finds the vast majority of its results very early on, which means that most of the runtime goes to waste. Instead of keep looking for ever-less-frequent honest pairs, this program uses the spare time to do the next logical thing: extending the set of *dishonest* pairs.

From the previous post we know that for all large-enough integers *r*, *sqrt(r2 \+ 1) = r*, where *sqrt* is the floating-point square root function. Our plan of attack is to find pairs *P = (x, y)* such that *x2 \+ y2 = r2 \+ 1* for some large-enough integer *r*. That's simple enough to do, but naively looking for individual such pairs is too slow to be interesting. We want to find these pairs in bulk, just like we did for honest pairs in the previous program.

Let *{**v**, **w**}* be an orthonormal pair of vectors. For all real scalars *r*, *||r **v** \+ **w**||2 = r2 \+ 1*. In *2*, this is a direct result of the Pythagorean theorem:

We're looking for vectors ***v*** and ***w*** such that there exists an *integer* *r* for which *x* and *y* are also integers. As a side note, note that the set of dishonest pairs we used in the previous two programs was simply a special case of this, where *{**v**, **w**}* was the standard basis of *2*; this time we wish to find a more general solution. This is where Pythagorean triplets (integers triplets *(a, b, c)* satisfying *a2 \+ b2 = c2*, which we used in the previous program) make their comeback.

Let *(a, b, c)* be a Pythagorean triplet. The vectors ***v*** *= (b/c, a/c)* and ***w*** *= (-a/c, b/c)* (and also
***w*** *= (a/c, -b/c)*) are orthonormal, as is easy to verify. As it turns out, for any choice of Pythagorean triplet, there exists an integer *r* such that *x* and *y* are integers. To prove this, and to effectively find *r* and *P*, we need a little number/group theory; I'm going to spare the details. Either way, suppose we have our integral *r*, *x* and *y*. We're still short of a few things: we need *r* to be large enough and we want a fast method to derive many more similar pairs from this one. Fortunately, there's a simple way to accomplish this.

Note that the projection of *P* onto ***v*** is *r **v***, hence *r = P **·** **v** = (x, y) **·** (b/c, a/c) = xb/c + ya/c*, all this to say that *xb + ya = rc*. As a result, for all integers *n*, *(x + bn)2 \+ (y + an)2 = (x2 \+ y2) + 2(xb + ya)n + (a2 \+ b2)n2 = (r2 \+ 1) + 2(rc)n + (c2)n2 = (r + cn)2 \+ 1*. In other words, the squared magnitude of pairs of the form
*(x + bn, y + an)* is *(r + cn)2 \+ 1*, which is exactly the kind of pairs we're looking for! For large enough *n*, these are dishonest pairs of magnitude *r + cn*.

It's always nice to look at a concrete example. If we take the Pythagorean triplet *(3, 4, 5)*, then at *r = 2* we have *P = (1, 2)* (you can check that *(1, 2) **·** (4/5, 3/5) = 2* and, clearly, *12 \+ 22 = 22 \+ 1*.) Adding *5* to *r* and *(4, 3)* to *P* takes us to *r' = 2 + 5 = 7* and *P' = (1 + 4, 2 + 3) = (5, 5)*. Lo and behold, *52 \+ 52 = 72 \+ 1*. The next coordinates are *r'' = 12* and *P'' = (9, 8)*, and again, *92 \+ 82 = 122 \+ 1*, and so on, and so on ...

Once *r* is large enough, we start getting dishonest pairs with magnitude increments of *5*. That's roughly *27,797,402 / 5* dishonest pairs.

So now we have plenty of integral-magnitude dishonest pairs. We can easily couple them with the honest pairs of the first program to form false-positives, and with due care we can also use the honest pairs of the second program. This is basically what this program does. Like the previous program, it too finds most of its results very early on---it gets to 200,000,000 false positives within a few seconds---and then slows down considerably.

Compile with `g++ flspos.cpp -oflspos -std=c++11 -msse2 -mfpmath=sse -O3`. To verify the results, add `-DVERIFY` (this will be notably slower.)

Run with `flspos`. Any command-line argument for verbose mode.

```
#include <cstdio>
#define _USE_MATH_DEFINES
#undef __STRICT_ANSI__
#include <cmath>
#include <cfloat>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

/* Make sure we actually work with 64-bit precision */
#if defined(VERIFY) && FLT_EVAL_METHOD != 0 && FLT_EVAL_METHOD != 1
#   error "invalid FLT_EVAL_METHOD (did you forget `-msse2 -mfpmath=sse'?)"
#endif

template <typename T> struct widen;
template <> struct widen<int> { typedef long long type; };

template <typename T>
inline typename widen<T>::type mul(T x, T y) {
    return typename widen<T>::type(x) * typename widen<T>::type(y);
}
template <typename T> inline T div_ceil(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline typename widen<T>::type sq(T x) { return mul(x, x); }
template <typename T>
T gcd(T a, T b) { while (b) { T t = a; a = b; b = t % b; } return a; }
template <typename T>
inline typename widen<T>::type lcm(T a, T b) { return mul(a, b) / gcd(a, b); }
template <typename T>
T div_mod_n(T a, T b, T n) {
    if (b == 0) return a == 0 ? 0 : -1;
    const T n_over_b = n / b, n_mod_b = n % b;
    for (T m = 0; m < n; m += n_over_b + 1) {
        if (a % b == 0) return m + a / b;
        a -= b - n_mod_b;
        if (a < 0) a += n;
    }
    return -1;
}

template <typename T> struct pythagorean_triplet { T a, b, c; };
template <typename T>
struct pythagorean_triplet_generator {
    typedef pythagorean_triplet<T> result_type;
private:
    typedef typename widen<T>::type WT;
    result_type p_triplet;
    WT p_c2b2;
public:
    pythagorean_triplet_generator(const result_type& triplet = {3, 4, 5}) :
        p_triplet(triplet), p_c2b2(sq(triplet.c) - sq(triplet.b))
    {}
    const result_type& operator*() const { return p_triplet; }
    const result_type* operator->() const { return &p_triplet; }
    pythagorean_triplet_generator& operator++() {
        do {
            if (++p_triplet.b == p_triplet.c) {
                ++p_triplet.c;
                p_triplet.b = ceil(p_triplet.c * M_SQRT1_2);
                p_c2b2 = sq(p_triplet.c) - sq(p_triplet.b);
            } else
                p_c2b2 -= 2 * p_triplet.b - 1;
            p_triplet.a = sqrt(p_c2b2);
        } while (sq(p_triplet.a) != p_c2b2 || gcd(p_triplet.b, p_triplet.a) != 1);
        return *this;
    }
    result_type operator()() { result_type t = **this; ++*this; return t; }
};

int main(int argc, const char* argv[]) {
    const bool verbose = argc > 1;

    const int min = 1 << 26;
    const int max = sqrt(1ll << 53);

    const size_t small_triplet_count = 1000;
    vector<pythagorean_triplet<int>> small_triplets;
    small_triplets.reserve(small_triplet_count);
    generate_n(
        back_inserter(small_triplets),
        small_triplet_count,
        pythagorean_triplet_generator<int>()
    );

    int found = 0;
    auto add = [&] (int x1, int y1, int x2, int y2) {
#ifdef VERIFY
        auto n1 = sq(x1) + sq(y1), n2 = sq(x2) + sq(y2);
        if (x1 < y1 || x2 < y2 || x1 > max || x2 > max ||
            n1 == n2 || sqrt(n1) != sqrt(n2)
        ) {
            fprintf(stderr, "Wrong false-positive: (%d, %d) (%d, %d)\n",
                    x1, y1, x2, y2);
            return;
        }
#endif
        if (verbose) printf("(%d, %d) (%d, %d)\n", x1, y1, x2, y2);
        ++found;
    };

    int output_counter = 0;
    for (int x = min; x <= max; ++x) add(x, 0,    x, 1);
    for (pythagorean_triplet_generator<int> i; i->c <= max; ++i) {
        const auto& t1 = *i;

        for (int n = div_ceil(min, t1.c); n <= max / t1.c; ++n)
            add(n * t1.b, n * t1.a,    n * t1.c, 1);

        auto find_false_positives = [&] (int r, int x, int y) {
            {
                int n = div_ceil(min - r, t1.c);
                int min_r = r + n * t1.c;
                int max_n = n + (max - min_r) / t1.c;
                for (; n <= max_n; ++n)
                    add(r + n * t1.c, 0,    x + n * t1.b, y + n * t1.a);
            }
            for (const auto t2 : small_triplets) {
                int m = div_mod_n((t2.c - r % t2.c) % t2.c, t1.c % t2.c, t2.c);
                if (m < 0) continue;
                int sr = r + m * t1.c;
                int c = lcm(t1.c, t2.c);
                int min_n = div_ceil(min - sr, c);
                int min_r = sr + min_n * c;
                if (min_r > max) continue;
                int x1 = x + m * t1.b, y1 = y + m * t1.a;
                int x2 = t2.b * (sr / t2.c), y2 = t2.a * (sr / t2.c);
                int a1 = t1.a * (c / t1.c), b1 = t1.b * (c / t1.c);
                int a2 = t2.a * (c / t2.c), b2 = t2.b * (c / t2.c);
                int max_n = min_n + (max - min_r) / c;
                int max_r = sr + max_n * c;
                for (int n = min_n; n <= max_n; ++n) {
                    add(
                        x2 + n * b2, y2 + n * a2,
                        x1 + n * b1, y1 + n * a1
                    );
                }
            }
        };
        {
            int m = div_mod_n((t1.a - t1.c % t1.a) % t1.a, t1.b % t1.a, t1.a);
            find_false_positives(
                /* r = */ (mul(m, t1.c) + t1.b) / t1.a,
                /* x = */ (mul(m, t1.b) + t1.c) / t1.a,
                /* y = */ m
            );
        } {
            int m = div_mod_n((t1.b - t1.c % t1.b) % t1.b, t1.a, t1.b);
            find_false_positives(
                /* r = */ (mul(m, t1.c) + t1.a) / t1.b,
                /* x = */ m,
                /* y = */ (mul(m, t1.a) + t1.c) / t1.b
            );
        }

        if (output_counter++ % 50 == 0)
            printf("%d\n", found), fflush(stdout);
    }
    printf("%d\n", found);
}

```
> 6 votes

# Answer
## Python, 27,797,402

Just to set the bar a little higher...

```
from sys import argv
verbose = len(argv) > 1
found = 0
for x in xrange(67108864, 94906266):
    found += 1
    if verbose:
        print "(%d, 0) (%d, 1)" % (x, x)
print found

```

It's easy to verify that for all *67,108,864 \<= x \<= 94,906,265 = floor(sqrt(253))* the pairs *(x, 0)* and *(x, 1)* are false positives.

**Why it works**: *67,108,864 = 226*. Therfore, all numbers *x* in the above range are of the form *226 \+ x'* for some *0 \<= x' \< 226*. For all positive *e*, *(x + e)2 = x2 \+ 2xe + e2 = x2 \+ 227e + 2x'e + e2*. If we want to have
*(x + e)2 = x2 \+ 1* we need at least *227e \<= 1*, that is, *e \<= 2-27* However, since the mantissa of double-precision floating point numbers is 52-bit wide, the smallest *e* such that *x + e \> x* is *e = 226 - 52 = 2-26*. In other words, the smallest representable number greater than *x* is *x + 2-26* while the result of *sqrt(x2 \+ 1)* is at most *x + 2-27*. Since the default IEEE-754 rounding mode is round-to-nearest; ties-to-even, it will always round to *x* and never to *x + 2-26* (where the tie-break is really only relevant for *x = 67,108,864*, if at all. Any larger number will round to *x* regardless).

---

## C++, 75,000,000+

Recall that *32 \+ 42 = 52*. What this means is that the point *(4, 3)* lies on the circle of radius *5* centered around the origin. Actually, for all integers *n*, *(4n, 3n)* lies on such circle of radius *5n*. For large enough *n* (namely, such that *5n \>= 226*), we already know a false-positive for all points on this circle: *(5n, 1)*. Great! That's another *27,797,402 / 5* free false-positive pairs right there! But why stop here? *(3, 4, 5)* is not the only such triplet.

This program looks for all positive integer triplets *(a, b, c)* such that *a2 \+ b2 = c2*, and counts false-positives in this fashion. It gets to *70,000,000* false-positives pretty fast but then slows down considerably as the numbers grow.

Compile with `g++ flspos.cpp -oflspos -std=c++11 -msse2 -mfpmath=sse -O3`. To verify the results, add `-DVERIFY` (this will be notably slower.)

Run with `flspos`. Any command-line argument for verbose mode.

```
#include <cstdio>
#include <cmath>
#include <cfloat>

using namespace std;

/* Make sure we actually work with 64-bit precision */
#if defined(VERIFY) && FLT_EVAL_METHOD != 0 && FLT_EVAL_METHOD != 1
#   error "invalid FLT_EVAL_METHOD (did you forget `-msse2 -mfpmath=sse'?)"
#endif

template <typename T> inline long long sqr(T x) { return 1ll * x * x; }
template <typename T>
T gcd(T a, T b) { while (b) { T t = a; a = b; b = t % b; } return a; }

int main(int argc, const char* argv[]) {
    const bool verbose = argc > 1;

    const int min = 1 << 26;
    const int max = sqrt(1ll << 53);

    int found = 0;
    auto add = [=, &found] (int x1, int y1, int x2, int y2) {
#ifdef VERIFY
        auto n1 = sqr(x1) + sqr(y1), n2 = sqr(x2) + sqr(y2);
        if (n1 == n2 || sqrt(n1) != sqrt(n2)) {
            fprintf(stderr, "Wrong false-positive: (%d, %d) (%d, %d)\n",
                    x1, y1, x2, y2);
            return;
        }
#endif
        if (verbose) printf("(%d, %d) (%d, %d)\n", x1, x2, y1, y2);
        ++found;
    };

    for (int x = min; x <= max; ++x) add(x, 0,    x, 1);

    for (int a = 1; a < max; ++a) {
        auto a2b2 = sqr(a) + 1;
        for (int b = 1; b <= a; a2b2 += 2 * b + 1, ++b) {
            int c = sqrt(a2b2);
            if (a2b2 == sqr(c) && gcd(a, b) == 1) {
                int max_c = max / c;
                for (int n = (min + c - 1) / c; n <= max_c; ++n)
                    add(n * a, n * b,    n * c, 1);
            }
        }

        if (a % 512 == 0) printf("%d\n", found), fflush(stdout);
    }

    printf("%d\n", found);
}

```
> 8 votes

# Answer
# C++11 - 100,993,667

### EDIT: New program.

The old one used too much memory. This one halves the memory usage by using a giant vector array instead of a hash table. Also it removes the random thread cruft.

```
   /* by feersum  2014/9
   http://codegolf.stackexchange.com/questions/37627/false-positives-on-an-integer-lattice */
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <vector>
using namespace std;
#define ul unsigned long long

#define K const

#define INS(A)   { bool already = false; \
    for(auto e = res[A.p[0][0]].end(), it = res[A.p[0][0]].begin(); it != e; ++it) \
        if(A.p[0][1] == it->y1 && A.p[1][0] == it->x2 && A.p[1][1] == it->y2) { \
            already = true; \
            break; } \
    if(!already) res[A.p[0][0]].push_back( {A.p[0][1], A.p[1][0], A.p[1][1]} ), ++n; }

#define XMAXMIN (1<<26)

struct ints3 {
    int y1, x2, y2;
};

struct pparm {
    int a,b,c,d;
    int E[4];
    pparm(int A,int B,int C, int D):
        E{B*B+D*D,A*B+C*D,A*A+C*C+2*(B+D),A+C}
    {
        a=A;b=B;c=C;d=D;
    }

};

struct ans {
    int p[2][2];

};
ostream&operator<<(ostream&o, ans&a)
{
    o<<'('<<a.p[0][0]<<','<<a.p[0][1]<<"),("<<a.p[1][0]<<','<<a.p[1][1]<<')'<<endl;
    return o;
}

vector<ints3> res[XMAXMIN];

bool print;
int n;

void gen(K pparm&p1, K pparm&p2)
{
#ifdef DBUG
    for(int i=0;i<2;i++){
    K pparm&p=i?p2:p1;
    cout<<' '<<p.a<<' '<<p.b<<' '<<p.c<<' '<<p.d<<' ';}
    cout<<endl;
#endif

    for(ul x = 0; ; ++x) {
        ans a;
        ul s[2];
        for(int i = 0; i < 2; i++) {
            K pparm &p = i?p2:p1;
            int *pt = a.p[i];
            pt[0] = p.b+x*(p.a+x);
            pt[1] = p.d+x*(p.c+x);
            s[i] = (ul)pt[0]*pt[0] + (ul)pt[1]*pt[1];
        }
        if(*s >> 53)
            break;
if(s[1] - s[0] != 1)
exit(4);

        if(sqrt(s[0]) == sqrt(s[1])) {
             for(int i = 0; i < 2; i++)
                if(a.p[i][0] > a.p[i][1])
                    swap(a.p[i][0], a.p[i][1]);
            if(a.p[0][0] > a.p[0][1])
                for(int i = 0; i < 2; i++)
                    swap(a.p[0][i], a.p[1][i]);
            INS(a)
        }
    }
}

int main(int ac, char**av)
{
    for(int i = 1; i < ac; i++) {
        print |= !strcmp(av[1], "-P");
    }

    #define JMAX 43000000
    for(ul j = 0; j < JMAX; j++) {
        pparm p1(-~j,j,~-j,0),p2(j,1,j,j);
        gen(p1,p2);
        if(!print && !(j%1024))
#ifdef DBUG
            cout<<j<<' ',
#endif
            cout<<n<<endl;

    }
    if(print)
        for(vector<ints3>& v: res)
            for(ints3& i: v)
                printf("(%d,%d),(%d,%d)\n", &v - res, i.y1, i.x2, i.y2);

    return 0;
}

```

Run with a `-P` argument to print out the points instead of the number thereof.

For me it takes under 2 minutes in the counting mode and about 5 minutes with printing directed to a file (~4 GB), so it did not quite become I/O limited.

My original program was neat, but I dropped most of it since it only could produce on the order of 10^5 results. What it did is to look for parameterizations of the form (x^2+Ax+B, x^2+Cx+D), (x^2+ax+b, x^2+cx+d) such that for any x, (x^2+Ax+B)^2 + (x^2+Cx+D)^2 = (x^2+ax+b)^2 + (x^2+cx+d)^2 + 1. When it found such a set of parameters {a,b,c,d,A,B,C,D} it proceeded to check all of the x values under the maximum. While looking at my debug output from this program, I noticed a certain parameterization of the parameterization of the parameterization that allowed me to produce a lot of numbers easily. I elected not to print out Ell's numbers since I had plenty of my own. Hopefully now someone won't print out both of our sets of numbers and claim to be the winner :)

```
 /* by feersum  2014/9
   http://codegolf.stackexchange.com/questions/37627/false-positives-on-an-integer-lattice */
    #include <iostream>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <functional>
    #include <unordered_set>
    #include <thread>
using namespace std;
#define ul unsigned long long

#define h(S) unordered_##S##set
#define P 2977953206964783763LL
#define K const

#define EQ(T, F)bool operator==(K T&o)K{return!memcmp(F,o.F,sizeof(F));}

struct pparm {
    int a,b,c,d;
    int E[4];
    pparm(int A,int B,int C, int D):
        E{B*B+D*D,A*B+C*D,A*A+C*C+2*(B+D),A+C}
    {
        a=A;b=B;c=C;d=D;
    }
    EQ(pparm,E)
};

struct ans {
    int p[2][2];
    EQ(ans,p)
};
ostream&operator<<(ostream&o, ans&a)
{
    o<<'('<<a.p[0][0]<<','<<a.p[0][1]<<"),("<<a.p[1][0]<<','<<a.p[1][1]<<')'<<endl;
    return o;
}

#define HASH(N,T,F) \
struct N { \
    size_t operator() (K T&p) K { \
        size_t h = 0; \
        for(int i = 4; i--; ) \
            h=h*P+((int*)p.F)[i]; \
        return h; \
    }};

#define INS(r, a) { \
    bool new1 = r.insert(a).second; \
    n += new1; \
    if(print && new1) \
        cout<<a; }

HASH(HA,ans,p)

bool print;
int n;

void gen(h()<ans,HA>&r, K pparm&p1, K pparm&p2)
{
#ifdef DBUG
    for(int i=0;i<2;i++){
    K pparm&p=i?p2:p1;
    cout<<' '<<p.a<<' '<<p.b<<' '<<p.c<<' '<<p.d<<' ';}
    cout<<endl;
#endif

    for(ul x = 0; ; ++x) {
        ans a;
        ul s[2];
        for(int i = 0; i < 2; i++) {
            K pparm &p = i?p2:p1;
            int *pt = a.p[i];
            pt[0] = p.b+x*(p.a+x);
            pt[1] = p.d+x*(p.c+x);
            s[i] = (ul)pt[0]*pt[0] + (ul)pt[1]*pt[1];
        }
        if(*s >> 53)
            break;
if(s[1] - s[0] != 1)
exit(4);

        if(sqrt(s[0]) == sqrt(s[1])) {
             for(int i = 0; i < 2; i++)
                if(a.p[i][0] > a.p[i][1])
                    swap(a.p[i][0], a.p[i][1]);
            INS(r,a)
        }
    }
    //if(!print) cout<<n<<endl;
}

void endit()
{
    this_thread::sleep_for(chrono::seconds(599));
    exit(0);
}

int main(int ac, char**av)
{
    bool kill = false;
    for(int i = 1; i < ac; i++) {
        print |= ac>1 && !stricmp(av[1], "-P");
        kill |= !stricmp(av[i], "-K");
    }

    thread KILLER;
    if(kill)
        KILLER = thread(endit);

    h()<ans, HA> res;
    res.reserve(1<<27);

    #define JMAX 43000000
    for(ul j = 0; j < JMAX; j++) {
        pparm p1(-~j,j,~-j,0),p2(j,1,j,j);
        gen(res,p1,p2);
        if(!print && !(j%1024))
#ifdef DBUG
            cout<<j<<' ',
#endif
            cout<<n<<endl;

    }
    exit(0);
}

```
> 4 votes

# Answer
## Java, Bresenham-esque circle scan

Heuristically I expect to get more collisions by starting at the wider end of the annulus. I expected to get some improvement by doing one scan for each collision, recording values for which `surplus` is between `0` and `r2max - r2` inclusive, but in my testing that proved slower than this version. Similarly attempts to use a single `int[]` buffer rather than lots of creation of two-element arrays and lists. Performance optimisation is a strange beast indeed.

Run with a command-line argument for output of the pairs, and without for simple counts.

```
import java.util.*;

public class CodeGolf37627 {
    public static void main(String[] args) {
        final int M = 144;
        boolean[] possible = new boolean[M];
        for (int i = 0; i <= M/2; i++) {
            for (int j = 0; j <= M/2; j++) {
                possible[(i*i+j*j)%M] = true;
            }
        }

        long count = 0;
        double sqrt = 0;
        long r2max = 0;
        List<int[]> previousPoints = null;
        for (long r2 = 1L << 53; ; r2--) {
            if (!possible[(int)(r2 % M)]) continue;

            double r = Math.sqrt(r2);
            if (r != sqrt) {
                sqrt = r;
                r2max = r2;
                previousPoints = null;
            }
            else {
                if (previousPoints == null) previousPoints = findLatticePointsBresenham(r2max, (int)r);

                if (previousPoints.size() == 0) {
                    r2max = r2;
                    previousPoints = null;
                }
                else {
                    List<int[]> points = findLatticePointsBresenham(r2, (int)r);
                    for (int[] p1 : points) {
                        for (int[] p2 : previousPoints) {
                            if (args.length > 0) System.out.format("(%d, %d) (%d, %d)\n", p1[0], p1[1], p2[0], p2[1]);
                            count++;
                        }
                    }
                    previousPoints.addAll(points);
                    System.out.println(count);
                }
            }
        }
    }

    // Surprisingly, this seems to be faster than doing one scan for all two or three r2s.
    private static List<int[]> findLatticePointsBresenham(long r2, long r) {
        List<int[]> rv = new ArrayList<int[]>();
        // Require 0 = y = x
        long x = r, y = 0, surplus = r2 - r * r;
        while (y <= x) {
            if (surplus == 0) rv.add(new int[]{(int)x, (int)y});

            // Invariant: surplus = r2 - x*x - y*y >= 0
            y++;
            surplus -= 2*y - 1;
            if (surplus < 0) {
                x--;
                surplus += 2*x + 1;
            }
        }

        return rv;
    }
}

```
> 2 votes

# Answer
## Java - 27,817,255

Most of these are the same as what Ell shows, and the rest are based on `(j,0) (k,l)`. For each `j`, I walk back some squares and check if the remainder gives a false positive. This takes up basically the entire time with only a 25k (about 0.1%) gain over just `(j,0) (j,1)`, but a gain is a gain.

This will finish in under ten minutes on my machine, but I don't know what you have. Because reasons, if it *doesn't* finish before the time runs out, it will have a drastically worse score. In that case, you can tweak the divisor on line 8 so that it finishes in time (this simply determines how far back it walks for each `j`). For some various divisors, scores are:

```
11    27817255 (best on OPs machine)
10    27818200
8     27820719
7     27822419 (best on my machine)

```

To turn on output for each match (and, god, it is slow if you do), just uncomment lines 10 and 19.

```
public class FalsePositive {
    public static void main(String[] args){
        long j = 67108864;
        long start = System.currentTimeMillis();
        long matches=0;
        while(j < 94906265 && System.currentTimeMillis()-start < 599900){
            long jSq = j*j;
            long limit = (long)Math.sqrt(j)/11; // <- tweak to fit inside 10 minutes for best results
            matches++; // count an automatic one for (j,0)(j,1)
            //System.out.println("("+j+",0) ("+j+",1)");
            for(int i=1;i<limit;i++){
                long k = j-i;
                long kSq = k*k;
                long l = (long)Math.sqrt(jSq-kSq);
                long lSq = l*l;
                if(kSq+lSq != jSq){
                    if(Math.sqrt(kSq+lSq)==Math.sqrt(jSq)){
                        matches++;
                        //System.out.println("("+j+",0) ("+k+","+l+")");
                    }
                }
            }
            j++;
        }
        System.out.println("\n"+matches+" Total matches, got to j="+j);
    }
}

```

For reference, the first 20 outputs it gives (for divisor=7, excluding `(j,0)(j,1)` types) are:

```
(67110083,0) (67109538,270462)
(67110675,0) (67109990,303218)
(67111251,0) (67110710,269470)
(67111569,0) (67110668,347756)
(67112019,0) (67111274,316222)
(67112787,0) (67111762,370918)
(67115571,0) (67115518,84346)
(67117699,0) (67117698,11586)
(67117971,0) (67117958,41774)
(67120545,0) (67120040,260368)
(67121043,0) (67120118,352382)
(67122345,0) (67122320,57932)
(67122449,0) (67122444,25908)
(67122633,0) (67122328,202348)
(67122729,0) (67121972,318784)
(67122849,0) (67122568,194224)
(67124195,0) (67123818,224970)
(67125201,0) (67125172,62396)
(67125705,0) (67124632,379540)
(67126195,0) (67125882,204990)

```
> 1 votes

# Answer
## Julia, 530 false positives

Here is a very naive brute force search, which you can view as a reference implementation.

```
num = 0
for i = 60000000:-1:0
    for j = i:-1:ifloor(0.99*i)
        s = i*i + j*j
        for x = ifloor(sqrt(s/2)):ifloor(sqrt(s))
            min_y = ifloor(sqrt(s - x*x))
            max_y = min_y+1
            for y = min_y:max_y
                r = x*x + y*y
                if r != s && sqrt(r) == sqrt(s)
                    num += 1
                    if num % 10 == 0
                        println("Found $num pairs")
                    end
                    #@printf("(i,j) = (%d,%d); (x,y) = (%d,%d); s = %d, r = %d\n", i,j,x,y,s,r)
                end
            end
        end
    end
end

```

You can print out the pairs (and their exact squared magnitudes) by uncommenting the `@printf` line.

Basically this starts the search at `x = y = 6e7` for the first coordinate pair and scans down about 1% of the way to the x-axis before decrementing x. Then for each such coordinate pair, it checks the entire arc of the same magnitude (rounding up and down) for a collision.

The code assumes that it's run on a 64-bit system, so that the default integer and floating-point types are 64-bit ones (if not, you can create them with `int64()` and `float64()` constructors).

That yields a meagre 530 results.
> 0 votes

---
Tags: fastest-code, arithmetic, floating-point
---


title: Distribution of Variables

text:
# Question
Title: Distribution of Variables
I was annoyed the other day when I got a point off in math class because I didn't distribute the factors of my function.

That is, I put (x+2)(x-3) when I should have put x^2 - x - 6.

Your job is to write a program that takes a string with the expression and convert it to the expanded form so I don't miss future points.

## Rules

* Any letters within the lowercase English alphabet can be used as "x" (for example: (a+1)(c+3)).
* All exponents in answer must be in the form (variable)^n where n is the power
* variables can be assumed to be 1 character long. That is, ab == a * b
* Your answer should not contain the "\*" character
* The spaces before and after a + or - must be present. Otherwise, no spaces are permitted, except for trailing spaces.
* You must account for exponents outside of parentheses, so (x+1)^n.

## Specifications

* You may create a program or function that takes a string parameter
* Your program must output the correct expression to STDOUT or a text file
* You may assume that all factors will be surrounded by parentheses. For example, x(x+1) will always be (x)(x+1).
* There will never be any other operation besides multiplication between parenthesis. This will never happen: (x)+(x+1).
* You may assume there will never be any nested parentheses/exponents.
* Order of the resulting expression should be highest exponents first, as per usual math standards. Otherwise, order does not matter.
* You may assume single digit exponents
* Built in expansion libraries/functions are not allowed, as the comments mention below

## Examples

```
(x+1)(x+2) --> x^2 + 3x + 2
(a)(a-4) --> a^2 - 4a
(c+1)^3 --> c^3 + 3c^2 + 3c  + 1
(a+1)(f-2) --> af - 2a + f - 2
(x-2)(x+4)(x-5)(x+10) --> x^4 + 7x^3 - 48x^2 - 140x + 400
(x+a+c)(b+g) --> xb + xg + ab + ag + cb + cg
(r+4)^2(b) --> br^2 + 8br + 16b

```

This is code-golf, so shortest program wins!

## Bonus

-25 bytes to anyone who makes their program compatible with complex numbers

# Answer
# JavaScript (E6) 834

While waiting for some clarification by OP, I start recycling my answer from this other question It's more than what is required here, so it could be golfed more. I have modified the spacing and added sorting by higher exponent (of any variable).

```
G=x=>x.replace(/\d/g,n=>' '.repeat(n-2)).length,
K=x=>Object.keys(x).sort((a,b)=>G(b)-G(a)),
A=(p,q,s,t,c)=>[(c=(s+1)*q[t]+~~p[t])?p[t]=c:delete(p[t])for(t in q)],
M=(p,q,t,c,o,u,f,r,v={})=>([A(v,(r={},[(c=p[f]*q[t])&&(r[o={},(u=f+t)&&(u.match(/[a-z]\^?\d*/ig).map(x=>o[x[0]]=~~o[x[0]]+(~~x.slice(2)||1)),K(o,u=k).map(i=>u+=o[i]>1?i+'^'+o[i]:i)),u]=c)for(f in p)],r),k)for(t in q)],v),
E=(p,n)=>--n?M(p,E(p,n)):p,
O=n=>{for(l=0;h(o=s.pop())>=h(n);)a=w.pop(b=w.pop()),o=='*'?a=M(a,b):o>d?a=E(a,b[k]):A(a,b,o),w.push(a);s.push(o,n)},
X=e=>(l=k='',w=[],s=[d='@'],h=o=>'@)+-*^('.indexOf(o),
(e+')').match(/\D|\d+/g).map(t=>(u=h(t))>5?(l&&O('*'),s.push(d)):u>1?O(t):~u?s.pop(s.pop(O(t)),l=1):(l&&O('*'),l=1,w.push(v={}),t<d?v[k]=t|0:v[t]=1)),
K(p=w.pop()).map(i=>(k+=(c=p[i])>1?s+c+i:c<-1?c+i:(c-1?'-':s)+(i||1),s=' + ')),k.replace(/-/g,' - ')||0)

```

**Test** in FireFox/FireBug console

```
;["(x+1)(x+2)","(a)(a-4)","(c+1)^3","(a+1)(f-2)","(x-2)(x+4)(x-5)(x+10)","(x+a+c)(b+g)","(r+4)^2(b)"]
.map(x => console.log(x + " -> " + X(x)))

```

*Output*

```
(x+1)(x+2) -> x^2 + 3x + 2
(a)(a-4) -> a^2 - 4a
(c+1)^3 -> c^3 + 3c^2 + 3c + 1
(a+1)(f-2) -> af + f - 2a - 2
(x-2)(x+4)(x-5)(x+10) -> x^4 + 7x^3 - 48x^2 - 140x + 400
(x+a+c)(b+g) -> xb + ab + cb + xg + ag + cg
(r+4)^2(b) -> r^2b + 8rb + 16b

```
> 1 votes

# Answer
## Mathematica 11-25=-14 40-25=15 characters

Really too easy in this language:

```
f=TraditionalForm@Expand@ToExpression@#&

```

Usage:

```
f["(x+2)(x-3)"]

```

Output:

x2 \- x - 6

And it's even shorter if you allow input that isn't a string (and don't care about term order):

```
f=Expand@ToExpression@#&

```

Used as follows for the same output:

```
f[(x+2)(x-3)]

```

Mathematica can natively support complex numbers.

EDIT: technically this answer fails because it will take ab (without spaces) as a single variable instead of a\*b as per the rules.

EDIT2:Changed so it will output in the required order
> 0 votes

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