A.D.A. Amiga Demoscene Archive

Hey Coders,

As at least some have interest in doing coding compos again I prepared the first competition. So here we go! Compete if you have balls!

**************************************************
AMYCODERS BESTS STRIKE BACK
Coder Compo
**************************************************

Name:    Sum Pyramid calculator
Type:     Riddle solver
Mission: calculate the missing numbers of the sum pyramid
Compos:
         - shortest routine
         - fastest routine (on 060)
Deadline:              20. June 2010, 20:20 h
Send entries to:      scicco/scarab - scicco AT scarab-amiga DOT com and tell in which compo you want to compete, you may hand in 2 solutions: one for the shortes and one for the fastets code compo.

**************************************************
Description of the riddle:

In demand is a pyramid of data fields where each field is the sum of the two numbers directly below.
E.g. this on:
  row1:   9            with 9=4+5
  row2:  4 5           with 4=3+1 and 5=1+4
  row3: 3 1 4

Each value must be greater than 0.

Given information are always:
  1. the head value of the pyramid, which is the value in row1
  2. the number of rows the pyramid has, this may be a
     value between 3 and 64
  3. SOME additional values inside the pyramid:
     it IS clear they are in the last row.
     it IS NOT clear in which columns they are.
     it will NOT be the whole row (or the riddle would be pretty easy ;)

Your job:
Solve the riddle by finding values that fit the rules. There may be different possible solutions. So find your way in doing it fast or/and small.

Check this for an example.

-------------------------------------------------------------------------

Find the coding rules in the readme provided in the download package.

Download the Compo Package which includes the detailed readme and the wrapping source code.

Now go and show us how to code!

Results will be published here after the deadline.

I'm sorry to tell you that I did a fault while typing the template 3. Please change your head value from 1658480 to 16584800 to make it solvable.

Sorry for this. The archive on the server is updated by now. So this is only important for those who already downloaded the Compo Package.

good initiative, I think I'll have a go at this!

wt..
I wouldn't be a bad coder if I wouldn't fail twice.

I just discovered that the zeroed space gots partially unzeroed because I decreased the buffer size for the pyramid without thinking about the copy routine used for testing purpose.

I've updated the compo package. Anyway, if you've downloaded it before, find the line #62 that looks like
move.w #32640-1,d0
and change it to
move.w #2080-1,d0

If you don't need zeroed space you may ignore this bug, it won't destroy your machine.

I hope this was the last fail. Sorry guys.

Nice idea to revive the old compos!

Please don't be demotivated when there is a lack of feedback. To be honest, I feel the problem you chose here may be a bit too abstract for some of us leisure time coders. At least I don't see a clean and beautiful solution right away, apart from a bruteforce approach. Ok, maybe that is just me and this problem can be mapped to some famous algorithm.

Nice compo! Well done Scicco!

Things are not quite what they seem at first glance in this one. It can be quite tricky to ensure that no values in the pyramid become zero when the additions are overflowing all over the place (which is inevitable when the pyramid is large). But it wouldn't be fun if it was easy, right? ;)

I assume there are no restrictions on the running time in the short compo or the size in the fast compo? Don't expect to be able to test my short solution on anything but the simplest cases. :)

Thanks for the feedback!

Azure, the idea was to find a mission which is not typical visual demo code as we (nowadays?) also have coders out there doing non-visual code - I want them do be on the same step as visual coders. The other thing is that I wanted to have the coders to compete not only in "who does it smalles/fastest" concerning pure assembly. Usually a coder has to think about the "How" - and this is another thing I wanted to create a challenge in. And I think this quest is not pre-thought by others that much as a line drawer for instance. And yep, I wanted it to be a quest where you have to think before you code - that's what it is about nowadays :D Anyway, I really hope there are some competing, if not - there will be another compo afterwards and somewhen I'll hit it ;)
About this compo: I tried bruteforce and a self made algorithm. First one was a bit smaller, second one is way faster. And as Blueberry said some things are tricky. But this is pure fun :)

Blueberry, there are no real restrictions, but please don't let the shortest run longer than 1 hour and keep the fastest within 64MB RAM usage ;) But I doubt your code will reach these borders...
Your shortest should solve any pyramid riddle constellation, but if you use the templates you should have most cases there.

Thanks again for your feedback guys and I hope you'll compete - good luck :)

After trying around a bit more I can say that bruteforce != bruteforce. IMHO there are multiple ways how this approach can be coded (e.g. top down, bottom up etc). Even my algorithm could be coded in two different ways, but the smalles one was ~14 bytes larger than my shortest bruteforce. I can hardly say if it is a very small one or more average, this makes it even more exciting and I'm very curious about other solutions. :)

Yeah, one hour in the worst case for a brute force solution is quite optimistic, to say the least...

For my short solution, one hour suffices for templates 1-4. Template 5 will (according to my calculations) take about 66 hours. All these cases are relatively well-behaved for the algorithm I use. I can construct a pyramid of height 5 which would require something like 350 000 times the age of the universe. :)

Thus my question: It is OK that the short version can only be tested on small examples and has to be verified by code inspection? The code is fairly straightforward. Unlike the fast version. ;)

Maybe there should be some kind of run-time limit for the routines? On some benchmark system... perhaps its possible to canfigure UAE such that everyone has the same possibility to measure the run-time.

Another question: are calls to pyramid_test_result allowed from within the solver? That would make some difference for bruteforce approaches...

Blueberry, what the heck did you code there??? :D
Makes sense, to keep the runtime within a range of approx. 1 hour (who will pay my electricity bill? :D)

dalton, sure you can call the code but its size will be added to your routine. All the wrapping code is only for your tests. And remember that it is not optimized ;) So it makes sense you code an optimized and fitting version by your own.

Well, as you said, there is bruteforce, and then there is bruteforce. :)

I think a time limit ruins the purpose of a "shortest" compo. Then it becomes "shortest with reasonable running time", which is something entirely different (that's what we do all the time for size-limited intros).

Of course the code should be testable on some examples. I can include guidelines on how to construct riddles that will run quickly, if you want to test it on large examples. :-p

Well, I must admit that you are right. ;) Then it would be fine to get those example riddles and a short description about. I will test your code then with special pyramids - i can also try to run it on UAE for the extreme pyramids. Ahh...well, don't mind, I think I can do that anyhow. :) Looking forward to your code and I hope its larger than mine :-p

No, it's not just you.
For the moment I doodled around on paper, solving some of the templates.
the "51" I was able to solve with a "magic" algo , the "283" with brute force, the "95" I have no bloody clue.
I don't know if I can manage to submit at least a totally out-of-whack-approach before the deadline.
This is really not my style of maths ... If there's any at all.

Come on, this is not about finding a smart math algorithm for solving this - I doubt there is a famous one (maybe Gauss, haven't tested it yet). This is less maths than you think it is. :) I can easily say that because I did two solutions both without heavy maths.

It's not about "heavy" maths ... it's maths ... that's the point ;)
And then comes the assembler thingie...

*cough*

Third time is a charm - or not.
Sniper just told me that I missed the fact that solving 64 rows will need doubles. And as we only have longs the largest pyramid may have 32 rows. So your code has to solve only pyramids with 3 to 31 rows. Sorry again, guys. My bruteforce worked also with overflows so I didn't recognized it..hehe

As the 5th template has 64 rows, replace it with this one:
template5:
dc.w 30
dc.l 879981839
dc.l 7,1
dc.l 8,3
dc.l 10,1
dc.l 20,1
dc.l 21,3
dc.l 22,2
dc.l 23,1
dc.l 0

So, 12 days left! Looking forward to your code soon. :)

Well, that depends on how you define the sum operation. The compo rules state that every value is the sum of the two values directly below it, and that all values are 32-bit unsigned integers. The supplied test code makes it clear that these sums are 32-bit two's complement additions which can overflow.

Defining it like this makes perfect sense and works with pyramids of any size. This is, as far as I understand it, the way the rules are currently specified, though it might not be what you originally intended. ;)

It would certainly make sense to specify that overflow is not permitted (and for even more fun: use signed instead of unsigned values). But that would be a change to the rules. Perhaps an idea for the next compo? :)

We could take a middle ground where the code only has to work on examples which can be solved without overflow, but the solutions are allowed to overflow if the solver so desires (still, zeros are not allowed). That would be open to people's different interpretations and ways of solving the puzzle.

Thanks for your detailed analyse work, Blueberry ;)

Anyway, the riddle says that any value (apart from the ones in the last row) must be the sum of the values below. This is not specified technically but mathematically. And - examplarily as byte values - 129 + 129 <> 2. So the fail is mainly that no pyramid with more than 32 lines is solvable with long values. The code I supplied is only for testing your own approach - it is not the rule. So the rules are still clear. Decreasing the maximum pyramid size down to 31 lines just make pyramids with the max size solvable using long values.

Ah well, forgive me, this is the first compo I set up - and I learn from it :D The next time I will cross check it more often to avoid things like this.

Yeah, that was sort of what I hinted at in my first post. But I admit it wasn't very clearly formulated. I was reluctant to give away too much information about my strategy. :-p

Anyway, will you allow both interpretations of the rules in the entries handed in? If overflow is not allowed, it seems I will have to rewrite both of my solutions. :(

Yeah, I re-read your post and it's exactly as you said: I do get it now but didn't back then. Damn, Blueberry, I owe you more than just a beer!

Well, I can accept them but then they are not comparable to solutions avoiding overflows as they solve a different job - it's just the test code that returns the same result. If it helps that any value is lower than $7fffffff I'd accept compromise and use only test cases withing this range - even if the rule say unsigned long. But if you calc pyramids like 2=4294967295+3 (hex: $2=$ffffffff+$3) I doubt that this can be a solution for the riddle - even if the testcode returns with ok.

Anyway, as I really look forward to your idea and code I'd say that I split the results in showing shortest/fastest code using overflows and those avoiding them or at least remark the entries that use overflows. Thus your code was not for nothing. However, it would be great to get a non-overflow routine from you anyway :)

Sorry again, I hope you are ok with it.

More challenges - more fun! :-D

The short one turned out to be easy to fix. In the end, the two versions differ only in a single instruction. And in the process of fixing it, I found another two bytes to shave off, making me reach the target I was aiming for. Yay! ;)

The fast one was quite a different story, though. The overflowing version took a shortcut that doesn't exist when overflow is not allowed. The new one ends up in combinatorial explosion in the worst case (I think this is unavoidable, at least with the given memory constraints, but I am looking forward to be proven wrong), but hopefully it solves your test cases quickly.

Expect some code in your inbox soon. :-)

Great! Nice to hear that it ended up that good! :)

Looking forward to your code and I'm sure it'll be excellent ;)

Two days left! Sunday is near...

...I'm sorry but as expected I can't come up with a submission.
Told you before it started that it would be unlikely. I'm just simply not a riddle-guy...

Sad to hear, anyway, the next compo will be a bit different and more "mathless", promise ;)

my algo solves problems 1,2 and 4... not good enough I guess

Attention:

As there are only two competitors who handed in a working solution and there are at least three coders working on solutions but don't have them ready yet, we (the two competitors) decided to extend the deadline till next sunday, the 27th of June.

So to all coders that do have code which is not 100% accurate yet: take the time and finish it to let us all have a good competition! We are looking forward to your code!

/scicco

It seems my code does in fact work on problems 3 and 5. Only it is so slow that I don't know when (and if) a valid solution will be returned. Anyway I submit the code now, hoping that your system is faster than mine =)

/Dalton

Ok, guys, it's time for the results.

First, find the result package including a statement and all entries here:

http://www.scarab-amiga.com/files/codercompo/sumpy ramid_results.zip

As written, this package includes a statement file with detailed text about the results, but find the short overview here:

Shortest (includes RTS):
-----------------------------

1. Place: 68 bytes Scicco
2. Place: 70 bytes Blueberry (two solutions, with and without overflow handling, both have the same size though)
3. Place: 292 bytes Sniper (does not handle overflows, C-code is included, too)
Not competing: 210 bytes Dalton (does not handle overflows, solution worked only for some pyramids so it wasn't able to compete)

Fastest (testes with 999 random pyramids):
-------------------------------------------------- ---

1. Place: 2165 frames Scicco (on average 0.04334 seconds for 1 pyramid)
2. Place: 2166 frames Blueberry (on average 0.04336 seconds for 1 pyramid, the overflow version needed 2168 frames)
3. Place: too many frames Sniper (test stopped after > 5 minutes trying to solve the 1st pyramid)

Now go and get the result package! :)

Thanks to all attendees!

/scicco

PS: most originally code was done by noname ... check the statement :)

I had too less spare time to optimize my entry. I coded most parts of the asm code on sunday between the german vs england football game and 20:00. ^^ Therefor its very slow and I think there is still a bug inside the crossover routine. Because it takes so long ...
May when I have a bit more time I optimize it and we will check the speed ;)
Was a good idea from Blueberry and Scicco with the weighted values maybe I'll combine it. Sorry dalton that you code doesnt solve all pyramids. But good to see that you tried a different solution.

It was a good compo!

Thanks Scicco.