| Bytes | Lang | Time | Link |
|---|---|---|---|
| 003 | Rust | 250131T131532Z | 138 Aspe |
| 005 | Python 3 | 221023T192554Z | arrmansa |
| nan | C++ | 220601T204041Z | benrg |
| 003 | Python3 | 220529T194154Z | Ajax1234 |
Rust, ~0.3ms
Rust port of @benrg's C++ answer.
/// A Rust rewrite of the given C++ alphametic puzzle solver.
///
/// Usage:
/// cargo run -- "CODE+GOLF=GREAT"
/// You can pass multiple puzzles as arguments.
use std::env;
use std::time::Instant;
//use std::cmp::Ordering;
// Digits
type Digit = i32;
const BASE: Digit = 10;
// Letters
type Letter = i32;
const ALPHABET_SIZE: usize = 26;
// Terms
type Term = i32;
/// Parse a character into a letter index (0 for 'A', 1 for 'B', etc.).
fn parse_letter(c: char) -> Letter {
(c as u8 - b'A') as Letter
}
/// Returns true if the character is a capital English letter ('A'..='Z').
fn is_letter(c: char) -> bool {
let index = c as u8;
index >= b'A' && index <= b'Z'
}
/// Convert a digit to a character (0 -> '0', 1 -> '1', etc.).
fn format_digit(d: Digit) -> char {
(b'0' + d as u8) as char
}
/// Convert a term to its absolute value.
fn term_abs(x: Term) -> Term {
if x < 0 { -x } else { x }
}
/// Result of parsing a formula.
struct ParseResult {
coeffs: [Term; ALPHABET_SIZE],
present_mask: u32,
leading_mask: u32,
}
/// Parse a formula of the form "BA+BB=CCC" into coefficients.
/// This effectively transforms something like "BA + BB - CCC = 0".
///
/// Returns:
/// Some(ParseResult) on success, None on parse failure.
fn parse_formula(formula: &str) -> Option<ParseResult> {
// We'll create an array of 26 coefficients initialized to 0.
let mut coeffs = [0; ALPHABET_SIZE];
let mut present_mask: u32 = 0;
let mut leading_mask: u32 = 0;
// We track current side (+1 for left, -1 for right).
let mut side: Term = 1;
// We track place (multiplier for next letter).
let mut place: Term = side;
// We'll iterate with an index, but we need to step over letters carefully
// then interpret +, -, =, etc.
let mut chars = formula.chars().peekable();
'outer: loop {
// Step 1: read as many letters as possible:
let mut letter_seq = Vec::new();
while chars.peek().map_or(false, |c| is_letter(*c)) {
letter_seq.push(chars.next().unwrap());
}
// If we read one or more letters, mark the first as leading:
if !letter_seq.is_empty() {
// The first letter in this sequence cannot be zero if it's leading.
let first_letter = letter_seq[0];
leading_mask |= 1 << parse_letter(first_letter);
// Process collected letters from right to left.
// For example, "BA" => 'A' first, then 'B'.
// Because the place value is assigned from right to left:
// "BA" means A has place 1, B has place 10, etc.
for c in letter_seq.iter().rev() {
let letter_index = parse_letter(*c) as usize;
coeffs[letter_index] += place;
present_mask |= 1 << letter_index;
place *= BASE;
}
}
// Step 2: check the next character for +, -, =, or end of string:
match chars.next() {
None => {
// End of string
return Some(ParseResult {
coeffs,
present_mask,
leading_mask,
});
}
Some(ch) => {
match ch {
'+' => {
place = side;
}
'-' => {
place = -side;
}
'=' => {
// Switch to the other side, but only once.
if side < 0 {
return None; // More than one '=' sign => parse error
}
side = -1;
place = side;
}
_ => {
// Unrecognized character => parse error
return None;
}
}
}
}
}
}
/// A variable in the puzzle.
#[derive(Clone)]
struct Var {
value: Digit,
coeff: Term,
minval: Digit, // 0 or 1 depending on whether it's leading
name: Letter, // letter index
}
/// A puzzle solver that stores the formula and variables.
struct Solver {
formula: String,
num_vars: usize,
vars: Vec<Var>,
}
impl Solver {
fn new() -> Self {
Solver {
formula: String::new(),
num_vars: 0,
vars: Vec::new(),
}
}
/// Solve the puzzle and return whether parsing was successful.
fn solve(&mut self, formula_str: &str) -> bool {
self.formula = formula_str.to_string();
// Parse
let parse_result = match parse_formula(formula_str) {
Some(res) => res,
None => return false,
};
let mut coeffs = parse_result.coeffs;
let present_mask = parse_result.present_mask;
let leading_mask = parse_result.leading_mask;
// Gather letters that appear in the puzzle.
let mut letters_used = Vec::new();
for i in 0..ALPHABET_SIZE {
if (present_mask & (1 << i)) != 0 {
letters_used.push(i as Letter);
}
}
// If no letters are used, it's invalid or trivial.
if letters_used.is_empty() {
return false;
}
// If more than BASE letters are used, can't solve (since base=10).
if letters_used.len() > BASE as usize {
return false;
}
// Sort letters by ascending absolute value of their coefficients.
// We'll replicate the std::sort with a custom comparator:
letters_used.sort_by(|&a, &b| {
let aa = term_abs(coeffs[a as usize]);
let bb = term_abs(coeffs[b as usize]);
aa.cmp(&bb)
});
// Build Var array
self.num_vars = letters_used.len();
self.vars.clear();
// We'll track how large a negative or positive sum this puzzle can produce
// to prune the tree in solve2.
let mut bounds = [0, 0]; // bounds[0] is negative side, bounds[1] is positive side
for &letter_idx in &letters_used {
let idx = letter_idx as usize;
let coeff = coeffs[idx];
// If the letter is leading, it can't be zero:
let is_leading = (leading_mask & (1 << idx)) != 0;
let minval = if is_leading { 1 } else { 0 };
self.vars.push(Var {
value: 0,
coeff,
minval,
name: letter_idx,
});
}
// According to the sign of each coeff, we add or subtract the maximum possible digit
// to bounds so that we can check if current partial assignment is feasible.
for var in &self.vars {
if var.coeff > 0 {
// With a digit 9, it gives +9*coeff to the sum
bounds[1] += var.coeff * (BASE - 1);
} else {
// With a digit 9, it gives -9*|coeff| to the sum
bounds[0] += var.coeff * (BASE - 1);
}
}
// Recursively search for solutions
// We'll start from the end of self.vars so that we're
// assigning digits to the largest absolute-coeff letters first.
let last_index = self.num_vars - 1;
self.solve2(last_index, 0, bounds[0], bounds[1]);
// The original code always returns true if parse succeeded,
// though it doesn't indicate whether a solution was found or not.
true
}
/// Recursive solver similar to solve2 in the C++ code.
///
/// Arguments:
/// pos: index of the current Var to assign
/// digits_used: a bitmask of which digits have been used so far
/// lower_bound: how negative the partial sum can be
/// upper_bound: how positive the partial sum can be
fn solve2(&mut self, pos: usize, digits_used: u16, mut lower_bound: Term, mut upper_bound: Term) {
let coeff = self.vars[pos].coeff;
let mut d = BASE - 1;
let e = self.vars[pos].minval; // minimum digit (0 or 1)
// Adjust the bounds so we assume the digit is (BASE-1) for this position.
// Because in the original code:
// if (coeff < 0) upper_bound += coeff * d;
// else lower_bound += coeff * d;
// We'll do that once before descending.
if coeff < 0 {
upper_bound += coeff * d;
} else {
lower_bound += coeff * d;
}
// We'll replicate the "do {...} while (--d >= e)" logic by a loop:
while d >= e {
// Check feasibility:
// We only proceed if:
// 1) lower_bound <= 0
// 2) upper_bound >= 0
// 3) digit unused
let digit_mask = 1 << d;
if lower_bound <= 0 && upper_bound >= 0 && (digits_used & digit_mask) == 0 {
// Assign digit
self.vars[pos].value = d;
if pos == 0 {
// If this is the last variable (position 0),
// we print the solution.
let mut digit_chars = [' '; ALPHABET_SIZE];
for v in &self.vars {
digit_chars[v.name as usize] = format_digit(v.value);
}
// Print out the formula with replaced letters:
for c in self.formula.chars() {
if is_letter(c) {
let idx = parse_letter(c) as usize;
print!("{}", digit_chars[idx]);
} else {
print!("{}", c);
}
}
println!();
} else {
// Recurse with pos-1
let new_used = digits_used | digit_mask;
self.solve2(pos - 1, new_used, lower_bound, upper_bound);
}
}
// Move from digit d to d-1, adjusting bounds.
lower_bound -= coeff;
upper_bound -= coeff;
if d == 0 {
break;
}
d -= 1;
}
}
}
fn main() {
let args: Vec<String> = env::args().collect();
if args.len() < 2 {
eprintln!("Usage: {} <FORMULA1> <FORMULA2> ...", args[0]);
return;
}
// For each argument, solve the puzzle:
let mut code = 0;
for (i, formula) in args.iter().enumerate() {
if i == 0 {
// Skip the program name
continue;
}
println!("{}", formula);
let start_time = Instant::now();
let mut solver = Solver::new();
if !solver.solve(formula) {
code = 1;
}
println!("{:.6}",start_time.elapsed().as_secs_f64());
}
// Return code
std::process::exit(code);
}
Python 3, <5ms
def solver(eqn, soln_format = "eqn"):
#get weights
weight = -1
weights = {}
for char in reversed(eqn):
if char=='=':
weight=1
continue
if char=='+':
if weight>0:
weight=1
else:
weight=-1
continue
if char not in weights:
weights[char] = 0
weights[char]+= weight
weight*=10
assert len(weights) <= 10
weights_sorted = list(weights.values()) + [0]*(10-len(weights.values()))
weights_sorted.sort()
_, order = zip(*sorted(zip(weights_sorted, range(10)), key=lambda x: abs(x[0]), reverse=True)) #abs sorted order
order_list = [num - sum(i<num for i in order[:idx]) for idx, num in enumerate(order)] #because indexes change
order_list = order_list[:len(weights.values())] #to ignore zeros
order_list.reverse() #to pop and append like a stack
for soln in backtrack(0, weights_sorted.copy(), order_list, list(reversed(range(10))), []):
weights_copy = weights.copy()
weight_soln_pair = [(weights_sorted[i],num) for i,num in zip(order, soln)]
assert sum(i*j for i,j in weight_soln_pair) == 0, "Major error"
final_soln = {}
for weight_val, soln_val in weight_soln_pair:
for char, weight in weights_copy.items():
if weight == weight_val:
final_soln[char] = soln_val
del weights_copy[char]
break
if soln_format == "eqn":
#CONVERT TO EQN
eqn_copy = eqn
for k, v in final_soln.items():
eqn_copy = eqn_copy.replace(k, str(v))
yield eqn_copy
elif soln_format == "dict":
yield final_soln
def backtrack(val, weights, test_order, remaining, soln):
#Check if end
if len(test_order)==0:
if val==0:
yield soln
return False
#Check if possible
if sum([i*j for i,j in zip(remaining, reversed(weights))]) + val < 0: #max
return False
if sum([i*j for i,j in zip(remaining, weights)]) + val > 0: #min
return False
#Backtrack for each digit
order = test_order.pop()
weight = weights.pop(order)
for i, num in enumerate(remaining):
del remaining[i]
yield from backtrack(val+num*weight, weights, test_order, remaining, soln + [num])
remaining.insert(i, num)
weights.insert(order, weight)
test_order.append(order)
return False
does pretty much the same as benrg's answer, but in python and does not remove the solutions with leading zeros
%%timeit -n 1 -r 1
print([*solver('CODE+GOLF=GREAT')])
['9428+1437=10865', '9438+1427=10865', '9265+1278=10543', '9275+1268=10543', '8653+0671=09324', '8673+0651=09324', '8643+0672=09315', '8673+0642=09315', '8612+0635=09247', '8632+0615=09247', '7642+0651=08293', '7652+0641=08293', '6918+0934=07852', '6938+0914=07852', '6918+0925=07843', '6928+0915=07843', '5928+0943=06871', '5948+0923=06871', '3857+0862=04719', '3867+0852=04719', '3612+0685=04297', '3682+0615=04297', '2918+0956=03874', '2958+0916=03874', '2918+0947=03865', '2948+0917=03865', '2846+0851=03697', '2856+0841=03697']
4.63 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
notebook link
C++, 10000× faster (~20 µs)
#include <stdio.h>
#include <time.h>
#include <algorithm>
// digits
typedef int digit_t;
const digit_t BASE = 10;
typedef unsigned digit_mask_t;
inline char format_digit(digit_t d) { return '0' + d; }
// letters
typedef int letter_t;
const letter_t ALPHABETSIZE = 26;
typedef unsigned letter_mask_t;
inline bool is_letter(char c) { return unsigned(c - 'A') < 26u; }
inline letter_t parse_letter(char c) { return letter_t(c - 'A'); }
// terms
typedef int term_t;
inline term_t term_abs(term_t x) { return x < 0 ? -x : x; }
bool parse_formula(const char* formula, term_t coeffs[ALPHABETSIZE], letter_mask_t* ppresent, letter_mask_t* pleading) {
// Convert BA+BB=CCC into A + 21*B - 111*C = 0.
letter_mask_t present = 0, leading = 0;
const char* p = formula;
term_t side = +1, place = +1;
for (;;) {
const char* r;
for (r = p; is_letter(*r); ++r) {}
if (p < r)
leading |= letter_mask_t(1) << parse_letter(*p);
for (const char* q = r; q != p; --q) {
letter_t l = parse_letter(q[-1]);
coeffs[l] += place;
present |= letter_mask_t(1) << l;
place *= BASE;
}
p = r;
switch (*p++) {
case 0:
*ppresent = present; *pleading = leading; return true;
case '+':
place = +side; break;
case '-':
place = -side; break;
case '=':
if (side < 0)
return false;
place = side = -1;
break;
default:
return false;
}
}
}
struct Var {
digit_t value;
term_t coeff;
digit_t minval; // 0 or 1
letter_t name;
};
class Solver {
const char* formula;
letter_t num_vars;
Var vars[BASE];
void solve2(Var*, digit_mask_t, term_t, term_t);
public:
bool solve(const char* formula);
};
bool Solver::solve(const char* formula) {
this->formula = formula;
term_t coeffs[ALPHABETSIZE] = {0};
letter_mask_t present, leading;
if (!parse_formula(formula, coeffs, &present, &leading))
return false;
// sort the used letters by magnitude of their coefficient
letter_t letters[BASE];
letter_t num_vars = 0;
for (letter_t i = 0; i < ALPHABETSIZE; ++i) {
if (present & (letter_mask_t(1) << i)) {
if (num_vars == BASE)
return false;
letters[num_vars++] = i;
}
}
if (num_vars == 0)
return false;
this->num_vars = num_vars;
std::sort(letters, letters + num_vars, [&](letter_t a, letter_t b) { return term_abs(coeffs[a]) < term_abs(coeffs[b]); });
// initialize tables
term_t bounds[2] = {0};
for (letter_t i = 0; i < num_vars; ++i) {
vars[i].name = letters[i];
vars[i].minval = digit_t((leading >> letters[i]) & 1);
term_t coeff = vars[i].coeff = coeffs[letters[i]];
bounds[coeff > 0] += coeff * (BASE - 1);
}
// call the recursive solver
solve2(vars + num_vars - 1, 0, bounds[0], bounds[1]);
return true;
}
void Solver::solve2(Var* pos, digit_mask_t digits_used, term_t lower_bound, term_t upper_bound) {
term_t coeff = pos->coeff;
digit_t d = BASE - 1, e = pos->minval;
// adjust bounds to reflect a digit equal to BASE-1, instead of anything in [0,BASE)
if (coeff < 0)
upper_bound += coeff * d;
else
lower_bound += coeff * d;
do {
if (lower_bound <= 0 && upper_bound >= 0 && !(digits_used & (digit_mask_t(1) << d))) {
pos->value = d;
if (pos == vars) {
// print the solution
char digit_chars[ALPHABETSIZE];
for (letter_t i = 0; i < num_vars; ++i)
digit_chars[vars[i].name] = format_digit(vars[i].value);
for (const char* p = formula; *p; ++p)
putchar(is_letter(*p) ? digit_chars[parse_letter(*p)] : *p);
putchar('\n');
} else {
solve2(pos - 1, digits_used | (digit_mask_t(1) << d), lower_bound, upper_bound);
}
}
lower_bound -= coeff;
upper_bound -= coeff;
} while (--d >= e);
}
int main(int argc, char **argv) {
int code = 0;
for (int i = 1; i < argc; ++i) {
puts(argv[i]);
clock_t t = clock();
code |= !Solver().solve(argv[i]);
t = clock() - t;
printf("%f\n", double(t) / CLOCKS_PER_SEC);
}
return code;
}
This is roughly 10,000 times faster than JeffSB's solver and 2,500 times faster than Ajax1234's solver on my machine on the problem CODE+GOLF=GREAT. The speed ratio varies widely with the problem. For FIFTY+STATES=AMERICA, the JeffSB/me ratio is 25,000, while for CORRECTS+REJECTED=MATTRESS it's about 25.
The algorithm is quite different. Neither JeffSB nor Ajax1234 explained theirs, but it appears they both do digitwise addition from right to left. This program converts a problem like TO+GO=OUT into a formula like \$-98 O + 10 G - 10 U + 9 T = 0\$, with the terms sorted by absolute value. For each term from left to right, for each possible value of that digit, it computes upper and lower bounds for the sum by assuming that every later digit is 0 or 9. If the bounds include 0 then it recurses.
Since it doesn't cost any time, this program supports a more general set of alphametics with arbitrarily many terms on both sides of the =, and subtraction as well as addition. It can very quickly solve problems like NINETEEN+NINETEEN+TEN+TEN+TEN+TEN+NINE+NINE+NINE+NINE+NINE+ONE+ONE+ONE+...=THOUSAND where there are 877 ONEs.
I tried computing slightly more sophisticated bounds, and rewriting the recursive function as an iterative one, but both changes only improved performance by 1-2%, and complicated the code, so I reverted them.
(Sources for example problems: Mike Keith, Michael Hartley)
Python3, 0.03 seconds:
def f(a, b, r, c = {}, s = [], k = 0, l = [], A = [], B = []):
if not a and not b:
yield f"{''.join(map(str, A))}+{''.join(map(str, B))}={''.join(map(str, l))}"
return
for x in c.get(a[-1], range(10)):
if a[-1] in c or x not in s:
_c, _s = {**c, a[-1]:[x]}, s+[x]
for y in _c.get(b[-1], range(10)):
if b[-1] in _c or y not in _s:
n_c, v = {**_c, b[-1]:[y]}, k+x+y
n_s = _s+[y]
if a[:-1] and b[:-1]:
_v, _k = v%10, v//10
if [_v] == n_c.get(r[-1], [_v])and (r[-1] in n_c or _v not in n_s):
yield from f(a[:-1], b[:-1], r[:-1], {**n_c, r[-1]:[_v]}, n_s+[_v], _k, [_v]+l, [x]+A, [y]+B)
else:
if len(str(v)) == len(r):
F = 1
for J, K in zip(r[::-1], str(v)[::-1]):
if n_c.get(J, [int(K)]) == [int(K)] and (J in n_c or int(K) not in n_s):
n_c[J] = [int(K)]
n_s = n_s + [int(K)]
else:
F = 0
break
if F: yield from f(a[:-1], b[:-1], '', n_c, n_s, 0, [v]+l, [x]+A, [y]+B)
t = time.time()
result = [*f('CODE', 'GOLF', 'GREAT')]
print(time.time() - t)
print(result)