fork(1) download
copy 
  1. use std::collections::{HashMap, HashSet};
  2.  
  3. fn main() {
  4.     //twitter.com/own_touch/status/1249253680475295749
  5.     Solver::new(
  6.         Exp::v("MISSHU")
  7.             .add(Exp::v("MIPPEI"))
  8.             .add(Exp::v("MISSETU"))
  9.             .eql(Exp::v("SAKETEE")),
  10.     )
  11.     .solve();
  12. }
  13.  
  14. enum Exp {
  15.     V(String),
  16.     Add(Box<Exp>, Box<Exp>),
  17.     Eql(Box<Exp>, Box<Exp>),
  18. }
  19.  
  20. impl Exp {
  21.     fn v(s: &str) -> Box<Exp> {
  22.         Box::new(Exp::V(s.to_string()))
  23.     }
  24.     fn add(self: Box<Exp>, b: Box<Exp>) -> Box<Exp> {
  25.         Box::new(Exp::Add(self, b))
  26.     }
  27.     fn eql(self: Box<Exp>, b: Box<Exp>) -> Box<Exp> {
  28.         Box::new(Exp::Eql(self, b))
  29.     }
  30.     fn calc(&self, map: &HashMap<char, i64>) -> Option<i64> {
  31.         match *self {
  32.             Exp::Add(ref a, ref b) => {
  33.                 if let (Some(a), Some(b)) = (a.calc(map), b.calc(map)) {
  34.                     Some(a + b)
  35.                 } else {
  36.                     None
  37.                 }
  38.             }
  39.             Exp::Eql(ref a, ref b) => {
  40.                 if let (Some(a), Some(b)) = (a.calc(map), b.calc(map)) {
  41.                     if a == b {
  42.                         Some(-1)
  43.                     } else {
  44.                         None
  45.                     }
  46.                 } else {
  47.                     None
  48.                 }
  49.             }
  50.             Exp::V(ref s) => {
  51.                 let mut v = 0;
  52.                 for c in s.chars() {
  53.                     v *= 10;
  54.                     v += map.get(&c).unwrap();
  55.                     if v == 0 {
  56.                         return None;
  57.                     }
  58.                 }
  59.                 Some(v)
  60.             }
  61.         }
  62.     }
  63.     fn print(&self) {
  64.         match *self {
  65.             Exp::Add(ref a, ref b) => {
  66.                 a.print();
  67.                 print!(" + ");
  68.                 b.print();
  69.             }
  70.             Exp::Eql(ref a, ref b) => {
  71.                 a.print();
  72.                 print!(" = ");
  73.                 b.print();
  74.             }
  75.             Exp::V(ref s) => {
  76.                 print!("{}", s);
  77.             }
  78.         }
  79.     }
  80.  
  81.     fn print_with(&self, map: &HashMap<char, i64>) {
  82.         match *self {
  83.             Exp::Add(ref a, ref b) => {
  84.                 a.print_with(&map);
  85.                 print!(" + ");
  86.                 b.print_with(&map);
  87.             }
  88.             Exp::Eql(ref a, ref b) => {
  89.                 a.print_with(&map);
  90.                 print!(" = ");
  91.                 b.print_with(&map);
  92.             }
  93.             Exp::V(ref s) => {
  94.                 let mut v = 0;
  95.                 for c in s.chars() {
  96.                     v *= 10;
  97.                     v += map.get(&c).unwrap();
  98.                 }
  99.                 print!("{}", v);
  100.             }
  101.         }
  102.     }
  103. }
  104.  
  105. struct Solver {
  106.     exp: Box<Exp>,
  107.     set: Vec<char>,
  108. }
  109.  
  110. impl Solver {
  111.     fn new(exp: Box<Exp>) -> Solver {
  112.         let mut set = HashSet::new();
  113.         Solver::pick(&mut set, &exp);
  114.         Solver {
  115.             exp,
  116.             set: set.into_iter().collect(),
  117.         }
  118.     }
  119.     fn pick(set: &mut HashSet<char>, exp: &Exp) {
  120.         match *exp {
  121.             Exp::Add(ref a, ref b) | Exp::Eql(ref a, ref b) => {
  122.                 Solver::pick(set, &a);
  123.                 Solver::pick(set, &b);
  124.             }
  125.             Exp::V(ref s) => {
  126.                 for c in s.chars() {
  127.                     set.insert(c);
  128.                 }
  129.             }
  130.         }
  131.     }
  132.     fn solve(&self) {
  133.         let mut ind: Vec<_> = (0..self.set.len()).collect();
  134.         let mut map = HashMap::new();
  135.         let mut flag = (1 << (ind.len() + 1)) - 1;
  136.         loop {
  137.             for (i, ix) in ind.iter().enumerate() {
  138.                 map.insert(self.set[*ix], i as i64);
  139.             }
  140.             if self.exp.calc(&map).is_some() {
  141.                 println!("found");
  142.                 for (k, v) in &map {
  143.                     print!("{}={}, ", k, v);
  144.                 }
  145.                 println!();
  146.                 self.exp.print();
  147.                 println!();
  148.                 self.exp.print_with(&map);
  149.                 println!();
  150.             }
  151.             let mut p = ind.len() - 1;
  152.             loop {
  153.                 flag ^= 1 << ind[p];
  154.                 ind[p] += 1;
  155.                 while ind[p] < ind.len() && (flag & (1 << ind[p])) != 0 {
  156.                     ind[p] += 1;
  157.                 }
  158.                 if ind[p] < ind.len() {
  159.                     flag |= 1 << ind[p];
  160.                     p += 1;
  161.                     break;
  162.                 }
  163.                 if p == 0 {
  164.                     return;
  165.                 }
  166.                 p -= 1;
  167.             }
  168.             while p < ind.len() {
  169.                 ind[p] = 0;
  170.                 while ind[p] < ind.len() && (flag & (1 << ind[p])) != 0 {
  171.                     ind[p] += 1;
  172.                 }
  173.                 flag |= 1 << ind[p];
  174.                 p += 1;
  175.             }
  176.         }
  177.     }
  178. }
  179.  
Success #stdin #stdout 2.41s 4272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
found
T=5, A=7, K=1, I=0, S=9, H=4, M=8, P=3, E=2, U=6, 
MISSHU + MIPPEI + MISSETU = SAKETEE
809946 + 803320 + 8099256 = 9712522
https://ideone.com/ERchE2
language:
Rust (rust 1.56)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!