Generation Recursion

Sierpiński Triangle

Boilerplate Code

This is boilerplate code to start with. In the code are prepared some useful structures such as 2D Point, Triangle and Svg. There is method addTriangle, which adds trinagle to SVG image and function to export image to SVG file. Only part to make is recursive function seprin named after Wacław Sierpiński. Recursive function serpin should add trinagles to SVG image. For depth 0 it should do nothing. For depth 1 it should stroke trianle given through parameters. We don't need fillColor, as fillColor pass there TransparentColor glabal constant. Since only strokeColor is relevant to this task.

/* PA1 - Seprinsky Triangle Boilerplate
 * Created by Tomas Dejmek, 8.11. 2021, dejmeto1@fit.cvut.cz
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "libs/svgimage.h"

void serpin(SVG_Point p1, SVG_Point p2, SVG_Point p3, char * strokeColor, int depth, SVG_Image * svg) {
    // TODO: Implementation
}

int main (int argc, const char *argv[]) {
    int sideSize = 800;
    int depth = 4;
    char filename[257] = "image.svg";
    // char color[16] = "black";
    char strokeColor[64] = "black";
    for (int i = 1; i < argc; i ++) {
        if (strcmp("--size", argv[i]) == 0) {
            if (++i >= argc) break;
            sscanf(argv[i], "%d", &sideSize);
        } 
        else if (strcmp("--depth", argv[i]) == 0) {
            if (++i >= argc) break;
            sscanf(argv[i], "%d", &depth);
        }
        else if (strcmp("--output", argv[i]) == 0) {
            if (++i >= argc) break;
            sscanf(argv[i], "%255s", filename);
        }
        else if (strcmp("--stroke", argv[i]) == 0) {
            if (++i >= argc) break;
            sscanf(argv[i], "%63s", strokeColor);
        }
    }

    SVG_Image svg;
    SVG_Init(&svg, sideSize, sideSize*sqrt(3)/2);
    SVG_Point p1 = {svg.width/2,          0}, 
              p2 = {          0, svg.height},
              p3 = {  svg.width, svg.height};
    serpin(p1, p2, p3, strokeColor, depth, &svg);

    int success = SVG_ToFile(&svg, filename);
    
    SVG_Release(&svg);

    if (!success) {
        return 1;
    }
    return 0;
}

Running

We can run it without parameters. All parameters have fallback values. It creates image.svg by default.

./a.out

Pictures above have been generated by this bash script.

for depth in {1..6}; do
    echo "$depth"
   ./a.out --depth "$depth" --output "serpin-${depth}.svg" --size 1080 --stroke \#3275a8;
done

Solution

reveal solution

void serpin(SVG_Point p1, SVG_Point p2, SVG_Point p3, char * strokeColor, int depth, SVG_Image * svg) {
    if (depth <= 0) return;
    SVG_AddTriangle(svg, p1, p2, p3, TransparentColor, strokeColor);
    SVG_Point p12 = {(p1.x+p2.x)/2, (p1.y+p2.y)/2};
    SVG_Point p13 = {(p1.x+p3.x)/2, (p1.y+p3.y)/2};
    SVG_Point p23 = {(p2.x+p3.x)/2, (p2.y+p3.y)/2};
    
    serpin(p1, p12, p13, strokeColor, depth-1, svg);
    serpin(p12, p2, p23, strokeColor, depth-1, svg);
    serpin(p13, p23, p3, strokeColor, depth-1, svg);
}

Generate All Binary Numbers of Lenght N

• Use string and recursion to generate all numbers.

$ ./a.out 
Input number between 1 and 20
3
000
001
010
011
100
101
110
111

show hint (boilerplate)

#include <iostream>
#define MAX 20

void listBinaryNumbers(char * buffer, int idx, int size) {
    // TODO
}


int main () {
    char buffer[MAX+5]; // allocated a little more, so we have always room to put string ending.
    int n = 5;
    printf("Input number between 1 and %d\n", MAX);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX) {
        printf("Invalid input.\n");
        return 1;
    }
    listBinaryNumbers(buffer, 0, n);    
    return 0;
}

reveal solution

void listBinaryNumbers(char * buffer, int idx, int size) {
    if (idx >= size) {
        buffer[size] = '\0'; // ensure string is ended right, then it is safe to use %s.
        printf("%s\n", buffer);
        return;
    }

    // We need two recursive calls here. Firstly we put zero on index then we put one;
    buffer[idx] = '0';
    listBinaryNumbers(buffer, idx+1, size);
    buffer[idx] = '1';
    listBinaryNumbers(buffer, idx+1, size);
}

• Second Variant (V2). Result does not include 3 consecutive ones.

$ ./a.out 
Input number between 1 and 20
3
000
001
010
011
100
101
110

reveal solution

// Lets count how many consecutive ones we have.
void listBinaryNumbersV2(char * buffer, int idx, int size, int numberOfConsecutiveOnes) {
    if (idx >= size) {
        buffer[size] = '\0';
        printf("%s\n", buffer);
        return;
    }

    // When we put 0, we reset counter of consecutives ones.
    buffer[idx] = '0';
    listBinaryNumbersV2(buffer, idx+1, size, 0);
    // We can prevent here that three are not possible.
    buffer[idx] = '1';
    if (numberOfConsecutiveOnes < 2) {
        // We put 1, we have to increase counter by one.
        listBinaryNumbersV2(buffer, idx+1, size, numberOfConsecutiveOnes + 1);
    }
}