8
\$\begingroup\$

TL;DR: Solve this particular challenge, a robot simulation, by stepping on all of the white pads, and avoiding the gray pads. You can step on a white pad any number of times, as long as you step on each white pad at least once. Solutions in languages like Befunge with a 2D instruction pointer would also be accepted, but H comes with the uHerbert program and its language specifications are given below. You do not need the uHerbert program to solve this, but it makes checking your solution a lot easier.

Here is what the level looks like. This is a 25x25 grid of cells, in which the robot and each white and gray pad occupy one cell. The robot is initially facing upward.

enter image description here

Background on uHerbert

Herbert is a robot simulation which I first encountered in the online IGF (Independent Games Festival) programming challenge back in 2008. For a long time, I was disappointed that I couldn't try out the challenges after the actual contest was over. Luckily, someone else must have read my mind and coded up this dandy little program: uHerbert (aka mu-Herbert or micro-Herbert).

H (Language Specifications)

The program is a robot simulation, but also acts an interpreter for the programming language H which serves only to move the robot.

There are three instructions:

  • S: the robot steps one cell forward
  • L: the robot turns left 90 degrees in place
  • R: the robot turns right 90 degrees in place

There are three standard programming features at your disposal: functions, parameters, and recursion. Two different parameter types are supported.

Numeric parameters

g(A):sslg(A-1)

Here, g is a function with a one numeric parameter. This is boiler plate code; following this you can write your actual program by calling your function and passing an argument:

g(4)

This would call your function 4 times, and the recursion automatically terminates when your parameter A reaches a value of zero:

g(4) = sslg(4-1) = sslg(3) = sslsslg(2) = sslsslsslg(1) = sslsslsslssl

Functional parameters

You can also use functional parameters, which basically just reproduce instructions that you pass in:

f(A):rAlA

So if you call this function and pass instructions, it would evaluate to:

f(ss) = rsslss
f(sslssr) = rsslssrlsslssr

Other syntax

Functions can have more than one parameter, and they can also have both types. They could alternatively have no parameters. The following are both valid functions as well:

j:ssss
k(A,B):Ajjjk(A,B-1)

As you can see, the function j takes no parameters, and the function k takes both types of parameters. A is a functional parameter and B is a numeric parameter, as described above.

Infinite recursion

Infinite recursion is also allowed, but can only be initiated once and is effectively terminated when you step on the final white pad (without having stepped on any gray pads):

m:sslssrm

Solve condition

The goal is to get the robot to step on all of the white pads, and to avoid stepping on any of the gray pads. White pads can be stepped on any number of times, as long as each one is stepped on at least once. The robot is able to step on any point in the grid that it can reach (some levels have barrier walls and in this level the gray pads sort of act as a barrier).

The puzzle shown earlier is available on the site above from level_pack2.zip and is called level3.txt. Both the uHerbert program and the level pack are still available from the above link as of today (the site has been archived but the archive engine still hosts it), but they are not required for a solution.

I would like to see the shortest solution possible as per code golf. Solutions in languages other than H will not be accepted as valid. (It would certainly be interesting to see an example solution in a language like Befunge where the instruction pointer travels on a 2D grid, but per atomic code golf scoring, only H instructions can be given an accurate score. The instruction pointer could be treated as the robot's position, for example.) A valid solution is one where the robot steps on all the white pads (each at least once) and does not step on any gray pads. Stepping in other parts of the grid is fine but in this particular puzzle you can't do that without stepping on a gray pad. The starting position of the robot cannot be changed.

I should also note that solutions which jump to a non-adjacent cell will not be accepted. This is not possible for the robot in the simulation, and would not represent a valid solution. H does not allow this anyway. So a valid solution must be one comprised of single steps. For each cell in the grid, there are only four adjacent cells: the ones orthogonal to it (above, below, and to the left and right). This of course would disallow diagonal steps, but because you are only able to turn in 90 degree increments, diagonal steps are not even possible.

If the robot is given an instruction which requires it to move into a barrier or outside the grid, the result is basically "derp" - the robot hits the wall and stays where it is, and the instruction pointer moves to the next instruction (the instruction is basically skipped).

Note about solution size

When you open this level in the program, you'll notice it is apparently possible to solve in 13 bytes. I am totally baffled as to how that is possible, and curious to see how close others are able to come to that. My shortest solution is 30 bytes in H. If anyone wants me to post it, I will, but I'd like to see other solutions before posting mine. The program also gives you a score, but the score is irrelevant to this question. Solutions of any score will be accepted.

It seems that the uHerbert program does not count parentheses or colons as part of your program (you will see this when it counts up your bytes). So for the purposes of this question, in the H language, parentheses and colons will not count as bytes towards your solution since they are primarily delimiters and purely syntactical rather than semantic in nature.

\$\endgroup\$
6
\$\begingroup\$

H, 13 bytes

a:ssr
b:sasaaab
b

Demo

animation

\$\endgroup\$
  • \$\begingroup\$ Clever. I remember poking at this puzzle back when it was first posted but I didn't find this solution. \$\endgroup\$ – Draco18s Jul 30 '17 at 5:04
  • \$\begingroup\$ Excellent work. This is clearly the intended solution. \$\endgroup\$ – Tim Jul 31 '17 at 14:27

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.