Evening Commute Solver

Question

I recently moved to an apartment overlooking the inner ring-road of town, and every day, a beautiful scene unfolds. The traffic lights are apparently so confusing (mostly because the Dutch are used to complex intersections, and this one is too simple for them to wrap their heads around), that the intersection invariably winds up as something that must have been the inspiration for a certain game which I shall call Evening Commute for copyright reasons which I will undoubtedly have circumvented by my clever renaming...

Please help my fellow confused Dutchmen, and make sure the red car makes it through the maze during Rush Hour!

Explanation of the game

The goal is to have the red car go to the right of a 6x6 grid (all the way off to the right), while only going straight forward or backward in the lengthwise direction of the car (which is 2 grid points long). For simplicity, the red car is always on the 3rd row.

Of course, there are obstacles: other cars and trucks, with length two. They can be placed horizontally and vertically, and can only move in their lengthwise direction. They cannot pass through other cars. All cars move at 1 grid point per move. The game is won when the red car can move off the grid at the right side of the board.

Explanation of the challenge

• Input: a valid game board, which is a 6x6 string with dots . for empty tiles, R's for the red (target) car on row 3, hex numbers 0 through B for cars (length 2), and hex numbers C through F for trucks (length 3). You need not worry about invalid boards; we are dealing with a carnage-free intersection.

Example input:

......
11..22
RRC...
..C..3
..C..3
..66..

As can be seen, numbers can be skipped; furthermore, there may be only trucks or only cars.

• Output: a sequence of moves. Each move is identified as XY, with X the identifier of the vehicle, and Y the move, which is one of v^<>, or down, up, left and right respectively for those not familiar with a certain programming language. The move Rx means 'move the red car off the board' and will always indicate the end of the sequence (and only appear at the end, of course!). Since the output is fairly unambigious, any easily human readable sequence of moves will do (newlines, leading spaces are allowed; even a single undelimited string will do; however, you are not allowed to use underhanded tricks on the output). A solution to above problem may be, for example, 6<6<CvRx.

In- and output is, if I made the challenge correctly, case-independent, and newlines can be assumed to be convenient to your language (no need for \r\n hell)

Scoring

The number of bytes (code-golf-style) plus the sum of the number of moves it takes you for each of the following test cases (I tried to calibrate the minimum number of moves to be competitive). Your program should be fully capable of solving any other test case I may throw at it, and hard-coding test cases will give you a penalty of 2^64, but if that's favourable, you might want to rethink your strategy.

11...C
D..E.C
DRRE.C
D..E..
2...33
2.FFF.

112.33
442..C
DRR..C
DEEE.C
D..566
77.588

C.1DDD
C.12..
CRR2..
3344.E
.....E
5566.E

C11.2.
C34.2D
C34RRD
EEE5.D
..6577
88699.

...next code-golf, somebody should make me a Rush Hour image recognition system.

Answer 1

Javascript (ES6), 1216 1206 1131 + 180 => 1311 bytes

a=>{a=a.replace(/\s/g,'');b=[];d={};e=[];f=[];g=[];h='.';[].concat.apply([],a.split('.').filter(k=>k).map(k=>k.match(/([^.])(\1*)/g)||k)).forEach(k=>k.length>1?(b.push(k[0]),(k.length<3?g:f).push(k[0])):(!e.includes(k)&&e.push(k),d[k]=d[k]?d[k]+1:1));Object.keys(d).forEach(k=>(d[k]<3?g:f).push(k));j=(l,m,n)=>l.substr(0,m)+n+l.substr(m+n.length);o=(p,q)=>~q.indexOf(p);I=(s,r,c)=>s.charAt(r*6+c)||'@';t=(s,r,c,F,G)=>{k=0;while(I(s,r+k*F,c+k*G)==h)k++;return k};u={};w=[];x={};x=(y,z,A)=>u[y]===[][0]?(u[y]=z,x[y]=A,w.push(y)):0;C=B=>{var z=u[B];return (!z?'':C(z))+x[B]};D=(B,r,c,q,E,F,G,n)=>{r+=E*F;c+=E*G;H=I(B,r,c);if(!o(H,q))return;L=o(H,f)?3:o(H,g)?2:[][0];J=B;for(i=0;i<n;i++){r-=F;c-=G;J=j(J,r*6+c,H);J=j(J,(r+L*F)*6+c+L*G,h);x(J,B,H+(!~F?'v':F?'^':!~G?'>':'<'));B=J}};x(a,null,'');K=!1;while(w.length) {B=w.splice(0,1)[0];if(I(B,2,5)=='R'&&!K){K=!0;break}for(r=0;r<6;r++){for(c=0;c<6;c++){if(I(B,r,c)!=h)continue;nU=t(B,r,c,-1,0);nD=t(B,r,c,1,0);nL=t(B,r,c,0,-1);nR=t(B,r,c,0,1);D(B,r,c,e,nU,-1,0,nU+nD-1);D(B,r,c,e,nD,1,0,nU+nD-1);D(B,r,c,b,nL,0,-1,nL+nR-1);D(B,r,c,b,nR,0,1,nL+nR-1)}}}return C(B).replace(/(R.)+$/,'Rx')}

I followed the algorithm and example from here. Rewriting the algorithm and input in the example to output moves cost a lot of bytes. I'm planning on rewriting the answer using an algorithm specifically designed for outputting moves instead of outputting board states.

Ungolfed:

func = inp => {
    inp = inp.replace(/\s/g, '');

    HORZS = [];
    tVERTS = {};
    VERTS = [];
    LONGS = [];
    SHORTS = [];
    EMPTY = '.';

    [].concat.apply([], inp.split('.').filter(k => k).map(k => k.match(/([^.])(\1*)/g) || k)).forEach(k =>
        k.length > 1 ? (
            HORZS.push(k[0]),
            (k.length < 3 ? SHORTS : LONGS).push(k[0])
        ) : (
            !VERTS.includes(k) && VERTS.push(k),
            tVERTS[k] = tVERTS[k] ? tVERTS[k] + 1 : 1
        )
    );
    Object.keys(tVERTS).forEach(k => (tVERTS[k] < 3 ? SHORTS : LONGS).push(k));

    setCharAt = (str, index, character) => str.substr(0, index) + character + str.substr(index + character.length);

    isType = (entity, type) => ~type.indexOf(entity);

    at = (state, r, c) => state.charAt(r * 6 + c) || '@';

    countSpaces = (state, r, c, dr, dc) => {
        k = 0;
        while (at(state, r + k * dr, c + k * dc) == EMPTY) k++;
        return k;
    };

    pred = {};
    queue = [];
    moves = {};

    propose = (next, prev, move) => pred[next] === [][0] ? (pred[next] = prev, moves[next] = move, queue.push(next)) : 0;

    trace = current => {
        var prev = pred[current];
        return (!prev ? '' : trace(prev)) + moves[current];
    };

    slide = (current, r, c, type, distance, dr, dc, n) => {
        r += distance * dr;
        c += distance * dc;
        car = at(current, r, c);
        if (!isType(car, type)) return;
        L = isType(car, LONGS) ? 3 : isType(car, SHORTS) ? 2 : [][0];
        sb = current;
        for (i = 0; i < n; i++) {
            r -= dr;
            c -= dc;
            sb = setCharAt(sb, r * 6 + c, car);
            sb = setCharAt(sb, (r + L * dr) * 6 + c + L * dc, EMPTY);
            propose(sb, current, car + (!~dr ? 'v' : dr ? '^' : !~dc ? '>' : '<'));
            current = sb;
        }
    };

    propose(inp, null, '');
    solved = !1;
    while (queue.length) {
        current = queue.splice(0, 1)[0];
        if (at(current, 2, 5) == 'R' && !solved) {
            solved = !0;
            break;
        }

        for (r = 0; r < 6; r++) {
            for (c = 0; c < 6; c++) {
                if (at(current, r, c) != EMPTY) continue;
                nU = countSpaces(current, r, c, -1, 0);
                nD = countSpaces(current, r, c, 1,  0);
                nL = countSpaces(current, r, c, 0, -1);
                nR = countSpaces(current, r, c, 0,  1);
                slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1);
                slide(current, r, c, VERTS, nD, 1,  0, nU + nD - 1);
                slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1);
                slide(current, r, c, HORZS, nR, 0,  1, nL + nR - 1);
            }
        }
    }

    return trace(current).replace(/(R.)+$/, 'Rx');
}

Example usage and output:

func(`......
11..22
RRC...
..C..3
..C..3
..66..`); // ==> "6<6<CvRx"

func(`11...C
D..E.C
DRRE.C
D..E..
2...33
2.FFF.`); // ==> "1>D^2^Cv3<3<3<CvCvEvF<F<EvRx"

func(`112.33
442..C
DRR..C
DEEE.C
D..566
77.588`); // ==> "3<C^R>R>2vE>E>2v2v2v1>4>D^D^R<R<E<E<E<5^5^5^Cv6<Cv8<Cv3>5^Rx"

func(`C.1DDD
C.12..
CRR2..
3344.E
.....E
5566.E`); // ==> "4>3>CvCvD>2^Rx"

func(`C11.2.
C34.2D
C34RRD
EEE5.D
..6577
88699.`); // ==> "D^9>5vE>E>E>E>Cv1<4^R<3v3vR<5^5^5^5^R>R>E<E<Dv7<Dv9<DvRx"