Maybe Smallest Mouse

[MerickOWA]

Darn it! I don't know how to squeeze any more instructions out of this mouse!

I'm down to 25 and have no idea how to get that last instruction out.

How did you come up with 2 instructions smaller so quickly!?

[adum]

well, let's just say i combined two ideas =) i had the advantage of seeing your solution to the previous challenge, which helped me, so it's not totally fair on my part =)

adum

[sigi]

ARGLGL... you guys drive me crazy. I spent quite a few hours now to get it below THIRTY and now I'm being asked for TWENTY-SEVEN and you're suggesting that it's even going to continue after that!?

The pain... goggles... don't help... must... use... powers

[gfoot]

I'm still stuck at 28... I only need to shave off one more for "mus minutoides", but hearing that you later need to do it in 24 means I might as well just go straight for that. I guess it means using a totally different approach - I can't see shaving off four instructions without changing the algorithm significantly.

[therethinker]

I hate these optimization challenges

Maybe you could also try challenges where you have to do it in under X cycles? I'm not sure if instructions & cycles become intertwined as you optimize, but it still might prove interesting, and end up being more of a RL scenario.

[gfoot]

Some of the challenges already are cycle-limited, e.g. Labyrinth and Flash Flood. One problem with these is that, unless it runs your program to completion anyway, it can't tell you how much over the limit you were. That's more of a problem on Flash Flood, where the data set is secret, so you can't try it out locally with a high cycle limit on the actual data set used in the challenge.

[adum]

i wonder if 24 instructions can be brute forced, if you are somewhat smart about pruning?

[gfoot]

I thought of it.

One interesting ramification is that brute-forcing 24 instructions would effectively also find all shorter solutions.

[gfoot]

Hmm, I don't now think that brute force is as impractical as I originally thought. By my calculation, the search space is equivalent to 70-80 bits of binary. Much less than Scrambled Eggs! I've set something up that can vaguely prune large(ish) parts of the search space - I'm not convinced about how effective that is, though, in practice.

It is rather slow though... I've currently set it off finding all programs up to 7 instructions long that add together the first two memory locations and print the result. It'll take several hours, I think. So searching the space of 24-instruction programs is beyond its scope without significant pruning, and/or heuristics to reduce the cost of rejecting a program or deciding not to recurse any deeper.

[sigi]

I've thought a bit about if it's worth pursuing this further. The unpruned search space is very large. One has to do some static analysis and pruning, and it should be more than just trivial pruning.

For the question at hand, it is obvious that the resulting program needs to contain at least a "p" (to print the answer), a "<" (because one has to access memory), and either a "-" or a ":", or both (probably both, but the comparison calls for either of them), and also a "?", because a condition needs to be tested. I'm sure one can come up with more restrictions like these for the question at hand. This means that the starting length for the programs to test has a lower bound (they need to contain at least one of each of the abovementioned instructions), and also that one can straight away skip all candidates that are missing any of these.

That should be the first step of narrowing it down, and then one has to think about how to prune effectively.

Care has to be taken, because we don't want to rule out "crazy" solutions through careless pruning. E.g. a 20-code version that crashes might as well produce a miraculous result after appending 1 more instructions, etc.

Still, I think it would be interesting to see if a brute force search is feasible. Probably one could also use an optimized version of the virtual machine.

[gfoot]

I'd be very careful about prescribing the form too much. Things like requiring a "p" and a "<" are sensible, but don't help much because most of the programs will have both those characters somewhere in them (think how small 25**24 is compared to 27**24).

I prune the tree on solutions that jump out-of-bounds beyond the instruction limit (it's OK if they jump beyond the end of the program, so long as it's within the instruction limit, because we need to recurse down to get longer programs). Pretty much any other exception means don't bother recursing. Printing something that's wrong immediately prunes; accessing memory out of bounds prunes; termination via "!" prunes. Mostly, this is based around there being no sense in extending a program that will never reach the new instructions.

I also only bother running programs that end with interesting characters - "pg?c$" I think. Anything else is pointless at the end of the program. But that's not a very powerful optimization - at best it skips about 1 in 30 programs.

Actually I think this brute-forcing is more interesting than actually thinking about the problem.

Edit: do these count as spoilers?

[the_impaler]

I've got the idea to solve Mus Minutoid while sitting in traffic and it worked. And I have no idea how to make it even shorter - waiting for some serious traffic jam, I guess.
May be you should try brute force starting from the other end - start from known 28 steps solution and try to shorten it. This way you would have less combinations to try .
I think i just let my cat to walk on keyboard and it may have a better chances.

[adum]

good news: this can be solved in 23 instructions, i just realized (by looking at tog's very clever solution), so a brute force is a degree easier =)

[gfoot]

It's scary how quickly he came up with those answers.

I feel like an old man now.

[the_impaler]

It's scary how quickly he came up with those answers.

I feel like an old man now.

yeah, I feel like leaking memory too
I need to make a punch card challenge or something in Algol 68 ... kharh-khargh-kharargh