12
1
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
- LeftR
- RightU
- UpD
- DownW
- 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";
load(logs, "L");
rows[2].innerHTML = "0 ";
load(cars, "V");
rows[4].innerHTML = "0 F ";
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";
}
}
function extLoad() {
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, " ");
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 += " ".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 + " ".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) {
alert("win!");
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="extLoad()" value="Load Course" />
<input type="button" onclick="save()" value="Save Course" />
</div>
</body>
Where to Start:
Related:
See also:
1
For those who can't see them, the first two characters of the post are Unicode U+1F438 : Frog Face
– cat – 2016-01-05T19:06:15.9776Solution:
WWUUUURURRWWUUU
-> Chewie playing frogger. – Digital Trauma – 2016-01-05T21:14:47.7133@DigitalTrauma "Let the Wookie win" - C3PO, to an arcade machine. – FryAmTheEggman – 2016-01-05T22:02:51.840
Also what happens if the frog hits the edge of the screen? – user81655 – 2016-01-05T23:54:04.157
@user8 you die and reset. You can try it on the snippet. – geokavel – 2016-01-05T23:55:05.820
@user81655 Ok, I made a new unbeatable course that ensures that there are always at least two spaces between vehicles. Thanks for noticing that. – geokavel – 2016-01-06T02:45:50.790
@user81655 Thank you for your comment! It has led to a significantly improved course generator (although they will be harder now :p). – geokavel – 2016-01-06T03:26:50.040
Are the odd rows (counting from frog's row = 0) left-moving or right-moving? – quintopia – 2016-01-06T03:32:18.133
2@quintopia Lowercase is left, so they go left. – geokavel – 2016-01-06T03:33:32.987