title: Too many pawns on a chess board

text:
# Question
Title: Too many pawns on a chess board
Given an integer 2n, find the number of possible ways in which 2n^2 black pawns and 2n^2 white pawns can be arranged on a 2n by 2n chess board such that no pawn attack another.

* A black pawn can attack only a white pawn, and vice versa.
* The usual chess rules of attacking follow, i.e, white pawns attack squares immediately diagonally in front, and the black pawns attack squares immediately diagonally backward (as seen by the white observer).
* All rotation, reflections count as distinct.

---

The program that can output all possible configurations for the highest value of 2n in 120 seconds wins. (All programs are welcome, though)

For example, Alice's program can deal with upto n=16 within 120 seconds while Bob's can deal with upto n=20 within the same time. Bob wins.

Platform: Linux 2.7GHz @ 4 CPUs

# Answer
> 10 votes
# Java, n=87 on my machine

The result for n=87 is

```
62688341832480765224168252369740581641682638216282495398959252035334029997073369148728772291668336432168

```

```
import java.math.BigInteger;

public class NonattackingPawns {

    static BigInteger count(int n) {
        BigInteger[][] a0 = new BigInteger[n+1][n*n+1], a1 = new BigInteger[n+1][n*n+1], tm;

        for(int h = 0; h <= n; h++) a0[h][0] = h%2==0? BigInteger.ONE: BigInteger.ZERO;

        for(int c = 1; c <= 2*n; c++) {
            int minp = 0;
            for(int h = 0; h <= n; h++) {
                java.util.Arrays.fill(a1[h], BigInteger.ZERO);
                if(h>0) minp += c >= 2*h-c%2 ? 2*h - c%2 : c;

                int maxp = Math.min(n*(c-1)+h, n*n);
                for(int p = minp; p <= maxp; p++) {
                    BigInteger sum = a0[h][p-h];

                    if(c%2==1 && h>0)
                        sum = sum.add(a0[h-1][p-h]);
                    else if(c%2==0 && h<n)
                        sum = sum.add(a0[h+1][p-h]);

                    a1[h][p] = sum;
                }
            }
            tm=a0; a0=a1; a1=tm;
        }
        BigInteger[] s = new BigInteger[n*n+1];
        for(int p = 0; p <= n*n; p++) {
            BigInteger sum = BigInteger.ZERO;
            for(int h = 0; h <= n; h++) sum = sum.add(a0[h][p]);
            s[p] = sum;

        }

        BigInteger ans = BigInteger.ZERO;
        for(int p = 0; p < n*n; p++) ans = ans.add(s[p].multiply(s[p]));
        return ans.shiftLeft(1).add(s[n*n].multiply(s[n*n]));
    }

    public static void main(String[] args) {
        for(int n = 0;; n++) {
            System.out.println(n + " " + count(n));
        }
    }

}

```

This currently uses a dynamic programming scheme taking O(n^4) operations to calculate the ways to place `p` pawns on the squares of one color for `0 <= p <= n^2`. I think it should be possible to do this much more efficiently.

Check out the results here.

### Explanation

In a valid solution, the lowermost white pawns in each column must form a zigzagging line like this:

That is, the height of the line in column *c* must be +/- 1 from its position in column *c - 1*. The line can also go onto two imaginary rows above the top of the board.

We can use dynamic programming to find the number of ways to draw a line on the first *c* columns that includes *p* pawns on those columns, is at height *h* on the *c*th column, using the results for column *c - 1*, heights *h +/- 1*, and number of pawns *p - h*.

# Answer
> 6 votes
# Java

Currently, my code is very long and tedious, I'm working on making it faster. I use a recursive method in order to find the values. It computes the first 5 within 2 or 3 seconds, but it gets much slower afterwards. Also, I'm not sure yet if the numbers are right, but the first few seem to line up with the comments. Any suggestions are welcome.

**Output**

```
2x2:    3
4x4:    30
6x6:    410
8x8:    6148
10x10:  96120

```

**Explanation**

The basic idea is recursion. Essentially you start with an empty board, a board with all zeros. The recursive method just checks to see if it can put a black or white pawn in the next position, if it can only put one color, it puts it there and calls itself. If it can put both colors it calls itself twice, one with each color. Each time it calls itself it decreases the squares left and the appropriate color left. When it has filled the entire board it returns the the current count + 1. If it finds out that there is no way to put a black or white pawn in the next position, it returns 0, which means it's a dead path.

**Code**

```
public class Chess {
    public static void main(String[] args){
        System.out.println(solve(1));
        System.out.println(solve(2));
        System.out.println(solve(3));
        System.out.println(solve(4));
        System.out.println(solve(5));
    }
    static int solve(int n){
        int m =2*n;
        int[][] b = new int[m][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                b[i][j]=0;
            }
        }
        return count(m,m*m,m*m/2,m*m/2,0,b);
    }
    static int count(int n,int sqLeft, int bLeft, int wLeft, int count, int[][] b){
        if(sqLeft == 0){
            /*for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    System.out.print(b[i][j]);
                }
                System.out.println();
            }
            System.out.println();*/
            return count+1;
        }
        int x=(sqLeft-1)%n;
        int y=(sqLeft-1)/n;
        if(wLeft==0){
            if(y!=0){
                if ((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!= 1)) {
                    b[x][y] = 2;
                    return count(n, sqLeft-1, bLeft-1, wLeft, count, b);
                } else {
                    return 0;
                }
            } else {
                b[x][y]=2;
                return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
            }
        } else if(bLeft==0){
            if(y!=n-1){
                if((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
                    b[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
                } else {
                    return 0;
                }
            } else {
                b[x][y]=1;
                return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
            }
        } else{
            if(y==0){
                if((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
                    int[][] c=new int[n][n];
                    for(int i = 0; i < n; i++){
                        System.arraycopy(b[i], 0, c[i], 0, n);
                    }
                    b[x][y]=2;
                    c[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else {
                    b[x][y]=2;
                    return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                }
            }else if(y==n-1){
                if((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1)){
                    int[][] c=new int[n][n];
                    for(int i = 0; i < n; i++){
                        System.arraycopy(b[i], 0, c[i], 0, n);
                    }
                    b[x][y]=2;
                    c[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else {
                    b[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
                }
            }else{
                if(((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1))&&((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2))){
                    int[][] c=new int[n][n];
                    for(int i = 0; i < n; i++){
                        System.arraycopy(b[i], 0, c[i], 0, n);
                    }
                    b[x][y]=2;
                    c[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,c)+count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else if ((x==0?true:b[x-1][y-1]!=1)&&(x==n-1?true:b[x+1][y-1]!=1)){
                    b[x][y]=2;
                    return count(n,sqLeft-1,bLeft-1,wLeft,count,b);
                } else if ((x==0?true:b[x-1][y+1]!=2)&&(x==n-1?true:b[x+1][y+1]!=2)){
                    b[x][y]=1;
                    return count(n,sqLeft-1,bLeft,wLeft-1,count,b);
                } else {
                    return 0;
                }
            }
        }
    }
}

```

Try it here *(Doesn't run fast enough for Ideone so the last value doesn't print, looks like my solution isn't very good!)*

# Answer
> 4 votes
# C++ with pthreads, n = ~~147~~ 156

The latest result is from running the same code as before on a beefier machine. This was now run on a desktop with a quad-core i7 (Core i7-4770), which got to n=156 in 120 seconds. The result is:

> 7858103688882482349696225090648142317093426691269441606893544257091315906431773702676266198643058148987365151560565922891852481847049321541347582728793175114543840164406674137410614843200

This is using a dynamic programming algorithm. I initially pondered approaches where the result would be built row by row, but I could never come up with a way to expand the solution without tracking a ton of state.

The key insights that enabled a reasonably efficient solution were:

* Since pawns on black squares can only attack pawns on other black squares, and the same is true for white squares, the black and white squares are independent, and can be processed separately. And since they are equivalent, we only need to process one of the two.
* The problem gets much easier when processing the board diagonal by diagonal.

If you look at one diagonal of a valid configuration, it always consists of a sequence of black pawns followed by a sequence of white pawns (where either sequence can also be empty). In other words, each diagonal can be fully characterized by its number of black pawns.

Therefore, the state tracked for each diagonal is the number of valid pawn configurations for each combination of:

* Number of black pawns in the row (or in other words, the position within the diagonal that separates the black pawns from the white pawns).
* Total count of black pawns used. We need to track the whole thing per pawn count because we only need the equal number of black pawns and white pawns at the very end. While processing the diagonals, the counts can be different, and still result in valid solutions in the end.

When stepping from one diagonal to the next one, there is another constraint to build valid solutions: The position that separates black pawns from white pawns can not increase. So the number of valid configurations is calculated as the sum of the valid configurations of the previous diagonal for positions that are equal or larger.

The basic DP step is then very simple. Each value in a diagonal is just a sum of values from the previous diagonal. The only somewhat painful part is calculating the indices and loop ranges correctly. Since we're working on diagonals, the length increases during the first half of the calculation, and decreases for the second half, which makes the calculation of the loop ranges more cumbersome. There's also some considerations for the values at the boundary of the board, since they only have diagonal neighbors on one side when stepping from diagonal to diagonal.

The amount of memory used is O(n^3). I keep two copies of the state data, and ping pong between them. I believe it would be possible to operate with a single instance of the state data. But you would have to be very careful that no values are updated before the old values are fully consumed. Also, it would not work well for the parallel processing I introduced.

Runtime complexity is... polynomial. There are 4 nested loops in the algorithm, so at first sight it would look like O(n^4). But you obviously need bigints at these sizes, and the numbers themselves also get longer at larger sizes. The number of digits in the result seems to increase roughly proportionally to n, which would make the whole thing O(n^5). On the other hand, I found some performance improvements, which avoids going through the full range of all loops.

So while this is still a fairly expensive algorithm, it gets much farther than the algorithms that enumerate solutions, which are all exponential.

Some notes on the implementation:

* While there can be up to 2\*n^2 black pawns on the black squares, I only calculate the configuration numbers up to n^2 black pawns. Since there's a symmetry between black and white pawns, the configuration count for k and 2\*n^2-k are the same.
* The number of solutions is calculated at the end from the configuration counts on the black squares based on a similar symmetry. The total number of solutions (which need to have 2\*n^2 pawns of each color) is the number of configurations for k black pawns on one color of squares multiplied by the number of configurations for 2\*n^2-k black pawns on the other color of squares, summed over all k.
* In addition to just storing the configuration counts per diagonal position and pawn count, I also store the range of pawn counts that have valid configurations per position. This allows cutting down the range of the inner loop substantially. Without this, I found that a lot of zeros were being added. I got a very substantial performance improvement from this.
* The algorithm parallelizes fairly well, particularly at large sizes. The diagonals have to be processes sequentially, so there is a barrier at the end of each diagonal. But the positions within the diagonal can be processed in parallel.
* Profiling shows that the bottleneck is clearly in adding bigint values. I played around with some variations of the code, but it's not heavily optimized. I suspect that there could be a significant improvement from inline assembly to use 64-bit additions with carry.

Main algorithm code. `THREADS` controls the number of threads used, where the number of CPU cores should be a reasonable starting point:

```
#ifndef THREADS
#define THREADS 2
#endif

#if THREADS > 1
#include <pthread.h>
#endif

#include <vector>
#include <iostream>
#include <sstream>

#include "BigUint.h"

typedef std::vector<BigUint> BigUintVec;
typedef std::vector<int> IntVec;

static int N;
static int NPawn;
static int NPos;

static BigUintVec PawnC[2];
static IntVec PawnMinC[2];
static IntVec PawnMaxC[2];

#if THREADS > 1
static pthread_mutex_t ThreadMutex;
static pthread_cond_t ThreadCond;
static int BarrierCount;
#endif

#if THREADS > 1
static void ThreadBarrier()
{
    pthread_mutex_lock(&ThreadMutex);

    --BarrierCount;
    if (BarrierCount)
    {
        pthread_cond_wait(&ThreadCond, &ThreadMutex);
    }
    else
    {
        pthread_cond_broadcast(&ThreadCond);
        BarrierCount = THREADS;
    }

    pthread_mutex_unlock(&ThreadMutex);
}
#endif

static void* countThread(void* pData)
{
    int* pThreadIdx = static_cast<int*>(pData);
    int threadIdx = *pThreadIdx;

    int prevDiagMin = N - 1;
    int prevDiagMax = N;

    for (int iDiag = 1; iDiag < 2 * N; ++iDiag)
    {
        BigUintVec& rSrcC = PawnC[1 - iDiag % 2];
        BigUintVec& rDstC = PawnC[iDiag % 2];

        IntVec& rSrcMinC = PawnMinC[1 - iDiag % 2];
        IntVec& rDstMinC = PawnMinC[iDiag % 2];

        IntVec& rSrcMaxC = PawnMaxC[1 - iDiag % 2];
        IntVec& rDstMaxC = PawnMaxC[iDiag % 2];

        int diagMin = prevDiagMin;
        int diagMax = prevDiagMax;;
        if (iDiag < N)
        {
            --diagMin;
            ++diagMax;
        }
        else if (iDiag > N)
        {
            ++diagMin;
            --diagMax;
        }

        int iLastPos = diagMax;
        if (prevDiagMax < diagMax)
        {
            iLastPos = prevDiagMax;
        }

        for (int iPos = diagMin + threadIdx; iPos <= iLastPos; iPos += THREADS)
        {
            int nAdd = iPos - diagMin;

            for (int iPawn = nAdd; iPawn < NPawn; ++iPawn)
            {
                rDstC[iPos * NPawn + iPawn] = 0;
            }

            rDstMinC[iPos] = NPawn;
            rDstMaxC[iPos] = -1;

            int iFirstPrevPos = iPos;
            if (!nAdd)
            {
                iFirstPrevPos = prevDiagMin;
            }

            for (int iPrevPos = iFirstPrevPos;
                 iPrevPos <= prevDiagMax; ++iPrevPos)
            {
                int iLastPawn = rSrcMaxC[iPrevPos];
                if (iLastPawn + nAdd >= NPawn)
                {
                    iLastPawn = NPawn - 1 - nAdd;
                }

                if (rSrcMinC[iPrevPos] > iLastPawn)
                {
                    continue;
                }

                if (rSrcMinC[iPrevPos] < rDstMinC[iPos])
                {
                    rDstMinC[iPos] = rSrcMinC[iPrevPos];
                }

                if (iLastPawn > rDstMaxC[iPos])
                {
                    rDstMaxC[iPos] = iLastPawn;
                }

                for (int iPawn = rSrcMinC[iPrevPos];
                     iPawn <= iLastPawn; ++iPawn)
                {
                    rDstC[iPos * NPawn + iPawn + nAdd] += rSrcC[iPrevPos * NPawn + iPawn];
                }
            }

            if (rDstMinC[iPos] <= rDstMaxC[iPos])
            {
                rDstMinC[iPos] += nAdd;
                rDstMaxC[iPos] += nAdd;
            }
        }

        if (threadIdx == THREADS - 1 && diagMax > prevDiagMax)
        {
            int pawnFull = (iDiag + 1) * (iDiag + 1);
            rDstC[diagMax * NPawn + pawnFull] = 1;
            rDstMinC[diagMax] = pawnFull;
            rDstMaxC[diagMax] = pawnFull;
        }

        prevDiagMin = diagMin;
        prevDiagMax = diagMax;

#if THREADS > 1
        ThreadBarrier();
#endif
    }

    return 0;
}

static void countPawns(BigUint& rRes)
{
    NPawn = N * N + 1;
    NPos = 2 * N;

    PawnC[0].resize(NPos * NPawn);
    PawnC[1].resize(NPos * NPawn);

    PawnMinC[0].assign(NPos, NPawn);
    PawnMinC[1].assign(NPos, NPawn);

    PawnMaxC[0].assign(NPos, -1);
    PawnMaxC[1].assign(NPos, -1);

    PawnC[0][(N - 1) * NPawn + 0] = 1;
    PawnMinC[0][N - 1] = 0;
    PawnMaxC[0][N - 1] = 0;

    PawnC[0][N * NPawn + 1] = 1;
    PawnMinC[0][N] = 1;
    PawnMaxC[0][N] = 1;

#if THREADS > 1
    pthread_mutex_init(&ThreadMutex, 0);
    pthread_cond_init(&ThreadCond, 0);

    BarrierCount = THREADS;

    int threadIdxA[THREADS] = {0};
    pthread_t threadA[THREADS] = {0};
    for (int iThread = 0; iThread < THREADS; ++iThread)
    {
        threadIdxA[iThread] = iThread;
        pthread_create(threadA + iThread, 0, countThread, threadIdxA + iThread);
    }

    for (int iThread = 0; iThread < THREADS; ++iThread)
    {
        pthread_join(threadA[iThread], 0);
    }

    pthread_cond_destroy(&ThreadCond);
    pthread_mutex_destroy(&ThreadMutex);
#else
    int threadIdx = 0;
    countThread(&threadIdx);
#endif

    BigUint solCount;
    BigUintVec& rResC = PawnC[1];
    for (int iPawn = 0; iPawn < NPawn; ++iPawn)
    {
        BigUint nComb = rResC[(N - 1) * NPawn + iPawn];

        nComb *= nComb;
        if (iPawn < NPawn - 1)
        {
            nComb *= 2;
        }

        solCount += nComb;
    }

    std::string solStr;
    solCount.toDecString(solStr);
    std::cout << solStr << std::endl;
}

int main(int argc, char* argv[])
{
    std::istringstream strm(argv[1]);
    strm >> N;

    BigUint res;
    countPawns(res);

    return 0;
}

```

This also needs a bigint class that I wrote for this purpose. Note that this is not a general purpose bigint class. It does just enough to support the operations used by this specific algorithm:

```
#ifndef BIG_UINT_H
#define BIG_UINT_H

#include <cstdint>
#include <string>
#include <vector>

class BigUint
{
public:
    BigUint()
      : m_size(1),
        m_cap(MIN_CAP),
        m_valA(m_fixedValA)
    {
        m_valA[0] = 0;
    }

    BigUint(uint32_t val)
      : m_size(1),
        m_cap(MIN_CAP),
        m_valA(m_fixedValA)
    {
        m_valA[0] = val;
    }

    BigUint(const BigUint& rhs)
      : m_size(rhs.m_size),
        m_cap(MIN_CAP),
        m_valA(m_fixedValA)
    {
        if (m_size > MIN_CAP)
        {
            m_cap = m_size;
            m_valA = new uint32_t[m_cap];
        }

        for (int iVal = 0; iVal < m_size; ++iVal)
        {
            m_valA[iVal] = rhs.m_valA[iVal];
        }
    }

    ~BigUint()
    {
        if (m_cap > MIN_CAP)
        {
            delete[] m_valA;
        }
    }

    BigUint& operator=(uint32_t val)
    {
        m_size = 1;
        m_valA[0] = val;

        return *this;
    }

    BigUint& operator=(const BigUint& rhs)
    {
        if (rhs.m_size > m_cap)
        {
            if (m_cap > MIN_CAP)
            {
                delete[] m_valA;
            }

            m_cap = rhs.m_size;
            m_valA = new uint32_t[m_cap];
        }

        m_size = rhs.m_size;

        for (int iVal = 0; iVal < m_size; ++iVal)
        {
            m_valA[iVal] = rhs.m_valA[iVal];
        }

        return *this;
    }

    BigUint& operator+=(const BigUint& rhs)
    {
        if (rhs.m_size > m_size)
        {
            resize(rhs.m_size);
        }

        uint64_t sum = 0;
        for (int iVal = 0; iVal < m_size; ++iVal)
        {
            sum += m_valA[iVal];
            if (iVal < rhs.m_size)
            {
                sum += rhs.m_valA[iVal];
            }
            m_valA[iVal] = sum;
            sum >>= 32u;
        }

        if (sum)
        {
            resize(m_size + 1);
            m_valA[m_size - 1] = sum;
        }

        return *this;
    }

    BigUint& operator*=(const BigUint& rhs)
    {
        int resSize = m_size + rhs.m_size - 1;
        uint32_t* resValA = new uint32_t[resSize];

        uint64_t sum = 0;

        for (int iResVal = 0; iResVal < resSize; ++iResVal)
        {
            uint64_t carry = 0;

            for (int iLhsVal = 0;
                 iLhsVal <= iResVal && iLhsVal < m_size; ++iLhsVal)
            {
                int iRhsVal = iResVal - iLhsVal;
                if (iRhsVal < rhs.m_size)
                {
                    uint64_t prod = m_valA[iLhsVal];
                    prod *= rhs.m_valA[iRhsVal];
                    uint64_t newSum = sum + prod;
                    if (newSum < sum)
                    {
                        ++carry;
                    }
                    sum = newSum;
                }
            }

            resValA[iResVal] = sum & UINT64_C(0xFFFFFFFF);
            sum >>= 32u;
            sum += carry << 32u;
        }

        if (resSize > m_cap)
        {
            if (m_cap > MIN_CAP)
            {
                delete[] m_valA;
            }

            m_cap = resSize;
            m_valA = resValA;
        }
        else
        {
            for (int iVal = 0; iVal < resSize; ++iVal)
            {
                m_valA[iVal] = resValA[iVal];
            }

            delete[] resValA;
        }

        m_size = resSize;

        if (sum)
        {
            resize(m_size + 1);
            m_valA[m_size - 1] = sum;
        }

        return *this;
    }

    void divMod(uint32_t rhs, uint32_t& rMod)
    {
        uint64_t div = 0;
        for (int iVal = m_size - 1; iVal >= 0; --iVal)
        {
            div <<= 32u;
            div += m_valA[iVal];

            uint64_t val = div / rhs;
            div -= val * rhs;

            if (val || iVal == 0 || iVal < m_size - 1)
            {
                m_valA[iVal] = val;
            }
            else
            {
                --m_size;
            }
        }

        rMod = div;
    }

    void toDecString(std::string& rStr) const
    {
        std::vector<char> digits;

        BigUint rem(*this);
        while (rem.m_size > 1 || rem.m_valA[0])
        {
            uint32_t digit = 0;
            rem.divMod(10, digit);
            digits.push_back(digit);
        }

        if (digits.empty())
        {
            rStr = "0";
        }
        else
        {
            rStr.clear();
            rStr.reserve(digits.size());

            for (int iDigit = digits.size() - 1; iDigit >= 0; --iDigit)
            {
                rStr.append(1, '0' + digits[iDigit]);
            }
        }
    }

private:
    static const int MIN_CAP = 8;

    void resize(int newSize)
    {
        if (newSize > m_cap)
        {
            uint32_t* newValA = new uint32_t[newSize];

            for (int iVal = 0; iVal < m_size; ++iVal)
            {
                newValA[iVal] = m_valA[iVal];
            }

            if (m_cap > MIN_CAP)
            {
                delete[] m_valA;
            }

            m_cap = newSize;
            m_valA = newValA;
        }

        for (int iVal = m_size; iVal < newSize; ++iVal)
        {
            m_valA[iVal] = 0;
        }

        m_size = newSize;
    }

    int m_size;
    int m_cap;

    uint32_t* m_valA;
    uint32_t m_fixedValA[MIN_CAP];
};

#endif // BIG_UINT_H

```

# Answer
> 0 votes
## Fantom

Here's an initial post that sets up the framework. I think the procedure is a relatively good one, but the implementation right now kind of sucks. I need to probably try to minimize the number of calculations I'm doing, and instead just pass more constants.

# Strategy

Basically, each white pawn must be attacking other white pawns. So I start by placing a white pawn, placing pawns in each place it attacks, and essentially filling in the board with all the places a white pawn HAS to go. I stop if I've added too many white pawns already. If, at the end of this, I have exactly 2n^2 pawns, it's a solution. If less than that, add another white pawn somewhere, fill out all his required places, and count again. I recursively split every time a fill with less than 2n^2 is found, and calculate number of solutions with and without the last pawn I added.

# Code

```
class main
{
  public  Void main(){

    echo(calculate(1))
    echo(calculate(2))
    echo(calculate(3))
    echo(calculate(4))
    echo(calculate(5))

  }

  public static  Int calculate(Int n){

    n *= 2
    //Initialize the array -  Definitely a weakpoint, but only runs once
    Bool[][] white := [,]
    n.times{
      row := [,]
      n.times{ row.add(false) }
      white.add(row)
    }

    return recurse(white, -1, 0, n, n*n/2)
  }

  private static  Int recurse(Bool[][] white, Int lastPlacement, Int numWhites, Int n, Int totalWhite){
    if(totalWhite - numWhites > n*n - 1 - lastPlacement) return 0
    lastPlacement++
    Int row := lastPlacement / n
    Int col := lastPlacement % n
    if(white[row][col]){ return recurse(white, lastPlacement, numWhites, n, totalWhite)}
    Bool[][] whiteCopy := copy(white)
    whiteCopy[row][col] = true
    Int result := fillIn(whiteCopy, numWhites + 1, totalWhite)
    if(result == -1){
      return recurse(white, lastPlacement, numWhites,n, totalWhite);
    }
    else if(result == totalWhite){
      //echo("Found solution")
      //echo("WhiteCopy = $whiteCopy")
      return recurse(white, lastPlacement, numWhites,n, totalWhite) + 1;
    }
    else return recurse(whiteCopy, lastPlacement, result,n, totalWhite) + recurse(white, lastPlacement, numWhites,n, totalWhite)

  }

  //Every white must be attacking other whites, so fill in the grid with all necessary points
  //Stop if number of whites used goes too high
  private static Int fillIn(Bool[][] white, Int count, Int n){
    white[0..-2].eachWhile |Bool[] row, Int rowIndex -> Bool?| {
      return row.eachWhile |Bool isWhite, Int colIndex -> Bool?|{
        if(isWhite){
          //Catching index out of bounds is faster than checking index every time
          try{
            if(colIndex > 0 && !white[rowIndex + 1][colIndex - 1]){
              white[rowIndex + 1][colIndex - 1] = true
              count++
            }
            if(!white[rowIndex + 1][colIndex + 1]){
              white[rowIndex + 1][colIndex + 1] = true
              count++
            }
          } catch {}
        }
        if(count > n){ count = -1; return true}
        return null
      }//End row.each
    }//End white.each
    return count
  }

  private static Bool[][] copy(Bool[][] orig){
    Bool[][] copy := [,]
    orig.each{
      copy.add(it.dup)
    }
    return copy
  }

}

```

# Output

Only makes it to 5 right now, but I think most of the issue is in implementation.

```
3
30
410
6148
96120

```

# Test

---
Tags: fastest-code, combinatorics, chess
---


# Question
Title: Print the map of a country with the weirdest code possible
It can be in any language, plus the map must be in the output only **not in the source code**.

This is my first question here, so please feel free to edit it. Also, there might be some rules about scoreboard which I'm not familiar how to put it here.

Cheers!

# Answer
> 17 votes
## Vatican

In CJAM:

```
46c

```

You can test it here

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


# Question
Title: Check over hand values for single-suited Mahjong
Mahjong is a tile game that is immensely popular in Asia. It is typically played with four players, and the goal of the game is to be the first person to complete a valid hand using the tiles. In mahjong there are three tile suits plus honour tiles — for this challenge we will only consider hands formed using tiles from a single suit.

Tiles are numbered from `1` to `9`, and there are exactly four copies of each tile. A valid hand consists of four sets of three and a pair, for a total of fourteen tiles.

A set of three can be either:

* A triplet, three of the same tile (e.g. `444`), or
* A sequence of three consecutive tiles (e.g. `123` or `678` but not `357`). Sequences do not wrap (so `912` is invalid).

A pair is simply two identical tiles (e.g. `55`).

# The challenge

Given a valid hand of fourteen tiles, determine its score based on the following criteria:

```
Condition                Description                                 Point/s
-------------------------------------------------------------------------------
Straight                 Contains the sequences 123 456 789          1
Identical sequences      Contains two identical sequences            1
All simples              Only 2-8, no 1s or 9s                       1
All sequences            All sets of three are sequences             1
All triplets             All sets of three are triplets              2
Flush                    Single-suit hand (always applies)           5

```

<sup>*(Scoring here is based off Japanese mahjong rules, but heavily simplified to make the spec less messy.)*</sup>

The score of a hand is the sum of points for the conditions it satisfies. If a hand can be decomposed in more than one way, take the highest scoring decomposition.

The input hand is guaranteed to be valid, i.e. fourteen tiles from 1 to 9 and each tile appearing at most four times, and may be assumed to be already sorted. Input is a list of digits (as a string or a single flat list of integers) via STDIN, function argument or command line. Output may be to STDOUT or return value.

# Test cases

```
22233355777888  ->  8  # 222 333 55 777 888, flush + all simp. + all trip.
11112345678999  ->  6  # 111 123 456 789 99, flush + straight
11123456788999  ->  5  # 111 234 567 88 999, flush only (no straight)
23344455566788  ->  7  # 234 345 456 567 88, flush + all simp. + all seq.
33334444555566  ->  8  # 33 345 345 456 456, flush + all simp. + all seq. + identical seq.
11122233377799  ->  7  # 111 222 333 777 99, flush + all trip. (no identical seq.)
12344556678889  ->  8  # 123 456 456 789 88, flush + all seq. + straight + identical seq.
11344556678999  ->  5  # 11 345 456 678 999, flush only (no identical seq.)
22233344455566  ->  8  # 222 333 444 555 66, flush + all simp. + all trip.
11112233344555  ->  5  # 111 123 234 345 55, flush only

```

For the fifth example, despite having two pairs of identical sequences, only one needs to be present to attain the point. The decomposition `345 345 345 345 66` would score the same, while `333 345 444 555 66` scores worse.

# Scoring

This is , so the solution in the fewest bytes wins. Standard loopholes apply.

---

*Related challenge: What are you waiting for? (A mahjong solver)*

# Answer
> 1 votes
# J (241 byes)

You need the latest version of  installed.

```
i=:>:@i.9
q=:,/^:4>@:{(i.9);(i.;i.;i.;i.)16
s=:3 :'(>./((5+([:(*./)(3*i.3)&e.)+(-.@:(-:~.))+((*./)@:(6&>:))+2*((*./)@:(6&<)))"1(}."1(y(-:/:~"1)"1((([:{&(i,.i){.),[:,/[:{&(((>:@i.7)+"0 1(i.3)),|:3 9$i)}.)"1 q))#q)))+([:(*./)[:-.((1 9)&e.))y'

```

---

Call the function `s` with a list of integers. For example, the following example script verifies the test cases above:

```
#!/usr/bin/jconsole
i=:>:@i.9
q=:,/^:4>@:{(i.9);(i.;i.;i.;i.)16
s=:3 :'(>./((5+([:(*./)(3*i.3)&e.)+(-.@:(-:~.))+((*./)@:(6&>:))+2*((*./)@:(6&<)))"1(}."1(y(-:/:~"1)"1((([:{&(i,.i){.),[:,/[:{&(((>:@i.7)+"0 1(i.3)),|:3 9$i)}.)"1 q))#q)))+([:(*./)[:-.((1 9)&e.))y'

echo (s 2 2 2 3 3 3 5 5 7 7 7 8 8 8)=8
echo (s 1 1 1 1 2 3 4 5 6 7 8 9 9 9)=6
echo (s 1 1 1 2 3 4 5 6 7 8 8 9 9 9)=5
echo (s 2 3 3 4 4 4 5 5 5 6 6 7 8 8)=7
echo (s 3 3 3 3 4 4 4 4 5 5 5 5 6 6)=8
echo (s 1 1 1 2 2 2 3 3 3 7 7 7 9 9)=7
echo (s 1 2 3 4 4 5 5 6 6 7 8 8 8 9)=8
echo (s 1 1 3 4 4 5 5 6 6 7 8 9 9 9)=5
echo (s 2 2 2 3 3 3 4 4 4 5 5 5 6 6)=8
echo (s 1 1 1 1 2 2 3 3 3 4 4 5 5 5)=5

exit''

```

---
Tags: code-golf, game
---


title: Analyze overhanded shuffles

text:
# Question
Title: Analyze overhanded shuffles
Rod is moderating a card game between two players: George and Tim. Currently, Tim is shuffling the cards. Rod suspects that Tim is trying to cheat, so he needs your help to check that the shuffle is fair.

Tim is doing the overhanded shuffle: he cuts a pile of cards from the bottom of the deck, then cuts various parts from the top of the pile onto the top of the deck, and repeats the process a few times.

Rod is eagle-eyed and can see exactly how many cards Tim is cutting each time, however he can't calculate and keep track of the cards as fast as Tim is shuffling. This is where you come in: Rod would like you to write a program or function that gets the detailed shuffling information and determines whether the shuffle is fair, weak or a trick.

* If after shuffling, less than 25 pairs of adjacent cards remain adjacent (in the same order), then the shuffle is fair and the game can go on.
* If at least 25 (but not all) pairs of adjacent cards remain adjacent, then the shuffle is weak and Rod will bonk Tim over the head and ask him to shuffle some more.
* If all the cards remain in the same position at the end, then Tim is obviously cheating and Rod will whack him with a large trout.

This is code golf, so the shortest code wins.

**Input:**

You will get a series of numbers between 0 and 52 (both exclusive) separated by space, on several lines, where each line represents a round of shuffling that begins and ends with all the cards piled together.

On each line, the first number is the number of cards Tim cuts from the bottom of the deck, and each subsequent number is a number of cards he drops from his hand onto the top of the deck. If any cards remain after the last number on a line, you should assume that Tim puts them on top of the deck.

The input is guaranteed to be valid. There is at least one line of numbers, and each line contains at least 2 numbers. The first number on each line is not smaller than the sum of all the other numbers on the same line. A trailing newline is optional, you may assume that the input has one or that it doesn't have one.

**Output:**

Your program should print/return "fair" if the shuffle is fair, "weak" if the shuffle is weak and "trick" if Tim is keeping all the cards in the same order. A trailing newline is optional.

**Example:**

The deck is assumed to have 52 cards, but for demonstration purposes, I'll use a smaller deck of 10 cards.

Input:

```
5 3 1
4 2 2

```

Initial deck, viewed from the top: `0 1 2 3 4 5 6 7 8 9`
`5``0 1 2 3 4` (`5 6 7 8 9` in hand)
`3``5 6 7 0 1 2 3 4` (`8 9` in hand)
`1``8 5 6 7 0 1 2 3 4` (`9` in hand)
end of line ➜ `9 8 5 6 7 0 1 2 3 4`
`4``9 8 5 6 7 0` (`1 2 3 4` in hand)
`2``1 2 9 8 5 6 7 0` (`3 4` in hand)
`2``3 4 1 2 9 8 5 6 7 0`
4 pairs remain adjacent: `(3 4) (1 2) (5 6) (6 7)`

**Test cases:**

```
43 5 5 5 5 5 5 5 5
43 5 5 5 5 5 5 5 5
43 5 5 5 5 5 5 5 5

```

Output: `fair`

---

```
43 5 5 5 5 5 5 5 5
43 5 5 5 5 5 5 5 5
43 5 5 5 5 5 5 5

```

Output: `weak`

---

```
29 24
19 18
38 2 1 8 13 6 4
47 15 16 5 2 1 7
34 22 9 3
44 9 10 11 3 1 7
33 18 4 2 3 3

```

Output: `fair`

---

```
24 6 12 4
25 3 19
36 4 25 2
19 11 1 3
15 9 3
37 5 27

```

Output: `weak`

---

```
26 13
26 13
26 13
26 13

```

Output: `trick`

---

```
50 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

```

Output: `weak`

---

```
50 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

```

Output: `trick`

---

```
50 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
49 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

```

Output: `fair`

**Requirements:**

* If you write a function, it can either read from the standard input or receive the input as a single string parameter. Also, the function can either print out the output or return it.
* The program must be runnable in Linux using freely available software.
* The source code must use only ASCII characters.
* No standard loopholes.

# Answer
# Pyth, 62 bytes

```
@c"weak trick fair"d-!JlfhT-M.:us_cG.u+NYtKrH7-52hK.zU52 2>J26

```

Demonstration.
> 3 votes

# Answer
# CJam, ~~76~~ 75 bytes

```
52,qN/{[~](52\-@/(\e_@{/(@+\e_}/\+}/2ew::m2f/0-,_!\26>-"weak trick fair"S/=

```

Try it online in the CJam interpreter.
> 4 votes

# Answer
## JavaScript, ~~292~~ 289 bytes

This could probably get some more bytes squeezed out of it, but it's a quick first pass for now:

```
d=[];for(i=0;i<52;i+=1)d[i]=i
s=prompt().split('\n')
s.forEach(function(e,i){s[i]=e.split(' ')
h=d.splice(-s[i][0],99)
for(j=1;j<s[i].length;j+=1)d.unshift.apply(d,h.splice(0,s[i][j]))
d.unshift.apply(d,h)})
for(c=0;i>1;i-=1)if(d[i-2]==d[i-1]-1)c+=1
alert(c<25?"fair":c<51?"weak":"trick")

```

EDIT: Saved 3 bytes by reusing the value of `i` from the deck-building loop when counting the number of adjacent cards.
> 2 votes

---
Tags: code-golf, card-games
---


title: Sum of smallest prime factors

text:
# Question
Title: Sum of smallest prime factors
SF(n) is a function which computes the smallest prime factor for a given number n.

We'll call T(N) the sum of every SF(n) with 2 \<= n \<= N.

T(1) = 0 (the sum is over 0 summands)

T(2) = 2 (2 is the first prime)

T(3) = 5 = 2 + 3

T(4) = 7 = 2 + 3 + 2

T(5) = 12 = 2 + 3 + 2 + 5

...

T(10000) = 5786451

The winner will be the one who manages to compute the largest T(N) in 60 seconds on my own laptop (Toshiba Satellite L845, Intel Core i5, 8GB RAM).

---

```
Current top score: Nicolás Siplis - 3.6e13 points - Nim

```

# Answer
## Nim, 3.6e13

Simply sieving is not the best answer when trying to calculate the highest N possible since the memory requirements become too high. Here's a different approach (started with Nim a couple days ago and fell in love with the speed and syntax, any suggestions to make it faster or more readable are welcome!).

```
import math
import sequtils
import nimlongint # https://bitbucket.org/behrends/nimlongint/

proc s(n : int) : int128 =
    var x = toInt128(n)
    (x * x + x) div 2 - 1

proc sum_pfactor(N : int) : int128 =
    var
        root = int(sqrt(float(N)))
        u = newSeqWith(root+1,false)
        cntA,cntB,sumA,sumB = newSeq[int128](root+1)
        pcnt,psum,ret : int128
        interval,finish,d,q,t : int

    for i in 0..root:
        cntA[i] = i-1
        sumA[i] = s(i)

    for i in 1..root:
        cntB[i] = N div i - 1
        sumB[i] = s(N div i)

    for p in 2..root:
        if cntA[p] == cntA[p-1]:
            continue

        pcnt = cntA[p - 1]
        psum = sumA[p - 1]
        q = p * p
        ret = ret + p * (cntB[p] - pcnt)
        cntB[1] = cntB[1] - cntB[p] + pcnt
        sumB[1] = sumB[1] - (sumB[p] - psum) * p
        interval = (p and 1) + 1
        finish = min(root,N div q)

        for i in countup(p+interval,finish,interval):

            if u[i]:
                continue

            d = i * p

            if d <= root:
                cntB[i] = cntB[i] - cntB[d] + pcnt
                sumB[i] = sumB[i] - (sumB[d] - psum) * p
            else:
                t = N div d
                cntB[i] = cntB[i] - cntA[t] + pcnt
                sumB[i] = sumB[i] - (sumA[t] - psum) * p

        if q <= root:
            for i in countup(q,finish-1,p*interval):
                u[i] = true

        for i in countdown(root,q-1):
            t = i div p
            cntA[i] = cntA[i] - cntA[t] + pcnt
            sumA[i] = sumA[i] - (sumA[t] - psum) * p

    sumB[1] + ret

var time = cpuTime()
echo(sum_pfactor(int(3.6e13))," - ",cpuTime() - time)

```
> 12 votes

# Answer
# C, Prime Sieve: 5e9

Results:

```
$ time ./sieve
Finding sum of lowest divisors of n = 2..5000000000
572843021990627911

real    0m57.144s
user    0m56.732s
sys 0m0.456s

```

Program:

While it's a rather staightforward program, it took me a while to figure out how to get the memory management right - I only have enough ram for 1 byte per number in the range, so I had to be careful. It's a standard sieve of Erasthones.

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

#define LIMIT ((unsigned long long)5e9 +1)
#define ROOT_LIMIT floor(sqrt(LIMIT))

int main()
{
    printf("Finding sum of lowest divisors of n = 2..%llu\n", LIMIT - 1);
    char * found_divisor;
    found_divisor = malloc(LIMIT * sizeof(char));
    if (found_divisor == NULL) {
        printf("Error on malloc");
        return -1;
    }
    unsigned long long i;
    unsigned long long trial_div;
    unsigned long long multiple;
    unsigned long long sum = 0;

    for (i = 0; i < LIMIT; ++i) {
        found_divisor[i] = 0;
    }

    for (trial_div = 2; trial_div <= ROOT_LIMIT; ++trial_div) {
        if (found_divisor[trial_div] == 0) {
            for (multiple = trial_div * trial_div; multiple < LIMIT; multiple += trial_div) {
                if (found_divisor[multiple] == 0) {
                    found_divisor[multiple] = 1;
                    sum += trial_div;
                }
            }
        }
    }

    for (i = 2; i < LIMIT; ++i) {
        if (found_divisor[i] == 0) {
            sum += i;
        }
    }

    free(found_divisor);
    printf("%lld\n", sum);
    return 0;
}

```
> 5 votes

# Answer
# Perl, brute force factoring

```
use ntheory ":all";
sub T {
  my $sum=0;
  for (1..$_[0]) {
    $sum += !($_%2) ? 2 : !($_%3) ? 3 : !($_%5) ? 5 : (factor($_))[0];
  }
  $sum
}
T(90_000_000);

```

I can get to about 9e7 in 25 seconds on my Linux machine. It could be faster by digging into the C code, as it is saying after a check for 2/3/5, completely factor the number.

There are much more clever ways to do this using sieving. I thought a simple brute force way would be a start. This is basically Project Euler problem 521, by the way.
> 3 votes

# Answer
## Go, 21e9

Does a sieve to find the minimum factor of each number \<= N. Spawns goroutines to count sections of the number space.

Run with "go run prime.go -P 4 -N 21000000000".

```
package main

import (
    "flag"
    "fmt"
    "runtime"
)

const S = 1 << 16

func main() {
    var N, P int
    flag.IntVar(&N, "N", 10000, "N")
    flag.IntVar(&P, "P", 4, "number of goroutines to use")
    flag.Parse()
    fmt.Printf("N = %d\n", N)
    fmt.Printf("P = %d\n", P)
    runtime.GOMAXPROCS(P)

    // Spawn goroutines to check sections of the number range.
    c := make(chan uint64, P)
    for i := 0; i < P; i++ {
        a := 2 + (N-1)*i/P
        b := 2 + (N-1)*(i+1)/P
        go process(a, b, c)
    }
    var sum uint64
    for i := 0; i < P; i++ {
        sum += <-c
    }
    fmt.Printf("T(%d) = %d\n", N, sum)
}

func process(a, b int, res chan uint64) {
    // Find primes up to sqrt(b).  Compute starting offsets.
    var primes []int
    var offsets []int
    for p := 2; p*p < b; p++ {
        if !prime(p) {
            continue
        }
        primes = append(primes, p)
        off := a % p
        if off != 0 {
            off = p - off
        }
        offsets = append(offsets, off)
    }

    // Allocate sieve array.
    composite := make([]bool, S)

    // Check factors of numbers up to b, a block of S at a time.
    var sum uint64
    for ; a < b; a += S {
        runtime.Gosched()
        // Check divisibility of [a,a+S) by our set of primes.
        for i, p := range primes {
            off := offsets[i]
            for ; off < S; off += p {
                if composite[off] {
                    continue // Divisible by a smaller prime.
                }
                composite[off] = true
                if a+off < b {
                    sum += uint64(p)
                }
            }
            // Remember offset for next block.
            offsets[i] = off - S
        }
        // Any remaining numbers are prime.
        for i := 0; i < S; i++ {
            if composite[i] {
                composite[i] = false // Reset for next block.
                continue
            }
            if a+i < b {
                sum += uint64(a + i)
            }
        }
    }
    res <- sum
}

func prime(n int) bool {
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

```

Note that the answer for N=21e9 is between 2^63 and 2^64, so I had to use unsigned 64-bit ints to count correctly...
> 3 votes

# Answer
# C++, 1\<\<34 ~ 1.7e10

```
Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz

$ g++ -O2 test3.cpp
$ time ./a.out
6400765038917999291

real    0m49.640s
user    0m49.610s
sys 0m0.000s

```

```
#include <iostream>
#include <vector>

using namespace std;

const long long root = 1 << 17; // must be a power of two to simplify modulo operation
const long long rootd2 = root >> 1;
const long long rootd2m1 = rootd2 - 1;
const long long mult = root; // must be less than or equal to root
const long long n = root * mult; // unused constant (function argument)

int main() {
  vector < int > sieve(rootd2, 0);
  vector < int > primes;
  vector < long long > nexts;
  primes.reserve(root);
  nexts.reserve(root);
  // initialize sum with result for even numbers
  long long sum = n / 2 * 2;
  // sieve of Erathosthenes for numbers less than root
  // all even numbers are skipped
  for(long long i = 1; i < rootd2; ++i){
    if(sieve[i]){
      sieve[i] = 0;
      continue;
    }
    const long long val = i * 2 + 1;
    primes.push_back(val);
    sum += val;
    long long j;
    for(j = (val + 1) * i; j < rootd2; j += val){
      sum += val * (1 - sieve[j]); // conditionals replaced by multiplication
      sieve[j] = 1;
    }
    nexts.push_back(j);
  }
  int k = primes.size();
  long long last = rootd2;
  // segmented sieve of Erathosthenes
  // all even numbers are skipped
  for(int segment = 2; segment <= mult; ++segment){
    last += rootd2;
    for(int i = 0; i < k; ++i){
      long long next = nexts[i];
      long long prime = primes[i];
      if(next < last){
        long long ptr = next & rootd2m1; // modulo replaced by bitmasking
        while(ptr < rootd2){
          sum += prime * (1 - sieve[ptr]); // conditionals replaced by multiplication
          sieve[ptr] = 1;
          ptr += prime;
        }
        nexts[i] = (next & ~rootd2m1) + ptr;
      }
    }
    for(int i = 0; i < rootd2; ++i){
      sum += ((segment - 1) * root + i * 2 + 1) * (1 - sieve[i]);
      sieve[i] = 0;
    }
  }
  cout << sum << endl;
}

```
> 2 votes

# Answer
# Java 8: 1.8e8 2.4e8

This entry does not compare to several of the other ones already up, but I wanted to post my answer since I had fun working on this.

The main optimizations of my approach are as follow:

* Every even number has a smallest factor of 2, so these can be added for free after every odd number is processed. Basically, if you have done the work to calculate `T(N)` when `N % 2 == 1`, you know that `T(N + 1) == T(N) + 2`. This allows me to start my counting at three and to increment by iteration by twos.
* I store my prime numbers in an array as opposed to a `Collection` type. This more than doubled the `N` I can reach.
* I use the prime numbers to factor a number as opposed to performing the Sieve of Eratosthenes. This means that my memory storage is restricted almost completely to my primes array.
* I store the square root of the number for which I am trying to find the smallest factor. I tried @user1354678's approach of squaring a prime factor each time, but this cost me about than 1e7 from my score.

That's about all there is to it. My code iterates from 3 on by twos until it detects that it has hit or exceeded the time limit, at which point it spits out the answer.

```
package sum_of_smallest_factors;

public final class SumOfSmallestFactors {
    private static class Result {
        private final int number;
        int getNumber() {
            return number;
        }

        private final long sum;
        long getSum() {
            return sum;
        }

        Result(int number, long sum) {
            this.number = number;
            this.sum = sum;
        }
    }

    private static final long TIME_LIMIT = 60_000_000_000L; // 60 seconds x 1e9 nanoseconds / second

    public static void main(String[] args) {
        SumOfSmallestFactors main = new SumOfSmallestFactors();
        Result result = main.run();
        int number = result.getNumber();
        long sum = result.getSum();
        System.out.format("T(%,d) = %,d\n", number, sum);
    }

    private int[] primes = new int[16_777_216];
    private int primeCount = 0;
    private long startTime;

    private SumOfSmallestFactors() {}

    private Result run() {
        startClock();
        int number;
        long sumOfSmallestFactors = 2;
        for (number = 3; mayContinue(); number += 2) {
            int smallestFactor = getSmallestFactor(number);
            if (smallestFactor == number) {
                addPrime(number);
            }
            sumOfSmallestFactors += smallestFactor + 2;
        }
        --number;

        Result result = new Result(number, sumOfSmallestFactors);
        return result;
    }

    private void startClock() {
        startTime = System.nanoTime();
    }

    private boolean mayContinue() {
        long currentTime = System.nanoTime();
        long elapsedTime = currentTime - startTime;
        boolean result = (elapsedTime < TIME_LIMIT);
        return result;
    }

    private int getSmallestFactor(int number) {
        int smallestFactor = number;
        int squareRoot = (int) Math.ceil(Math.sqrt(number));

        int index;
        int prime = 3;
        for (index = 0; index < primeCount; ++index) {
            prime = primes[index];

            if (prime > squareRoot) {
                break;
            }

            int remainder = number % prime;
            if (remainder == 0) {
                smallestFactor = prime;
                break;
            }
        }

        return smallestFactor;
    }

    private void addPrime(int prime) {
        primes[primeCount] = prime;
        ++primeCount;
    }
}

```

Running on a different system (Windows 8.1, Intel core i7 @ 2.5 GHz, 8 GB RAM) with the latest version of Java 8 has markedly better results with no code changes:

```
T(240,308,208) = 1,537,216,753,010,879

```
> 2 votes

# Answer
# R, 2.5e7

Simple minded sieve of Eratosthenes, vectorised as much as possible. R's not really designed for this sort of problem and I'm pretty sure it can be made faster.

```
MAX <- 2.5e7
Tot <- 0
vec <- 2:MAX
while(TRUE) {
    if (vec[1]*vec[1] > vec[length(vec)]) {
        Tot <- Tot + sum(as.numeric(vec))
        break
    }

    fact <- which(vec %% vec[1] == 0)
    Tot <- Tot + vec[1]*length(vec[fact])
    vec <- vec[-fact]
}
Tot

```
> 1 votes

# Answer
## Python, ~7e8

Using an incremental Sieve of Erathostenes. Some care does need to be taken that a marked value is marked with its lowest divisor, but the implementation is otherwise fairly straight forward.

Timing was taken with PyPy 2.6.0, input is accepted as a command line argument.

```
from sys import argv
from math import sqrt

n = int(argv[1])
sieve = {}
imax = int(sqrt(n))

t = n & -2
i = 3
while i <= n:
  divs = sieve.pop(i, [])
  if divs:
    t += divs[-1]
    for v in divs:
      sieve.setdefault(i+v+v, []).append(v)
  else:
    t += i
    if i <= imax: sieve[i*i] = [i]
  i += 2

print t

```

---

**Sample Usage**

```
$ pypy sum-lpf.py 10000
5786451

$ pypy sum-lpf.py 100000000
279218813374515

```
> 1 votes

# Answer
# Common Lisp, 1e7

```
(defvar input 10000000)
(defvar numbers (loop for i from 2 to input collect i))
(defvar counter)
(defvar primes)

(setf primes (loop for i from 2 to (floor (sqrt input))
    when (loop for j in primes
        do (if (eq (mod i j) 0) (return nil))
        finally (return t))
    collect i into primes
    finally (return primes)))

(format t "~A~%"
    (loop for i in primes
        do (setf counter 0)
        summing (progn (setf numbers (remove-if #'(lambda (x) (if (eq (mod x i) 0) (progn (incf counter) t))) numbers))
                (* i counter)) into total
        finally (return (+ total (reduce #'+ numbers)))))

```

I've opted to first generate a list of prime numbers from 2 to `(sqrt input)`, then test every value with the primes, whereas previously I would test against every number up to `(sqrt input)`, which would be pointless (e.g., if a number is divisible by 4, it's also divisible by 2, so it's already accounted for.)

Thank God for side-effects while I'm at it. The remove-if both lowers the size of the list and counts how many elements were removed, so I just have to multiply that by whatever value the loop is on and add that into the running total.

(Fun fact: `delete` is the destructive equivalent of `remove`, but for whatever reason, `delete` is all sorts of slower than `remove` in this case.)
> 0 votes

# Answer
## Java 2.14e9

## Pure Sieve of Eratosthenes with advantage of BitSet

I have calculated the Smallest Prime factor sum upto `Integer.MAX_VALUE - 1` just in `33.89 s`. But I can't proceed any larger because any further will lead to Integer Overflow on the Size of Bitset. So I'm working on to create another Bitset for the next set of Ranges. Until then, this is the fastest I'm able to generate.

---

```
T(214,74,83,646) = 109931450137817286 in 33.89 s
aka
T(2,147,483,646) = 109931450137817286 in 33.89 s

```

---

```
import java.util.BitSet;

public class SmallPrimeFactorSum {

    static int    limit     = Integer.MAX_VALUE - 1;

    // BitSet is highly efficient against boolean[] when Billion numbers were involved
    // BitSet uses only 1 bit for each number
    // boolean[] uses 8 bits aka 1 byte for each number which will produce memory issues for large numbers
    static BitSet primes    = new BitSet(limit + 1);
    static int    limitSqrt = (int) Math.ceil(Math.sqrt(limit));

    static long   start     = System.nanoTime();

    static long   sum       = 0;

    public static void main(String[] args) {
        genPrimes();
    }

    // Generate Primes by Sieve of Eratosthenes
    // Sieve of Eratosthenes is much efficient than Sieve of Atkins as
    // Sieve of Atkins involes Division, Modulus, Multiplication, Subtraction, Addition but
    // Sieve of Eratosthenes involves only addition
    static void genPrimes() {

        // Inverse the Bit values
        primes.flip(0, limit + 1);

        // Now all Values in primes will now be true,
        // True  represents     prime number
        // False represents not prime number

        // Set 0 and 1 as not Prime number
        primes.clear(0, 2);

        // Set all multiples of each Prime as not Prime;
        for ( int prime = 2; prime > 0 && prime <= limit && prime > 0; prime = primes.nextSetBit(prime + 1) ) {
            // Add Current Prime as its Prime factor
            sum += prime;
            // Skip marking if Current Prime > SQRT(limit)
            if ( prime > limitSqrt ) {
                continue;
            }
            // Mark Every multiple of current Prime as not Prime
            for ( int multiple = prime + prime; multiple <= limit && multiple > 0; multiple += prime ) {
                // Mark as not Prime only if it's true already
                if ( primes.get(multiple) ) {
                    // Add Current Prime as multiple's Prime factor
                    sum += prime;
                    primes.clear(multiple);
                }
            }
        }

        System.out.printf("T(%d) = %d in %.2f s", limit, sum, (System.nanoTime() - start) / 1000000000.0);
        //System.out.printf("Total Primes upto %d : %d\n", limit, primes.cardinality());
    }

}

```
> 0 votes

# Answer
# Julia, 5e7

Surely Julia can do better but this is what I have for now. This does 5e7 in about 60 seconds on JuliaBox but I can't test locally yet. Hopefully by then I'll have thought of a more clever approach.

```
const PRIMES = primes(2^16)

function lpf(n::Int64)
    isprime(n) && return n
    for p in PRIMES
        n % p == 0 && return p
    end
end

function T(N::Int64)
    local x::Int64
    x = @parallel (+) for i = 2:N
        lpf(i)
    end
    x
end

```

Here we're creating a function `lpf` that iterates through sequential primes and checks the input for divisibility by each. The function returns the first divisor encountered, thereby obtaining the least prime factor.

The main function computes `lpf` on the integers from 2 to the input in parallel and reduces the result by summing.
> 0 votes

# Answer
**Rust 1.5e9**

A very naive Eratosthene sieve, but I felt Rust did not receive any love here !

```
// Expected (approximate) number of primes
fn hint(n:usize) -> usize {
    if n < 2 {
        1
    } else {
        n / ((n as f64).ln() as usize) + 1
    }
}

fn main() {
    let n:usize = match std::env::args().nth(1) {
        Some(s) => s.parse().ok().expect("Please enter a number !"),
        None => 10000,
    };
    let mut primes = Vec::with_capacity(hint(n));
    let mut sqrt = 2;
    let s = (2..).map(|n:u32| -> u32 {
        if (sqrt * sqrt) < n {
            sqrt += 1;
        }
        let (div, unseen) = match primes.iter().take_while(|&p| *p <= sqrt).filter(|&p| n % p == 0).next() {
            Some(p) => (*p, false),
            None => (n, true),
        };
        if unseen {
            primes.push(div);
        }
        div
    }).take(n-1).fold(0, |acc, p| acc + p);
    println!("{}", s);
}

```
> 0 votes

---
Tags: math, fastest-code, primes, division
---


title: Implement bzip2's run-length encoding

text:
# Question
Title: Implement bzip2's run-length encoding
### Background

After applying the BWT (as seen in Burrows, Wheeler and Back) and the MTF (as seen in Move to the printable ASCII front), the bzip2 compressor applies a rather unique form of run-length encoding.

### Definition

For the purpose of this challenge, we define the transformation BRLE as follows:

Given an input string **s** that consists solely of ASCII characters with code points between 0x20 and 0x7A, do the following:

1. Replace each run of equal characters by a single occurrence of the character and store number of repetitions after the first.
2. Encode the number of repetitions *after the first occurrence of the character*, using bijective base-2 numeration and the symbols `{` and `}`.

A non-negative integer **n** is encoded as the string **bk…b0** such that **n = 2ki(bk)+…+20i(b0)**, where **i(`{`) = 1** and **i(`}`) = 2**.

Note that this representation is always unique. For example, the number **0** is encoded as an empty string.
3. Insert the string of curly brackets that encodes the number of repetitions after the single occurrence of the corresponding character.

# Step-by-step example

```
Input:  "abbcccddddeeeeeffffffggggggghhhhhhhh"
Step 1: "abcdefgh" with repetitions 0, 1, 2, 3, 4, 5, 6, 7
Step 2: "" "{" "}" "{{" "{}" "}{" "}}" "{{{"
Step 3: "ab{c}d{{e{}f}{g}}h{{{"

```

### Task

Implement an involutive program or function that reads a single string from STDIN or as command-line or function argument and prints or returns either the BRLE or its inverse of the input string.

If the input contains no curly brackets, apply the BRLE. If the input contains curly brackets, apply its inverse.

### Examples

```
INPUT:  CODEGOLF
OUTPUT: CODEGOLF

INPUT:  PROGRAMMING
OUTPUT: PROGRAM{ING

INPUT:  PUZ{LES
OUTPUT: PUZZLES

INPUT:  444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
OUTPUT: 4{{8{{{G{{{{W{{{{{

INPUT:  y}}}{{
OUTPUT: yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

```

### Additional rules

* You *cannot* use any built-ins that compute the BRLE or its inverse of a string.
* You *can* use built-ins that:

+ Compute the RLE or RLD of a string, as long as the number of repetitions is not stored in bijective base-2.
    + Perform base conversion of any kind.
* Your code may print a trailing newline if you choose STDOUT for output.
* Your code has to work for any input of 1000 or less ASCII characters in the range from 0x20 to 0x7A, plus curly brackets (0x7B and 0x7D).
* If the input contains curly brackets, you may assume that it is a valid result of applying the BRLE to a string.
* Standard code golf rules apply. The shortest submission in bytes wins.

# Answer
> 4 votes
# CJam, 50 48 bytes

```
l_{}`:T&1${_T#)_(@a?)+}%{(\2b)*}%@e`{(2b1>Tf=}%?

```

Thanks for Dennis for saving 2 bytes.

Try it online.

### Explanation

```
l_              e# Read and duplicate input.
{}`:T           e# T = "{}"
&               e# If the input has '{ or '}:
    1$          e# Input.
    {           e# For each character:
        _T#)    e# If it is '{ or '}:
            _(  e# Return 0 for '{ or 1 for '}.
            @a  e# Otherwise, convert the character itself to an array (string).
        ?
        )+      e# If it is a number, increment and append to the previous array.
                e# If it is a string with at least 1 character, do nothing.
    }%
    {(\         e# For each character and bijective base 2 number:
        2b)*    e# Repeat the character 1 + that many times.
    }%
                e# Else:
    @           e# Input.
    e`          e# Run-length encoding.
    {(          e# For each character and length:
        2b1>    e# Convert the length to base 2 and remove the first bit.
        Tf=     e# Map 0 to '{ and 1 to '}.
    }%
?               e# End if.

```

# Answer
> 3 votes
# Pyth, 48 ~~50~~ bytes

```
J`Hs?m*hdi+1xLJtd2tczf-@zTJUz@Jzsm+ed@LJtjhd2rz8

```

*2 bytes thanks to @Maltysen.*

Demonstration. Test harness.

Explanation:

```
J`Hs?m*hdi+1xLJtd2tczf-@zTJUz@Jzsm+ed@LJtjhd2rz8
                                                    Implicit: z = input()
                                                    H is empty dict.
J`H                                                 J = repr(H) = "{}"
   s                                                Print the concatenation of
    ?                        @Jz                    If z and J share any chars:
                     f     Uz                       Filter range(len(z))
                      -@zTJ                         On the absence of z[T] in J.
                   cz                               Chop z at these indices.
                                                    just before each non '{}'.
                  t                                 Remove empty initial piece.
     m*hd                                           Map to d[0] *
         i       2                                  the base 2 number
            xLJtd                                   index in J mapped over d[:-1]
          +1                                        with a 1 prepended.
                                             rz8    Otherwise, run len. encode z
                                 m                  map over (len, char)
                                         jhd2       Convert len to binary.
                                        t           Remove leading 1
                                     @LJ            Map to element of J.
                                  +ed               Prepend char.
                                s                   Concatenate.

```

# Answer
> 2 votes
# OCaml, 252

`t` is the function that does the transformation.

```
#load"str.cma"open Str
let rec(!)=group_beginning and
g=function|1->""|x->(g(x/2)^[|"{";"}"|].(x mod 2))and($)i s=if g i=s then i else(i+1)$s and
t s=global_substitute(regexp"\(.\)\1*\([{}]*\)")(fun s->String.make(1$matched_group 2 s)s.[!1]^g(!2- !1))s

```

At first I was thinking I had to check for the presence of curly braces, but it turned out to be unnecessary. The decoding clearly has no effect on strings that are already decoded, and the encoding part proved equally harmless to ones that were already encoded.

# Answer
> 1 votes
# JavaScript (*ES6*), 162

```
f=s=>
(t=s[R='replace'](/[^{}][{}]+/g,n=>n[0].repeat('0b'+n[R](/./g,c=>c!='{'|0))))==s
?s[R](/(.)\1*/g,(r,c)=>c+r.length.toString(2).slice(1)[R](/./g,c=>'{}'[c])):t

// TEST
out=x=>O.innerHTML += x + '\n';

test=s=>O.innerHTML = s+' -> '+f(s) +'\n\n' + O.innerHTML;

[['CODEGOLF','CODEGOLF']
,['PROGRAMMING','PROGRAM{ING']
,['PUZ{LES','PUZZLES']
,['444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW','4{{8{{{G{{{{W{{{{{']
,['y}}}{{','yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy']]
.forEach(v=>{
  w=f(v[0])
  out('Test ' + (w==v[1]?'OK':'Fail')+'\nInput:    '+v[0]+'\nExpected: '+v[1]+'\nResult:   '+w)
})
```

```
Your test: <input id=I style='width:300px'><button onclick='test(I.value)'>-></button>
<pre id=O></pre>
```

**Some explanation**

Number *n* to BB2 using 0 and 1: `(n+1).toString(2).slice(1)`

String in BB2 to number: to\_number ("0b1"+string) - that is, add a leftmost 1 binary digit and convert from binary (and decrease by 1, not needed in this specific instance).

Regular expression to find any character followed by `{` or `}`: `/[^{}][{}]+/g`

Regular expression to find repeated characters: `/(.)\1*/g`

Using that regexp in replace, first param is the "repeated" char (eventually repeat just 1 time), second param is the total repeated string, whose length is the number that I need to encode in BB2 *already incremented by 1*

... then put all together ...

---
Tags: code-golf, string, compression, encoding
---


title: Rebuilding an ASCII City

text:
# Question
Title: Rebuilding an ASCII City
```
     +--+
+--+ |  | +--+ +--+
|  | |  | |  | |  |
+--+ +--+ +--+ +--+

```

The people of ASCIIville are rebuilding their city and are sketching out new blueprints. Your job is to draw their new city based on how many buildings they want.

The input will be how many buildings there are. Each building is half the hight of the input (rounded up if odd), not including the top and bottom of the building.

Let's draw a basic example of `4`

```
+--+ +--+ +--+ +--+
|  | |  | |  | |  |
|  | |  | |  | |  |
+--+ +--+ +--+ +--+

```

As you can see here, there are two `|`s in every building because the input was four. *But there's a catch!* (meaning the example above is incorrect, and the example at the top of this post is the *real* output for 4)

For each building that isn't a prime number, its height goes down by one. If the number is divisible by *3*, *5*, or *10*, it goes down one more. If it's divisible by two or more of those numbers, the amount deducted adds up (*10 is divisible by 10 and 5, and it's not a prime, so it gets deducted by 3*).

Let's look at an example with an input of `5`.

```
     +--+
+--+ |  | +--+ +--+ +--+
|  | |  | |  | |  | |  |
|  | |  | |  | |  | |  |
+--+ +--+ +--+ +--+ +--+

```

Here's an example of `7`

```
     +--+                     +--+
+--+ |  | +--+ +--+ +--+      |  |
|  | |  | |  | |  | |  | +--+ |  |
|  | |  | |  | |  | |  | |  | |  |
|  | |  | |  | |  | |  | |  | |  |
+--+ +--+ +--+ +--+ +--+ +--+ +--+

```

And an example of `10`

```
     +--+                     +--+
+--+ |  | +--+ +--+ +--+      |  | +--+
|  | |  | |  | |  | |  | +--+ |  | |  | +--+
|  | |  | |  | |  | |  | |  | |  | |  | |  | +--+
|  | |  | |  | |  | |  | |  | |  | |  | |  | |  |
|  | |  | |  | |  | |  | |  | |  | |  | |  | |  |
+--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+ +--+

```

And back to `6`

```
     +--+
+--+ |  | +--+ +--+ +--+
|  | |  | |  | |  | |  | +--+
|  | |  | |  | |  | |  | |  |
+--+ +--+ +--+ +--+ +--+ +--+

```

**Rules:**

* If a number gets deducted so much that it's height is less than or equal to zero, it is not shown but a space is left for it (I don't believe this is possible, `6` is the closest I've found to reaching zero).
* Trailing spaces are allowed.
* The width of each building must be 2.
* Your input can be from stdin or encoded into the program.
* Your program must be a *full program*, no functions.
* Your program must be able 4-15 builds. 0-3 and negative numbers aren't needed and are not specified to do anything, meaning they can throw an error, print garbage, or do nothing.

# Answer
# CJam, ~~68 66 58~~ 55 bytes

This is too long for now. But a start.

```
ri:K"!;tK"206b4b<{S5*a*"+--+ "a:I+K)2/)"|  | "e]I+}%zN*

```

*UPDATE: Now hardcoding for inputs till 15 instead of calculating the offset. Suggestion by Sp3000*

Try it online here
> 4 votes

# Answer
# Python 2, 247 245 237 229 bytes

```
I=input()
R=range
B=[(-~I/2)-(x%3<1)-(x%5<1)-(x%10<1)-(~all([x%a for a in R(2,x)]or[x==2])+2)for x in R(1,I+1)]
E='+--+'
O=['\n']*I
for r in R(I):
 for h in B:O[r]+=['|  |',' '*4,E][(r==h)+(r>=h)]
print ''.join(O[::-1])+'\n'+E*I

```
> 3 votes

# Answer
## C#, 223 205 bytes

This takes advantage of the need to only go to 15 buildings.

```
class P{
    static void Main(string[]a){
        int w=int.Parse(a[0]),
            h=(w+3)/2,
            b,
            x,
            y=-1;
        for(;++y<=h;)
            for(x=-2;++x<w;)
                System.Console.Write(x<0?"\n":(b=y-("012021101211102"[x]&7))<0?"     ":b>0&y<h?"|  | ":"+--+ ");
    }
}

```

### 260 bytes

And a more generic answer that will work for any number of buildings.

```
class P{
    static void Main(string[]a){
        int w=int.Parse(a[0]),
            h=(w+3)/2,
            b,
            x,
            y=-1;
        for(;++y<=h;)
            for(x=-2;++x<w;){
                if(x<1)
                    b=-1;
                else
                    for(b=1;++b<x;)
                        if((x+1)%b<1)break;
                System.Console.Write(x<0?"\n":(b=y-x%3/2-x%5/4-x%10/9-(b<x?0:1))<0?"     ":b>0&y<h?"|  | ":"+--+ ");
            }
    }
}

```
> 3 votes

# Answer
# Groovy, ~~234~~, ~~225~~, ~~223~~ 219 bytes

Abusing the 15 building limit

```
b=args[0]as int
m={n->(n!=2&(2..n-1).any{n%it==0}?1:0)+([3,5,10].sum{n%it==0?1:0})}
(9..0).each{println((1..b).collect{d=((b/2)as int)+1-m(it);(0..9).collect{it!=d&it!=0?it<d?"|  |":"    ":"+--+"}}*.get(it).join(" "))}

```
> 2 votes

# Answer
# Python 2, 163 bytes

```
n=input()
k=-~n/2
for i in range(k+2):
 s="";p=j=1
 while~n+j:a=(j%3<1)+(j%5<1)+(j%10<1)+(p%j<1);s+=" |+  -  - |+   "[(i>=a)+(i in{a,k+1})::3];p*=j*j;j+=1
 print s

```

The primality checking part borrows @xnor's algorithm from here.

If we hardcode the first 15 offsets, we can get **137 bytes**:

```
n=input()
k=-~n/2
for i in range(k+2):
 s=""
 for j in range(n):a=881740113>>2*j&3;s+=" |+  -  - |+   "[(i>=a)+(i in{a,k+1})::3]
 print s

```

I'm assuming trailing spaces at the end of each line is okay, but if the question meant trailing spaces after the entire output then it's +9 bytes for `.rstrip()`.
> 2 votes

# Answer
# Swift, ~~375~~, 350 bytes

```
import Darwin;let(B,u,z,d)=(4.0,1.0,0.0,2.0);let H=ceil(B/d);func p(n:Double)->Double{var D=d;while D<n{if n%D==0{return 1};D++};return n==1 ?1:0};for var h=z;h<H+2;h++ {for var b=u;b<=B;b++ {var m=b%3==0 ?u:z+b%5==0 ?1:0;m=min(2,b%10==0 ?m+1:m);m += p(b);if h<m {print("     ")}else if h==H+1||h==m {print("+--+ ")}else{print("|  | ")}};print("\n")}

```

Here is the indented code

```
import Darwin
let(B,u,z,d)=(4.0,1.0,0.0,2.0)
let H=ceil(B/d)
func p(n:Double)->Double{
     var D=d
    while D<n{
        if n%D==0{
            return 1
        }
        D++
    }
    return n==1 ?1:0
}
for var h=z;h<H+2;h++ {
    for var b=u;b<=B;b++ {
        var m=b%3==0 ?u:z+b%5==0 ?1:0
        m=min(2,b%10==0 ?m+1:m)
        m += p(b)
        if h<m {
            print("     ")
        }
        else if h==H+1||h==m {
            print("+--+ ")
        }
        else{
            print("|  | ")
        }
    }
    print("\n")
}

```

`B` contains the number of buildings.
`p` returns 1 when a number is not prime.

I need to import Foundation in order to use the `ceil` function.

I didn't managed to optimize the code for just the fifteen cases, but I will eventually make it later.

edit: Taking @Kametrixom advice and optimize the `mod` part (I forgot to reduce var name length).
> 2 votes

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


title: Schedule a 4-way stop

text:
# Question
Title: Schedule a 4-way stop
A bunch of cars are lined up at a 4-way stop sign waiting to proceed. Everyone is confused about who gets to go next, who is going which way, etc. Clearly suboptimal.

Your job is to schedule the traffic at the stop sign in an optimal fashion.

You receive as input 4 strings of turn requests, one for each of the four cardinal directions. Each request is either `L` for left, `S` for straight, or `R` for right.

```
LLSLRLS
SSSRRSRLLR
LLRLSR
RRRLLLL

```

The first row is the lineup at the North entrance to the intersection. The first car in line wishes to turn left (that is, exit East). The subsequent rows are for the incoming East, South, and West entrances. So the first car coming from the West wishes to exit South.

Traffic moves in a series of steps. At each step, you must choose a subset of the cars at the head of their lines to proceed. The cars chosen must not *interfere* with each other. Two cars interfere if they exit the same direction or if they must cross each other's path (given standard right-hand driving rules). So two opposite cars both wishing to go straight may go at the same step. So may 4 cars all wishing to turn right. Two opposite cars can both turn left simultaneously.

Your job is to schedule the intersection in a minimum series of steps. For each step, output a line with the incoming cars' compass direction(s) listed. For the example above, the minimal schedule is 14 steps. One minimal schedule is:

```
N    [L from North]
E    [S from East]
E    [S from East]
E    [S from East]
NESW [L from North, R from East, L from South, R from West]
NE   [S from North]
EW   [R from East]
NESW [L from North, R from East, L from South, R from West]
W    [L from West]
EW   [L from East, L from West]
NESW [R from North, L from East, R from South, L from West]
NES  [L from North, R from East, L from West]
NS   [S from North, S from South]
SW   [R from South, L from West]

```

Your program should be able to handle 50 cars in each line in under 1 minute. Input of the 4 strings and output of the schedule may be in any convenient manner for your language.

Shortest program wins.

A larger example:

```
RRLLSSRLSLLSSLRSLR
RLSLRLSLSSRLRLRRLLSSRLR
RLSLRLRRLSSLSLLRLSSL
LLLRRRSSRSLRSSSSLLRRRR

```

which requires a minimum of 38 rounds. One possible solution:

```
E
EW
E
ESW
S
NS
ES
NESW
NSW
ESW
ES
NSW
NS
NS
NW
EW
NSW
NS
EW
NES
EW
NSW
NE
E
NE
EW
E
E
EW
EW
EW
W
ESW
NSW
NSW
NS
NSW
NEW

```

# Answer
**Python, 1219 Bytes**

I didn't spend very much time/effort trying to golf this, but I might improve it if other answers start popping up. I use A\* search with an admissible heuristic, guaranteeing optimality. I am pretty sure (although I haven't bothered to confirm) that the heuristic is also consistent, meaning that it is *O*(dynamic programming).

The program reads in four lines from STDIN in the format you have specified, and prints the result to STDOUT, also in the format you specified.

```
from heapq import heappush,heappop
from itertools import combinations
N,E,S,W=range(4)
L="L"
R="R"
T="S"
d=[{L:E,R:W,T:S},{L:S,R:N,T:W},{L:W,R:E,T:N},{L:N,R:S,T:E}]
b=set([(N,S,W,E),(N,S,E,W),(S,N,W,E),(S,N,E,W),(E,W,N,E),(N,S,W,N),(S,N,E,S),(W,E,S,W)])
for x in list(b):b.add(x[2:]+x[:2])
def v(*a):return a[1]!=a[3] and a not in b
i=lambda:raw_input()+'\n'
i=map(lambda l:map(lambda e:("NESW"[l[0]],d[l[0]][e]), l[1]),enumerate((i()+i()+i()+i()).split()))
q=[]
heappush(q,(0,[],i))
while q:
    h,a,n=heappop(q)
    m=sum(map(bool,n))
    if m==0:
        print "\n".join(a)
        break
    for r in range(4,0,-1):
        f=False
        for c in combinations(range(4),r):
            l=True
            for i in c:
                if not n[i]:
                    l=False
                    break
            if not l:continue
            l=True
            for x,y in combinations(c,2):
                if not v(x,n[x][0][1],y,n[y][0][1]):
                    l = False
                    break
            if l==False:continue
            f=True
            e=list(n)
            for i in c:e[i]=e[i][1:]
            heappush(q,(m-r+min(map(len,e)),a+["".join([n[x][0][0] for x in c])],e))
        if f:break

```

Example usage:

```
$ time echo "RRLLSSRLSLLSSLRSLR\nRLSLRLSLSSRLRLRRLLSSRLR\nRLSLRLRRLSSLSLLRLSSL\nLLLRRRSSRSLRSSSSLLRRRR" | python 4way.py
NES
NEW
NSW
NS
NS
ESW
NS
NES
NEW
NS
NES
NSW
NS
NS
NSW
NW
NS
NS
NS
EW
ES
SW
EW
EW
SW
ES
EW
EW
EW
EW
E
EW
EW
EW
EW
EW
E
EW
echo   0.00s user 0.00s system 38% cpu 0.002 total
python 4way.py  0.02s user 0.01s system 90% cpu 0.030 total

```
> 3 votes

---
Tags: code-golf
---