mkrause · August 11, 2018 18:20
diff --git a/spectacular_spiders.js b/spectacular_spiders.js
 /*
 "Spectacular Spiders" puzzle.
 */

 "use strict";

 /*

 piece: particular puzzle piece (physical object)
 placement: a piece in a certain orientation (placed on a tile)
 grid: the abstract 3x3 grid of tiles
 tile: one particular tile in the grid

 solution: list of (sequential) placements, possibly intermediate
 solution set: set of solutions

 */

 // Copy an arbitrary array
 function copy(arr) {
    return arr.slice(0);
 }

 // Size of the (square) grid
 var gridSize = 3;

 // Piece definitions: the numbers refer to specific spiders, the sign the side shown
 // The numbers are in order: top, right, bottom, left
 // 1: RB
 // 2: FW
 // 3: W
 // 4: R
 // +: head
 // -: tail
 var pieces = [
    [+1, -3, +2, -1], // 0
    [-2, +3, +1, +3], // 1
    [+4, -4, -2, -3], // 2
    [-2, -4, -1, -4], // 3
    [-1, +2, -3, +4], // 4
    [+2, -1, +4, -2], // 5
    [+1, +3, +3, +2], // 6
    [+3, +1, +4, -3], // 7
    [-4, +2, -4, -1] // 8
 ];

 // orientations:
 // 0: 0deg CW
 // 1: 90deg CW
 // 2: 180deg CW
 // 3: 270deg CW
 var orient = {
    up: 0,
    right: 1,
    down: 2,
    left: 3
 };

 function Placement(piece, orientation) {
    this.piece = piece;
    this.orientation = orientation;
 }

 // Return a rotated version of this placement (by N quarter turns clockwise)
 Placement.prototype.rotated = function(turns) {
    return new Placement(this.piece, (this.orientation + turns) % 4);
 };

 Placement.prototype.toString = function() {
    var rep = "" + this.piece;
    switch (this.orientation) {
        case orient.up:
            rep += '^';
            break;
        case orient.right:
            rep += '>';
            break;
        case orient.down:
            rep += 'v';
            break;
        case orient.left:
            rep += '<';
            break;
    }
    
    return rep;
 };

 function Sequence(sequence, placement) {
    this.placements = [];
    
    // Create a new sequence from an existing one
    if (sequence) {
        this.placements = copy(sequence.placements);
    }
    
    // Add one placement
    if (placement) {
        this.placements.push(placement);
    }
 }

 Sequence.prototype.validPlacements = function() {
    // Pieces already placed
    var usedPieces = this.placements.map(function(placement) {
        return placement.piece;
    });
    
    // Pieces not yet placed
    var remainingPieces = [0, 1, 2, 3, 4, 5, 6, 7, 8]
        .filter(function(index) {
            return usedPieces.indexOf(index) === -1;
        });
    
    var validPlacements = [];
    for (var pieceKey in remainingPieces) {
        var piece = remainingPieces[pieceKey];
        var orientations = [orient.up, orient.right, orient.down, orient.left];
        for (var orientationKey in orientations) {
            var orientation = orientations[orientationKey];
            var placement = new Placement(piece, orientation);
            
            // Try a placement, see if it matches
            if (!matches(placement, this)) {
                continue;
            }
            
            validPlacements.push(placement);
        }
    }
    
    return validPlacements;
 };

 // Source: http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array
 Sequence.prototype.rotated90 = function() {
    var seq = new Sequence(this);
    
    var n = gridSize;
    for (var i = 0; i < n; i++) { // Row index
        for (var j = 0; j < n; j++) { // Column index
            // Current placement
            var placement = this.placements[i * n + j];
            
            // Change orientation by 90deg CW
            var newOrient = (placement.orientation + 1) % 4;
            
            // Transpose, with each row in the transposed matrix reversed
            seq.placements[(n - 1 - i) + j * n] = new Placement(placement.piece, newOrient);
        }
    }
    
    return seq;
 }

 // Return a normalized version of this sequence (i.e. independent of grid orientation)
 Sequence.prototype.normalized = function() {
    var normalized = null;
    var rotated = new Sequence(this);
    
    // Rotate four times, then always select the same rotation
    // according to a fixed rule (here, lowest piece/orientation index up front)
    var currentLowestPiece = Infinity;
    var currentLowestOrientation = Infinity;
    for (var i = 0; i < 4; i++) {
        rotated = rotated.rotated90();
        if (rotated.placements[0].piece <= currentLowestPiece
            && rotated.placements[0].orientation < currentLowestOrientation) {
            normalized = rotated;
            currentLowestPiece = rotated.placements[0].piece;
            currentLowestOrientation = rotated.placements[0].orientation;
        }
    }
    
    return normalized;
 };

 Sequence.prototype.toString = function() {
    var pl = this.placements.map(function(placement) {
        return placement.toString();
    });
    
    var strRep = pl.slice(0,3).join(' ') + '\n'
        + pl.slice(3,6).join(' ') + '\n'
        + pl.slice(6,9).join(' ') + '\n';
    
    return strRep;
 };

 // Determine whether a placement matches a prior sequence
 // Needs to match potentially two placements: one to the left, one above
 function matches(placement, sequence) {
    // console.log(sequence.toString(), placement.toString());
    
    // Index of the tile where the new placement will be added
    var tileIndex = sequence.placements.length;
    
    var matchesBefore = true;
    var matchesAbove = true;
    
    // If the piece is not at the left edge of the grid, check
    // its placement to the left
    if (tileIndex % gridSize !== 0) {
        var placement1 = sequence.placements[tileIndex - 1];
        var placement2 = placement;
        
        // Compare
        var piece1 = placement1.piece;
        var piece2 = placement2.piece;
        // Note: need to start from 4 to prevent -1 % 4 == -1
        var spiderIndex1 = (4 + (orient.right - placement1.orientation)) % 4;
        var spiderIndex2 = (4 + (orient.left - placement2.orientation)) % 4;
        var spider1 = pieces[piece1][spiderIndex1];
        var spider2 = pieces[piece2][spiderIndex2];
        
        // Spiders should match up (e.g. -1 and +1)
        if (spider1 + spider2 !== 0) {
            matchesBefore = false;
        }
        
        // console.log(placement1.toString(), placement2.toString());
        // console.log(spider1, spider2);
    }
    
    // If the piece is not at the top edge of the grid, check
    // its placement above
    if (tileIndex >= gridSize) {
        var placement1 = sequence.placements[tileIndex - gridSize];
        var placement2 = placement;
        
        // Compare
        var piece1 = placement1.piece;
        var piece2 = placement2.piece;
        // Note: need to start from 4 to prevent -1 % 4 == -1
        var spiderIndex1 = (4 + (orient.down - placement1.orientation)) % 4;
        var spiderIndex2 = (4 + (orient.up - placement2.orientation)) % 4;
        var spider1 = pieces[piece1][spiderIndex1];
        var spider2 = pieces[piece2][spiderIndex2];
        
        // Spiders should match up (e.g. -1 and +1)
        if (spider1 + spider2 !== 0) {
            matchesAbove = false;
        }
    }
    
    // if (sequence.toString() == "6>, 3>, 0>" && placement.toString() == '7>') {
    //     console.log(sequence.toString(), placement.toString(), matchesBefore, matchesAbove);
    // }
    
    return matchesBefore && matchesAbove;
 }

 function placeOne(sequence) {
    var newSequences = [];
    
    var validPlacements = sequence.validPlacements();
    for (var placementKey in validPlacements) {
        var placement = validPlacements[placementKey];
        var validSequence = new Sequence(sequence, placement);
        newSequences.push(validSequence);
    }
    
    return newSequences;
 }

 // One recursive step of the search algorithm (breadth-first)
 function step(sequenceSet) {
    // Stop when no possible sequences
    if (sequenceSet.length == 0) {
        return [];
    }
    
    // Stop when at the last tile
    var terminationLength = gridSize * gridSize;
    if (sequenceSet[0].placements.length == terminationLength) {
        return sequenceSet;
    }
    
    var newSequenceSet = [];
    for (var sequenceKey in sequenceSet) {
        var sequence = sequenceSet[sequenceKey];
        var newSequences = placeOne(sequence);
        Array.prototype.push.apply(newSequenceSet, newSequences);
    }
    
    return step(newSequenceSet);
 }

 // Run the search algorithm
 var initialSequence = new Sequence();
 var solutionSet = step([initialSequence]);

 // Normalize solutions
 var normalizedSolutionSet = solutionSet.map(function(solution) {
    return solution.normalized();
 });

 // Make unique
 var uniqNormalizedSolutionSet = {};
 normalizedSolutionSet.forEach(function(solution) {
    var strRep = solution.toString();
    uniqNormalizedSolutionSet[strRep] = solution;
 });

 // Print solutions
 for (var solutionKey in uniqNormalizedSolutionSet) {
    var solution = uniqNormalizedSolutionSet[solutionKey];
    console.log("Solution:");
    console.log(solution.toString());
 }

 console.log("Number of solutions: " + Object.keys(uniqNormalizedSolutionSet).length);
	/*
	"Spectacular Spiders" puzzle.
	*/

	"use strict";

	/*

	piece: particular puzzle piece (physical object)
	placement: a piece in a certain orientation (placed on a tile)
	grid: the abstract 3x3 grid of tiles
	tile: one particular tile in the grid

	solution: list of (sequential) placements, possibly intermediate
	solution set: set of solutions

	*/

	// Copy an arbitrary array
	function copy(arr) {
	return arr.slice(0);
	}

	// Size of the (square) grid
	var gridSize = 3;

	// Piece definitions: the numbers refer to specific spiders, the sign the side shown
	// The numbers are in order: top, right, bottom, left
	// 1: RB
	// 2: FW
	// 3: W
	// 4: R
	// +: head
	// -: tail
	var pieces = [
	[+1, -3, +2, -1], // 0
	[-2, +3, +1, +3], // 1
	[+4, -4, -2, -3], // 2
	[-2, -4, -1, -4], // 3
	[-1, +2, -3, +4], // 4
	[+2, -1, +4, -2], // 5
	[+1, +3, +3, +2], // 6
	[+3, +1, +4, -3], // 7
	[-4, +2, -4, -1] // 8
	];

	// orientations:
	// 0: 0deg CW
	// 1: 90deg CW
	// 2: 180deg CW
	// 3: 270deg CW
	var orient = {
	up: 0,
	right: 1,
	down: 2,
	left: 3
	};

	function Placement(piece, orientation) {
	this.piece = piece;
	this.orientation = orientation;
	}

	// Return a rotated version of this placement (by N quarter turns clockwise)
	Placement.prototype.rotated = function(turns) {
	return new Placement(this.piece, (this.orientation + turns) % 4);
	};

	Placement.prototype.toString = function() {
	var rep = "" + this.piece;
	switch (this.orientation) {
	case orient.up:
	rep += '^';
	break;
	case orient.right:
	rep += '>';
	break;
	case orient.down:
	rep += 'v';
	break;
	case orient.left:
	rep += '<';
	break;
	}

	return rep;
	};

	function Sequence(sequence, placement) {
	this.placements = [];

	// Create a new sequence from an existing one
	if (sequence) {
	this.placements = copy(sequence.placements);
	}

	// Add one placement
	if (placement) {
	this.placements.push(placement);
	}
	}

	Sequence.prototype.validPlacements = function() {
	// Pieces already placed
	var usedPieces = this.placements.map(function(placement) {
	return placement.piece;
	});

	// Pieces not yet placed
	var remainingPieces = [0, 1, 2, 3, 4, 5, 6, 7, 8]
	.filter(function(index) {
	return usedPieces.indexOf(index) === -1;
	});

	var validPlacements = [];
	for (var pieceKey in remainingPieces) {
	var piece = remainingPieces[pieceKey];
	var orientations = [orient.up, orient.right, orient.down, orient.left];
	for (var orientationKey in orientations) {
	var orientation = orientations[orientationKey];
	var placement = new Placement(piece, orientation);

	// Try a placement, see if it matches
	if (!matches(placement, this)) {
	continue;
	}

	validPlacements.push(placement);
	}
	}

	return validPlacements;
	};

	// Source: http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array
	Sequence.prototype.rotated90 = function() {
	var seq = new Sequence(this);

	var n = gridSize;
	for (var i = 0; i < n; i++) { // Row index
	for (var j = 0; j < n; j++) { // Column index
	// Current placement
	var placement = this.placements[i * n + j];

	// Change orientation by 90deg CW
	var newOrient = (placement.orientation + 1) % 4;

	// Transpose, with each row in the transposed matrix reversed
	seq.placements[(n - 1 - i) + j * n] = new Placement(placement.piece, newOrient);
	}
	}

	return seq;
	}

	// Return a normalized version of this sequence (i.e. independent of grid orientation)
	Sequence.prototype.normalized = function() {
	var normalized = null;
	var rotated = new Sequence(this);

	// Rotate four times, then always select the same rotation
	// according to a fixed rule (here, lowest piece/orientation index up front)
	var currentLowestPiece = Infinity;
	var currentLowestOrientation = Infinity;
	for (var i = 0; i < 4; i++) {
	rotated = rotated.rotated90();
	if (rotated.placements[0].piece <= currentLowestPiece
	&& rotated.placements[0].orientation < currentLowestOrientation) {
	normalized = rotated;
	currentLowestPiece = rotated.placements[0].piece;
	currentLowestOrientation = rotated.placements[0].orientation;
	}
	}

	return normalized;
	};

	Sequence.prototype.toString = function() {
	var pl = this.placements.map(function(placement) {
	return placement.toString();
	});

	var strRep = pl.slice(0,3).join(' ') + '\n'
	+ pl.slice(3,6).join(' ') + '\n'
	+ pl.slice(6,9).join(' ') + '\n';

	return strRep;
	};

	// Determine whether a placement matches a prior sequence
	// Needs to match potentially two placements: one to the left, one above
	function matches(placement, sequence) {
	// console.log(sequence.toString(), placement.toString());

	// Index of the tile where the new placement will be added
	var tileIndex = sequence.placements.length;

	var matchesBefore = true;
	var matchesAbove = true;

	// If the piece is not at the left edge of the grid, check
	// its placement to the left
	if (tileIndex % gridSize !== 0) {
	var placement1 = sequence.placements[tileIndex - 1];
	var placement2 = placement;

	// Compare
	var piece1 = placement1.piece;
	var piece2 = placement2.piece;
	// Note: need to start from 4 to prevent -1 % 4 == -1
	var spiderIndex1 = (4 + (orient.right - placement1.orientation)) % 4;
	var spiderIndex2 = (4 + (orient.left - placement2.orientation)) % 4;
	var spider1 = pieces[piece1][spiderIndex1];
	var spider2 = pieces[piece2][spiderIndex2];

	// Spiders should match up (e.g. -1 and +1)
	if (spider1 + spider2 !== 0) {
	matchesBefore = false;
	}

	// console.log(placement1.toString(), placement2.toString());
	// console.log(spider1, spider2);
	}

	// If the piece is not at the top edge of the grid, check
	// its placement above
	if (tileIndex >= gridSize) {
	var placement1 = sequence.placements[tileIndex - gridSize];
	var placement2 = placement;

	// Compare
	var piece1 = placement1.piece;
	var piece2 = placement2.piece;
	// Note: need to start from 4 to prevent -1 % 4 == -1
	var spiderIndex1 = (4 + (orient.down - placement1.orientation)) % 4;
	var spiderIndex2 = (4 + (orient.up - placement2.orientation)) % 4;
	var spider1 = pieces[piece1][spiderIndex1];
	var spider2 = pieces[piece2][spiderIndex2];

	// Spiders should match up (e.g. -1 and +1)
	if (spider1 + spider2 !== 0) {
	matchesAbove = false;
	}
	}

	// if (sequence.toString() == "6>, 3>, 0>" && placement.toString() == '7>') {
	// console.log(sequence.toString(), placement.toString(), matchesBefore, matchesAbove);
	// }

	return matchesBefore && matchesAbove;
	}

	function placeOne(sequence) {
	var newSequences = [];

	var validPlacements = sequence.validPlacements();
	for (var placementKey in validPlacements) {
	var placement = validPlacements[placementKey];
	var validSequence = new Sequence(sequence, placement);
	newSequences.push(validSequence);
	}

	return newSequences;
	}

	// One recursive step of the search algorithm (breadth-first)
	function step(sequenceSet) {
	// Stop when no possible sequences
	if (sequenceSet.length == 0) {
	return [];
	}

	// Stop when at the last tile
	var terminationLength = gridSize * gridSize;
	if (sequenceSet[0].placements.length == terminationLength) {
	return sequenceSet;
	}

	var newSequenceSet = [];
	for (var sequenceKey in sequenceSet) {
	var sequence = sequenceSet[sequenceKey];
	var newSequences = placeOne(sequence);
	Array.prototype.push.apply(newSequenceSet, newSequences);
	}

	return step(newSequenceSet);
	}

	// Run the search algorithm
	var initialSequence = new Sequence();
	var solutionSet = step([initialSequence]);

	// Normalize solutions
	var normalizedSolutionSet = solutionSet.map(function(solution) {
	return solution.normalized();
	});

	// Make unique
	var uniqNormalizedSolutionSet = {};
	normalizedSolutionSet.forEach(function(solution) {
	var strRep = solution.toString();
	uniqNormalizedSolutionSet[strRep] = solution;
	});

	// Print solutions
	for (var solutionKey in uniqNormalizedSolutionSet) {
	var solution = uniqNormalizedSolutionSet[solutionKey];
	console.log("Solution:");
	console.log(solution.toString());
	}

	console.log("Number of solutions: " + Object.keys(uniqNormalizedSolutionSet).length);
No results found