27 views

Skip to first unread message

May 28, 2011, 2:56:54 AM5/28/11

to scala...@googlegroups.com

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.

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.

May 28, 2011, 3:11:21 AM5/28/11

to HamsterofDeath, scala...@googlegroups.com

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

--Russ P.

http://RussP.us

May 28, 2011, 3:50:57 AM5/28/11

to Russ Paielli, HamsterofDeath, scala...@googlegroups.com

I don't think that's the right interpretation on the riddle. The three

participants aren't actually telling each other the results.

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>:

May 28, 2011, 4:34:56 AM5/28/11

to scala...@googlegroups.com

exactly. the statements made can only be true for exactly one pair of

numbers. to figure out the pair is the riddle.

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

May 28, 2011, 10:43:20 AM5/28/11

to HamsterofDeath, scala...@googlegroups.com

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.

Okay:

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

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

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

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

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

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

}))

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 }

})

...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

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

May 28, 2011, 11:20:51 AM5/28/11

to Rex Kerr, HamsterofDeath, scala...@googlegroups.com

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

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

May 28, 2011, 11:36:13 AM5/28/11

to Alec Zorab, HamsterofDeath, scala...@googlegroups.com

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

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

May 30, 2011, 3:51:05 PM5/30/11

to Rex Kerr, Alec Zorab, scala...@googlegroups.com

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.

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.

May 30, 2011, 4:58:45 PM5/30/11

to HamsterofDeath, Rex Kerr, Alec Zorab, scala...@googlegroups.com

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 ?

- val someVal = {
- val firstElem = ...
- val secondElem = firstElem.someMethod(...)
- }

- val firstElem = ...
- val someVal = firstElem.someMethod(...)

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

--

ENSEIRB-MATMECA - student

TECHNICOLOR R&D - intern

BORDEAUX I - master's student

SCALA - enthusiast

May 30, 2011, 5:19:31 PM5/30/11

to HamsterofDeath, scala...@googlegroups.com

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

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

May 30, 2011, 5:22:46 PM5/30/11

to scala...@googlegroups.com

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 ?

val someVal = {

val firstElem = ...

val secondElem = firstElem.someMethod(...)

}

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.

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 :

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

val firstElem = ...

val someVal = firstElem.someMethod(...)

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu