A Good Time to Refuse

Question

The Setup

Suppose you're given n fuses, with 1 ≤ n ≤ 5, each of which is a meter long, and where each fuse has an associated burn rate of N meters per D hours.

A fuse can be lit at one or both ends, subsequently extinguished at one or both ends, relit, re-extinguished, etc., as many times as needed until the fuse is fully consumed. You are able to light and extinguish fuses instantaneously, and you can observe the exact instant a fuse is fully consumed (burnt up).

A fuse cannot be cut nor can it be lit anywhere except at its ends.

Such a setup allows for an infinitely accurate timing system, by measuring the time between any two fuse lighting/consumption events. For example, given two fuses with a burn rate of 1 meter per hour, you can measure exactly 45 minutes (3/4 hours) by

1. simultaneously: lighting the first fuse at both ends, lighting the second fuse at one end, and marking the start of your time interval
2. lighting the second end of the second fuse at the instant the first fuse is consumed (30 minutes later)
3. marking the end of your time interval at the instant the second fuse is consumed (15 minutes later)

The Challenge

Given a fractional number of hours t, and a set of n fractions representing exact burn rates of n fuses, write a program or function that outputs/returns a truthy value if t hours can be precisely measured through systematic burning of the fuses, or a falsy value otherwise.

The input to the program can be any of the following:

• command-line arguments of the form TN/TD N1/D1 N2/D2 N3/D3 ...
• a string of the form TN/TD N1/D1 N2/D2 N3/D3 ... read from stdin or equivalent
• a string of the form TN/TD N1/D1 N2/D2 N3/D3 ... passed as a function argument
• an array of strings ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...] passed as a function argument

In all cases t = TN/TD, where TN,TD ∈ [1,10000].

Likewise, in all cases: burn rate for fuse i = N_i /D_i = N<i>/D<i>, where N<i>,D<i> ∈ [1,10] ∀ i.

You may assume there will always be between 1 and 5 fuses (inclusive), and that all inputs are valid and in-range. You may also assume that all input fractions are given in lowest terms.

You may not use floating point numbers with fractional components for this challenge. That is, if you use floating point numbers anywhere in your application, they may only take on integral values with zero fractional component.

Scoring

This is a code-golf challenge, hence the shortest compliant submission in bytes will be awarded the win.

---

Example Inputs/Outputs

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)

Happy fusing! :)

Answer 1

Python 2, 305

This is the golfed version. It is practically unusable for n > 3, as the time (and space) complexity is like 3ⁿ²... actually that may be way too low for the time. Anyway, the function accepts a list of strings.

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

A slightly optimized version can finish the test cases in a couple of minutes. It might still be slow for an impossible n=5 case though.

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())

Answer 2

Python 2, 331

It's a little bit longer than feersum's version, but it's much faster. All testcases together take about 3 seconds on my laptop. A complete search for n=5 takes abount 10 minutes though. Some of the code is similar to feersum's version, but I didn't deliberately copy any code.

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

Usage:

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())

Explanation:

The lambda expression g does some preprocessing of the input, like converting strings into fractions, seperating goal time from burn rates and calculating the burn times (=1/burn rate).

The function h divides all burn times x into 3 sets n, b and w (n stand for non_burning, b for one_end_burning, and w for both_ends_burning). It iterates over all those arrangements (except the arrangement n=x, b=[], w=[]), determines the fuse with the shortest burn rate (save time in m), and recursively call h with updated burn times. In y I save all possible times someone can measure using the fuses. In the recursive call these values also get updated.

As soon as I find the value, it terminates alle calls with True.