# Optimum Letter Cards for Spelling Words

Let's say you have a list of words and you want to be able to use letter cards to spell each word. For example, to spell cat, you would use three cards labelled C, A, T.

Assuming each card is double-sided, submit a program to define a minimum number of cards that can be used to spell the entire list of words.

Input is the word list, it can be file-based, hard-coded, command line, whatever. Output is the list of cards, formatted and ordered as you see fit, provided it is clear how the cards are labelled.

Case is not significant: Golf, golf and GOLF are equivalent.

Some hints:

• the number of cards can be no less than the length of the longest word
• it makes no sense for a card to have the same letter on both sides
• while case is not significant, recommend lower case to take advantage of certain symmetries

Examples, these take advantage of certain symmetries:

Input: ben, bog, bug, den, do, doe, dog, due, dug, Ed, end, gob, God, Ned, ode, pen, Poe, pug

Output: b/d, e/g, o/n

Input: an, and, ape, are, be, bed, bud, bur, Dan, Deb, dub, ear, Ed, era, nap, pan, pea, pub, Rae, ran, rub

Output: a/b, d/r, e/n

Making it a popularity contest, so elegance of code, run-time performance, and cleverness (including rule-bending & loopholes) are important!

Addition: Some have asked about "allowed" symmetries, whether special fonts can be used, and whether the cards can be folded.

Allowed symmetries are any letters which look similar to each other after 0, 90, 180 or 270 degrees rotation. This includes b/q, d/p and n/u. I would also say M/W, Z/N, and of course I/l (capital i, lowercase L). I'm probably scratching the surface, so if there are any others you're unsure about, just ask.

To keep it simple, please restrict to a standard sans-serif font, say that used in SE.

As far as folding, while you can do some amazing substitutions, e.g. B can be D, E, F, I, P, or R, and maybe C or L if you fold really creatively, I think that's bending, literally, too much!

I came up with this problem while playing with some similar cards with my kids. I noted how easy it was to come up with single-sided cards vs. how difficult it was to come up with double-sided cards.

Addition: Have provided a bounty to be awarded to the most popular answer. If there's a tie, will award to the one who submitted first.

Another hint:

• solving the single-sided problem will give you an idea of the minimum number of cards needed (e.g. 20 single-sided cards translates to at least 10 double sided-cards needed)

Addition: Oh bother, I was busy and forgot about the bounty expiring. It ended up going to no one because the only answer was submitted before the bounty started! Sorry about that.

• Just to clarify, what is allowed? Are the only symmetry pairs n/u, d/p? What about b/q and m/w? And what if I fold a P card in two so the top half becomes D? – Sp3000 Nov 17 '14 at 23:33
• 1. Is their a list of approved "symmetries", I would think that it could differ based on font, which is a potential loop hole(use a font where the characters are all the same, ie the cards would always be equal to / or something like that) 2. "Case is not significant" so "N" could be represented by "u"? – David Rogers Nov 18 '14 at 3:36
• I think you're doing your question an injustice by making it a popularity contest. You don't get creativity by telling people to be creative, you get it by giving them a hard challenge and having them squeeze out everything they can. – xnor Nov 18 '14 at 4:09
• @sp3000 - b/q of course. Regarding your other questions, I'll clarify the rules. – Yimin Rong Nov 18 '14 at 7:26
• Having this as a popularity contest (not to mention the bounty too) is not quite right. What gaurantee is there that the answers are optimal ? What if one answer gives suboptimal result, but for some reasons, has the highest votes.. – Optimizer Nov 21 '14 at 8:32

# C# - CardChooser

## Summary

This application uses a brute force method to attempt to solve each list. First I create a list of potential cards to select from, then I determine which is a best fit(removes the most chars + shortens long words most), add this to a result list and continue with this process until I have selected enough potential cards to remove every word in the list, then I rematch those cards to each word and print the output.

If you would like to see a more limited version of this code without downloading and building the provided windows forms application you can use the link provided to run my program on smaller sets of data, please note that this is the console application version so the resulting cards are NOT rotated: http://ideone.com/fork/VD1gJF

## Revision History

Current - Added better result optimization suggested by @Zgarb

Update 3 - More code cleanup, more bugs fixed, better results

Update 2 - Windows Forms, More verbose output

Update 1 - New/Better support for character symmetries

Original - Console Application

## Examples

acr, aft, ain, sll, win, say, said, fast, epic

hes, will, with, wont, would, wouldve, wouldnt, yet, you, youd, youll

aaaa, bbbb, cccc

## Code

I still need to combine this into one larger project with the ConsoleApp and WindowsForms code all sharing the same classes and methods, then split out the different regions in the RunButton_Click method so I can write units around them, anyway whenever I find time to do that I will, for now this is what I have:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace CardChooserForms
{
public partial class CardChooser : Form
{
private class Solution : IEquatable<Solution>
{
public List<string> Cards { get; set; }
public List<string> Remaining { get; set; }

public int RemainingScore
{
get
{
return this.Remaining.Sum(b => b.ToCharArray().Count());
}
}

public bool Equals(Solution other)
{
return new string(Cards.OrderBy(a => a).SelectMany(a => a).ToArray()) == new string(other.Cards.OrderBy(a => a).SelectMany(a => a).ToArray());
}

public override int GetHashCode()
{
return (new string(Cards.OrderBy(a => a).SelectMany(a => a).ToArray())).GetHashCode();
}
}
private class Symmetry
{
public char Value { get; set; }
public Int16 RotationDifference { get; set; }
}

/// <summary>
/// This is where Symmetries are stored, right now it only has support for pairs(two values per array)
/// </summary>
private static Symmetry[][] _rotatableCharacters = new Symmetry[][] {
new Symmetry[] { new Symmetry {Value = 'Z'}, new Symmetry {Value = 'N', RotationDifference = 90}},
new Symmetry[] { new Symmetry {Value = 'd'}, new Symmetry {Value = 'p', RotationDifference = 180 }},
new Symmetry[] { new Symmetry {Value = 'u'}, new Symmetry {Value = 'n', RotationDifference = 180 }},
new Symmetry[] { new Symmetry {Value = 'm'}, new Symmetry {Value = 'w', RotationDifference = 180 }},
new Symmetry[] { new Symmetry {Value = 'b'}, new Symmetry {Value = 'q', RotationDifference = 180 }},
new Symmetry[] { new Symmetry {Value = 'l'}, new Symmetry {Value = 'I', RotationDifference = 0}},
};

//These all control the output settings
private readonly static int _defualtSpacing = 25;
private readonly static int _defualtFontSize = 8;
private readonly static Font _defualtFont = new Font("Microsoft Sans Serif", _defualtFontSize);
private readonly static Brush _defualtBackgroundColor = Brushes.Beige;
private readonly static Brush _defualtForegroundColor = Brushes.Black;

public CardChooser()
{
InitializeComponent();
}

private void RunButton_Click(object sender, EventArgs e)
{
#region Input Parsing
//Get input
string input = InputRichTextBox.Text;

if (!input.Contains(","))
throw new ArgumentException("Input must contain more than one value and must be seprated by commas.");

//Parse input
var inputLowercasedTrimedTransformed = input.Split(',').Select(a => a.ToLowerInvariant().Trim()).ToArray();
var inputSplitTrimIndex = input.Split(',').Select(a => a.Trim()).ToArray().Select((a, index) => new { value = a, index }).ToArray();
#endregion Input Parsing

#region Card Formation
var inputCharParsed = inputLowercasedTrimedTransformed.Select(a => a.ToCharArray()).ToArray();
var possibleCards = GetAllCasesTwoLengthArrayElements(
UniqueBiDirection(
//Get unique characters
inputCharParsed
.SelectMany(a => a)
.Distinct()
.Select(a => new
{
Character = a,
PossibleCharacters = inputCharParsed.SelectMany(b => b).Where(b => b != a).ToList()
})
//Now get distinct cards(ie NB == BN, NB != NE)
.SelectMany(a => a.PossibleCharacters.Select(b => new string(new char[] { a.Character, b })).ToArray()).ToArray()
).ToArray()
).ToArray();

//Now get every possible character each card can eliminate
var possibleCharsFromCards = GetAllPossibleCharsFromACards(possibleCards).ToArray();

//Now set up some possibilities that contain only one card
var possibleCardCombinations = possibleCards.Select((a, index) => new Solution
{
Cards = new List<string> { a },
//Use the index of each card to reference the possible characters it can remove, then remove them per card to form a initial list of cards
Remaining = inputLowercasedTrimedTransformed.Select(b => b.RemoveFirstInCharArr(possibleCharsFromCards[index].ToLowerInvariant().ToCharArray())).ToList()
})
//Take the best scoring card, discard the rest
.OrderBy(a => a.RemainingScore)
.ThenBy(a => a.Remaining.Max(b => b.Length))
.Take(1).ToList();
#endregion Card Formation

#region Card Selection
//Find best combination by iteratively trying every combination + 1 more card, and choose the lowest scoring one
while (!possibleCardCombinations.Any(a => a.Remaining.Sum(b => b.ToCharArray().Count()) == 0) && possibleCardCombinations.First().Cards.Count() < possibleCards.Count())
{
//Clear the list each iteration(as you can assume the last generations didn't work
var newPossibilites = new List<Solution>();
var currentRoundCardCombinations = possibleCardCombinations.ToArray();
possibleCardCombinations.Clear();

foreach (var trySolution in currentRoundCardCombinations)
foreach (var card in possibleCards.Select((a, index) => new { value = a, index }).Where(a => !trySolution.Cards.Contains(a.value)).ToArray())
{
var newSolution = new Solution();
newSolution.Cards = trySolution.Cards.ToList();
newSolution.Remaining = trySolution.Remaining.ToList().Select(a => a.RemoveFirstInCharArr(possibleCharsFromCards[card.index].ToLowerInvariant().ToCharArray())).ToList();
}

//Choose the highest scoring card
possibleCardCombinations = newPossibilites
.OrderBy(a => a.RemainingScore)
.ThenBy(a => a.Remaining.Max(b => b.Length))
.Distinct().Take(1).ToList();
}
var finalCardSet = possibleCardCombinations.First().Cards.ToArray();
#endregion Card Selection

#region Output
using (var image = new Bitmap(500, inputSplitTrimIndex.Count() * _defualtSpacing + finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing))
using (Graphics graphic = Graphics.FromImage(image))
{
//Background
graphic.FillRectangle(_defualtBackgroundColor, 0, 0, image.Width, image.Height);

graphic.DrawString("Total Number of Cards Required: " + finalCardSet.Count(), _defualtFont, _defualtForegroundColor, new PointF(0, 0));
graphic.DrawString(
"Cards: " + String.Join(", ", finalCardSet.Select(a => a[0] + "/" + a[1])),
_defualtFont,
_defualtForegroundColor,
new RectangleF(0, _defualtSpacing, image.Width - _defualtSpacing, finalCardSet.Count() * 5));

//Results
foreach (var element in inputSplitTrimIndex)
{
//Paint the word
graphic.DrawString(element.value + " -> ", _defualtFont, _defualtForegroundColor, new PointF(0, element.index * _defualtSpacing + finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing));

//Now go through each character, determining the matching card, and wether that card has to be flipped
foreach (var card in GetOrderedCardsRequired(inputLowercasedTrimedTransformed[element.index].ToLowerInvariant(), finalCardSet.ToArray()).ToArray().Select((a, index) => new { value = a, index }))
using (var tempGraphic = Graphics.FromImage(image))
{
//For cards that need to flip
if (Char.ToUpperInvariant(element.value[card.index]) != Char.ToUpperInvariant(card.value[0]) &&
Char.ToUpperInvariant(element.value[card.index]) != Char.ToUpperInvariant(card.value[1]))
{
//TODO this is hacky and needs to be rethought
var rotateAmount = _rotatableCharacters
.OrderByDescending(a => a.Any(b => b.Value == Char.ToLowerInvariant(element.value[card.index])))
.First(a => a.Any(b => Char.ToUpperInvariant(b.Value) == Char.ToUpperInvariant(element.value[card.index])))
[1].RotationDifference;

//Rotate
tempGraphic.TranslateTransform(
_defualtSpacing * (_defualtFontSize / 2) + card.index * _defualtSpacing + (rotateAmount == 90 ? 0 : _defualtSpacing / 2) + (rotateAmount == 180 ? -(_defualtSpacing / 4) : 0),
finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing + element.index * _defualtSpacing + (rotateAmount == 180 ? 0 : _defualtSpacing / 2));
tempGraphic.RotateTransform(rotateAmount);

//Print string
tempGraphic.DrawString(
String.Join("/", card.value.ToCharArray().Select(a => new string(new char[] { a })).ToArray()),
_defualtFont,
Brushes.Black,
new RectangleF(-(_defualtSpacing / 2), -(_defualtSpacing / 2), _defualtSpacing, _defualtSpacing));
}
else
tempGraphic.DrawString(
String.Join("/", card.value.ToCharArray().Select(a => new string(new char[] { a })).ToArray()),
_defualtFont,
_defualtForegroundColor,
new RectangleF(
_defualtSpacing * (_defualtFontSize / 2) + card.index * _defualtSpacing,
finalCardSet.Count() * (_defualtFontSize / 2) + _defualtSpacing + element.index * _defualtSpacing,
_defualtSpacing, _defualtSpacing));
}
}

OutputPictureBox.Image = new Bitmap(image);
}
#endregion Output
}

private IEnumerable<string> GetAllPossibleCharsFromACards(string[] cards)
{
return cards.Select(a =>
new string(a.ToCharArray().Concat(_rotatableCharacters
.Where(b => b.Select(c => c.Value).Intersect(a.ToCharArray()).Count() > 0)
.SelectMany(b => b.Select(c => c.Value))
.Distinct().ToArray()).Distinct().ToArray()));
}

private IEnumerable<string> GetOrderedCardsRequired(string word, string[] cards)
{
var solution = new List<string>();
var tempCards = GetAllPossibleCharsFromACards(cards).Select((a, index) => new { value = a, index }).ToList();

foreach (var letter in word.ToCharArray())
{
//TODO this still could theoretically fail I think
var card = tempCards
//Order by the least number of characters match
.OrderBy(a => word.ToLowerInvariant().Intersect(a.value.ToLowerInvariant()).Count())
.ThenByDescending(a => tempCards.Sum(b => b.value.ToLowerInvariant().Intersect(a.value.ToLowerInvariant()).Count()))
//Then take the least useful card for the other parts of the word
.First(a => a.value.ToLowerInvariant().Contains(Char.ToLowerInvariant(letter)));
tempCards.Remove(card);
}
return solution;
}

private static IEnumerable<string> UniqueBiDirection(string[] input)
{
var results = new List<string>();
foreach (var element in input)
if (!results.Any(a => a == new string(element.ToCharArray().Reverse().ToArray()) || a == element))
return results;
}

private static IEnumerable<string> GetAllCasesTwoLengthArrayElements(string[] input)
{
if (input.Any(a => a.Length != 2))
throw new ArgumentException("This method is only for arrays with two characters");

List<string> output = input.ToList();
foreach (var element in input)
{
output.Add(new string(new char[] { Char.ToUpperInvariant(element[0]), Char.ToUpperInvariant(element[1]) }));
output.Add(new string(new char[] { element[0], Char.ToUpperInvariant(element[1]) }));
output.Add(new string(new char[] { Char.ToUpperInvariant(element[0]), element[1] }));
}
return output;
}

private void SaveButton_Click(object sender, EventArgs e)
{
using (var image = new Bitmap(OutputPictureBox.Image))
image.Save(Directory.GetCurrentDirectory() + "Output.png", ImageFormat.Png);
}
}

public static class StringExtensions
{
public static string RemoveFirstInCharArr(this string source, char[] values)
{
var tempSource = source.ToUpperInvariant();
foreach (var value in values)
{
int index = tempSource.IndexOf(Char.ToUpperInvariant(value));
if (index >= 0) return source.Remove(index, 1);
}
return source;
}
}
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;

namespace CardChooserForms
{
static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
static void Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new CardChooser());
}
}
}

namespace CardChooserForms
{
partial class CardChooser
{
/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel.IContainer components = null;

/// <summary>
/// Clean up any resources being used.
/// </summary>
/// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}

#region Windows Form Designer generated code

/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.InputRichTextBox = new System.Windows.Forms.RichTextBox();
this.EnterInputLabel = new System.Windows.Forms.Label();
this.RunButton = new System.Windows.Forms.Button();
this.OutputPictureBox = new System.Windows.Forms.PictureBox();
this.OutputPanel = new System.Windows.Forms.Panel();
this.SaveButton = new System.Windows.Forms.Button();
((System.ComponentModel.ISupportInitialize)(this.OutputPictureBox)).BeginInit();
this.OutputPanel.SuspendLayout();
this.SuspendLayout();
//
// InputRichTextBox
//
this.InputRichTextBox.Location = new System.Drawing.Point(60, 40);
this.InputRichTextBox.Name = "InputRichTextBox";
this.InputRichTextBox.Size = new System.Drawing.Size(400, 100);
this.InputRichTextBox.TabIndex = 0;
this.InputRichTextBox.Text = "";
//
// EnterInputLabel
//
this.EnterInputLabel.AutoSize = true;
this.EnterInputLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
this.EnterInputLabel.Location = new System.Drawing.Point(57, 20);
this.EnterInputLabel.Name = "EnterInputLabel";
this.EnterInputLabel.Size = new System.Drawing.Size(81, 17);
this.EnterInputLabel.TabIndex = 1;
this.EnterInputLabel.Text = "Enter Input:";
//
// RunButton
//
this.RunButton.Font = new System.Drawing.Font("Microsoft Sans Serif", 20F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
this.RunButton.Location = new System.Drawing.Point(60, 147);
this.RunButton.Name = "RunButton";
this.RunButton.Size = new System.Drawing.Size(180, 52);
this.RunButton.TabIndex = 2;
this.RunButton.Text = "Run";
this.RunButton.UseVisualStyleBackColor = true;
this.RunButton.Click += new System.EventHandler(this.RunButton_Click);
//
// OutputPictureBox
//
this.OutputPictureBox.Location = new System.Drawing.Point(3, 3);
this.OutputPictureBox.Name = "OutputPictureBox";
this.OutputPictureBox.Size = new System.Drawing.Size(500, 500);
this.OutputPictureBox.SizeMode = System.Windows.Forms.PictureBoxSizeMode.AutoSize;
this.OutputPictureBox.TabIndex = 3;
this.OutputPictureBox.TabStop = false;
//
// OutputPanel
//
this.OutputPanel.AutoScroll = true;
this.OutputPanel.Location = new System.Drawing.Point(4, 205);
this.OutputPanel.Name = "OutputPanel";
this.OutputPanel.Size = new System.Drawing.Size(520, 520);
this.OutputPanel.TabIndex = 4;
//
// SaveButton
//
this.SaveButton.Font = new System.Drawing.Font("Microsoft Sans Serif", 20F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
this.SaveButton.Location = new System.Drawing.Point(280, 147);
this.SaveButton.Name = "SaveButton";
this.SaveButton.Size = new System.Drawing.Size(180, 52);
this.SaveButton.TabIndex = 5;
this.SaveButton.Text = "Save";
this.SaveButton.UseVisualStyleBackColor = true;
this.SaveButton.Click += new System.EventHandler(this.SaveButton_Click);
//
// CardChooser
//
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(534, 737);
this.Name = "CardChooser";
this.Text = "Card Chooser";
((System.ComponentModel.ISupportInitialize)(this.OutputPictureBox)).EndInit();
this.OutputPanel.ResumeLayout(false);
this.OutputPanel.PerformLayout();
this.ResumeLayout(false);
this.PerformLayout();

}

#endregion

private System.Windows.Forms.RichTextBox InputRichTextBox;
private System.Windows.Forms.Label EnterInputLabel;
private System.Windows.Forms.Button RunButton;
private System.Windows.Forms.PictureBox OutputPictureBox;
private System.Windows.Forms.Panel OutputPanel;
private System.Windows.Forms.Button SaveButton;
}
}

• How do you spell "might" without an i card? – Claudiu Nov 18 '14 at 17:44
• "of course I/l (capital i, lowercase L)", so the lowercase l should stand for the capital I. – David Rogers Nov 18 '14 at 20:55
• oh it seems you should specify that in the output – Claudiu Nov 18 '14 at 22:13
• @Claudiu yeah I thought about that for awhile, this really comes down to the second question I asked Yimin Rong and I think he clarified it correctly, if I output a "l" in a card it should be inferred just like the examples that it can be used for both a upper cased I and lower l, that would results in a output that doesn't match the case perfectly but I think that's "OK" as it still satisfies the conditions of the question, but again I'm open to clarifying if necessary, maybe in a later version I can output the resulting generated strings with the characters rotated or something like that... – David Rogers Nov 19 '14 at 1:43
• i think there's a mistake. said's last letter isn't W or p – proud haskeller Nov 20 '14 at 10:50