Typescript class for finding the number of Costas arrays for any given order

costas-counter.ts

export class CostasCounter {
    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

    totalFound: number = 0;
    totalFoundCenter: number = 0;

    constructor(private order: number) {
        this.init();
    }

    private init(): void {
        this.curRow = 0;

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

    public count(): void {        
        let odd = this.order % 2 == 1;
        let middleMark = Math.floor(this.order / 2) + (odd ? 1 : 0);
        this.curRow = 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 && (this.curRow > 0 || i < middleMark));

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

            // Print progress every 100000th cycle
            if (loop++ % 100000 == 0) {
                let minutes = (Date.now() - t0) / 60000;
                console.log(`progress: ${(100 * this.estimatedProgress()).toFixed(4)}% searched at ${minutes.toFixed(2)} mins`);
            }

            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 order, we have found a Costas array
            if (this.curRow == this.order) {
                this.totalFound++;

                // Keep count of how many that has its first mark in the middle (only relevant for
                // odd orders) to be able to calculate total count when finished
                if (this.rows[0] == middleMark - 1)
                    this.totalFoundCenter++;

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

        } while (true);

        this.totalFound = odd
            ? (this.totalFound - this.totalFoundCenter) * 2 + this.totalFoundCenter
            : this.totalFound * 2;

        let secs = (Date.now() - t0) / 1000;
        console.log(`FINISHED: ${secs.toFixed(1)} secs`);
        console.log(`total found: ${this.totalFound}`);
    }

    private estimatedProgress(): number {
        let progress: number = 0;

        for (let i = 0; i < this.curRow; i++) {
            let order = i == 0 ? this.order / 2 : this.order;
            progress += this.rows[i] * 1 / Math.pow(order, i + 1);
        }

        return progress;
    }

    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;
    }
}