puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Programmer Dude on 23 Jun 2005 16:52 Richard Harter writes: > Save the Earth now!! > It's the only planet with chocolate. Are you sure about that?
From: Richard Harter on 23 Jun 2005 17:32 On Thu, 23 Jun 2005 15:52:03 -0500, Programmer Dude <Chris(a)Sonnack.com> wrote: >Richard Harter writes: > >> Save the Earth now!! >> It's the only planet with chocolate. > >Are you sure about that? > I'm sure. I may be wrong, but I'm sure. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: pete on 24 Jun 2005 08:51 Michael Wojcik wrote: > In article <1119251599.617332.209790(a)g43g2000cwa.googlegroups.com>, > spinoza1111(a)yahoo.com writes: > > You > > have to assume that "in addition to test for equality, we can regard > > numbers as bitwise accessible". > > 1. This assumption does not affect the representation of the > algorithm's efficiency in big-O notation. > > 2. This assumption is unnecessary; XOR can be implemented without > access to the numbers' bitwise representation, since it's possible > to compute a number's base-two representation (in linear time). unsigned uint_xor(unsigned a, unsigned b) { unsigned result = 0; unsigned factor = 1; unsigned sum = a + b; do { result += sum % 2 * factor; factor *= 2; a /= 2; b /= 2; sum = a + b; } while (sum != 0); return result; } -- pete
From: Richard Harter on 24 Jun 2005 10:33 On 22 Jun 2005 12:41:45 GMT, mwojcik(a)newsguy.com (Michael Wojcik) wrote: > >In article <1119251599.617332.209790(a)g43g2000cwa.googlegroups.com>, spinoza1111(a)yahoo.com writes: >> You >> have to assume that "in addition to test for equality, we can regard >> numbers as bitwise accessible". > >1. This assumption does not affect the representation of the >algorithm's efficiency in big-O notation. > >2. This assumption is unnecessary; XOR can be implemented without >access to the numbers' bitwise representation, since it's possible >to compute a number's base-two representation (in linear time). AFAIK computing the base-two representation of a number m requires O(log n) arithmetic operations. Ergo give that there n/2 distinct pairs the cost of the XOR scheme is O(n* log(n)) if we have to build the XOR operation by hand. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: Michael Wojcik on 24 Jun 2005 18:20
In article <Pine.LNX.4.60-041.0506231317130.4095(a)unix48.andrew.cmu.edu>, "Arthur J. O'Dwyer" <ajo(a)nospam.andrew.cmu.edu> writes: > > > In standard APL, you'd have to write some support code to convert an > > integer to an array of Booleans so you could apply {not-equal} to it. > > Actually, now that I think more about it, it's not that bad. Well, of course in APL changing an integer into an array of something usually isn't... > It's been a > semester since I went on my APL kick, so I'm having trouble remembering > that APL's matrix operations are really cool. In J notation, I think > you can do the following [UNTESTED]: I don't know the J notation, though I'll look it up when I have a moment. I did some experimenting in OpenAPL and came up with the following. It's a lot longer than your solution and uses a couple of constants and a temporary (though still all within one expression), because I don't know what the APL equivalent is of the J operators you used to do the expansion in base 2 and the compression back down to base 10, so I had to do it manually. But it's a fun exercise. Here's my version: +/(2*-c-{rho}c){times} ({noteq}/(1+c{eta}c{<-}{iota}{ceil}2{log}{ceil}/x){represent}x) That should be written all on one line, which is easy in APL notation. Everything in curly-braces is actually a single symbol. {rho} is the Greek letter rho; {<-} is the left-pointing arrow; etc. There's an image of it here: http://pws.cablespeed.com/~mwojcik/find-unique-apl.png The array of numbers is in x, eg via x{<-}(1 3 6 4 2 6 3 4 5 5 1). The program works as follows (reading right to left, bottom line first): 1. {ceil}/x applies the {ceil} operator, which is also "max", to the array. The result is the largest value in the array (6). 2. {ceil}2{log} applied to the result above gives the ceiling of the log base 2 of the largest value in the array. That's the number of bits to use for each value (so this program is independent of the machine's word size, and will work for integers of any size that the APL implementation can handle). Here that's 3, of course. 3. The {iota} operator applied to that number generates the array [1,n], where n is the operand. So it produces (1 2 3). 4. That array is assigned to a temporary variable c with c{<-}. 5. c{eta}c is the set member-of function; for each element in the left operand, it evaluates to 1 if that element is a member of the right operand. Since each element of a set is a member of that set, this produces the boolean vector of 1's that's as long as the number of elements in c: (1 1 1). 6. 1+ adds 1 to each element of that result: (2 2 2). 7. The result of step 6 becomes the left operand for the APL {represent} operator; its right operand is x, our original array. {represent} says "create a matrix where each column represents the corresponding element of the right operand, and each row is the integer part of the quotient of that element divided by m**r, where r is the row number and m is the r'th element of the left- hand operator" (or something like that). Since the left operator is an array of (2 2 2...), we get: 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 which is a matrix of the binary representations of the numbers in the original array. Hurrah! 8. Across that whole thing we apply the {noteq} operator, with {noteq}/, giving: 0 1 0 Ah ha - we have our answer (2, in its binary representation). Everything else is just UI candy. 9. The remaining bit will turn that back into a base-10 number. First, we take {rho}c, which is the "shape" of c - here its length, 3. (Remember that c is our array (1 2 3), which we used above to create an array of 2's of the appropriate length.) 10. Subtract the size of c from each element in c and negate the result, with -c-{rho}c, to get (2 1 -0). Don't worry about that negative 0. 11. We take 2 to the power of that array, with 2*, and get (4 2 1). 12. Multiply that by our answer from step 8, using the {times} operator, and get (0 2 0). 13. Apply + across that vector, summing its members, and get 2. Short and sweet and pretty as a picture, and it uses just as many bits per array item as necessary. One of these days I'll have to find a real APL reference, rather than just experimenting with my reference card and a few sample programs at hand... -- Michael Wojcik michael.wojcik(a)microfocus.com Therefore, it is possible to enjoy further by using under the Netscape 2.0. However, Netscape will hangup at sometimes. You should give it up. -- roro |