Finden Sie Brückentage in einer Liste von Tagen

Question

Ich möchte "Brückentage" aus einer Liste von Tagen finden. Die Liste:

days = [ 
%{value: ~D[2017-04-01], categories: ["weekend"]}, 
%{value: ~D[2017-04-02], categories: ["weekend"]}, 
%{value: ~D[2017-04-03], categories: []}, 
%{value: ~D[2017-04-04], categories: []}, 
... 
%{value: ~D[2017-04-13], categories: ["bank holiday"]}, 
%{value: ~D[2017-04-14], categories: ["bank holiday"]}, 
%{value: ~D[2017-04-15], categories: ["weekend"]}, 
%{value: ~D[2017-04-16], categories: ["weekend", "bank holiday"]}, 
... ] 

Der Monat als auf der Webseite gemacht:

Jemand, der will seine/ihre Urlaubstage maximieren würde, weil die einen Urlaub am 10., 11. und 12. nehmen würde zu einem 10-tägigen Urlaub (8. - 17.) für eine Investition von nur 3 Ferientagen führen.

Ich möchte eine Funktion bridge_days(days, number_of_invested_vacation_days) schreiben, die eine Liste dieser drei Tage [~D[2017-04-10], ~D[2017-04-11], ~D[2017-04-12]] ergibt, wenn sie mit bridge_days(days, 3) aufgerufen wird. 3 ist die Anzahl der investierten Urlaubstage.

Ein anderer Monat Beispiel:

bridge_days(days, 1) in [~D[2017-05-26]] weil eine Investition von 1 Urlaubstag ergibt 4 Tage Urlaub zur Folge hätte.

Eigentlich würde bridge_days/2 oft zu einer Liste von Listen führen, weil es oft mehrere Optionen gibt.

Mein Ansatz besteht darin, die Liste durchzuschleifen und +1 und -1 jeden Tages zu vergleichen. Das Problem ist, dass es ewig dauern muss.

Gibt es einen schlaueren Weg als diese rohe Gewalt anzuwenden, um dieses Problem zu lösen?

Answer 1

Hier ist eine Idee für eine Bruteforce O(n^2) Algorithmus, der für kurze Listen ziemlich schnell sein sollte. Ich werde eine vereinfachte Darstellung der Tage verwenden: eine Liste von Booleschen Werten. true bedeutet, es ist ein Urlaub, false bedeutet, dass es nicht ist. So funktioniert der Algorithmus:

Wir betrachten jeden Index der Liste als möglichen Starttag.

Für jeden Index finden wir die Anzahl der Tage, die wir mit der gegebenen Anzahl von Urlauben hätten haben können. Dafür schneiden wir die alten Tage ab und nehmen dann unter Verwendung der reduce_while die Tage, bis wir alle Urlaube genutzt haben (oder die Liste endet). Wir verfolgen auch die Anzahl der Feiertage.

Wir verwenden Enum.max_by, um den obigen Schritt auf jeden Tag anzuwenden und den besten Tag zurück zu bekommen, um den Urlaub zu beginnen. Sie können die tatsächlichen Urlaubstage durch Iterieren von diesem Index erhalten.

defmodule A do 
    def go(days, vacation) do 
    0..(length(days) - 1) 
    |> Enum.max_by(fn from -> 
     days |> Enum.drop(from) |> Enum.reduce_while({0, 0}, fn holiday?, {collected, taken} -> 
     cond do 
      # If it's a holiday, we've collected one day without consuming more vacations. 
      holiday? -> {:cont, {collected + 1, taken}} 
      # If we've taken all vacations possible, we halt. 
      vacation == taken -> {:halt, {collected, taken}} 
      # Otherwise, we collect another day and also consume one vacation day. 
      true -> {:cont, {collected + 1, taken + 1}} 
     end 
     end) 
     |> elem(0) 
    end) 
    end 
end 

t = true 
f = false 
# April from your screenshot. 
days = [t, t, f, f, f, f, f, t, t, f, f, f, t, t, t, t, t, f, f, f, f, t, t, f, f, f, f, f, t, t] 
IO.inspect A.go(days, 3) 

Ausgang:

7 

So ist der achte Tag des Monats ist der beste Tag, um den Urlaub zu starten, die Ihre Beschreibung passt.

Answer 2

Sie haben einen Algorithmus angefordert. Ich glaube, dass der entscheidende Punkt darin besteht, Ihre Tage auf eine Liste von "dienstfreien/arbeitsfreien" Tagen zu reduzieren. In diesem function, haben Sie die folgenden bridge_days(collapsed_days, 3)

:

• Suche nach dem kleinsten

  collapsed_days = [ 
      {:off, 2}, 
      {:on, 5}, {:off, 2}, 
      {:on, 3}, {:off, 5}, 
      {:on, 4}, {:off, 2}, 
      {:on, 5}, {:off, 2} 
  ] 
  

  Jetzt ist Ihre function Brücke Tage wäre wie folgt: Für April dies entspräche Anzahl der Diensttage, in diesem Fall {:on, 3}

• So viele Urlaubstage entsprechend anwenden, so wird es: {:off, 3}

• Collapse resultierenden konsekutiven {:off, _} Tage, so wird die Liste:

  [ {: off, 2}, {: on, 5}, {: Aus, 10}, {: on, 4}, {: off, 2}, { : on, 5}, {: off, 2} ]

• im Fall, dass Sie mehr Urlaubstage haben anzuwenden, dann markieren Sie sie entsprechend an. zum Beispiel bridge_days(collapsed_days, 5), zusätzlich zu {:off, 10}, müssen Sie auch eine {:off, 2} erstellen, indem Sie diese Tage unmittelbar vor oder nach {:off, 10} nehmen.

• Für den Fall, dass Sie weniger Urlaubstage als die kleinsten {:on, _} Betrag haben, dann bewerben Sie sich so viele wie Sie können.

Ich glaube, dass dies immer in der optimalen Lösung führen soll, aber ich kann falsch sein, wie ich es nicht mehr aus dem Weg gegangen, diese zu mathematisch Beweis der Fall zu sein. Wenn Sie nicht sehen können, wie Sie dies mathematisch beweisen können, versuchen Sie es durch Erschöpfung zu beweisen, indem Sie alle Randfälle testen.

Da Sie die genaue im Gegensatz zu einer einfachen Zahl zurückgeben müssen, kann es am besten sein, mit Triplets zu arbeiten: {:off, 2, [~D[2017-04-01], ~D[2017-04-02]]} stattdessen, und fusionieren Sie Ihre Listen entsprechend.

Bitte geben Sie Feedback in den Kommentaren, wenn Sie einen Kantenfall finden, der diesen Ansatz unterbricht.