🐸🐸

You must make the shortest program to always find the optimal solution to a simplified Frogger game on a 9x9 grid.

Course Elements:

• L - Log (Length: 3-4). When you hop on a log, it carries you with it.
• V - Vehicle (Length: 1-2)
• Speed (1-2): On the left hand side of the row will be the speed that elements in the row move.
• Spaces: There will always be at least two spaces between elements.
• Direction: In both the Vehicle and the Log sections, the direction of movement in each lane alternates between left and right.

Course Structure:

• If it's capital, it goes right; if it's lowercase, it goes left. All elements in a row go the same direction. As soon as part of an element goes off the screen, it will appear on the opposite side of the screen.
• The first row is a safe zone. The frog starts at F, which is always the same spot.
• The next 3 rows are roads with Vehicles.
• The next row is a safe zone.
• The next 3 rows are water (touching water == death) with Logs.
• Once you reach the W lane you win.
• If the frog dies it goes back to F

Player Controls:

• L - Left
• R - Right
• U - Up
• D - Down
• W - Wait

After you move, another frame passes. (Note that the frame passes after your move, not at the same time as your move.) Your program must give the optimal solution as a sequence of characters such as URWUUL. If a course has no solution, your program should output N.

Examples: (Since I did these by hand I don't know if they are optimal solutions.)

0WWWWWWWWW
1  lll
2  LLLL
2  llll
0
1  vv  vv
1  V  V
1   vv
0    F    

Solution: WUWUUURWUULWUU

0WWWWWWWWW
2   lll
1   LLLL
1   lll
0
2   vv
1  VV
2   vv
0    F    

Solution: WUWUWUUWUUWWUU

0WWWWWWWWW
2   llll
2   LLL
1   llll
0
2  v   vv
1  VV  VV
1  v  v
0    F    

Solution: WWUUUURURRWWUUU

0WWWWWWWWW
2  llll
2   LLL
1   lll
0
1   vv  v
2 V  V  V
2 v  v  v
0    F    

Solution: N (No way to get past first row.)

Test these in the snippet by pasting the course into the textbox and pushing "Load Course". Then paste the solution into "Input" and push submit.

Snippet: It's hard to make test cases, so I made this snippet which lets you see if your program can solve randomly-generated courses. For testing purposes, all you need to do is input your program's solution (e.g. LRUWL...) into the "Input" section and push submit. To reset the course back to it's original state push "Reset". Let me know if you find any bugs.

var timer;
var f_x, f_y;
var replaced;
var copy;
document.body.onkeyup = function(e) {
var a = document.activeElement;
if (a !== controls && a !== data) hop(e.keyCode);
};

function setup() {
stop();
var rows = game.children;
rows[0].innerHTML = "0WWWWWWWWW";
rows[2].innerHTML = "0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
rows[4].innerHTML = "0&nbsp;&nbsp;&nbsp;&nbsp;F&nbsp;&nbsp;&nbsp;&nbsp;";
copy = game.innerHTML;
save();

f_x = 5;
f_y = 9;
replaced = " ";
}

function save() {
data.value = "";
for (var i = 1; i <= 9; i++) {
data.value += getRow(i).textContent;
if (i < 9) data.value += "\n";
}
}

stop();
var rows = data.value.split("\n");
replaced = " ";
for (var i = 0; i < rows.length; i++) {
var r = getRow(i + 1);
r.innerHTML = rows[i].replace(/ /g, "&nbsp;");
if (rows[i].indexOf("V") !== -1 || rows[i].indexOf("L") !== -1) r.className = "right";
else if (rows[i].indexOf("v") !== -1 || rows[i].indexOf("l") !== -1) r.className = "left";
var f = rows[i].indexOf("F");
if (f !== -1) {
f_y = i + 1;
f_x = f;
}
}
copy = game.innerHTML;
}

function reset() {
stop();
game.innerHTML = copy;
f_x = 5;
f_y = 9;
replaced = " ";
}

function play() {
if (!timer) {
timer = setInterval(next, 1500);
}
}

function stop() {
if (timer) {
clearInterval(timer);
timer = null;
}
}

function input(i) {
var s = controls.value;
if (i === 0) {
stop();
sub.disabled = true;
}
if (s[i] === "L") hop(65);
else if (s[i] === "U") hop(87);
else if (s[i] === "R") hop(68);
else if (s[i] === "D") hop(83);
next();
if (i < s.length - 1) setTimeout(function() {
input(i + 1);
}, 750);
else sub.disabled = false;
}

function load(part, code) {
for (var r = 0; r < 3; r++) {
var row = part.children[r];
var s = "";
var dir = r % 2;
row.className = dir === 1 ? "right" : "left";
s += Math.floor(Math.random() * 2) + 1;
var end = 0;
for (var c = 0; c < 9-end;) {
var spaces = Math.min(9 - end - c , Math.floor(Math.random() * 2) + 2);
if(c === 0 && end===0) {
spaces = Math.floor(Math.random()*4);
end = Math.max(0,2-spaces);
}
s += "&nbsp;".repeat(spaces);
c += spaces;
var type = "";
var len = 0;
var rand = Math.floor(Math.random() * 2);
if (code === "L") {
type = dir === 1 ? "L" : "l";
len = rand + 3;
} else {
type = dir === 1 ? "V" : "v";
len = rand + 1;
}
if (c + len > 9-end) continue;
s += type.repeat(len);
c += len;

}
row.innerHTML = s + "&nbsp;".repeat(end);
}
}

function next() {
move(logs);
move(cars);
}

function move(part) {
var rows = part.children;
for (var i = 0; i < rows.length; i++) {
var s = rows[i].textContent;
var f = s.indexOf("F") !== -1;
if (f) {
replace(f_y, f_x, false);
s = rows[i].textContent;
}
var speed = s[0];
var stuff = s.substring(1);
var v = vel(speed, rows[i].className);
rows[i].textContent = s[0] + shift(stuff, speed, rows[i].className);
if (f) {
if (part === logs) {
f_x += v;
if (f_x < 1 || f_x > 9) {
go(5 - f_x, f_y - 9);
return;
}
}
replace(f_y, f_x, true);
s = rows[i].textContent.substring(1);
var c = f_x + v;
var t = "";
if (c > 9) t = s.substring(f_x) + s.substring(0, c - 9);
else if (c < 0) t = s.substring(0, f_x) + s.substring(9 + c);
else t = v > 0 ? s.substring(f_x, c) : s.substring(c, f_x);
if (t.indexOf("V") !== -1 || t.indexOf("v") !== -1) {
go(5 - f_x, f_y - 9);
}

}

}
}

function vel(mag, dir) {
var d = dir === "right" ? 1 : -1;
var m = parseInt(mag);
return d * m;
}

function shift(s, n, d) {
n = parseInt(n);
for (var i = 0; i < n; i++) {
if (d === "left") {
s = s.substring(1) + s.substring(0, 1);
} else {
s = s.substring(s.length - 1) + s.substring(0, s.length - 1);
}
}
return s;
}

function hop(k) {
if (k === 65) go(-1, 0);
else if (k === 87) go(0, 1);
else if (k === 68) go(1, 0);
else if (k === 83) go(0, -1);
}

function go(x, y) {

replace(f_y, f_x, false);
f_y -= y;
f_x += x;
replace(f_y, f_x, true);
if (f_x < 1 || f_x > 9 || f_y > 9) {
go(5 - f_x, f_y - 9);
return;
}

if (f_y == 1) {
go(5 - f_x, f_y - 9);
}

}

function replace(y, x, f) {

var row = getRow(y);
if (!row) return false;

var s = row.textContent;
if (x < 1 || x >= s.length) return false;
if (f) {
replaced = s[x];
if (replaced === "V" || replaced === "v" || (replaced.charCodeAt(0) === 160 && y < 5)) {
go(5 - f_x, f_y - 9);

} else {
row.textContent = s.substring(0, x) + "F" + s.substring(x + 1);
}
} else {
row.textContent = s.substring(0, x) + replaced + s.substring(x + 1);
}

}

function getRow(y) {
if (y < 1 || y > 9) return false;
if (y === 1) return game.firstChild;
if (y === 9) return game.lastChild;
if (y > 5) return cars.children[y - 6];
if (y < 5) return logs.children[y - 2];
return game.children[2];
}
<body onload="setup()"><code id="game"><div></div><div id="logs"><div></div><div></div><div></div></div><div></div><div id="cars"><div></div><div></div><div></div></div><div></div></code>
<input type="button" value="Step" onclick="next()" />
<input type="button" value="Pause" onclick="stop()" />
<input type="button" value="Play" onclick="play()" />
<input type="button" value="Reset" onclick="reset()" />
<input type="button" value="New Course" onclick="setup()" />
<div>Controls: WASD</div>
<div>Input:
<input type="text" id="controls" />
<input type="submit" onclick="input(0)" id="sub" />
</div>
<div>
<textarea id="data" rows=9 cols=12></textarea>
<input type="button" onclick="save()" value="Save Course" />
</div>
</body>

Where to Start:

Related:

• For those who can't see them, the first two characters of the post are Unicode U+1F438 : Frog Face
– cat
Jan 5, 2016 at 19:06
• Solution: WWUUUURURRWWUUU -> Chewie playing frogger. Jan 5, 2016 at 21:14
• @DigitalTrauma "Let the Wookie win" - C3PO, to an arcade machine. Jan 5, 2016 at 22:02
• Also what happens if the frog hits the edge of the screen? Jan 5, 2016 at 23:54
• @quintopia Lowercase is left, so they go left. Jan 6, 2016 at 3:33

Javascript, 854 bytes

function f(w){h=[];z=[];for(y=0;y<9;y++){l=w.split('\n')[y];r={s:parseInt(l[0]),d:1,e:[]};for(x=0;x<9;x++){c=l[1+x];if(c=='v'||c=='l')r.d=-1;r.e.push(c);}z.push(r);}h.push(z);h.push(z);for(g=2;g<40;g++){z=JSON.parse(JSON.stringify(z));for(y=0;y<9;y++){r=z[y];if(r.s>0&&(g%2==0||r.s==2)){i=0;t=0;if(r.d==-1){t=r.e[0];for(i=0;i<8;i++)r.e[i]=r.e[i+1];r.e[i]=t;}else{t=r.e[8];for(i=8;i>0;i--)r.e[i]=r.e[i-1];r.e[i]=t;}}}h.push(z);}j=15;k="";m(0,4,8,"","");return k==""?"N":k;function m(s,a,b,u,v){if(s<j){q={'U':[0,-1],'D':[0,1],'L':[-1,0],'R':[1,0]}[u];if(q)a+=q[0],b+=q[1];v+=u;if(!b){j=s;k=v;return;}if(s>0){for(i=0;i<3;i++){z=h[s*2+i-2];r=z[b];if(i&&(i==1||r.s==2)&&r.e[a].toUpperCase()=='L')a+=r.d;if(a<0||a>8||b>8)return;z=h[s*2+i-1];e=z[b].e;if(e[a].toUpperCase()=='V'||(b<4&&e[a].toUpperCase()!='L'))return;}}t="UWRLD";for(x in t)m(s+1,a,b,t[x],v);}}}


Ungolfed

function solve(input) {
var grids = [];
var maxgrid = 40;
var grid = [];
var lines = input.split('\n');
for (var y = 0; y < 9; y++) {
var line = lines[y];
var row = {
speed: parseInt(line[0]),
direction: 1,
cells: []
}
for (var x = 0; x < 9; x++) {
var c = line[1 + x];
if (c == 'v' || c == 'l')
row.direction = -1;
row.cells.push(c);
}
grid.push(row);
}
grids.push(grid);
grids.push(grid);
// animate grids
for (var g = 2; g < maxgrid; g++) {
grid = JSON.parse(JSON.stringify(grid));
for (var y = 0; y < 9; y++) {
var row = grid[y];
if (row.speed > 0 && (g % 2 == 0 || row.speed == 2)) {
if (row.direction == -1) {
var i, temp = row.cells[0];
for (i = 0; i < 8; i++)
row.cells[i] = row.cells[i + 1];
row.cells[i] = temp;
}
else {
var i, temp = row.cells[8];
for (i = 8; i > 0; i--)
row.cells[i] = row.cells[i - 1];
row.cells[i] = temp;
}
}
}
grids.push(grid);
}
var best = 15;
var best_moves = "";
var forceExit = false;

move(0, 4, 8, "", "");
return best_moves == "" ? "N" : best_moves;

function move(step, fx, fy, dir, moves) {
if (step >= best)
return "die";
switch (dir) {
case 'U':
fy--;
break;
case 'D':
fy++;
break;
case 'L':
fx--;
break;
case 'R':
fx++;
break;
}
if (dir != '')
moves += dir;
if (fy == 0) {
best = step;
best_moves = moves;
return "win";
}
if (step > 0) {
for (var i = 0; i < 3; i++) {
var grid = grids[step * 2 + i - 2];
if (i > 0 && (i == 1 || row.speed == 2)) {
var row = grid[fy];
if (row.cells[fx].toUpperCase() == 'L')
fx += row.direction;
}
if (fx < 0 || fx > 8 || fy > 8)
return "die";
var grid = grids[step * 2 + i - 1];
var cells = grid[fy].cells;
if (cells[fx].toUpperCase() == 'V')
return "die";
if (fy < 4 && cells[fx].toUpperCase() != 'L')
return "die";
}
}
move(step+1, fx, fy, 'U', moves);
move(step+1, fx, fy, 'W', moves);
move(step+1, fx, fy, 'R', moves)
move(step+1, fx, fy, 'L', moves);
move(step+1, fx, fy, 'D', moves)
}
}


I'm only testing for Up, Wait and Right in the example to speed things up:

JSFiddle

• Awesome that someone finally did this! Apr 17, 2019 at 21:44
• 805 bytes Sep 25, 2021 at 20:29