Skip to content

Instantly share code, notes, and snippets.

@Pastor

Pastor/impl.cxx

Last active September 15, 2024 20:52
Show Gist options
  • Save Pastor/410a1cb2a599d2b6e09b156d0069425c to your computer and use it in GitHub Desktop.
Save Pastor/410a1cb2a599d2b6e09b156d0069425c to your computer and use it in GitHub Desktop.
Download ZIP
Ya numbers
Raw
impl.cxx
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <set>
struct Context {
std::map<char, int> symbols;
std::set<int> used;
int offset;
enum State {
GENERATED, DEFINED, FAILED
};
explicit Context(const int offset) : offset(offset) {
}
State next(const char ch, const int value, int *result) const {
if (symbols.contains(ch)) {
*result = symbols.at(ch);
return DEFINED;
}
for (auto k = value; k < 10; ++k) {
if (used.contains(k)) {
continue;
}
*result = k;
return GENERATED;
}
return FAILED;
}
void assign(const char ch, const int value) {
symbols[ch] = value;
used.insert(value);
}
void reset(const char ch) {
if (symbols.contains(ch)) {
used.erase(symbols.at(ch));
symbols.erase(ch);
}
}
void print(const std::string &text, const std::streamsize width) const {
for (auto x: text) {
std::cout << symbols.at(x);
}
std::cout << std::endl;
}
[[nodiscard]] auto to_number(const std::string &text) const {
std::string result;
for (auto x: text) {
if (symbols.contains(x)) {
result += std::to_string(symbols.at(x));
} else {
result += x;
}
}
return result;
}
};
bool processing(Context &in,
const std::string &x,
const std::string &y,
const std::string &z,
const int index, const bool carried) {
if (index > x.size() || index > y.size()) {
const auto max_size = std::max(x.size(), std::max(y.size(), z.size()));
const auto sX = in.to_number(x);
const auto sY = in.to_number(y);
const auto sZ = in.to_number(z);
try {
const auto nX = std::stoi(sX);
const auto nY = std::stoi(sY);
if (const auto nZ = std::stoi(sZ); nX + nY == nZ) {
return true;
}
} catch ([[maybe_unused]] const std::invalid_argument &e) {
std::vector<char> free;
for (char i = 0; i < 10; ++i) {
if (!in.used.contains(i)) {
free.push_back(i);
}
}
for (int i = 1; i <= max_size; ++i) {
char cX = -1, cY = -1, cZ = -1;
if (i <= sX.size()) {
cX = sX.at(sX.size() - i);
}
if (i <= sY.size()) {
cY = sY.at(sY.size() - i);
}
if (i <= sZ.size()) {
cZ = sZ.at(sZ.size() - i);
}
if (cX == -1) {
if (cY != -1 && !std::isdigit(cY) && cZ != -1 && !std::isdigit(cZ)) {
for (const auto value: free) {
auto mutant = value;
if (carried) {
mutant += 1;
if (mutant < 10 && !in.used.contains(mutant) && !in.used.contains(value)) {
in.assign(cY, value);
in.assign(cZ, mutant);
return true;
}
}
}
} else if (cY != -1 && !std::isdigit(cY) && cZ != -1 && std::isdigit(cZ)) {
const auto nZ = in.symbols.at(cZ);
for (const auto value: free) {
auto mutant = value;
if (carried) {
mutant += 1;
}
if (mutant < 10 && !in.used.contains(mutant) && mutant == nZ) {
in.assign(cY, value);
return true;
}
}
} else if (cY != -1 && std::isdigit(cY) && cZ != -1 && !std::isdigit(cZ)) {
auto mutant = carried ? in.symbols.at(cY) + 1 : in.symbols.at(cY);
if (!in.used.contains(mutant)) {
in.assign(cZ, mutant);
return true;
}
} else {
if (!in.used.contains(1)) {
in.assign(cZ, 1);
return true;
}
}
} else if (cY == -1) {
if (!std::isdigit(cX) && cZ != -1 && !std::isdigit(cZ)) {
for (const auto value: free) {
auto mutant = value;
if (carried) {
mutant += 1;
if (mutant < 10 && !in.used.contains(mutant) && !in.used.contains(value)) {
in.assign(cX, value);
in.assign(cZ, mutant);
return true;
}
}
}
} else if (!std::isdigit(cX) && cZ != -1 && std::isdigit(cZ)) {
const auto nZ = in.symbols.at(cZ);
for (const auto value: free) {
auto mutant = value;
if (carried) {
mutant += 1;
}
if (mutant < 10 && !in.used.contains(mutant) && mutant == nZ) {
in.assign(cX, value);
return true;
}
}
} else if (std::isdigit(cX) && cZ != -1 && !std::isdigit(cZ)) {
const auto mutant = carried ? in.symbols.at(cX) + 1 : in.symbols.at(cX);
if (!in.used.contains(mutant)) {
in.assign(cZ, mutant);
return true;
}
} else {
if (!in.used.contains(1)) {
in.assign(cZ, 1);
return true;
}
}
} else if (cZ == -1) {
if (!in.used.contains(1)) {
in.assign(cZ, 1);
return true;
}
}
}
}
return false;
}
auto context = in;
int nX, nY, nZ;
const auto xSymbol = x.at(x.size() - index);
const auto ySymbol = y.at(y.size() - index);
const auto zSymbol = z.at(z.size() - index);
for (nX = 0; nX < 10; ++nX) {
const auto xState = context.next(xSymbol, nX, &nX);
if (xState == Context::FAILED) {
continue;
}
context.assign(xSymbol, nX);
for (nY = 0; nY < 10; ++nY) {
const auto yState = context.next(ySymbol, nY, &nY);
if (yState == Context::FAILED) {
continue;
}
context.assign(ySymbol, nY);
for (nZ = 0; nZ < 10; ++nZ) {
const auto zState = context.next(zSymbol, nZ, &nZ);
if (zState == Context::FAILED) {
continue;
}
context.assign(zSymbol, nZ);
auto summary = nX + nY;
auto need_carried = carried;
if (summary > 10) {
summary = summary % 10;
need_carried = true;
}
if (carried && summary + 1 == nZ) {
if (processing(context, x, y, z, index + 1, summary + 1 > 10)) {
in = context;
return true;
}
} else if (summary == nZ) {
if (processing(context, x, y, z, index + 1, need_carried)) {
in = context;
return true;
}
} else {
//TODO: Next
}
if (zState == Context::GENERATED) {
context.reset(zSymbol);
} else {
break;
}
}
if (yState == Context::GENERATED) {
context.reset(ySymbol);
} else {
break;
}
}
if (xState == Context::GENERATED) {
context.reset(xSymbol);
} else {
break;
}
}
return false;
}
void start(const std::string &x, const std::string &y, const std::string &z) {
Context context(0);
const std::streamsize max_size = static_cast<std::streamsize>(std::max(x.size(), y.size()));
const auto ret = processing(context, x, y, z, 1, false);
std::cout.width(max_size);
std::cout << x << std::endl << y << std::endl << z << std::endl;
if (ret) {
context.print(x, max_size);
context.print(y, max_size);
context.print(z, max_size);
} else {
std::cout << "UNSOLVABLE" << std::endl;
}
}
int main() {
start("x", "y", "z");
start("win", "lose", "game");
start("love", "hate", "feel");
start("four", "seven", "eight");
start("a", "b", "a");
start("odin", "odin", "mnogo");
}
Raw
impl.rs
use crate::Next::{Defined, Failed, Generated};
use std::cmp::max;
use std::collections::HashMap;
use std::fmt::{Display, Formatter};
type Char = char;
type Digit = u8;
type ProcessingResult = Result<Context, ()>;
#[derive(Clone, Debug, Default, PartialEq)]
struct Context {
symbols: HashMap<Char, Digit>,
}
#[derive(Clone, Debug, PartialEq)]
enum Next {
Generated(Digit),
Defined(Digit),
Failed,
}
fn at(text: &String, index: usize) -> Option<Char> {
if text.len() < index {
return None;
}
text.chars().nth(text.len() - index)
}
impl Context {
fn next(&self, ch: Char, val: Digit) -> Next {
if let Some(val) = self.symbols.get(&ch) {
return Defined(*val);
} else {
for num in val..10 {
if self.used_num(num) {
continue;
}
return Generated(num);
}
}
Failed
}
fn used_num(&self, num: Digit) -> bool {
self.symbols.values().any(|&x| x == num)
}
fn register(&mut self, ch: Char, val: Digit) {
self.symbols.insert(ch, val);
}
fn unregister(&mut self, ch: Char) {
self.symbols.remove(&ch);
}
fn print(&self, text: &str) {
println!("{}", self.to_number(text));
}
fn to_number(&self, text: &str) -> String {
let mut result = String::new();
text.chars().for_each(|ch| {
if let Some(num) = self.symbols.get(&ch) {
result.push_str(&num.to_string());
} else {
result.push(ch);
}
});
result
}
fn free_nums(&self) -> Vec<Digit> {
let mut result = Vec::new();
for x in 0..10 {
if self.used_num(x) {
continue;
}
result.push(x);
}
result
}
fn processing(context: Context, x: &str, y: &str, z: &str, index: usize, carried: bool) -> ProcessingResult {
if index > x.len() || index > y.len() {
let sx = context.to_number(x);
let sy = context.to_number(y);
let sz = context.to_number(z);
if let Ok(nx) = sx.parse::<Digit>() {
if let Ok(ny) = sy.parse::<Digit>() {
if let Ok(nz) = sz.parse::<Digit>() {
if nx + ny == nz {
return Ok(context);
}
return Err(());
}
}
}
let mut context = context;
let free = context.free_nums();
let max_size = max(x.len(), max(y.len(), z.len()));
for i in 1..=max_size {
let cx = at(&sx, i);
let cy = at(&sy, i);
let cz = at(&sz, i);
match (cx, cy, cz) {
(None, Some(y), Some(z)) if !y.is_digit(10) && !z.is_digit(10) => {
for val in free.clone() {
let mut mutant = val;
if carried {
mutant += 1;
if mutant < 10 && !context.used_num(mutant) && !context.used_num(val) {
context.register(y, val);
context.register(z, mutant);
return Ok(context);
}
}
}
}
(None, Some(y), Some(z)) if !y.is_digit(10) && z.is_digit(10) => {
let nz = context.at(z);
for val in free.clone() {
let mut mutant = val;
if carried {
mutant += 1;
}
if mutant < 10 && !context.used_num(mutant) && mutant == nz {
context.register(y, val);
return Ok(context);
}
}
}
(None, Some(y), Some(z)) if y.is_digit(10) && !z.is_digit(10) => {
let mutant = if carried {
context.at(y) + 1
} else {
context.at(y)
};
if !context.used_num(mutant) {
context.register(z, mutant);
return Ok(context);
}
}
(Some(x), None, Some(z)) if !x.is_digit(10) && !z.is_digit(10) => {
for val in free.clone() {
let mut mutant = val;
if carried {
mutant += 1;
if mutant < 10 && !context.used_num(mutant) && !context.used_num(val) {
context.register(x, val);
context.register(z, mutant);
return Ok(context);
}
}
}
}
(Some(x), None, Some(z)) if !x.is_digit(10) && z.is_digit(10) => {
let nz = context.at(z);
for val in free.clone() {
let mut mutant = val;
if carried {
mutant += 1;
}
if mutant < 10 && !context.used_num(mutant) && mutant == nz {
context.register(x, val);
return Ok(context);
}
}
}
(Some(x), None, Some(z)) if x.is_digit(10) && !z.is_digit(10) => {
let mutant = if carried {
context.at(x) + 1
} else {
context.at(x)
};
if !context.used_num(mutant) {
context.register(z, mutant);
return Ok(context);
}
}
(_, _, Some(z)) if !z.is_digit(10) => {
if !context.used_num(1) {
context.register(z, 1);
return Ok(context);
}
}
(_, _, _) => {
continue;
}
}
}
return Err(());
}
let mut context = context.clone();
let x_symbol = x.as_bytes()[x.len() - index] as char;
let y_symbol = y.as_bytes()[y.len() - index] as char;
let z_symbol = z.as_bytes()[z.len() - index] as char;
for nx in 0..10 {
let x_state = context.next(x_symbol, nx);
let nx = if let Generated(n) = x_state {
n
} else if let Defined(n) = x_state {
n
} else {
continue;
};
context.register(x_symbol, nx);
for ny in 0..10 {
let y_state = context.next(y_symbol, ny);
let ny = if let Generated(n) = y_state {
n
} else if let Defined(n) = y_state {
n
} else {
continue;
};
context.register(y_symbol, ny);
for nz in 0..10 {
let z_state = context.next(z_symbol, nz);
if z_state == Failed {
continue;
}
let nz = if let Generated(n) = z_state {
n
} else if let Defined(n) = z_state {
n
} else {
continue;
};
context.register(z_symbol, nz);
let mut sum = nx + ny;
let mut need_carried = carried;
if sum > 10 {
sum = sum % 10;
need_carried = true;
}
if carried && sum + 1 == nz {
if let Ok(ctx) = Self::processing(context.clone(), &x, &y, &z, index + 1, sum + 1 > 10) {
return Ok(ctx);
}
} else if sum == nz {
if let Ok(ctx) = Self::processing(context.clone(), &x, &y, &z, index + 1, need_carried) {
return Ok(ctx);
}
}
if let Generated(_) = z_state {
context.unregister(z_symbol);
} else {
break;
}
}
if let Generated(_) = y_state {
context.unregister(y_symbol);
} else {
break;
}
}
if let Generated(_) = x_state {
context.unregister(x_symbol);
} else {
break;
}
}
Err(())
}
fn start(x: &str, y: &str, z: &str) {
let context: Context = Context::default();
let result = Self::processing(context, x, y, z, 1, false);
println!("{}", x);
println!("{}", y);
println!("{}", z);
if let Ok(ctx) = result {
ctx.print(x);
ctx.print(y);
ctx.print(z);
} else {
println!("UNSOLVABLE")
}
}
fn at(&self, ch: Char) -> Digit {
self.symbols.get(&ch).copied().unwrap()
}
}
impl Display for Context {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
self.symbols.iter().for_each(|(k, v)| {
f.write_fmt(format_args!("{} = {}, ", k, v)).unwrap();
});
Ok(())
}
}
fn main() {
Context::start("x", "y", "z");
Context::start("win", "lose", "game");
Context::start("love", "hate", "feel");
Context::start("four", "seven", "eight");
Context::start("a", "b", "a");
Context::start("odin", "odin", "mnogo");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment