# Optimally solve the Flux Puzzle

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.
• 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!

# Smalltalk 497

|b R M s g a|
b:=Stdin nextLine.R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)(6 1)(4 6 1)(4 6 1)(4 1)).
s:=Set new.q:=OrderedCollection new.
a value:b value:''.
[|x i n p|
x:=q removeFirst.p:=x key.i:=(p indexOf:$_). (M at:i)do:[:m||v| n:=p copy.n at:i put:(p at:i+m-5);at:i+m-5put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9)ifTrue:[
v printCR.(n splitForSize:4)map:#printCR.^self].
a value:n value:v]]loop.


Input:

YRGYB_BRRYYR


Output:

DLURRULDDLLU
YBYR
RGR_
YBYR


Exec. Time (bytecode, not jitted): 100ms

Input:

RRRRBG_BYYYY


Output:

DRRUULLDLURDDRRULULD
YBRR
GY_Y
YBRR


Exec. Time 2s unjitted; 0.8s jitted (most time spent in collection code)

Here is an ungolfed version for readability:

|b R M s g add|
b:=Stdin nextLine.
R:='D--R-L--U'.
M:=#((6 9)(4 6 9)(4 6 9)(4 9)
(1 6 9)(1 4 6 9)(1 4 6 9)(1 4 9)
(6 1)(4 6 1)(4 6 1)(4 1)).
s := Set new.
queue := OrderedCollection new.

(s includes:p) ifFalse:[
]].

[
|x i n p|

x := queue removeFirst.
p := x key.
i := (p indexOf:$_). (M at:i) do:[:m | |v| n := p copy. n at:i put:(p at:i+m-5); at:i+m-5 put:$_.
v:=(x value,(R at:m)).
(n to:4)=(n from:9) ifTrue:[
v printCR.
(n splitForSize:4) map:#printCR.
^ self
].
] loop.


# Python 372

This was longer than I expected, I might go back later and see if I can optimize more. It uses a pretty inefficient method of brute-forcing the answer, but it seems to consistently run at no more than 8 seconds on my relatively old laptop.

A=lambda s,i,n:s[:i]+n+s[i+1:]
def M(b):
i=b.find('_')
for d,n in([('L',i+1)]if i%4<3 else[])+([('R',i-1)]if i%4>0 else[])+([('D',i-4)]if i>4 else[])+([('U',i+4)]if i<8 else[]):yield d,A(A(b,i,b[n]),n,'_')
def F():
c=[('',raw_input())]
while 1:
for (m,b)in c:
if b[:4]==b[8:]:return m,b
c=[(m+d,n)for(m,b)in c for(d,n)in M(b)]
print F()

• Have you tried it with RRRRBG_BYYYY? I just tried it on ideone and it said "time limit exceeded" – durron597 May 14 '14 at 21:50
• @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 May 14 '14 at 21:59
• that is the longest example :) – durron597 May 14 '14 at 22:00

# Java 1364

I golfed this some but I'm sure there's plenty more I could do. For example I close the input stream which is not necessary ;) I just wanted to put something up.

import java.util.*;class F{enum D{R{B b(B i){return i.z==3?null:g(i,1);}},L{B b(B i){return i.z==0?null:g(i,-1);}},D{B b(B i){return i.y==2?null:g(i,4);}},U{B b(B i){return i.y==0?null:g(i,-4);}};abstract B b(B i);B g(B i,int f){f+=4*i.y+i.z;char[]s=i.s.toCharArray();s[i.e]=s[f];s[f]='_';return w.get(new String(s));}}enum C{_,G,B,R,Y;}class B{C[][]a=new C[3][4];String s;int y,z,e,c;B p;D d;B(String p){int i,j,q;for(i=0;i<3;i++){for(j=0;j<4;j++){q=4*i+j;a[i][j]=C.valueOf(p.substring(q,q+1));if(a[i][j]==C._){y=i;z=j;e=q;}}}s=p;}boolean v(){return Arrays.equals(a[0],a[2]);}void p(B b,D n){p=b;d=n;c=p.c+1;}String g(){String u="\n";for(int i=0;i<3;i++,u+="\n")for(int j=0;j<4;j++)u+=a[i][j];return u;}}Set<B>b=new HashSet<B>(),p;static Map<String,B>w=new HashMap<>();void p(String f,String s){int n=s.length();if(n==0){B o=new B(f);w.put(f,o);if(o.v())b.add(o);}else{Set e=new HashSet();for(int i=0;i<n;i++){char c=s.charAt(i);if(!e.contains(c)){p(f+c,s.substring(0,i)+s.substring(i+1,n));e.add(c);}}}}public static void main(String[]a){new F().r();}void r(){Scanner c=new Scanner(System.in);String t=c.nextLine();p("",t);for(int i=0;i<20;i++,b=p){p=new HashSet<>(b);for(B o:b)if(o.c==i)for(D d:D.values()){B n=d.b(o);if(n!=null&&!p.contains(n)){n.p(o,d);p.add(n);}}}B q=w.get(t);while(!q.v()){System.out.print(q.d);q=q.p;}System.out.println(q.g());c.close();}}


Ungolfed:

import java.util.*;

class F {
enum D {
R {
B b(B i) {
return i.z == 3 ? null : g(i, 1);
}
},
L {
B b(B i) {
return i.z == 0 ? null : g(i, -1);
}
},
D {
B b(B i) {
return i.y == 2 ? null : g(i, 4);
}
},
U {
B b(B i) {
return i.y == 0 ? null : g(i, -4);
}
};

abstract B b(B i);

B g(B i, int f) {
f += 4*i.y + i.z;
char[] s = i.s.toCharArray();
s[i.e] = s[f];
s[f] = '_';

return w.get(new String(s));
}
}

enum C {
_, G, B, R, Y;
}

class B {
C[][] a = new C[3][4];
String s;

int y,z,e,c;

B p;
D d;

B(String p) {
int i,j,q;
for(i = 0; i < 3; i++) {
for(j = 0; j < 4; j++) {
q=4*i+j;
a[i][j] = C.valueOf(p.substring(q,q+1));
if(a[i][j] == C._) {
y = i;
z = j;
e = q;
}
}
}

s = p;
}

boolean v() {
return Arrays.equals(a[0], a[2]);
}

void p(B b, D n) {
p = b;
d = n;
c = p.c + 1;
}

String g() {
String u = "\n";
for(int i = 0; i < 3; i++,u+="\n")for(int j = 0; j < 4; j++) u += a[i][j];
return u;
}
}

Set<B> b = new HashSet<B>(),p;
static Map<String, B> w = new HashMap<>();

void p(String f, String s) {
int n = s.length();
if (n == 0) {
B o = new B(f);
w.put(f, o);
}
else {
Set e = new HashSet();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if(!e.contains(c)) {
p(f + c, s.substring(0, i) + s.substring(i+1, n));
}
}
}
}

public static void main(String[] a) {
new F().r();
}

void r() {
Scanner c = new Scanner(System.in);
String t = c.nextLine();

p("", t);

for(int i = 0; i < 20; i++, b=p) {
p = new HashSet<>(b);

for(B o : b)
if(o.c == i)
for(D d : D.values()) {
B n = d.b(o);
if(n != null && !p.contains(n)) {
n.p(o, d);
}
}
}

B q = w.get(t);
while(!q.v()) {
System.out.print(q.d);
q = q.p;
}
System.out.println(q.g());

c.close();
}
}

• Ungolfing the identifiers would be extremely helpful here... – AJMansfield May 19 '14 at 12:18
• @AJMansfield If you want to understand this you can read my code review version of the same code: codereview.stackexchange.com/questions/50962/… – durron597 May 19 '14 at 12:47