Saturday, February 28, 2015

jsonFormatter – jQuery Plugin

I recently needed to display some JSON on a webpage, but the JSON being displaying was hard to ready due to its length and lack of formatting. I searched the web and found a nice little JavaScript routine written by Vladimir Bodurov (http://bodurov.com/JsonFormatter/).

I took his script, made a few modifications, converted it into a jQuery Plugin, and published it to GitHub (https://github.com/MHeironimus/jsonFormatter). To use this plugin include jsonFormatter.min.css and jsonFormatter.min.js in your html file. See the jsonFormatterExample.html file for an example on how to do this. If you wish to use the darkTheme, include the jsonFormatter-darkTheme.min.css file.

An example webpage that uses the jsonFormatter jQuery Plugin can be viewed at https://static.heironimus.info/blog/jsonformatter/example/jsonFormatterExample.html.

Example

Before

After

HTML

<html>

<head>

<title>jsonFormatter Example</title>

</head>

<body>

<h1>jsonFormatter Example</h1>

<h2>Default Theme, Default Options Example</h2>

<div class="exampleJavaScript">$('.jsonFormatter').jsonFormatter();</div>

<div class="exampleJson jsonFormatter">{stringValue:"string value",numberValue:-4.506,booleanValue:true,arrayOfStrings:['one','two','three'],arrayOfObjects:[{firstProperty:1,secondProperty:2},{firstProperty:3,secondProperty:4}],undefinedProperty:undefined,emptyProperty:{}}</div>

</section>

$(document).ready(function () {

$('.jsonFormatter').jsonFormatter();

});

</script>

</body>

</html>

Documentation

.jsonFormatter(options)

Returns: jQuery

Description: If the matched elements contain JSON, they are formatted to be easier to read. Arrays and object are optionally collapsible.

Options

quoteKeys

Type: Boolean
Default: true

Specifies if object’s keys should be quoted in the formatted output.

collapsible

Type: Boolean
Default: true

Specifies if arrays and objects are collapsible in the formatted output.

hideOriginal

Type: Boolean
Default: true

Specifies if the original element is hidden. The element will only be hidden if it contains valid JSON that was successfully formatted.

Tuesday, January 27, 2015

Solving Scramble Squares Puzzles

A couple of years ago my kids got a Scramble Squares puzzle (https://scramblesquares.com/) from their grandmother. A Scramble Squares puzzle contains nine squares puzzle pieces. The edge of each piece has half an image on it (e.g. the head of a zebra, the tail of an elephant, etc.). The puzzle pieces must be arranged in a 3 x 3 grid so that the images on the edges line up correctly (e.g. the head of the zebra is against the tail of the zebra). The actual puzzle my kids received was the Serengeti puzzle - https://scramblesquares.com/product/serengeti-scramble-squares/). After spending a couple of hours trying to solve the puzzle, I decided to write a computer program that would do it for me.

XML Puzzle File

First I defined an XML representation of each puzzle piece:

<North>

<Image>Zebra</Image>

<Half>Bottom</Half>

</North>

<South>

<Image>Giraffe</Image>

<Half>Bottom</Half>

</South>

<East>

<Image>Rhinoceros</Image>

</East>

<West>

<Image>Elephant</Image>

<Half>Bottom</Half>

</West>

<CenterImageDirection>NorthEast</CenterImageDirection>

</PuzzlePiece>

Each piece could be given a unique name, designated by the Name element. Each piece had a North, South, East, and West side defined. Each side consisted of two elements: Image and Half. Image indicated what picture was on the edge and Half indicated if it was the Top half or the Bottom half of the image. Each puzzle piece also has an image in the center. I was not sure if this image had anything to do with the solution to the puzzle or not, so I included an element to indicate which direction this image was rotated. As it turned out, this image is not significant, so this is not really necessary.

Next I defined an XML representation of the entire puzzle:

</ScrambleSquaresPuzzleFile>

The puzzle contains three elements. The first, NumberOfRows, indicates how many rows of pieces should be in the solution. The second, NumberOfColumns, indicates how many columns of pieces should be in the solution. The last, PuzzlePieces, contains the list of puzzle pieces that make up the puzzle.

Brute Force Algorithm

My first attempt to solve the puzzle was to use a brute force algorithm that would try every possible permutation. There are nine pieces in the puzzle and each piece can be rotated in four different directions. The following formula can be used to determine how many possible solutions must be tried:

(# of sides)^(number of pieces) * (number of pieces)!

4^9 * 9! = 262,144 * 362,880 = 95,126,814,720

It turns out that 95 billion possible solutions is a lot, even for today’s fast computers. On my HP Pavilion HPE with a 3.4 GHz Intel Core i7-2600 processor, it took over 26 hours to solve the puzzle. It found four solutions (basically one solution rotated four different directions). I was happy to know the solution to the puzzle, but I was determined to reduce the time it took to solve the puzzle. No one wants to wait a full day to find the solution to a puzzle.

Multi-Threaded Brute Force Algorithms

Because the original algorithm was single threaded, it was only using a small portion of the available CPU power. My next set of solutions used various multi-threading techniques to break the work up into parts that could be done in parallel. In one I used the .NET Parallel.ForEach function (https://learn.microsoft.com/en-us/dotnet/api/system.threading.tasks.parallel.foreach) to break up the work. In another I used .NET Tasks (https://learn.microsoft.com/en-us/dotnet/api/system.threading.tasks.task). I also tried .NET Threads (https://learn.microsoft.com/en-us/dotnet/api/system.threading.thread). All of these solutions still tried all of the 95,126,814,720 possible solutions, but did so using most of the available CPU power. These algorithms got the solving time down below 10 hours, but that was still a long time to wait to solve the puzzle.

Edge Solve Algorithm

The final algorithm I attempted first determined for each side of each piece which other puzzle piece edges would match. Then it would only attempt to build the solution to the puzzle using known matching edges. This significantly reduced the number of possible solutions that needed to be tested. In the case of the Serengeti puzzle, only 10,699 solutions had to be attempted, rather than 95,126,814,720. The program could now solve the puzzle in under a second.

Scramble Squares Puzzles

I have used this program to find the solution to the following four Scramble Squares puzzles:

Serengeti (https://scramblesquares.com/product/serengeti-scramble-squares/)
Pufferbellies (https://scramblesquares.com/product/pufferbellies-scramble-squares/)
Butterflies (https://scramblesquares.com/product/butterflies-scramble-squares/)
Classic Cars (https://scramblesquares.com/product/classic-cars-scramble-squares/)

Unlike the other three puzzles, the Butterflies puzzle actually has eight solutions (two solutions rotated four ways).

Scramble Squares Solver Program

You can download my Scramble Squares Solver program at https://static.heironimus.info/instructables/scramble-squares/ScrambleSquaresSolver.zip. You can download the source code and unit tests for the program at https://static.heironimus.info/instructables/scramble-squares/ScrambleSquaresSolverSource.zip. You can go to https://scramblesquares.com/ to purchase your own Scramble Squares puzzles.

Sunday, December 14, 2014

Arduino: ColecoVision Cartridge Reader

With the numerous emulators and documentation on classic gaming consoles available today, it is easier than ever to create a “homebrew” video game for one of these classic game consoles (see http://en.wikipedia.org/wiki/Homebrew_(video_games) for more information about homebrew video games). Even though it is easier than it used to be, it can still be quite a challenge. It often helps to see how existing games work before creating a new one from scratch.

This article explains how to create a ColecoVision cartridge reader using an Arduino UNO (or similar product) and a PC.

What You Need

Arduino UNO (or similar board) - http://arduino.cc/en/Main/ArduinoBoardUno
Two 8-bit Shift Registers (74HC595 or similar chips) [this could also be implemented with a single 16-bit Shift Register (STP16C596), but I have not tested this implementation]
Standard Card Edge Connector 15 Position (CONN SEC II 15 POS 100C/L) - http://www.mouser.com/ProductDetail/TE-Connectivity-AMP/5530841-2/?qs=sGAEpiMZZMvlX3nhDDO4AIGhITdGxFYIj%252be5B1rBFtQ%3d
Prototyping PC Board – to mount the 15 position standard card edge connector
Wire
ColecoVision Cartridge to read

Note: If using an Arduino board with 29 or more digital I/O pins (e.g. the Arduino Due, Arduino MEGA ADK, Arduino Mega 2560, etc.), this can be built without using the two 8-bit shift registers (i.e. the 74HC595 or STP16C596).

ColecoVision Cartridge Overview

ColecoVision cartridges typically come in sizes of 8K, 16K, 24K, or 32K. I have also encountered a few 12K cartridges. They generally have one to four 8K rom chips, although I have seen a few exceptions. For example, the Pitfall cartridge I own has a single 16K rom chip.

Image of the inside of the 24k Donkey Kong cartridge.

ColecoVision Cartridge Pin Outs

ColecoVision cartridges have 15 address pins, 8 data pins, 4 low-enabled chip select pins, 2 ground pins, and a Vcc pin. The layout of the 30 ColecoVision pins is shown below:

Not Enough Pins

The Arduino UNO only has 20 pins that can be used for digital I/O. Two of these are used for the serial communication to the host PC, and I avoid using pin 13, since it is wired to the LED on the Arduino board. That leaves only 17 pins on the Arduino to connect to the 27 pins (15 address, 8 data, and 4 chip select) on the ColecoVision cartridge.

Shift Register Circuit

In order to reduce the number of Arduino pins required, a shift register circuit can be used that allows the Arduino to set the cartridge’s 15 address pins using only three Arduino pins. This circuit is described in detail on the Arduino website at http://arduino.cc/en/tutorial/ShiftOut. The LEDs and resistors shown in the example are not required for the cartridge reader, but I included them so I could see what the cartridge reader was doing.

Connections Table

From	Pin	To	Pin
Cartridge Connector (A01)	9	74HC595 #1	1
Cartridge Connector (A02)	11	74HC595 #1	2
Cartridge Connector (A03)	15	74HC595 #1	3
Cartridge Connector (A04)	17	74HC595 #1	4
Cartridge Connector (A05)	21	74HC595 #1	5
Cartridge Connector (A06)	23	74HC595 #1	6
Cartridge Connector (A07)	25	74HC595 #1	7
Arduino	GND	74HC595 #1	8
Arduino	Vcc	74HC595 #1	10
Arduino	11	74HC595 #1	11
Arduino	12	74HC595 #1	12
Arduino	GND	74HC595 #1	13
Arduino	10	74HC595 #1	14
Cartridge Connector (A00)	7	74HC595 #1	15
Arduino	Vcc	74HC595 #1	16
Cartridge Connector (A09)	26	74HC595 #2	1
Cartridge Connector (A10)	16	74HC595 #2	2
Cartridge Connector (A11)	14	74HC595 #2	3
Cartridge Connector (A12)	24	74HC595 #2	4
Cartridge Connector (A13)	19	74HC595 #2	5
Cartridge Connector (A14)	20	74HC595 #2	6
Arduino	GND	74HC595 #2	8
Arduino	Vcc	74HC595 #2	10
Arduino	11	74HC595 #2	11
Arduino	12	74HC595 #2	12
Arduino	GND	74HC595 #2	13
74HC595 #1	9	74HC595 #2	14
Cartridge Connector (A08)	28	74HC595 #2	15
Arduino	Vcc	74HC595 #2	16

Chip Select Pins

The four chip select pins on the cartridge correspond to the four ROM chips that may be present in the cartridge. The first chip select pin (Chip Select 0x8000) should be toggled (high to low) when reading any addresses between 0x8000 and 0x9FFF. Likewise, Chip Select 0xA000 should be toggled for addresses between 0xA000 and 0xBFFF, Chip Select 0xC000 for 0xC000 through 0xDFFF, and Chip Select 0xE000 for 0xE000 through 0xFFFF.

From	Pin	To	Pin
Arduino	A0	Cartridge Connector (Chip Select 0x8000)	18
Arduino	A1	Cartridge Connector (Chip Select 0xA000)	22
Arduino	A2	Cartridge Connector (Chip Select 0xC000)	2
Arduino	A3	Cartridge Connector (Chip Select 0xE000)	27

Data, Vcc, and Ground Pins

Once the address pins and chip select pins have been wired up, the data, Vcc, and ground pins of the cartridge can be connected to the Arduino.

From	Pin	To	Pin
Arduino	Vcc	Cartridge Connector (Vcc)	30
Arduino	GND	Cartridge Connector (GND)	13, 29
Arduino	2	Cartridge Connector (Data 0)	5
Arduino	3	Cartridge Connector (Data 1)	3
Arduino	4	Cartridge Connector (Data 2)	1
Arduino	5	Cartridge Connector (Data 3)	4
Arduino	6	Cartridge Connector (Data 4)	6
Arduino	7	Cartridge Connector (Data 5)	8
Arduino	8	Cartridge Connector (Data 6)	10
Arduino	9	Cartridge Connector (Data 7)	12

Arduino Sketch File

The following Arduino Sketch file causes the Arduino to wait for a line from the host computer. If the line read in is “READ ALL”, the Arduino will do the following:

Send a “START:” line to the host computer.
Read all of the data from the cartridge and send it to the host computer in HEX, one byte per line.
Send a “:END” line to the host computer.

One the cartridge data has been sent to the host computer, the Arduino is ready for its next command from the host computer.

// ColecoVision / ADAM Cartridge Reader
// for the Arduino UNO
// 2014-11-25
//----------------------------------------------------------------------------------

// Arduino Pins
const int gcChipSelectLine[4] = { A0, A1, A2, A3 };
const int gcShiftRegisterClock = 11;
const int gcStorageRegisterClock = 12;
const int gcSerialAddress = 10;
const int gcDataBit[8] = { 2, 3, 4, 5, 6, 7, 8, 9 };

// Shifts a 16-bit value out to a shift register.
// Parameters:
//   dataPin - Arduino Pin connected to the data pin of the shift register.
//   clockPin - Arduino Pin connected to the data clock pin of the shift register.
//----------------------------------------------------------------------------------
void shiftOut16(int dataPin, int clockPin, int bitOrder, int value)
{
  // Shift out highbyte for MSBFIRST
  shiftOut(dataPin, clockPin, bitOrder, (bitOrder == MSBFIRST ? (value >> 8) : value));  
  // shift out lowbyte for MSBFIRST
  shiftOut(dataPin, clockPin, bitOrder, (bitOrder == MSBFIRST ? value : (value >> 8)));
}

// Select which chip on the cartridge to read (LOW = Active).
// Use -1 to set all chip select lines HIGH.
//----------------------------------------------------------------------------------
void SelectChip(byte chipToSelect)
{
  for(int currentChipLine = 0; currentChipLine < 4; currentChipLine++)
  {
    digitalWrite(gcChipSelectLine[currentChipLine], (chipToSelect != currentChipLine));
  }
}

// Set Address Lines
//----------------------------------------------------------------------------------
void SetAddress(unsigned int address)
{
    SelectChip(-1);
  
    // Disable shift register output while loading address
    digitalWrite(gcStorageRegisterClock, LOW);
    
    // Write Out Address
    shiftOut16(gcSerialAddress, gcShiftRegisterClock, MSBFIRST, address);  

    // Enable shift register output
    digitalWrite(gcStorageRegisterClock, HIGH);
    
    int chipToSelect;
    
    if (address < 0xA000) {
      chipToSelect = 0;
    } else if (address < 0xC000) {
      chipToSelect = 1;
    } else if (address < 0xE000) {
      chipToSelect = 2;
    } else {
      chipToSelect = 3;
    }
    SelectChip(chipToSelect);
}

// Read data lines
//----------------------------------------------------------------------------------
void ReadDataLines()
{
  const char cHexLookup[16] = {
    '0', '1', '2', '3', '4', '5', '6', '7', 
    '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    
  int highNibble = 0;
  int lowNibble = 0;
  boolean dataBits[8];
  char byteReadHex[4];

  for(int currentBit = 0; currentBit < 8; currentBit++)
  {
    dataBits[currentBit] = digitalRead(gcDataBit[currentBit]);
  }

  highNibble = (dataBits[7] << 3) + (dataBits[6] << 2) + (dataBits[5] << 1) + dataBits[4];
  lowNibble = (dataBits[3] << 3) + (dataBits[2] << 2) + (dataBits[1] << 1) + dataBits[0];

  Serial.write(cHexLookup[highNibble]);
  Serial.write(cHexLookup[lowNibble]);
  Serial.println();
}

// Read all of the data from the cartridge.
//----------------------------------------------------------------------------------
void ReadCartridge()
{
  unsigned int baseAddress = 0x8000;
  
  Serial.println("START:");
  
  // Read Current Chip (cartridge is 32K, each chip is 8k)
  for (unsigned int currentAddress = 0; currentAddress < 0x8000; currentAddress++) 
  {
    SetAddress(baseAddress + currentAddress);
    ReadDataLines();  
  }
  
  Serial.println(":END");
}

// Returns the next line from the serial port as a String.
//----------------------------------------------------------------------------------
String SerialReadLine()
{
  const int BUFFER_SIZE = 81;
  char lineBuffer[BUFFER_SIZE];
  int currentPosition = 0;
  int currentValue;
  
  do
  {
    // Read until we get the next character
    do
    {
      currentValue = Serial.read();
    } while (currentValue == -1);
    
    // ignore '\r' characters
    if (currentValue != '\r')
    {
      lineBuffer[currentPosition] = currentValue;
      currentPosition++;
    } 
  
  } while ((currentValue != '\n') && (currentPosition < BUFFER_SIZE));
  lineBuffer[currentPosition-1] = 0;
  
  return String(lineBuffer);
}

// Indicate to remote computer Arduino is ready for next command.
//----------------------------------------------------------------------------------
void ReadyForCommand()
{
  Serial.println("READY:");
}

void setup()
{
  // Setup Serial Monitor
  Serial.begin(57600);
  
  // Setup Chip Select Pins
  for(int chipLine = 0; chipLine < 4; chipLine++)
  {
    pinMode(gcChipSelectLine[chipLine], OUTPUT);
  }
  
  // Setup Serial Address Pins
  pinMode(gcShiftRegisterClock, OUTPUT);
  pinMode(gcStorageRegisterClock, OUTPUT);
  pinMode(gcSerialAddress, OUTPUT);
  
  // Setup Data Pins
  for(int currentBit = 0; currentBit < 8; currentBit++)
  {
    pinMode(gcDataBit[currentBit], INPUT_PULLUP);
  }
  
  while (!Serial) {
    ; // wait for serial port to connect. Needed for Leonardo only.
  }  
  
  // Reset Output Lines
  SetAddress(0);
  
  ReadyForCommand();
}

void loop()
{
  if (Serial.available() > 0)
  {
    String lineRead = SerialReadLine();
    lineRead.toUpperCase();
    
    if (lineRead == "READ ALL")
    {
      ReadCartridge();
    } // lineRead = "Read All"
    
    ReadyForCommand();
    
  } // Serial.available
}

If you are fortunate enough to be using an Arduino board with 29 or more digital I/O pins (e.g. the Arduino Due, Arduino MEGA ADK, Arduino Mega 2560, etc.) and you are not using the shift register circuit, the SetAddress function in the sketch file above will need to be re-written.

PC Software

I wrote a little Windows application which can read the ColecoVision cartridge data sent by the Arduino, display it on the screen, and save it to a file.

The Windows executable and associated sketch file can be downloaded at ColecoVisionCartridgeReader.zip. The source code for the application and associated sketch file can be downloaded at ColecoVisionCartridgeReaderSource.zip. The latest version of the source code can be found on GitHub at MHeironimus/ColecoVisionCartridgeReader.

After the program reads the contents of the cartridge from the Arduino, it truncates any 8K sections from the end of the cartridge that are blank (i.e. all bytes are set to FF).

Reading a Cartridge

Once all of the circuits have been built and connected to the Arduino, the sketch file has been loaded onto the Arduino, and the ColecoVisionCartridgeReader.exe is installed on the host PC, a ColecoVision cartridge can be read.

Recommended steps to follow:

Insert the cartridge into the connector.
Plug the Arduino into the PC.
Start the ColecoVisionCartridgeReader.exe application.
Select File -> Read From Arduino from the main menu.
Verify the settings are correct and click the Read button.

The progress dialog should appear and within 30 seconds the contents of the cartridge should appear on the screen.

Observations

The first two bytes of all ColecoVision cartridges are 55 and AA. If the AA comes first, the cartridge displays the standard ColecoVision title screen (e.g. standard ColecoVision cartridges like Donkey Kong, Mouse Trap, Zaxxon, etc.). If the 55 comes first, the cartridge skips the standard title screen (e.g. third-party cartridges like Q*Bert, Frogger, Pitfall, etc.).

Interesting Cartridges to Read

Cartridge Reader with Donkey Kong Loaded

Almost everyone who owns a ColecoVision has a Donkey Kong cartridge, since it came with the game console. There are at least two different versions of this cartridge in circulation. The first edition of this cartridge was 24K, but the second edition was only 16K. Using the Arduino ColecoVision Cartridge reader, you can determine which edition you have. Another way to tell is to look at Pauline’s umbrella on the second and third levels of the game. In the 24K version of the cartridge, the umbrella has a glitch shown in the following screenshot, but the updated 16K version of the cartridge does not.

24k Version

16k Version

Another interesting cartridge to look at is Fortune Builder. It is one of the few 32K cartridges. It also has a large number of text strings, which can be interesting to read through.

Cartridge Reader with Fortune Builder Loaded

Possible Future Enhancements

Detect 12K cartridges and truncate the duplicate 4K at the end of the cartridge image.
Have the Arduino check the first two bytes of the cartridge to verify they are correct before reading the entire cartridge.
Speed up the transfer of the cartridge data by sending multiple bytes on the same line.