// Řešení všech úloh na hledání kolizí z úlohy 38-3-S

#include <stdio.h>
#include <stdint.h>
#include <string>
#include <unordered_map>
#include <iostream>
#include <random>
#include <cassert>

typedef unsigned int uint;
typedef uint32_t u32;
typedef uint64_t u64;

// Funkce ze zadání

u32 f(u64 x)
{
	return (x * 13043831838999645351U) >> 32;
}

u32 g(std::string x)
{
	u32 y = 1;
	for (size_t i=0; i < x.size(); i++)
		y = y * 2654289787 + x[i];
	return y;
}

// Náhodný generátor ze standardní knihovny

std::mt19937 mt(2);
std::mt19937_64 mt64(2);
std::uniform_int_distribution<u64> ui64;
std::uniform_int_distribution<uint> unice(0, 26+26+10);

// Náhodné 64-bitové číslo
static inline u64 rng64()
{
	return ui64(mt64);
}

// Náhodný znak do hezkého řetězce
static inline char rng_nice_char()
{
	uint i = unice(mt);
	if (i < 26)
		return 'A' + i;
	else if (i < 52)
		return 'a' + i - 26;
	else
		return '0' + i - 52;
}

// Náhodný hezký řetězec
std::string random_nice_string(uint len)
{
	std::string out(len, ' ');
	for (uint i=0; i < len; i++)
		out[i] = rng_nice_char();
	return out;
}

// Náhodné kolize funkce f
void f_random_collision()
{
	const int num_attempts = 50;
	u64 total_steps = 0;

	for (int attempt=0; attempt < num_attempts ; attempt++) {
		std::unordered_map<u32, u64> known;

		for (u64 i=1;; i++) {
			u64 x = rng64();
			u32 h = f(x);
			// std::cout << x << " -> " << h << std::endl;
			if (known.count(h)) {
				std::cout << "Kolize po " << i << " krocích: " << h << " (" << x << " / " << known[h] << ")\n";
				total_steps += i;
				break;
			}
			known[h] = x;
		}
	}

	std::cout << "Průměrný počet kroků: " << total_steps / num_attempts << std::endl;
}

// Hledáme x takové, že f(x) = y
u64 f_invert(u32 y)
{
	u64 attempts = 0;
	for (;;) {
		u64 x = rng64();
		u32 h = f(x);
		if (h == y) {
			std::cout << "Inverze " << y << ": " << x << " po " << attempts << " krocích.\n";
			return x;
		}
		attempts++;
		if (attempts % 1000000 == 0) {
			std::cout << attempts / 1000000 << "\r";
			std::cout.flush();
		}
	}
}

// Multikolize f heuristickou metodou
void f_multicollision()
{
	// u64 z0 = f_invert(0);
	u64 z0 = 548449283274199704;
	// u64 zm1 = f_invert(0xffffffff);
	u64 zm1 = 5239948424758888359;

	u64 x = 0;
	for (int i=0; i < 1000000; i++) {
		u32 h;
		x += z0;
		for (;;) {
			h = f(x);
			// std::cout << "\t" << x << " " << h << std::endl;
			if (h == 0)
				break;
			if (h < 0x80000000)
				x += zm1;
			else
				x += z0;
		}
		std::cout << x << "\n";
	}
}

// Multikolize f pomocí teorie čísel
void f_multicollision_fast()
{
	// Multiplikativní inverze násobitele z funkce f modulo 2^64
	u64 z = 2279388007517903639U;	// Python: pow(13043831838999645351, -1, 2**64)

	for (int i=0; i < 1000000; i++) {
		u64 x = z * i;
		u32 h = f(x);
		assert(h == 0);
		std::cout << x << "\n";
	}
}

// Náhodné kolize funkce g
std::pair<std::string, std::string> g_random_collision()
{
	std::unordered_map<u32, std::string> known;

	for (u64 i=1;; i++) {
		std::string x = random_nice_string(6);
		u32 h = g(x);
		// std::cout << x << " -> " << h << std::endl;
		if (known.count(h)) {
			std::cout << "Kolize po " << i << " krocích: " << h << " (" << x << " / " << known[h] << ")\n";
			return std::pair(x, known[h]);
		}
		known[h] = x;
	}
}

// Multikolize funkce g
void g_multicollision()
{
	auto [ z0, z1 ] = g_random_collision();

	for (uint i=0; i < 1000000; i++) {
		std::string x;
		for (uint j=0; j<20; j++)
			if (i & (1 << j))
				x += z0;
			else
				x += z1;
		u32 h = g(x);
		std::cout << x << " " << h << "\n";
	}
}

int main()
{
	// f_random_collision();
	// f_multicollision_fast();
	// g_random_collision();
	g_multicollision();
}