Faster implementation of verbal arithmetic in Prolog

by

Consider using finite domain constraints, for example, in SWI-Prolog:

:- use_module(library(clpfd)).

puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
        Vars = [S,E,N,D,M,O,R,Y],
        Vars ins 0..9,
        all_different(Vars),
                  S*1000 + E*100 + N*10 + D +
                  M*1000 + O*100 + R*10 + E #=
        M*10000 + O*1000 + N*100 + E*10 + Y,
        M #\= 0, S #\= 0.

Example query:

?- time((puzzle(As+Bs=Cs), label(As))).
% 5,803 inferences, 0.002 CPU in 0.002 seconds (98% CPU, 3553582 Lips)
As = [9, 5, 6, 7],
Bs = [1, 0, 8, 5],
Cs = [1, 0, 6, 5, 2] ;
% 1,411 inferences, 0.001 CPU in 0.001 seconds (97% CPU, 2093472 Lips)
false.

More Related Contents:

  1. High-performance merging of ordered sets
  2. Google app script timeout ~ 5 minutes?
  3. What is the purpose of the EBP frame pointer register?
  4. nth fibonacci number in sublinear time
  5. Algorithm to calculate the number of divisors of a given number
  6. Why are difference lists more efficient than regular concatenation in Haskell?
  7. Analyzing Code for Efficiency?
  8. Apache Spark: map vs mapPartitions?
  9. Reading GHC Core
  10. CSS3 Transitions: Is “transition: all” slower than “transition: x”?
  11. Size of store buffers on Intel hardware? What exactly is a store buffer?
  12. Avoid stalling pipeline by calculating conditional early
  13. What’s the fastest way to merge/join data.frames in R?
  14. How to optimize vlookup for high search count ? (alternatives to VLOOKUP)
  15. What is the fastest way to get the value of π?
  16. Fast query runs slow in SSRS
  17. Entity Framework query slow, but same SQL in SqlQuery is fast
  18. R: speeding up “group by” operations
  19. Bulk inserts taking longer than expected using Dapper
  20. Why are compilers so stupid?
  21. SVN performance after many revisions
  22. In SQLite, do prepared statements really improve performance?
  23. Mapping 2 vectors – help to vectorize
  24. MongoDB ranged pagination
  25. Why is appending to a list bad?
  26. Why is putImageData so slow?
  27. preallocate list in R
  28. How to analyze golang memory?
  29. Performance of bcp/BULK INSERT vs. Table-Valued Parameters
  30. How to avoid Query Plan re-compilation when using IEnumerable.Contains in Entity Framework LINQ queries?

Leave a Comment