Speed Coding 2016 – Q4 Solution
3 August 2016, by Chris Arnott
This post explains the solutions to Question 4 of our speed coding 2016 competition. If you haven’t yet read the question, head back and have a go now.
The quickest answer that came through to this question was from Matthew Richards (yes really!). He solved the problem in 1:11:41 and used C#. Here’s his solution:
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Challenge4
{
class Program
{
static void Main(string[] args)
{
// Read tile data
var tileData = File.ReadAllLines(@"c:\test\tiles.txt").SkipWhile(l => l.StartsWith("#"));
var tiles = tileData.Select(singleTileData => new Tile(singleTileData)).ToList();
// Get a list of available tiles
var tileBag = new List<SingleTile>();
foreach (var templateTile in tiles)
{
for (int i = 0; i < templateTile.Quantity; i++)
{
tileBag.Add(new SingleTile(templateTile));
}
}
// Get a grid to fill in
var grid = new SingleTile[7, 7];
var startingTile = tileBag.First(tile => tile.Letter == 'D');
grid[3, 3] = startingTile;
startingTile.Used = true;
// Fill in the grid
if (!FillTheGrid(grid, tileBag))
{
Console.WriteLine("Unable to find solution!");
Console.ReadKey();
}
PrintTheGrid(grid);
SaveAsImage(grid);
Console.WriteLine(tileBag.Count(tile => !tile.Used));
Console.ReadKey();
}
private static void SaveAsImage(SingleTile[,] grid)
{
var tileImages = (Bitmap) Image.FromFile(@"c:\test\AllTiles.png");
var tileImage = new Bitmap[24];
for (int i = 0; i < 24; i++)
{
tileImage[i] = tileImages.Clone(new Rectangle(i*120, 0, 120, 120), PixelFormat.DontCare);
}
var outputImage = new Bitmap(840, 840);
using (var graphics = Graphics.FromImage(outputImage))
{
for (int x = 0; x < grid.GetLength(0); x++)
{
for (int y = 0; y < grid.GetLength(1); y++)
{
var thisTile = tileImage[grid[x, y].Letter - 'A'];
for (int r = 0; r < grid[x, y].Rotations; r++)
{
thisTile.RotateFlip(RotateFlipType.Rotate90FlipNone);
}
graphics.DrawImage(thisTile, x*120, y*120);
for (int r = 0; r < grid[x, y].Rotations; r++)
{
thisTile.RotateFlip(RotateFlipType.Rotate270FlipNone);
}
}
}
}
outputImage.Save(@"c:\test\Map.png");
}
private static void PrintTheGrid(SingleTile[,] grid)
{
for (int y = 0; y < grid.GetLength(1); y++)
{
for (int x = 0; x < grid.GetLength(0); x++)
{
if (grid[x, y] == null)
{
Console.Write("?? ");
}
else
{
Console.Write("{0}{1} ", grid[x, y].Letter, grid[x, y].Rotations);
}
}
Console.WriteLine();
}
}
static bool FillTheGrid(SingleTile[,] grid, List<SingleTile> tileBag)
{
bool allFound = true;
for (int x = 0; x < grid.GetLength(0); x++)
{
for (int y = 0; y < grid.GetLength(1); y++)
{
if (grid[x, y] == null)
{
allFound = false;
if (FillSingleTile(grid, tileBag, x, y))
{
return true; // Found a solution
}
}
}
}
return allFound;
}
static bool FillSingleTile(SingleTile[,] grid, List<SingleTile> tileBag, int x, int y)
{
foreach (var tile in tileBag.Where(tile => !tile.Used))
{
for (int r = 0; r < 4; r++)
{
if (ValidHere(grid, tile, x, y))
{
tile.Used = true;
grid[x, y] = tile;
// Show progress
PrintTheGrid(grid);
Console.WriteLine();
if (FillTheGrid(grid, tileBag))
{
return true;
}
tile.Used = false;
}
tile.Rotate();
}
}
grid[x, y] = null;
return false;
}
static bool ValidHere(SingleTile[,] grid, SingleTile tile, int x, int y)
{
if (!CheckNormalAdjacency(grid, tile.Features[3], x - 1, y, 1)) return false;
if (!CheckNormalAdjacency(grid, tile.Features[1], x + 1, y, 3)) return false;
if (!CheckNormalAdjacency(grid, tile.Features[0], x, y - 1, 2)) return false;
if (!CheckNormalAdjacency(grid, tile.Features[2], x, y + 1, 0)) return false;
if (!CheckSpecialAdjacency(grid, tile, x - 1, y - 1)) return false;
if (!CheckSpecialAdjacency(grid, tile, x - 1, y)) return false;
if (!CheckSpecialAdjacency(grid, tile, x - 1, y + 1)) return false;
if (!CheckSpecialAdjacency(grid, tile, x, y - 1)) return false;
if (!CheckSpecialAdjacency(grid, tile, x, y)) return false;
if (!CheckSpecialAdjacency(grid, tile, x, y + 1)) return false;
if (!CheckSpecialAdjacency(grid, tile, x + 1, y - 1)) return false;
if (!CheckSpecialAdjacency(grid, tile, x + 1, y)) return false;
if (!CheckSpecialAdjacency(grid, tile, x + 1, y + 1)) return false;
return true;
}
private static bool CheckSpecialAdjacency(SingleTile[,] grid, SingleTile tile, int x, int y)
{
if (x < 0 || x >= grid.GetLength(0) || y < 0 || y >= grid.GetLength(1))
{
return true; // Valid by default
}
var otherTile = grid[x, y];
if (otherTile == null) return true;
if (grid[x, y].Letter == tile.Letter) return false;
if (grid[x, y].Special == tile.Special && tile.Special != '.') return false;
return true;
}
private static bool CheckNormalAdjacency(SingleTile[,] grid, char feature, int x, int y, int edge)
{
if (x < 0 || x >= grid.GetLength(0) || y < 0 || y >= grid.GetLength(1))
{
return true; // Valid by default
}
var otherTile = grid[x, y];
if (otherTile == null) return true;
return otherTile.Features[edge] == feature;
}
public class Tile
{
public Tile(string tileData)
{
var splits = tileData.Split(' ');
Letter = splits[0].First();
Quantity = int.Parse(splits[1]);
Features = splits[2];
Special = splits[3].First();
}
public char Letter;
public int Quantity;
public string Features;
public char Special;
}
public class SingleTile
{
public SingleTile(Tile tile)
{
Letter = tile.Letter;
Features = tile.Features;
Special = tile.Special;
}
public char Letter;
public string Features;
public char Special;
public int Rotations = 0;
public bool Used = false;
public void Rotate()
{
Features = Features[3] + Features.Substring(0, 3);
Rotations = (Rotations + 1)%4;
}
}
}
}
His solution snakes from the top of the board to the bottom, restricting the next tiles as required. Most of the difficulty in this problem is getting all the information into code. Especially in the time that was provided.
If you managed to complete this problem at all, then you would have placed in our top 5!
FollowTags: 2016, solution, speed coding, technical
Categories: Social, Softwire, Technical