cpp4fun/algo/ship_game.cpp at master · ayubsayyad/cpp4fun · GitHub

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
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <tuple>

struct Point{
    int     y_;
    char    x_;
    Point(int y, char x) : y_(y), x_(x){}
};

struct Compare {
    bool operator() (const Point  &lhs, const Point& rhs) const{
        return std::tie(lhs.y_, lhs.x_) < std::tie(rhs.y_, rhs.x_);
    }
};

struct Ship{
    Point p1_;
    Point p2_;
    int total_cells;
    int hit_cells;

    Ship(Point p1, Point p2): p1_(p1), p2_(p2){
        total_cells = (std::abs(p1_.y_ - p2_.y_) + 1) * (std::abs(p1_.x_ - p2_.x_) + 1);
        hit_cells = 0;
        //std::cout << total_cells << std::endl;
    }

    bool hit_ship(const Point& bullet){
        if((bullet.y_ >= p1_.y_) && (bullet.y_ <= p2_.y_) &&
           (bullet.x_ >= p1_.x_) && (bullet.x_ <= p2_.x_)){
            hit_cells++;

            return true;
        }
        return false;
    }
};

int getCoordinates(const std::string& str, int startidx, Point& pt){

    int chars = 3;

    char n[3] = {0};
    n[0] = str[startidx];
    char ch = str[startidx + 1];
    if(str[startidx + 1] < 65){
        n[1] = str[startidx + 1];
        ch = str[startidx + 2];
        chars = 4;
    }

    pt = Point(atoi(n), ch);

    return chars;

}

std::string solution(int N, const std::string ships, const std::string T){
    std::vector<Ship> vec;
    int start_idx = 0;
    int i = 0;
    for(; i <= ships.size(); ++i){
        if((ships[i] == ',') || (ships[i] == '\0')){
            Point pt1(0,0);
            int chars = getCoordinates(ships, start_idx, pt1);

            Point pt2(0,0);
            chars = getCoordinates(ships, start_idx + chars, pt2);

            vec.push_back(Ship(pt1, pt2));
            ++i;
            start_idx = i;
        }
    }

    std::set<Point, Compare> bullet_set;
    i = 0;
    start_idx = 0;
    for(; i <= T.size(); ++i){
        if(T[i] == ' ' || T[i] == '\0'){
            Point bullet(0,0);
            getCoordinates(T, start_idx, bullet);
            i++;
            start_idx = i;

            auto iter = bullet_set.find(bullet);
            if(iter != bullet_set.end()){
                //std::cout << "found" << std::endl;
                continue;
            }
            bullet_set.insert(bullet);

            for(Ship& s : vec){
                if(s.hit_ship(bullet)) break; // ships are not overlapping so if bullet hits, it wont hit again
            }
        }
    }

    int distroyed = 0;
    int hit = 0;
    for(Ship& s : vec){
        if(s.hit_cells != 0){
            if(s.hit_cells >= s.total_cells){
                distroyed++;
            }
            else{
                hit++;
            }
        }
    }

    char solution[100 + 1] = {0};
    snprintf(solution, 100, "%d,%d", distroyed, hit);

    return std::string(solution);
}

int main(){
    std::cout << solution(10, "1B 2C,2D 4D", "2B 2D 3D 4D 4A") << std::endl;;
    std::cout << solution(10, "1A 1B,2C 2C", "1B") << std::endl;
    std::cout << solution(10, "1A 2A,12A 12A", "12A 12A") << std::endl;
}