Algorithms

17-Jun-11 3:20

Hi all,

I am sure there are loads of samples around but I am really not finding a relevant one for some reasons (perhaps it's a Friday brain melt thing)

I have two points in 3D space - I know their coordinates (x, y, z) and I know their rotations (x, y, z)

I know this should be enough information to calculate a line (is it a vector? it's been sooo long since uni D'Oh! | :doh:

)

What I want is to calculate the point (x, y, z) where the lines intersect (if any). The Z axis is actually not important, I want an intersect point on only X and Y planes, the Z value of the point will be half way between the original 2 points Z value.

Can any shed some light, or has a link? All info I am finding doesn't seem to allow me to make use of my rotation data.

Thanks for any help

I may or may not be responsible for my own actions

dasblinkenlight17-Jun-11 5:51

17-Jun-11 5:51

Here is a very good tutorial[^], section 2 has what I think you're looking for. It deals mostly with 2D, but it is easily extended to 3D.

In general, I highly recommend TopCoder's tutorials on algorithms: very down-to-earth, they are often written by highly skilled "competition programmers" for other "competition programmers" (as opposed to typical coursework written by professors for students, often loaded with very important and equally boring details).

musefan17-Jun-11 5:55

17-Jun-11 5:55

Thanks I will take a look into this

I may or may not be responsible for my own actions

Roger Wright17-Jun-11 20:34

Roger Wright

17-Jun-11 20:34

I think we need a bit more information; you've said that you have two points in 3-space, but want to calculate the intersection of two lines. That does not compute, Will Robinson. Do you have equations for your two lines? If so, let one line be f(x,y,z) and the other g(x,y,z). Use simple linear algebra to solve for x, y, and z such that f(x,y,z) - g(x,y,z) = 0. If not, you really need to clarify your question.

Will Rogers never met me.

musefan21-Jun-11 0:12

21-Jun-11 0:12

the two points have rotation data which is how I consider them lines (infinitely long lines running thou the know point at the given angle)

I didn't have the line equations which turns out to be what I was actually trying to find.

I have worked it all out now anyway, but thanks for the reply

I may or may not be responsible for my own actions

BobJanova20-Jun-11 23:41

BobJanova

20-Jun-11 23:41

In general, lines in 3D do not intersect. The closest thing is the line-line closest approach[^] which is too complex to explain here, but that article is good.

The Z axis is actually not important, I want an intersect point on only X and Y planes
This leads me to believe that you actually want 2D line intersection. There are a number of ways to formulate that but a nice one is using the line equations:

Line 1 = (a1,b1) + k1(dx1,dy1) =>
  x1 = a1 + k1.dx1 and
  y1 = b1 + k1.dy1
Line 2 = (a2,b2) + k2(dx2,dy2) =>
  x2 = a2 + k2.dx2 and
  y2 = b2 + k2.dy2

Target: L1 = L2 =>
a1 + k1.dx1 = a2 + k2.dx2
b1 + k1.dy1 = b2 + k2.dy2

There are only four unknowns (k1 and k2, and the meeting point (x1,x2)). The bottom two equations eliminate the coordinates leaving two equations and two unknowns. Now eliminate k2 (k2 = (k1.dy1 + b1 - b2)/dy2):
  a1 + k1.dx1 = a2 + (dx2/dy2)(k1.dy1 + b1 - b2)
  k1(dx1 - [dx2.dy1/dy2]) = a2 + (dx2/dy2)(b1 - b2)
  k1 = [a2 + (dx2/dy2)(b1 - b2)] / (dx1 - [dx2.dy1/dy2])
Looks complex, but all those quantities are known at the start, so you can calculate k1 (unless dy2 is 0, in which case special case it, or the whole right hand side is 0, in which case the lines are parallel and there is no intersection).

Then you can use the k1 to calculate k2 from either of the last two equations, and then use k1 and k2 to find the intersection point. Note that if k1 or k2 is < 0 the intersection is 'before' the 'beginning' of the respective line; you may want to count such cases as failures, depending on the problem (and similarly for k > 1).

(NB I didn't check that maths, there may be a mistake, but the principle is sound.)

musefan21-Jun-11 0:08

Pattern Cracking Question

21-Jun-11 0:08

Thanks for the reply. I have solved this already now thou.

I did just want 2D intersection which is why I said the Z axis is not important, I can take a middle ground value for the resulting Z co-ordinate. The part I was really trying to find out (as it turns out) is to determine the line equations from the data I had.

For this I used cosine and sine methods to calculate a "second point" for each "line". From this I could then calculate the slope (m) and y-intersect (b) for my line equations. Then I solve the equations to get the intersect point. simple when you know how Smile | :)

I may or may not be responsible for my own actions

YSLGuru16-Jun-11 12:57

YSLGuru

16-Jun-11 12:57

NOTE: Please let me know if another section/forum on the site is more appropriate for this question.

I'm trying to solve an algorithm puzzle and I was hoping to get some help. Its not for any formal study, just a mind exercise/ puzzle but I've hit a road block:

The goal is to figure out what algorithm or formula can be used to decrypt and encrypted string of characters where you know the characters being encrypted and what their encrypted value is but not how the encrypted value is determined. Obviously this would be like looking for a needle in a haystack except that there are some parameters to this that help (I think) narrow the process down. I can't help but think there's got to be a pattermn or method for figuring out something like this when you know the values of both the unencrypted character and what it encrypts to.

The parameters of the puzzle are:

1) The encrypted characters are limited to the printiable set of characters within the standard 256 character ASCII set of characters (basically what's on a standard US keyboard). I suppose the thing woiuld work with non-visible charactres but I believe the intent is to use any of the keyboard characters a user could use and so that would include numbers, letters and some of the special characters too.

2) the string of characters to encrypt is limited to 12.

3) Each single character is encrypted to a 2 character value (I think it's always a number but I'm not certain ) so that a string of 12 characters will be encrypted to a 24 character long value.

4) Each character is encrypted to the exact same value based on its position in the string of characters to be encrypted.
For example if the text to encrypt is abcdefga1234 then the lower case a is encrypted to the value 57 for position 01 in this string of 12 characters and in the 8th position the lower case a is encrypted to a value of 0A.
No matter what combination of characters are in positions 1 thru 7, the lowercase a will always been encrypted as 0A when it is in the 8th position in the string of characters.

5) Each combination of characters plus position has a unique encrypted value and that value is constant when the position of the character is the same.

I hope the last 2 above make sense; it's hard to convey these in words.

I know that a large lookup table of characters along with their decrypted values and position could be sued to decrypt an encrypted string but unfortunately that’s not the answer to the puzzle. The goal is to decipher what formula or algorithm will decrypt an encrypted character using the above parameters.

If anyone has any links or suggested reading material on how to solve something like this I would most appreciate it.

Moreno Airoldi17-Jun-11 22:52

Moreno Airoldi

17-Jun-11 22:52

Ok let's see if I can come up with something, sounds fun! Smile | :)

The hints we can gather from the given puzzle parameters are:

1) It seems we're talking ASCII characters, one byte per character and a well-known codification.

2) A maximum length of 12 chars, ok.

3) Putting together this with what I see in point 4, it seems the encrypted 2-character data seems to represent a byte value in hex (examples are "57" an "0A", both valid hex byte values).

4) So, the character position in the input string is the second variable to take into account (the first is the character ASCII code itself, see point 1).

5) This confirms what I said for points 1, 3 and 4.

So, we want to find an operation "op" which, applied to the two variables (character code and position) gives us the resulting hex code.

Now let's have a look at the examples we find in point 4.
We know that the ASCII code for "a" is decimal 97, hex 61h, so:

61h op 01h = 57h
61h op 08h = 0Ah

(where 01h and 08h are the character positions in the example, of course)
Let's have it in binary and decimal too, it will be useful:

0110 0001 op 0000 0001 = 0101 0111
0110 0001 op 0000 1000 = 0000 1010

97 op 1 = 87
97 op 8 = 10

Now, one interesting thing we can see is there seems to be a symmetrical relation between the three values:

97 - 10 = 87

This hints at a relation where the only variable is the character position (1 or 8).
So, let't try to find an operation which transforms our equation system in:

97 - 10 = 87
97 - 87 = 10

Looking at the binary representation of 87 and 10, I can seen that if I shift 87 three digits to the right I obtain 10 (0101 0111 shr 3 = 0000 1010).

So, one possibile solution for the puzzle is:

1) Take the charater's ASCII code ("a" = 97)

2) Subtract 10 (97 - 10 = 87)

3) Shift the resulting byte to the right by a number of digits equal to the character's position plus 2, where the first position in the input string is 1, but if the number of digits to shift is 10 or more, subtract 10. (so, 1 + 2 = 3 -> shr 3 ; 8 + 2 = 10 -> 10 - 10 = 0 -> shr 0).

3) Subtract the resulting byte from the character's ASCII code (so, 97 - 10 = 87 ; 97 - 87 = 10).

While this works for the two given examples, it's a very weak explanation. For example, what I say in point 3 can work in other ways too, and still give the correct results.

Maybe someone who is more experienced in cryptography than me will come up with a better solution.

Hope this can somehow help you, it sure was fun for me! Wink | ;)

2+2=5 for very large amounts of 2
(always loved that one hehe!)

dasblinkenlight20-Jun-11 9:36

20-Jun-11 9:36

In general, it is not doable: consider what happens when "a large lookup table" that you describe in your post is filled with randomly generated unique entries. Your target alphabet easily accommodates this, so the result satisfies each of your criteria 1 though 5. Yet the only way to "crack" this "pattern" would be to record the entire lookup table.

musefan21-Jun-11 0:34

21-Jun-11 0:34

Clearly a very basic algorithm if each character is changed individually. I would say it is just a shift cipher of some sort.

First convert the characters to hex

a  b  c  d  e  f  g  a  1  2  3  4  =
61 62 63 64 65 66 67 61 31 32 33 34

now find out what values you need to add to those to get your resulting encryption. As I only have two values to use, here is a sample

   61  62  63  64  65  66  67  61  31  32  33  34
+ -10                         -57
--------------------------------------------------
   57                          0A

fill in the rest and look for a pattern. Could be a repeating key, e.g. -10 +5 +23 - 57

interestingly (and maybe a coincidence) is that the second "a" is a reduction of the previously calculated "a"

So the algorithm could be...

1. start with a byte array of size [256] that contains all -10 values
2. loop each character
3. convert character to hex (iHex)
4. convert iHex to decimal (iDec)
5. encrypted hex (eHex) equals: iHex - bytearray[iDec]
6. set new bytearray value: bytearray[iDec] = eHex (ready for next use)
7. output eHex to result string
8. process next character

...of course that is just one possible to match the results you have given

I may or may not be responsible for my own actions

YSLGuru21-Jun-11 10:41

YSLGuru

21-Jun-11 10:41

First off thanks to both Moreno Airoldi and musefan for providing such detailed and well thoughout replies, this is the kind of help internet forums/boards are all about.

I didn't realize how beenficial it would be to prvide additional sample values esle I would have given more then just the few I did. I am going to check out both your recomendations but it will be a day or so before I can get to them (thats why my own reply to each of you has been so slow coming) and so in the mean time here are more examples that might actually scream a pattern to you 2 who are clearly more versed in patterns.

I tried to provide a sampleing without going over board. The belwo restroicted to a,b & c (in upper & lower case) is for just the first 3 positions and the resulting number of rows is 18. To show all 12 positions for just a few characters is a lot.

Anyway, if anything about the pattern in teh eblow jumps out at you please let me know else I'll let you know what comes of testing your suggestions.

Thanks

Position, unencrypted character, encrytped value

1 a 57
2 a 24
3 a 2A
1 A 77
2 A 04
3 A 0A
1 b 54
2 b 27
3 b 29
1 B 74
2 B 07
3 B 09
1 c 55
2 c 26
3 c 28
1 C 75
2 C 06
3 C 08

BobJanova22-Jun-11 0:33

BobJanova

22-Jun-11 0:33

Well obviously the same character in upper and lower case in the same position differs by (hex) 20. This strongly implies that the ANSI value of the character is being used in a relatively unsophisticated way (upper and lower case are separated by hex 20 in ANSI). The difference can be either way; to me this suggests an xor. However, it is not totally trivial as a->b->c is not just +1 each time:

(ASCII value a 61 b 62 c 63)
Slot 1 a 57 b 54 c 55
Slot 2 a 24 b 27 c 26
Slot 3 a 2A b 29 c 28

All numbers posted here are in the range 06-77. I would guess that it is a 7 bit algorithm (working on 00-7F) and operating with XORing the input character with some function of the input. Let's look at the XOR values for those slots:

Slot 1 a 36 b 36 c 36
Slot 2 a 45 b 45 c 45
Slot 3 a 4B b 4B c 4B

Looks like I'm onto something there. All that remains is to determine what the XOR parameter which is a function of position is. There isn't enough information in 3 slots and the pattern 36->45->4B does not immediately jump out at me as being meaningful. The encrypted value of 'aaaaaaaaaaaa' should provide all the XOR keys and hopefully that is enough to identify how they are calculated.

musefan22-Jun-11 3:34

22-Jun-11 3:34

You beat me to it Frown | :(

Your suggestion of encrypting "aaaaaaaaaaaa" should be enough to solve this you are right.

I think there is no pattern as it is just a random set of chars used to provide the XOR values, which should start with "6EK........."

I think the OP has been lucky that such a simple algorithm was decided on

If my jokes make me laugh, then I have already succeeded with 100% of my target audience

merge k AVL trees complexity

BobJanova22-Jun-11 4:34

BobJanova

22-Jun-11 4:34

Well he said it was a mind exercise/puzzle, so I guess it's supposed to be solvable by a person in a reasonable time.

You may well be right that the XOR key is simply a 12 character pass code/encryption key.

Encrypting 'aaaaaaaaaaa' (or the equivalent with byte zeroes) is often useful for key analysis in simple encryption schemes. I had to modify the first version of my stream encryptor because by throwing a stream of zeroes at it, it would dispense the key. (Real life binary messages, particularly if you're using my socket library as well, often have quite a few zeroes in known places – for example if you request an EXE or DLL download you can rely on 16 or more consecutive zeroes in places in the header; and 4 byte length encoded messages will generally be possible to generate with three zeroes in known positions.)

Hesham Yassin16-Jun-11 0:14

Hesham Yassin

16-Jun-11 0:14

Hello everybody

i am trying to disprove the claim:
the time complexity of merging K AVL trees is O(the sum of their nodes number)

i tried to calculate the complexity of meging K AVL trees but there could be more than one algorithm.

How do i disprove the claim.

Thanks

Alan Balkany16-Jun-11 5:13

Alan Balkany

16-Jun-11 5:13

If you handle every node in every tree, the complexity will be O(the sum of their nodes number).

So one way to disprove this is to come up with a merging algorithm that avoids handling every node. One way to avoid handling every node is to reuse the existing structure of the AVL trees.

This can be done in trivial cases where the ranges of key values for the trees don't overlap. If they DO overlap (which is most likely), then you have a much more difficult problem, because you have to "weave" one tree into another, while maintaining the tree's balanced property.

You may be able to find subtrees whose key values don't overlap, and merge these. Using bigger building blocks like this avoids handling every node, and reduces the time complexity of your algorithm. After merging, you will probably have to do a little rearranging to restore the balanced property.

But it seems very hard, and in most cases, probably impossible.

dasblinkenlight17-Jun-11 10:10

17-Jun-11 10:10

If you diligently handle every node, I think the time will be O(N*Log2 N), where N is the sum of all nodes numbers.

dasblinkenlight17-Jun-11 10:08

17-Jun-11 10:08

To merge K trees in O(N), where N is the sum of node counts, you must never search on insertion: all your insertions must complete in O(1). In other words, on each step you must insert the new root node, and maybe do a rotation or two. However, the new root could come from any of the K trees that you are merging, so the time to search for that node would be O(K) (perhaps you could do O(Log2 K), but regardless of how you do it, K will be a factor to it). That's why I think the best you can do is O(N*Log2 K).