1 /*
2  *  Make.org Core API
3  *  Copyright (C) 2018 Make.org
4  *
5  * This program is free software: you can redistribute it and/or modify
6  *  it under the terms of the GNU Affero General Public License as
7  *  published by the Free Software Foundation, either version 3 of the
8  *  License, or (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU Affero General Public License for more details.
14  *
15  *  You should have received a copy of the GNU Affero General Public License
16  *  along with this program.  If not, see <https://www.gnu.org/licenses/>.
17  *
18  */
19 
20 package org.make.api.sequence
21 
22 import org.make.api.proposal.ProposalScorer
23 import org.make.api.proposal.ProposalScorer.VotesCounter
24 import org.make.api.technical.MakeRandom
25 import org.make.core.DateHelper._
26 import org.make.core.proposal.ProposalKeywordKey
27 import org.make.core.proposal.indexed.Zone.{Consensus, Controversy}
28 import org.make.core.proposal.indexed.{IndexedProposal, Zone}
29 import org.make.core.sequence.{
30   ExplorationSequenceConfiguration,
31   ExplorationSortAlgorithm,
32   SpecificSequenceConfiguration
33 }
34 import org.make.core.sequence.ExplorationSequenceConfiguration.SequenceThresholds
35 import org.make.core.technical.CollectionUtils.ImprovedSeq
36 import org.make.core.technical.RefinedTypes.Ratio
37 import eu.timepit.refined.auto._
38 
39 import scala.Ordering.Double.IeeeOrdering
40 import scala.annotation.tailrec
41 import scala.collection.mutable.{HashSet => MSet}
42 
43 object SelectionAlgorithm {
44 
45   object ExplorationSelectionAlgorithm {
46     def selectProposalsForSequence(
47       configuration: ExplorationSequenceConfiguration,
48       nonSequenceVotesWeight: Double,
49       includedProposals: Seq[IndexedProposal],
50       newProposals: Seq[IndexedProposal],
51       testedProposals: Seq[IndexedProposal],
52       userSegment: Option[String]
53     ): Seq[IndexedProposal] = {
54 
55       // Choose new proposals first and complete with enough tested proposals.
56       // this setting will give more sequence fallbacks in the beginning of consultations
57       // but should remove the need of fallback in the end of consultations, in the "vote-only" phase
58       val chosenNewProposals: Seq[IndexedProposal] = chooseNewProposals(configuration, includedProposals, newProposals)
59 
60       val testedProposalsConfiguration = createTestedProposalsConfiguration(
61         configuration,
62         nonSequenceVotesWeight,
63         includedProposals,
64         userSegment,
65         chosenNewProposals.size
66       )
67 
68       val deDuplicatedTestedProposals = removeAuthorDuplication(chosenNewProposals, testedProposals)
69       val chosenTestedProposals = chooseTestedProposal(deDuplicatedTestedProposals, testedProposalsConfiguration)
70 
71       includedProposals ++ MakeRandom.shuffleSeq(chosenNewProposals ++ chosenTestedProposals)
72     }
73 
74     private def chooseNewProposals(
75       configuration: ExplorationSequenceConfiguration,
76       includedProposals: Seq[IndexedProposal],
77       newProposals: Seq[IndexedProposal]
78     ): Seq[IndexedProposal] = {
79       val availableSpace = configuration.sequenceSize - includedProposals.size
80       val neededNewProposals = Math.ceil(configuration.newRatio * availableSpace).toInt
81 
82       NewProposalsChooser.choose(newProposals, neededNewProposals)
83     }
84 
85     private def createTestedProposalsConfiguration(
86       configuration: ExplorationSequenceConfiguration,
87       nonSequenceVotesWeight: Double,
88       includedProposals: Seq[IndexedProposal],
89       userSegment: Option[String],
90       chosenNewProposalsCount: Int
91     ): TestedProposalsSelectionConfiguration = {
92       val votesCounter: VotesCounter = if (userSegment.isDefined) {
93         VotesCounter.SegmentVotesCounter
94       } else {
95         VotesCounter.SequenceVotesCounter
96       }
97 
98       val neededTested = Math.max(configuration.sequenceSize - chosenNewProposalsCount - includedProposals.size, 0)
99       val neededControversies: Int = Math.round(neededTested * configuration.controversyRatio).toInt
100       val neededTops = neededTested - neededControversies
101 
102       val controversySorter = Sorter.parse(configuration.controversySorter)
103       val topSorter = Sorter.parse(configuration.topSorter)
104 
105       TestedProposalsSelectionConfiguration(
106         votesCounter = votesCounter,
107         ratio = nonSequenceVotesWeight,
108         neededControversies = neededControversies,
109         controversySorter = controversySorter,
110         neededTops = neededTops,
111         topSorter = topSorter,
112         keywordsThreshold = configuration.keywordsThreshold,
113         candidatesPoolSize = configuration.candidatesPoolSize,
114         sequenceThreshold = configuration.sequenceThresholds
115       )
116     }
117 
118     @SuppressWarnings(Array("org.wartremover.warts.MutableDataStructures"))
119     def resolveIgnoredKeywords(proposals: Seq[IndexedProposal], keywordsThreshold: Ratio): MSet[ProposalKeywordKey] = {
120       if (proposals.isEmpty) {
121         MSet.empty
122       } else {
123         val maxOccurrences = Math.floor(keywordsThreshold * proposals.size).toInt
124         proposals
125           .flatMap(_.keywords)
126           .countOccurencesBy[ProposalKeywordKey](_.key)
127           .collect {
128             case (key, occurences) if occurences >= maxOccurrences => key
129           }
130           .to(MSet)
131       }
132     }
133 
134     private def chooseTestedProposal(
135       testedProposals: Seq[IndexedProposal],
136       configuration: TestedProposalsSelectionConfiguration
137     ): Seq[IndexedProposal] = {
138       val (tops, controversies) =
139         testedProposals
140           .zip(
141             testedProposals
142               .map(proposal => {
143                 ProposalScorer(proposal.votes, configuration.votesCounter, configuration.ratio)
144               })
145           )
146           .collect({
147             case (proposal, scorer) if scorer.sampledZone(configuration.sequenceThreshold) == Consensus =>
148               ZonedProposal(proposal, Consensus, scorer.topScore.sample)
149             case (proposal, scorer) if scorer.sampledZone(configuration.sequenceThreshold) == Controversy =>
150               ZonedProposal(proposal, Controversy, scorer.controversy.sample)
151           })
152           .partition(_.zone == Consensus)
153 
154       // Applying the different selection algorithms consists in sorting the proposals in some order,
155       // and then take enough of them, using the same de-duplication + equalizer everytime.
156 
157       val sortedControversies = configuration.controversySorter.sort(controversies)
158       val sortedTops = configuration.topSorter.sort(tops)
159 
160       val ignoredKeywords = resolveIgnoredKeywords(testedProposals, configuration.keywordsThreshold)
161 
162       val chosenControversies = TestedProposalsChooser.choose(
163         sortedControversies,
164         configuration.neededControversies,
165         ignoredKeywords,
166         configuration.candidatesPoolSize
167       )
168       val availableTops = removeAuthorDuplication(chosenControversies, sortedTops)
169       chosenControversies ++
170         TestedProposalsChooser.choose(
171           availableTops,
172           configuration.neededTops,
173           ignoredKeywords,
174           configuration.candidatesPoolSize
175         )
176     }
177 
178     @SuppressWarnings(Array("org.wartremover.warts.MutableDataStructures"))
179     private def removeAuthorDuplication(
180       chosenProposals: Seq[IndexedProposal],
181       candidates: Seq[IndexedProposal]
182     ): Seq[IndexedProposal] = {
183       val chosenAuthors = chosenProposals.map(_.author.userId).to(MSet)
184       candidates.filterNot(p => chosenAuthors.contains(p.author.userId))
185     }
186 
187     final case class TestedProposalsSelectionConfiguration(
188       votesCounter: VotesCounter,
189       ratio: Double,
190       neededControversies: Int,
191       controversySorter: Sorter,
192       neededTops: Int,
193       topSorter: Sorter,
194       keywordsThreshold: Ratio,
195       candidatesPoolSize: Int,
196       sequenceThreshold: SequenceThresholds
197     )
198 
199     final case class ZonedProposal(proposal: IndexedProposal, zone: Zone, score: Double)
200 
201     sealed trait Sorter {
202       def sort(proposals: Seq[ZonedProposal]): Seq[IndexedProposal]
203     }
204 
205     object Sorter {
206       def parse(name: ExplorationSortAlgorithm): Sorter = {
207         name match {
208           case ExplorationSortAlgorithm.Bandit    => BanditSorter
209           case ExplorationSortAlgorithm.Equalizer => EqualizerSorter
210           case ExplorationSortAlgorithm.Random    => RandomSorter
211         }
212       }
213     }
214 
215     object BanditSorter extends Sorter {
216       override def sort(proposals: Seq[ZonedProposal]): Seq[IndexedProposal] = {
217         proposals.sortBy(-_.score).map(_.proposal)
218       }
219     }
220 
221     object RandomSorter extends Sorter {
222       override def sort(proposals: Seq[ZonedProposal]): Seq[IndexedProposal] = {
223         MakeRandom.shuffleSeq(proposals).map(_.proposal)
224       }
225     }
226 
227     object EqualizerSorter extends Sorter {
228       override def sort(proposals: Seq[ZonedProposal]): Seq[IndexedProposal] = {
229         proposals.map(_.proposal).sortBy(_.votesSequenceCount)
230       }
231     }
232 
233     object NewProposalsChooser {
234       def choose(candidates: Seq[IndexedProposal], neededCount: Int): Seq[IndexedProposal] = {
235         candidates.sortBy(_.createdAt).distinctBy(_.author.userId).take(neededCount)
236       }
237     }
238 
239     object TestedProposalsChooser {
240 
241       /**
242         * Chooses some proposals in a sorted list of proposals and preserve a few properties:
243         * - no keyword duplication in the list (ie. a given keyword should appear only once)
244         * - no author duplication in the list
245         * - proposals with fewer votes will be boosted (see below)
246         *
247         * In order to boost the proposals with fewer votes, instead of taking the first element of the list,
248         * the one with the fewest number of sequence votes in the 10 first proposals is chosen.
249         * The proposal pool is then cleaned of proposals sharing any keyword / author with that proposal
250         * before choosing the next proposal.
251         *
252         * @param candidates the whole pool of proposals from which to choose
253         * @param neededCount the target number of proposals needed
254         * @param ignoredKeywords keywords that shouldn't be used to deduplicate proposals
255         * @return a list consisting of at most the required number of proposals, without any duplication.
256         *         The result can be empty or contain fewer elements than required.
257         */
258       def choose(
259         candidates: Seq[IndexedProposal],
260         neededCount: Int,
261         ignoredKeywords: MSet[ProposalKeywordKey],
262         candidatesPoolSize: Int
263       ): Seq[IndexedProposal] = {
264         chooseRecursively(List.empty, candidates, neededCount, ignoredKeywords, candidatesPoolSize)
265       }
266 
267       @tailrec
268       private def chooseRecursively(
269         accumulator: List[IndexedProposal],
270         candidates: Seq[IndexedProposal],
271         neededCount: Int,
272         ignoredKeywords: MSet[ProposalKeywordKey],
273         candidatesPoolSize: Int
274       ): Seq[IndexedProposal] = {
275         if (neededCount <= 0) {
276           accumulator
277         } else {
278           candidates.take(candidatesPoolSize).minByOption(_.votesSequenceCount) match {
279             case None => accumulator
280             case Some(chosen) =>
281               val newAccumulator = chosen :: accumulator
282               if (neededCount <= 1) {
283                 newAccumulator
284               } else {
285                 chooseRecursively(
286                   accumulator = newAccumulator,
287                   candidates = deduplicate(chosen, candidates, ignoredKeywords),
288                   neededCount = neededCount - 1,
289                   ignoredKeywords,
290                   candidatesPoolSize
291                 )
292               }
293           }
294         }
295       }
296 
297       @SuppressWarnings(Array("org.wartremover.warts.MutableDataStructures"))
298       private def deduplicate(
299         chosen: IndexedProposal,
300         candidates: Seq[IndexedProposal],
301         ignoredKeywords: MSet[ProposalKeywordKey]
302       ): Seq[IndexedProposal] = {
303         val forbiddenKeywords = chosen.keywords.filterNot(k => ignoredKeywords.contains(k.key)).to(MSet)
304         candidates.filter { proposal =>
305           !proposal.keywords.exists(forbiddenKeywords.contains) && chosen.author.userId != proposal.author.userId
306         }
307       }
308     }
309   }
310 
311   object RoundRobinSelectionAlgorithm {
312 
313     /*
314     Returns the list of proposal to display in the sequence
315     The proposals are chosen such that:
316     - if they are imposed proposals (includeList) they will appear first
317     - the rest is only new proposals to test (less than newProposalVoteCount votes)
318     - new proposals are tested in a round robin mode until they reach newProposalVoteCount votes
319     - tested proposals are filtered out if their engagement rate is too low
320     - the non imposed proposals are ordered randomly
321      */
322     def selectProposalsForSequence(
323       sequenceConfiguration: SpecificSequenceConfiguration,
324       includedProposals: Seq[IndexedProposal],
325       newProposals: Seq[IndexedProposal],
326       testedProposals: Seq[IndexedProposal]
327     ): Seq[IndexedProposal] = {
328 
329       val proposalsPool: Seq[IndexedProposal] = newProposals ++ testedProposals
330 
331       // balance proposals between new and tested
332       val sequenceSize: Int = sequenceConfiguration.sequenceSize
333       val includedSize: Int = includedProposals.size
334 
335       val proposalsToChoose: Int = sequenceSize - includedSize
336 
337       val proposals = proposalsPool.sortBy(_.votesSequenceCount).take(proposalsToChoose)
338 
339       includedProposals ++ MakeRandom.shuffleSeq(proposals)
340     }
341 
342   }
343 
344   object RandomSelectionAlgorithm {
345 
346     def selectProposalsForSequence(
347       sequenceConfiguration: SpecificSequenceConfiguration,
348       includedProposals: Seq[IndexedProposal],
349       newProposals: Seq[IndexedProposal],
350       testedProposals: Seq[IndexedProposal]
351     ): Seq[IndexedProposal] = {
352 
353       val excludedIds = includedProposals.map(_.id)
354       val candidates = (newProposals ++ testedProposals)
355         .filter(p => !excludedIds.contains(p.id))
356       val shuffled = MakeRandom.shuffleSeq(candidates)
357       includedProposals ++ shuffled.take(sequenceConfiguration.sequenceSize - includedProposals.size)
358     }
359   }
360 }