puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 28 Jun 2005 14:34 spinoza1111(a)yahoo.com wrote: > I conclude that the XOR solution is junk, in part because I didn't > think of it, and in part because it sucks. It requires either a magic > transformation of integers into their binary representation, > acceptable > in practical contexts, but theoretically unacceptable. The notion that bitwise operations would be off topic in a comp.programming puzzle, is bizarre. -- pete
From: spinoza1111 on 29 Jun 2005 06:01 pete wrote: > spinoza1111(a)yahoo.com wrote: > > > I conclude that the XOR solution is junk, in part because I didn't > > think of it, and in part because it sucks. It requires either a magic > > transformation of integers into their binary representation, > > acceptable > > in practical contexts, but theoretically unacceptable. > > The notion that bitwise operations would be off topic > in a comp.programming puzzle, is bizarre. I didn't say that bitwise operations were offtopic. I said that as a solution illustrative of complexity theory they suck and blow. > > -- > pete
From: Randy Howard on 29 Jun 2005 12:00 On Wed, 29 Jun 2005 05:01:07 -0500, spinoza1111(a)yahoo.com wrote (in article <1120038300.118485.221930(a)g43g2000cwa.googlegroups.com>): > > > pete wrote: >> spinoza1111(a)yahoo.com wrote: >> >>> I conclude that the XOR solution is junk, in part because I didn't >>> think of it, and in part because it sucks. It requires either a magic >>> transformation of integers into their binary representation, >>> acceptable >>> in practical contexts, but theoretically unacceptable. >> >> The notion that bitwise operations would be off topic >> in a comp.programming puzzle, is bizarre. > > I didn't say that bitwise operations were offtopic. I said that as a > solution illustrative of complexity theory they suck and blow. Only because it took you so long to understand it. By your own admission, if you had thought of it first you would have had a different opinion. You're really just upset at being caught out (yet again) by posting an incredibly poor solution to a programming problem that others blew holes in.
From: Christopher Barber on 1 Jul 2005 13:33 spinoza1111(a)yahoo.com wrote: >>ok here is a puzzle. >>there is an integer array whose length is odd, and all the numbers in >>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! > > Real programming is not a matter of solutions isomorphic to problems, > and responding to one problem as expressed "today" with a solution > tuned to that problem. > > Instead, the real programmer recognizes, as an aura around the user's > expression of the problem, a genuine class of problems to which today's > problem will evolve. Often solving the problem as stated is exactly what is needed in "real programming", but you are right that it can be important to recognize how to generalize your solutions. > He thus eschews solutions which are overly tuned, in a trickster > fashion, to one empirical property of the problem such as "integers". I don't see how "integers" is an empirical property of a problem. No experimentation was needed. The problem stated the data type. In the real programming world, you usually know the data types of your input in advance. You also neglect that the more significant limitiation to the problem definition is not that it specified integers but that it specified that each value appears exactly twice except for one unique value, this latter property seems much more strange than limiting the data set to integers. In any case, even if you generalize the problem there are a number of other O(n) and O(n log n) solutions that do not require use of XOR. The solution you posted was no better than O(n^3) and is obviously too expensive to use unless n is very small. It is also more expensive and takes more code than the brute-force O(n^2) solution, so there is no reason to use it even when n is small. No "real world" programmer would use such an algorithm, so it is strange to find you lecturing us about "real programming". > With which I think I shall end my participation in this thread. I rather doubt it. - Christopher
From: Gerry Quinn on 1 Jul 2005 14:22
In article <da3uov$6p5$1(a)grapevine.lcs.mit.edu>, cbarber(a)curl.com says... > spinoza1111(a)yahoo.com wrote: > > He thus eschews solutions which are overly tuned, in a trickster > > fashion, to one empirical property of the problem such as "integers". > > I don't see how "integers" is an empirical property of a problem. No > experimentation was needed. The problem stated the data type. In > the real programming world, you usually know the data types of your > input in advance. You also neglect that the more significant limitiation to > the problem definition is not that it specified integers but that it specified > that each value appears exactly twice except for one unique value, this latter > property seems much more strange than limiting the data set to integers. Furthermore, the properties of XOR are not relevant only to integers. Indeed, the set of datatypes for which its properties are useful is larger than the set of numbers. A use which almost everyone will be familiar with is in graphics. An efficient way to draw an moving outline - such as the new size of a window or the region where an object is to be placed - on a typical memory-mapped display is to XOR the pixel data of the region to be outlined with a value that has all bits set, then XOR with that value again to restore the original pixel data. Depending on the display system, the results may be varied, but all but extraordinary circumstances you will get a visible line, and it's fast. With PC hardware nowadays it's not needed, but it was used on Windows until quite recent versions, and is probably still in use in many systems. Observe, incidentally, that this will work even if the pixel data is in the form of floating point numbers! The reason XOR might not work on a floating point version of the puzzle discussed here might in fact be considered an empirical property or quirk of the floating point equality operator and/or the floating point arithmetic system, rather than XOR. The operator considers two numbers equal when their representation is different, because the arithmetic system represents the same number in different ways when it feels like it. Surely *that's* something of an empirical fact about how computer software/hardware works? - Gerry Quinn |