Problem about a wall and bricks. How to decide?

Question

Programming

Good afternoon!
At a junior interview, they asked me a problem on which I got stuck.
Here is the task, tell me where to dig? All the solutions that come to my mind require a huge amount of memory and are terribly suboptimal :(
The task itself:
There are two types of bricks: 3 and 4 long. From these bricks you need to build a wall 25 long and 10 rows high. An additional condition is that there are gaps in two consecutive rows vertical lines should not be created between bricks.That is, for example, a wall 8 long and two rows high cannot be built (1 row (4.4), 2 row (4.4) - a gap in the middle)
. possible combinations of bricks when building a wall of this size
Thanks in advance for your help

Answer 1

Well, I would start by solving the equation in positive integers 3*x+4*y=25. There are two solutions: (x=3, y=4) and (x=7, y=1). Those. we have 2 classes of rows. There are 7!/(3!*4!)=35 options for the arrangement of bricks in the first class, 8!/(7!*1!)=8 in the second class. Total 35+8=43 variants of the row. We generate them. Now we fill in a 43*43 matrix, putting ones where the rows of bricks (one in a column, the second in a column) are compatible with the condition of the absence of a common vertical gap (for each variant of the row we build a set {L[1], L[1] + L [2], ... L1+...L[N-1]}, then it is obvious that the series are "compatible" if the intersection of the sets is empty). It's all fast and requires little memory. In python - 30 lines. By the way, in the constructed matrix there are much more zeros than ones. several rows are simply not compatible with any other. And then, alas, too much if I understand the problem correctly. Like in the classical problem "put 8 queens on a chessboard so that they do not beat each other."
Update:
The code in python 3.4.3 that solves the problem by iterating (except for getting the "classes" of the series) is given below:

import itertools


def build_tail(height, row):
    if height == 9:
        return neighbours_number[row]
    else:
        return sum(build_tail(height+1, i) for i in acceptable_neighbours[row])


rows = {i for i in itertools.permutations([3, 3, 3, 4, 4, 4, 4], 7)} | \
       {i for i in itertools.permutations([3, 3, 3, 3, 3, 3, 3, 4], 8)}

acc_rows = [set(itertools.accumulate(row[: -1])) for row in rows]
acceptable_neighbours = [[i for i, b in enumerate(acc_rows) if not (a & b)] for a in acc_rows] # copied from @bobrovskyserg
neighbours_number = [len(i) for i in acceptable_neighbours]

print(sum(build_tail(1, i) for i in range(0, len(acc_rows))))

The solution time is ~40 seconds, I confirm the answer of bobrovskyserg . I went to deal with his algorithm ...

Answer 2

Usual combinatorics
1. We determine all the different combinations of bricks that fit exactly 25 m - there are not so many of them, by the way, because 25 \u003d 3x3 + 4x4 \u003d 7x3 + 1x4, and only
2. We determine which of them cannot lie next to -for gaps
3. Recursive enumeration of the resulting options for the first, for him - the second, etc. rows
Nothing particularly non-optimal from memory should be obtained
. PS Oh, yes, you just need to calculate the number. Then it’s easier to start solving the problem on a piece of paper in a box - you see, you don’t need to program at all

Answer 3

The wall must be level. Right?
We are building a tree.
(left +3, right +4)
We go only to 21, 22 and 25

3 
|\
6  7
|\ |\
9 10 11
|\ |\ |\
12 13 14 15
15 16 17 18 19
18 19    21 22 
21 22       25
   25

4 is easier. there are only 2 values. The rest of the branches were already in the top three.
Those branches that have already been (start with the same number) can be thrown out, because these are "gaps"

0
3  4 
6  7  8
9 10 11
12 13 
15 16 
18 19
21 22
   25

That is, 4 + 4 + 4|3 The sums are the same if you start with 3.
3 + 4 + 4 = 4 + 4 + 3
3 + 3 + 3 + 3 = 4 + 4 + 4
But you won't get 8.
3 + 3|4 != 4 + 4
We count branches. 11 pieces.
But we are not interested in the intersection of the first and the last. 11 - 1.
What is the result? We have a seamless wall, or rather its rows (10 rows).
ten! = 3628800;
PS.
Forgive me mathematicians.
UPD: Fixed branches.