Fillit in C compared with the Rust version

The Game Rules

The Input

The program will take a list of a maximum of twenty-six Tetriminos. This list comprises a four-line Tetriminos; an empty new line separates every Tetriminos.

A Tetriminos description must respect the following rules:

Exactly four lines of four characters followed by newlines
A Tetriminos is a classic Tetris piece composed of four blocks
Each character must be either a # when the tile corresponds to one of the four blocks or a . when the tile is empty
Each block must touch another one with at least one of its edges.

Here are examples of valid Tetriminos:

....  ....  ####  ....  .##.  ....  .#..  ....  ....
..##  ....  ....  ....  ..##  .##.  ###.  ##..  .##.
..#.  ..##  ....  ##..  ....  ##..  ....  #...  ..#.
..#.  ..##  ....  ##..  ....  ....  ....  #...  ..#.

Here are examples of invalid Tetriminos:

####  ...#  ##...  #.  ....  ..##  ####  ,,,,  .HH.
...#  ..#.  ##...  ##  ....  ....  ####  ####  HH..
....  .#..  ....   #.  ....  ....  ####  ,,,,  ....
....  #...  ....       ....  ##..  ####  ,,,,  ....

As each Tetriminos occupies only four of the sixteen available squares, it's possible to describe the same Tetriminos in several ways. However, the rotation of a Tetriminos describes a different Tetriminos from the original for this game. This means no rotation is possible on a Tetriminos when arranging it with the other Tetriminos.

Those four Tetriminos are, therefore, completely distinct:

##..  .###  ....  ....  ....
#...  ...#  ...#  ....  .##.
#...  ....  ...#  #...  .##.
....  ....  ..##  ###.  ....

Find the Smallest Square

This game aims to arrange the Tetriminos to form the smallest possible square. Tetriminos are placed in the order in which they appear in the file. Of the various possible solutions for achieving the smallest square, the one where each Tetrimino is placed as far up and as far to the left as possible will be chosen.

Your program must display the smallest solution square on the standard output. To identify each Tetrimino in the solution square, you will assign an uppercase letter (starting with A) to that Tetrimino in the order they appear in the description file.

Here is a link to a valid input file and to the only expected solution. You can find a lot of different input files along with the associated solutions on the fastest program's repository.

Context

One of my last performance projects at 42
A challenge with more than 300 participants
Staff team participating

Code in Rust (still compiles after a long time). Code in C (no more compile after a long time).

Technical

Introduce the subject and rules (backtracking)
Explain man(2) function limitations
Using bitfields
Computing the smallest map sqrt(x)
Difficulty of the different maps and pieces

Algorithm tricks

Always writing a piece after the last position of the same piece
Recursively texting, storing, and writing the output
Using chars in a bit map

Conclusion

Best Results in C
Best Results in Rust

Talk About Other Ideas

Using GPU (I tried, but it was bad, too many draw calls)
Multithreading
SIMD

Asking Questions

Do you have better ideas?
Why is C slower? Why is code generation bad for C?
Can you beat me?

Kerollmops / blog