// LL 2021

const display = 0; // min=0 max=274 step=1

Canvas.setpenopacity(-1);
const turtle = new Turtle();

function walk(i) {
    if (i==0) {
        for (var j=1; j<=9; j++) {
            drawDot(j);
        }
        slow = !display;
        target = display ? (display-1) : (Math.random() * 120 | 0);
        return true;
    }
    
    if (i==1) {
        getSolutions();
        if (target >= solutions.length) return false;
        console.log(`target: ${target+1} - solution: ${solutions[target]} - count: ${solutions.length}`);
        return true;
    }
    
    if (solutions[target].length < 2) return false;

    drawLine(solutions[target][0], solutions[target][1]);
    solutions[target].shift();
    sleep(100);

    return true;
}

const dslopes = [ [1, 0], [0, 1], [1, -1], [1, 1], [-1, 2], [1, 2], [-2, 1], [2, 1] ];

function getSolutions() {
    solutions = [];

    const solver = new Solver();

    var attempts = 0;
    while (++attempts < 100000) {
        const pattern = solver.iterate();
        if (isGood(pattern)) {
        	solutions.push(pattern);
        }
        if (solver.current_dot > 8) break;
    }
    
    solutions.sort(function(a, b) {
        for (var i = 0, c = Math.min(a.length, b.length); i < c; i++) {
            if (a[i] != b[i]) return a[i] - b[i];
        }
        return a.length - b.length;
    });
}

class Solver {
    constructor(start_dot = 1, start_slopes = [], depth = 0) {
        this.current_dot = start_dot;
        this.start_slope_count = start_slopes.length;
        this.used_slopes = [...start_slopes];
        this.available_slopes = [];
        this.depth = depth;
        for (var j = 1; j <= 8; j++) {
			var included = false;
			for (var k=0; k<this.used_slopes.length && !included; k++) {
				included |= j == this.used_slopes[k];
				included |= -j == this.used_slopes[k];
			}

            if (!included) {
                this.available_slopes.push(j);
            }
        }
        this.findOptions();
        this.child_solver = undefined;
    }
    
    findOptions() {
        this.options = [];
        this.available_slopes.forEach(slope => {
            for (var flip = -1; flip <= 1; flip += 2) {
                this.used_slopes.push(slope * flip);
                const new_pattern = getPattern(this.current_dot, this.used_slopes);
                if (new_pattern.length > 0) this.options.push(slope * flip);
                this.used_slopes.pop();
            }
        });
    }
    
    iterate() {
        if (this.used_slopes.length == 8) {
            const slopes = this.used_slopes;
            this.used_slopes = [];
            return getPattern(this.current_dot, slopes);
        }

        if (this.child_solver !== undefined) {
            const pattern = this.child_solver.iterate();
            if (this.child_solver.child_solver === undefined && this.child_solver.options.length < 1) {
            	this.child_solver = undefined;
            }
            return pattern;
        }

        if (this.current_dot > 9) return [];
        if (this.options.length < 1) {
        	if (this.depth == 0) {
        		this.current_dot++;
        		this.findOptions();
        	}
        	return [];
        }

        const option = this.options.shift();
        
        const new_slopes = (this.used_slopes.length > 0) ? [...this.used_slopes, option] : [ option ];
        this.child_solver = new Solver(this.current_dot, new_slopes, this.depth + 1);
        return this.child_solver.iterate();
    }
}

function getPattern(start_dot, slopes) {
    const pattern = [ start_dot ];
    for (var j=0; j<slopes.length; j++) {
        var next_dot = nextDot(pattern[pattern.length-1], slopes[j], 1);
        if (next_dot < 0) return [];
        if (pattern.includes(next_dot)) {
        	next_dot = nextDot(pattern[pattern.length-1], slopes[j], 2);
        	if (next_dot < 0) return [];
       	}
        pattern.push(next_dot);
    }
    return pattern;
}

function isGood(pattern) {
	if (pattern.length != 9) return false;
    for (var i=0; i<9; i++) {
    	for (var j=i+1; j<9; j++) {
    		if (pattern[i] == pattern[j]) return false;
    	}
    }
    return true;
}

function nextDot(dot, slope_index, step) {
    const flip = (slope_index < 0) ? -1 : 1;
    const dx = dslopes[Math.abs(slope_index)-1][0] * flip * step;
    const dy = dslopes[Math.abs(slope_index)-1][1] * flip * step;
    const x = (dot-1) % 3, y = (dot-1) / 3 | 0;
    if (x+dx < 0 || x+dx > 2 || y+dy < 0 || y+dy > 2) return -1;
    return x + dx + (y + dy) * 3 + 1;
}

function drawDot(index) {
    const x = (-1 + ((index-1) % 3)) * 60, y = (-1 + ((index-1) / 3 | 0)) * 60;
    for (var r = 6; r > 0; r -= .15) turtle.jump(x, y - r), turtle.circle(r, 0, 50);
}

function drawLine(index0, index1) {
    const cx0 = (-1 + ((index0-1) % 3)) * 60, cy0 = (-1 + ((index0-1) / 3 | 0)) * 60;
    const cx1 = (-1 + ((index1-1) % 3)) * 60, cy1 = (-1 + ((index1-1) / 3 | 0)) * 60;
    const thickness = 1, steps = 60;
    for (var j = 0, a = 0; j < steps; j++, a += Math.PI * 2 / steps) {
        const x0 = cx0 + thickness * Math.cos(a), y0 = cy0 + thickness * Math.sin(a);
        const x1 = cx1 + thickness * Math.cos(a), y1 = cy1 + thickness * Math.sin(a);
        turtle.jump(x0, y0); turtle.goto(x1, y1);
    }
}

function sleep(ms) {
    if (!slow) return;
    const start = Date.now();
    while (Date.now()-start < ms);
}