forked from YasinEhsan/CPPrograms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rat.cpp
177 lines (141 loc) · 4.46 KB
/
rat.cpp
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
//Yasin Ehsan
//RAT CLASS + SHortest path NON Recursive
// --> I couldn't upload two files in shortest path project submission, so the non recursive version is here
// RAT CLASS- Learned: friend function implementation and freedom to customize operator funcs
//SHORTEST PATH NR: Recursive code isn't always the more succint
// - DEBUG Hurdles: 1) switched rows and colomns. 2) appended weight matrix instead of the cost matrix
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int NUM_ROWS = 5, NUM_COLS = 6;
string path[NUM_ROWS][NUM_COLS];
void calculateCosts() {
static int weight[NUM_ROWS][NUM_COLS] = {{3,4,1,2,8,6},
{6,1,8,2,7,4},
{5,9,3,9,9,5},
{8,4,1,3,2,6},
{3,7,2,8,6,4}};
static int cost [NUM_ROWS][NUM_COLS]; //Should be static so the cost remains same reagardless of many time the function is called
// Copy the leftmost column of the weight matrix to the cost matrix, and initialize the leftmost column of the path matrix.
for(int i = 0; i < NUM_ROWS; i++){
cost[i][0] = weight[i][0];
path[i][0] = to_string(i);
}
// For each remaining column,
// Calculate the cost of each square in the column (non-recursively),
// and store the correct number in the cost matrix and the correct string in the path matrix.
for(int i = 1; i < NUM_COLS; i++){
for(int j = 0; j < NUM_ROWS; j++){
//Determining the cheapest option
int up = cost[(j-1 + NUM_ROWS)%NUM_ROWS][i-1]; //next col thus J + 1
int left = cost[j][i-1]; //Becuz this prog is non-recursive we increment J rather decrement J
int down = cost[(j+1)%NUM_ROWS][i-1];
int minCost = min(min(up,down), left);
//storing variable
if(minCost==up)
path[j][i] = path[(j-1 + NUM_ROWS) % NUM_ROWS][i-1] + to_string(j);
else if(minCost==left)
path[j][i] = path[j][i-1] + to_string(j);
else
path[j][i] = path[(j+1)%NUM_ROWS][i-1] + to_string(j);
cost[j][i] = weight[j][i] + minCost;
}
}
int minRow = 0;
// Check which square in the rightmost column has the lowest cost. Store the row number of that square in minRow
for(int i = 0; i < NUM_ROWS; i++)
if(cost[minRow][NUM_COLS-1] > cost[i][NUM_COLS-1])
minRow = i;
cout << "The length of the shortest path is " << cost[minRow][NUM_COLS-1];
cout << ".\nThe rows of the path from left to right are " << path[minRow][NUM_COLS-1] << ".";
}//SHORTEST PATH ENDS HERE
class Rat{
private:
int n;
int d;
public:
Rat(){
n=0;
d=1;
}
Rat(int i, int j){
n = i;
d = j;
}
Rat(int i){
n=i;
d=1;
}
int getN(){ return n;}
int getD(){ return d;}
void setN(int i){ n=i;}
void setD(int i){ d=i;}
Rat operator+(Rat r){
Rat t;
t.n = n*r.d + d*r.n; //'this' makes it more clear to me. NOT WORKING
t.d = d*r.d;
return t;
}
Rat operator-(Rat r){
Rat t;
t.n = n*r.d - d*r.n;
t.d = d*r.d;
return t;
}
Rat operator*(Rat r){
Rat t;
t.n = n*(r.n);
t.d = d*r.d;
return t;
}
Rat operator/(Rat r){
Rat t;
t.n = n*(r.d);
t.d = d*r.n;
return t;
}
// 2 overloaded i/o operators
friend ostream& operator<<(ostream& os, Rat r);
friend istream& operator>>(istream& is, Rat& r);
//end Rat
};
int gcd(int a, int b){ // a is greater and b is smaller...Though it doesnt matter
if(b == 0)
return a;
return gcd(b, a%b);
}
ostream& operator<<(ostream& os, Rat r){
if(r.n > r.d){
if(r.n % r.d == 0)
os << r.n / r.d << endl;//simplfies to integer
else
os<<r.n/r.d<< " " << r.n%r.d << " / " << r.d <<endl;//creates mixed number
}
else
os<< r.n / gcd(r.n, r.d) << " / " << r.d / gcd(r.n, r.d) <<endl; //reduces function
return os;
}
istream& operator>>(istream& is, Rat& r){
is>>r.n>>r.d;
return is;
}
int main(){
cout << "****SHORTEST PATH Non Recursive OUTPUT****\n";
calculateCosts(); //calling SP NR
cout << "\n\n****RAT CLASS OUTPUT****\n";
Rat x(1,2), y(2,3), z;
z=x*y; // returns 2/6
cout<<z; // returns 1/3 simplified
x.setN(3);
y.setD(2);
z=x+y;
cout<<z;
printf("%s", "\nAyoo, enter a rat");
cin>>x;
cout<<x;
Rat v(5);
z = x+v;
cout<<z;
return 0;
}