xkcd

by **phlip** » Wed May 26, 2010 11:11 am UTC

My times for Robo-children wrote:Test 0: 0:35
Test 1: 0:24
Test 2: 0:14
Test 3: 0:05
RndTest: 5:32
RndTest: 5:49

Yay for n² algorithms...
[edit]
Gah, my times for Rocket Planes are even worse... 7:34 to sort one of the random 10-bit sequences...

by **JavaBean** » Wed May 26, 2010 3:06 pm UTC

My robo-children answer is n² too, and with a slightly larger constant factor than yours. As Berengal demonstrated, though, it doesn't have to be - his looks n*log(n) to me, with a pretty small constant factor? Most of the time it's O(n), even, but for pathological inputs like RRRRRRRRRRRRBBBBBBBBBBBBB it will be n*log(n).

Rocket planes, though, seems like it absolutely has to be n², because you have to move N blue (or red) dots by an average of N/2 places, with only iterative access to the list.

My rocket planes performance is pretty poor, though since my design looks pretty efficient I think it's because I move reds to the back instead of blues to the front, and the test inputs have significantly more reds than blues. My times:
Test 0 0:20
Test 1 0:11
Test 2 0:05
Test 3 0:04
Test 4 1:43

by **D4N_** » Wed May 26, 2010 3:35 pm UTC

Just did Robo-Children with an incredibly slow algorithm, about 8 minutes on the random input. It's because I remove only 1 red and 1 blue on each iteration of the loop. The price of simplicity is inefficiency it seems.

by **Ephphatha** » Wed May 26, 2010 3:48 pm UTC

Robo-children wrote:0. 0:16
1. 0:05
2. 0:06
3. 0:05
Rnd 1. 0:44
Rnd 2. 0:59

Does alright on parts too,

Spoiler:

I really should go to bed instead of trying to optimise all my old solutions for space...

by **Steax** » Wed May 26, 2010 3:57 pm UTC

And thus, the complete opposite for robo-children: brute force?

Spoiler:

I know, I know.

by **D4N_** » Wed May 26, 2010 4:34 pm UTC

Your brute force method fails for certain inputs that the game doesn't give. For example 20B 20R or something similar, I'm pretty sure you could move all of those branches into a single loop and get something that works with a few modifications.

by **Steax** » Wed May 26, 2010 5:09 pm UTC

That's true, I meant that as a joke solution.

Now back to figuring out soldiers. I'm not good with binary arithmetic, can someone lend a hand? Not a complete solution, just what multiplication in binary is like. I have a shrewd feeling it has to do with a logical comparison...

by **TNorthover** » Wed May 26, 2010 5:15 pm UTC

Steax wrote:Now back to figuring out soldiers. I'm not good with binary arithmetic, can someone lend a hand? Not a complete solution, just what multiplication in binary is like. I have a shrewd feeling it has to do with a logical comparison...

Even simpler in this case. Multiplying by 2 is the binary equivalent of when we multiply by 10.

by **BobTheElder** » Wed May 26, 2010 5:20 pm UTC

Well thanks, xkcd, for totally distracting me from my project...

edit: robot planes is destroying my brain.

Not really a comment on the difficulty, I'm a computer programming noob. Just... argh.

by **Dr. Willpower** » Wed May 26, 2010 5:53 pm UTC

BobTheElder wrote:Well thanks, xkcd, for totally distracting me from my project...

edit: robot planes is destroying my brain.

Not really a comment on the difficulty, I'm a computer programming noob. Just... argh.

Roboplanes or Rocket Planes?

by **Steax** » Wed May 26, 2010 6:33 pm UTC

TNorthover wrote:
Steax wrote:Now back to figuring out soldiers. I'm not good with binary arithmetic, can someone lend a hand? Not a complete solution, just what multiplication in binary is like. I have a shrewd feeling it has to do with a logical comparison...

Even simpler in this case. Multiplying by 2 is the binary equivalent of when we multiply by 10.

Err, do you mean the other way around? So I should multiply by 2, three times, in which multiplying by 2 is simply adding another 0 at the end-

Oh my god. I feel like a total idiot now.

To raise my self-esteem, I finally finished Engineers. The real problem was getting it all to fit. I think I used a terribly efficient approach:

Spoiler:

Has anyone else finished that level? Care to share some ideas to optimize it? It took me a lot of shifting and nudging and moving around to even get a belt from the 'ok' point to the end cell.

EDIT: I feel like an even bigger idiot now.

Spoiler:

I got a simpler solution:
?lvl=24&code=c13:13f0;c18:13f0;c17:13f0;c16:13f0;c15:13f0;c14:13f0;c8:13f2;c9:13f2;c10:13f2;c11:13f2;c7:2f2;c8:2f2;c8:3f2;c8:4f1;c8:5f1;c8:6f1;c8:7f1;c9:2f2;c9:3f2;r9:4f2;c9:7f0;c10:2f2;c10:3f3;p10:4f7;c10:5f3;c10:6f3;i10:7f6;c11:2f2;c11:3f0;r11:4f3;c11:5f3;c11:6f2;c11:7f0;g12:2f3;p12:3f7;c12:4f3;c12:5f3;i12:6f7;i12:7f6;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c13:2f0;c13:3f2;b13:4f3;c13:5f3;i13:6f7;c13:7f0;c14:2f0;c14:3f3;p14:4f7;c14:5f3;i14:6f7;c14:7f3;c15:2f0;c15:3f0;b15:4f0;c15:6f2;c16:2f0;c16:3f0;c16:4f1;c16:5f1;c16:6f1;c17:2f0;c6:2f2;c18:2f0;c18:3f1;c18:4f1;c18:5f1;c18:6f1;c18:7f1;c18:8f1;c6:8f1;c6:7f1;c6:6f1;c6:5f1;c6:4f1;c6:3f1;c18:11f3;c18:12f3;c7:13f2;c6:13f2;c6:11f3;c6:12f3;c7:10f0;c8:10f0;p8:11f4;c9:11f0;c10:10f3;q10:11f7;c14:10f3;q14:11f3;c15:11f2;c16:10f2;p16:11f6;c10:8f3;c10:9f3;c14:8f3;c14:9f3;c17:10f2;c17:11f2;c18:10f1;c18:9f1;c6:10f1;c6:9f1;c7:11f0;

It was basically the first, but removed the need for the yellow marker. I realized that after the first part where I put the yellow marker, I only need the mark once anyway so I don't need to save it. I know the last color, so just check against the first color and kaboom, I'm set. The solution above is made bigger to ease someone who wants to see how it works.

How it works: Split red/blue. If it goes into red zone, that means the last checked one was red, and it's anticipating a green (end marker). It only writes the last checked one if it finds that the next is not green. If it does find a green, that means the last node in the strip was red. Get rid of the green; the first node is back on top. Check the first node. If it's red, then no need to rewrite anything; the last and first nodes are gone anyway, and repeat from the beginning. If they don't match, throw it away. If it's empty at this point, then we're done.

The beauty of this one is that we don't need to check if there's only 1 left; it automatically does so, because it never actually removes the last node, so it just ends up checking itself (and validating, thus clearing the strip).

by **Berengal** » Wed May 26, 2010 6:57 pm UTC

Not quite content with my sorting algorithm, I trippled it;

Spoiler:

Sorted a 49-long string consisting of mostly reds in a rather acceptable time.

by **TNorthover** » Wed May 26, 2010 7:41 pm UTC

Steax wrote:EDIT: I feel like an even bigger idiot now.
Spoiler:
I got a simpler solution:
?lvl=24&code=c13:13f0;c18:13f0;c17:13f0;c16:13f0;c15:13f0;c14:13f0;c8:13f2;c9:13f2;c10:13f2;c11:13f2;c7:2f2;c8:2f2;c8:3f2;c8:4f1;c8:5f1;c8:6f1;c8:7f1;c9:2f2;c9:3f2;r9:4f2;c9:7f0;c10:2f2;c10:3f3;p10:4f7;c10:5f3;c10:6f3;i10:7f6;c11:2f2;c11:3f0;r11:4f3;c11:5f3;c11:6f2;c11:7f0;g12:2f3;p12:3f7;c12:4f3;c12:5f3;i12:6f7;i12:7f6;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c13:2f0;c13:3f2;b13:4f3;c13:5f3;i13:6f7;c13:7f0;c14:2f0;c14:3f3;p14:4f7;c14:5f3;i14:6f7;c14:7f3;c15:2f0;c15:3f0;b15:4f0;c15:6f2;c16:2f0;c16:3f0;c16:4f1;c16:5f1;c16:6f1;c17:2f0;c6:2f2;c18:2f0;c18:3f1;c18:4f1;c18:5f1;c18:6f1;c18:7f1;c18:8f1;c6:8f1;c6:7f1;c6:6f1;c6:5f1;c6:4f1;c6:3f1;c18:11f3;c18:12f3;c7:13f2;c6:13f2;c6:11f3;c6:12f3;c7:10f0;c8:10f0;p8:11f4;c9:11f0;c10:10f3;q10:11f7;c14:10f3;q14:11f3;c15:11f2;c16:10f2;p16:11f6;c10:8f3;c10:9f3;c14:8f3;c14:9f3;c17:10f2;c17:11f2;c18:10f1;c18:9f1;c6:10f1;c6:9f1;c7:11f0;

It was basically the first, but removed the need for the yellow marker. I realized that after the first part where I put the yellow marker, I only need the mark once anyway so I don't need to save it. I know the last color, so just check against the first color and kaboom, I'm set. The solution above is made bigger to ease someone who wants to see how it works.

How it works: Split red/blue. If it goes into red zone, that means the last checked one was red, and it's anticipating a green (end marker). It only writes the last checked one if it finds that the next is not green. If it does find a green, that means the last node in the strip was red. Get rid of the green; the first node is back on top. Check the first node. If it's red, then no need to rewrite anything; the last and first nodes are gone anyway, and repeat from the beginning. If they don't match, throw it away. If it's empty at this point, then we're done.

The beauty of this one is that we don't need to check if there's only 1 left; it automatically does so, because it never actually removes the last node, so it just ends up checking itself (and validating, thus clearing the strip).

Nice! I had a similar version but with two separate delay loops instead of a path across the centre (it hadn't occurred to me). I think I've got delays nicely optimized down to a 4x3 block now.

Spoiler:

Still, the most beautiful so far in the thread is Berengal's n*log_5(n) for equal numbers of blue/red.

Edit: this is getting me all inspired to hook out my FPGA board again. If only there wasn't so much boilerplate faff involved.

by **BobTheElder** » Wed May 26, 2010 8:03 pm UTC

Dr. Willpower wrote:
BobTheElder wrote:Well thanks, xkcd, for totally distracting me from my project...

edit: robot planes is destroying my brain.

Not really a comment on the difficulty, I'm a computer programming noob. Just... argh.

Roboplanes or Rocket Planes?

Rocket planes! :p
It's... KIND of almost there... I just can't think any more.
Actually I fail utterly, but yeah.

Also, can someone tell me why

Spoiler:

works for soldiers? I'm sure it's obvious but like I said, I can't think any more. I need to go do some coding while my brain can complete simple tasks.

It's kinda disturbing that I don't really understand most of my solutions for this game.

I did a piece of maths coursework like that once =D

by **evilbeanfiend** » Wed May 26, 2010 8:34 pm UTC

BobTheElder wrote:Also, can someone tell me why
Spoiler:
adding 3 reds

works for soldiers? I'm sure it's obvious but like I said, I can't think any more.

Spoiler:

by **BobTheElder** » Wed May 26, 2010 9:32 pm UTC

evilbeanfiend wrote:
BobTheElder wrote:Also, can someone tell me why
Spoiler:
adding 3 reds

works for soldiers? I'm sure it's obvious but like I said, I can't think any more.

Spoiler:
left shift is the same as multiplying by the base, so by 2 for binary, adding 3 reds is 3 left shifts 2^3 = 8

yey! sense and simplicity!
(or possibly sence and simplisity)
my brain feels slightly happier now...

by **PleasingFungus** » Wed May 26, 2010 9:34 pm UTC

Hello! This is the creator of the game, saying hello. I was very surprised when I popped into the Coding forum (to find something to read while I waited for an assignment to compile) only to find this thread staring me in the face!

Anyway, just thought I'd say a few things:

The version on JayIsGames (the one linked to at the top of the thread) is slightly obsolete. I've been updating constantly (pretty much an update every day, I think!) to the versions that I control: the Kongregate version and the one on my website. Nothing too major, but there are bugfixes and UI improvements and that sort of a thing. (Plus, I get a penny or two if you play the Kongregate version, so you'd be Supporting the Developer!)
I take suggestions via Formspring and on the official feedback thread, so if there's anything you'd like to see added or changed, anything that you found particularly confusing that you think I should clarify, that kind of a thing, just let me know! I tend to be pretty responsive.
I've got a brand new mailing list set up for news about new releases and that kind of a thing (for major updates and/or games after Manufactoria), or, if you prefer to be completely deluged with up-to-the-minute development news, I've also got a devblog which you can follow or subscribe or whatever suits your fancy.
Steax, I hate to tell you, but pretty much half the people who've played Manufactoria beat Robo-Children in that way. (There are at least half a dozen examples on the aforementioned feedback thread.) The funny thing is that you can actually make a 'valid' version of it - the tape can hold at most fifty symbols, so if you make a version that can handle 25 symbols in either direction (entirely possible), you can make an unbeatable version of the level. It's very silly, but there you go.

Anyway, hopefully this has been useful/interesting, and hopefully I won't get filtered as spam for posting fifty links!

Nicholas Feinberg,
"Pleasing Fungus Games"

EDIT: completed incomplete parenthetical

by **jaap** » Wed May 26, 2010 9:35 pm UTC

TNorthover wrote:Nice! I had a similar version but with two separate delay loops instead of a path across the centre (it hadn't occurred to me). I think I've got delays nicely optimized down to a 4x3 block now.
Spoiler:
?lvl=24&code=p12:3f3;y12:2f3;r7:8f2;p7:9f0;r7:10f1;i8:8f7;c8:9f0;c8:10f1;c9:8f3;c9:9f2;c9:10f0;b10:8f3;p10:9f6;b10:10f0;p9:4f7;c9:6f3;c9:7f3;c9:5f2;i11:5f3;c12:4f3;c12:5f3;c12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c8:4f3;c8:5f3;c8:6f3;c8:7f3;i11:3f2;c10:3f0;c9:3f3;c11:8f1;c11:7f1;c11:6f1;c11:4f1;c11:2f2;c13:8f1;c13:7f1;c13:6f1;i13:5f0;c13:4f1;i13:3f4;c13:2f0;c14:3f2;c15:3f3;c15:5f0;i14:5f6;c14:4f3;c14:6f2;c15:6f3;c15:7f3;c16:4f3;c16:5f3;c16:6f3;c16:7f3;q11:9f6;q13:9f0;r14:8f2;p14:9f0;r14:10f1;i15:8f7;c15:9f0;c15:10f1;c16:8f3;c16:9f2;c16:10f0;b17:8f3;p17:9f6;b17:10f0;p15:4f7;c10:5f2;

Here's my much smaller solution to Engineers:

Spoiler:

I've been going over all the levels I've done, trying to improve them.
I'm kind of stuck on the levels Judiciary and Ophanim. It just does not seem possible to do it within that small a space.

by **Laguana** » Wed May 26, 2010 10:14 pm UTC

jaap wrote:I'm kind of stuck on the levels Judiciary and Ophanim. It just does not seem possible to do it within that small a space.

I ended up sacrificing any hope of efficiency for cramming it all in there on Ophanim:

Spoiler:

by **phlip** » Wed May 26, 2010 10:40 pm UTC

PleasingFungus wrote:(Plus, I get a penny or two if you play the Kongregate version, and

And... what? I get a penny or two if you play the Kongregate version, and I'll share it with all of you? I get a penny or two if you play the Kongregate version, and here's your own spaceship?

Also: holy crap is that a lot of links for a second post. But I think I'll allow it in this case.

by **PleasingFungus** » Thu May 27, 2010 12:03 am UTC

phlip wrote:
PleasingFungus wrote:(Plus, I get a penny or two if you play the Kongregate version, and

And... what? I get a penny or two if you play the Kongregate version, and I'll share it with all of you? I get a penny or two if you play the Kongregate version, and here's your own spaceship?

Nope! You get a penny and a spaceship and a UNICORN.

Slightly more seriously: I'm sorry if it sounded crass. I was just trying to point out reasons why people might want to play the versions that I'm actively maintaining, and supporting the developer - not even paying me! Just giving me a single ad impression! - seemed like a reasonable motivation. If you feel it was inappropriate, I can edit it out of the original post.

EDIT: Oh! I really thought I'd finished that sentence. Um. I guess I deserved that mocking, then.

phlip wrote:Also: holy crap is that a lot of links for a second post. But I think I'll allow it in this case.

Thank you! I appreciate it.

(P.S.: The unicorn is made of solid silver.)

by **Briareos** » Thu May 27, 2010 12:42 am UTC

0:53 and 21 parts for Teachers:

Spoiler:

by **walkerm930** » Thu May 27, 2010 1:09 am UTC

i made a really complex solution for Androids. it passes all the tests but has 55 parts and 36 are conveyors! Also, the last RndTest took 3:18

Spoiler:

by **joshz** » Thu May 27, 2010 1:14 am UTC

I just got a 7-line test case. :shock:

by **joshz** » Thu May 27, 2010 1:28 am UTC

I'm not really sure how to implement carrying for Officers (adding 1 to a binary string).

by **Lothar** » Thu May 27, 2010 1:41 am UTC

joshz wrote:I'm not really sure how to implement carrying for Officers (adding 1 to a binary string).

Hint:

Spoiler:

Hint 2:

Spoiler:

Solution:

Spoiler:

My Solution:

Spoiler:

by **phlip** » Thu May 27, 2010 1:45 am UTC

joshz wrote:I'm not really sure how to implement carrying for Officers (adding 1 to a binary string).

The way I did it was:

Spoiler:

by **Steax** » Thu May 27, 2010 1:47 am UTC

PleasingFungus wrote:Steax, I hate to tell you, but pretty much half the people who've played Manufactoria beat Robo-Children in that way. (There are at least half a dozen examples on the aforementioned feedback thread.) The funny thing is that you can actually make a 'valid' version of it - the tape can hold at most fifty symbols, so if you make a version that can handle 25 symbols in either direction (entirely possible), you can make an unbeatable version of the level. It's very silly, but there you go.

Wow, do you have more statistics like this? It would be interesting to know, for example, how many people built sort functions, or how many people used which approach to count reds and blues?

Is it possible to move the save cookie to the other site?

TNorthover wrote:Nice! I had a similar version but with two separate delay loops instead of a path across the centre (it hadn't occurred to me). I think I've got delays nicely optimized down to a 4x3 block now.
Spoiler:
?lvl=24&code=p12:3f3;y12:2f3;r7:8f2;p7:9f0;r7:10f1;i8:8f7;c8:9f0;c8:10f1;c9:8f3;c9:9f2;c9:10f0;b10:8f3;p10:9f6;b10:10f0;p9:4f7;c9:6f3;c9:7f3;c9:5f2;i11:5f3;c12:4f3;c12:5f3;c12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c8:4f3;c8:5f3;c8:6f3;c8:7f3;i11:3f2;c10:3f0;c9:3f3;c11:8f1;c11:7f1;c11:6f1;c11:4f1;c11:2f2;c13:8f1;c13:7f1;c13:6f1;i13:5f0;c13:4f1;i13:3f4;c13:2f0;c14:3f2;c15:3f3;c15:5f0;i14:5f6;c14:4f3;c14:6f2;c15:6f3;c15:7f3;c16:4f3;c16:5f3;c16:6f3;c16:7f3;q11:9f6;q13:9f0;r14:8f2;p14:9f0;r14:10f1;i15:8f7;c15:9f0;c15:10f1;c16:8f3;c16:9f2;c16:10f0;b17:8f3;p17:9f6;b17:10f0;p15:4f7;c10:5f2;

Still, the most beautiful so far in the thread is Berengal's n*log_5(n) for equal numbers of blue/red.

Edit: this is getting me all inspired to hook out my FPGA board again. If only there wasn't so much boilerplate faff involved.

Interesting, I wonder if we can find a way to get bridges between the last-red/last-blue states so they don't eat up half the board, they really use up space...

by **joshz** » Thu May 27, 2010 1:48 am UTC

How do you tell what the last in a string is? Because I need to

Spoiler:

by **Vault** » Thu May 27, 2010 2:13 am UTC

Steax wrote:Is it possible to move the save cookie to the other site?

I don't think you can move your cookie, but redoing all the old levels on the Kongregate version isn't too hard. I moved my solutions over to it because for whatever reason the version there is a lot easier on my computer. Like, instead of sitting at 67% cpu usage having the tab open, it's at like 22.

by **phlip** » Thu May 27, 2010 2:32 am UTC

You can probably copy the LSO files - I haven't tried with this game, but it works for others. Go to:
For Windows: %APPDATA%\Macromedia\Flash Player\#SharedObjects\<random string>
(For XP and older, APPDATA is usually C:\Documents and Settings\<username>\Application Data... for Vista and newer, it's usually C:\Users\<username>\AppData)
For Linux (and probably for OSX too): ~/.macromedia/Flash_Player/#SharedObjects/<random string>

In there, copy everything in the flash.games.m.fizzlebot.com/manufactoria.swf/ dir into chat.kongregate.com/gamez/0008/0396/live/Manufactoria.swf/. You should probably make backups of the destination, just in case something gets messed up (if the different sites have different values or the version mismatch breaks or something).

Failing that, you can just use the save/load function in the game itself... you have to do each puzzle one at a time, but it would work.

by **Steax** » Thu May 27, 2010 2:36 am UTC

joshz wrote:How do you tell what the last in a string is? Because I need to
Spoiler:
replace just the last with B if R and R if B.

If you need en example, open the spoiler:

Spoiler:

by **Nix** » Thu May 27, 2010 2:42 am UTC

After solving the game and optimizing most of my solutions I really wanted a way to verify my solutions with a more comprehensive set of inputs, and also get a more representing measure of efficiency than the times given by the game. Keeping score of the best solutions would be a bonus.

So I threw together a quick and dirty C++ program that verifies solutions with all inputs with up to 10 reds+blues (no technical reason not to go even higher, but it will slow down) and saves the overall fastest solution for every part count. It's probably full of bugs from super poor testing. I haven't even nearly covered all branches in my manual testing and there's no test code apart from some simple assertions. It's certainly ugly code too, but since there's plenty of interest in the game here now, I thought I'd share the work in progress. It's also working well enough for me at the moment so I might not get to polishing it very much.

The code is in public domain, feel free to do what you like with it. See if anyone can even make it compile.

PM any patches and I'll include them here. It would be nice to have something like this working on the web, but that's not something I'm willing to tackle myself.

Added help: The normal use is to start the program, then paste in a complete save code copied from the game, followed by enter. When done pasting codes, press ctrl-D for EOF and it'll save the scores (not if you kill it by ctrl-C). New versions will also quit when input "q". An optional single command line argument gives the solver name it uses for saving any new scores. Use -? or some other invalid syntax on the command line to list the command line options.

A typical short session would look like this:

Code: Select all: $./manufactoria-checker Nix ?lvl=1&code=c12:6f3;c12:7f3;c12:8f3; Robotoast! ( 1) 8188 steps total with 2047 inputs ( 4.00 average) with 3 parts matches previous size and speed record $

Next version here. Newest here.

I'm keeping a database of the the best solutions on this thread and ones sent to me along with mine. The results as text and the database file to download are kept updated in a later post. Some of the solutions on this thread have also been disqualified due to my interpretation of the rules, for example I'm allowing the empty string as a binary 0 in the input (and output) and requiring the solutions to handle it as such. Opinions?

Here's a record of previous additions to the list I edited to this message while the list was here:

2010-05-26 Updated records with some new optimizations by me, mostly thanks to re-solving when moving out of JayIsGames. Fixed the program to handle full urls in save strings used by the pleasingfungus.com version as well.

2010-05-27 Worked really hard to improve Lothar's step count in Officers! I think 27 parts is ~~optimal~~, same as Lothar's. It was really hard to achieve in the first place (I didn't look at his solution). Also redid the similar Generals! to reduce from 43 parts to 29.

2010-05-27 Now I looked at Lothar's solution for Officers! Wow, it seems to be a totally different approach and at least is structured different. Funny we reached the same part count. Maybe his approach can even be optimized in size even further?

2010-05-27 Yes it can! Some simplish squeezing without real structural/algorithmic changes resulted in a two part reduction, it's the Lothar/Nix entry.

2010-05-28 JavaBean totally beat jaap's previous record in Engineers! reducing the part count from 33 to 27 which they think must be pretty nearly optimal for size, also killing my speed record of 112600 in 96480 steps with "surely the fastest n² algorithm available". I'll say more when I have looked at their solution after trying to reach 27 myself.

2010-05-28 JavaBean improved more levels for speed: my Robolamp (two sizes), my Robobears, Briareos's Teachers/21, and new Politicians/36. No new part count records.

2010-05-29 Steve496 broke a whole set of records. He has simply faster solutions to replace mine in Robofish and Milidogs. In Politicians he reduced part count record from 35 to 32 but with a slower algorithm. Same with Ophanim: 124 down to 78 parts. In Academics (35 to 31 parts), Rocket planes (24 to 18), and Seraphim (41 to 35), he beat my part count records while also being faster (although in Rocket planes, Berengal's 40 parter is still fastest). Well done!

2010-05-29 Steve496 has a new series. For Robobugs he has a speed-optimized 21 part solution that kills the smaller 13377 step solution by doing it in 8342. Related to this one, he brings up the point that a set of basically identical incrementally smaller solutions can be churned out. He recommends that I only keep one smallest and one fastest solution for each level, and I tend to agree. Are there going to be enough unique middle ground solutions that are neither smallest nor overall fastest but are still interesting? Should just the clearly boring variants be filtered out manually? Opinions?

Steve496 also squeezes one part out of Teachers and reaches 19 in a slightly slower solution. In Politicians he improves his own solution from 32 to 29 parts also improving speed. Same with Ophanim – 78 to 75. In Engineers he cuts out two parts from previous best and comes up with a slower 25 parter.

Dernam (not registered here) has a huge 35 to 23 part drop in Seraphim to beat Steve496, improving speed on the way.

Also included is enne's improvement from my 125 part Metatron to 104 parts, from below in this thread.

2010-05-30 Moved the score list to a new post on the new page. Edit history continues there.

2010-06-01 New version in a later post.

2010-06-10 Added some help for program usage, and link to new version.

by **orangeperson** » Thu May 27, 2010 6:39 pm UTC

You might want to write some better test cases for the comparison one. I just wrote something which chops off leading zeros and compares lengths, and tested that, and it passed everything.

Edit: I just tried the kongregate version, and I got a 404 (just in the game box).

by **Dr. Willpower** » Fri May 28, 2010 5:32 pm UTC

Not a solution, nevermind.

by **darkspork** » Sat May 29, 2010 10:23 am UTC

Damn it. You've created one more thing for me to not sleep over.

by **enne** » Sat May 29, 2010 4:25 pm UTC

Here's a faster and smaller Metatron solution that only uses 104 parts:

Spoiler:

Thanks for the writing the checker, Nix. That's quite nifty.

by **Lothar** » Sun May 30, 2010 2:28 am UTC

That's neat, enne. Your solution gave me some tips I could use on mine, and it came out to 102 parts, and after a bit more optimization, I got it down to only 74 parts!

Spoiler:

It runs a bit slower, since I route 0+1 to the 1+0 case in order to save parts (it saves about 12, I think).

EDIT: Optimized a tiny bit more, but didn't change the part count. :/

by **Ephphatha** » Sun May 30, 2010 4:37 am UTC

I'm not entirely sure what judiciary is actually asking for. Are we meant to accept palindromes? Strings where the middle two elements are the same?

Edit: And now that I look at the test cases, I've worked it out...

by **Lothar** » Sun May 30, 2010 4:47 am UTC

Ephphatha wrote:I'm not entirely sure what judiciary is actually asking for. Are we meant to accept palindromes? Strings where the middle two elements are the same?

Strings that are composed of two identical strings in a row, such as RBBRBB.

Who is online