Created
December 18, 2012 20:27
-
-
Save orangutanboy/4331641 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// <reference path="scripts/jquery.d.ts" /> | |
| module Trainline { | |
| export var pointState = { | |
| Available: "AVAILABLE", | |
| Crossed: "CROSSED", | |
| Unavailable: "UNAVAILABLE" | |
| } | |
| export var pointSide = { | |
| Unknown: "UNKNOWN", | |
| Left: "LEFT", | |
| Right: "RIGHT", | |
| Top: "TOP", | |
| Bottom: "BOTTOM" | |
| } | |
| export class Point { | |
| public x: number; | |
| public y: number; | |
| private state: string; | |
| private entrySide: string; | |
| private exitSide: string; | |
| public propertyChangedCallback: { (changedPoint: Point): void; }; | |
| constructor(x: number, y: number) { | |
| this.x = x; | |
| this.y = y; | |
| this.state = pointState.Available; | |
| this.entrySide = pointSide.Unknown; | |
| } | |
| //Set the state without kicking off the property changed event | |
| public SetUnavailable(): void { | |
| this.state = pointState.Unavailable; | |
| } | |
| showPoint(): void { | |
| if (!this.entrySide || this.entrySide === pointSide.Unknown) { | |
| return; | |
| } | |
| if (!this.exitSide || this.exitSide === pointSide.Unknown) { | |
| return; | |
| } | |
| $("#image" + this.x + this.y).attr("src", "content/" + this.entrySide + "_" + this.exitSide + ".png"); | |
| } | |
| get EntrySide(): string { | |
| return this.entrySide; | |
| } | |
| set EntrySide(value: string) { | |
| this.entrySide = value; | |
| this.showPoint(); | |
| this.propertyChangedCallback(this); | |
| } | |
| get ExitSide(): string { | |
| return this.exitSide; | |
| } | |
| set ExitSide(value: string) { | |
| this.exitSide = value; | |
| this.showPoint(); | |
| this.propertyChangedCallback(this); | |
| } | |
| get State(): string { | |
| return this.state; | |
| } | |
| set State(value: string) { | |
| this.state = value; | |
| this.propertyChangedCallback(this); | |
| } | |
| EntrySideFrom(fromPoint: Point): string { | |
| if (Math.abs(fromPoint.x - this.x) > 1 | |
| || Math.abs(fromPoint.y - this.y) > 1) { | |
| //Not adjacent, so | |
| return pointSide.Unknown; | |
| } | |
| if (fromPoint.x != this.x | |
| && fromPoint.y != this.y) { | |
| return pointSide.Unknown; | |
| } | |
| if (fromPoint.x < this.x) { | |
| return pointSide.Left; | |
| } | |
| if (fromPoint.x > this.x) { | |
| return pointSide.Right; | |
| } | |
| if (fromPoint.y < this.y) { | |
| return pointSide.Bottom; | |
| } | |
| return pointSide.Top; | |
| } | |
| public static OppositeOf(side: string): string { | |
| switch (side) { | |
| case pointSide.Bottom: | |
| return pointSide.Top; | |
| case pointSide.Top: | |
| return pointSide.Bottom; | |
| case pointSide.Left: | |
| return pointSide.Right; | |
| case pointSide.Right: | |
| return pointSide.Left; | |
| default: | |
| return pointSide.Unknown; | |
| } | |
| } | |
| } | |
| export class Grid { | |
| points: Point[][]; | |
| columnTotals: number[]; | |
| rowTotals: number[]; | |
| includePoints: Point[]; | |
| currentPoint: Point; | |
| startPoint: Point; | |
| endPoint: Point; | |
| ignoreEvents: bool; | |
| constructor(totals: number[], startY: number, endX: number) { | |
| this.ignoreEvents = true; | |
| this.columnTotals = totals.slice(0, 8); | |
| this.rowTotals = totals.slice(8, 16); | |
| this.points = this.createPoints(); | |
| this.setExtremePoints(0, startY, endX, 0); | |
| this.ignoreEvents = false; | |
| } | |
| setExtremePoints(startX: number, startY: number, endX: number, endY: number): void { | |
| this.startPoint = this.currentPoint = this.points[startX][startY]; | |
| this.startPoint.State = pointState.Crossed; | |
| this.startPoint.EntrySide = pointSide.Left; | |
| this.startPoint.ExitSide = pointSide.Right; | |
| this.endPoint = this.points[endX][endY]; | |
| this.endPoint.State = pointState.Crossed; | |
| this.endPoint.EntrySide = pointSide.Top; | |
| this.endPoint.ExitSide = pointSide.Bottom; | |
| } | |
| public crossedPointsInColumn(column: number): number { | |
| var crossedPoints = 0; | |
| this.points[column].forEach(checkPoint => | |
| { | |
| if (checkPoint.State == pointState.Crossed) { | |
| crossedPoints++; | |
| } | |
| }); | |
| return crossedPoints; | |
| } | |
| private crossedPointsInRow(row: number): number { | |
| var crossedPoints = 0; | |
| this.points.forEach(column => | |
| { | |
| column.forEach(checkPoint => | |
| { | |
| if (checkPoint.y == row && checkPoint.State == pointState.Crossed) { | |
| crossedPoints++; | |
| } | |
| }); | |
| }); | |
| return crossedPoints; | |
| } | |
| private setUnavailableInColumn(column: number): void { | |
| for (var row = 0; row <= 7; ++row) { | |
| if (this.points[column][row].State == pointState.Available) { | |
| this.points[column][row].SetUnavailable(); | |
| } | |
| } | |
| } | |
| private setUnavailableInRow(row: number): void { | |
| for (var column = 0; column <= 7; ++column) { | |
| if (this.points[column][row].State == pointState.Available) { | |
| this.points[column][row].SetUnavailable(); | |
| } | |
| } | |
| } | |
| pointPropertyChanged(changedPoint: Point) { | |
| if (this.ignoreEvents) { | |
| return; | |
| } | |
| var changedPointColumn = changedPoint.x; | |
| var changedPointRow = changedPoint.y; | |
| var columnCrossedPoints = this.crossedPointsInColumn(changedPoint.x); | |
| //Have the max amount in this column | |
| if (columnCrossedPoints >= this.columnTotals[changedPoint.x]) { | |
| //Set all available to unavailable | |
| this.setUnavailableInColumn(changedPoint.x); | |
| } | |
| var rowCrossedPoints = this.crossedPointsInRow(changedPoint.y); | |
| //Have the max amount in this row | |
| if (rowCrossedPoints >= this.rowTotals[changedPoint.y]) { | |
| //Set all available to unavailable | |
| this.setUnavailableInRow(changedPoint.y); | |
| } | |
| } | |
| createPoints(): Point[][] { | |
| var points: Point[][] = []; | |
| for (var x = 0; x <= 7; ++x) { | |
| points.push(new Point[]); | |
| for (var y = 0; y <= 7; ++y) { | |
| points[x].push(this.buildPoint(x, y)); | |
| } | |
| } | |
| return points; | |
| } | |
| buildPoint(x: number, y: number): Point { | |
| var myPoint = new Point(x, y); | |
| myPoint.propertyChangedCallback = p => this.pointPropertyChanged(p); | |
| return myPoint; | |
| } | |
| clone(): Grid { | |
| //TODO:MJ clone this properly | |
| var clonedGrid = new Grid(this.columnTotals.concat(this.rowTotals), this.startPoint.y, this.endPoint.x); | |
| this.points.forEach(origColumn => { | |
| origColumn.forEach(origPoint => { | |
| var clonedPoint = clonedGrid.points[origPoint.x][origPoint.y]; | |
| clonedPoint.EntrySide = origPoint.EntrySide; | |
| clonedPoint.ExitSide = origPoint.ExitSide; | |
| clonedPoint.State = origPoint.State; | |
| }) | |
| }); | |
| clonedGrid.currentPoint = clonedGrid.points[this.currentPoint.x][this.currentPoint.y]; | |
| clonedGrid.endPoint = clonedGrid.points[this.endPoint.x][this.endPoint.y]; | |
| return clonedGrid; | |
| } | |
| public IsValid(): bool { | |
| return this.NoColumnsToLeftHaveOnePointAvailable(); | |
| } | |
| // if 1 point remains available in column and guesspoint is same side as the finish point from this row, | |
| // then the track can't pass into and out of the column again to use the single point | |
| private NoColumnsToLeftHaveOnePointAvailable(): bool { | |
| var maxCheckCol = Math.min(this.endPoint.x, this.currentPoint.x) - 1; | |
| for (var checkCol = 0; checkCol <= maxCheckCol; ++checkCol) { | |
| if (this.columnTotals[checkCol] - this.crossedPointsInColumn(checkCol) == 1) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| IsSolved(): bool { | |
| if (this.currentPoint.EntrySideFrom(this.endPoint) != pointSide.Bottom) | |
| return false; | |
| for (var index = 0; index <= 7; ++index) { | |
| if (this.crossedPointsInColumn(index) != this.columnTotals[index] || this.crossedPointsInRow(index) != this.rowTotals[index]) | |
| return false; | |
| } | |
| return true; | |
| } | |
| } | |
| export class AdjacentPointCalculator { | |
| public getAvailableAdjacentPoints(startGrid: Grid): Point[] { | |
| var adjacentPoints: Point[] = []; | |
| var adjacentPoint: Point; | |
| if ((adjacentPoint = AdjacentPointCalculator.pointToLeft(startGrid))) { | |
| if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Right)) { | |
| adjacentPoints.push(adjacentPoint); | |
| } | |
| } | |
| if ((adjacentPoint = AdjacentPointCalculator.pointToRight(startGrid))) { | |
| if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Left)) { | |
| adjacentPoints.push(adjacentPoint); | |
| } | |
| } | |
| if ((adjacentPoint = AdjacentPointCalculator.pointBelow(startGrid))) { | |
| if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Top)) { | |
| adjacentPoints.push(adjacentPoint); | |
| } | |
| } | |
| if ((adjacentPoint = AdjacentPointCalculator.pointAbove(startGrid))) { | |
| if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Bottom)) { | |
| adjacentPoints.push(adjacentPoint); | |
| } | |
| } | |
| return adjacentPoints; | |
| } | |
| static canBeUsed(adjacentPoint: Point, requiredEntrySide: string): bool { | |
| return (adjacentPoint.State == pointState.Available && | |
| (adjacentPoint.EntrySide == requiredEntrySide || adjacentPoint.EntrySide == pointSide.Unknown)); | |
| } | |
| static pointToLeft(startGrid): Point { | |
| if (startGrid.currentPoint.x > 0 && startGrid.currentPoint.y < 7) { | |
| return startGrid.points[startGrid.currentPoint.x - 1][startGrid.currentPoint.y]; | |
| } | |
| return null; | |
| } | |
| static pointToRight(startGrid: Grid): Point { | |
| if (startGrid.currentPoint.x < 7) { | |
| return startGrid.points[startGrid.currentPoint.x + 1][startGrid.currentPoint.y]; | |
| } | |
| return null; | |
| } | |
| static pointBelow(startGrid: Grid): Point { | |
| if (startGrid.currentPoint.y > 0) { | |
| return startGrid.points[startGrid.currentPoint.x][startGrid.currentPoint.y - 1]; | |
| } | |
| return null; | |
| } | |
| static pointAbove(startGrid: Grid): Point { | |
| if (startGrid.currentPoint.y < 7 && startGrid.currentPoint.x < 7) { | |
| return startGrid.points[startGrid.currentPoint.x][startGrid.currentPoint.y + 1]; | |
| } | |
| return null; | |
| } | |
| } | |
| export class GridSolver { | |
| solved: bool; | |
| startGrid: Grid; | |
| adjacentPointCalculator: AdjacentPointCalculator; | |
| constructor(startGrid: Grid) { | |
| this.startGrid = startGrid; | |
| this.adjacentPointCalculator = new AdjacentPointCalculator(); | |
| } | |
| private calcPossibleGrids(gridToSolve: Grid): Grid[] { | |
| var guesses: Grid[] = []; | |
| var startGrid = gridToSolve.clone(); | |
| startGrid.currentPoint.State = pointState.Crossed; | |
| var adjacentPoints = this.adjacentPointCalculator.getAvailableAdjacentPoints(startGrid); | |
| if (adjacentPoints.length == 0) { | |
| return null; | |
| } | |
| adjacentPoints.forEach(point => | |
| { | |
| var guessGrid = startGrid.clone(); | |
| var exitPoint = guessGrid.currentPoint; | |
| if (exitPoint.EntrySideFrom(startGrid.endPoint) != pointSide.Bottom) { | |
| guessGrid.currentPoint = guessGrid.points[point.x][point.y]; | |
| guessGrid.currentPoint.State = pointState.Crossed; | |
| guessGrid.currentPoint.EntrySide = guessGrid.currentPoint.EntrySideFrom(startGrid.currentPoint); | |
| exitPoint.ExitSide = Point.OppositeOf(guessGrid.currentPoint.EntrySide); | |
| if (guessGrid.IsValid()) { | |
| guesses.push(guessGrid); | |
| } | |
| } | |
| }); | |
| return guesses; | |
| } | |
| public solve(): void { | |
| this.recursePossibleGrids(this.startGrid); | |
| } | |
| public recursePossibleGrids(startGrid: Grid): void { | |
| var possibleGrids = this.calcPossibleGrids(startGrid); | |
| if (possibleGrids == null) { | |
| return; | |
| } | |
| possibleGrids.forEach(guessGrid => | |
| { | |
| if (this.solved) { | |
| return; | |
| } | |
| if (guessGrid.IsSolved()) { | |
| guessGrid.currentPoint.ExitSide = pointSide.Bottom; | |
| //OnSolved(guessGrid); | |
| this.solved = true; | |
| return; | |
| } | |
| if (!this.solved) { | |
| this.recursePossibleGrids(guessGrid); | |
| } | |
| }); | |
| } | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment