Problem with instanciation of list :)

Help!
1

Hi,
I am trying to solve a problem (description). Kattio is the custom reader for prolog. I am reading in a word that comes in unicode characters, that is, a list of numbers.
I permute the list, split it in two and get prolog to find all the possible palindroms over List1. I need the length of the list that is not used to write the palindrom, that is to say List2. The length of List2 is N.
But when I try to append all the N to a new list of Ns, I get an error because the list is not instantiated. I tried to write it before in main, make a custom append, but nothing works so far.

[kattio].
main :-
% reading input 
	read_atom(X),
	(X == end_of_file ; atom_codes(X, X2),
% solving for X2 because it needs conversion, receiving N everytime a solution is found,
% trying to add this N to a list of Ns.
% to do next is to find the smallest element of the list Ns, that is the solution to the problem
	solve(X2,N), write(N), append(Ns, N),
	 fail
	).
% make all possible permutations, split in 2 lists such as List1 is a palindrom, and return the % length of the list of the letters not used in the solution
solve(Y,N):- permutation(Y,X), append(List1,List2, X), is_palindrome(List1), writeln(List1), writeln(List2), length(List2,N).
is_palindrome(L) :- reverse(L,L).

I get the error:

ERROR: -g main: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [15] throw(error(instantiation_error,_1210))

So I understand that I need to instantiate the list Ns before I use it, but I cannot find a way. I would be very grateful for any help!

2

I ran your code and got these warnings:

Warning: /tmp/pal.pl:1:
Warning:    Singleton variables: [Ns]
Warning: /tmp/pal.pl:1:
Warning:    Singleton variable in branch: Ns

Try fixing those and see what happens.

Also, the sequence append(Ns, N), fail is effectively a no-op – the append will be undone on backtracking.

It’s probably better to split your code into a part that generates the answers and a part that outputs them. You can use predicates such as forall/2 and maplist/2 to generate all results and to apply the same predicate (e.g., print) to all elements of a list.

1 Like
3

Sorry, I still don’t get it. Shall I create an additional layer where I use forall/2 and maplist? Could you please link me an example?

4

PS: It’s easier to understand your code when it’s formatted uniformly:

main :-
    % reading input
    read_atom(X),
    ( X == end_of_file
    ; atom_codes(X, X2),
      % solving for X2 because it needs conversion, receiving N
      % everytime a solution is found, trying to add this N to a list
      % of Ns.  to do next is to find the smallest element of the list
      % Ns, that is the solution to the problem
      solve(X2,N),
      write(N),
      append(Ns, N),
      fail
    ).

% make all possible permutations, split in 2 lists such as List1 is a
% palindrom, and return the % length of the list of the letters not
% used in the solution
solve(Y,N):-
    permutation(Y,X),
    append(List1,List2, X),
    is_palindrome(List1),
    writeln(List1),
    writeln(List2),
    length(List2,N).
is_palindrome(L) :- reverse(L,L).
1 Like
5

Perhaps maplist and forall are too advanced for you right now; but getting a repeat/fail loop working properly has its own challenges.

I don’t understand your problem description; it might help if you could give a sample input and expected output.

6

As Peter said

This site has Useful Prolog references and the first one is Coding Guidelines for Prolog

7

For example, if I input “aad”, the desired output is “0”, because “aad” can be transformed in a palindrom (“ada”). Right now the output I get is “3213203213203232”, that is a list of all N (length of the list of letters not used in my palindrom), from which I want to extract the minimum.

With “abc”, the desired output is “2”, since we need to remove at least 2 letters to get a palindrome. The output I get right now is 323232323232. (minimum = 2)

Since I have the list of all possible Ns, I believe I just need a way to unify it somehow… which has proved incredibly challenging so far.

I have something like that in mind now, but it does not solve the instanciation problem:

[kattio].

main :-
	read_atom(X),
	(X == end_of_file ; atom_codes(X, X2),
	gather_results(X2),
	 fail
	).
gather_results(X2) :-
	solve(X2,Ns),
	write(Ns).

solve(Y, Ns):-
	permutation(Y,X),
	append(List1,List2, X),
	is_palindrome(List1),
	length(List2,N),
	[N:Ns].

is_palindrome(L) :- reverse(L,L).
8

Yes, I will format properly!

9

OK, let’s look at solve/2, but make it simpler:

%! palindrome_by_removing(+Letters:list, -Removed:list, -Palindrome:list) is nondet.
% Succeeds if zero or more letters from Letters are removed 
% (and unified with Removed) and the remaining letters form 
% Palindrome (a palindrome). There must be at least
% one letter in Palindrome; Removed may be empty.
% For example:
% palindrome_by_removing([z,a,z], [a], [z,z]). 
% palindrome_by_removing([z,a,z], [z,z], [a]).

We can deal with getting the minimal length to remove later.

1 Like
10

I’ve amended your code to give an idea of how you could with minimal changes make your code do what you want, and give you an idea of how findall works. However, your algorithm is very inefficient since generating the number of permutations increases dramatically, e.g. for 13 letters you will generate 6 billion combinations! You could solve it alot faster if you think about if a letter occurs either an even number or odd number of times in a palindrome.

[kattio].

main :-
	read_atom(X),
	(X == end_of_file ; atom_codes(X, X2),
	gather_results(X2),
	 fail
	).

gather_results(X2) :-
    solve(X2,Ns),
    writeln(Ns),
    min_list(Ns,N),
    write(N).

solve(Y, Ns):-
    findall(N,(
        permutation(Y,X),
        append(List1,List2, X),
        is_palindrome(List1),
        length(List2,N)
    ), Ns).

is_palindrome(L) :- reverse(L,L).
1 Like
11

@Ian u are absolutely right, it’s very inefficient.
This is how I solved it in another language (grouping by even and odd groups and counting odd groups). But this time I wanted to do something more in line with prolog.
Is there a way to get rid of the permutations, by for example sorting the list beforehand, or exiting as soon as N is zero? Edit: just found out that findall does not generate all possible solutions, so it’s hard to get around permutations…

@peter.ludemann thank you for the tips! Do you think “palindrome-by_removing” will also have the efficiency problem?

12

Thank you friends, I got it with a frequency list!
Thank you very much for all the help :heart_eyes: :heart:

main :-
    read_string(X),
	gather_results(X).

gather_results(List) :-
    solve(List,Ns),
    count_odds(Ns, The_Odds),
    Final is max(0,The_Odds -1),
    write(Final).

solve(List, Ns):-
% count how many of each character
% aggregate is [explained here](https://stackoverflow.com/questions/6060268/prolog-count-the-number-of-times-a-predicate-is-true)
	findall(R, (aggregate(count, member(_,List), R)), Ns).

% mine was not enough instanciated, picked that from stack
% https://stackoverflow.com/questions/44510056/how-to-count-only-the-number-elements-in-a-list-prolog
count_odds([],0).
count_odds([H|Tail], N) :-
    count_odds(Tail, N1),
    (  odd(H)
    -> N is N1 + 1
    ;  N = N1
    ).

odd(X) :- 1 is mod(X, 2).