8
Flux is very similar to the Fifteen Puzzle.
However, instead of numbers, the squares are colors.
- There are 4 colors: Red, Yellow, Blue, and Gray.
- There are exactly 4 red squares, 4 yellow squares, 2 blue squares, 1 gray square, and 1 empty square.
- The grid has 3 rows and 4 columns
- A grid configuration is solved when the top row is exactly the same as the bottom row.
- The middle row is not relevant when considering whether the board is solved.
- You do not have to handle invalid input. Trust that there will be the correct number of each of the input symbols.
Input
- You must accept an input of twelve of these characters that use these symbols to represent a square on the board:
RYGB_
- These input characters must be interpreted to go across, then down.
- It is your choice whether you require some other character (newline, EOF, whatever) to terminate input, or just go as soon as you've received 12 characters.
Example:
YRGYB_BRRYYR
which corresponds to to the board:
YRGY
B_BR
RYYR
Output
- You must output the moves required for an OPTIMAL solution
- These will use the characters
LRUD
for Left, Right, Up, Down. This is considered to be the "piece moves to the left", not the "emptiness moves to the left"
Example:
LURDRDLULDLU
And then print out the resulting board. For the example we've used so far:
RBYR
YYG_
RBYR
Other rules
- Your program must run in under 15 seconds or it is disqualified.
- Make sure to try it with the following board:
RRRRBG_BYYYY
- That board, with it's three symmetries, is the "hardest" possible board.
- Make sure to try it with the following board:
- You may not use any external resources, or have any input data files.
Some stats
- There are exactly 415,800 possible boards
- There are exactly 360 "solution" boards
- My program that I wrote to test this out runs in about 2 seconds in Java, without much optimization.
- This program, with minimal golfing, is 1364 bytes.
Scoring
- This is code-golf, fewest characters that meets the other requirements wins!
Have you tried it with
RRRRBG_BYYYY
? I just tried it on ideone and it said "time limit exceeded" – durron597 – 2014-05-14T21:50:02.237@durron597 Yeah that seems to take well over the limit (I only tested with your example and some trivial cases :\ ) I will try to optimize it to stay within the limit later. It might help to add some of the longest examples to test in the question. (Off the top of my head I don't really know what these would look like or how many moves they would take) – KSab – 2014-05-14T21:59:54.600
that is the longest example :) – durron597 – 2014-05-14T22:00:23.913