2022 Holiday Coding Challenge

8 minute read

Published:

One of the programming groups I’m in recently posted a challenge for the holiday season. The task is to print the following ASCII art using whatever language you like:

        *      *    
        **    **    
        ***  ***    
        ********    
    ****************
     ************** 
      ************  
        ********    
       **********   
      ************  
     ************** 
    ****************
        ********    
        ***  ***    
        **    **    
        *      *  

It’s a big star comprised of a 9x9 square with eight right triangles, each of which are 4x4 units high/wide. The challenge is to see how minimal a program you can create to generate the image.

I decided on C, since it’s one of the three languages I’m most comfortable with (the other being R and Python). C seemed the most in the “spirit” of the challenge, since the challenge was originally posted on the retrocomputing forum (original forum post here). Python and R require quite a bit of overhead as far as interpreters, but C can be compiled directly into assembly.

First Thoughts / Intuition

Usually with problems like these, I either start with a quick and rough solution and then refine it, or spend a lot of time up front trying to come up with an efficient solution. I opted for the second approach for this problem.

The star fills a 17x17 block in all, which is almost a nice size for programming. If only the center block was 8x8, it would be a 16x16 block that fits nicely into 16-bit integers. My first approach was to think through the problem as if it was an 8x8 square in the center.

In this case, we essentially have a 16x16 matrix. Since we only have two possible characters, we can just use binary vectors for each row. A memory efficient solution for this is to make a length 16 array of 16-bit unsigned integers, then bitshift thorugh each in order.

This approach works fine, but there’s a lot of wasted space since the design has so much symmetry. I decided it would be better to just store the upper quadrant of the star, then figure out how to print the rest with math.

The upper quadrant of the star is the 8x8 section at the top left, corresponding to this:

    *   
    **  
    *** 
    ****
********
 *******
  ******
   *****

8x8 is an especially nice size, because it’s a total of 64 binary values. This fits perfectly into a single unsigned long! If we set unsigned long bitmap = 0xF8FCFEFFF0703010, then every byte corresponds to one row (10 = 00010000, bitshifting through and printing prints in reverse, which corresponds to 0 0 0 0 1 0 0 0). To print the whole row, we print the byte forward and reverse. To add in the middle row/column in the 17x17 version, we just print a character before we print the byte in reverse.

Optimizing the Initial Solution

This solution can work, but we can do better. One of the largest problems is that unsigned long takes a bunch of characters to write out, and there’s still quite a bit of redundancy in the bitmap. Notice that all the lower bits have 0 as the lower nibble, and all upper bits have F as the upper nibble. If we just store the non 0/F part of the byte, we can store the whole thing as a single 32-bit integer: 0x8CEFF741. For each value, we expand it to a 9-bit integer corresponding to that row (the 9th bit representing the center value).

As an example for the third row, we have the value 0x7. The expansion proceeds like this (printed characters in parentheses, _ corresponds to space):

     0x7  =  0111             ( * * * _ )
=>  0x70  =  01110000         ( _ _ _ _ * * * _ )
=> 0x070  = 001110000         ( _ _ _ _ * * * _ )
=> print forward and reverse:   _ _ _ _ * * * _ * * * _ _ _ _ 

If we do this for each line, we’ll have the first 8 lines of the star. We just need to print a single line of 9 stars, then repeat the process in reverse, and that’ll print the entire star.

The complete code looks like this:

#include <stdio.h>
int m=0x8CEFF731; // 32 bit bitmap, each nibble is a line of the top 8x8 corner
                  // high 4 bytes have to be OR'd with 0xF0 to produce the right number
                  // decompressed bitmap looks like this:
                  // 01 03 07 0F
                  // FF EF CF 8F
                  //
                  // Each entry is a half line, so to print the top half we print and mirror
                  // 01 10
                  // 03 30 
                  // 07 70
                  // 0F F0 
                  // ...etc 
                  
char s[]=" *";    // this is the string we print from

// f is a quick function to decompress a nibble, 
// then print forward and backwards
// it takes in a value b so that I can cleanly print the center value
void f(int i, int b){
    int j=-1;
    int v=b>>i; // get just the nibble
    v=i>15?0xF0|v:v<<4; // if it's a high byte, OR it with 0xF0
    v=(v&0xFF)|(i>15)<<8; // set middle value
    // print 
    for(;j++<16;)
        putchar(s[v>>(j>8?16-j:j)&1]);
    putchar('\n');
}
int main(){
    int i=-1;
    // print both halves
    for(;i++<15;)
        f((i<7 ? i : 15-i)*4, i!=7 ? m : 0);
}

Link to run it yourself: https://onlinegdb.com/GDbOeKoxx.

Making it small

Now that we have working code, how small can we make it? I’m borrowing a lot of tricks from the Ray Tracing Business Card, which incorporates a lot of fun techniques. We can start by saving a lot of characters by calline #define putchar p, which saves us 6 characters every time we call putchar(). Additionally, we can change the type of f() to int, which doesn’t do anything but saves us a character. All the hexadecimal values can be converted to decimal except for m to save us a few characters. Lastly, we can do some refactoring to reduce variable declaration. We’ll also remove the comments and spaces.

#include <stdio.h>
int m=0x8CEFF731; 
int f(int i,int b){
    int j=-1;
    int v=(i>15?240|b>>i:b>>i<<4&255)|(i>15)<<8;
    for(;j++<16;)putchar(" *"[v>>(j>8?16-j:j)&1]);
    putchar('\n');
}
int main(){
    int i=-1;
    for(;i++<15;)f((i<7?i:15-i)*4, i!=7?m:0);
}

Finally, we can remove all the newlines to make one mess of a single line script. We can also remove the #include statement–it causes a warning but it does successfully compile. Not great practice for production programming, but helpful for here!

int m=0x8CEFF731;int f(int i,int b){int j=-1;int v=
(i>15?240|b>>i:b>>i<<4&255)|(i>15)<<8;for(;j++<16;)
putchar(" *"[v>>(j>8?16-j:j)&1]);putchar('\n');}int 
main(){int i=-1;for(;i++<15;)f((i<7?i:15-i)*4,i!=7?m:0);}

I’ve added newlines in here to make it look better on the screen, but it works as a single line too! Final count is just 212 characters.

Making it Smaller

We still have quite a few extra lines in here due to the extra function call. Could we make it smaller?

We can start by moving some functions into the for loop of the code. For example, instead of calling putchar('\n') at the end of each iteration, we can just use for(; i++<15; puts("")) to achieve the same effect. Similarly, we can define v within the j loop, then explicitly calculate any changes to it in the putchar call itself. The result is somehow less readable, but it’s shorter code overall.

#include <stdio.h>
int m=0x8CEFF731;
char s[]=" *";   

int main(){
    int i=-1,j,v,k;
    for(;i++<16;putchar('\n')){
        for(j=-1, v=(i!=8)*m>>((i<8?i:16-i)*4), k=i>3&i<13; j++<16;){
            putchar(s[((k?0xF0|v:v<<4)&255|k<<8) >> (j>8?16-j:j)&1]);
        }
    }
}

You’ll notice that I defined and additional variable k to indicate when i is in the range where we should print a star in the center. This ends up saving a couple characters overall. We also only use m once now, so we can remove it and just use the value explicitly in the single place it appears.

We can then remove all the brackets, spaces, and newlines to get a final character count of just 173 characters.

int main(){int i=-1,j,v,k;for(;i++<16;puts(""))for(j=-1,
v=(i!=8)*0x8CEFF731>>((i<8?i:16-i)*4),k=i>3&i<13;j++<16;)
putchar(" *"[((k?240|v:v<<4)&255|k<<8)>>(j>8?16-j:j)&1]);}

You can try it yourself here!

There are definitely better solutions out there (someone posted a C solution of just 143 characters), but I think this solution is good enough for me.