Piet (Mondrian)'s Puzzle For more information, watch this video, and go to A276523 for a related sequence.

The Mondrian Puzzle (for an integer n) is the following:

Fit non-congruent rectangles into a n*n square grid. What is the smallest difference possible between the largest and the smallest rectangle?

For 6, the optimal difference for M(6) is 5, and can be demonstrated like so:

 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)


The largest rectangle (L) has an area of 2 * 4 = 8, and the smallest rectangle (S) has an area of 1 * 3 = 3. Therefore, the difference is 8 - 3 = 5.

Keep in mind that currently, no optimal solutions for n &gt; 44 have been found.

Your task is to create a program that generates a Mondrian grid that contains a (non-optimal) solution, given an integer n.

You will be tested on the numbers from 100 to 150. Your score for each test will be the difference between the largest and smallest rectangle. Your total score is the sum of your scores for all the tests from 100 to 150.

You must present your output like so:

{number}
{grid}


Where number is the score (the difference between largest and smallest), and grid is either:


A multi-lined string, or
A two-dimensional list.


The grid MUST clearly show where a rectangle starts and ends.

Rules:


Your program must fit within your answer.
Your program must output a value for any number between 100 and 150 within 1 hour on a modern laptop.
Your program must generate the same solution for an integer n every time the program is run.
You must provide a link to the outputs of all 51 solutions (using Pastebin, Github Gist... anything, really).
You must have at least two rectangles on the square grid for your solution.
Piet, 9625

(It finally works!)

The people demanded it, so here it is. This is an extremely naive solution (essentially the same as the loose upper bounds on the OEIS page): it divides each square into just two rectangles.

This gist contains the details in two files:


The program's output (using npiet v1.3) for all required inputs. Note that I only captured stdout, so the ? is the input prompt, followed immediately by the output score, then the grid.
The "pseudo-assembly" source I used to plan out the program.




Explanation

This program takes a single number N as input. If the number is odd, the score is the number; if even, the score is twice the number.

After outputting the score, the rest of the left-hand side of the program is spent filling the stack with five lots of the following information:


The grid width (which is N)
A number of lines to print
A character to print across the grid (either _ or space)
A character to print at each edge of the grid (either space or |)


The right-hand side of the program takes each set of four values and prints out that part of the grid.