Courbes de Lance
Cette semaine, c'est Damien qui vous propose un #KataOfTheWeek : Courbes de Lance
Briefing du Kata : Imaginons que tu es propriétaire d'un compte Netflix à 4 écrans simultanés. Grand seigneur que tu es, tu as partagé tes identifiants avec plein de gens (en tout cas plus de 3 autres personnes), mais comme tu es prévoyant, tu veux leur envoyer le planning du nombre d'écrans dont tu as besoin, et eux se débrouillent entre eux pour se partager le reste des écrans.
Par exemple, dans la semaine du lundi 05/07/2021 au dimanche 11/07/2021:
- exigence A: tu veux toujours au minimum 1 écran pour toi
- exigence B: le mardi de 20h00 à 00h00, c'est la soirée cinéma "chacun de son côté" de tes parents, donc il te faut 2 écrans de plus
- exigence C: exceptionnellement, tu as promis à ton petit frère de lui réserver un écran ce même mardi à partir de 22h00 jusqu'au lendemain à 02h00
- exigence D: ce même mercredi, ta soeur a besoin d'un écran pour regarder un film avec son copain de 02h00 à 04h00.
Si on combine toutes ces exigences, on obtient le planning suivant:
- de lundi 00h00 à mardi 20h00, il te faut 1 écran
- de mardi 20h00 à mardi 22h00, il te faut 3 écrans
- de mardi 22h00 à mercredi 00h00, il te faut 4 écrans
- de mercredi 00h00 à mercredi 04h00, il te faut 2 écrans
- de mercredi 04h00 jusqu'à la fin de la semaine, il te faut 1 écran.
Ton but est donc de créer une API (un module dans le langage de ton choix, pas une API HTTP) permettant de fournir une collection d'exigences et de récupérer le résultat du calcul du planning à partir de ces exigences.
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur en Java :
import java.time.Instant;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.function.BinaryOperator;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import static io.lalahtalks.lancescurve.StringUtils.indent;
public class LancesCurveComputing {
public static void main(String[] args) {
var requirements = getRequirements();
var lancesCurve = new LancesCurveComputer<>(requirements, 0, Integer::sum).compute();
System.out.println(lancesCurve);
}
private static Collection<Requirement<Integer>> getRequirements() {
var requirementA = getRequirementA();
var requirementB = getRequirementB();
var requirementC = getRequirementC();
var requirementD = getRequirementD();
return List.of(requirementA, requirementB, requirementC, requirementD);
}
private static Requirement<Integer> getRequirementA() {
var requirementAStart = Instant.parse("2021-07-05T00:00:00Z");
var requirementAEnd = Instant.parse("2021-07-12T00:00:00Z");
return new Requirement<>(1, requirementAStart, requirementAEnd);
}
private static Requirement<Integer> getRequirementB() {
var requirementBStart = Instant.parse("2021-07-06T20:00:00Z");
var requirementBEnd = Instant.parse("2021-07-07T00:00:00Z");
return new Requirement<>(2, requirementBStart, requirementBEnd);
}
private static Requirement<Integer> getRequirementC() {
var requirementCStart = Instant.parse("2021-07-06T22:00:00Z");
var requirementCEnd = Instant.parse("2021-07-07T02:00:00Z");
return new Requirement<>(1, requirementCStart, requirementCEnd);
}
private static Requirement<Integer> getRequirementD() {
var requirementDStart = Instant.parse("2021-07-07T02:00:00Z");
var requirementDEnd = Instant.parse("2021-07-07T04:00:00Z");
return new Requirement<>(1, requirementDStart, requirementDEnd);
}
private LancesCurveComputing() {
}
}
final class LancesCurveComputer<T> {
private final Collection<Requirement<T>> requirements;
private final T identity;
private final BinaryOperator<T> reducer;
LancesCurveComputer(Collection<Requirement<T>> requirements, T identity, BinaryOperator<T> reducer) {
this.requirements = requirements;
this.identity = identity;
this.reducer = reducer;
}
LancesCurve<T> compute() {
var abscissas = getOrderedAbscissas();
var intervals = getOrderedIntervals(abscissas);
var resultRequirements = getOrderedRequirements(intervals);
var smoothed = smooth(resultRequirements);
return new LancesCurve<>(smoothed);
}
private List<Requirement<T>> smooth(List<Requirement<T>> requirements) {
if (requirements.isEmpty()) {
return List.of();
}
var previous = requirements.get(0);
var smoothed = new ArrayList<Requirement<T>>();
for (var i = 1; i < requirements.size(); i++) {
var current = requirements.get(i);
if (current.getValue().equals(previous.getValue())) {
previous = new Requirement<>(
previous.getValue(),
previous.getInterval().getStart(),
current.getInterval().getEnd());
} else {
smoothed.add(previous);
previous = current;
}
}
smoothed.add(previous);
return List.copyOf(smoothed);
}
private List<Requirement<T>> getOrderedRequirements(List<InstantInterval> intervals) {
var resultRequirements = new ArrayList<Requirement<T>>();
for (var interval : intervals) {
var value = requirements.stream()
.filter(r -> r.getInterval().intersects(interval))
.map(Requirement::getValue)
.reduce(identity, reducer);
var resultRequirement = new Requirement<>(value, interval);
resultRequirements.add(resultRequirement);
}
return resultRequirements;
}
private List<InstantInterval> getOrderedIntervals(List<Instant> orderedAbscissas) {
var intervals = new ArrayList<InstantInterval>();
for (var i = 0; i < orderedAbscissas.size() - 1; i++) {
var start = orderedAbscissas.get(i);
var end = orderedAbscissas.get(i + 1);
var interval = new InstantInterval(start, end);
intervals.add(interval);
}
return intervals;
}
private List<Instant> getOrderedAbscissas() {
return requirements.stream()
.flatMap(it -> Stream.of(it.getInterval().getStart(), it.getInterval().getEnd()))
.distinct()
.sorted()
.collect(Collectors.toList());
}
}
final class InstantInterval {
private final Instant start;
private final Instant end; // exclusive
InstantInterval(Instant start, Instant end) {
if (!end.isAfter(start)) {
throw new IllegalArgumentException("end must be strictly after start");
}
this.start = start;
this.end = end;
}
Instant getStart() {
return start;
}
Instant getEnd() {
return end;
}
boolean contains(Instant instant) {
return !instant.isBefore(start)
&& instant.isBefore(end);
}
boolean containsExcludingBounds(Instant instant) {
return instant.isAfter(start)
&& instant.isBefore(end);
}
boolean intersects(InstantInterval other) {
return contains(other.start) || containsExcludingBounds(other.end);
}
}
final class Requirement<T> {
private final T value;
private final InstantInterval interval;
Requirement(T value, InstantInterval interval) {
this.value = value;
this.interval = interval;
}
Requirement(T value, Instant start, Instant end) {
this(value, new InstantInterval(start, end));
}
T getValue() {
return value;
}
InstantInterval getInterval() {
return interval;
}
@Override
public String toString() {
return "Requirement {" +
"\n value = " + value +
"\n start = " + interval.getStart() +
"\n end = " + interval.getEnd() +
"\n}";
}
}
final class LancesCurve<T> {
private final List<Requirement<T>> requirements;
LancesCurve(List<Requirement<T>> requirements) {
this.requirements = List.copyOf(requirements);
}
@Override
public String toString() {
var builder = new StringBuilder();
requirements.forEach(it -> builder.append('\n').append(it));
return "LancesCurve {" +
indent(builder.toString()) +
"\n}";
}
}
class StringUtils {
static String indent(String s) {
return s.replace("\n", "\n ");
}
private StringUtils() {
}
}
Votre équipe TakiVeille