8
\$\begingroup\$

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!
\$\endgroup\$

3 Answers 3

2
\$\begingroup\$

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:=[:p :m|(s includes:p)ifFalse:[s add:p.q add:p->m]].
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.

add := [:p :m |
  (s includes:p) ifFalse:[
    s add:p.
    queue add:(p->m).
  ]].

add value:b value:''.

[
  |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
    ].
    add value:n value:v]
] loop.
\$\endgroup\$
0
\$\begingroup\$

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

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);
            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();
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Ungolfing the identifiers would be extremely helpful here... \$\endgroup\$ May 19, 2014 at 12:18
  • \$\begingroup\$ @AJMansfield If you want to understand this you can read my code review version of the same code: codereview.stackexchange.com/questions/50962/… \$\endgroup\$
    – durron597
    May 19, 2014 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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