costas-multi-walk.ts

export class CostasMultiWalk {
    rows: number[]; // Holds the column index for each row point
    freeCols: boolean[]; // Keeps track of which columns that are still free (unoccupied)
    dv: string[]; // Holds the displacement vectors
    curRow: number; // Current row during search/backtracking

    constructor(private order: number) {
    }

    private init(): void {
        this.curRow = 0;
        this.rows = [];
        this.freeCols = [];
        this.dv = [];

        for (let i = 0; i < this.order; i++) {
            this.freeCols.push(true);
            this.rows.push(-1);
        }
    }

    public generateWalks(ofLength: number): CostasWalk[] {
        this.init();

        this.curRow = 0;

        let result: CostasWalk[] = [];
        let totalFound: number = 0;
        let totalFoundCenter: number = 0;
        let odd = this.order % 2 == 1;
        let middleMark = Math.floor(this.order / 2) + (odd ? 1 : 0);

        let t0 = Date.now();
        let loop = 0;

        do {
            let curCol = this.rows[this.curRow];

            // Find the next free column index that is larger than the current column index. No need to search beyond
            // the middle point since we simply can flip the array horizontally to get the rest
            // let nextCol = this.freeCols.findIndex((x, i) => x && i > curCol);
            let nextCol = this.freeCols.findIndex((x, i) => x && i > curCol && (this.curRow > 0 || i < middleMark));

            // Free the previous column
            if (curCol > -1)
                this.freeCols[curCol] = true;


            if (nextCol == -1) {
                // If there were no more free columns to try for this row..

                if (this.curRow == 0)
                    break; // Search is finished

                // If we're not finished, backtrack by removing the displacement vectors added by the current row point
                this.rows[this.curRow] = -1;
                this.curRow--;
                this.dv.splice(this.dv.length - this.curRow, this.curRow);
            }
            else {
                // Calculate new displacement vectors that would be added by this point                
                this.rows[this.curRow] = nextCol;
                let newDvs = this.calculateNewDisplacementVectors(this.curRow);
                let success = true;

                // Check if there are any duplicates..
                for (let i = 0; i < this.dv.length; i++)
                    if (newDvs.indexOf(this.dv[i]) > -1) {
                        success = false;
                        break;
                    }

                // If not, add displacement vectors and proceed to next row
                if (success) {
                    this.dv = this.dv.concat(newDvs);
                    this.freeCols[nextCol] = false;
                    this.curRow++;
                }
                else {
                    continue; // otherwise, continue search on this row
                }
            }

            // If we got to 'ofLength', we have a CostasWalk
            if (this.curRow == ofLength) {
                totalFound++;

                let cw = new CostasWalk();
                cw.order = this.order;
                cw.baseLength = ofLength;
                cw.rows = this.rows.slice(0, ofLength);
                cw.id = cw.rows.join("-");
                cw.result = [];

                result.push(cw);

                // Backtrack to continue search
                this.curRow--;
                this.dv.splice(this.dv.length - this.curRow, this.curRow);
            }

        } while (true);

        return result;
    }

    public continueWalk(walk: CostasWalk, runtimeMs?: number): void {
        this.init();

        this.curRow = walk.rows.length;
        let stopRow = walk.baseLength;

        walk.rows.forEach((c, index) => {
            this.rows[index] = c;
            this.freeCols[c] = false;
        }, this);

        for (let i = 1; i < this.curRow; i++)
            this.dv = this.dv.concat(this.calculateNewDisplacementVectors(i));

        let result: number[][] = [];
        let totalFound: number = 0;
        let totalFoundCenter: number = 0;
        let odd = this.order % 2 == 1;
        let middleMark = Math.floor(this.order / 2) + (odd ? 1 : 0);

        let t0 = Date.now();
        let cycle = 0;
        let cycleLimit = 50000;

        do {

            let curCol = this.rows[this.curRow];

            // Find the next free column index that is larger than the current column index. 
            // Middle point optimization is of no use here since we are never processing the first row
            let nextCol = this.freeCols.findIndex((x, i) => x && i > curCol);

            // Free the previous column
            if (curCol > -1)
                this.freeCols[curCol] = true;

            if (nextCol == -1) {
                // If there were no more free columns to try for this row..

                if (this.curRow == stopRow)
                    break; // Search is finished

                // If we're not finished, backtrack by removing the displacement vectors added by the current row point
                this.rows[this.curRow] = -1;
                this.curRow--;
                this.dv.splice(this.dv.length - this.curRow, this.curRow);
            }
            else {
                // Calculate new displacement vectors that would be added by this point                
                this.rows[this.curRow] = nextCol;
                let newDvs = this.calculateNewDisplacementVectors(this.curRow);
                let success = true;

                // Check if there are any duplicates..
                for (let i = 0; i < this.dv.length; i++)
                    if (newDvs.indexOf(this.dv[i]) > -1) {
                        success = false;
                        break;
                    }

                // If not, add displacement vectors and proceed to next row
                if (success) {

                    this.dv = this.dv.concat(newDvs);
                    this.freeCols[nextCol] = false;
                    this.curRow++;

                    if (runtimeMs && ++cycle > cycleLimit && this.curRow < this.order) {
                        if ((Date.now() - t0) >= runtimeMs)
                            break;
                        else
                            cycle = 0;
                    }
                }
            }

            // If we got to order, we have found a Costas array
            if (this.curRow == this.order) {
                result.push(this.rows.slice());

                // Backtrack to continue search
                this.curRow--;
                this.dv.splice(this.dv.length - this.curRow, this.curRow);
            }

        } while (true);
        
        walk.finished = this.curRow == stopRow;
        walk.rows = this.rows.slice(0, this.curRow);
        result.forEach(x => walk.result.push(x));
        walk.runtime = Date.now() - t0;               
    }

    private calculateNewDisplacementVectors(row: number): string[] {
        let dv: string[] = [];

        for (let i = 0; i < row; i++)
            dv.push(`${this.rows[row] - this.rows[i]},${row - i}`);

        return dv;
    }
}

export class CostasWalk {
    id: string;
    order: number;
    baseLength: number;
    rows: number[];
    active: boolean = false;
    finished: boolean = false;
    result: number[][];
    runtime: number;
}