day4.cpp

/*
 * ============================================================================
 *
 *       Filename:  day4.cpp
 *
 *    Description:  Day 4 of Advent of Code solution
 *
 *        Version:  1.0
 *        Created:  12/4/2019 7:23:58 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  invakid404 
 *
 * ============================================================================
*/

#include <bits/stdc++.h>

#define TARGET_K 6

#define ENDL '\n'
#define RANGE(i, a, b) for(auto i = a; i <= b; ++i)

namespace {
	std::unordered_set<int> valid_passwords;

	auto recurse(int lo, int hi, int curr, int k, bool repeated) -> void {
		if(k == TARGET_K) {
			if(curr >= lo && curr <= hi) {
				valid_passwords.emplace(curr);
			}

			return;
		}

		auto last_digit = curr % 10;

		if(k + 1 == TARGET_K && !repeated) {
			auto final_val = curr * 10 + last_digit;

			recurse(lo, hi, final_val, k + 1, true);
			return;
		}

		RANGE(i, last_digit, 9) {
			auto new_val = curr * 10 + i;
			auto new_repeated = repeated || i == last_digit;

			recurse(lo, hi, new_val, k + 1, new_repeated);
		}
	}

	auto generate_passwords(int lo, int hi) -> void {
		recurse(lo, hi, 0, 0, false);
	}

	auto part_one() -> int {
		return static_cast<int>(valid_passwords.size());
	}

	auto has_two_repeated(int n) -> bool {
		std::unordered_map<int, int> digit_count;

		while(n) {
			auto d = std::div(n, 10);

			++digit_count[d.rem];
			n = d.quot;
		}

		for(auto& val : digit_count) {
			if(val.second == 2) {
				return true;
			}
		}

		return false;
	}

	auto part_two() -> int {
		auto sol = 0;

		for(auto& val : valid_passwords) {
			if(has_two_repeated(val)) {
				++sol;
			}
		}

		return sol;
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int lo, hi;
	std::cin >> lo >> hi;
	
	auto start = std::chrono::high_resolution_clock::now();

	generate_passwords(lo, hi);

	std::cout << part_one() << ENDL;
	std::cout << part_two() << ENDL;
		
	auto end = std::chrono::high_resolution_clock::now();

	std::cout << "Time elapsed: " 
		<< std::chrono::duration_cast<std::chrono::milliseconds>
			(end - start).count()
		<< ENDL;

	return 0;
}