The Hidden Blade Assassin's Creed in Depth

My programming contest is over for now. Round 3 of 3 closed this week. Now we have to wait for the judges to score rounds 2 and 3 to see if I will win the Grand Prize - a trip to San Francisco.

Round 3 was definitely my strongest. I expect my program to dominate the competition on any test the judges throw at it. Some of my competitors published their execution times on a set of benchmark tests we were all using. Here's how my program stacks up against theirs (all times in milliseconds, lower numbers are better):

Note how the other programs get progressively slower as the problem size grows. That's called linear or O(n) running time. My program solves any problem in 15 milliseconds or less. The 574395734 test is a near worst-case scenario for it.

Now I will go into some detail about the problem statement and my solution. This will get technical but at least there are pretty pictures...

The problem is called Running Numbers because it acts like a crazy odometer. Given three 128 bit input values (in hexadecimal):

Create an accumulator that starts with value Source. On the first cycle (cycle number zero), add DWORD adder to the accumulator. For this addition treat both the accumulator and the adder as four independent 32-bit words. If the result of any addition exceeds the 32-bit capacity it simply "rolls over", discarding the carry:

For the second cycle (number 1), add BYTE adder to the accumulator. This time the accumulator and adder will be treated as 16 individual bytes, each rolling over without carry:

Continue doing BYTE additions for 35 more cycles. On the 37th cycle (cycle number 36), the whole process starts over with a DWORD addition. In other words, do a DWORD addition whenever the cycle number is evenly divisible by 37. Otherwise, do a BYTE addition. Run this simulation until a cycle ends with all bytes equal to zero or all bytes equal Source (their original values). When that happens, print the number of cycles completed and exit.

Here's pseudocode for the simulation:

    a = Source
    cycle = 0
    do
        if cycle % 37 == 0
            a = a + DWORD adder
        else
            a = a + BYTE adder
        cycle = cycle + 1
    while a != 0 AND a != Source
    print cycle

So there's my winning solution. I think it's elegant in its simplicity. Just kidding!

When I read the problem description, it screamed "Streaming SIMD Extentions" (SSE):
Q. 128 bit integer registers?
A. SSE2
Q. Add as four DWORDS?
A. PADDD (_mm_add_epi32 intrinsic)
Q. Add as sixteen BYTES?
A. PADDB (_mm_add_epi8 intrinsic)

Meanwhile, the 37 cycle pattern whispered, "You have 40 cores. Use 37 threads to decompose it." Yet SSE and threading will only go so far when your basic algorithm is "grind it out". In order to go really fast one needs to optimize the algorithm.

I named my algorithm barrel lock because it's analogous to opening a 4 dial lock when you already know the combination.

Partition the 128 bit accumulator into four logical dials as indicated by the four colors in this diagram:

Each dial consists of 4 non-contiguous bytes. The red dial is made up of the least significant byte of each DWORD while the yellow dial is the set of most significant bytes. A dial is not considered solved until all four bytes reach their target values.

The algorithm works in four phases from right to left. The first phase gets the red dial into position. The second phase works on the green dial without moving the red dial, and so on.

For example consider a test where:

Source = d6b610c012e049601632f70094c145c0
BYTE adder = 1bbffa833f0e0f733ca510f5044ef24a
DWORD adder = 39499f0b48e0f3ec3cca214b7a1e0474

The solution proceeds as follows:

That should give you a flavor for how I solved this problem. For complete details, see the write up I did on the contest forums.

TLDR: Stabguy is a genius and deserves a vacation

agreed

And a clever solution once again. I really like your threading setup as well. Not that I've got much experience in the field...

All those school years working on art projects...wasted. I don't know what the hell is going on in this topic anymore.

Don't worry, Joey, I wouldn't be able to draw if my life depended on it.

Speaking of that, my girlfriend e-mailed me about a scholarship for comic book fans. I just need to submit a portfolio and actually know a good amount of graphic novel lore. I got this...

Joey, why didn't you take my advice? You should dump your girlfriend. It will save you a lot of money! And time! And time is money! So you're actually saving money^2! And since money is the root of all evil, you're saving (squareroot(evil))^2, which is the same as evil!
So by dumping your girlfriend, you not only save time and money, you're sparing yourself a lot of evil as well!

I. AM. A. GENIUS!!!111!!!!11!!!

Holy f*ck, that makes sense!

That makes so much sense it scares me

If saving money = having more money for yourself...

...then...

...saving evil = having more evil for yourself...

...hence...

evil is conserved and spread

My girlfriend is a member on here, by the way.

NAPPA: vageta how much sense dose this make?

VAGETA: TOOOO MUUUUCH!!!!

WHAAAAAT !!

Aww yeah

Actually, it doesn't make sense, but whatever.

If it's the girl I'm thinking of, I had been wondering whether she was your girlfriend or a relative of yours (cousin or something).

Okay, you all really want to know? It's FLAE. There. It's out.

I thought it was JosieFogey or something like that.

Ha. That's actually hilarious.

I actually chuckled.

Decided to check out this topic.... so that's what happened to 18. He must have "account suicided", im surprised he didn't just post porn everywhere. One time I was bored on gamefaqs I posted pain olympics on some board... was worth it.

He was taken back to Abstergo.

Who thinks an Assassin smiley would be awesome for posts? Just the bottom (chin?) of a yellow circle with a white hood and a small line indicating a mouth. I think Ezio's wider hood with the loops at the neck would be better. Thoughts?

nice idea !!!

Where is the topic about writing Ian's bio for the "About" section? It's been stuck on one type since the last post. I've been having trouble finding it and the new "staff" post stab just put up reminded me of that.

Say what? I don't think there's a special topic for Ian's bio suggestions. Just post it here or wherever. And I didn't post anything new about "staff". Ian recently updated the About page to reflect piano wire in his pocket, presumably inspired by what you said here, Joey. That's why the page got bumped in the Recent Posts list.

Huh. I swear we made a topic about ian's bio. Or it could just be random posts. My mistake.

http://www.youtube.com/watch?v=LrhahoGqe-s&feature=related

Back after a week of vacation with no internet connection. How I've missed you all.

You were missing? I hardly noticed.

Ha. And I missed you too.

I noticed, and I missed you too GB. Welcome back!

Well thank you Lisa.

Just read the last twenty posts... interesting choice of a partner, Joey...

Well they wouldn't stop bugging me about our partnership. I had to tell them.

I win! no replies for 2 days! And i just beat myself. ;D

...wait...

That's not right, is it?

No. No it isn't...

Yeah, I thought so.

----WARNING----
From this point on, you're entering a smiley free zone!

NO. MORE. F***ING. SMILEYS!

It's more fun if you plan with somebody else.

I'm on board with this.

Base Phi reporting to Unit Gamma. We have a breach in Indianapolis, IN. Please proceed to immediate elimination.

Roger that Phi. Proceed.

Wait, now I'm confused. Are you going to eliminate him, or am I going to do it? You're the unit, so you'll have to do it!

You may fire when ready.