Editorial for Lyndon's Golf Contest 1 P5 - Basic Triangle

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Dingledooper

47 bytes

We can solve this problem using two for-loops: an outer loop that keeps track of the n^{th} row, and an inner loop that prints the correct number of *s on each row. A solution that implements this idea is given below:


Although it is possible to squeeze a few more bytes out of this solution, a different method is required to achieve a better score. Instead of outputting character-by-character, let's consider a line-oriented approach, where we initialize a char array and incrementally append *s to the end of it, using puts() to output its state every iteration. We can get down to 49 bytes with this approach:

char s[15];i;main(){for(;i<15;puts(s))s[i++]=42;}

A further 2 bytes can be saved by executing an advanced technique known as Delete Random Characters And Hope The Compiler Doesn't Segfault. If you try removing the 15 from the array declaration, you'll find (most likely) that the code still ACs:

char s[];i;main(){for(;i<15;puts(s))s[i++]=42;}

An empty [] tells the compiler to set the array's size to 1, by default. The reason a segmentation fault does not occur has to do with the way C distributes memory. More specifically, s contains enough "free" memory after it to allow us to modify their contents.

45 bytes

In order to go lower, we'll need a slight change of approach. Rather than manually updating our array, let's try to use memset(). According to the man page:

  • The memset() function fills the first n bytes of the memory area pointed to by s with the constant byte c.
  • The memset() function returns a pointer to the memory area s.

The fact that it returns the pointer is especially useful, as it allows us to embed it directly inside the puts statement when printing each line. Along with the empty [] trick from earlier, we can achieve a 52-byte solution:

char s[];main(n){for(;n<16;)puts(memset(s,42,n++));}

Note that here, we declare n as an argument to main. The first argument to main holds ARGC, so n is automatically initialized to 1 instead of 0, saving a byte. Recall that s is basically an array of size 1, and in theory, it is only being used by memset() to supply a memory address that we can fill to. In fact, we can just replace char s[] with an implicitly declared integer, and pass its address to memset():


Now we are down to 46 bytes! For the last byte, notice that puts returns the number of bytes written. This allows us to use its return value in place of n in the for-loop condition to obtain our full solution:


41 bytes [*]

Although not necessary to score full points, a 41-byte solution was found during the contest by lynn:


Instead of using memset to output n *s on each line, we can use strcat to incrementally append a * to some memory address. Like with the intended 45-byte solution, it uses the address of a global "dummy" variable instead of an array, which works for the same reason.

Another worthy mention that was achieved in-contest is the 45-byte solution by Garklein and kotatsugame, which essentially adds pointer abuse to the given 47-byte solution:



There are no comments at the moment.