Pizza Problem

main.cpp

///! Version: C++17

#include <algorithm> // for std::reverse()
#include <cstdint> // int64_t
#include <filesystem> // std::filesystem::path
#include <fstream> // std::ifstream, std::ofstream
#include <iostream> // the usual console I/O stuff
#include <sstream> // istringstream for parsing a string, see split() below
#include <string> // std::getline(), std::stol()
#include <vector>

// Borrowed from https://www.fluentcpp.com/2017/04/21/how-to-split-a-string-in-c/
std::vector<std::string> split(const std::string& s, char delimiter) {
	std::vector<std::string> tokens;
	std::string token;
	std::istringstream tokenStream(s);
	while (std::getline(tokenStream, token, delimiter)) {
		tokens.push_back(token);
	}
	return tokens;
}

int main() {
	///////////////////////////////////////////////////////////////////////////
	//** SETUP PHASE                                                       **//
	///////////////////////////////////////////////////////////////////////////
	
	// Set this alias as a shorthand
	namespace fs = std::filesystem;
	
	std::ifstream input_file;
	std::ofstream output_file;
	
	/**
	 * Supposing a file structure like:
	 *  MyProject (directory):
	 *  	- main.cpp (this file)
	 *  	- input.txt
	 *  	- output.txt
	 */
	fs::path input_path("input.txt");
	fs::path output_path("output.txt");
	
	// The maximum number of slices of pizza to order
	int64_t max_num_slices = 0;
	// The number of different types of pizza
	int64_t num_of_types = 0;
	
	// List of the number of slices in each type of pizza
	// Predicate: length of this vector must be equal to num_of_types!
	std::vector<int64_t> num_of_slices_per_type;
	
	// This is where I will hold input lines before parsing them into their true values
	std::vector<std::string> input_lines;
	
	///////////////////////////////////////////////////////////////////////////
	//** INPUT PHASE                                                       **//
	///////////////////////////////////////////////////////////////////////////
	
	input_file.open(input_path);
	
	if (input_file.is_open()) {
		std::string string_buffer;
		
		while (std::getline(input_file, string_buffer)) {
			if (string_buffer.empty()) {
				continue;
			}
			input_lines.push_back(string_buffer);
		}
		
		// input_lines now holds the contents of the input file.
		// Now, I have to parse the values in the strings.
		
		// Split the first line on spaces.
		std::vector<std::string> first_line = split(input_lines[0], ' ');
		
		// Convert the strings into int64's.
		max_num_slices = std::stol(first_line[0]);
		num_of_types = std::stol(first_line[1]);
		
		// Split the second line on spaces.
		std::vector<std::string> second_line = split(input_lines[1], ' ');
		
		// Convert the strings into int64's.
		for (const std::string& str : second_line) {
			num_of_slices_per_type.push_back(std::stol(str));
		}
		
		// Print out the values to be sure we got it right.
		std::cout << "INPUT VALUES:\n"
		          << max_num_slices << ' ' << num_of_types
		          << std::endl;
		for (const auto& val : num_of_slices_per_type) {
			std::cout << val << ' ';
		}
		std::cout << '\n' << "END INPUT VALUES" << std::endl;
		
		// Close the input file. We don't need it anymore.
		input_file.close();
	} else {
		std::cerr << "Something went wrong when I tried to open the input file!\n";
	}
	
	// Check the predicate for the vector. My logic below depends
	// on the predicate being true; if there is a mismatch here; then:
	// if num_of_types > num_of_slices_per_type.size()
	//	-> the for-loop below immediately triggers undefined behaviour
	//	   in the form of an out-of-bounds access.
	// if num_of_types < num_of_slices_per_type.size()
	// -> the for-loop below succeeds, but the output is incorrect.
	assert(num_of_slices_per_type.size() == num_of_types &&
		"The number of slices per type does not match the number of types of pizza!");
	
	///////////////////////////////////////////////////////////////////////////
	//** PROCESSING PHASE                                                  **//
	///////////////////////////////////////////////////////////////////////////
	
	// Iterate backwards through the list.
	// If the current number of pizza slices plus
	// the number of pizza slices per the current type of pizza
	// is less than the maximum number of pizza slices,
	// add the number of pizza slices per the current type of pizza
	// to the current number of pizza slices,
	// and record the index of the type of pizza and how many
	// types of pizza meet this criteria.
	int64_t current_num_slices = 0;
	int64_t counter = 0;
	std::string accumulator;
	for (int64_t i = num_of_types - 1; i >= 0; i--) {
		if (current_num_slices + num_of_slices_per_type[i] <= max_num_slices) {
			accumulator += std::to_string(i) + " ";
			counter++;
			current_num_slices += num_of_slices_per_type[i];
		}
	}
	
	// Counter will be the first line of the output.
	
	// Remove the final space at the end of the string
	accumulator.pop_back();
	
	// Reverse the second line of the output so that the indexes
	// are in ascending order like the input.
	std::reverse(accumulator.begin(), accumulator.end());
	
	///////////////////////////////////////////////////////////////////////////
	//** OUTPUT PHASE                                                      **//
	///////////////////////////////////////////////////////////////////////////
	
	std::cout << "OUTPUT VALUES:\n"
	          << counter << '\n'
	          << accumulator << '\n'
	          << "END OUTPUT VALUES"
	          << std::endl;
	
	// Open the output file and overwrite any existing data.
	output_file.open(output_path, std::ios::trunc);
	
	if (output_file.is_open()) {
		output_file << counter << std::endl;
		output_file << accumulator << std::endl;
		
		output_file.close();
	} else {
		std::cerr << "Something went wrong when I tried to open the output file!\n";
	}
	
	return 0;
}