|
Насчет задачи про монеты, я обещал опубликовать код кодера/декодера для своего решения. Код на С++, можно для быстрой проверки засунуть в любой онлайн-компилятор.
#include <iostream>
#include <random>
#include <limits>
#include <cassert>
namespace {
// decoder for 2x2 problem
inline uint8_t decode2x2(uint8_t layout)
{
return (layout >> 2 ^ layout) & 2 | ((layout >> 1 ^ layout) & 4) >> 2;
}
// helper function based on the truth table of the flip bit value given
// the default encoded value and the target 2-bit value to be encoded
inline uint8_t findFlip2x2Helper(uint8_t x)
{
return static_cast<uint8_t>(x == 0 || x == 2 || x == 5 || x == 7) << 1
| static_cast<uint8_t>(x == 0 || x == 1 || x == 4 || x == 5);
}
// returns position of the bit to be flipped in 2x2 (i.e. 4-bit) problem
inline uint8_t findFlipBit2x2(uint8_t oddity, uint8_t magic_bit)
{
oddity = decode2x2(oddity) << 2 | magic_bit;
oddity = findFlip2x2Helper(oddity & 0xF) | findFlip2x2Helper(~oddity & 0xF);
assert(oddity <= 3);
return oddity;
}
// returns 4-bit oddity for the given 8x8 problem
inline uint8_t calculateOddity8x8(uint64_t layout)
{
layout ^= layout >> 8;
layout ^= layout >> 16;
layout ^= layout >> 2;
layout ^= layout >> 1;
uint8_t oddity{ 0 };
oddity |= static_cast<uint8_t>((layout & 0x1000000000) >> 33);
oddity |= static_cast<uint8_t>((layout & 0x100000000) >> 30);
oddity |= static_cast<uint8_t>((layout & 0x10) >> 3);
oddity |= static_cast<uint8_t>(layout & 0x1);
assert(oddity <= 0xF);
return oddity;
}
// returns 4-bit oddity for the given 4x4 problem
inline uint8_t calculateOddity4x4(uint16_t layout)
{
layout ^= layout >> 4;
layout ^= layout >> 1;
uint8_t oddity{ 0 };
oddity |= static_cast<uint8_t>((layout & 0x400) >> 7);
oddity |= static_cast<uint8_t>((layout & 0x100) >> 6);
oddity |= static_cast<uint8_t>((layout & 0x4) >> 1);
oddity |= static_cast<uint8_t>(layout & 0x1);
assert(oddity <= 0xF);
return oddity;
}
// downscales 8x8 problem to 4x4 problem by XOR-ing 4x4 blocks of the 8x8 problem
inline uint16_t downscaleXOR8x8To4x4(uint64_t layout)
{
layout ^= layout >> 32;
layout ^= layout >> 4;
layout = (layout & 0xF000000) >> 12 | (layout & 0xF0000) >> 8 | (layout & 0xF00) >> 4 | (layout & 0xF);
return static_cast<uint16_t>(layout);
}
inline uint8_t downscaleXOR4x4To2x2(uint16_t layout)
{
layout ^= layout >> 8;
layout ^= layout >> 2;
layout = (layout & 0x30) >> 2 | (layout & 0x3);
return static_cast<uint8_t>(layout);
}
uint64_t encode(uint64_t layout, int mc_r, int mc_c)
{
uint8_t magic_bit = mc_r << 3 | mc_c;
uint8_t flip_bit{ 0 };
uint8_t oddity = calculateOddity8x8(layout);
uint8_t fb = findFlipBit2x2(oddity, (magic_bit & 0x20) >> 4 | (magic_bit & 0x4) >> 2);
flip_bit |= (fb & 0x2) << 4;
flip_bit |= (fb & 0x1) << 2;
uint16_t layout_4x4 = downscaleXOR8x8To4x4(layout);
oddity = calculateOddity4x4(layout_4x4);
fb = findFlipBit2x2(oddity, (magic_bit & 0x10) >> 3 | (magic_bit & 0x2) >> 1);
flip_bit |= (fb & 0x2) << 3;
flip_bit |= (fb & 0x1) << 1;
uint8_t layout_2x2 = downscaleXOR4x4To2x2(layout_4x4);
fb = findFlipBit2x2(layout_2x2, (magic_bit & 0x8) >> 2 | (magic_bit & 0x1));
flip_bit |= (fb & 0x2) << 2;
flip_bit |= fb & 0x1;
return layout ^ 0x1ULL << (63 - flip_bit);
}
uint8_t decode(uint64_t coded_sequence)
{
uint8_t coded_value{ 0 };
uint8_t oddity = calculateOddity8x8(coded_sequence);
uint8_t decoded_sequence = decode2x2(oddity);
coded_value |= (decoded_sequence & 0x2) << 4;
coded_value |= (decoded_sequence & 0x1) << 2;
uint16_t coded_sequence_4x4 = downscaleXOR8x8To4x4(coded_sequence );
oddity = calculateOddity4x4(coded_sequence_4 x4);
decoded_sequence = decode2x2(oddity);
coded_value |= (decoded_sequence & 0x2) << 3;
coded_value |= (decoded_sequence & 0x1) << 1;
uint8_t coded_sequence_2x2 = downscaleXOR4x4To2x2(coded_sequence _4x4);
decoded_sequence = decode2x2(coded_sequence_2x2);
coded_value |= (decoded_sequence & 0x2) << 2;
coded_value |= decoded_sequence & 0x1;
return coded_value;
}
}
int main()
{
std::default_random_engine generator{};
std::uniform_int_distribution<uint64_t> distribution{ 0, std::numeric_limits<uint64_t>::max() };
uint64_t layout{ distribution(generator) };
std::cout << "The initial layout is " << layout << std::endl;
int mc_r, mc_c;
{
std::cout << "Enter the row (1-based) where the magic coin is located: ";
std::cin >> mc_r; --mc_r;
std::cout << "Enter the column (1-based) where the magic coin is located: ";
std::cin >> mc_c; --mc_c;
}
uint64_t coded_sequence = encode(layout, mc_r, mc_c);
uint8_t guess = decode(coded_sequence);
std::cout << "I think the magic coin was in position (" << (guess >> 3) + 1 << ", " << (guess & 7) + 1 << ")" << std::endl;
}
|
