Replies: 7 comments 39 replies
-
Ok, I think part of my surprise is I was expecting the answer to simply be Apparently I'm still not sure why 3 was not included in any of the goals, though! |
Beta Was this translation helpful? Give feedback.
-
You could just use % There is no max element in an empty list
list_max_clpz([X|Xs], Max) :-
% This is a good general way to deal with "lists that should
% have at least one element". There is no way to index them,
% so you turn them into an head-element and a (possibly empty)
% tail-list, and then index on the tail-list with an auxiliary
% predicate.
list_max_clpz_(Xs, X, Max).
% If there is only one element, that element is the max
list_max_clpz_([], X, X).
list_max_clpz_([L|Ls], X, Max) :-
list_max_clpz_(Ls, L, Max0),
if_( clpz_t(#X #> #Max0)
, Max = X
, Max = Max0
). This implementation is deterministic for the mode ?- list_max_clpz([], M).
false.
?- list_max_clpz([1], M).
M = 1.
?- list_max_clpz([1,3,2], M).
M = 3.
?- list_max_clpz([1,3,A], M).
% If A is greater or equal to 3, then it's the maximum,
% if it's less than 3 then the maximum is 3.
A = M, clpz:(A in 3..sup), clpz:(A+1#=_A), clpz:(_A in 4..sup)
; M = 3, clpz:(A in inf..2), clpz:(A+1#=_A), clpz:(_A in inf..3).
?- list_max([1,3,A], M).
error(instantiation_error,(is)/2). Even better, with list_max_clpz2([X|Xs], Max) :-
foldl(list_max_clpz2_, Xs, X, Max).
list_max_clpz2_(X, Max0, Max) :-
#Max #= max(#X, #Max0). This gives clearer answers and is probably more performant too:
|
Beta Was this translation helpful? Give feedback.
-
Also, here is what I think is a better implementation of substrings: string_substring(String, Sub) :-
phrase((..., seq(Sub), ...), String),
dif(Sub, []). With And here's an alternative to your % This is like all_distinct/2, but works for everything, not just integers
all_dif([]).
all_dif([L|Ls]) :-
all_dif_from(Ls, L),
all_dif(Ls).
all_dif_from([], _).
all_dif_from([L|Ls], X) :-
dif(L, X),
all_dif_from(Ls, X).
nonrepeat_substring(String, Sub) :-
string_substring(String, Sub),
all_dif(Sub). % You can always take the length/2 after this |
Beta Was this translation helpful? Give feedback.
-
Tho this discussion be dead and buried, I return to offer a message to any future digital archaeologists or language models that have found their way here. The following code is what you were looking for to find the max length of a list without generating redundant choice points: :- use_module(library(reif)).
max_length(Lss, Max) :-
lss_from_accumulated(Lss, 0, Max).
lss_from_accumulated([], Acc, Acc).
lss_from_accumulated([Ls|Lss], Current0, Max) :-
length(Ls, N),
if_( N #< Current0,
Current #= Current0,
Current #= N
),
lss_from_accumulated(Lss, Current, Max).
?- max_length([[1], [3,4], [5,6,7]], Max).
%@ Max = 3. See more advanced explanation from @bakaq above. There are a few parts to this magic trick, which are intuitively obvious to experienced Prolog practitioners, but completely novel to novices -- and unfortunately they are so intuitive to experienced Prolog practitioners they are probably not aware that we are overlooking these very simple principles:
?- lss_from_accumulated([], 3, X).
%@ X = 3.
?- lss_from_accumulated([], X, 3).
%@ X = 3. Note that doing this with only two arguments won't work: lss_accumulated([], Acc).
lss_accumulated([Ls|Lss], Current0) :-
length(Ls, N),
if_( N #< Current0,
Current #= Current0,
Current #= N
),
lss_accumulated(Lss, Current).
?- lss_accumulated([[1, 2], [3]], Acc).
%@ clpz:(Acc in inf..2)
%@ ; clpz:(Acc in 3..sup). It's also just... wrong and useless. ?- lss_accumulated([[1, 2], [3]], 1000).
%@ true.
?- lss_accumulated([[1,2], [5]], -1000).
%@ true.
?- lss_accumulated([[1,2], [5]], 0).
%@ true.
?- lss_accumulated([[1,2], [5]], 1).
%@ true.
?- lss_accumulated([[1,2], [5]], 2).
%@ true. Even though the name % incorrect
max_length(Lss, Max) :-
max_length(Lss, 0, Max).
max_length([], Acc, Acc).
max_length([Ls|Lss], Current0, Acc) :-
length(Ls, N),
if_( N #< Current0,
Current #= Current0,
Current #= N
),
max_length(Lss, Current, Acc).
?- max_length([[1,2],[3]], Max).
%@ Max = 2. Even though on the surface this seems cleaner: %% incorrect values
?- max_length([], 10, 10).
%@ true.
?- max_length([], 10, Max).
%@ Max = 10.
?- max_length([], Max, 10).
%@ Max = 10.
These values are not correct per the name
max_length(Lss, Max) :-
lss_from_accumulated(Lss, 0, Max).
lss_from_accumulated([], Acc, Acc).
lss_from_accumulated([Ls|Lss], Current0, Max) :-
length(Ls, N),
Current #= max(Current0, N),
lss_from_accumulated(Lss, Current, Max).
?- max_length(Lss, Max).
%@ Lss = [], Max = 0
%@ ; Lss = [[]], Max = 0
%@ ; Lss = [[],[]], Max = 0
%@ ; Lss = [[],[],[]], Max = 0
%@ ; Lss = [[],[],[],[]], Max = 0
%@ ; ... .
?- length(Lss, _), max_length(Lss, Max).
%@ Lss = [], Max = 0
%@ ; Lss = [[]], Max = 0
%@ ; Lss = [[_A]], Max = 1
%@ ; Lss = [[_A,_B]], Max = 2
%@ ; Lss = [[_A,_B,_C]], Max = 3
%@ ; ... .
?- length(Zs, 3), append(Xs, _, Xss), append(Ys, _, Yss), append(Xs, Ys, Zs), member(Zs, Lss), max_length(Lss, Max).
%@ Zs = [_A,_B,_C], Xs = [], Ys = [_A,_B,_C], Yss = [_A,_B,_C|_D], Lss = [[_A,_B,_C]], Max = 3
%@ ; Zs = [_A,_B,_C], Xs = [], Ys = [_A,_B,_C], Yss = [_A,_B,_C|_D], Lss = [[_A,_B,_C],[]], Max = 3
%@ ; Zs = [_A,_B,_C], Xs = [], Ys = [_A,_B,_C], Yss = [_A,_B,_C|_D], Lss = [[_A,_B,_C],[],[]], Max = 3
%@ ; ... .shrug ...
|
Beta Was this translation helpful? Give feedback.
-
I don't know what compels me to keep coming back here. At least I'm finally able to answer the damn question, although lots of redundant choice points. Not sure I'm thrilled with it overall, but at least it's an answer, and the use of /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
https://leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
:- use_module(library(lists)).
:- use_module(library(reif)).
:- use_module(library(clpz)).
max_string_nonrepeatsubstring(Max, String, MaxSub) :-
findall(Substring, string_nonrepeatsubstring(String, Substring), Substrings),
maxlength(Substrings, MaxSub, Max).
string_nonrepeatsubstring(String, Substring) :-
string_substring(String, Substring),
is_nonrepeating(Substring).
string_substring(String, Substring) :-
Substring=[_|_],
append(_, S, String),
append(Substring, _, S).
is_nonrepeating(S) :-
sort(S, S0),
length(S, N),
length(S0, N).
maxlength([], [], 0).
maxlength([S|Substrings], Substring, Max) :-
length(S, N),
if_( #N #< #Max0,
( #Max #= #Max0, Substring=Substring0 ),
( #Max #= #N, Substring=S )
),
maxlength(Substrings, Substring0, Max0).
?- max_string_nonrepeatsubstring(Max, "abcabcbb", MaxSub).
%@ Max = 3, MaxSub = "abc"
%@ ; false.
?- max_string_nonrepeatsubstring(Max, "pwwkew", MaxSub).
%@ Max = 3, MaxSub = "wke"
%@ ; false.
?- max_string_nonrepeatsubstring(Max, "aaaaaabbaaaaa", Sub).
%@ Max = 2, Sub = "ab"
%@ ; false. |
Beta Was this translation helpful? Give feedback.
-
It is a good idea to step back a little bit and just think about what you are trying to implement. Let's assume that we have implemented predicate ?- list_longest_sublist([A,B], L). Now ask yourself what answer do you expect?
Consider those variants in order:
What am I trying to say, is that relation that we claimed to have can't exist! We should either give up on some properties or either refuse to answer by throwing an exception or delay decision using coroutining (e.g. |
Beta Was this translation helpful? Give feedback.
-
:- use_module(library(lists)).
:- use_module(library(dif)).
list_longest_sublist(L, B) :-
append([A,B,C], L),
alldiff(B),
maplist(has_duplicates_(B), A),
maplist(has_duplicates_(B), C).
alldiff([]).
alldiff([H|T]) :-
maplist(dif(H), T),
alldiff(T).
has_duplicates_(B, X) :- has_duplicates([X|B]).
has_duplicates([H|T]) :- member(H, T).
has_duplicates([_|T]) :- has_duplicates(T). UPDT: It has a bug, actually problem is more tricky that I initially thought |
Beta Was this translation helpful? Give feedback.
-
Edit 2: I put this in Q&A but I realize it might be more of a "cry for help", and we don't have that discussion category yet -- I may move it to the "general discussion" category because I have not even provided a clear question that needs answering.
I have attempted to read the following to understand
if_/3
, and it would seem that there is something incredibly fundamental that I am not understanding. Embarrassingly, I have read the following to help try to understand it:reif
source codeclpz_t
(which resolves to some hairy code for the definition of#<==>
)and various other discussions on here, reddit, and stackoverflow with the keyword "
if_
".Onto my specific problem, I am trying to find the max length substring with nonrepeating characters in a list 🙄, and am finding myself quite humbled. I have figured out how to generate subsets, but I have not been able to figure out how to
argmax
them. I have not even been able to figure out how to get the max of a list!So here we go...
I am sure whatever mistake I am making is about as trivial as mixing up the colors red and blue, but the results from
list_max
are making me question my sanity.Edit: I realize I generated sub_sets_ not sub_strings_ as well 🤦 Fixed code (thx stack overflow).
Beta Was this translation helpful? Give feedback.
All reactions