puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Richard Harter on 16 Jun 2005 14:22 On 9 Jun 2005 21:39:13 -0700, "Darius" <ranveerkunal(a)gmail.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. Some notes on this puzzle: Firstly, people aren't quite getting right the properties of the xor operator that enable the cute little trick. They are: For all a,b,c a^a = 0 // Self inverse a^0 = a // 0 is an identity a^b = b^a // commutative a^(b^c) = (a^b)^c // associative People tend to overlook the need for the associative property. It might be supposed that using xor is a frivolous, accidental solution based on a happenstance feature of the representation of integers. Not so. Boolean vectors over an orthonormal basis are fundamental. As has been pointed out, in some representation systems some values can have more than one bit representation, e.g., one's complement arithemetic has +0 and -0. The xor scheme can still be used by using a canonical representation. The trick can also be applied to an array of strings. One way is to create a composite representation for each string consisting of the string length, the string itself, and padding with zeroes out to the maximum string length. The details are left to the student as an exercise. Now let us generalize a bit and remove the xor solution. Suppose we have an array of elements E with a defined order relationship. That is, for any pair of elements either one is greater than the other or they are equal, and transitivity holds, i.e., for all a,b,c : a<b and b<c => a<c If the array may be rearranged then we can again find the singleton with O(1) space and O(n) time. The general idea is to select a pivot value and then partition the array into elements smaller than the pivot, equal to the pivot, and larger than the pivot. If the pivot is the singleton we are done; otherwise repeat on the partition having an odd number of elements. If the cannot be altered we can still do it in O(1) space and O(n*log(n)) time by doing a virtual partitioning. If there is no ordering relationship, only equality, then we can use the obvious O(n**2) algorithm. There is more that can be said about this puzzle, but this is all I wish to say for the moment. 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: spinoza1111 on 17 Jun 2005 06:25 Note: Randy Howard's trolling of this thread will be ignored as requested by others. Christopher Barber wrote: > spinoza1111(a)yahoo.com wrote: > > > > Christopher Barber wrote: > > >>>One real problem, however, with the XOR algorithm is that it assumes > >>>that your programming language can like C coerce to pure bit strings, > >>>and that this operation won't do something horrible. Most modern > >>>languages don't even permit these monkeyshines. > >> > >>Not true. Most modern languages do support bitwise operations on integers. > >>What languages are you thinking of that do not? True that many languages will > >>not let you access the bit-pattern of arbitrary data structures. > > > > Incorrect. Only C lets you "see" the bitwise representation of an > > integer. > > C, C++, C#, Java, VB all support efficient bitwise operations, including XOR, > on integers. What language are you thinking of that doesn't support this? You don't understand my point at all. It is that the use of XOR adds a new "equality" operator which in possible (if not actual) scenarios may fail, and accurate programming is concerned to minimize these scenarios, no matter what empirical laundry lists of programming languages can be produced. > > > Using XOR, you just happen to get lucky, in the sense that XOR just > > happens to be independent of bigendian and smallendian. > > It doesn't "just happen" to be independent of byte order, it is an inherent > quality of the operation. Sure, it's order-independent. But the idea that using XOR is somehow clever produces bitwise operations such as shifts which are order-dependent. > > > But the > > corrupting effect of this puzzle is that it will teach the tyro to keep > > on the lookout for bitwise stunts and sooner or later, said tyro will > > find some stunt that does depend on the order of bits. > > Any "stunt" involving XOR will not depend on the order of the bits. We know that. You need not remind us. > > >>>The validity of the operation for a floating point array forces the > >>>compiler implementor to guarantee that all floating point values will > >>>have the same bit pattern if they are equal. This guarantee in the case > >>>of fp simply isn't made in general, and the algorithm as actually > >>>implemented for a floating point array will FAIL as a result. > >> > >>Yes, that is correct, but the problem specified *integers* not floating > >>point numbers. > > > > It didn't state that the language, in which the algorithm was written > > in your case, had to support coercion of integers to bit strings. News > > fa-lash: this is unusual outside C. > > You only need bitwise operations on integers. You don't need to be able to > coerce integers to bit strings. BTW, there is no such data structure as a > "bit string" in C, and there is no coercion involved for integers. This is not true. What I am saying here is that for each data type the programmer has a human right to an isomorphic correspondence of his concepts of each data types. Programs that depend on a bit representation are therefore deficient. > > >>>It won't even work on an integer array if there are separate > >>>representations of negative and positive zero. Nearly all, but not all, > >>>modern machines use twos-complement which means that all integers have > >>>a unique bit pattern. > >> > >>I don't think there are *any* modern machines not using twos-complement > >>integers. Can you name one? > > > > Not off the top of my head. But keep in mind that there are all sorts > > of compact and embedded processors out there in computerland. > > Yes, I know, but I would be very suprised to find any kind of processor > using ones-complement. Furthermore, many recent languages explicitly > specify that integers are represented using twos-complement. > You don't understand the need for minimizing assumptions, I see. > >>Note that for either floating point or ones-complement you can fix the > >>representation > >>problem normalize all values to a canonical representation before applying > >>XOR. This doesn't change the time complexity of the algorithm. > > > > That won't work if the values are available only once, as in the case > > of an array which is being altered by another thread. > > Huh? If another thread is altering the thread and you are not using some > kind of lock, then there isn't any algorithm that will provide reliable > results. Well, this is just one more random constraint I thought to raise because it seems that we're really just playing around with constraints and solutions at this point in a way that is pointless. > > >>The only way this problem would be O(n^2) would be if it stipulated a > >>linked-list representation, excluded use of XOR and did not allow use of > >>external data structures. > > > > On the one hand, you can introduce constraints. On the other, you can > > find a deus ex machina. Therefore the theory does not categorise > > algorithms once and for all, it allows us to speak about properties of > > algorithms. > > > > But owing to corporate surveillance and its Benthamite potential, the > > speech is silenced by posters who have to treat the theory as a set of > > dead answers. > > You keep spewing this "corporate surveillance and Benthamite potential" > mantra. What does it mean? Whose speech is being silenced? The speech being silenced doesn't belong to anyone. Sure, the censor can nail an individual who owns some text. But a more general censorship silences ways of speaking including the ability to be clear about solutions. > > > I had to beat the XOR solution out of you. > > I think you are mixing posters up. Most of us didn't bother to post > the solution, because as you can see, it is very simple, and because > we didn't want to spoil it for people that had not figured it out yet. It's not at all "simple" in the sense of being elegant or minimal. I've shown this. Furthermore, the puzzle called for an answer, and anyone trying to get the answer simply didn't have to read the other posts. Therefore this is a lame and post-facto excuse for a silence that is the result of corporate surveillance and its Benthamite potential, where the bare possibility makes people afraid to be prolix or even clear, lest some clown subject their text to a negative interpretation. > > > I may have heard it in > > graduate school but it is a fairly useless bit of information. XOR has > > some interesting properties, it is true, and this may be because unlike > > And, Or and Not considered as individual operators, you can build all > > of propositional logic on top of a single Xor operator. > > Are you claiming you can implement the other bitwise operators using XOR? No, my mistake. The Sheffer Stroke (Nand) does this but not XOR.
From: spinoza1111 on 17 Jun 2005 06:32 CBFalconer wrote: > spinoza1111(a)yahoo.com wrote: > > CBFalconer wrote: > >> spinoza1111(a)yahoo.com wrote: > >>> > >> ... snip ... > >>> > >>> I still don't see the actual XOR solution. > >> > >> ^ represents XOR, as in C. a and b are any fixed arbitrary value. > >> Then the following lemmas hold: > >> > >> a ^ b ^ a == b > >> a ^ a == 0 > >> a ^ 0 == a > > > > OK, now you're talking. I had to beat it out of you, but I > > appreciate the thought. I've used XOR but only in assembler. > > ... snip 80 odd lines of ??? ... > > I don't know what you are smoking, but it had a better effect on > Coleridge. We should send that person from Porlock more often. In many ways, the Sixties were the death of the human race, because in that decade people learned that their humanity, including their desire to speculate and cohere, was something that could be properly expressed only recreationally, and the rest of the time they needed to be corporate drones. And I for one am tired of these dreamlike accusations of "smoking" something directed against an attempt to be coherent as opposed to fashionably brutal. I was wrong on XOR being able to simulate all the other Boolean operators. But the rest of the post merely states what you should know if you claim to be a programmer, and this is the avoidance of any form of excess assumption, perhaps even surplus to a claim in the language manual that the language requires integers to be implemented in a certain way. > > -- > Chuck F (cbfalconer(a)yahoo.com) (cbfalconer(a)worldnet.att.net) > Available for consulting/temporary embedded and systems. > <http://cbfalconer.home.att.net> USE worldnet address!
From: spinoza1111 on 17 Jun 2005 06:32 CBFalconer wrote: > spinoza1111(a)yahoo.com wrote: > > CBFalconer wrote: > >> spinoza1111(a)yahoo.com wrote: > >>> > >> ... snip ... > >>> > >>> I still don't see the actual XOR solution. > >> > >> ^ represents XOR, as in C. a and b are any fixed arbitrary value. > >> Then the following lemmas hold: > >> > >> a ^ b ^ a == b > >> a ^ a == 0 > >> a ^ 0 == a > > > > OK, now you're talking. I had to beat it out of you, but I > > appreciate the thought. I've used XOR but only in assembler. > > ... snip 80 odd lines of ??? ... > > I don't know what you are smoking, but it had a better effect on > Coleridge. We should send that person from Porlock more often. > > -- > Chuck F (cbfalconer(a)yahoo.com) (cbfalconer(a)worldnet.att.net) > Available for consulting/temporary embedded and systems. > <http://cbfalconer.home.att.net> USE worldnet address!
From: spinoza1111 on 17 Jun 2005 06:50
Christopher Barber wrote: > spinoza1111(a)yahoo.com wrote: > > > > Christopher Barber wrote: > > >>>One real problem, however, with the XOR algorithm is that it assumes > >>>that your programming language can like C coerce to pure bit strings, > >>>and that this operation won't do something horrible. Most modern > >>>languages don't even permit these monkeyshines. > >> > >>Not true. Most modern languages do support bitwise operations on integers. > >>What languages are you thinking of that do not? True that many languages will > >>not let you access the bit-pattern of arbitrary data structures. > > > > Incorrect. Only C lets you "see" the bitwise representation of an > > integer. > > C, C++, C#, Java, VB all support efficient bitwise operations, including XOR, > on integers. What language are you thinking of that doesn't support this? Your horizon is remarkably limited but at the same time, and in another dimension, you demand a lack of structure. Your horizon is limited to a laundry list of existing programs. But complementary to this you want to violate notation (where equal means equal) to "solve" a problem. Complexity theory is independent of machine architecture in the sense that one needs complexity theory to survive radical novelties in machine architecture, Therefore a "solution" that demands the right to replace equality with an assumption about the ways in which numbers will be represented is simultaneously too respectful of existing programming language while disrespectful of any mathematics capable of surviving change. The original intention of the earliest programming languages was the worthy one of allowing the scientist or mathematician to thing not in terms of bits but of numbers, but here the solution reverts back to programmer control by way of assembly language in a passive-aggressive fashion. It seems to me that an abstract complexity theory has the right to demand, independent of existing programming languages, that the only way to express equality is using the equals sign, and not to rely on a whole new set of assumptions. No matter how many existent programming languages support bitwise operations on integers assumed without argument to be twos-complement, mathematics has to be "ignorant" of this factoid in order to ensure that its results can be reused when preconditions change. I conclude that this "puzzle" has no place in complexity theory. Instead, it belongs in a class called Stupid C Tricks. I am obliged to you for your information, which won't spoil any poster's enjoyment of solving the problem on his own, since if he has common sense he won't read random posts until he has solved the problem. I apologize for my own stupid error when I confused Nand and Xor. But because this thread has become infected by the troll Randy Howard I suggest we pack it in. You have along one dimension a looser metatheory in which we can treat C as a form of computer science (which it isn't) while along another a rigid respect for existing implementations which indicate at this time that twos-complement is the best way of representing numbers. I think that independent of today's favored implementations we have only one way of thinking about equality, in which an object, such as a number, cannot undergo a real transformation to something else, a bit string, for the convenience of the theoretical programmer. I suggest we pack it in and agree to disagree. |