# 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 = Ni /Di = 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 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! :)

• @MartinBüttner I would guess it would be the floating point number restriction. Commented Nov 3, 2014 at 22:05
• @MartinBüttner I agree it isn't a restriction on the source code. I don't think [restricted-source] fits this question as it currently stands. Commented Nov 3, 2014 at 22:43
• @chilemagic: I wanted to draw attention to the fact that floating point logic couldn't be used, but if the consensus is that it's not a proper use of the tag, I'll strip it.
– COTO
Commented Nov 3, 2014 at 23:37
• The test cases are too big :) Commented Nov 4, 2014 at 3:41
• Lol, I'm using an O( (n!)^3 ) algorithm for golfing purposes. Commented Nov 4, 2014 at 3:46

# Python 2, 305

This is the golfed version. It is practically unusable for n > 3, as the time (and space) complexity is like 3n2... 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)
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())

• Nice, 8 upvotes for a buggy code: calling the function with the example in the description: print f('3/4 1/1 1/1'.split()) returns 0, though as the description says, it is solvable. Commented Nov 6, 2014 at 12:55
• @Jakube Thanks for testing...it is very rare on this site! It is fixed now; I forgot in one place to divide by the factor of 1 or 2 depending on how many ends of the rope are lit. Commented Nov 6, 2014 at 13:34

# 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.

• You young Python programmers are spoiled with all your built-in fractions and big integers. Back when I was a young'un, all we had was 1's and 0's, which we had to type in one-at-a-time at a console without a monitor. Sometimes we didn't have 1s.
– COTO
Commented Nov 6, 2014 at 14:54