Sexta-feira, 10 de Outubro de 2008

Codebits Quizz Show III

* Update: Desafio terminado! Seguem as qualificações!

 

Pos.NomeTacadasCódigo
1.Marcos Henrich121->>+>>+>-->>+++>++>-[>+++[>++++[>++++<-]<-]<<+]>>>>+++.>+.>.-.>.>+++.>-.>++++.+.---.+++++++.<+++++.-.>>.>++.--..++++++++.
2.Paula Valença123++++[>++++<-]>[-<+>>>>++<++++<+++++<]>+++.>+.<---.-.>>.<++.>[-<+<+<+<+>>>>]<<.>+.+.---.+++++++.<+++++.-.<.<++.--..++++++++.
3.André Cruz125++++[>++++<-]>[>+++>++>+++++>++++>+[>++<<]>-]>+++.>+.<---.-.[>]<.<<<<++.>-.>++++.+.---.+++++++.<+++++.-.>>>.<++.--..++++++++.
4.Paulo Afonso127+++[>++++++<-]>-[[<+++++++>>+<-]>-]<<[<]>>>>>>-.>>>++.<<+++.-.>>>>>>---.<<<<++.[<]>>-.>>++.+.---.<.<+++++.-.[>]<<<<<.<<+.--..<.
5.Nuno Pereira130>++++[>++++++<-]>-[[<+++++>>+<-]>-]<<[<]>>>>>>>--.>>>>.<<<.-.>>>>>>>>>>++.<<<<<<<++.[<]>>+.>>.+.---.<.<<+.-.[>]<<<<<<.<<<<.--..<+.
6.João Sil132++++[>++++<-]>[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
6.Fernando Duarte Silva132++++[>++++<-]>[>+++++>++++>++>++++++>+++++++>+++[<]>-]>+++.>+.<---.-.>>.<++.>>>-.<++++.+.---.+++++++.>+++++.-.<<.>>>++.--..++++++++.
6.José Celestino132++++[>++++[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]<-]>>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
6.Pedro Gomes132++++[->++++<]>[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
6.Mário Valente132++++[>++++<-]>[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
6.Diogo Matias132++++[>++++<-]>[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
12.H. Barquero134++++++++++++++++[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
12.Francisco Ferreira134++++++++++++++++[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
12.Carlos Pires134++++[>++++[>+++++>++++>++>++++++>+++++++>+++<<<<<<-]<-]>>+++.>+.<---.-.>>.<++.>>>-.<++++.+.---.+++++++.>+++++.-.<<.>>>++.--..++++++++.
15.Gilberto Gonçalves135++++++++++++++++[>+++++>++++>++>+++++++>++++++>+++<<<<<<-]>+++.>+.<---.-.>>.<++.>>-.>++++.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
16.Pedro MG139++++[>++++[>+++++>++++>++>+++++++>+++++++>+++<<<<<<-]>+>>>>---[<]<-]>>-.>+.<---.-.>>.<++.>>-.>.+.---.+++++++.<+++++.-.<.>>>++.--..++++++++.
17.Francico Huhn144++++++++++[->++++++++>++++++>+++>+++++++++++>++++++++++>+++++<<<<<<]>+++.>+++++.<---.-.>>++.<++.>>+.>.+.---.+++++++.<+++++.-.<.>>>.--..++++++++.
18.Bruno Barreto145++++++++++[>++++++++>+++++++>+++>+++++++++++>++++++++++>+++++<<<<<<-]>+++.>-----.<---.-.>>++.<++.>>+.>.+.---.+++++++.<+++++.-.<.>>>.--..++++++++.
19.João Pedro Pereira146++++++++++[->++++++++>++++++>+++>+++++++++++>+++++<<<<<]>+++.>+++++.<---.-.>>++.<++.>>+.-----------.+.---.+++++++.+++++++++++.-.<.>>.--..++++++++.
19.Gustavo Carvalho146++++++++++[>++++++++>++++++>++++++++++>+++++++++++>+++>+++++<<<<<<-]>+++.>+++++.<---.-.>>>>++.<<<++.>>+.<.+.---.+++++++.>+++++.-.>.>.--..++++++++.
21.Miguel Louro Manso147++++++++++[>++++++++>+++++++>+++>++++++++++>+++++++++++>+++++<<<<<<-]>+++.>-----.<---.-.>>++.<++.>>>+.<.+.---.+++++++.>+++++.-.<<.>>>.--..++++++++.
22.Pedro Correia149++++++++++[>+++>++++++++>+++++++>+++++++++++>++++++++++>+++++<<<<<<-]>>+++.>-----.<---.-.<++.>>++.>+.>.+.---.+++++++.<+++++.-.<<<.>>>>>.--..++++++++.
23.Filipe Batista151++++++++[>++++++++++>++++++++>++++<<<-]>+++.>+.<---.-.>>.<++.<<++++++[>+++++>+++++>+++>+++++<<<<-]>++.>+++.+.---.+++++++.<+++++.-.>>>++.<.--..++++++++.
24.Márcio Henrique154++++++++++[>++++++++>++++++>+++>+++++>+++++++>+++++++++++>++++++++++<<<<<<<-]>+++.>+++++.<---.-.>>++.>>---.>+.>.+.---.+++++++.<+++++.-.<<<.>.--..++++++++.
25.electron plusplus160 ++++[->+++++<]>+[-<++++>>+++<]<-.>>++.<<---.-.>++++++[-<-------->]<+.>>++.------------[-<++>>+>+<<]<+.-----------.+.---.+++++++.+++++++++++.-.<.>>>-----.--..>+.
26.Marco Gonçalves161++++++++++[>++++++++>+++++++++>++++++++++>+++>+++++++>+++++<<<<<<-]>+++.>>---.+++++++++++++++.-.>++.>---.<<.<++++++++++.+.---.+++++++.>+++++.-.>.>>.--..++++++++.
27.André Moniz177++++++++++[>++++++++>++++++>++++++++>+++<<<<-]>+++.>+++++.>.-.>++.<<++.<++++++++++++++++++++++++++++.-----------.+.---.+++++++.+++++++++++.-.>>>.++++++++++++++++++.--..++++++++.
28.David Serrano190++++++++++++++++++[>++>+++>++++>+++++>++++++>+++++++<<<<<<-]++++++++++++++++++>>>>-------.<-------.>---.-.<<<----.>>++.>>+++.-----------.+.---.+++++++.>----------.-.<<<<<.>----.--..++++++++.
28.Ricardo Saramago190++++++++++++++++++[>++>+++>++++>+++++>++++++>+++++++<<<<<<-]++++++++++++++++++>>>>-------.<-------.>---.-.<<<----.>>++.>>+++.-----------.+.---.+++++++.>----------.-.<<<<<.>----.--..++++++++.
30.Tomás Senart218++++[>++++++++<-]+++++++[>>>++++++++++<<<-]++++++++[>>>>++++++++++<<<<-]+++++++++++[>>>>>++++++++++<<<<<-]>>>>+++.<-----.>---.-.<<<.>>++.>>+.-----------.+.---.+++++++.+++++++++++.-.<<<<.++++++++++++++++++.--..++++++++.
31.Miguel Luis265++++++++++[>++++++++>++++++>++++++++>++++++++>+++>+++++++>+++++++++++>++++++++++>++++++++++>++++++++++>++++++++++>++++++++++++>+++++++++++>+++>+++++>+++++>+++++>++++++<<<<<<<<<<<<<<<<<<-]>+++.>+++++.>.>-.>++.>---.>+.>.>+.>--.>+++++.>----.>+++++.>++.>.>--.>--.>----.

 

 

 

Para o fim-de-semana que se aproxima propomos um desafio de Golf.

Em vez de tacadas teremos o número de caracteres utilizados num programa para resolver o problema proposto.

Dada a diversidade das linguagens de programação utilizadas pelos participantes no Codebits, propomos um back to basics, a linguagem proposta tem apenas oito funções.

Neste desafio a resposta certa será um programa escrito na linguagem de programação Brainfuck que devolva a expressão

SAPO Codebits 2008

Regras: a expressão é case sensitive e o programa não pode receber qualquer input.
O 'par' do desafio é de 300 caracteres e haverá um vencedor - o que resolver o desafio utilizando o menor número de caracteres.

Podem testar os vossos programas neste Interpretador Online de Brainfuck.

Envia o programa para o email do codebits, codebits@sapo.pt.

Bom fim-de-semana!

PS: Tanto este como o desafio II terminam segunda-feira às 19h00. Colocaremos nos respectivos comentários os nomes de quem acertou. Neste desafio a ordem é pelo número de caracteres utilizados, no desafio II pela ordem de chegada da resposta.


publicado por joaovelhote às 11:55
link do post | comentar
|
23 comentários:
De André a 10 de Outubro de 2008 às 12:30
Com newline no fim?


De joaovelhote a 10 de Outubro de 2008 às 12:31
Olá André,
não. Só "SAPO Codebits 2008".


De Gilberto Gonçalves a 10 de Outubro de 2008 às 19:20
132? Parece que vou ter de diminuir mais o meu :D


De Tomás Senart a 10 de Outubro de 2008 às 19:47
Que cena.. Não consigo fazer mais pequeno do que 218.


De Tomás Senart a 10 de Outubro de 2008 às 21:02
198...


De Francisco Huhn a 11 de Outubro de 2008 às 18:09
Vou nos 144, um dos recordes anteriores... :\


De Berardo a 11 de Outubro de 2008 às 18:28
134 caracteres para mim :/


De Paula Valenca a 11 de Outubro de 2008 às 22:02
Hums, minimisando custos heuristicamente (leia-se: meio a adivinhar), suspeito que não é possível fazer melhor que 123.

Mas posso estar enganada... ;)


De Jose Celestino a 13 de Outubro de 2008 às 01:47
Eu diria que minimizando os custo heuristicamente nao seria possivel ir abaixo dos 132. Mas pelos visto ... :|


De Diogo Matias a 13 de Outubro de 2008 às 14:28
Hehe, foi o que pensei... D:


De Francisco Huhn a 11 de Outubro de 2008 às 23:12
O source da melhor solução será postado?

Gostava muito de ver esse source (com comments, porque aprendi que em brainfuck, ler o código dos outros é tipo MI)...

Cumps


De joaovelhote a 12 de Outubro de 2008 às 09:06
Francisco, sim claro que publicaremos o código da melhor solução!


De Paulo a 13 de Outubro de 2008 às 16:08
O tempo entre quizz devia ser de uma semana para o pessoal ter tempo no fim de semana..

128 :| como fizeram para 121? colaram uns postits ao monitor? hehe


De Francisco Huhn a 13 de Outubro de 2008 às 18:32
Já jouve o fim-de-semana 11,12 de Outubro, acho que é suficiente...

Também nao faço a mínima como resolveram com 121... o_O


Sugestão para os Quizzs: um quiz relacionado com o Cubo de Rubik não era mal pensado! :D (por exemplo: menos movimentos ou outra coisa qqr)


De Gilberto Gonçalves a 13 de Outubro de 2008 às 19:58
Porquê que eu não tenho um link?


De joaovelhote a 13 de Outubro de 2008 às 21:57
Gilberto, enviaste o E-mail com o mesmo endereço com que te inscreveste? Envia-me um email para o codebits@sapo.pt sff.

Obrigado!


De Gilberto Gonçalves a 14 de Outubro de 2008 às 22:33
Já viste o meu e-mail?


De joaovelhote a 15 de Outubro de 2008 às 00:02
Olá Gilberto, sim!
Na próxima actualização das tabelas já incluo o teu link.

Um abraço!
JP


De Paula Valenca a 13 de Outubro de 2008 às 20:17
ohhh... overflow... nice!
parabens!!


De Marcos Henrich a 13 de Outubro de 2008 às 21:44
Decidi comentar este pequeno mas confuso código, pelo menos fica para posteridade.
O objectivo obter o output: “SAPO Codebits 2008“
Codificado em ascii por: {83,65,80,79,32,67,111,100,101,98,105,116,115,32,50,48,48,56}
A primeira parte do código cria uma array que é mais tarde multiplicada por 16, agrupando assim uma ou várias letras ao múltiplo de 16 mais próximo:
{'2' ,'0','8'} {50,48,56} → 3*16 = 48
{'A' ,'C'} {65,67} → 4*16 = 64
{'S' ,'P','O'} {84,80,79} → 5*16 = 80
{'d' ,'e','b'} {100,101,98} → 6*16 = 96
{'o' ,'t','s'} {111,116,115} → 7*16 = 112
Para ser mais fácil de entender começo por mostrar uma versão simples do código sem nenhuma tentativa de compressão que ficou com 133 caracteres.
+++++>++++>++>++++++>+++++++>+++[[>++++[>++++<-]<-]<]>>>+++.>+.<---.-.>>.<++.>>>-.<++++.+.---.+++++++.>+++++.-.<<.>>>++.--..++++++++.
Começa por inicializar a tal array +++++>++++>++>++++++>+++++++>+++ {5,4,2,6,7,3}, uma ordem que convêm para o texto em questão .
Depois aplicasse uma multiplicação por 16 [[>++++[>++++<-]<-]<], entre todos os membros da array até encontrar um igual a zero.
Exemplificando para a primeira multiplicação temos isto em três ponteiros +++>++++>++++, faz-se uma primeira multiplicação entre o ponteiro 2 e 3 ficando com +++> >+(16x), e depois um multiplicação entre os ponteiros 1 e 3 ficando com > > +(68x).
Ficando assim para a próxima multiplicação dois ponteiros livres entre o primeiro resultado e o próximo valor a multiplicar +++++++ > > > +(68x).
Esta parte do código é simples, >>>+++.>+.<---.-.>>.<++.>>>-.<++++.+.---.+++++++.>+++++.-.<<.>>>++.--..++++++++. , apenas percorre a array e efectua operações de maneira a obter o resultado desejado.
Agora vêm a parte complicada e onde está o verdadeiro brainfuck... como passar dos 133 aos 121 caracteres??!
Na verdade depois de feito é bastante simples, olha-se para o código e vê-se quais as partes que parecem longas demais, repara-se logo na criação da array que chega a ter +++++++, se todos os valores da array são entre 3 e 7 porque usar uns entre 0 e 4 e somar 3 antes de multiplicar? Aqui está algo que simplifica muito!!
Depois de uma serie de teste reparou-se que o mais pequeno era uma array entre -2 e 3 a qual se somava 5 antes da multiplicação. ficando com: +>>+>-->>+++>++>-->- em vez de +++++>++++>++>++++++>+++++++>+++, 21 caracteres em vez de 32, menos 11!
Mas existe aqui um problema! A condição de paragem para a multiplicação é encontrar um zero, e agora existem dois zeros! Para resolver isto é preciso mudar a condição de paragem, porque não -1?
Sim, boa ideia... para isso vamos omitir o primeiro valor a multiplicar dentro da multiplicação e depois não haverá qualquer problema, bastando inserir um - no principio da array para parra as multiplicações, assim, [[>++++[>++++<-]<-]<] ficou [>+++[>++++[>++++<-]<-]<<+] e +>>+>-->>+++>++>-->- ficou ->>+>>+>-->>+++>++>-.
Ficamos assim com uma solução de 121 caracteres que por muito que tente não consigo simplificar mais:
->>+>>+>-->>+++>++>-[>+++[>++++[>++++<-]<-]<<+]>>>>+++.>+.>.-.>.>+++.>-.>++++.+.---.+++++++.<+++++.-.>>.>++.--..++++++++.

Bom esta ultima parte não ficou muito bem explicada mas já dá para ter uma ideia.


De joaovelhote a 13 de Outubro de 2008 às 21:53
Marcos, és o maior!


De Paula Valenca a 14 de Outubro de 2008 às 00:34
Já agora eu explico o meu, que tem uma metodologia muito diferente: menos truques e gestao da tape inteligentes, mais pura algoritmia e matematica.

Eu precisava de praticar o meu C++ e como tal... toca a desenvolver um programa que calcule uma solucao optima ou quase optima!

Defini o que me pareciam ser as "operacoes" atomicas para representar os codigos ASCII e os custos associados a cada um. E depois era só correr o programa à procura de uma solucao que escolhesse a melhor operacao para cada codigo de forma a ter um custo minimo. Mais concretamente:

Seja N o codigo ASCII de uma letra. Podemos escrever
N = q*s + r, para uns certos q, s e r.
Se só quisermos escrever N, fica

Q[>S<-]>R.

o custo é q + s + r + 5 e o truque é escolher q, s e r tal que a soma seja minima (que foi o que o pessoal andou todo a fazer)

Se quisermos escrever varios caracteres o custo para cada é:
- r + 2 se q e s forem reutilizados
- s + r + 4 se só q for reutilizado
- q + s + r + 5 se nenhum for reutilizado

Mas esta string é facil e depois de perceber estas operacoes ve-se a olho nu que o ideal é usar sempre o mesmo q = 8 (um segundo olhar e organizacao permite por q = 16 = 4*4)

Mas quando ia a adicionar os custos do apontador a mover na tape apercebi-me que afinal havia mais formas de representar um numero que podiam ser optimas.

O meu truque foi aperceber-me da coincidencia entre o caracter de espaco - 32 - e a diferenca entre maiusculas e minusculas. Ou seja, baixei de 8 para 6 casas na tape, fiz uma soma de 32 às 4 casas de caracteres para re-obter o espaco, por a casa dos numeros no valor certo e converter maiusculas para minusculas. Melhor gestao de tape e 6 casas ficaram 5.

Com uma string tao pequena, não estava a ver como utilizar melhor a entropia da string. Dai que, a partir daqui, melhor só mesmo usando os truques do Marcos. Daí o parecer-me heuristicamente que nao dava para mais.

Estava enganada! Parabens, Marcos!


De Marcos Henrich a 14 de Outubro de 2008 às 09:28
Pois... truques atrás de truques. Fiquei muito surpreendido por 123 caracteres, sem truques.
Quando vi que mais alguém tinha feito 123, pensei que tinham descoberto um truque extra forte, por isso fui a procura de mais um pequeno truque para reduzir e tive a sorte de encontrar.
Passei muito mais tempo a procura de truques que propriamente no algoritmo.
Parabéns Paula, por mim nem sequer era possível chegar heuristicamente aos 125!


Comentar post