Size contest

[Sfel]

I recently stumbled across this problem: https://www.spoj.pl/problems/SUMITR/ and had a fun-yet-frustrating time solving it in C/C++ on the gcc compiler. I got my code to 253 bytes when all whitespace is removed.

The code I'm attaching doesn't have all whitespace removed for clarity purposes (the code gets accepted, so don't download if you don't want to be spoiled). I'm really curious if someone can come up with less hackish approaches or more hackish ones that can reduce the size even further.

One problem is that you cannot read the contents of a test case using cin, because cin is slower than scanf on that site, so you have to use scanf, which requires a few extra characters.

So basically, the contest is to get that problem accepted using C/C++ and their gcc compiler. Let's see who can do it using the fewest bytes!

For clarity, I suggest you attach your code with whitespace and indentation.

[abachler]

The problem needs more explanation as there are at least 3 mutually exclusive ways of interpretting what sum is wanted.

[Sfel]

I'll try.

You're given a triangle of numbers, let's take the second example:
1
1 2
4 1 2
2 3 1 1

You start from the first element of the first row (1). You can go to the element below it (1) or to the element below it and one step to the right (2). From these, you can do the same thing. Out of all possible such paths, choose the one with the sum of elements maximised. Output that sum.

For the example, the path would be made up of the numbers 1 1 4 3, resulting in a sum of 1+1+4+3=9.

[abachler]

Oh that's simple, now define the array in which the numbers are held. Then just find the largest element in each row.

[laserlight]

Originally Posted by abachler

Oh that's simple, now define the array in which the numbers are held. Then just find the largest element in each row.

The rules on how to traverse the path means that that will not work for all cases since it may come up with an invalid path.

[Sfel]

Yes. For example:
7
1 4
5 2 3

You would select 7 + 4 + 5 = 16, but this is invalid.
The correct paths are: 7 1 5, 7 1 2, 7 4 2, 7 4 3, with the max being 7 + 4 + 3 = 14

To find out if your solution is good you can solve this first https://www.spoj.pl/problems/SUMTRIAN/ and reduce the file size after.

[EVOEx]

Here's my try. I registered and it got accepted. 191 characters in total, but I bet there are better ways than this.

Warning: this contains a spoiler. That's why I changed the text color to the background color. To actually view it, select it.

I challenge everyone to do a better job .

#define Z(a)scanf("%d",&a);
int r,b[101],i,j,m,o,p,z,y;main(){for(Z(r)r--;){for(y=i=!Z(m)i++<m;)for(j=b[i]=o=0;j++<i&&Z(z))b[j]=((p=b[j])>o?b[j]:o)+z,o=p,b[j]>y&&(y=b[j]);printf("%d\n",y);}}
 

*edit*
2 characters less now (so score 189):

#define Z(a)scanf("%d",&a);
int r,b[101],i,j,m,o,p,z,y,x;main(){for(Z(r)r--;){for(y=i=!Z(m)i++<m;)for(j=b[i]=o=0;j++<i&&Z(z))x=b[j]=((p=b[j])>o?b[j]:o)+z,o=p,x>y&&(y=x);printf("%d\n",y);}}
 

*edit*
-4 for 185:

#define Z(a)scanf("%d",&a);
r,b[101],i,j,m,o,p,z,y,x;main(){for(Z(r)r--;){for(y=i=!Z(m)i++<m;)for(j=b[i]=o=0;j++<i&&Z(z))x=b[j]=((p=b[j])>o?b[j]:o)+z,o=p,x>y&&(y=x);printf("%d\n",y);}}
 

I even got it accepted without the "=0" but I'm not sure if that's legal or just luck... So I won't count this -2 :P

[IceDane]

I've done this challenge on project euler before. First off, they have a small triangle in which you can really test all possibilities, but then higher up, there's another version of the same challenge with a 100 line triangle.

Depending on whether or not they use a large triangle for testing purposes, the brute-force method might be feasible. But for a 100 line triangle, there are 2^99 possibilities. That's about 20 billion years to to test all paths even with 10^12 paths checked per second.

There is an easy way to do this. Just takes some time to figure out. Starting at the top and always choosing the path with the highest number will not do.

[Sfel]

EVOEx: ~180 characters is really nice, guess that makes your solution the best so far . Good job.

IceDane: I know the PE problem, but there was no size restriction there. I think the problem is rather trivial without a source size restriction, but with one it becomes rather interesting, since there are both math-related facts you can notice to reduce the size and various programming tricks.

[IceDane]

Originally Posted by Sfel

EVOEx: ~180 characters is really nice, guess that makes your solution the best so far . Good job.

IceDane: I know the PE problem, but there was no size restriction there. I think the problem is rather trivial without a source size restriction, but with one it becomes rather interesting, since there are both math-related facts you can notice to reduce the size and various programming tricks.

I think putting a size restriction on the code removes the interesting part from it, as it only results in code without any whitespace at all and so on. It's pretty much golfing. Someone posting some really different method of doing would be far more interesting, using some probability math or something similar(Just throwing ........ out there).

[EVOEx]

Originally Posted by IceDane

I think putting a size restriction on the code removes the interesting part from it, as it only results in code without any whitespace at all and so on. It's pretty much golfing. Someone posting some really different method of doing would be far more interesting, using some probability math or something similar(Just throwing ........ out there).

Hmmm I don't like size restrictions too much either. I do, however, like golfing (in the programming sense), where the contest is actually to make it as small as possible. Unfortunately, there aren't many of these contests... So I just made it a challenge for myself to see how good I could do here.

[anon]

I had done it on Project Euler too.

Anyway, I got it down to 255 bytes and accepted with a lousy 0.73 seconds but I'm happy.

#include <cstdio>
#define R(x)scanf("%d",&x);
int main(){int a[5000],n,m,k,i,j,p;R(n)while(n--){R(m)k=m*(m+1)/2;for(i=0;i!=k;++i)R(a[i])i=k-m;j=i- --m;while(m){for(p=0;p!=m;++p)a[j+p]+=a[i+p]>a[i+p+1]?a[i+p]:a[i+p+1];i=j;j-=--m;}printf("%d\n",a[0]);}}
 

[EVOEx]

Originally Posted by anon

I had done it on Project Euler too.

Anyway, I got it down to 255 bytes and accepted with a lousy 0.73 seconds but I'm happy.

#include <cstdio>
#define R(x)scanf("%d",&x);
int main(){int a[5000],n,m,k,i,j,p;R(n)while(n--){R(m)k=m*(m+1)/2;for(i=0;i!=k;++i)R(a[i])i=k-m;j=i- --m;while(m){for(p=0;p!=m;++p)a[j+p]+=a[i+p]>a[i+p+1]?a[i+p]:a[i+p+1];i=j;j-=--m;}printf("%d\n",a[0]);}}
 

Some hacks to make it even smaller:
- Drop the include . (-18 chars)
- Drop the "int" before main (-4 chars)
- Move all variable declarations to outside the main function, then you can drop the int there (-4 chars)
- Something I didn't even do in my code: Take on of the variables and remove it, together with the comma. Then, move it inside the parenthesis of main. Eg: main(m). This saves on comma (-1 char)

So with just a few basic hacks, you can manage to save 27 chars .
Also, the space you need for "- --m" can probably be removed by changing the "i=k-m" to "i=k-m--" and changing " --m" to "m".

Just some funny tricks you can ignore if you don't give a damn, though :P
Also, to use these tricks, you MUST compile it with a C compiler. It's NOT valid C++ .

[anon]

I have shortened it by 19 bytes without any tricks by simplifying the processing loop (one non-nested loop with a simple if condition to adjust one of the counters - the other counter just can go from x to y).

These kinds of obfuscation contests are not really my cup of tea, though. So I did manage to squeeze it into the limit, fine.

[Sfel]

I'm not really a big fan of them either, I just thought this was a simple problem and it would be fun to try to squeeze into this limit. Doesn't serve any real purpose but...

Also, it's a shame there aren't more contests here, of any kind. Here, even if you have no idea where to start, you can see what others did and learn from them. On online judge sites or project euler, there is little opportunity to learn things. You're either very good already in which case only a few problems will be of interest or just starting, in which case the learning curve will be really really steep.

Not to mention that all PE problems and online judge problems are targeted more towards mathematics, rather than programming. At least this challenge requires a (little) more in-depth grasp of the language to be able to reduce the size. This section could offer what other sites don't.