6
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is really close to being a duplicate of the most recent challenge. The only differences are that your grid and goal are fixed, and that tiles are rectangular and can only move along one axis. Well and of course that you don't require an optimal solution, but BFS will probably still make for the shortest code. Also, providing only 3 test cases is dangerous in that people could hardcode 3 optimal solutions. You should at least threaten to swap out the test cases if you suspect anyone of doing that. \$\endgroup\$ – Martin Ender Mar 27 '15 at 23:06
  • \$\begingroup\$ @MartinBüttner Oh dear... And there I was, searching the entire site for duplicates, but not the front page. Also, I meant to include a rule about the test cases, but that must have gotten lost in a rewrite. \$\endgroup\$ – Sanchises Mar 27 '15 at 23:10
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/48236/… (thanks @MartinBüttner) \$\endgroup\$ – Sanchises Mar 27 '15 at 23:14
  • \$\begingroup\$ In your first example, the truck F does not comply with the spec because it has 4 letters instead of 3. I assume this is a typo as it makes the puzzle impossible. In some of the others the red car can only leave by the left hand side (not the right.) I assume this is allowed. \$\endgroup\$ – Level River St Mar 27 '15 at 23:57
  • \$\begingroup\$ @steveverrill The first was a typo, the rest I double-checked and they are possible to go off on the right hand side. Of course, the red car may go left a few times to achieve this goal. (I didn't say the game is easy)... \$\endgroup\$ – Sanchises Mar 28 '15 at 8:37
1
\$\begingroup\$

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"
\$\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.