16
\$\begingroup\$

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! :)

\$\endgroup\$
7
  • \$\begingroup\$ @MartinBüttner I would guess it would be the floating point number restriction. \$\endgroup\$
    – hmatt1
    Nov 3 '14 at 22:05
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – hmatt1
    Nov 3 '14 at 22:43
  • \$\begingroup\$ @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. \$\endgroup\$
    – COTO
    Nov 3 '14 at 23:37
  • \$\begingroup\$ The test cases are too big :) \$\endgroup\$
    – feersum
    Nov 4 '14 at 3:41
  • 5
    \$\begingroup\$ Lol, I'm using an O( (n!)^3 ) algorithm for golfing purposes. \$\endgroup\$
    – feersum
    Nov 4 '14 at 3:46
8
\$\begingroup\$

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)
    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())
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Jakube
    Nov 6 '14 at 12:55
  • \$\begingroup\$ @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. \$\endgroup\$
    – feersum
    Nov 6 '14 at 13:34
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – COTO
    Nov 6 '14 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.