A little math puzzle for you all

[thepenguin]

If you have two buckets, each with a volume of fluid inside, which we will assume to be an even integer.

If the two volumes are A and B, find a physically possible method of obtaining a quantity of liquid with volume (A xor B).

(And yes, this is a little more than just a random thought experiment)

EDIT: By XOR, I meant bitwise xor...

 

[statickid]

Um... Fill up only one bucket?

 

[Artlav]

If you mean xor as bitwise operation on integers:
Get four set of buckets, each twice as small as the next, starting with the original ones.

Look at the bucket A - it have a total volume (A'), and a volume of liquid (A). Get the liquid in upper half of the total volume into one A'/2 bucket, and from the lower half into the other one (pour A' into A'/2, if A'/2 is full, pour the remainder into the second A'/2).
You now have either a full A'/2 bucket and a partial A'/2 bucket, or an empty one and partial one.
The full/empty one is your highest-order bit, the partial one is the remainder.

Now repeat all of it with partial A'/2 and A'/4s, partial A'/4 and A'/8s and so on until you get a set of either empty or full smaller buckets.

Then, repeat with B, and pad the bucket count with empty buckets until it's the same as A or vice-versa.

Now you have the integers decomposed into binary.
Perform the XOR operation (put the two sets side to side, pick each full bucket that have an empty pair), dump the resulting water into bucket C, done!


It's kind of a brute-force approach - i can't think of any "clever" way to do it.
Or maybe you meant some other kind of XOR?

 

[BLANDCorporatio]

I liked statickid's answer because while facetious (isn't it?) it's also correct in a way, and highlights a problem with the problem. Just what extra props can we bring to bear on it?

Artlav's solution is also correct, by the parameters of the problem. Hey, it's "physically possible", which is what you wanted.

EDIT: my candidate solution was WRONG, that's not how you get powers of 2.

Anyway, an interesting observation, I think: with a pair of buckets A and B, you can compute A mod B. Also, if A and B are even, A mod B is even (2*n mod 2*m: let n=k*m + n mod m; then 2*n = k*2m + 2*(n mod m); (n mod m) < m then 2*(n mod m) < 2m)

 

[thepenguin]

If you mean xor as bitwise operation on integers:
Get four set of buckets, each twice as small as the next, starting with the original ones.

You don't know the volumes of the original buckets, though...

 

[BLANDCorporatio]

I do wonder whether the problem is well posed then.

Are A and B measured in litres? Or gallons? There'll be different results.

Anyway, in some unit of measurement, the volumes must be even integers- as you've stated in the problem description. For this to make sense, we need to know what that unit of measurement is.

Then just get a bucket of the appropriate unit of volume and measure A and B.

 

[Artlav]

You don't know the volumes of the original buckets, though...

Get a bucket big enough, pour water out of A into it, fill A to the brim, pour the result into a rectangular container, measure the volume.

Alternatively, you can measure the volumes of liquid in A and B, find the integer base for them, and derive volumes from there.

But if you have a ruler and can do math, then you can skip all the intricates, and just compute the volumes of A and B, do the math, and measure out the volume of XOR.


On a related note, if you ask N different people "Imagine a forest. Now, tell me what you see", then you would get N different answers (especially in a diverse community like ours) - each person would remember his most memorable image of a forest, and describe it.
In simple terms - constrain your problems to get useful solutions.

i.e. if A and B are integers, then A*3 and B*3 are also integers, but A XOR B is not the same as (A*3) XOR (B*3), so your result would vary chaotically depending on which integers it is - integer number of litres? Integer number of cubic centimetres? Integer number of atoms? Or should we do a GCD first?

 

[statickid]

While it did seem facetious it was the only answer I could think of given the information.

I think as a logic problem isn't it important to know more information?


Is the even integer the volume of one bucket or both buckets?

Is there a requirement of having equal or unequally sized buckets?

Can a bucket be partially empty?

Do I have power to add more buckets and tools?

Finally, what really is the question? What constitutes truth in this scenario?

reasoning:

I HAVE two buckets with fluid IN them. The volume of the fluid is irrelevant due to the nature of the question.

It states that the volumes that I already HAVE are volume A and volume B.

At this point I see my original answer is backwards. The sizes of the buckets are also irrelevant; they don't need to be filled because they already have liquid.


The assignment says find a physically possible way to OBTAIN (A xor B). Since what I have in my possession is (A and B). I actually just need to dump out one bucket. Dump out volume A I have (B not A) dump out volume B and I have (A not B)

 

[thepenguin]

ok, maybe I was trying to be too clever. The problem in it's simplest form would be:

Given two integers, find their bitwise xor without converting them to binary numbers (or computing it directly, of course. I'm looking for a clever solution to this.)

 

[Artlav]

I'm looking for a clever solution to this.

Cleverness of the solution without stating the entire problem is about as meaningless as speed without stating the frame of reference.

Given two integers, find their bitwise xor without converting them to binary numbers (or computing it directly, of course.

Integers don't exist on their own. Are we talking apples and oranges?
Or grains of sand in buckets?

You have to define what physical objects do you want to manipulate.
Otherwise, the "physically possible method" answer will be this:

Which is an arithmetic and logic unit.
Perfectly physically possible, takes integers and an order, does XOR, gives answer.
Connect that to the output of sand grain counters, and your buckets will be turned into xor-ed number. Didn't compute it directly, just made a computing machine.

So, unless you want to find out all the many ways how to make a computer, you should clearly state what you have in mind.



Then,
Bitwise operations are defined only in terms of binary representation of numbers.
So, "don't convert to binary" could very well be a contradictional constraint.

Here is a little program for you:
http://orbides.1gb.ru/etc/bitwise.zip
It plots 256 of x and y, x from left to right, y from bottom to top, and each dot is X OP Y (shades of gray from 0 black to 255 white).
You can select the OP by left and right keys (xor, or, and, +, *, div, mod), and select scale by up and down.

For example, X xor Y looks like that:

The pattern continue to repeat as you look deeper.
Incidentally, it's very well compressible by lzw.

Any inspiration from the visuals?

 

[Albinon]

For Volume(A) XOR Volume(B):
If Volume(A) > Volume(B) then the resulting volume = Volume(A) - Volume(B)
If Volume(B) > Volume(A) then the resulting volume = Volume(B) - Volume(A)
If Volume(A) = Volume(B) then the resulting volume = 0

Place a mark in both buckets where the top of the volume lies. Empty the lesser bucket. Take the fuller bucket and pour it into the lesser until the volume reaches that mark. The answer is now in the fuller bucket.

If the two volumes are A and B, find a physically possible method of obtaining a quantity of liquid with volume (A xor B).

This is more of a logic problem than a math problem.

 

[BLANDCorporatio]

I'm afraid that candidate solution computes abs(A - B). It does not compute (A xor B).

Just an example: let A = 16, B = 1. A-B = 15, A xor B = 17.

I'm not sure whether the candidate solution uses repeated subtractions. I assumed not. Anyway, by repeated subtractions you will get volumes smaller than the originals. Whereas the little counterexample above shows, XOR can be greater than both numbers.

Anyway, I decided to cheat and google the thing.

Apparently, there's no end of people trying to answer a hacker.org challenge that (I think) goes like this: suppose you have a computer that does not have native bitwise operators. It can however perform {insert description of instruction set here}. Implement a XOR function.

For example, you may have either a very reduced instruction set computer, or a very reduced instruction set language, like braintenderloveandcare.

All solutions I've seen however imply constructing a sequence of variables that make the binary representation of your original operands.

So then, to make this problem clear, exactly which instruction set do we have? Are we allowed comparison operators? Which ones? Are we allowed arithmetic? Which ones? Based on that, pick one of the solutions in the stackoverflow threads I've linked to via google search above.

 

[Albinon]

Quote:
Originally Posted by BLANDCorporatio

I'm afraid that candidate solution computes abs(A - B). It does not compute (A xor B).

Just an example: let A = 16, B = 1. A-B = 15, A xor B = 17.

​

I do agree with you when using Binary math, however the problem originally stated physically possible method. Since XOR excludes like inputs, I considered equal volumes to be like inputs, if you will. Thus I removed the equal volumes.

More generally, XOR is true whenever an odd number of inputs is true. A chain of XORs—a XOR b XOR c XOR d (and so on)—is true whenever an odd number of the inputs are true and is false whenever an even number of inputs are true. http://en.wikipedia.org/wiki/Exclusive_or

Once again, the problem as stated is not specific enough for a proper solution to be had. It needs a clearer body of parameters. As stated it can have any number of solutions that can be valid.

 

[BLANDCorporatio]

Well then, why use the difference to represent XOR? After all, you might as well say, a non-zero volume is "true" (Which is the C convention) so if and only if one bucket of the two is empty, XOR is the volume of the nonempty bucket; if the previous condition fails, XOR is an empty bucket.

 

[thepenguin]

wow. Sorry to cause so much confusion here, I didn't think there were that many different interpretations possible :facepalm:. (one should never assume.)

probably a better way of phrasing this would be as follows:

How can the bitwise xor of two integers be computed without performing a binary decomposition of the two aforementioned integers?

A little more information on the problem:
The scenario consists of a cellular automata simulation where each cell has a certain value of fluid in it (each cell has an infinite capacity). This fluid exists in discrete quantities, and can be transported in particular units to interact with other volumes of the fluid. The fluid can also be an anti-fluid which annihilates an equal volume of the regular fluid on contact (think of it as a negative quantity).

 

[BLANDCorporatio]

I'm afraid a proper XOR implementation will contain some parts where you decompose the integers into binary representations. And that's ok, as long as it can be done with the "computer" you have. And since some cellular automata are Turing-complete, you can compute binary decompositions with them too

But your cellular automata is as yet unspecified. All we know is that each cell's state is described by an integer. We only assume (because it's typical of CA) that the cells are connected in a square (so two-dimensional) grid:

...- 0 - 0 - ...
... | | ...
...- 0 - 0 - ...
etc.

What's the update rule? How does a cell's contents change based on the neighbor's contents?

 

[thepenguin]

The update rule can take various forms, depending on ranges that the person who defines the system can also define. (BTW, yes, these are squares)

The options for any cell are as follows:
1. Updates can be shut off entirely for this cell. Its value will not change.
2. The cell will follow the "normal" update rules. These rules are approximately equal to the laws of thermodynamics.
3. A cell can function similarly to a "normal" cell, however it may have a "field" that will push its contents into neighboring cells along a force vector.

For the sake of simplicity, I am currently defining all cells to be option #1.

Also, all matter in the system is conserved (neither created nor destroyed), however it is possible to create large "reservoirs" of + and - fluid such that one can have a practically infinite supply of both.

 

[BLANDCorporatio]

(For clarity for future posters: thepenguin means the total amount of matter is conserved; yes, you can change a zero cell into a million plus matter and a million minus matter, but their sum is still zero)

Argh.

Just give me the text of the homework assignment already.

Or whatever you got from the person asking to solve it.

Because you still don't specify the rules of your automaton! It either does nothing (option one, a bit boring), or it "resembles thermodynamics" (HOW, exactly? are there rates of diffusion? what are they?), or you have these force vectors that act in unspecified ways on the cell's contents, on neighbors' contents, as well as each other (to these vectors even add? do they act on what's two cells away?)

Compare and contrast to [ame="http://en.wikipedia.org/wiki/Conway_game_of_life"]an actual cellular automaton specification[/ame]:

- square grid
- each cell has eight neighbors
- each cell can be alive or dead
- any live cell with fewer than two live neighbours dies, as if caused by under-population.
- any live cell with two or three live neighbours lives on to the next generation.
- any live cell with more than three live neighbours dies, as if by overcrowding.
- any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

And yep, while it's rather counterintuitive to do so, one can construct a Turing machine based on those rules. It can compute XOR and anything else.

 

[statickid]

(For clarity for future posters: thepenguin means the total amount of matter is conserved; yes, you can change a zero cell into a million plus matter and a million minus matter, but their sum is still zero)

Argh.

Just give me the text of the homework assignment already.

Or whatever you got from the person asking to solve it.

Because you still don't specify the rules of your automaton! It either does nothing (option one, a bit boring), or it "resembles thermodynamics" (HOW, exactly? are there rates of diffusion? what are they?), or you have these force vectors that act in unspecified ways on the cell's contents, on neighbors' contents, as well as each other (to these vectors even add? do they act on what's two cells away?)

Compare and contrast to an actual cellular automaton specification:

- square grid
- each cell has eight neighbors
- each cell can be alive or dead
- any live cell with fewer than two live neighbours dies, as if caused by under-population.
- any live cell with two or three live neighbours lives on to the next generation.
- any live cell with more than three live neighbours dies, as if by overcrowding.
- any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

And yep, while it's rather counterintuitive to do so, one can construct a Turing machine based on those rules. It can compute XOR and anything else.

...and when you press the "run simulation" button it makes cool patterns, as if by MAGIC!

 

[thepenguin]

Because you still don't specify the rules of your automaton! It either does nothing (option one, a bit boring), or it "resembles thermodynamics" (HOW, exactly? are there rates of diffusion? what are they?), or you have these force vectors that act in unspecified ways on the cell's contents, on neighbors' contents, as well as each other (to these vectors even add? do they act on what's two cells away?)

I probably shouldn't have mentioned modes 2 or 3... What I'm describing is this:
The Game

However, I am describing it rather badly, I take it.

By the way, I am familiar with Conway's Game of Life, and understand that most automata hava well-defined rulesets.