Home > Software design >  Codewars UndefinedBehaviorSanitizer:DEADLYSIGNAL
Codewars UndefinedBehaviorSanitizer:DEADLYSIGNAL

Time:11-15

When I use this code in Visual Studio, it works normally, but when I paste it to Codewars, this error appears. What did I suppose to do? Also, is the output function are valid?

This code for Skyscrapers 4x4 kata from codewars https://www.codewars.com/kata/5671d975d81d6c1c87000022/train/cpp Also can change it to 6x6 (and any other size) easily.

STDERR
UndefinedBehaviorSanitizer:DEADLYSIGNAL
==1==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x0000ffffffff (pc 0x0000004254dd bp 0x000000000000 sp 0x7fff88975810 T1)
==1==The signal is caused by a WRITE memory access.
==1==WARNING: invalid path to external symbolizer!
==1==WARNING: Failed to use and restart external symbolizer!
    #0 0x4254dc  (/workspace/test 0x4254dc)
    #1 0x42cf0a  (/workspace/test 0x42cf0a)
    #2 0x42b79e  (/workspace/test 0x42b79e)
    #3 0x42b31f  (/workspace/test 0x42b31f)
    #4 0x42af7b  (/workspace/test 0x42af7b)
    #5 0x42f2f5  (/workspace/test 0x42f2f5)
    #6 0x42566d  (/workspace/test 0x42566d)
    #7 0x7f929bdf5bf6  (/lib/x86_64-linux-gnu/libc.so.6 0x21bf6)
    #8 0x404249  (/workspace/test 0x404249)

UndefinedBehaviorSanitizer can not provide additional info.
==1==ABORTING

Code:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;

void print(vector<int> array) {
    for (unsigned int i = 0; i < array.size(); i  ) cout << array[i] << " ";
}

int check_visible(vector<int> row) {
    int visible = 0, current_height = 0;
    for (unsigned int i = 0; i < row.size(); i  ) {
        if (row[i] > current_height) {
            current_height = row[i];
            visible  ;
        }
    }
    return visible;
}


class possible_vars {
public:
    vector<int> vars;

    /*possible_vars& operator= (const possible_vars& vars2)
    {
        vars = vars2.vars;
        return *this;
    }*/
    possible_vars& operator= (const vector<int>& vars2)
    {
        vars = vars2;
        return *this;
    }

    possible_vars(int bsize) {
        for (int i = 0; i < bsize; i  ) vars.push_back(i   1);
    }

    possible_vars(vector<int> input) {
        vars = input;
    }

    int size() {
        return vars.size();
    }

    bool remove_variant(int num) {
        bool is_changed = false;
        for (unsigned int i = 0; i < vars.size(); i  ) {
            if (vars[i] == num) {
                vars.erase(vars.begin()   i);
                is_changed = true;
                break;
            }
        }
        return is_changed;
    }

    bool is_var_here(int var) {
        if (find(vars.begin(), vars.end(), var) != vars.end()) return true;
        else return false;
    }
};

class skyscrapers {
public:
    vector<vector<possible_vars>> solution;
    vector<vector<short>> solution_static;
    vector<int> clues;
    vector<vector<int>> patterns;
    vector<int> pattern;
    int basic_size;

    skyscrapers(int size_of_field) {
        solution = vector<vector<possible_vars>>(size_of_field, vector<possible_vars>(size_of_field,possible_vars(size_of_field)));
        solution_static = vector<vector<short>>(size_of_field, vector<short>(size_of_field, false));
        clues = vector<int>(size_of_field * size_of_field);
        basic_size = size_of_field;
    }

    vector<vector<possible_vars>> patterns_by_det;
    vector<vector<possible_vars>> excluding_patterns;

    void generate_excluding_base() {
        possible_vars for_one_number(basic_size);
        vector<possible_vars> for_one_pattern;
        for (int i = 0; i < basic_size; i  ) {
            for_one_pattern.push_back(for_one_number);
        }
        for (int i = 0; i < basic_size; i  ) {
            excluding_patterns.push_back(for_one_pattern);
        }
    }

    void generate_patterns() {
        vector<int> base;
        for (int i = 0; i < basic_size; i  ) {
            base.push_back(i   1);
        }
        generate_patterns_re(base);
        int seen;
        patterns_by_det = vector<vector<possible_vars>>(basic_size);
        for (unsigned int i = 0; i < patterns.size(); i  ) {
            seen = check_visible(patterns[i]);
            patterns_by_det[seen - 1].push_back(possible_vars(patterns[i]));
        }
        generate_excluding_base();
        for (unsigned int i = 0; i < patterns_by_det.size(); i  ) {
            for (unsigned int j = 0; j < patterns_by_det.size(); j  ) {
                for (unsigned int k = 0; k < patterns_by_det[i].size(); k  ) {
                    excluding_patterns[i][j].remove_variant(patterns_by_det[i][k].vars[j]);
                }
            }
        }
    }

    void generate_patterns_re(vector<int> possible_vars) {
        vector<int> next;
        if (possible_vars.size() > 1) {
            for (unsigned int i = 0; i < possible_vars.size(); i  ) {
                pattern.push_back(possible_vars[i]);
                next = possible_vars;
                next.erase(next.begin()   i);
                generate_patterns_re(next);
                pattern.pop_back();
            }
        }
        else {
            pattern.push_back(possible_vars[0]);
            patterns.push_back(pattern);
            pattern.pop_back();
        }
    }

    vector<possible_vars*> get_row(int row_index) {
        vector<possible_vars*> row;
        possible_vars* cell;
        if (row_index / basic_size == 0) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution[i][row_index % basic_size];
                row.push_back(cell);
            }
        }
        else  if (row_index / basic_size == 1) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution[row_index % basic_size][basic_size - 1 - i];
                row.push_back(cell);
            }
        }
        else  if (row_index / basic_size == 2) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution[basic_size - 1 - i][basic_size - 1 - row_index % basic_size];
                row.push_back(cell);
            }
        }
        else  if (row_index / basic_size == 3) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution[basic_size - 1 - row_index % basic_size][i];
                row.push_back(cell);
            }
        }
        return row;
    }

    vector<short*> get_static_row(int row_index) {
        vector<short*> row;
        short* cell;
        if (row_index / basic_size == 0) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution_static[i][row_index % basic_size];
                row.push_back(cell);
            }
        }
        else  if (row_index / basic_size == 1) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution_static[row_index % basic_size][basic_size - 1 - i];
                row.push_back(cell);
            }
        }
        else  if (row_index / basic_size == 2) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution_static[basic_size - 1 - i][basic_size - 1 - row_index % basic_size];
                row.push_back(cell);
            }
        }
        else  if (row_index / basic_size == 3) {
            for (int i = 0; i < basic_size; i  ) {
                cell = &solution_static[basic_size - 1 - row_index % basic_size][i];
                row.push_back(cell);
            }
        }
        return row;
    }

    void remove_all_vars(int y, int x) {
        for (int i = 0; i < basic_size; i  ) {
            if (i != x) solution[y][i].remove_variant(solution[y][x].vars[0]);
        }
        for (int i = 0; i < basic_size; i  ) {
            if (i != y) solution[i][x].remove_variant(solution[y][x].vars[0]);
        }
    }

    bool normalize() {
        bool is_changed = false;
        for (int i = 0; i < basic_size; i  ) {
            for (int j = 0; j < basic_size; j  ) {
                if (solution_static[i][j] == false and solution[i][j].vars.size() == 1) {
                    solution_static[i][j] = true;
                    remove_all_vars(i, j);
                    is_changed = true;
                }
            }
        }
        return is_changed;
    }

    bool add_obvious() {
        bool is_changed = false;
        map<int, int> counting;
        for (int i = 0; i < basic_size; i  ) counting.insert(pair<int, int>(i   1, 0));
        for (int i = 0; i < basic_size; i  ) {
            for (int j = 1; j <= basic_size; j  ) counting[j] = 0;
            for (int j = 0; j < basic_size; j  ) {
                for (int k = 0; k < solution[i][j].size(); k  ) {
                    counting[solution[i][j].vars[k]]  = 1;
                }
            }
            for (int k = 1; k <= basic_size; k  ) {
                if (counting[k] == 1) {
                    for (int j = 0; j < basic_size; j  ) {
                        if (solution_static[i][j] == false and solution[i][j].is_var_here(k)) {
                            solution[i][j].vars = { k };
                            solution_static[i][j] = true;
                            remove_all_vars(i, j);
                            is_changed = true;
                        }
                    }
                }
            }
        }
        for (int j = 0; j < basic_size; j  ) {
            for (int j = 1; j <= basic_size; j  ) counting[j] = 0;
            for (int i = 0; i < basic_size; i  ) {
                for (int k = 0; k < solution[i][j].size(); k  ) {
                    counting[solution[i][j].vars[k]]  = 1;
                }
            }
            for (int k = 1; k <= basic_size; k  ) {
                if (counting[k] == 1) {
                    for (int i = 0; i < basic_size; i  ) {
                        if (solution_static[i][j] == false and solution[i][j].is_var_here(k)) {
                            solution[i][j].vars = { k };
                            solution_static[i][j] = true;
                            remove_all_vars(i, j);
                            is_changed = true;
                        }
                    }
                }
            }
        }
        return is_changed;
    }

    bool fix_matrix() {
        bool is_changed = false, is_changed_global = false;
        do {
            is_changed = normalize();
            is_changed_global  = is_changed;
        } while (is_changed == true);
        do {
            is_changed = add_obvious();
            is_changed_global  = is_changed;
        } while (is_changed == true);
        return is_changed_global;
    }

    bool use_excluding_patterns() {
        bool is_changed = false;
        vector<possible_vars*> row;
        int current_value;
        for (unsigned int curr_clue = 0; curr_clue < clues.size(); curr_clue  ) {
            if (clues[curr_clue] != 0) {
                row = get_row(curr_clue);
                current_value = clues[curr_clue] - 1;
                for (unsigned int i = 0; i < excluding_patterns[current_value].size(); i  ) {
                    for (int j = 0; j < excluding_patterns[current_value][i].size(); j  ) {
                        is_changed  = row[i]->remove_variant(excluding_patterns[current_value][i].vars[j]);
                    }
                }
            }
        }
        return is_changed;
    }

    bool use_patterns() {
        bool is_changed = false, is_suitable;
        vector<possible_vars*> row;
        vector<short*> static_row;
        int current_value;
        vector<possible_vars> current_patterns;
        for (unsigned int curr_clue = 0; curr_clue < clues.size(); curr_clue  ) {
            if (clues[curr_clue] != 0) {
                row = get_row(curr_clue);
                static_row = get_static_row(curr_clue);
                current_value = clues[curr_clue] - 1;
                current_patterns = patterns_by_det[current_value];
                for (unsigned int i = 0; i < current_patterns.size(); i  ) {
                    //for (int print = 0; print < current_patterns[i].size(); print  ) cout << current_patterns[i].vars[print] << " ";
                    //cout << endl;
                    for (int j = 0; j < current_patterns[i].size(); j  ) {
                        is_suitable = row[j]->is_var_here(current_patterns[i].vars[j]);
                       // cout << j 1 << "-> " << is_suitable << endl;
                        if (is_suitable == false) {
                            current_patterns.erase(current_patterns.begin()   i);
                            i--;
                            //cout << endl << "Erased, now current patterns:" << endl;
                            /*for (int print1 = 0; print1 < current_patterns.size(); print1  ) {
                                for (int print2 = 0; print2 < current_patterns[print1].size(); print2  ) cout << current_patterns[print1].vars[print2] << " ";
                                cout << endl;
                            }
                            cout << endl;*/
                            break;
                            
                        }
                    }
                }
                if (current_patterns.size() == 1) {
                    for (unsigned int i = 0; i < row.size(); i  ) {
                        if (*static_row[i] == false) {
                            *static_row[i] = true;
                            is_changed = true;
                            *row[i] = possible_vars(vector<int>(1, current_patterns[0].vars[i]));
                        }
                        
                    }
                }
            }
        }
        return is_changed;
    }

    void print() {
        for (int i = 0; i < 4; i  ) {
            for (int j = 0; j < 4; j  ) {
                for (int k = 0; k < solution[i][j].size(); k  ) cout << solution[i][j].vars[k];
                cout << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
};

int** SolvePuzzle(int* clues) {
    
    skyscrapers result(4);
    result.generate_patterns();
    for (int i = 0; i < 16; i  ) {
        result.clues[i] = clues[i];
    }
    bool is_changed = true;
    result.use_excluding_patterns();
    result.fix_matrix();
    while (is_changed) {
        is_changed = result.use_patterns();
        is_changed  = result.fix_matrix();
    }
    int** answer[4][4];
    for (unsigned int i = 0; i < result.solution.size(); i  ) {
        for (unsigned int j = 0; j < result.solution[i].size(); j  ) {
            *answer[i][j] = &result.solution[i][j].vars[0];
        }
    }
    return **answer;
}

CodePudding user response:

This block of code appears suspicious for several reasons:

int** answer[4][4];
for (unsigned int i = 0; i < result.solution.size(); i  ) {
    for (unsigned int j = 0; j < result.solution[i].size(); j  ) {
        *answer[i][j] = &result.solution[i][j].vars[0];
    }
}
return **answer;

&result.solution[i][j].vars[0] is a pointer to something inside that result object. As soon as the function returns, result will destruct and the pointers assigned to answer[i][j] is no longer valid when the function returns.

Also, returning **answer is really suspicious. With regards to a local 2-d array, this statement would in essence only return the int** inside answer[0][0]. None of the other values inside answer would be passed back - even if result wasn't destructing.

CodePudding user response:

The problem is that you made a 4x4 array of int**. Here is the fixed code:

int** answer = new int*[4];
for (unsigned int i = 0; i < result.solution.size(); i  ) {
  answer[i] = new int[4];
    for (unsigned int j = 0; j < result.solution[i].size(); j  ) {
        answer[i][j] = result.solution[i][j].vars[0];
    }
}
  • Related