Instructions
Requirements and Specifications
- Consider the consecutive 'ones' in the matrix and group them (green boxes).
- Each group should contain the largest number of 'ones' and no blank cells.
- The number of 'ones' in a group must be a power of 2 i.e. a group can contain:
- Grouping is carried-on in decreasing order meaning, one must try to group for 8 (octet) first, then for 4 (quad), followed by 2 and lastly for 1 (isolated 'ones').
- Grouping is done either horizontally or vertically or in terms of rectangles/squares. Diagonal grouping of 'ones' is not permitted.
- The same element(s) may repeat in multiple groups only if this increases the size of the group.
- The elements around the edges of the matrix, including the four corners, are adjacent and can be grouped together.
Source Code
PROBLEM A
#include <iostream>
#include "Board.h"
using namespace std;
int getMaxHeight(int *M, int r, int c, int i, int j, int w)
{
int j2 = -1;
int i2;
if (*(M + j * r + i) != 0) {
for (j2 = j; j2 < c && *(M + j2 * r + i) != 0; j2++)
{
for (i2 = i; i2 - i < w; i2++)
{
if (*(M + r * j2 + i2) == 0)
return j2 - j;
}
}
}
return j2 - j;
}
void findLargestRectangle(int *M, int r, int c, int i, int j, int *ei, int *ej)
{
int max_width = 0;
int max_height = 0;
int max_area_covered = 0;
*ei = *ej = -1;
for (max_width = 0; max_width < r - i && (*(M + j * r + (i + max_width)) != 0); max_width++)
{
int area_covered;
int height_i = getMaxHeight(M, r, c, i, j, max_width + 1);
if (height_i > max_height)
{
max_height = height_i;
}
area_covered = height_i * (max_width + 1);
if (area_covered > max_area_covered)
{
max_area_covered = area_covered;
*ei = i + max_width;
*ej = j + height_i - 1;
}
}
}
void printMatrix(int* M, int r, int c)
{
cout << "Generated grid:" << endl << endl;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cout << *(M + r * i + j) << " ";
}
cout << endl;
}
}
int main()
{
int j2;
int i2;
int i = 0;
int j = 0;
int total_rects = 0;
// Ask for number of rows and columns
int r, c;
cout << "Enter number of rows (2-10): ";
cin >> r;
// check that value is between 2 and 10
if (r < 2 || r > 10)
{
cout << "Number of rows must be between 2 and 10" << endl;
exit(1);
}
cout << "Enter number of columns (2-10): ";
cin >> c;
// check that value is between 2 and 10
if (c < 2 || c > 10)
{
cout << "Number of columns must be between 2 and 10" << endl;
exit(1);
}
// Create a matrix and fill it
int *M = (int*)malloc((r*c) * sizeof(int));
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
*(M + r * i + j) = (int)(rand() % 2); // random between 0 and 1
}
}
cout << endl;
printMatrix(M, r, c);
cout << endl;
for (j = 0; j < c; j++) {
for (i = 0; i < r; i++)
{
if (*(M + j * c + i) == 1) // the value is 1
{
findLargestRectangle(M, r, c, i, j, &i2, &j2);
int start_i;
int start_j;
total_rects++;
for (start_j = j; start_j <= j2; start_j++)
{
for (start_i = i; start_i <= i2; start_i++)
{
*(M + start_j * c + start_i) = 2;
}
}
//printMatrix(M, r, c);
}
}
}
cout << "The minimum number of rectnagles/squares formed is " << total_rects << endl; // print
return 0;
}
PROBLEM B
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int main()
{
// read file
string file_name;
cout << "Enter the file name: ";
getline(cin, file_name);
ifstream file(file_name);
string line;
int i = 0;
getline(file, line);
int n = stoi(line);
string departure_city, destination_city;
int departure_day, departure_month, departure_hour, departure_min;
int departure_tz_hr, departure_tz_min;
int destination_day, destination_month, destination_hour, destination_min;
int destination_tz_hr, destination_tz_min;
int departure_tz, destination_tz;
int travel_time_hr, travel_time_min;
int travel_time;
int departure_time;
for (int i = 0; i < n; i++)
{
int fid = 0;
for (int j = 0; j < 6; j++)
{
getline(file, line);
if (fid == 0) // departure city
{
departure_city = line;
}
else if (fid == 1) // departure time
{
departure_month = stoi(line.substr(0, 2));
departure_day = stoi(line.substr(3, 5));
departure_hour = stoi(line.substr(6, 8));
departure_min = stoi(line.substr(9, 11));
if (line.substr(9,11).at(0) == '0')
departure_time = departure_hour * 100 + departure_min;
else
departure_time = departure_hour * 100 + departure_min;
//departure_time = departure_hour * 100 + departure_min * 10;
}
else if (fid == 2) // departure time zone
{
char sign = line.at(0);
int idx = line.find(':');
departure_tz_hr = stoi(line.substr(1, idx));
departure_tz_min = stoi(line.substr(idx + 1, line.length()));
if (line.substr(idx + 1).length() == 2)
departure_tz = departure_tz_hr * 100 + departure_tz_min;
else
departure_tz = departure_tz_hr * 100 + departure_tz_min * 10;
if (sign == '-')
departure_tz = -departure_tz;
}
else if (fid == 3)
destination_city = line;
else if (fid == 4)
{
char sign = line.at(0);
int idx = line.find(':');
destination_tz_hr = stoi(line.substr(1, idx));
destination_tz_min = stoi(line.substr(idx + 1));
if(line.substr(idx + 1).length() == 2)
destination_tz = destination_tz_hr * 100 + destination_tz_min;
else
destination_tz = destination_tz_hr * 100 + destination_tz_min*10;
if (sign == '-')
destination_tz = -destination_tz;
}
else if (fid == 5)
{
char sign = line.at(0);
int idx = line.find(':');
travel_time_hr = stoi(line.substr(0, idx));
travel_time_min = stoi(line.substr(idx + 1, line.length()));
if (line.substr(idx + 1).length() == 2)
travel_time = travel_time_hr * 100 + travel_time_min;
else
travel_time = travel_time_hr * 100 + travel_time_min*10;
}
fid++;
}
// Print info read
/*
cout << "Departure: " << departure_city << endl;
cout << "Departure Time: " << departure_month << " " << departure_day << " " << departure_time << endl;
cout << "Departure Timezone: " << departure_tz << endl;
cout << "Destination: " << destination_city << endl;
cout << "Destination Timezone: " << destination_tz << endl;
cout << "Travel Time: " << travel_time << endl << endl;
*/
cout << endl;
cout << "Data Set " << (i + 1) << ":" << endl;
cout << "Departs " << departure_city << " ";
if(departure_month < 10)
cout << "0" << departure_month << " " << departure_day << " ";
else
cout << departure_month << " " << departure_day << " ";
if (departure_hour < 10)
cout << "0" << departure_hour << ":";
else
cout << departure_hour << ":";
if (departure_min < 10)
cout << "0" << departure_min << endl;
else
cout << departure_hour << endl;
// Now calculate
// take departure time and convert to UTC+00
int departure_UTC = departure_time - departure_tz;
// calculate arrival time
int arrival_UTC = departure_UTC + travel_time;
// now convert to the destination timezone
int arrival_time = arrival_UTC + destination_tz;
int days = 0;
while (arrival_time > 2359)
{
arrival_time -= 2400;
days++;
}
int arrival_hour = arrival_time / 100;
int arrival_min = arrival_time - arrival_hour * 100;
while (arrival_min > 59)
{
arrival_min -= 60;
arrival_hour += 1;
}
cout << "Arrives " << destination_city << " ";
if (arrival_hour < 10)
cout << "0" << arrival_hour << ":";
else
cout << arrival_hour << ":";
if (arrival_min< 10)
cout << "0" << arrival_min << " ";
else
cout << arrival_min << " ";
if (days == 1)
cout << "following day" << endl;
else if (days == 0)
cout << "same day" << endl;
else
cout << days << " days after" << endl;
}
file.close();
}
PROBLEM C
#include <iostream>
#include "Deck.h"
#include "Hand.h"
#include <time.h>
using namespace std;
int main()
{
srand(time(NULL));
Deck deck; // creates deck
deck.shuffle();
Card card = deck.pop();
cout << card << endl;
// start game
bool playing = true;
bool playingRound = false;
int roundType = 0;
double money = 1000; // initial money
string playerName; // store player name here
char input;
double bet;
cout << "Enter player name: ";
getline(cin, playerName);
while (playing)
{
if (roundType == 0)
{
// ask if player wants to play demo or game
cout << "Do you wish to play in (e)-Demo or (g)-Game mode? ";
cin >> input;
if (input == 'g' || input == 'G') // game mode
{
// display amount
roundType = 1;
playingRound = true;
}
}
else if (roundType == 1) // game mode
{
// display amount
cout << playerName << ", you have $" << money << " dollars." << endl;
cout << "How much you want to bet? ";
cin >> bet;
cout << endl;
if (bet >= 10 && bet <= money && bet <= 1000)
{
playingRound = true;
// create player hand and dealers hand
Hand dealer;
// Add one card face down
Card c = deck.pop();
dealer.add(c);
// add one card face up
c = deck.pop();
c.showFace();
dealer.add(c);
// take 3 cards from deck and add them to players hand
Hand player;
for (int i = 0; i < 2; i++)
{
c = deck.pop();
c.showFace();
player.add(c);
}
// Now, start round
while (playingRound)
{
cout << "Dealer's cards: " << dealer << endl << endl;
cout << "Your cards: " << player << endl;
// ask for next step
cout << "(H)-Hit, (S)-Stand (Q)-Quit: ";
cin >> input;
dealer.showAll();
if (input == 'h' || input == 'H') // hit
{
// deal a new card to player
c = deck.pop();
c.showFace();
player.add(c);
if (player.getValue() == 21) // player got 21
{
cout << "Your cards: " << player << endl << endl;
cout << "Dealer's cards: " << dealer << endl << endl;
while (dealer.getValue() < 17)
{
Card c = deck.pop();
c.showFace();
dealer.add(c);
cout << "Dealer drew: [" << dealer.getValue() << "] " << c << endl;
}
if (dealer.getValue() == 21) // it's a tie
{
cout << "It's a tie!" << endl;
}
else if (dealer.getValue() < 21 || dealer.getValue() > 21) // player wins
{
cout << "You won!";
double k = 1.0;
if (player.getHandCount() == 2) // if player won with a 2-cards hand, it's because the hand is blackjack
k = 1.5;
money += bet;
}
playingRound = false;
}
else if (player.getValue() > 21)
{
cout << "Your cards: " << player << endl << endl;
cout << "Dealer's cards: " << dealer << endl << endl;
while (dealer.getValue() < 17)
{
Card c = deck.pop();
c.showFace();
dealer.add(c);
cout << "Delaer drew: [" << dealer.getValue() << "] " << c << endl;
}
if (dealer.getValue() <= 21) // dealer wins
{
cout << "Dealer wins" << endl;
money -= bet;
}
else if (dealer.getValue() > player.getValue()) // player wins
{
cout << "You won!" << endl;
money += bet;
}
else if (dealer.getValue() == player.getValue()) // tie
{
cout << "It's a tie!" << endl;
}
playingRound = false;
}
// if the dealer's hand is less than 17, then take a new card
if (dealer.getValue() < 17)
{
c = deck.pop();
dealer.add(c);
}
}
else if (input == 's' || input == 'S') // // stand
{
while (dealer.getValue() < 17)
{
Card c = deck.pop();
c.showFace();
dealer.add(c);
cout << "Delaer drew: [" << dealer.getValue() << "] " << c << endl;
}
if (dealer.getValue() > 21 || dealer.getValue() < player.getValue()) // dealer wins
{
cout << "You won!" << endl;
money += bet;
}
else if (dealer.getValue() > player.getValue()) // dealer wins
{
cout << "Dealer wins" << endl;
money -= bet;
}
else // dealer's hand is equal to player's hand
{
cout << "It's a tie!" << endl;
}
playingRound = false;
}
else if (input == 'q' || input == 'Q') // quit
{
// player automatically loses
cout << "You lost!" << endl;
playingRound = false;
}
}
}
else
cout << "You must place a bet between $10 and $1000 or less than the available money." << endl;
}
// ask if player wants to continue
if (!playingRound)
{
cout << "Do you want to continue? (Y/N): ";
cin >> input;
if (input == 'n' || input == 'N' || input == 'y' || input == 'Y')
{
if (input == 'n' || input == 'N')
{
playing = false;
cout << "Thanks for playing!" << endl;
}
}
}
}
}