I’m developing a form module for my chatbot, one part of the process involves the system intuiting which endpoint to use to send the form according to the JSON properties (all this persisted in the DB with their respective relationships).
Simplifying the problem I need to get an algorithm that is able to receive a “dynamic” filter:
Group A (dynamic filter): ["name", "name", "name", "email", "breed", "age", "age", "school"]
In addition, the algorithm must also receive two-dimensional array as follows:
Group B: (sample) [["name", "age", "email"], ["name", "breed", "age"], ["name", "age"], ["name", "age", "school"], ["name", "email"]]
And get as a final result something like this:
Result: [["name", "email"], ["name", "age", "school"], ["name", "breed", "age"]]
As you can see, the only restriction is when you create an array that matches the filter elements, these filter elements must be removed, so the filter is dynamic.
Looking elsewhere, I am aware I can simplify the process by explicitly indicating to which form each set of properties corresponds, but I would like to develop this algorithm as a personal challenge. Moreover, while elaborating the algorithm I realized that the only failure would occur if two endpoints share the same properties, which is impossible, at least in my case.
Any kind of collaboration is welcome, thank you (my first post).
EDIT 1 (Being clear)
Thanks for comments, as I said, the only condition is that you must obtain the arrays B with the elements of A, I will give you an example of execution:
I have my “dynamic” filter of: [1, 1, 2, 3, 3].
And I have a sample: [[1, 2, 3], [1, 2], [1, 3]].
It looks like the dynamic filter applies for all the elements of the sample, BUT, once you get an array of the sample, you must remove those elements from the filter, that’s why it’s “dynamic”, because it changes, execution:
- Program starts, initial state:
filter: [1, 1, 2, 3, 3]
sample: [[1, 2, 3], [1, 2], [1, 3]]
result: []
- I get the first array of sample and check if their elements match with the filter:
[1, 2, 3]yep, it’s, now my situation is:
filter: [1, 3]
sample: [[1, 2], [1, 3]]
result: [[1, 2, 3,]] (what I got from the sample)
- I get an array that is
[1, 3], oh, yes there is but still –[1, 2]has to be checked.
filter: [] (empty, good work)
sample: [[1, 2]]
result: [[1, 2, 3], [1, 3]]
what if… it takes the wrong route?
The previous example was “simple” because the order helped a lot, but, what would happen if we put [1, 2] at the beginning (the array we know is not valid for the sample)?
Note: I’m going to make the algorithm fall into the error that cannot be solved for now.
- Program starts, initial state:
filter: [1, 1, 2, 3, 3]
sample: [[1, 2], [1, 2, 3], [1, 3]]
result: []
- It takes first array of sample
[1, 2]and it matches with the filter, so:
filter: [1, 3, 3]
sample: [[1, 2, 3], [1, 3]]
result: [[1, 2]]
- It looks nothing is wrong, but, let’s keep checking.
[1, 2, 3]seems is no longer valid, because we no longer have a two in the filter, but[1, 3]it is, okay…
filter: [3]
sample: [[1, 2, 3]]
result: [[1, 2], [1, 3]]
- Well, there is an element still in the filter, we have to keep checking until the filter is empty. But the only element is the sample doesn’t match with the filter, so we can conclude this combination is not valid.
Question: How can my algorithm know which combination was incorrect to try other combinations?
The algorithm should have two endings:
- Here is your result, the filter is empty.
- For all combinations, the filter was never empty, there are no matches.
Typescript Playground
Exercise
If you are interested in knowing the context of my problem, I share the link to the typescript playground where I was solving this problem.
In general aspects, I want to obtain the endpoints according to the attributes linked to the questions that are subsequently related to their answers.
It sounds like an overcomplicated problem (I’m not sure) and there may be simpler ways to do it, but solving the commented algorithm became a personal interest.
3
It’s not clear
- What logic in the sorting
- What logic in matching items including other items (seems greedy, we need to match longest items first)
Otherwise, an attempt based on the rules I’ve understood:
const filter = ["name", "name", "name", "email", "breed", "age", "age", "school"];
const input = [["name", "age", "email"], ["name", "breed", "age"], ["name", "age"], ["name", "age", "school"], ["name", "email"]];
let copy = filter.slice();
const result = input.toSorted((a,b) => b.length-a.length).filter(arr => {
let i = 0;
const filtered = copy.filter(item => !(arr[i] === item && ++i));
if(filtered.length + arr.length === copy.length){
copy = filtered;
return true;
}
});
result.reverse().forEach(arr => console.log(...arr));2