81 lines
2.0 KiB
C++
81 lines
2.0 KiB
C++
#include <fstream>
|
|
#include <iostream>
|
|
#include <sstream>
|
|
#include <vector>
|
|
|
|
std::vector<int> getCrabs(const std::string &file_name) {
|
|
std::vector<int> crabs;
|
|
|
|
std::ifstream file(file_name);
|
|
std::string str;
|
|
std::getline(file, str);
|
|
int tmp{};
|
|
char tmp_char{};
|
|
std::stringstream ss(str);
|
|
while (ss >> tmp) {
|
|
if (tmp >= crabs.size()) {
|
|
crabs.resize(tmp + 1);
|
|
}
|
|
crabs[tmp] += 1;
|
|
ss >> tmp_char;
|
|
}
|
|
return crabs;
|
|
}
|
|
|
|
uint64_t diff(uint64_t a, uint64_t b) {
|
|
if (a < b) {
|
|
return b - a;
|
|
}
|
|
return a - b;
|
|
}
|
|
|
|
static std::vector<uint64_t> fuel_cost{ 0 };
|
|
|
|
uint64_t increasingFuel(uint64_t a, uint64_t b) {
|
|
auto difference = diff(a, b);
|
|
while (fuel_cost.size() <= difference) {
|
|
fuel_cost.push_back(fuel_cost.back() + fuel_cost.size());
|
|
}
|
|
return fuel_cost[difference];
|
|
}
|
|
|
|
uint64_t leastFuelCrabs(const std::vector<int> &crabs, bool increasing_fuel) {
|
|
uint64_t least = -1;
|
|
for (uint64_t i = 0; i < crabs.size(); i++) {
|
|
uint64_t fuel = 0;
|
|
for (uint64_t j = 0; j < crabs.size(); j++) {
|
|
if (!increasing_fuel) {
|
|
fuel += diff(j, i) * crabs[j];
|
|
} else {
|
|
fuel += increasingFuel(j, i) * crabs[j];
|
|
}
|
|
}
|
|
if (fuel < least) {
|
|
least = fuel;
|
|
}
|
|
}
|
|
return least;
|
|
}
|
|
|
|
uint64_t part1(const std::vector<int> &crabs) {
|
|
return leastFuelCrabs(crabs, false);
|
|
}
|
|
|
|
uint64_t part2(const std::vector<int> &crabs) {
|
|
return leastFuelCrabs(crabs, true);
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
if (argc < 2) {
|
|
std::cerr << "You must provide input file!" << std::endl;
|
|
return 1;
|
|
}
|
|
auto crabs = getCrabs(argv[1]);
|
|
std::cout << "The least fuel crabs have to use is \033[91;1m"
|
|
<< part1(crabs) << "\033[0m." << std::endl;
|
|
std::cout << "The least fuel crabs have to use with correctly computed "
|
|
"consumption is \033[91;1m"
|
|
<< part2(crabs) << "\033[0m." << std::endl;
|
|
return 0;
|
|
}
|