wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Compacting Pairs of Numbers
        
(Message started by: Virgilijus on Dec 21^st, 2015, 11:37am)

Title: Compacting Pairs of Numbers
Post by Virgilijus on Dec 21^st, 2015, 11:37am

After accidentally leaving the door open between the crocodile farm and the nursery, Willy has had to find another job. With his reputation preceding him, he can only find work in the boring and seemingly infinite Number Storage Warehouse.

On his first day, Willy's boss puts him to task; he needs to store every single unique pair of positive integers on the shelf. However, Willy has an idea; if he can take each unique pair and somehow transform them into a unique single number, he'll double the amount of pairs they can store (though his coworker, Mr. Cantor, disagrees) and perhaps he'll get a promotion.

Devise a way to transform a unique pair of positive integers (x,y) into a single, unique positive integer output (z). Note: order does matter to the pair i.e. f(x,y) = z implies f(y,x) =/= z.

Title: Re: Compacting Pairs of Numbers
Post by towr on Dec 21^st, 2015, 10:34pm

[hide]z = frombase10str(tobase9str(x) + '9' + tobase9str(y))
e.g. (123, 345) => 1469556; (987, 654) => 13169806
[/hide]
I bet there's more efficient ways though. [hide]I mean, aside from using a large base B and B+1.[/hide]

Title: Re: Compacting Pairs of Numbers
Post by rmsgrey on Dec 22^nd, 2015, 9:11am

A bijective mapping:

[hide]1) Convert y in Z to y' in N by taking the absolute value, doubling it, and subtracting 1 if y is negative.

2) Pad the shorter number with leading zeroes so they're the same length, then, starting with the first digit of x, interleave the digits of x and y' to produce a new number, z, with the same sign as x.

To reverse:

2') If z has an odd number of digits, pad it with a leading 0, then take alternate digits and the sign of z as x, and the remaining digits as y'

1') If y' is odd, add 1 and subtract the result from 0. Either way, halve that number to give y.[/hide]

Title: Re: Compacting Pairs of Numbers
Post by markr on Dec 23^rd, 2015, 10:45pm

[hide]
Similar to the diagonal method of mapping fractions to integers:

f(x,y) = (x^2 + y^2 + 2xy - 3x - y + 2) / 2
[/hide]

Title: Re: Compacting Pairs of Numbers
Post by towr on Dec 24^th, 2015, 1:06pm

Very nice, that.