Um bom momento para recusar

16

A configuração

Suponha que você receba n fusíveis, com 1 ≤ n ≤ 5, cada um com um metro de comprimento e cada fusível com uma taxa de queima associada de N metros por D horas.

Um fusível pode ser aceso em uma ou em ambas as extremidades, subsequentemente extinto em uma ou em ambas as extremidades, religado, reintegrado etc., tantas vezes quantas forem necessárias até que o fusível seja totalmente consumido. Você é capaz de acender e apagar fusíveis instantaneamente e pode observar o instante exato em que um fusível é totalmente consumido (queimado).

Um fusível não pode ser cortado nem aceso em qualquer lugar, exceto nas extremidades.

Essa configuração permite um sistema de tempo infinitamente preciso, medindo o tempo entre dois eventos de iluminação / consumo de fusível. Por exemplo, considerando dois fusíveis com uma taxa de queima de 1 metro por hora, você pode medir exatamente 45 minutos (3/4 horas)

  1. simultaneamente: acendendo o primeiro fusível nas duas extremidades, acendendo o segundo fusível em uma extremidade e marcando o início do seu intervalo de tempo
  2. acendendo a segunda extremidade do segundo fusível no instante em que o primeiro fusível é consumido (30 minutos depois)
  3. marcando o final do seu intervalo de tempo no instante em que o segundo fusível é consumido (15 minutos depois)

O desafio

Dado um número fracionário de horas t , e um conjunto de n frações representando taxas exatas de queima de n fusíveis, escreva um programa ou função que produza / retorne um valor verdadeiro se t horas puder ser medido com precisão através da queima sistemática dos fusíveis, ou valor falso caso contrário.

A entrada para o programa pode ser uma das seguintes:

  • argumentos de linha de comando do formulário TN/TD N1/D1 N2/D2 N3/D3 ...
  • uma cadeia de caracteres da forma TN/TD N1/D1 N2/D2 N3/D3 ...lida stdinou equivalente
  • uma cadeia de caracteres do formulário TN/TD N1/D1 N2/D2 N3/D3 ...passada como argumento de função
  • uma matriz de strings ["TN/TD", "N1/D1", "N2/D2", "N3/D3", ...]passadas como argumento de função

Em todos os casos t = TN/ TD, onde TN, TD∈ [1,10000].

Da mesma forma, em todos os casos: taxa de queima do fusível i = N i / D i = N<i>/ D<i>, onde N<i>, D<i>∈ [1,10] ∀ i .

Você pode assumir que sempre haverá entre 1 e 5 fusíveis (inclusive) e que todas as entradas são válidas e estão dentro do alcance. Você também pode assumir que todas as frações de entrada são fornecidas nos termos mais baixos.

Você não pode usar números de ponto flutuante com componentes fracionários para este desafio. Ou seja, se você usar números de ponto flutuante em qualquer lugar do aplicativo, eles poderão assumir apenas valores integrais com zero componente fracionário.

Pontuação

Este é um desafio de , portanto, o menor envio compatível em bytes será concedido.


Exemplo de entradas / saídas

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)

Feliz fusão! :)

COTO
fonte
@ MartinBüttner Eu acho que seria a restrição de número de ponto flutuante.
precisa saber é o seguinte
2
@ MartinBüttner Concordo que não é uma restrição ao código fonte. Eu não acho que [fonte restrita] se encaixa nessa questão como está atualmente.
precisa saber é o seguinte
@chilemagic: Eu queria chamar a atenção para o fato de que a lógica de ponto flutuante não poderia ser usada, mas se o consenso é que não é um uso adequado da tag, eu a retirarei.
COTO
Os casos de teste são grandes demais :)
feersum 4/11/14
5
Lol, estou usando um algoritmo O ((n!) ^ 3) para fins de golfe.
feersum

Respostas:

8

Python 2, 305

Esta é a versão do golfe. É praticamente inutilizável para n> 3 , pois a complexidade do tempo (e espaço) é como 3 n 2 ... na verdade, isso pode ser muito baixo para o tempo. De qualquer forma, a função aceita uma lista de 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

Uma versão ligeiramente otimizada pode concluir os casos de teste em alguns minutos. Ainda pode ser lento para um caso n = 5 impossível .

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())
feersum
fonte
11
Bom, 8 upvotes para um código de buggy: chamando a função com o exemplo na descrição: print f ('3/4 1/1 1 / 1'.split ()) retorna 0, embora, como diz a descrição, seja solucionável .
Jakube
@Jakube Obrigado por testar ... é muito raro neste site! Está consertado agora; Esqueci-me de um lugar para dividir pelo fator 1 ou 2, dependendo de quantas pontas da corda estão acesas.
feersum
3

Python 2, 331

É um pouco mais longo que a versão do feersum, mas é muito mais rápido. Todos os casos de teste juntos levam cerca de 3 segundos no meu laptop. Uma busca completa por n = 5 leva cerca de 10 minutos. Parte do código é semelhante à versão do feersum, mas eu não copiei deliberadamente nenhum código.

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

Uso:

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

Explicação:

A expressão lambda g realiza algum pré-processamento da entrada, como converter seqüências de caracteres em frações, separar o tempo do objetivo das taxas de gravação e calcular os tempos de gravação (= 1 / taxa de gravação).

A função h divide todos os tempos de gravação x em 3 conjuntos n, bew (n representa non_burning, b para one_end_burning e w para both_ends_burning). Ele itera sobre todos esses arranjos (exceto o arranjo n = x, b = [], w = []), determina o fusível com a menor taxa de queima (economize tempo em m) e chama recursivamente h com tempos de queima atualizados. Em y, guardo todas as vezes possíveis que alguém pode medir usando os fusíveis. Na chamada recursiva, esses valores também são atualizados.

Assim que eu encontrar o valor, ele termina todas as chamadas com True.

Jakube
fonte
4
Vocês jovens programadores de Python são mimados com todas as suas frações embutidas e grandes números inteiros. Quando eu era jovem, tudo o que tínhamos era 1's' e 0's, que precisávamos digitar um de cada vez em um console sem monitor. Às vezes não tínhamos 1s.
COTO