10
\$\begingroup\$

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-
AD---
---C-
AD---

output:
EEEEE
BBECE
ADECE
ADECE
ADEEE

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

output:
AAAAA
BBBBA
BCCCA
BDDDA
BEEEA
Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ @Sp3000 not a dup, as this challenge has a guarantee of correct input. \$\endgroup\$
    – Nathan Merrill
    Mar 15, 2016 at 10:00
  • \$\begingroup\$ Is the input guaranteed to have each starting letter exactly 2 times ? Will it always have all starting letters A-E ? \$\endgroup\$
    – Ton Hospel
    Mar 15, 2016 at 10:04
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Martin Ender
    Mar 15, 2016 at 10:52
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Nathan Merrill
    Mar 15, 2016 at 11:11
  • 4
    \$\begingroup\$ 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 \$\endgroup\$
    – Ton Hospel
    Mar 15, 2016 at 12:20

1 Answer 1

Reset to default
4
\$\begingroup\$

Perl, 130 128 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-
AD---
---C-
AD---

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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.