#!/usr/local/bin/perl
# 
# This Perl program converts an alphametic puzzle equation to a MiniZinc (.mzn) model.
#
# Examples:
#
#   * satisfiability
#     $ perl alphametic2mzn.pl "SEND+MORE=MONEY"
#     $ perl alphametic2mzn.pl "SATURN + URANUS + NEPTUNE + PLUTO = PLANETS"
#   * optimality: maximize on variable MOST
#     $ perl alphametic2mzn.pl "SEND+MOST=MONEY" MOST max
# 
# See my MiniZinc page at http://hakank.org/minizinc/
# 
$|=1;
use strict;
use warnings;


my $eq = $ARGV[0] || "SEND+MORE=MONEY";
my $opt_var = $ARGV[1] || ""; # optimize on which word/variable?
my $opt_dir = $ARGV[2] || ""; # direction of optimality (min|max)

$eq =~  s/\s+//g;
if ($opt_var and $eq and $eq !~ /$opt_var/) {
  die "Something is wrong: The opt var $opt_var is not in the equation\n";
}

if ($opt_dir and $opt_dir !~ /^(?:min|max)/) {
  die "Something is wrong: The opt direction ('$opt_dir') is not min(imize) or max(imize)\n";
}


my @eq = split /=/, $eq;
my @adds = split /\+/, $eq[0];
my @result = $eq[1];

my $date = scalar localtime;

my %first_letters = ();
for ((@adds,@result)) {
  $first_letters{$1}++ if /^(.)/;
}

my @first_letter_constraint = "";
for (sort keys %first_letters) {
  push @first_letter_constraint, "\t$_ > 0";
}

my $first_letter_constraint_str = join " /\\\n", @first_letter_constraint;

my @letters = split //, $eq;
my %letters = ();
for (@letters) {
  $letters{$_}++;
}

my $all_letters = "";
my @letters_arr = ();
for (sort keys %letters) {
  next if $_ !~ /\w/;
  $all_letters .= "var Digit_xxx: $_;\n";
  push @letters_arr, $_;
}

my $letter_len = scalar @letters_arr;
my $letters_array_str = join ",", @letters_arr;

my $adds_str = "";
my @output = ();
my @adds_constraints = "";
my %adds = ();
my @all_vars = ();
for ((@adds, @result)) {
  my $split = join ",", split //;
  push @output, <<EOT;
  "$_: ", show($_), " (", show([$split]), ")\\n",
EOT
  next if $adds{$_}++;
  push @adds_constraints, "\tto_num([$split], $_)";
  $adds_str .= "var int: $_;\n" if length $_ > 1;
  push @all_vars, $_ if length $_ > 1;
}

my $adds_constraints_str = join " /\\\n", @adds_constraints;
my $output = join "", @output;
my $all_vars_str = join ",", @all_vars;

# solve satisfy or optimality?
my $goal = "satisfy";
my $direction =  "";
if ($opt_var and $opt_dir) {
  if ($opt_dir) {
    $direction = $opt_dir =~ /min/ ? "minimize" : "maximize";
  }
  warn "Optimize: $direction on $opt_var";
  $goal = "$direction $opt_var";

}

print <<EOT;
% 
% Alphametic problem $eq in MiniZinc
% 
% This model was generated by $0
% ($date)

%
% $0 was created by Hakan Kjellerstrand (hakank\@gmail.com).
% See my other MiniZinc models at http://hakank.org/minizinc/
%
% 

include "globals.mzn";

set of int: Digit_xxx = 0..9;

$all_letters

array[1..$letter_len] of var Digit_xxx : LD = [$letters_array_str];

$adds_str

predicate to_num(array[int] of var Digit_xxx: a, var int: n) =
          let { int: len = length(a) }
          in
          n = sum(i in 1..len) (
            pow(10, len-i) * a[i]
          )
          /\\ forall(i in 1..len) (a[i] >= 0)
;

solve :: int_search(LD ++ [$all_vars_str], anti_first_fail, indomain_split, complete) $goal;

constraint
\tall_different(LD)
$adds_constraints_str /\\
\t$eq
$first_letter_constraint_str
;

output [
  "$eq:\\n",
$output
]
;

EOT