# Connect the letters

Inspired by this little game.

## Challenge

Given as input the initial position of a grid (always 5x5), like this:

-ABCD
-A---
---C-
---BD
--E-E


You need to connect the letters (same letters all together), removing all empty - spaces. The letters will be always A,B,C,D and E.

Every pair of letters must be connected by a single unbranched line that can bend at right angles (using the very same letter to depict the line).

The input is guaranteed to have each starting letter exactly 2 times and it will always have all starting letters A-E.

The input can be read from stdin, or one only string as arg to some function, or even an array/matriz/list of chars, the most convinient way to your coding-language.

Since this is shortest code in bytes wins!

## Example

There is not only one solution to each problem, but the rules apply to all (no empty space and no separated letters). And the input is guaranteed to have at least one correct output.

Let's start connecting the letters A:

AABCD
AA---
AA-C-
AA-BD
AAE-E


Now, connecting the letters B:

AABCD
AAB--
AABC-
AABBD
AAE-E


Now, connecting the letters C:

AABCD
AABC-
AABC-
AABBD
AAE-E


Now, connecting the letters D:

AABCD
AABCD
AABCD
AABBD
AAE-E


And, finally the letters E:

AABCD
AABCD
AABCD
AABBD
AAEEE


## Another Samples

input:
E--E-
BB-C-
---C-

output:
EEEEE
BBECE

input:
A----
---B-
-C-C-
-D-D-
BE-EA

output:
AAAAA
BBBBA
BCCCA
BDDDA
BEEEA

• @Sp3000 not a dup, as this challenge has a guarantee of correct input. Mar 15, 2016 at 10:00
• Is the input guaranteed to have each starting letter exactly 2 times ? Will it always have all starting letters A-E ? Mar 15, 2016 at 10:04
• @NathanMerrill that seems like a fairly minor difference. I can't imagine that the check for solvability will would take up the majority of the code. Mar 15, 2016 at 10:52
• @MartinBüttner in my challenge, the check for solvability is the challenge, no connecting needed. While the two challenges will have similarities, they feel drastically different in my mind. Mar 15, 2016 at 11:11
• A favorite technique of mine for some questions like this is to use random numbers to fill in positions to avoid backtracking and stop if I hit a solution. That only works if a solution is guaranteed, otherwise the program can run forever (if a solution is guaranteed you can often write the code so that long runtimes get exponentially more unlikely for longer times). For this technique the questions are very different Mar 15, 2016 at 12:20

# Perl, 130128 127 bytes

Includes +4 for -n0 (program does not work from the commandline so - and space are counted too)

Call with the input on STDIN:

perl -n0 connectletters.pl
E--E-
BB-C-

Teminate with ^D or ^Z or whatever closes STDIN on your system
connectletters.pl:
/-/?map{$_="$$_$'";s%\pL%$_="$0$'";1while do{s/[$&-](.{5}|)0|0(.{5}|)[$&-]/0$+0/s};/$&/||$&%eg;!/1/&&do\$0}A..E:exit!print