Solucionador reverso do FizzBuzz

32

Sinopse: Dada a saída de um programa FizzBuzz generalizado, retorne a lista de fatores e palavras usadas para o programa.

Descrição do Desafio

Imagine um programa FizzBuzz generalizado que inclua como entrada uma lista de fatores e palavras a serem usados ​​e o número para começar. Por exemplo, se a entrada deste programa foi

3 2,Ninja 5,Bear 7,Monkey

O programa imprimiria números de 3para 100, substituindo números divisíveis por 2com Ninja, números divisíveis por 5com Beare números divisíveis por 7com Monkey. Para números divisíveis, em seguida, mais de um desses termos, o programa concatenará as palavras, imprimindo itens como NinjaBearou BearMonkeyou NinjaMonkeyou NinjaBearMonkey. Aqui está a saída dessa entrada:

3
Ninja
Bear
Ninja
Monkey
Ninja
9
NinjaBear
11
Ninja
13
NinjaMonkey
Bear
Ninja
17
Ninja
19
NinjaBear
Monkey
Ninja
23
Ninja
Bear
Ninja
27
NinjaMonkey
29
NinjaBear
31
Ninja
33
Ninja
BearMonkey
Ninja
37
Ninja
39
NinjaBear
41
NinjaMonkey
43
Ninja
Bear
Ninja
47
Ninja
Monkey
NinjaBear
51
Ninja
53
Ninja
Bear
NinjaMonkey
57
Ninja
59
NinjaBear
61
Ninja
Monkey
Ninja
Bear
Ninja
67
Ninja
69
NinjaBearMonkey
71
Ninja
73
Ninja
Bear
Ninja
Monkey
Ninja
79
NinjaBear
81
Ninja
83
NinjaMonkey
Bear
Ninja
87
Ninja
89
NinjaBear
Monkey
Ninja
93
Ninja
Bear
Ninja
97
NinjaMonkey
99
NinjaBear

Observe que sempre que o programa precisa combinar palavras, ele sempre passa do número mais baixo para o número mais alto . Portanto, não será impressa algo como MonkeyBear(já que Monkey é um número maior que Bear).

Seu programa deve tomar na saída do programa FizzBuzz generalizado como entrada e saída da entrada dada ao programa FizzBuzz generalizada. Em outras palavras, escreva um "programa reverso" para o programa FizzBuzz generalizado. Por exemplo, dado o bloco de código acima como entrada, seu programa deve ser exibido 3 2,Ninja 5,Bear, 7,Monkey.

Existem algumas regras que as palavras sempre seguirão:

  • Sempre será possível dizer exatamente quais são os fatores e as palavras da entrada.
  • Cada palavra começará com uma letra maiúscula e não conterá outras letras maiúsculas ou números.
  • Cada fator é único.

Amostras de entradas e saídas

Entrada:

Calvins
7
Hobbies
9
10
11
Calvins
13
14
15
Hobbies
17
Calvins
19
20
21
22
23
CalvinsHobbies
25
26
27
28
29
Calvins
31
Hobbies
33
34
35
Calvins
37
38
39
Hobbies
41
Calvins
43
44
45
46
47
CalvinsHobbies
49
50
51
52
53
Calvins
55
Hobbies
57
58
59
Calvins
61
62
63
Hobbies
65
Calvins
67
68
69
70
71
CalvinsHobbies
73
74
75
76
77
Calvins
79
Hobbies
81
82
83
Calvins
85
86
87
Hobbies
89
Calvins
91
92
93
94
95
CalvinsHobbies
97
98
99
100

Saída:

6 6,Calvins 8,Hobbies

Entrada:

FryEggman
7
Am
Fry
The
11
FryAmEggman
13
14
FryThe
Am
17
FryEggman
19
AmThe
Fry
22
23
FryAmEggman
The
26
Fry
Am
29
FryTheEggman
31
Am
Fry
34
The
FryAmEggman
37
38
Fry
AmThe
41
FryEggman
43
Am
FryThe
46
47
FryAmEggman
49
The
Fry
Am
53
FryEggman
The
Am
Fry
58
59
FryAmTheEggman
61
62
Fry
Am
The
FryEggman
67
Am
Fry
The
71
FryAmEggman
73
74
FryThe
Am
77
FryEggman
79
AmThe
Fry
82
83
FryAmEggman
The
86
Fry
Am
89
FryTheEggman
91
Am
Fry
94
The
FryAmEggman
97
98
Fry
AmThe

Saída:

6 3,Fry 4,Am 5,The 6,Eggman

Entrada:

DeliciousTartApplePie
DeliciousCreamPancakeStrawberry
DeliciousProfiterole
DeliciousCream
DeliciousPancake
DeliciousCreamStrawberryTart

Saída:

95 1,Delicious 2,Cream 3,Pancake 4,Strawberry 5,Tart 19,Apple 95,Pie 97,Profiterole

Você pode obter o código que usei para gerar as entradas aqui .

code-golf absinto
fonte
A lista sempre sobe exatamente para 100?
Dennis
@Dennis Sim, o limite superior é sempre 100.
absinto
15
É apenas uma honra estar em um de seus exemplos.
NinjaBearMonkey
Esta é uma versão muito melhor do seu desafio do que era originalmente na caixa de areia :)
Beta Decay
11
@NinjaBearMonkey Suponho que escolher nomes com muitas palavras nos fez exemplos melhores. Obrigado por me incluir também @Pyrrha! :)
FryAmTheEggman

Respostas:

10

Pitão, 73 bytes

jd+J-101lK.zjL\,Sm,_-F>2+_Jf}d@KTUKd{smtcdf-@dTGUdf>T\:K

Essa foi certamente uma pergunta difícil. Acho que abordei todos os casos extremos, incluindo tudo no exemplo de @ MartinBüttner e o exemplo de não repetição de fatores.

NinjaBearMonkey , Deliciousness

No nível alto, o programa encontra primeiro todas as palavras cortando as seqüências alfabéticas em letras maiúsculas.

Em seguida, as linhas são mapeadas para saber se cada sequência aparece ou não na linha e cada fator possível é testado para verificar se produz a mesma ordem. Caso isso aconteça, o fator é adicionado a uma lista global, que é verificar se o fator já estava presente. Se ainda não estava presente, o fator é usado. As sequências são ordenadas pela primeira aparição na entrada, o que desambigua a ordem das sequências de caracteres que cada uma aparece apenas uma vez na mesma linha.

Depois disso, é apenas formatação e impressão.

isaacg
fonte
5

Scala, 350 caracteres

(s:String)⇒{def g(a:Int,b:Int):Int=if(b==0)a.abs else g(b,a%b);val(j,q)=(s.lines:\100→Map.empty[String,Int]){case(l,(n,m))⇒if(l(0).isDigit)(n-1,m)else(n-1,m++(Seq(Seq(l(0)))/:l.tail){case(x,c)⇒if(c.isUpper)Seq(c)+:x else (x(0):+c)+:x.tail}.map{t⇒val w=t.mkString;w→g(m.getOrElse(w,n),n)})};s"${j+1}"+q.map{case(k,v)=>s" $v,$k"}.toSeq.sorted.mkString}

não ganhando ... mas boa pergunta.

resultados testados:

scala> (s:String)⇒{def g(a:Int,b:Int):Int=if(b==0)a.abs else g(b,a%b);val(j,q)=(s.lines:\100→Map.empty[String,Int]){case(l,(n,m))⇒if(l(0).isDigit)(n-1,m)else(n-1,m++(Seq(Seq(l(0)))/:l.tail){case(x,c)⇒if(c.isUpper)Seq(c)+:x else (x(0):+c)+:x.tail}.map{t⇒val w=t.mkString;w→g(m.getOrElse(w,n),n)})};s"${j+1}"+q.map{case(k,v)=>s" $v,$k"}.toSeq.sorted.mkString}
res0: String => String = <function1>

scala> res0("""DeliciousTartApplePie
     | DeliciousCreamPancakeStrawberry
     | DeliciousProfiterole
     | DeliciousCream
     | DeliciousPancake
     | DeliciousCreamStrawberryTart""")
res1: String = 95 1,Delicious 2,Cream 3,Pancake 4,Strawberry 5,Tart 95,Apple 95,Pie 97,Profiterole

scala> res0("""FryEggman
     | 7
     | Am
     | Fry
     | The
     | 11
     | FryAmEggman
     | 13
     | 14
     | FryThe
     | Am
     | 17
     | FryEggman
     | 19
     | AmThe
     | Fry
     | 22
     | 23
     | FryAmEggman
     | The
     | 26
     | Fry
     | Am
     | 29
     | FryTheEggman
     | 31
     | Am
     | Fry
     | 34
     | The
     | FryAmEggman
     | 37
     | 38
     | Fry
     | AmThe
     | 41
     | FryEggman
     | 43
     | Am
     | FryThe
     | 46
     | 47
     | FryAmEggman
     | 49
     | The
     | Fry
     | Am
     | 53
     | FryEggman
     | The
     | Am
     | Fry
     | 58
     | 59
     | FryAmTheEggman
     | 61
     | 62
     | Fry
     | Am
     | The
     | FryEggman
     | 67
     | Am
     | Fry
     | The
     | 71
     | FryAmEggman
     | 73
     | 74
     | FryThe
     | Am
     | 77
     | FryEggman
     | 79
     | AmThe
     | Fry
     | 82
     | 83
     | FryAmEggman
     | The
     | 86
     | Fry
     | Am
     | 89
     | FryTheEggman
     | 91
     | Am
     | Fry
     | 94
     | The
     | FryAmEggman
     | 97
     | 98
     | Fry
     | AmThe""")
res2: String = 6 3,Fry 4,Am 5,The 6,Eggman
Gilad Hoch
fonte
4

Python 2, 366 340 331 bytes

Este programa recebe entrada via stdin.

Nova abordagem:

Calcule o fator das palavras de apenas uma ocorrência pela distância do final da linha. Por exemplo (a partir da última amostra): DeliciousTartApplePiePie é calcular como: [95,19,5,1][0]e Apple é: [95,19,5,1][1].

import sys
import re
d=[(i,re.findall('[A-Z][a-z]*',l)[::-1])for i,l in enumerate(sys.stdin)]
e=101-len(d)
print e," ".join(`x`+','+`y`[1:-1]for x,y in sorted({next((j-i for j,t in d if j>i and w in t),[x for x in range(i+e,0,-1)if(i+e)%x==0][d[i][1].index(w)]):w for w,i in{w:i for i,l in d[::-1]for w in l}.items()}.iteritems()))

Abordagem antiga:

import sys
import re
l=[(i,re.findall('[A-Z][a-z]*',l))for i,l in enumerate(sys.stdin)]
e=101-len(l)
d={}
for i,s in l:
 for w in s[::-1]:
  if w not in d.values():
   d[next((j-i for j,t in l[i+1:]if w in t),next(m for m in range(i+e,0,-1)if(i+e)%m==0and m not in d))]=w 
print e," ".join(`x`+','+`y`[1:-1]for x,y in sorted(d.iteritems()))

Uso:

python FizzBuzzReverseSolver.py < Sample1.txt

Explicação (da abordagem antiga):

  • Em geral, o programa cria uma lista de número de linha e lista de palavras (por exemplo [(0, []), (1, ['Ninja']), (2, ['Bear']), ...].
  • Para cada palavra em cada linha (a partir do final da linha):
    • Encontre a próxima ocorrência da palavra e insira a diferença e a palavra em um dicionário predefinido.
    • Se não for encontrado, insira o maior fator do número da linha (inclusive ele mesmo) que ainda não existe no dicionário e a palavra no dicionário.
TheCrypt
fonte