[Médio] 5 números, 5 condições, quantas soluções?

[thoga31 582]

Considere-se 5 números, A, B, C, D e E, que pertencem ao intervalo [1, 9].

Objectivo: pretende-se conhecer a lista de conjuntos {A, B, C, D, E} que cumpram as seguintes condições:

1. A != B != C != D != E
   
2. A + B + C + D + E = 23
   
3. (A + B + C) / D = E
   
4. Não se quer os conjuntos em que os valores de A, B e C sejam iguais entre si. Ou seja, o conjunto {1, 2, 3, 4, 5} é o mesmo que {3, 1, 2, 4, 5}, pelo que só se quer um deles. Isto deve-se ao facto de A+B+C constituir o numerador da condição nº3 - a ordem destes três números é, então, indiferente, e consideram-se os conjuntos-solução iguais.
   
5. O ponto 4 aplica-se igualmente aos valores de D e E. Considerando que A+B+C = P, temos que P/D = E <=> P/E = D. Desta forma, considera-se que {1, 2, 3, 4, 5} é o mesmo que {1, 2, 3, 5, 4}.
   

Input: não aplicável.

Output: são esperados 6 conjuntos.

Restrições: incluídas no objectivo.

[pmg 86]

5 ciclos encadeados ... Brute Force FTW!

[thoga31 582]

5 ciclos encadeados ... Brute Force FTW!

5 ciclos... depende da linguagem

[pmg 86]

http://ideone.com/osrU8J

#include <stdio.h>

int main(void) {
   for (int a = 1; a < 10; a++) {
       for (int b = a + 1; b < 10; b++) {
           for (int c = b + 1; c < 10; c++) {
               for (int d = 1; d < 10; d++) {
                   if ((d == a) || (d == b) || (d == c)) continue;
                   for (int e = d + 1; e < 10; e++) {
                       if ((e == a) || (e == b) || (e == c)) continue;
                       if (a + b + c + d + e != 23) continue;
                       if ((a + b + c) / d != e) continue;
                       if ((a + b + c) % d == 0) printf("(%d + %d + %d) / %d = %d\n", a, b, c, d, e);
                   }
               }
           }
       }
   }
   return 0;
}

Edit

DIGA NAO A MAGIC NUMBERS

// ...
#define TARGET_SUM 23
// ...
                       if (a + b + c + d + e != TARGET_SUM) continue;

// ...

Edited February 17, 2013 by pmg
DIGA NAO A MAGIC NUMBERS

[thoga31 582]

A solução que eu e o @pwseo desenvolvemos enquanto estávamos a analisar o desafio do ponto de vista da Programação Funcional

import Control.Monad (guard)
import Data.List (nub, nubBy, permutations)

solutions = do
 a <- [1..9]
 b <- [1..9]
 c <- [1..9]
 d <- [1..9]
 e <- [1..9]
 guard $ nub [a,b,c,d,e] == [a,b,c,d,e]
 guard $ a + b + c + d + e == 23
 guard $ (a + b + c) / d == e
 return [a,b,c,d,e]

main :: IO ()
main = mapM_ (print . map truncate) $ nubBy f solutions
 where
   f (a:b:c:_) (d:e:f:_) = [a,b,c] `elem` permutations [d,e,f]

Aquele do pode ser reduzido ao seguinte, mas pessoalmente gosto mais do do:

solutions = [[a,b,c,d,e] | a <- [1..9], b <- [1..9], c <- [1..9], d <- [1..9], e <- [1..9], nub [a,b,c,d,e] == [a,b,c,d,e], a + b + c + d + e == 23, (a + b + c) / d == e]

Edited February 17, 2013 by thoga31

[pmg 86]

O ideone "nao gosta" de alguns elementos que usas no teu programa.

http://ideone.com/8PsxS3

[thoga31 582]

Os imports são fantasmas e tu tens medo de fantasmas, certo?

Edited February 17, 2013 by thoga31

[pmg 86]

Agora ja funciona

http://ideone.com/5XCGSX

Eu nao sei Haskell, nao sei absolutamente nada de Haskell.

Nao sei (nao sabia) o que sao os imports ... e nao tenho medo de fantasmas.

Acho os imports muito importantes: tao importantes como os #includes em C

Edited February 17, 2013 by pmg

[thoga31 582]

Agora ja funciona

http://ideone.com/5XCGSX

Eu nao sei Haskell, nao sei absolutamente nada de Haskell.

Nao sei (nao sabia) o que sao os imports ... e nao tenho medo de fantasmas.

Acho os imports muito importantes: tao importantes como os #includes em C

Calma, homem, estava apenas a brincar...

Mas uma coisa: se sabes o que são os #include's em C, então sabes o que são os import's, ou outra qualquer designação, noutras LP's. Todos têm a mesma função.

[HappyHippyHippo 1,165]

não vamos comparar resultados em relação a linguagens

é claro que cada uma tem um objectivo, tornado a realização de um trabalho mais simples ou não dependendo desse objectivo.

se usasse uma das muitas bibliotecas matemáticas de C que existem por ai, o calculo das permutações também seria numa linha.

se querem minimizar, peguem numa linguagem lógica como ProLog ou Mercury

[mjamado 42]

Uma solução em JS: http://jsfiddle.net/YpwwE/3/

[pwseo 234]

se querem minimizar, peguem numa linguagem lógica como ProLog ou Mercury

A linguagem usada pelo thoga tem uma funcionalidade que se adapta bem a este tipo de computações com diversos resultados, onde podemos simplesmente especificar os dados e as condições que estes devem cumprir. Semelhante a prolog, portanto, mas com outra sintaxe.

Aqui fica uma nova versão em Haskell praticamente sem imports (a função guard faz partida stdlib de Haskell e já existe "nativamente" nas list comprehensions, mas aqui importamos explicitamente para a podermos chamar dentro do bloco "do".

Inspirei-me na solução do pmg e passei para Haskell. A solução inicial do thoga31 não é tão optimizada porque o problema original nada dizia acerca de soluções "repetidas" (pontos 4 e 5), e havia 72 soluções iniciais.

import Control.Monad (guard)
 
solutions = do
  a <- [1..9]
  b <- [a + 1..9]
  c <- [b + 1..9]
  d <- [1..9]
  guard $ d `notElem` [a, b, c]
  e <- [d + 1..9]
  guard $ e `notElem` [a, b, c]
  guard $ sum [a, b, c, d, e] == 23
  guard $ quotRem (a + b + c) d == (e, 0)
  return [a, b, c, d, e]
 
main = mapM_ print solutions

EDITS: Correcções sugeridas pelo pmg mais abaixo.

Edited February 17, 2013 by pwseo

[pmg 86]

No problema a resolver (com soma = 23) nao acontece que a divisao inteira de (a + b + c) por d de um valor "errado" igual a e. Com soma = 21 ja acontece ... e, segundo me parece, as solucoes Haskell apresentadas estao erradas ...

Exemplo: (1 + 6 + 7) / 3 = 4 (soma 21)

Para soma = 21 o problema apresentado nao tem solucoes!!

Edited February 17, 2013 by pmg

[pwseo 234]

No problema a resolver (com soma = 23) nao acontece que a divisao inteira de (a + b + c) por d de um valor "errado" igual a e. Com soma = 21 ja acontece ... e, segundo me parece, as solucoes Haskell apresentadas estao erradas ...

Sim, tens razão, mas já alterei o meu exemplo para funcionar correctamente. De facto esse foi um erro introduzido por mim ao utilizar a divisão inteira (já tinha discutido isso com o thoga31 mas voltei a esquecer-me).

No teu exemplo em C isso não acontece porque há conversão dos inteiros para doubles durante o cálculo (acho eu), e o resultado final é truncado para um int. Como em Haskell os dados são fortemente tipados, tal conversão implícita não ocorre.

Solução: deixo o Haskell fazer os cálculos com Doubles (como já acontecia no exemplo do thoga) e converto o resultado final para Integer.

Edited February 17, 2013 by pwseo

[pmg 86]

No teu exemplo em C isso não acontece porque há conversão dos inteiros para doubles durante o cálculo ...

Not quite

O codigo apresentado por mim apenas faz calculos inteiros.

O que acontece é que eu verifico o resultado da divisao inteira e o resultado do modulo

// ...
if ((a + b + c) / d != e) continue; // divisao
if ((a + b + c) % d == 0) printf("(%d + %d + %d) / %d = %d\n", a, b, c, d, e); // modulo
// ...

[pwseo 234]

Tens razão, não vi com atenção suficiente. Obrigado pelo reparo, de qualquer modo.

Aqui fica a correcção

Edited February 17, 2013 by pwseo