C++

Forum

 
Simple Tree Code/ Wrong Output Help

hixtus (5)
We've been tasked to create an Octree that has blue and white voxels. However, I've only been able to get the correct answers for Inputs with Level 1 and Level 2. I've been stuck on this problem for days. I would appreciate any help or correction I can get. Thank you

Details:
1. p - denotes that the large voxel still needs to be divided into octants
b - voxel is blue
w - voxel is white
2. Assume that voxels that were not assigned any color are white
3. Input: N denotes how many pairs are to be added to each other

Correct Output:
4096
3072
2048
1184

Input:
1
2
3
4
5
6
7
8
9
 
4
b
w
pbbbbwwww
pbwbwbwbw
pbpbbwwwwbbwwwwpbbwwwwbbb
ppbbwwwwbbbwwwwbpbbwwwwbb
pppbwwwwwbwwwwwwbwwwwwwbw
pwpwpwbwwwwwbwwwwwbwwwwwb

Octree: 
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
 
  #include <iostream>
#include <queue> 
#include <string>
#include <cmath>
using namespace std; 

int N,lvl;
string s1,s2;
int index_a = 0;
int index_b = 0;
int VCount();

struct Node 
{ 
    char data;
    vector<Node *>child; 
}; 

Node *newNode(char data) 
{ 
    Node *temp = new Node; 
    temp->data = data;
    return temp; 
} 

Node *root;
int Voxels(vector<Node *> _root, int level);


int main() 
{ 
    cin>>N;
    for(int i=0;i<N;i++){
        root = newNode('w');
        cin>>s1;
        cin>>s2;
            lvl = 1;
            for(int j = 0; s1[j] != '\0'; j++){
                if(s1[j] == 'p')
                    lvl++;
            }
        cout<<VCount();
        cout<<'\n';
        index_a = 0;
        index_b = 0;
        lvl = 0;
    }     
return 0;   
}  

int VCount(){

    int _vox = 0;

        for(int l = 0; l < 8; l++)                                                                      //  Level 1
            (root->child).push_back(newNode('w'));   
                if (lvl == 1)
                return Voxels(root->child,1);

            if (lvl >= 2){
                 for(int k = 0; k < 8; k++){                                                             //  Level 2
                    for(int j = 0; j < 8; j++){
                        (root->child[k]->child).push_back(newNode('w'));
                    }
                 }
                _vox = Voxels(root->child,2);


            if (lvl >= 3){
                for(int l = 0; l < 8; ++l){
                    for(int k = 0; k < 8; k++){                                                         //  Level 3
                        for(int j = 0; j < 8; j++){
                            (root->child[l]->child[k]->child).push_back(newNode('w')); 
                        }

                    }
                    _vox += Voxels(root->child[l]->child,3);
                }


                if (lvl == 4){
                    for(int l = 0; l < 8; l++){      
                        for(int k = 0; k < 8; k++){                                                     //  Level 4
                            for(int j = 0; j < 8; j++){
                                for(int i = 0; i < 8; i++)
                                    (root->child[l]->child[k]->child[j]->child).push_back(newNode('w'));   
                            }
                        _vox += Voxels(root->child[l]->child[k]->child,4);
                    }
                  }
                }

            }

        }

    return _vox;  
}

int Voxels(vector<Node *> _root, int level){
int _voxels = 0;
int _ind;
int branch = 0;

        if(s1.size() == 1){
                if(s1[index_a] =='b' || s2[index_b] == 'b')
                    return 4096;
                else
                    return 0;
            }

        index_a++;
        index_b++;
        _ind = index_a;


            if(s1[index_a] != 'p' && s2[index_b] != 'p'){
                for(int i = index_a, j = 0; i < s1.size() && s1[i] != 'p'; i++,j++){
                    if(s1[i] == 'b'){
                        _root[branch]->child[j]->data = 'b';
                        _voxels++;
                    }
                    if(j==7){
                        branch++;
                        j=0;
                    }
                    index_a = i;  
                }
                for(int i = index_b, j = 0; i < s2.size() && s2[i] != 'p'; i++, j++){
                    if(s2[i] == 'b' && s1[_ind] != 'b'){
                        _root[branch]->child[j]->data = 'b';
                        _voxels++;
                    }
                    if(j==7){
                        branch++;
                        j=0;
                    }
                   _ind++;
                }
            }

return (4096/pow(8,level-1))*_voxels;
}


Thank you so much!
Last edited on
ne555 (10692)
https://selftaughtcoders.com/rubber-duck-debugging/

> We've been tasked to create an Octree that has blue and white voxels.
...
> However, I've only been able to get the correct answers for Inputs with Level 1 and Level 2.
¿quack?

> Details:
> 1. p - denotes that the large voxel still needs to be divided into octants
¿quack?

> b - voxel is blue
> w - voxel is white
> 2. Assume that voxels that were not assigned any color are white
¿quack?

> 3. Input: N denotes how many pairs are to be added to each other
¿quack?

> Correct Output:
> 4096
> 3072
> 2048
> 1184
¿quack?


answer the duck
nuderobmonkey (640)
It's hard to follow the logic of your program, you have not even one comment at this. That's very very bad programming style.

All I can see is that your VCount function cries to being implemented in a recursive manner:
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
 
/*
 * Recursive calling, depth: from 'level' to (gloal) 'lvl'.
 */
int VCount( Node* node, int level)
{
    // Recursion stop condition
    if (level == lvl)
        return Voxels( node, level );
    
    // Creating 8 children for this Node
    for (int i = 0;  i < 8;  ++i)
    {
         (node->child).push_back(newNode('w'));
    }
    
    // Calling VCount in recursive manner
    // and adding from each leaf the 'vox' value
    // (whatever 'vox' may be).
    int vox = 0;
    for (Node* & child : node->child)
    {
        vox += VCount( child, level+1);
    }
    return vox;   
}
Last edited on
dhayden (5798)
You are passing root by value to Voxels. That means Voxels modifies it's local copy and then throws it away. Is that what you intended?

You haven't really described the problem with enough detail for us (or me anyway) to understand it. Can you elaborate?
Topic archived. No new replies allowed.