Questions 101-109
A bunch of potential implementations in different (obscure?) languages
In which we geek out with code
101: Let's write a solver in 8-bit Applesoft BASIC
I thought there was an implementation in "BASIC Computer Games", but it doesn't look like it.
http://www.calormen.com/jsbasic/
999: Let's write a solver in 6502 Assembly for the Apple ][
https://github.com/dj-on-github/py6502
ApplePy: https://www.youtube.com/watch?v=EhK5JNx0irA
https://github.com/jtauber/applepy
CC65: http://cc65.github.io/cc65/
102: Let's write a solver in C sharp (Targeting Unity)
Done. Three files, could prune it down some. Running inside Unity, so it's got some overhead of handling its own stack.
using System.Collections.Generic;
using UnityEngine;
using BigDiceGames;
class SolveContext
{
public List<int> PlacedPieces;
public List<int> UnplacedPieces;
public int currentPieceIndex;
public int currentCellIndex;
public int currentFlippedIndex;
public int currentRotIndex;
public static List<PentominoPiece> PENTOMINO_PIECES;
public SolveContext()
{
PlacedPieces = new List<int>();
UnplacedPieces = new List<int>();
for (int i = 0; i < 12; ++i) {
UnplacedPieces.Add(i);
}
currentPieceIndex = 0;
currentCellIndex = 0;
currentFlippedIndex = 0;
currentRotIndex = 0;
}
public void RandomizeUnsolved()
{
for (int i = 0; i < UnplacedPieces.Count - 1; ++i) {
int swapPos = UnityEngine.Random.Range(i + 1, UnplacedPieces.Count - 1);
int oldIVal = UnplacedPieces[i];
int oldSVal = UnplacedPieces[swapPos];
UnplacedPieces[i] = oldSVal;
UnplacedPieces[swapPos] = oldIVal;
//Debug.Log(string.Format("new contents of loc{0}:{1}", i, UnplacedPieces[i]));
}
}
public SolveContext Copy()
{
SolveContext c = new SolveContext();
c.PlacedPieces = new List<int>(PlacedPieces);
c.UnplacedPieces = new List<int>(UnplacedPieces);
c.currentPieceIndex = currentPieceIndex;
c.currentCellIndex = currentCellIndex;
c.currentFlippedIndex = currentFlippedIndex;
c.currentRotIndex = currentRotIndex;
return c;
}
public SolveContext GetNextSolveContext()
{
PentominoPiece p = PENTOMINO_PIECES[UnplacedPieces[currentPieceIndex]];
SolveContext c = Copy();
if (c.currentRotIndex < p.RotSymmetry - 1) {
c.currentRotIndex++;
return c;
}
c.currentRotIndex = 0;
if ((c.currentFlippedIndex < 1) && (p.Flippable)) {
c.currentFlippedIndex++;
return c;
}
c.currentFlippedIndex = 0;
if (c.currentCellIndex < 4) {
c.currentCellIndex++;
return c;
}
c.currentCellIndex = 0;
if (c.currentPieceIndex < c.UnplacedPieces.Count - 1) {
c.currentPieceIndex++;
return c;
}
return null;
}
public SolveContext Push()
{
SolveContext c = Copy();
//Debug.Log("Pushing");
//Debug.Log("before pp " + c.PlacedPieces);
//foreach (int p in c.PlacedPieces) {
// Debug.Log(p);
//}
//Debug.Log("before upp " + c.UnplacedPieces);
//foreach (int p in c.UnplacedPieces) {
// Debug.Log(p);
//}
int pi = c.UnplacedPieces[c.currentPieceIndex];
c.PlacedPieces.Add(pi);
c.UnplacedPieces.Remove(pi);
//Debug.Log("after pp " + c.PlacedPieces);
//foreach (int p in c.PlacedPieces) {
// Debug.Log(p);
//}
//Debug.Log("after upp " + c.UnplacedPieces);
//foreach (int p in c.UnplacedPieces) {
// Debug.Log(p);
//}
c.currentPieceIndex = 0;
c.currentCellIndex = 0;
c.currentFlippedIndex = 0;
c.currentRotIndex = 0;
return c;
}
}
public class PieceMgr : MonoBehaviour {
public GameObject EmptyCellSprite;
public GameObject FilledCellSprite;
public int Width = 10;
public int Height = 6;
int oldWidth;
int oldHeight;
List<GameObject> emptyCells;
List<GameObject> filledCells;
const int CELL_COUNT = 60;
List<PentominoPiece> pentominoPieces;
List<int> occupations;
bool solved;
List<SolveContext> solveStack;
float solvedTime;
public float BragTime;
public float TargetFPS;
public Camera GameCamera;
// Use this for initialization
void Start () {
emptyCells = new List<GameObject>();
filledCells = new List<GameObject>();
pentominoPieces = new List<PentominoPiece>();
for (int i = 0; i < 12; ++i) {
pentominoPieces.Add(new PentominoPiece(i));
}
SolveContext.PENTOMINO_PIECES = pentominoPieces;
occupations = new List<int>();
solveStack = new List<SolveContext>();
ResetSolveState();
}
// Update is called once per frame
void Update () {
if (Input.GetKeyDown(KeyCode.Alpha3)) {
Height = 3;
}
if (Input.GetKeyDown(KeyCode.Alpha4)) {
Height = 4;
}
if (Input.GetKeyDown(KeyCode.Alpha5)) {
Height = 5;
}
if (Input.GetKeyDown(KeyCode.Alpha6)) {
Height = 6;
}
bool updateTray = false;
if (Width != oldWidth) {
oldWidth = Width;
Height = CELL_COUNT / Width;
oldHeight = Height;
updateTray = true;
}
if (Height != oldHeight) {
oldHeight = Height;
Width = CELL_COUNT / Height;
oldWidth = Width;
updateTray = true;
}
if (updateTray) {
LayoutCells();
}
if (!solved) {
float startTime = Time.realtimeSinceStartup;
if (TargetFPS == 0) {
UpdateSolver();
}
else
{
float expirationTime = startTime + 1.0f / TargetFPS;
while((!solved) &&(Time.realtimeSinceStartup < expirationTime)) {
UpdateSolver();
}
}
}
else
if (Time.realtimeSinceStartup > solvedTime + BragTime) {
ResetSolveState();
}
}
int findEmptyIndex()
{
for (int x = 0; x < Width; ++x) {
for (int y = 0; y < Height; ++y) {
int testIndex = GetCellIndex(x, y);
if (occupations[testIndex] == -1) {
return testIndex;
}
}
}
return -1;
}
bool indexToXY(int index, out int x, out int y)
{
if ((index < 0) || (index >= Height * Width)) {
x = -1;
y = -1;
return false;
}
x = index % Width;
y = index / Width;
return true;
}
void UpdateSolver()
{
if (solved) {
return;
}
if (solveStack.Count == 0) {
Debug.Log("no solve stack");
return;
}
int emptyIndex = findEmptyIndex();
if (emptyIndex == -1) {
Debug.Log("no empty index");
return;
}
int x = -1;
int y = -1;
bool idxGot = indexToXY(emptyIndex, out x, out y);
if (!idxGot) {
Debug.Log("no xy");
return;
}
SolveContext curSolveContext = solveStack[solveStack.Count - 1];
if (canPlaceContext(curSolveContext, x, y)) {
placeContext(curSolveContext, x, y);
updateSpritesFromOccupations();
SolveContext next = curSolveContext.Push();
solveStack.Add(next);
if (next.PlacedPieces.Count == 12) {
solved = true;
solvedTime = Time.realtimeSinceStartup;
updateSpritesFromOccupations();
Debug.Log("solved. Done");
}
}
else {
while(true) {
if (solveStack.Count == 0) {
Debug.Log("no solve stack on pop");
return;
}
curSolveContext = solveStack[solveStack.Count - 1];
solveStack.RemoveAt(solveStack.Count - 1);
SolveContext next = curSolveContext.GetNextSolveContext();
if (next != null) {
solveStack.Add(next);
removeUnplacedFromContext(curSolveContext);
break;
}
}
}
}
void removeUnplacedFromContext(SolveContext context)
{
bool anyUpdates = false;
for (int i = 0; i < CELL_COUNT; ++i) {
if (context.UnplacedPieces.Contains(occupations[i])) {
occupations[i] = -1;
anyUpdates = true;
}
}
if (anyUpdates) {
updateSpritesFromOccupations();
}
}
bool canPlaceContext(SolveContext sc, int x, int y)
{
return CanPlacePiece(sc.UnplacedPieces[sc.currentPieceIndex], sc.currentCellIndex, x, y, sc.currentFlippedIndex, sc.currentRotIndex);
}
void placeContext(SolveContext sc, int x, int y)
{
PlacePiece(sc.UnplacedPieces[sc.currentPieceIndex], sc.currentCellIndex, x, y, sc.currentFlippedIndex, sc.currentRotIndex);
}
void ResetSolveState()
{
occupations.Clear();
for (int i = 0; i < CELL_COUNT; ++i) {
occupations.Add(-1);
}
solveStack.Clear();
SolveContext startContext = new SolveContext();
startContext.RandomizeUnsolved();
solveStack.Add(startContext);
updateSpritesFromOccupations();
solvedTime = -1;
solved = false;
}
void LayoutCells()
{
Transform parentTransform = this.gameObject.transform;
if (emptyCells.Count != CELL_COUNT) {
for (int i = 0; i < CELL_COUNT; ++i) {
GameObject emptyObj = Instantiate(EmptyCellSprite);
emptyObj.name = string.Format("empty{0:D2}", i);
emptyObj.transform.SetParent(parentTransform);
emptyCells.Add(emptyObj);
}
}
if (filledCells.Count != CELL_COUNT) {
for (int i = 0; i < CELL_COUNT; ++i) {
GameObject filledObj = Instantiate(FilledCellSprite);
filledObj.name = string.Format("filled{0:D2}", i);
filledObj.transform.SetParent(parentTransform);
filledCells.Add(filledObj);
}
}
float s = 10.0f / Width;
parentTransform.localScale = new Vector3(s, s, s);
parentTransform.position = new Vector2(-s * Width / 2.0f, -s * Height / 2.0f);
for (int x = 0; x < Width; ++x) {
for (int y = 0; y < Height; ++y) {
Vector2 pos = new Vector2(x, y);
int index = GetCellIndex(x,y);
emptyCells[index].transform.localPosition = pos;
filledCells[index].transform.localPosition = pos;
emptyCells[index].name = string.Format("empty [{0:D2} {1:D2}]", x, y);
filledCells[index].name = string.Format("filled [{0:D2} {1:D2}]", x, y);
}
}
ResetSolveState();
}
int GetCellIndex(int x, int y)
{
if ((x < 0) || (x >= Width) ||
(y < 0) || (y >= Height)) {
return -1;
}
else {
return Width * y + x;
}
}
bool CanPlacePiece(int pieceIndex, int cellNumber, int x, int y, int flipped, int rot)
{
PentominoPiece p = pentominoPieces[pieceIndex];
List<int> indices = GetIndicesForPiece(p, cellNumber, x, y, flipped, rot);
foreach (int i in indices) {
if (i == -1) {
return false;
}
if (occupations[i] != -1) {
return false;
}
}
return true;
}
void PlacePiece(int pieceIndex, int cellNumber, int x, int y, int flipped, int rot)
{
PentominoPiece p = pentominoPieces[pieceIndex];
if (!CanPlacePiece(pieceIndex, cellNumber, x, y, flipped, rot))
return;
List<int> indices = GetIndicesForPiece(p, cellNumber, x, y, flipped, rot);
for (int i = 0; i < indices.Count; ++i) {
int index = indices[i];
occupations[index] = pieceIndex;
}
}
void updateSpritesFromOccupations()
{
if (filledCells.Count == 0) {
return;
}
for (int i = 0; i < CELL_COUNT; ++i) {
bool isActive = filledCells[i].activeSelf;
bool shouldBeActive = (occupations[i] != -1);
if (isActive != shouldBeActive) {
filledCells[i].SetActive(shouldBeActive);
}
if (shouldBeActive) {
SpriteRenderer sr = filledCells[i].GetComponent<SpriteRenderer>();
PentominoPiece p = pentominoPieces[occupations[i]];
sr.color = p.PieceColor;
}
}
}
/// <summary>
/// Gets the indices for piece.
/// </summary>
/// <returns>The indices for piece.</returns>
/// <param name="p">P.</param>
/// <param name="cellNumber">which cell is to be the center</param>
/// <param name="x">The x coordinate.</param>
/// <param name="y">The y coordinate.</param>
/// <param name="flipped">Flipped.</param>
/// <param name="rot">Rot.</param>
List<int> GetIndicesForPiece(PentominoPiece p, int cellNumber, int x, int y, int flipped, int rot)
{
//Debug.Log(string.Format("placing piece {0} CN {1} X {2} Y {3} F {4} R {5}", p.Name, cellNumber, x, y, flipped, rot));
List<int> outIndices = new List<int>();
List<Vec2i> rotatedPositions = new List<Vec2i>();
for (int i = 0; i < p.Cells.Count; ++i) {
Vec2i cellPos = p.Cells[i];
//Debug.Log(string.Format("i {0} x {1} y {2}", i, cellPos.x, cellPos.y));
int rx = cellPos.x * cos4(rot) + cellPos.y * (-1 * sin4(rot));
int ry = cellPos.x * sin4(rot) + cellPos.y * cos4(rot);
if (flipped > 0) {
rx *= -1;
}
//Debug.Log(string.Format("i {0} rx {1} ry {2}", i, rx, ry));
rotatedPositions.Add(new Vec2i(rx, ry));
}
int offsetX = rotatedPositions[cellNumber].x;
int offsetY = rotatedPositions[cellNumber].y;
//Debug.Log(string.Format("ox {0} oy {1}", offsetX, offsetY));
for (int i = 0; i < p.Cells.Count; ++i) {
Vec2i r = rotatedPositions[i];
int translatedX = r.x - offsetX + x;
int translatedY = r.y - offsetY + y;
//Debug.Log(string.Format("i {0} rx {1} ry {2}", i, translatedX, translatedY));
outIndices.Add(GetCellIndex(translatedX, translatedY));
}
return outIndices;
}
int sin4(int theta)
{
switch (theta % 4) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 0;
case 3:
return -1;
}
return -2;
}
int cos4(int theta)
{
switch (theta % 4) {
case 0:
return 1;
case 1:
return 0;
case 2:
return -1;
case 3:
return 0;
}
return -2;
}
}999: Let's write a solver in D
https://www.wired.com/2014/07/d-programming-language/
103: Let's write a solver in F sharp
How different is this? It would be fun to try.
104: Let's write a solver in Javascript
Could be interesting to see it running by itself in a browser.
Maybe use that Coding Train library.
105: Let's write a solver in Brainf**k
https://en.wikipedia.org/wiki/Esoteric_programming_language#Brainfuck
Maybe not. Let's keep this clean.
999: Let's write a solver in Erlang
106: Let's write a solver in Forth
https://www.gnu.org/software/gforth/
107: Let's write a solver in FORTRAN
108: Let's write a solver in Go
109: Let's write a solver in Haskell
Last updated