This does not behave as expected in the test cases GRRY and GRBRY.
Oops. You're right. I've fixed the image now; reload. I forgot to preserve default-exits when I reduced the map vertically and horizontally.
EDIT: You are right. States 4,5,6,7,8,9,A,B,C,D,E fail to accept a following Y/G if entered from a red or blue self-loop. Mea culpa.
EDIT 2: Fixed. 152 parts. :)
<klmz> it reminds me of that people used to keep quoting adelikat's IRC statements in the old good days
<adelikat> no doubt
<adelikat> klmz, they still do
Bisqwit: if you actually managed to move the exit, Robotoast! could be solved in 0 parts. Many solutions could be greatly improved upon so if this is the case, would you be so kind to tell us how?
Bisqwit: if you actually managed to move the exit, Robotoast! could be solved in 0 parts. Many solutions could be greatly improved upon so if this is the case, would you be so kind to tell us how?
It is not possible. As I wrote earlier, these are illustrations, and only correct barring transcription errors. I wrote a program that eases the planning of the solutions when they do not immediately fit into the given size grid, or even the largest, 13x13 grid. As part of the ease of planning, the entry and exit points can also be moved. Naturally, when/if I reached the point that the solution would fit in the game's constraints, I'd use that instead of these illustrations. (Though I could still use an illustration instead for artistic purposes.)
Bisqwit, how did you make those awesome gifs? If it is something something you automated I would like to incorporate in my list (like on mouse over).
That accept if one of each color is present level is interesting, I think it might be possible even with the limited space, but this is something I need to work on more.
Edit: Ok it is possible
Scepheo wrote:
It's possible, but I'm quite sure you don't have enough space.
I started off trying to be super compact, and later realized certain parts I didn't need, and had plenty of space so the result isn't very aesthetically pleasing or compact.
Apparently there is a bug if you try to save on a custom level, it puts you back on the last level, but with your design intact, so I couldn't actually run this to test it, but theoretically it works (if not it is something silly like 1 conveyor facing wrong way). I will write an explanation/proof tomorrow.
Edit2: missed an overlapping conveyor, fixed
Edit3: missed a more serious problem, I'll fix tomorrw :(, picture removed
Edit4: nevermind it was correct, I need sleep
Bisqwit, how did you make those awesome gifs? If it is something something you automated I would like to incorporate in my list (like on mouse over).
Initially I created them by making a dozen screenshots until I've covered all five frames of animation, and then animating them using mogrify and gifsicle.
The later ones are created completely using this PHP script (click link).
It requires this graphics file, which also indicates the meanings of the numbers used to construct the map.
You can also access it directly. Just add the Manufactoria saved-game parameters to it, for example:
Too bad Manufactoria, when fed a level code, can't return whether the level works or not, otherwise, this whole smallest-level list could be an automated submission process. Ah well. But considering Bisqwit's last post, I'd better get to fixing my list. And I might decide to make a pretty html page for it (with images, of course).
@Bisqwit:
I don't think a string of zero length should be accepted. But if it should be, then just a small change would fix it:
Judiciary! 46 parts accepting null strings
<klmz> it reminds me of that people used to keep quoting adelikat's IRC statements in the old good days
<adelikat> no doubt
<adelikat> klmz, they still do
Oops. Nothing a quick and dirty fix can't handle though.
Seraphim, 21 parts:
?lvl=29&code=p12:6f7;c12:5f3;c12:4f3;c12:11f3;g12:3f3;p10:6f6;p14:6f0;r14:7f1;b10:5f3;b14:5f3;r10:7f1;p11:4f5;p13:4f5;g11:5f1;g13:5f1;q13:6f2;q11:6f4;q12:7f0;c12:10f3;c12:9f3;q12:8f0;
Fails with more than two strings in the input:
* bbGbbGbb (three strings)
* bGbG (three strings, the last one of which is empty)
* GGGG...GGGGG...G (lots of empty strings)
The correct implementation is like this (21 parts) (and it's faster)!
<klmz> it reminds me of that people used to keep quoting adelikat's IRC statements in the old good days
<adelikat> no doubt
<adelikat> klmz, they still do
@klmz: If you cannot make any assumptions on input strings, then you're right, my solution fails. But in that case your solution also fails at input bGbY for example.
In any case, the Malevolence Engine seems to only check inputs having 1 Green label and no Yellow labels, so I think it's irrelevant.
@Gunty:
Well, the main quest of the game stated that "NO ROBOT will have uellow or green on its tapes, UNLESS YOU PUT IT THERE". However, the bonus stages violate that by formally using green as the string separator. This could be justified is green is supposed to be "glue" to concatenate string tapes consist of red and blue. we have no clue of what yellow is and can't make any safe assumption of it.
<klmz> it reminds me of that people used to keep quoting adelikat's IRC statements in the old good days
<adelikat> no doubt
<adelikat> klmz, they still do
The Malevolence Engine seems to have a bone to pick with me. If I reuse my solution to robo-children which I put back on page 1, it finds no flaw but then calls me a cheater on the success screen and gives me no score.
The Malevolence Engine seems to have a bone to pick with me. If I reuse my solution to robo-children which I put back on page 1, it finds no flaw but then calls me a cheater on the success screen and gives me no score.
solution
You can't remove all of one color, then remove all the next because there is no way to tell once you've removed all of one color without entering a potential infinite loop. The other approach of seeing what the firt symbol is, forking for each case, would require 16 states with connections that probably make this impossible (bisqwit came close, but it didn't quite fit, and isn't fully correct yet, another error case is brgby, or any of the solo switches that want a color, but get one of the other pair colors first).
Solution:
The idea is to always make progress each time you return to the main loop (the black box). Progress is defined as removing at least one or exiting. If this holds true, it will eventually terminate. This solution is correct so long as the color removed was redudant (2 or more present) or this string lacks another color, in which case it doesn't matter what is removed since it is doomed to rightfully fail).
The blue red box is entered only when it knows a blue and a red have been encountered, likewise for the yellow green box. These just check then that the opposite two colors are present or fail if they aren't, using the brute force state method.
The blue box is entered only when a blue has been found and removed, it then adds a blue and finds the next blue or red. If a red is found, goto the blue red box (exit case). Otherwise a blue is found (impossible there there is no blue since one was added), then it is removed and we have accomplished our task for the main loop (2 blues removed, 1 added). If there were no more blues before adding one, then this loop won't exit until that same blue is found again. In this case that means there were no reds, so it is safe to fail, but we cannot not know this is the case, luckily this one blue is removed and the invariant is maintained.
The red box is the complement of the blue box.
If main loop does not encounter a red/blue, the orange box is entered. If the string is empty, we exit at the black X). Now suppose a yellow is encountered (equivalent logic for green), it is then added back, and another yellow green switch is encountered, if yellow there is net of -1 yellow, return to main loop, if green, yellow green are present, enter yellow green box. If blue, it is safe to enter the blue box which we have shown will make progress, (same for red). The last case to check for is a yellow or green followed by nothing, that same yellow that was added is then removed again in the next switch and sent back to the main loop, with progress (empty string now).
Therefore it is correct and exits.
PS: The malevolence engine is cool, now it would make sense to go for speed too (on the built in levels that is)
I went though and compared our list (update) to xkcds and the results were surprising, they managed to beat us in many levels that appeared optimal. Here is the summary of the differences. I have not had time to find the links to their solutions (it is possible they were not actually posted, but if you find them let me know please)
tasvideos losses on
Robo-children! nitsuja 17 v 16 Nix
Judiciary! klmz 46 v 39 J.P.
Politicians! scepho 23 v 20 Nix
Engineers! nitsuja 21 v 20 Nix
Seraphim klmz/gunty 21 v 19 tehtmi
Ophanim TheRandomPie_IV 53 v 40 J.P.
tasvideos wins on
Officers! flagitious 18 v 20 J.P.
Generals! flagitious 17 v 18 J.P.
Metatron flagitious 37 v 46 J.P.
Police klmz 32 v ??? (they quoted his)
I went though and compared our list (update) to xkcds and the results were surprising, they managed to beat us in many levels that appeared optimal. Here is the summary of the differences. I have not had time to find the links to their solutions (it is possible they were not actually posted, but if you find them let me know please)
If you're just looking for smaller solutions from any source, the Kongregate forums also have some winning devices:
Police! (29 parts) by yaichi, modification of barbrady1978
It is noted by yaichi that his Metatron solution fails on the null string, but the malevolence engine has no problems with that. Anyway, even though no one has tackled my first challenge yet, I've got another one that I think is considerably more fiendish:
Here are the codes for the winning XKCD leves:
Robochildren:
?lvl=18&code=c12:11f3;b10:6f3;p10:7f6;r10:8f1;y11:6f2;q11:7f4;c11:8f1;b12:5f3;p12:6f6;g12:7f3;p12:8f3;r13:8f0;r12:3f3;r12:4f3;p12:10f3;q12:9f0;
Judiciary:
?lvl=20&code=c10:5f3;g10:6f2;b11:2f3;p11:3f2;r11:4f1;p11:5f0;c11:6f3;c11:7f3;y11:8f3;c11:9f3;c11:10f2;c12:2f3;q12:3f7;c12:4f3;y12:5f0;b12:6f0;p12:7f0;r12:8f0;r12:9f3;q12:10f2;c13:3f0;p13:5f1;c13:6f1;q13:7f0;y13:8f2;q13:9f0;c13:10f2;c14:7f0;r14:8f2;p14:9f1;c14:10f1;q15:7f3;p15:8f1;q15:9f7;b15:10f0;b16:8f0;y16:9f1;c12:11f3;q12:12f6;
Politicians:
?lvl=22&code=c12:12f3;b10:6f3;p10:7f6;r10:8f1;y11:6f2;q11:7f4;c11:8f1;p11:9f0;r11:10f1;r12:3f3;b12:4f3;b12:5f3;p12:6f6;c12:7f3;g12:8f3;p12:9f3;q12:10f6;p12:11f3;r13:9f0;r12:2f3;
Engineers:
?lvl=24&code=c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c12:6f3;r11:1f3;p11:2f5;y12:2f3;c10:3f2;r10:4f1;i11:3f3;q11:4f0;c12:3f3;p12:4f3;c13:2f0;q13:3f0;b13:4f1;c12:5f3;
Seraphim:
?lvl=29&code=b10:5f3;p10:6f2;r10:7f1;p12:6f3;c12:9f3;c12:10f3;c12:11f3;r13:3f3;p13:4f0;b13:5f1;c13:6f1;q12:7f4;q12:8f0;q11:6f0;y11:5f1;q12:4f6;y12:3f3;g12:5f3;p11:4f5;
The xkcd topic also had a few posts concerning the SLOWEST solutions for problems, which seems to be an interesting challenge - unlike say a C++ program where you can just insert a for loop that does mindless work, anything in a manufactoria algorithm has to be changing state and/or doing work or it will go into an infinite loop. Couple that with a space restriction and there must be some upper limit to how long a solution can go for while still being valid. (Although it's likely that the upper limit could be made astonishingly high - think busy beaver problem.)
Thanks, Pointless Boy, although the metatron one is not a record, which is 37. BTW what was your first challenge (I'd probably want to start with it)?
There is also a forum at the main site, but its 26 pages...
Thanks random pie, I'll update the list today and convert it to html so links can be clicked.
Slowest is interesting, but I haven't even tried fastest yet.
I started off trying to be super compact, and later realized certain parts I didn't need, and had plenty of space so the result isn't very aesthetically pleasing or compact.
Apparently there is a bug if you try to save on a custom level, it puts you back on the last level, but with your design intact, so I couldn't actually run this to test it, but theoretically it works (if not it is something silly like 1 conveyor facing wrong way). I will write an explanation/proof tomorrow.
Edit2: missed an overlapping conveyor, fixed
Edit3: missed a more serious problem, I'll fix tomorrw :(, picture removed
Edit4: nevermind it was correct, I need sleep
The idea is to always make progress each time you return to the main loop (the black box). Progress is defined as removing at least one or exiting. If this holds true, it will eventually terminate. This solution is correct so long as the color removed was redudant (2 or more present) or this string lacks another color, in which case it doesn't matter what is removed since it is doomed to rightfully fail).
The blue red box is entered only when it knows a blue and a red have been encountered, likewise for the yellow green box. These just check then that the opposite two colors are present or fail if they aren't, using the brute force state method.
The blue box is entered only when a blue has been found and removed, it then adds a blue and finds the next blue or red. If a red is found, goto the blue red box (exit case). Otherwise a blue is found (impossible there there is no blue since one was added), then it is removed and we have accomplished our task for the main loop (2 blues removed, 1 added). If there were no more blues before adding one, then this loop won't exit until that same blue is found again. In this case that means there were no reds, so it is safe to fail, but we cannot not know this is the case, luckily this one blue is removed and the invariant is maintained.
The red box is the complement of the blue box.
If main loop does not encounter a red/blue, the orange box is entered. If the string is empty, we exit at the black X). Now suppose a yellow is encountered (equivalent logic for green), it is then added back, and another yellow green switch is encountered, if yellow there is net of -1 yellow, return to main loop, if green, yellow green are present, enter yellow green box. If blue, it is safe to enter the blue box which we have shown will make progress, (same for red). The last case to check for is a yellow or green followed by nothing, that same yellow that was added is then removed again in the next switch and sent back to the main loop, with progress (empty string now).
Therefore it is correct and exits.
PS: The malevolence engine is cool, now it would make sense to go for speed too (on the built in levels that is)