a hard riddle

[HamsterofDeath]

not exactly scala related, but i was trying to solve it in scala and i
suspect some people here would have fun with it.
there are 3 people. let's name them peter, simon and daniel. the three
are supposed to figure out a pair of numbes. the possible pairs are all
combinations of numbers from 0 to 1000, meaning:
(0,0), (1,0), (2,0)....(1000,0),(1,1),(1,2) up to (1000,1000)
peter knows the product of the pair, simon knows the sum, and daniel
knows the difference.

the following conversation takes places:

peter: i don't know the solution
simon: i already knew that
peter: know i know the solution
simon: know i know it, too
daniel: wtf? i can only suspect one of the numbers but can't be sure
peter: the number you are suspecting is wrong
daniel: k, now i now the numbers, too

i'll post my solution as soon as i get one, including the scala code
thar produces it. have fun.

[Russ Paielli]

I'm not sure I understand the problem, but if you know the sum and difference, that's two independent equations in two unknowns. The solution is simple. Just add the two equations, and one of the variables drops out. Subtract the two equations, and the other variable drops out.

--Russ P.

--
http://RussP.us

[Ruediger Keller]

I don't think that's the right interpretation on the riddle. The three
participants aren't actually telling each other the results.

It seems you can determine the numbers without knowing the sum,
product and difference.

At least, that is my interpretation of the riddle.

Regards,
Rüdiger

2011/5/28 Russ Paielli <russ.p...@gmail.com>:

[HamsterofDeath]

exactly. the statements made can only be true for exactly one pair of
numbers. to figure out the pair is the riddle.

Am 28.05.2011 09:50, schrieb Ruediger Keller:
> I don't think that's the right interpretation on the riddle. The three
> participants aren't actually telling each other the results.
>
> It seems you can determine the numbers without knowing the sum,
> product and difference.
>
> At least, that is my interpretation of the riddle.
>
> Regards,

> R�diger

[Rex Kerr]

Spoiler warning...code to solve the problem is here.  I didn't actually give the answer, but Scala will if you paste everything into the REPL.

On Sat, May 28, 2011 at 2:56 AM, HamsterofDeath <h-s...@gmx.de> wrote:

there are 3 people. let's name them peter, simon and daniel. the three
are supposed to figure out a pair of numbes. the possible pairs are all
combinations of numbers from 0 to 1000, meaning:
(0,0), (1,0), (2,0)....(1000,0),(1,1),(1,2) up to (1000,1000)

Okay:

val pairs = for (i <- 0 to 1000; j <- i to 1000) yield (i,j)
 

peter knows the product of the pair, simon knows the sum, and daniel
knows the difference.

the following conversation takes places:

peter: i don't know the solution

So we know that Peter knows that the product is not unique.  Let's call this the "Peter Property".

val pprop = pairs.groupBy(p => p._1*p._2).filter(_._2.size > 1).map(_._2).flatten.toSet
 

simon: i already knew that

This means that Simon knows that for the sum, every product between 0*sum and (sum/2)*(sum/2) has the Peter Property.  Let's call this the "Simon Property".

val sprop = pairs.filter(p => {
  val sum = p._1 + p._2
  (0 to (sum/2)).forall(i => pprop contains ((i,sum-i)))
}).toSet
 

peter: now i know the solution

Out of all the pairs that might make up Peter's product, exactly one has the Simon Property.  Let's call this these the "Peter Possibilities".

val pposs = pprop.groupBy(p => p._1 * p._2).values.
   map(_.filter(sprop contains)).filter(_.size==1).flatten.toSet
 

simon: now i know it, too

Out of all the pairs that might make up Simon's sum, exactly one is a Peter Possibility.  Let's call these the "Simon Possibilities".

val sposs = sprop.groupBy(p => p._1+p._2).values.
    map(_.filter(pposs contains)).filter(_.size==1).flatten.toSet
 

daniel: wtf? i can only suspect one of the numbers but can't be sure

The difference between the numbers is not unique, and furthermore, within that set of pairs, one number is overrepresented (but does not occur in every pair--this means there must be at least three pairs).  Let's call this the Daniel Dilemma.

val ddilem = sposs.groupBy(p => p._1 - p._2).values.filter(lp => (lp.size > 2 && {
  val ns = lp.toList.map{ case(i,j) => List(i,j) }.flatten
  (ns.toSet.size < ns.size && lp.exists{ case (i,j) => ns.filter(_==i).size == 1 && ns.filter(_==j).size == 1 })
}))

peter: the number you are suspecting is wrong

We can throw away the pairs with that number in common.

val phint = ddilem.map(xs => {
  val ns = xs.toList.map{ case(i,j) => List(i,j) }.flatten
  xs.filter{ case (i,j) => ns.filter(_==i).size == 1 && ns.filter(_==j).size == 1 }
})
 

daniel: k, now i know the numbers, too

...and there exists only one number left for Daniel

val dknows = phint.filter(_.size==1)

And since we are supposed to know the answer now too, there should really be only one pair left.

dknows.head.head

  --Rex

[Alec Zorab]

Rex's solution is interesting because it's the first time I've seen
x.map(f).flatten do a different thing to x.flatMap(f). Having played
follow the types a little bit it becomes clear what's going on, but
it's an unusual example nonetheless

[Rex Kerr]

If you think I exploted the difference between flatMap and map+flatten intentionally, you're giving me too much credit.

When I'm quickly thinking and writing through a problem as I did here, I tend to use the most basic methods that accomplish what I'm looking for (e.g. map + flatten instead of flatMap).  The reason is that I don't know what I'm doing yet, and if I want to insert a logical step between the map and flatten, it's easier to do if I write it as map + flatten than as flatMap.  Note the map + filter + flattens, for example.  (flatCollect, anyone?)

  --Rex

[HamsterofDeath]

i solved it completely: http://pastebin.com/n0HKSFmr

however, the code is quite.... unreadable. when solving math problems, i always run into the problem that the code tends to become very, very abstract and i myself don't understand what exactly is going on if i don't add some images explaining the logic.

any idea how this code can be simplified a bit?
adding type annotations is obviously not going to help - what does map[int, iterable[(int,int)]] going to tell you? not much.

[Alex Repain]

2011/5/30 HamsterofDeath <h-s...@gmx.de>

i solved it completely: http://pastebin.com/n0HKSFmr

however, the code is quite.... unreadable. when solving math problems, i always run into the problem that the code tends to become very, very abstract and i myself don't understand what exactly is going on if i don't add some images explaining the logic.

any idea how this code can be simplified a bit?
adding type annotations is obviously not going to help - what does map[int, iterable[(int,int)]] going to tell you? not much.

Hum, first off, why the hell would you do this ?

1.     val someVal = {
2.     
   
3.       val firstElem = ...
4. 
   
5.       val secondElem = firstElem.someMethod(...)
6. 
   
7.     }

I really find it weird both to read and write. Just doesn't feel right enough. I can understand that you try grouping the computations in semantically relevant groups, but for a problem as "simple" (architecturally) as that riddle, why do you need this ? I would just write it like this :

1. val firstElem = ... 
2. 
   
3. val someVal = firstElem.someMethod(...)

Because as demonstrated by Rex, the problem would just fit into 7 Scala affectations, and boom goes the dynamite. I would start thinking about your style when designing a very deep problem solution, or a computing-oriented library, but not for this task. A scriptic style would feel clearer, faster, and more natural to me. I would also rethink the blank lines and comments. Maybe there's a logic behind them, but from one step backward, it just seems messy...

Apart from that, I don't think there's anything I can say about your function chaining style, I use about the same aspects of scala ...

Am 28.05.2011 17:36, schrieb Rex Kerr:

If you think I exploted the difference between flatMap and map+flatten intentionally, you're giving me too much credit.

When I'm quickly thinking and writing through a problem as I did here, I tend to use the most basic methods that accomplish what I'm looking for (e.g. map + flatten instead of flatMap).  The reason is that I don't know what I'm doing yet, and if I want to insert a logical step between the map and flatten, it's easier to do if I write it as map + flatten than as flatMap.  Note the map + filter + flattens, for example.  (flatCollect, anyone?)

  --Rex

On Sat, May 28, 2011 at 11:20 AM, Alec Zorab <alec...@googlemail.com> wrote:

Rex's solution is interesting because it's the first time I've seen
x.map(f).flatten do a different thing to x.flatMap(f). Having played
follow the types a little bit it becomes clear what's going on, but
it's an unusual example nonetheless

--
Alex REPAIN
ENSEIRB-MATMECA - student
TECHNICOLOR R&D - intern
BORDEAUX I      - master's student
SCALA           - enthusiast

[Rex Kerr]

On Mon, May 30, 2011 at 3:51 PM, HamsterofDeath <h-s...@gmx.de> wrote:

i solved it completely: http://pastebin.com/n0HKSFmr

however, the code is quite.... unreadable.

Mathematics is often hard to read in code.

But using long uninformative variable names really doesn't help.  Observe:

  val everySinglePossiblePairInTheProblem =
    for (firstNumberInPair <- lowestNumberInRange to highestNumberInRange;
        secondNumberInPair <- firstNumberInPair to highestNumberInRange) yield {
      firstNumberInPair -> secondNumberInPair
  }

vs.

  val ps = for (i <- i0 to i1; j <- i to i1) yield (i,j)

In the first case, there is _way too much text_ to easily see what is going on.  The second case might be too brief (e.g. I chose "pairs" not "ps" in my code), but I'm pretty sure most people will be able to decipher the intent of the second well before the first.

There are probably other ways to make the code more readable, but keeping variable names short and maximally to the point is a big help in mathematical code.

  --Rex

P.S. Here's a probably-close-to-optimally-short solution without comments based on my previous code.  I wouldn't call it readable (or efficient), just short.  (Sadly, the compiler special-cases unary operators so I need double symbols.)

val pairs = for (i <- 0 to 1000; j <- i to 1000) yield (i,j)

val ** = (p: (Int,Int)) => p._1 * p._2
val ++ = (p: (Int,Int)) => p._1 + p._2
val -- = (p: (Int,Int)) => p._1 - p._2
def ::(p: (Int,Int)) = p._1 :: p._2 :: Nil
val peter = pairs.groupBy(**).values.filter(_.size > 1).flatten.toSet
val simon = pairs.filter(p => (0 to ++(p)/2).map(i => (i,++(p)-i)).forall(peter)).toSet
val peter2 = peter.groupBy(**).map(_._2.filter(simon)).filter(_.size==1).flatten.toSet
val simon2 = simon.groupBy(++).map(_._2.filter(peter2)).filter(_.size==1).flatten.toSet
def count(ps: Iterable[(Int,Int)]) = ps.toList.flatMap(::).groupBy(identity).mapValues(_.size)
def solo(ps: Iterable[(Int,Int)]) = { val c = count(ps); ps.map(::).filter(_.forall(c(_)==1)) }
def up(a: Int, b: Int, c: Int) = (a < b) && (b < c)
val daniel = simon2.groupBy(--).values.filter(lp => lp.size>2 && up(0, solo(lp).size, lp.size))
val daniel2 = daniel.map(solo).filter(_.size==1).flatten
val answer = daniel2.head

[HamsterofDeath]

Am 30.05.2011 22:58, schrieb Alex Repain:

2011/5/30 HamsterofDeath <h-s...@gmx.de>

i solved it completely: http://pastebin.com/n0HKSFmr

however, the code is quite.... unreadable. when solving math problems, i always run into the problem that the code tends to become very, very abstract and i myself don't understand what exactly is going on if i don't add some images explaining the logic.

any idea how this code can be simplified a bit?
adding type annotations is obviously not going to help - what does map[int, iterable[(int,int)]] going to tell you? not much.

Hum, first off, why the hell would you do this ?

1.     val someVal = {
2.     
   
3.       val firstElem = ...
4. 
   
5.       val secondElem = firstElem.someMethod(...)
6. 
   
7.     }

because i can. why should intermediate variables be visible after someVal has been calculated? if i just write them flat, the reader cannot see immediately where the vals are used. using "my style", you can. actually, i consider this a strength of scala. you can nest anything as deep as you want.
think of it like an inner or private method that just happens to be declared as a val, but might be made a def and/or moved to the outside should i decide to want to do that. this is difficult if there are only flat val declarations. having a structure increases to number of options you have and assumptions you can make about the code.

I really find it weird both to read and write. Just doesn't feel right enough. I can understand that you try grouping the computations in semantically relevant groups, but for a problem as "simple" (architecturally) as that riddle, why do you need this ? I would just write it like this :

1. val firstElem = ... 
2. 
   
3. val someVal = firstElem.someMethod(...)

Because as demonstrated by Rex, the problem would just fit into 7 Scala affectations

if i inline everything, i bet it fits into a single expression :)

, and boom goes the dynamite. I would start thinking about your style when designing a very deep problem solution, or a computing-oriented library, but not for this task. A scriptic style would feel clearer, faster, and more natural to me. I would also rethink the blank lines and comments. Maybe there's a logic behind them, but from one step backward, it just seems messy...

the blank lines are more or less random. the comments are fine. don't you dare talking bad about them.