Die Einrichtung

Angenommen , sind Sie gegebenen n Sicherungen, mit 1 ≤ n ≤ 5, von denen jeder einen Meter lang, und wo jede Sicherung hat einen zugehörigen Verbrennungsrate von N Meter pro D Stunden.

Eine Sicherung kann an einem oder an beiden Enden gezündet, anschließend an einem oder an beiden Enden gelöscht, erneut gezündet, usw. werden, und zwar so oft, bis die Sicherung vollständig verbraucht ist. Sie können Sicherungen augenblicklich anzünden und löschen und genau beobachten, wann eine Sicherung vollständig verbraucht (durchgebrannt) ist.

Eine Sicherung kann nur an ihren Enden durchtrennt oder entzündet werden.

Ein solcher Aufbau ermöglicht ein unendlich genaues Zeitgebungssystem, indem die Zeit zwischen zwei Zünd- / Verbrauchsereignissen gemessen wird. Zum Beispiel können Sie bei zwei Sicherungen mit einer Brenngeschwindigkeit von 1 Meter pro Stunde genau 45 Minuten (3/4 Stunden) messen

1. gleichzeitig: Zünden Sie die erste Sicherung an beiden Enden an, zünden Sie die zweite Sicherung an einem Ende an und markieren Sie den Beginn Ihres Zeitintervalls
2. Anzünden des zweiten Endes der zweiten Sicherung in dem Moment, in dem die erste Sicherung verbraucht ist (30 Minuten später)
3. Markieren Sie das Ende Ihres Zeitintervalls in dem Moment, in dem die zweite Sicherung verbraucht ist (15 Minuten später).

Die Herausforderung

Ausgehend von einer Bruchzahl von Stunden t und einer Menge von n Brüchen, die die exakten Brennraten von n Sicherungen darstellen, schreiben Sie ein Programm oder eine Funktion, die einen wahren Wert ausgibt / zurückgibt, wenn t Stunden durch systematisches Brennen der Sicherungen genau gemessen werden können, oder a sonst falscher Wert.

Die Eingabe in das Programm kann eine der folgenden sein:

• Befehlszeilenargumente des Formulars TN/TD N1/D1 N2/D2 N3/D3 ...
• eine Zeichenfolge der Form TN/TD N1/D1 N2/D2 N3/D3 ..., aus der gelesen wurde, stdinoder eine entsprechende Zeichenfolge
• Eine Zeichenfolge der Form, TN/TD N1/D1 N2/D2 N3/D3 ...die als Funktionsargument übergeben wird
• Ein Array von Zeichenfolgen, ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...]die als Funktionsargument übergeben werden

In allen Fällen t = TN/ TD, wo TN, TD∈ [1,10000].

Ebenso ist in allen Fällen: Rate für Sicherung verbrennen i = N _i / D _i = N<i>/ D<i>, wobei N<i>, D<i>∈ [1,10] ∀ i .

Sie können davon ausgehen, dass immer zwischen 1 und 5 Sicherungen (einschließlich) vorhanden sind und dass alle Eingaben gültig und innerhalb des Bereichs liegen. Sie können auch davon ausgehen, dass alle Eingabefraktionen in niedrigsten Ausdrücken angegeben sind.

Sie dürfen für diese Aufgabe keine Gleitkommazahlen mit Bruchkomponenten verwenden. Wenn Sie also an einer beliebigen Stelle in Ihrer Anwendung Gleitkommazahlen verwenden, können diese nur ganzzahlige Werte mit einer Bruchkomponente von Null annehmen.

Wertung

Dies ist eine Code-Golf- Herausforderung, daher wird der Gewinn für die kürzeste konforme Einreichung in Bytes vergeben.

Beispiel Ein- / Ausgänge

input:  29/6 3/2 2/3 3/5 3/7 7/5
output: true

One solution:
  - light both ends of fuse 1, mark start of interval
  - on fuse 1 consumption: light both ends of fuse 2, light one end of fuse 5
  - on fuse 5 consumption: extinguish one end of fuse 2, light both ends of fuse 3,
    light both ends of fuse 4
  - on fuse 2 consumption: extinguish one end of fuse 3, extinguish both ends of
    fuse 4
  - on fuse 3 consumption: relight one end of fuse 4
  - on consumption of fuse 4: mark end of interval (29/6 hours)

input:  2/1 3/1 5/1 7/1
output: false

input:  5/1 6/1 1/6 9/1 1/9
output: true

One solution:
  - light fuse 1 at one end, light fuse 2 at both ends, light fuse 4 at both ends
  - on fuse 1 consumption: extinguish one end of fuse 2, mark start of interval
  - on fuse 4 consumption: relight one end of fuse 2
  - on fuse 2 consumption: mark end of interval (5 hours)

Viel Spaß beim Verschmelzen! :)

Python 2, 305

Dies ist die Golfversion. Es ist praktisch unbrauchbar für n> 3 , da die zeitliche (und räumliche) Komplexität wie 3 ^{n 2 ist} ... tatsächlich ist dies für die Zeit viel zu gering. Auf jeden Fall akzeptiert die Funktion eine Liste von Zeichenfolgen.

def f(i):
 Z=range;r=map(__import__('fractions').Fraction,i);R=r[1:];n=len(R);L=[[[1]*n,[0]]];g=0
 for m,p in L: 
  for d in([v/3**i%3for i in Z(n)]for v in Z(3**n)):
    try:x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]>0);L+=[[[m[i]-x*R[i]*d[i]for i in Z(n)],[p[0]+x]+p]]
    except:g|=p[0]-r[0]in p
 return g

Eine leicht optimierte Version kann die Testfälle in wenigen Minuten abschließen. In einem unmöglichen Fall mit n = 5 kann dies jedoch noch langsam sein .

def fLessslow(i):
 Z=range
 r=map(__import__('fractions').Fraction,i)
 R=r[1:]
 n=len(R)
 L=[((1,)*n,(0,))]
 ls = set(L)
 for m,p in L: 
  if p[0]-r[0]in p: return 1
  for d in([v/3**i%3 for i in Z(n)]for v in Z(3**n)):
   if any(d[i] and m[i]<=0 for i in Z(n)):continue
   try:
    x=min(m[i]/R[i]/d[i]for i in Z(n)if m[i]*d[i]>0)
    thing = (tuple(m[i]-x*R[i]*d[i]for i in Z(n)),(p[0]+x,)+p)
    if thing not in ls:L+=[thing];ls.add(thing)
   except:5
 return 0

print fLessslow('5/1 6/1 1/6 9/1 1/9'.split())
print fLessslow('29/6 3/2 2/3 3/5 3/7 7/5'.split())

Python 2, 331

Es ist ein bisschen länger als Feersums Version, aber es ist viel schneller. Alle Testfälle zusammen dauern auf meinem Laptop ca. 3 Sekunden. Eine vollständige Suche nach n = 5 dauert jedoch ca. 10 Minuten. Ein Teil des Codes ähnelt der Version von feersum, aber ich habe keinen Code absichtlich kopiert.

from fractions import*
f=Fraction
r=range
g=lambda x:h(f(x[0]),[1/f(i)for i in x[1:]],[])
def h(t,x,y):
 for i in r(1,3**len(x)):
  c=[[],[],[]]
  for j in r(len(x)):c[i/3**j%3]+=[x[j]]
  n,b,w=c
  m=min(b+[i/2 for i in w])
  if h(t,[i for i in n+[j-m for j in b]+[j-2*m for j in w]if i],[i+m for i in y]+[m]):return True
 return t in y

Verwendung:

print g('3/4 1/1 1/1'.split())
print g('29/6 3/2 2/3 3/5 3/7 7/5'.split())
print g('2/1 3/1 5/1 7/1'.split())
print g('5/1 6/1 1/6 9/1 1/9'.split())

Erläuterung:

Der Lambda-Ausdruck g führt eine Vorverarbeitung der Eingabe durch, z. B. Konvertieren von Zeichenfolgen in Brüche, Trennen der Zielzeit von den Brennraten und Berechnen der Brennzeiten (= 1 / Brennrate).

Die Funktion h teilt alle Brennzeiten x in 3 Sätze n, b und w (n steht für Nichtbrennen, b für Einendbrennen und w für Beidesendbrennen). Es durchläuft alle diese Anordnungen (außer der Anordnung n = x, b = [], w = []), bestimmt die Sicherung mit der kürzesten Brennrate (spart Zeit in m) und ruft rekursiv h mit aktualisierten Brennzeiten auf. Ich speichere alle möglichen Zeiten, in denen jemand mit den Sicherungen messen kann. Im rekursiven Aufruf werden diese Werte ebenfalls aktualisiert.

Sobald ich den Wert finde, werden alle Aufrufe mit True beendet.