Error in recursive function

Pages: 12
Hi everyone,
I was tasked with writing a program, that for an input n returns a wall with the biggest height possible. The rows have to consist of 'bricks' from length 1 to n and as an added difficulty the mortar joints mustn't overlap in any two rows. As an example this is one possible output for n = 4:
Edit: Removed because I made a mistake...

As you can see, there is no point where two mortar joints overlap. The code I have so far can solve this as well, however my task is to specifically test it for n = 10, where the wall should have a height of 6 rows. My programm however stops after the wall has a height of 4.
I tried implementing a recursive function, which - as I said earlier - partially works. Could anybody please have a look at my code and point me in the direction of making the recursion work properly?
Code: (ver. 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
#include <fstream>
#include <vector>

std::vector<std::vector<int> > wall;
std::vector<std::pair<bool, int> > usedBricks;

bool overlaps(int pos, int maxSize, int jointPos)
{
	for (int i = 0; i < wall.size(); i++)
	{
		for (int j = 0; j < wall[0].size(); j++)
		{
			if (wall[i][j] == jointPos && pos != wall[i].size() - 1) //since I'm now storing the position of the joint,
//I just have to check if there already is a joint at said position
				return true;
		}
		
	}

	return false;
}

bool allUsed() //checks if every brick has been used
{
	for (int i = 0; i < usedBricks.size(); i++)
	{
		if (!usedBricks[i].first) return false;
	}

	return true;
}


void makeWall(int jointPos, int gapSize, int maxSize, int position, int row, std::vector<int> joints)
{
	if (allUsed()) return;

	if (jointPos + gapSize > maxSize || gapSize - 1 > (usedBricks.size() - 1)) //if the new brick is bigger than the max. brick size
	{
		for (int i = 0; i < usedBricks.size(); i++)
		{
			if (!usedBricks[i].first && usedBricks[i].second + jointPos <= maxSize &&
				!overlaps(position, maxSize - 1, jointPos + usedBricks[i].second)) //look for another one that fits
				gapSize = usedBricks[i].second;
		}
	}

	jointPos += gapSize;

	if (jointPos > maxSize || gapSize - 1 > usedBricks.size() - 1) return;

	if (overlaps(position, maxSize -1, jointPos) || usedBricks[gapSize - 1].first) //if there is a joint at that position
	{
		if (gapSize - 1 > usedBricks.size() - 1)
			gapSize = 1;

		makeWall(jointPos - gapSize, gapSize + 1, maxSize, position, row, joints);
	}
	else
	{
		usedBricks[gapSize - 1].first = true;
		joints[position] = jointPos;
		makeWall(jointPos, gapSize + 1, maxSize, position +1, row, joints);
	}

	
	if (allUsed())
	{
		
		wall.push_back(joints); //add row to wall

		for (int x = 0; x < joints.size(); x++)
		{
			joints[x] = 0;
		}

		for (int i = 0; i < usedBricks.size(); i++)
		{
			usedBricks[i].first = false;
		}

		makeWall(0, 1, maxSize, 0, row +1, joints);
	}
	else return;

}

//_________________MAIN______________

int main() {
	int n, sum = 0, jointPlacement = 0, gap = 1;
	//std::vector<std::vector<bool> > wall;
	std::vector<int> joints;

	std::cout << "Please submit 'n':" << std::endl;
	std::cin >> n;



	for (int i = 1; i <= n; i++)
	{
		sum += i;
		usedBricks.push_back(std::make_pair(false, i)); 

	}

	for (int i = 0; i < n; i++)
	{
		jointPlacement += gap;
		joints.push_back(jointPlacement); //now I'm saving the position of a joint without actually inserting it into the wall
//this ensures that a brick with the length 10 is actually as long as bricks the with the lengths 1,2,3 and 4
		gap++;
	}

	wall.push_back(joints);

	for (int i = 0; i < joints.size(); i++)
	{
		joints[i] = 0;
	}

	if (n > 1) //if there is more than one row
		makeWall(0, 1, sum, 0, 1, joints);

	std::ofstream myfile;
	myfile.open("mauer.txt");

	int watch = 0;
	int it = 0;

	for (int i = 0; i < wall.size(); i++)
	{
		wall[i].insert(wall[i].begin(), 0);
	}
	

	for (int i = 0; i < wall.size(); i++)
	{
		for (int j = 0; j < sum+(n+1); j++)
		{
			if (watch == wall[i][it])
			{
				myfile << "|";
				if (it + 1 < wall[i].size())
					it++;
			}
			else 
			{
				myfile << "-";
				watch++;
			}
		}
		myfile << std::endl;
		watch = 0;
		it = 0;
	}

	myfile.close();

	return 0;

}
Last edited on
I prefer to just ask rather than try to follow :)
Can you explain how you think you should get 6 from 10? You got 3 from 4.
Last edited on
Can you explain how you think you should get 6 from 10? You got 3 from 4.


Well, first and foremost because it was given in the description of my task (wording was something along the lines of: "Write a program that outputs a wall as high as possible for the given n. Example: Given n = 10 your wall should have a height of 6.")

However, as I don't like just working with given values I tried constructing the first 10 units of each row of these walls on paper and found that there are only the aforementioned 6 ways to place bricks without having two joints in the same column of my vector.
Ok. So its not a computation, it is limited by the possible solutions.

This makes me suspect you are hitting your base case in the recursion prematurely.

Let me ask a different question then... do you always use all the bricks, and if so, did you use them all when you put in 10? And you only have 1 brick for each size?

This sounds familiar ... sort of suduko or magic squareish type thing...
Last edited on
Let me ask a different question then... do you always use all the bricks, and if so, did you use them all when you put in 10? And you only have 1 brick for each size?


Each row consists of - in this case - 10 bricks with the lengths 1 to 10, each brick can be used exactly once per row, yes.

My program uses all the bricks for each row ( I'll just attach the output for n= 10), but stops after 4 rows.

Output:
|-|--|---|----|-----|------|-------|--------|---------|----------|
|--|---|----|-----|------|-------|--------|---------|----------|-|
|---|-----|------|--------|---------|----------|-------|----|-|--|
|-----|------|-------|--------|---------|----------|----|--|-|---|
It's an interesting problem.

Can you repost your code with comments. I can't figure out how your code works.

Notice that for each of your solutions, any subset of the rows will also work. [ Edit: as explained both above and below, the goal is to find the maximum height of a wall with no overlapping joints.] For example, here's your solution for N=10:
|-|--|---|----|-----|------|-------|--------|---------|----------|
|--|---|----|-----|------|-------|--------|---------|----------|-|
|---|-----|------|--------|---------|----------|-------|----|-|--|
|-----|------|-------|--------|---------|----------|----|--|-|---|

The first 3 rows are a solution too:
|-|--|---|----|-----|------|-------|--------|---------|----------|
|--|---|----|-----|------|-------|--------|---------|----------|-|
|---|-----|------|--------|---------|----------|-------|----|-|--|

So how does your code come up with a 4-row solution. Why doesn't it show the 1-row solution:
|-|--|---|----|-----|------|-------|--------|---------|----------|


Shouldn't you have to enter the number of rows, in addition to the number of bricks?

Here's something interesting: the goal is to have no overlapping interior joints. That means that each column in the output can have at most one joint. In other words, the total number of interior joints in the wall can't exceed the number of interior columns in the output. With a little math, you can turn this into an equation for an upper bound on the number of rows

Last edited on
right.
I was thinking it looks like the old number problem:

1 2 3
2 3 1
3 1 2

where each column and each row can only have each number once. I suspect if you can solve that one (which, I think, is magic squares, but I forget, I havent done any classic problems in a long while). Here the value indicates the brick width.

which should therefore have a square solution. I am missing something, probably obvious...
Last edited on
jonnin wrote:
Can you explain how you think you should get 6 from 10?

Because you can't put 63 pigeons in 62 holes.


63 = 7 x 9
62 = ( 1 + 2 + .... + 10 ) + 9 - 2
Last edited on
@jonnin you're thinking of Latin squares. And yes, his problem does sound sort of Coding Theory-esque, although I don't immediately see an obvious solution just based off Latin squares. The solution might correspond to some cyclic code, although I'm not sure where to begin. I think it'd be easier if n were prime...

I hypothesize that you can always start with the row |1|2|3|...|n| and then permute from there, if my coding theory knowledge is correct. Not sure if that's true anymore.

I, so far, cannot find a solution for n=10 with #rows being > 4.

Edit: Here is my brute-force "solution" (It's technically correct [I think], but it's possible that you'll die of old age before it finishes for n=10.)
Clearly it can be improved upon!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#include <iostream>
#include <algorithm>
#include <vector>

using Row = std::vector<int>;
using Wall = std::vector<Row>;

std::string to_string(const Row& row)
{
    int n = row.size();
    std::string s;
    s.reserve( (n * (n-1) / 2) + n + 1 + 1);
    for (auto brick : row)
    {
        s += "|";
        for (int j = 0; j < brick; j++)
        {
            s += "-";
        }
    }
    s += "|";
    return s;
}

std::string to_string(const Wall& wall)
{
    std::string s;
    for (size_t i = 0; i < wall.size(); i++)
    {
        s += (to_string(wall[i]) + "\n");
    }
    return s;
}

std::vector<std::string> to_string_vector(const Wall& wall)
{
    std::vector<std::string> vs(wall.size());
    for (size_t i = 0; i < wall.size(); i++)
    {
        vs[i] = to_string(wall[i]);
    }
    return vs;
}

bool overlapping(const Wall& wall)
{
    if (wall.size() <= 1) return false;
    
    std::vector<std::string> wall_str = to_string_vector(wall);
    size_t m = wall_str[0].length();
    
    if (m <= 2) return false;
    
    for (size_t col = 1; col < m - 1; col++) // bad for cache
    {
        int sum = 0;
        for (size_t row = 0; row < wall_str.size(); row++)
        {
            if (wall_str[row][col] == '|')
                sum++;
        }
        if (sum > 1)
        {
            return true;
        }
    }
    return false;
    
}

int factorial(int n)
{
  return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}

int main()
{    
    int n = 7;
    Row row(n);
    for (int i = 0; i < n; i++)
    {
        row[i] = i + 1;
    }
    
    // O(n! * n! * n) complexity... at least?
    
    int max_rows = 0;
    do {
        
        Wall wall;
        Row starting_row = row;
        
        int curr_rows = 0;
        
        do {
            
            wall.push_back(starting_row);
            curr_rows++;
            
            if (overlapping(wall))
            {
                //std::cout << "(overlapping)\n";
                //std::cout << to_string(wall) << std::endl;
                wall.pop_back();
                curr_rows--;
            }
            else
            {
                if (curr_rows > max_rows)
                {
                    max_rows = curr_rows;
                    std::cout << "(good), max # rows = " << max_rows << "\n";
                    std::cout << to_string(wall);
                    std::cout << std::endl;
                }

            }
        
        } while (std::next_permutation(starting_row.begin(), starting_row.end()));
        
    } while (std::next_permutation(row.begin(), row.end()));

}

Last edited on
Alright, now thats what I call a flood of replies.

Can you repost your code with comments. I can't figure out how your code works.


I did, if you're still interested.


Shouldn't you have to enter the number of rows, in addition to the number of bricks?


No, the point is to find the maximum number of rows the wall can have without overlapping joints (just for clarification, I tested your program, which actually works really well.)

I, so far, cannot find a solution for n=10 with #rows being > 4.


Well, as I said, the value 6 was given, so I assume that it's right.

Here is my brute-force "solution"
That works actually quite well (besides the runtime ;) ), I find the approach using integers instead of the whole wall quite interesting. I'll see and try to optimize it a bit, but so far thank you very much for your work.
See Edit, same mistake I did. The only correct output for n = 4 was confirmed
|-|--|---|----|
|--|---|----|-|
|----|---|-|--|


That looks wrong because the joints take a place in the wall again, whereas they should not take one. I visualized it here:
https://gyazo.com/a4fed8dee38374505ebb9c8d3745dac5

Edit:
Oh and btw, I think I found a mistake I made while still planning this whole thing. I my program I put the joints right in the vector with the bricks, which in return means, that a brick with the length 10 is not the same length as the bricks with the lengths 1,2,3 and 4.
|-|--|---|----|
|----------|


Yay, means I have to do a more complex graphical output than a console window.

Last edited on
|-|-----|------|---|-------|--------|----|---------|--|----------|
|--|-----|----|------|---|-------|-|---------|----------|--------|
|---|-----|------|----|-------|--------|---------|--|----------|-|
|----|-----|------|-------|-|--|--------|---------|----------|---|
|-----|------|--|-------|----|--------|---|----------|-|---------|
|------|----|-------|--|--------|-|---------|---|----------|-----|
Alright, I fixed the mistake outlined in my last post, but I still have the problem that it just stops after adding 2 rows...
Atleast the output for n = 4 is now correct.

I suspect that the sequence in my recursion is somehow messed up and it quits too early because of that. I'll have a deeper look at that.


|-|-----|------|---|-------|--------|----|---------|--|----------|
|--|-----|----|------|---|-------|-|---------|----------|--------|
|---|-----|------|----|-------|--------|---------|--|----------|-|
|----|-----|------|-------|-|--|--------|---------|----------|---|
|-----|------|--|-------|----|--------|---|----------|-|---------|
|------|----|-------|--|--------|-|---------|---|----------|-----|


That's quite nice, did you solve it by hand?
Last edited on
Civer1999 wrote:
That's quite nice, did you solve it by hand?


No, I wrote a program to solve it. Which took an embarassingly long time. I feel like taking it out on a few housebricks at the moment.

My solution isn't recursive, but it does go forward and back along a few false trails, so there's probably a better way.

It takes (actually, it's still taking) a lot longer to prove computationally that you can't build 7 rows from 10 bricks, despite the fact that you can easily show this by "pigeons in holes" (see my post above, and also @dhayden's).

Last edited on
I have a program that finds an answer in 0.889s:
|-|--|---|----|-----|------|-------|--------|---------|----------|
|--|---|----|-----|------|-------|--------|---------|----------|-|
|---|-----|----|------|-------|--------|---------|----------|-|--|
|-----|------|---|--------|-------|----------|----|--|-|---------|
|-------|----------|---|--------|-----|----|--|-|---------|------|
|----------|----|-------|---|--------|--|------|---------|-|-----|


Oddly enough, it takes much longer (55s) to find a solution for N=9:
53 columns
max rows is 6
Wall:
|-|--|---|----|-----|------|-------|--------|---------|
|--|---|----|-----|------|-------|--------|---------|-|
|---|------|----|-----|-------|--------|---------|-|--|
|-----|------|---|--------|----|---------|-|--|-------|
|---------|--------|---|----|-----|--|-------|-|------|
|-------|------|-----|--|----|--------|---------|-|---|


I think my answer is different from Civer1999's because when I start a new row, I start from the configuration of the previous row rather than the configuration of the first row.

Basically my program computes the maximum number of rows and then runs until it finds a solution with that many.
Try 20 bricks and 11 rows.

20 bricks and 10 rows: solution in a fraction of a second.
20 bricks and 12 rows: excluded by pigeon-hole principle.

20 bricks and 11 rows: not excluded by combinatorics, but I can't find a solution either.
I have a program that finds an answer in 0.889s:


That's actually really fast, but your output has the same mistake mine had. Due to adding the joints, the output looks right, but please have a look at line 1 and line 3. There are overlapping joints.

Depends whether joints have any thickness, @Civer1999. Difficult to portray on the console if they don't.

My (limited) experience with bricklaying suggests that you do need a large wadge of mortar to stick the bricks together.
Depends whether joints have any thickness, @Civer1999. Difficult to portray on the console if they don't.

My (limited) experience with bricklaying suggests that you do need a large wadge of mortar to stick the bricks together.


That's true, but I actually asked my teacher whether the joints should have a thickness, to which he answered: "No, for this exercise we are going to assume that the joints do not need to be filled with mortar, much like building walls with toy bricks." Quite late for a clarification like that, but I did assume the same you did, as the task just says brick wall and not toy brick wall.

Oh and btw, I updated my code to the newest version which actually respects this new rule. However it still exits the recursion too early, and uses a .txt-file for output, which is not optimal.
Last edited on
Ah well, @Civer1999, I give you solutions for both possibilities. Neither are recursive. Both took too short a time to measure.

Unit-thickness joints (as earlier):
|-|-----|------|---|-------|--------|----|---------|--|----------|
|--|-----|----|------|---|-------|-|---------|----------|--------|
|---|-----|------|----|-------|--------|---------|--|----------|-|
|----|-----|------|-------|-|--|--------|---------|----------|---|
|-----|------|--|-------|----|--------|---|----------|-|---------|
|------|----|-------|--|--------|-|---------|---|----------|-----|



Zero-thickness joints (not easy to portray at the console):
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
| |           |         |             |       |               |                 |                   |   |     |
| |           |         |             |       |               |                 |                   |   |     |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|   |           |             |         |               |       |                 |     |                   | |
|   |           |             |         |               |       |                 |     |                   | |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|     |           |         |             |       |                 | |   |                   |               |
|     |           |         |             |       |                 | |   |                   |               |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|       |           |             |         |               |     |                 | |   |                   |
|       |           |             |         |               |     |                 | |   |                   |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|         |           |             |               | |                 |                   |   |     |       |
|         |           |             |               | |                 |                   |   |     |       |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
|           |             |     |               |         |                 | |                   |       |   |
|           |             |     |               |         |                 | |                   |       |   |
|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|
Last edited on
Ah well, @Civer1999, I give you solutions for both possibilities. Neither are recursive. Both took too short a time to measure.


Wow, amazing! You do use the pigdeon-hole principle to find the upper bound of rows and find the solution with that upper bound in mind, right? And how do you solve it if not in a recursive form? Is there an algorithm I just didn't find?

Sorry for so many questions, I hope you'll bear with me.
Pages: 12