CODEWITHSUNDEEP
prolog
Toma Radu-Petrescu
Toma Radu-Petrescu

Reputation: 2262

How to generate a list with some numbers?

I want to generate a list with all the numbers abc, where a = c and b >= a + c.

I know how to generate the numbers, but I do not know how to add them to the list because I can not do something like L = [Number|L].

I don't know how to define the add predicate... or should I do it in another way? I have tried defining it as add(Nr, L, [Nr|L])., but I have no idea of what to do after that.

c(0). c(1). c(2). c(3). c(4). c(5). c(6). c(7). c(8). c(9).
bts(L, Lr) :- c(A), A =\= 0, c(C), A =:= C, c(B), C =\=9, B >= A + C,
    Nr is A * 100 + B * 10 + C, 
    add(......).
solve(L) :- bts([], L).

The output should be:
L=[121,131,141,151,161,171,181,191,242,252,262,272,282,292,363,373,383,393,484,494]

Upvotes: 0

Views: 97

Answers (3)

Toma Radu-Petrescu
Toma Radu-Petrescu

Reputation: 2262

This is the solution I found:

bts(1000, []) :- !.
bts(Nr, L) :-
         N is Nr + 1, 
         bts(N, X),
         once(((number_chars(Nr, [H1, H2, H3]), number_chars(A, [H1]), number_chars(C, [H3]),
                A =:= C, number_chars(B, [H2]), B >= A + C,
                L = [Nr|X]);
               L = X)).

solve(L) :- bts(100, L).

Upvotes: 1

CapelliC
CapelliC

Reputation: 60014

a simple application of findall/3 and between/3

abc(Ns) :- findall(N, (between(1,9,A),between(1,9,B),C=A,B>=A+C,N is A * 100 + B * 10 + C), Ns).

Upvotes: 1

mat
mat

Reputation: 40768

You are on the right track. Here are two small tips:

  1. First and most importantly, focus on what a single solution looks like. You can always use meta-predicates like findall/3 and setof/3 to collect all solutions into a list of solutions.
  2. Second, there are more intelligent ways to describe solutions in your case. Currently, you are using generate and test, which is an infeasible strategy for larger problems. Instead, use your Prolog system's constraint solvers to declaratively describe all requirements. This lets the engine apply pruning to avoid generating all combinations.

In total, my recommendation is to do it similar to the following:

abc(Ls) :-
        Ls = [A,B,C],
        A #= C,
        A #\= 0,
        C #\= 9,
        B #>= A + C,
        Ls ins 0..9.

We can now try the most general query to see what solutions look like in general:

?- abc(Ls).
Ls = [_940, _946, _940],
_940 in 1..4,
2*_940#=<_946,
_946 in 2..9.

This is of course not very useful, but it at least tells us that our relation terminates and is deterministic.

This means that so-called labeling, which is the search for concrete solutions will also terminate. That is a very nice property, because it means that the search will always terminate, even if it may take a long time.

In this case, the search is of course trivial, and we can use for example label/1 to enumerate solutions:

?- abc(Ls), label(Ls).
Ls = [1, 2, 1] ;
Ls = [1, 3, 1] ;
Ls = [1, 4, 1] ;
Ls = [1, 5, 1] ;
etc.

Now, to obtain the results you want, we will use findall/3 to collect all solutions into a list:

?- abc(Ls),
   findall(N, (label(Ls),
               atomic_list_concat(Ls,A),atom_number(A,N)), Ns).
Ls = [_774, _780, _774],
Ns = [121, 131, 141, 151, 161, 171, 181, 191, 242|...],
_774 in 1..4,
2*_774#=<_780,
_780 in 2..9.

I have also taken the liberty to apply a small transformation to each solution, so that you get the desired result immediately.

The formalism I am applying here is called CLP(FD), and the exact details for invoking this mechanism differ slightly between available Prolog systems. Check your system's manual for more information, and see also .

Upvotes: 1

Related Questions