prolog - Solution to Smullyan's numerical machines -

prolog - Solution to Smullyan's numerical machines -

here propose find solution smullyan's numerical machines defined here.

problem statement

they're machines take list of digits input, , transform list of digits next rules based on pattern of input. here rules of machine given in link above, expressed bit more formally. allow m machine, , m(x) transformation of x. define few rules this:

m(2x) = x m(3x) = m(x)2m(x) m(4x) = reverse(m(x)) // reverse order of list. m(5x) = m(x)m(x)

and not match rule rejected. here few examples:

m(245) = 45 m(3245) = m(245)2m(245) = 45245 m(43245) = reverse(m(3245)) = reverse(45245) = 54254 m(543245) = m(43245)m(43245) = 5425454254

and questions are, find x such that:

m(x) = 2 m(x) = x m(x) = x2x m(x) = reverse(x) m(x) = reverse(x2x)reverse(x2x)

here sec illustration bit more complex exhaustive search (especially if want first 10 or 100 solutions).

m(1x2) = x m(3x) = m(x)m(x) m(4x) = reverse(m(x)) m(5x) = truncate(m(x)) // remove first element of list truncate(1234) = 234. valid if m(x) has @ to the lowest degree 2 elements. m(6x) = 1m(x) m(7x) = 2m(x)

questions:

m(x) = xx m(x) = x m(x) = reverse(x) (non-)solutions

writing solver in prolog pretty straightforward. except it's exhaustive exploration (a.k.a brute force) , may take time set of rules.

i tried couldn't express problem in terms of logic constraints clp(fd), tried chr (constraint handling rules) express in terms of constraints on lists (especially append constraints), no matter how express it, boils downwards exhaustive search.

question

any thought approach take resolve problem of kind in reasonable amount of time? ideally able generate solutions shorter bound.

here improvement @celelibi's improved version (cele_n). roughly, gets factor of 2 constraining length of first argument, , factor of 2 pretesting 2 versions.

cele_n sicstus 2.630s cele_n swi 12.258s 39,546,768 inferences cele_2 sicstus 0.490s cele_2 swi 2.665s 9,074,970 inferences appendh([], [], xs, xs). appendh([_, _ | ws], [x | xs], ys, [x | zs]) :- appendh(ws, xs, ys, zs). m([h|a], x) :- = [_|_], % new m(h, x, a). m(1, x, a) :- append(x, [2], a). m(3, x, a) :- appendh(x, b, b, x), m(a, b). m(4, x, a) :- reverse(x, b), m(a, b). m(5, x, a) :- x = [_| _], m(a, [_|x]). m(h1, [h2 | b], a) :- \+ \+ ( h2 = 1 ; h2 = 2 ), % new m(a, b), ( h1 = 6, h2 = 1 ; h1 = 7, h2 = 2 ). answer3(x) :- between(1, 13, n), length(x, n), reverse(x, a), m(x, a). run :- time(findall(x, (answer3(x), write(x), nl), _)).

prolog constraint-programming