eu300.d

import std.stdio, std.parallelism, std.range, std.algorithm;

enum L = 12; 

struct V {int x,y;}

int optLen(int seed) {
    int[32*32] field;
    V[4] vecs = [V(1,0), V(0,-1), V(-1,0), V(0,1)];
    V[L] path;

    int fld(V p) { return field[p.y*32+p.x]; }
    void set(V p, int v) { field[p.y*32+p.x] = v; }
    V step(V p, int ang) {
        auto v = vecs[ang & 3];
        return V(p.x+v.x, p.y+v.y);
    }

    int[L] dna;
    foreach(i; 0..L) {
        if (seed & (1 << i)) dna[i] = 2;
        else dna[i] = 1;
    }

    int cpn() {
        int n = 0;
        foreach(p; path) {
            if (fld(p)==1) {
                if (fld(V(p.x+1, p.y))==1) n++;
                if (fld(V(p.x, p.y+1))==1) n++;
            }
        }
        return n;
    }

    int maxcpn = 0; 

    void draw(int n, V p, int angle) {
        if (fld(p) != 0) return; // busy cell       
        set(p, dna[n]);
        path[n] = p;
        
        if (n==L-1) { // all drawn
            auto cp = cpn();
            if (cp > maxcpn) 
                maxcpn = cp;            
            set(p, 0);
            return;
        }

        draw(n+1, step(p, angle), angle);
        draw(n+1, step(p, angle-1), (angle-1)&3);
        draw(n+1, step(p, angle+1), (angle+1)&3);
        set(p, 0);
    }

    auto p0 = V(16,16);
    set(p0, dna[0]); path[0] = p0;
    draw(1, V(17,16), 0);
    return maxcpn;
}

void main() {   
    auto lens = iota(1<<L).map!optLen;
    taskPool.reduce!"a+b"(lens).writeln;
}

//                        L=13 1-thread  parallel ; L=14 parallel
// Intel Core i7 2.6 GHz           20.0      4.06 ;         22.02
// M1 running x86_64              15.65      3.15 ;         18.06
// M1 running arm64               11.84      2.44 ;         13.7
//                                       time in seconds
//L=15 Intel parallel: 138.770351 sec

// https://projecteuler.net/problem=300