Daily: Cutting a Wall | C++

December 19th, 2021 02:10:51 PM

					
/* Good morning! Here's your coding interview problem for today. This problem was asked by LinkedIn. A wall consists of several rows of bricks of various integer lengths and uniform height. Your goal is to find a vertical line going from the top to the bottom of the wall that cuts through the fewest number of bricks. If the line goes through the edge between two bricks, this does not count as a cut. For example, suppose the input is as follows, where values in each row represent the lengths of bricks in that row: [[3, 5, 1, 1], [2, 3, 3, 2], [5, 5], [4, 4, 2], [1, 3, 3, 3], [1, 1, 6, 1, 1]] The best we can we do here is to draw a line after the eighth brick, which will only require cutting through the bricks in the third and fifth row. Given an input consisting of brick lengths for each row such as the one above, return the fewest number of bricks that must be cut to create a vertical line. AUTHORS NOTE: Makes following assumptions: - Each row is same length - Data is in file called "data.dat" and formatted in space-separated rows - The cuts at the beginning and end of the wall are not solutions This requires the following file named data.dat that is a space separated file, or similar formatted file: ----START FILE---- 3 5 1 1 2 3 3 2 5 5 4 4 2 1 3 3 3 1 1 6 1 1 ----END FILE---- */ #include <algorithm> #include <iostream> #include <fstream> #include <map> #include <sstream> #include <string> #include <vector> using namespace std; int main() { vector<vector<int>> wall; ifstream in; in.open("data.dat"); if(!in.good()) { cout << "ERROR: File failed to open properly.\n"; } /* Get input from space separated file */ string line; while(!in.eof()) { getline(in, line); int i; vector<int> currv; stringstream strs(line); while(strs >> i) currv.push_back(i); wall.push_back(currv); } /* Convert each value from "length of brick" to "position at end of brick" */ for(int y = 0; y < wall.size(); y++) { wall.at(y).pop_back(); //Delet last val for(int x = 1; x < wall.at(y).size(); x++) //Skip the first bc data doesn't need change wall.at(y).at(x) += wall.at(y).at(x-1); } /* Check output. COMMENT OUT */ // for(auto row : wall) // { // for(int pos : row) // cout << pos << " "; // cout << endl; // } /* Determine which ending position is most common, and cut there */ //Exclude final position, which will be the size of the wall int mode = -1; int amt = -1; vector<int> tried; for(auto row : wall) { for(int pos : row) //For each pos in the wall { //Guard. If pos is contained in the list, skip pos if(find(tried.begin(), tried.end(), pos) != tried.end()) continue; tried.push_back(pos); /* Cycle through each row to see if it contains the pos */ int curramt = 0; for(auto currrow : wall) { if( find( currrow.begin(), currrow.end(), pos ) != currrow.end() ) curramt++; } //cout << pos << " " << curramt << endl; if(curramt > amt) { amt = curramt; mode = pos; } } } cout << "Please cut at position " << mode << endl; cout << "This will cut through " << (wall.size() - amt) << " bricks." << endl; return 0; }

Featured Posts