RabbitFarm

2025-03-29

The Weekly Challenge 314 (Prolog Solutions)

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1: Equal Strings

You are given three strings. You are allowed to remove the rightmost character of a string to make all equals. Write a script to return the number of operations to make it equal otherwise -1.

The approach we’ll take is to pop off the last letter of each and compare the remainders. If they are equal then we are done. Otherwise we’ll continue popping off letter until we’re done.

A special case to consider is when the strings are of unequal length. In that case we make sure to only pop off letters from equal length strings, although the untouched strings will still be used when checking to see if we are done.

We’re going to define some convenience predicates, some with the intention that they’re going to be called from a maplist.

⟨remove last letter 1 ⟩≡


remove_last(S, S1):-
length(Last, 1),
append(S1, Last, S).
◇

Fragment referenced in 7.

⟨strings all of the same size 2 ⟩≡


match_length(Length, S, S):-
length(S, Length).
match_length(_, _, nil).
◇

Fragment referenced in 7.

⟨all strings are equal 3 ⟩≡


all_equal([H|T]):-
maplist(==(H), T).
◇

Fragment referenced in 7.

⟨all strings are empty 4 ⟩≡


all_empty(L):-
maplist(==([]), L).
◇

Fragment referenced in 7.

⟨max size of all strings 5 ⟩≡


max_string_size(Strings, MaxLength):-
maplist(length, Strings, Lengths),
max_list(Lengths, MaxLength).
◇

Fragment referenced in 7.

We’ll define a predicate for doing all the co-ordination and overall logic.

⟨equal strings 6 ⟩≡


equal_strings(Strings, Operations):-
equal_strings(Strings, 0, Operations), !.
equal_strings(Strings, Operations, Operations):-
last(Strings, S),
\+ S = [],
all_equal(Strings).
equal_strings(Strings, _, -1):-
last(Strings, S),
S = [].
equal_strings(Strings, OperationsAccum, Operations):-
max_string_size(Strings, MaxLength),
maplist(match_length(MaxLength), Strings, S1),
delete(S1, nil, S2),
subtract(Strings, S2, S4),
maplist(remove_last, S2, S3),
append(S4, S3, S5),
all_equal(S5),
\+ all_empty(S5),
length(S2, Removals),
Operations is OperationsAccum + Removals.
equal_strings(Strings, OperationsAccum, Operations):-
max_string_size(Strings, MaxLength),
maplist(match_length(MaxLength), Strings, S1),
delete(S1, nil, S2),
subtract(Strings, S2, S4),
maplist(remove_last, S2, S3),
append(S4, S3, S5),
\+ all_equal(S5),
length(S2, Removals),
O is OperationsAccum + Removals,
equal_strings(S5, O, Operations).
◇

Fragment referenced in 7.

The rest of the code just wraps this predicate into a file.

"ch-1.p" 7≡


⟨remove last letter 1 ⟩
⟨strings all of the same size 2 ⟩
⟨all strings are equal 3 ⟩
⟨all strings are empty 4 ⟩
⟨max size of all strings 5 ⟩
⟨equal strings 6 ⟩
◇

Sample Run
$ gprolog --consult-file prolog/ch-1.p 
| ?- equal_strings(["abb", "ab", "abc"], Operations). 
 
Operations = 2 
 
yes 
| ?- equal_strings(["ayz", "cyz", "xyz"], Operations). 
 
Operations = -1 
 
yes 
| ?- equal_strings(["yza", "yzb", "yzc"], Operations). 
 
Operations = 3 
 
yes 
| ?-

Part 2: Sort Column

You are given a list of strings of same length. Write a script to make each column sorted lexicographically by deleting any non sorted columns. Return the total columns deleted.

We’ll start with a short predicate for convenience.

⟨column 8 ⟩≡


column(I, L, Column):-
maplist(nth(I), L, Column).
◇

Fragment referenced in 10.

⟨sort column 9 ⟩≡


sort_column(Strings, Removals):-
last(Strings, S),
length(S, L),
findall(R, (
between(1, L, I),
column(I, Strings, Column),
msort(Column, ColumnSorted),
\+ Column == ColumnSorted,
R = Column
), Rs),
length(Rs, Removals).
◇

Fragment referenced in 10.

Finally, let’s assemble our completed code into a single file.

"ch-2.p" 10≡


⟨column 8 ⟩
⟨sort column 9 ⟩
◇

Sample Run
$ gprolog --consult-file prolog/ch-2.p 
| ?- sort_column(["swpc", "tyad", "azbe"], Removals). 
 
Removals = 2 
 
yes 
| ?- sort_column(["cba", "daf", "ghi"], Removals). 
 
Removals = 1 
 
yes 
| ?- sort_column(["a", "b", "c"], Removals). 
 
Removals = 0 
 
yes 
| ?-

References

The Weekly Challenge 314
Generated Code

posted at: 19:05 by: Adam Russell | path: /prolog | permanent link to this entry