puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Michael Wojcik on 22 Jun 2005 09:05 In article <Pine.LNX.4.60-041.0506211205310.3192(a)unix50.andrew.cmu.edu>, "Arthur J. O'Dwyer" <ajo(a)nospam.andrew.cmu.edu> writes: > > Which APL variants have XOR as an atomic operator? I can't find it > in the J manual. (I was going to point out that (if XOR existed in APL) > the complete XOR program would be three characters long.) According to my handy APL reference card, the not-equal operator (which is represented by the mathematical not-equal glyph, the equals sign with a slash through it) can also be used for XOR. However it appears that's only for vectors of Boolean values (ie it's just a logical operator, not a bitwise one). My mistake. I did run across an APL variant (Micro-APL) which implemented bitwise operators with &, !, and | for AND, OR, and XOR. (That's the "broken" vertical bar for XOR - the solid one is used in APL for residue and absolute value, of course.) So in Micro-APL you could do: a{<-}(1 2 3 4 5 3) |/a 3 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. -- Michael Wojcik michael.wojcik(a)microfocus.com Unlikely prediction o' the day: Eventually, every programmer will have to write a Java or distributed object program. -- Orfali and Harkey, _Client / Server Programming with Java and CORBA_
From: pete on 22 Jun 2005 06:29 Richard Harter wrote: > > On Wed, 22 Jun 2005 01:49:41 GMT, pete <pfiland(a)mindspring.com> wrote: > > >If you only had to do a single pivot selection, > >then the whole algorithm would be O(n), > >but you have to do pivot selections O(log(n)) times. > > > >I'll take back the O(n * n) worst case claim, > >but an O(n) operation, done O(log(n)) times, > >is an O(n * log(n)) algorithm. > > You are missing a point. There are indeed log(n) selections but costs > are n, n/2, n/4, etc, for a total cost of 2n which is O(n). Think > about it; if you really don't see it ask again, and I will be > tediously detailed in the analysis. OK. I take it all back. As Tim Rentsch said, "clever algorithm!" /* BEGIN new.c */ #include <stdio.h> long unsigned f(long unsigned x); int main(void) { long unsigned x; for (x = 1; x != 100; ++x) { printf("x is %lu, f(x) is %lu\n", x, f(x)); } return 0; } long unsigned f(long unsigned x) { long unsigned count; for (count = 0; x != 0; count += x) { x /= 2; } return count; } /* END new.c */ -- pete
From: CBFalconer on 22 Jun 2005 21:50 karen wrote: > <spinoza1111(a)yahoo.com> wrote in message > .... snip ... >> >> STILL fails to work for floating point systems because in FP >> systems there can be >1 bitwise representation of the same n. > > Never mind the validity of the code. Do you recall the original > specs? > > "ok here is a puzzle. there is an integer array whose length is > odd, and all the the array appear exactly two times except one. > Find the number in O(n) time. Try to do it without using any > other data structure." > > Note that word "INTEGER". It doesn't HAVE to work for floating > point systems! Shhh. You might interfere with the exposition of his erudition. -- Some informative links: news:news.announce.newusers http://www.geocities.com/nnqweb/ http://www.catb.org/~esr/faqs/smart-questions.html http://www.caliburn.nl/topposting.html http://www.netmeister.org/news/learn2quote.html
From: Randy Howard on 22 Jun 2005 22:08 In article <42BA10C2.73ECA87D(a)yahoo.com>, cbfalconer(a)yahoo.com says... > karen wrote: > > <spinoza1111(a)yahoo.com> wrote in message > >> STILL fails to work for floating point systems because in FP > >> systems there can be >1 bitwise representation of the same n. > > > > Never mind the validity of the code. Do you recall the original > > specs? > > > > "ok here is a puzzle. there is an integer array whose length is > > odd, and all the the array appear exactly two times except one. > > Find the number in O(n) time. Try to do it without using any > > other data structure." > > > > Note that word "INTEGER". It doesn't HAVE to work for floating > > point systems! > > Shhh. You might interfere with the exposition of his erudition. No force on earth seems capable of that. -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs
From: Arthur J. O'Dwyer on 23 Jun 2005 13:37
On Wed, 22 Jun 2005, Michael Wojcik wrote: > > "Arthur J. O'Dwyer" <ajo(a)nospam.andrew.cmu.edu> writes: >> >> Which APL variants have XOR as an atomic operator? I can't find it >> in the J manual. (I was going to point out that (if XOR existed in APL) >> the complete XOR program would be three characters long.) > > According to my handy APL reference card, the not-equal operator > (which is represented by the mathematical not-equal glyph, the equals > sign with a slash through it) can also be used for XOR. However it > appears that's only for vectors of Boolean values (ie it's just a > logical operator, not a bitwise one). My mistake. Yeah, I found that out too. :) [...] > 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. 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]: a = 2 3 6 2 8 6 3 -> 2 3 6 2 8 6 3 #. ~:/ |: #: a -> 8 The second line says: Take 'a' and expand each of its entries in base 2. 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 Then apply the logical XOR operator ~: down each column of the transpose of that matrix, producing the row vector 1 0 0 0 Then compress that array down to the base-2 number 8. I'm sure there's at least one shorter way to do it. ;) -Arthur |