Interesting but hard problem

[Racket Noob]

Hi guys!

I know this post isn't strictly related to Shen, but here are a lot of smart guys who (hopefully!) may find this problem interesting (see picture below):

I don't know how to solve this one. Is it some sort of Dynamic programming? Or something else? It would be so nice if someone could solve this...

RN

[Mark Tarver]

That's a really nice problem.  With deadlines etc.  I haven't the time to work on it; but it is the sort of thing that Prolog is very good at.   A straightforward implementation would be combinatorially explosive and heuristics are needed.  

Mark

[Mark Tarver]

(defprolog insert-l

  [X | _] Z I <-- (insert X Z I);

  [_ | Y] Z I <-- (insert-l Y Z I);)

  

(defprolog insert

  X Y [X | Y] <--;

  X [W | Y] [W | Z] <-- (insert X Y Z);)

  

(defprolog total

  Ns Total <-- (total-h Ns (- (length Ns) 1) Total);)  

  

(defprolog total-h

  [] _ 0 <--;

  [N | Ns] L M <-- (total-h Ns (- L 1) M*)

                   (is M (+ (* N (pow10 L)) M*));)

                   

(define pow10

  0 -> 1

  Expt -> (* 10 (pow10 (- Expt 1))))

(defprolog ans

  X <-- (is Show (output "~%X = ~S~%" X)) (is Answer (y-or-n? "More? ")) (checkans Answer);)

  

(defprolog checkans

  false <--;)      

 I started this and reminded myself I need to stick to what I planned to do today.

(32-) (prolog? (insert-l [0 1 2 3 4 5 6 7 8 9] [1 2 3 4] I) (ans I))

X = [0 1 2 3 4]

More?  (y/n) y

X = [1 0 2 3 4]

More?  (y/n) y

X = [1 2 0 3 4]

More?  (y/n) y

X = [1 2 3 0 4]

More?  (y/n) y

X = [1 2 3 4 0]

More?  (y/n) y

X = [1 1 2 3 4]

More?  (y/n) y

X = [1 1 2 3 4]

More?  (y/n) y

X = [1 2 1 3 4]

More?  (y/n) y

X = [1 2 3 1 4]

More?  (y/n) y

X = [1 2 3 4 1]

More?  (y/n) y

X = [2 1 2 3 4]

More?  (y/n) y

X = [1 2 2 3 4]

More?  (y/n) y

X = [1 2 2 3 4]

More?  (y/n) y

etc etc.

(33-)  (prolog? (total [1 2 3 4] T) (return T))

1234

This is part of the code.  Maybe some other people here can work this up into a solution.

[Mark Tarver]

Well I had a few minutes left after chores so I finished the program.  Here is a solution.  It uses incrementally bounded depth first search and is written in Shen Prolog.

(defprolog eureka!

  E1 E2 E3 <-- (search-cycle (digits E1) E1* (digits E2) E2* (digits E3) E3* 0)

               (total E1* T1)

               (total E2* T2)

               (total E3* T3)

               (is Answer (output "~A + ~A = ~A~%" T1 T2 T3));)

               

(define digits

  N -> (map (/. N (- (string->n N) 48)) (explode N)))               

  

(defprolog search-cycle

  E1 E1* E2 E2* E3 E3* Depth <-- (insert-digits-depth E1 E1* Depth)

                                 (insert-digits-depth E2 E2* Depth)

                                 (insert-digits-depth E3 E3* Depth)

                                 (balanced? E1* E2* E3*);

  E1 E1* E2 E2* E3 E3* Depth <-- (search-cycle E1 E1* E2 E2* E3 E3* (+ 1 Depth));)

(defprolog balanced?

  E1 E2 E3 <-- (total E1 T1) (total E2 T2) (total E3 T3) (when (= (+ T1 T2) T3));)

  

(defprolog insert-digits-depth

  Ns Ns 0 <-- !;

  Ns Result Depth <-- (insert-digits Ns Intermediate)

                      (insert-digits-depth Intermediate Result (- Depth 1));) 

                         

(defprolog insert-digits

  Ns Result <-- (insert-l [0 1 2 3 4 5 6 7 8 9] Ns Result);)                          

(defprolog insert-l

  _ I I <--;

  [X | _] Z I <-- (insert X Z I);

  [_ | Y] Z I <-- (insert-l Y Z I);)

  

(defprolog insert

  X Y [X | Y] <--;

  X [W | Y] [W | Z] <-- (insert X Y Z);)

  

(defprolog total

  Ns Total <-- (is Expt (- (length Ns) 1)) (total-h Ns Expt Total);)  

  

(defprolog total-h

  [] _ 0 <--;

  [N | Ns] Expt M <-- (is Expt-1 (- Expt 1))

                      (total-h Ns Expt-1 M*)

                      (is M (+ (* N (pow10 Expt)) M*));)

                   

(define pow10

  0 -> 1

  Expt -> (* 10 (pow10 (- Expt 1)))) 

Here are some tests.

(57-) (prolog? (eureka! 1 1 3))

1 + 12 = 13

true

(58-) (prolog? (eureka! 1 10 30))

10 + 120 = 130

true

(59-) (prolog? (eureka! 91 19 11))

91 + 19 = 110

true

(60-) (prolog? (eureka! 11 11 33))

211 + 121 = 332

true

(61-) (prolog? (eureka! 3782 9362 2349))

Heap exhausted during allocation: 153153536

As you can see, and I guessed, a logically complete procedure is exponentially complex.   Signing out now.

Mark

[fuzzy wozzy]

11 + 11 = 33:

151 + 181 = 332

161 + 171 = 332

[fuzzy wozzy]

in 11 + 11 = 33, to find 121 + 211 = 332 using shen list,
given (addList), such that (addList [3 8 4] [2 7 9]) = [6 6 3]),

look for (addList [1 X 1] [Y 1 1]) whose answer gives [3 3 _],
which leads to X = 2, Y = 2.

for (addList [1 X 1] [1 Y 1]) whose answer gives [3 3 _],
[X Y] = [5 8] or [6 7].

[Willi Riha]

I have just come across this interesting link.

A very good,, but extremely hard problem! 25-30 years ago, I would have invested a lot of time trying to solve it, because "mathematical puzzles" was what stimulated me.then.

This particular puzzle, as it has been presented is difficult, but it invites a number of generalisations, which are a great deal more complicated.

Instead of just 2 terms in the sum, you could have k terms. Instead of  sums, you could also consider sums and differences and/or  a mixture of other arithmetic operations. In this generality, I am not even sure if it can be solved in exponential time.! But I haven't read about any recent advances in the theory of NP-completeness, since my retirement, 16 years ago.

.

.

On Thursday, July 14, 2016 at 8:58:03 AM UTC+1, Racket Noob wrote:

[Mark Tarver]

One interesting question is whether every such k-tuple has at least one solution.  I think it does and one might evolve a linear or polynomial time algorithm for finding a solution but that solution would be very non-optimal.

I agree the problem invites interesting generalisations.  In its most general form, it invites you to 'balance' a list L of sentences from a language L (meaning 'language' in the formal sense) using a finite set of operations O to create L*, where a relation R holds over L*.  I'm pretty certain there is no non-exponential algorithm for the problem in its most general form.  Such a program has commercial use - no doubt.  It links many process from the chemical transposition of molecules to Rubik's Cube.

The Prolog approach I used is not the final word in execution.  There are alternative approaches which are as elegant but which offer faster execution and the opportunity for concurrency.  The exponential nature is not affected by the speedup of course, and as I used to say to my students,  you cannot kill an exponential dragon with a linear sword.

Mark

[Mark Tarver]

I should have used K and not L; as in

In its most general form, it invites you to 'balance' a list L of sentences from a language K  (meaning 'language' in the formal sense) using a finite set of operations O to create L*, where a relation R holds over L*.

[fuzzy wozzy]

(prolog? (eureka! 22 123 30))
227 + 123 = 350
true

22 + 1283 = 1305 might be the minimum answer.

[Mark Tarver]

Nice; but I count 3 insertions in your answer (8,1, 5) and the Prolog one has 2 (7,5).

Mark

--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

[fuzzy wozzy]

to find 11 + 11 + 11 = 55, one could permutatively do...

(addList [X 1 1] [Y 1 1] [Z 1 1]) and match the answer with either [5 5 _] or [_ 5 5], for a starter,
and several answers can be found,

(addList [4 1 1] [0 1 1] [1 3 1]) = [5 5 3], equivalent to 411 + 11 + 131 = 553, if a leading zero is not counted as an insertion.
(addList [0 1 1] [1 3 1] [1 1 3]) = [2 5 5], equivalent to 11 + 131 + 113 = 255.

the following solution would give all answers for this particular example, when matching it with [5 5 _] or [_ 5 5],
if the answers are numbers of three digits or less.

(addList [X 1 1] [Y 1 1] [Z 1 1])
(addList [X 1 1] [Y 1 1] [1 Z 1])
(addList [X 1 1] [Y 1 1] [1 1 Z])
(addList [X 1 1] [1 Y 1] [Z 1 1])
(addList [X 1 1] [1 Y 1] [1 Z 1])
(addList [X 1 1] [1 Y 1] [1 1 Z])
(addList [X 1 1] [1 1 Y] [Z 1 1])
(addList [X 1 1] [1 1 Y] [1 Z 1])
(addList [X 1 1] [1 1 Y] [1 1 Z])
............................................  \\ all the way to
(addList [1 1 X] [1 1 Y] [Z 1 1])
(addList [1 1 X] [1 1 Y] [1 Z 1])
(addList [1 1 X] [1 1 Y] [1 1 Z])

finding 11 + 234 + 503 = 55, would be similarly done using the format,

(addList [X 1 1] [Y 2 3 4] [Z 5 0 3])

and applying the above method, one would imagine...

[fuzzy wozzy]

if adding two 10-digit numbers, and the minimum insertions happen to be 3 for each number,
that would be quite complex to find the answers, actually, too hard for me to begin to think about...

[Mark Tarver]

You won't beat the Prolog program when it produces an answer because it is guaranteed to find a best answer within the limits of memory.  If you want to do better you have to find an alternative heuristic approach, but snippets of code don't really add up to a program.  Certainly 10-digits numbers are beyond the scope of my scope.   This is something you could try to do but starting with say 4 digit numbers - and trying to present a program rather than just bits of code.

Mark

On Wed, Jul 20, 2016 at 7:25 AM, fuzzy wozzy <swtch...@gmail.com> wrote:

if adding two 10-digit numbers, and the minimum insertions happen to be 3 for each number,
that would be quite complex to find the answers, actually, too hard for me to begin to think about...

[Mark Tarver]

You won't beat the Prolog program when it produces an answer because it is guaranteed to find a best answer within the limits of memory.  If you want to do better you have to find an alternative heuristic approach, but snippets of code don't really add up to a program.  Certainly 10-digit numbers are beyond the scope of my Prolog program.   This is something you could try to do but starting with say 4 digit numbers - and trying to present a program rather than just bits of code.

typos - in a rush

Mark :)

[fuzzy wozzy]

to solve 3782 + 9362 = 2349 doesn't really require a computer, a quick guess yields,

(addList [X 3 7 8 2] [9 Y 3 6 2]), where X = Y = 5, gives [1 4 9 1 4 4], then,
2253782 + 95362 = 2349144, with 7 insertions (2, 2, 5, 5, 1, 4, 4).

considering that 1 + 1 = 3 took 3 insertions to solve, 7 insertions for a much larger number like this
probably isn't too bad, and could be close to an actual answer.

[fuzzy wozzy]

actually, 1 + 10 = 30 took 3 insertions, 1 + 1 = 3 took only 2 insertions...

[Mark Tarver]

I think we can't have any more hand-solutions; this is a programming group after all.

Mark

[fuzzy wozzy]

"I know this post isn't strictly related to Shen"....
that alone indicated to me that the original requester of this post was not necessarily looking for a
shen implementation to be presented as an answer to the question (imagine the great surprise upon
realizing that it was done so), but if one were to assume that everyone here, including any newcomers,
are indeed EXPERT prolog programmers, I may be the only one who is at a hopelessly complete loss
to ever understand the prolog presentation of the solution, and could someone expertly shenturianish
please port or translate prolog shen to functional shen perhaps?

as for the functional shen version of my clunky cumbersome version of the attempt at a solution,
I would say that my solution is too amateurish and verbose that, while it would be simpler than simple
to present it in the functional shen format, I would dare not do so until I have found and presented something
more agreeably savory for the pleasure of the EXPERT shenturians, whom, as you may know, may not
take kindly to anything if not the nearly-perfected solution...