flat assembler
Message board for the users of flat assembler. Index > Heap > Ponder This...
Author
 Thread  bitRAKE Joined: 21 Jul 2003 Posts: 2913 Location: [RSP+8*5] bitRAKE IBM Research has a puzzle each month... The puzzle for December is: Quote:Consider a random walk on the 2-d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i-1, j), (i+1, j), (i, j-1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. These four points will form one of the five tetrominoes (considering mirror images to be the same). For each tetromino find the probability that it will be the one formed in this way. Code:``` _|_ lattice covered _|_|_|_ (start in center) _|_|_|_|_|_ |_|_|_|_| |_|_| | _|_ _| | _ _ _ | | | _ |_| _ |_ |_ | _ _ | | |_ ``` _________________¯\(°_o)/¯ unlicense.org 10 Dec 2008, 04:41
nop

Joined: 01 Sep 2008
Posts: 165
Location: right here left there
nop
i luv puzzles but im not very gud at them is the answer 0.25^4 = .00390625 ? nah maybe not i know its 42 oops thats more than 1 i give up  10 Dec 2008, 10:35  bitRAKE Joined: 21 Jul 2003 Posts: 2913 Location: [RSP+8*5] bitRAKE First I thought of an easy way to calculate the probability of each lattice position in x86, but that doesn't help answer the problem. Next I determined the number of possiblities for each shape and work backward trying to determine the probability of each shape position. I don't have an answer either - just something to think about when I'm in the shower. 10 Dec 2008, 16:30
 Tomasz Grysztar Assembly Artist Joined: 16 Jun 2003 Posts: 7719 Location: Kraków, Poland Tomasz Grysztar bitRAKE wrote: Code:``` _ |_| ``` Is this right? Shouldn't it be Code:``` _ |_ ```instead? 10 Dec 2008, 17:48
 edfed Joined: 20 Feb 2006 Posts: 4237 Location: 2018 edfed in fact, there are only 2dominos Code:``` _|_ lattice covered _|_|_|_ (start in center) _|_|_|_|_|_ |_|_|_|_| |_|_| | _| p = 2/3 _ _ p = 1/3 ``` but there is a possibility, what appens if the point move from A top b and b to a continousously? _ 10 Dec 2008, 19:30
 vid Verbosity in development Joined: 05 Sep 2003 Posts: 7105 Location: Slovakia vid Quote:Consider a random walk on the 2-d integer lattice starting at (0,0). From a lattice point (i,j) the walk moves to one of the four points (i-1, j), (i+1, j), (i, j-1) or (i, j+1) with equal probability. The walk continues until four different points (including (0,0)) have been visited. Doesn't that mean you can walk infitely long without ever getting to solution? (as long as you don't say that random infinite times has to always produce all possible values... that goes more to philosophy IMO) 10 Dec 2008, 20:47
 bitRAKE Joined: 21 Jul 2003 Posts: 2913 Location: [RSP+8*5] bitRAKE Tomasz, your figure better represents the path - I shouldn't have closed the loop to represent the tetrominoes. vid, sure, it can go to infinity without touching four unique points, but the probability of it doing so deminishes faster than all other options. I don't think the probabilities should sum to one. 11 Dec 2008, 02:36
 r22 Joined: 27 Dec 2004 Posts: 805 r22 I would run a simulation using a good PRNG and see where the results converge. But I tend to take a brute-force approach to mathematics where infinity is involved. Using the ideal cases SQUARE: 1 * 1/2 * 1/4 = .125 LINE: 1 * 1/4 * 1/4 = .0625 L: 1 * 1/4 * 1/2 = .125 T: 1 * 1/2 * 1/4 * 1/4 = .03125 The T because it has to always double back has the worst P and LINE will have the 2nd worst. 12 Dec 2008, 21:30
 Xorpd! Joined: 21 Dec 2006 Posts: 161 Xorpd! This seems quite straightforward to me. Code:` ` In the above, 1:4 are possible intermediate configurations (the asterisk marks the current active position) and A:E are the possible final outcomes. Now, P(A|2) = ½P(A|1), P(A|1) = ¼+¼P(A|2) = ¼+(1/8)P(A|1) = 2/7 P(B|2) = ½P(B|1) P(B|1) = ½+¼P(B|2) = ½+(1/8)P(B|1) = 4/7 P(C|2) = ½+½P(C|1) P(C|1) = ¼P(C|2) = (1/8)+(1/8)P(C|1) = 1/7 P(B|4) = ½P(B|3) P(B|3) = ¼+¼P(B|4) = ¼+(1/8)P(B|3) = 2/7 P(C|4) = ½+½P(C|3) P(C|3) = ¼P(C|4) = (1/8)+(1/8)P(C|3) = 1/7 P(D|4) = ½P(D|3) P(D|3) = ¼+¼P(D|4) = ¼+(1/8)P(D|3) = 2/7 P(E|4) = ½P(E|3) P(E|3) = ¼+¼P(E|4) = ¼+(1/8)P(E|3) = 2/7 We know that P(1) = 1/3 P(3) = 2/3 So that P(A) = P(1)P(A|1) = (1/3)(2/7) = 2/21 P(B) = P(1)P(B|1)+P(3)P(B|3) = (1/3)(4/7)+(2/3)(2/7) = 8/21 P(C) = P(1)P(C|1)+P(3)P(C|3) = (1/3)(1/7)+(2/3)(1/7) = 1/7 P(D) = P(3)P(D|3) = (2/3)(2/7) = 4/21 P(E) = P(3)P(E|3) = (2/3)(2/7) = 4/21 13 Dec 2008, 08:24
 bitRAKE Joined: 21 Jul 2003 Posts: 2913 Location: [RSP+8*5] bitRAKE Xorpd! wrote:This seems quite straightforward to me. Well done. Wish I was as comfortable with these types of problems. Here is my brute force method: Code:```lattice \ dd .W, .N, .E, .S .W dd .wW, .wN, .E, .wS .N dd .nW, .nN, .nE, .S .E dd .W, .eN, .eE, .eS .S dd .sW, .N, .sE, .sS .wW dd ._, .L, .wwE, .L .wN dd .Z, .L, .O, .wnS .wS dd .Z, .wsN, .O, .L .nW dd .L, .Z, .nwE, .O .nN dd .L, ._, .L, .nnS .nE dd .neW, .Z, .L, .O .eN dd .O, .L, .Z, .enS .eE dd .eeW, .L, ._, .L .eS dd .O, .esN, .Z, .L .sW dd .L, .O, .swE, .Z .sE dd .seW, .O, .L, .Z .sS dd .L, .ssN, .L, ._ .wwE dd .wW, .T, .eE, .T .wnS dd .T, .wN, .sE, .T .wsN dd .T, .T, .nE, .wS .neW = .wsN .nwE dd .nW, .T, .T, .eS .nnS dd .T, .nN, .T, .sS .eeW = .wwE .esN = .nwE .enS dd .sW, .eN, .T, .T .seW = .wnS .ssN = .nnS .swE = .enS ._ dd 0 .L dd 0 .T dd 0 .O dd 0 .Z dd 0 ... ; next node in random direction EAX mov edx,[edx+eax*4] cmp edx,lattice._ jc .loop add dword [edx],1 ; reset lattice lea edx,[lattice] jnc .loop ... ```...accurate to within ±2^-18 with my PRNG. _________________¯\(°_o)/¯ unlicense.org 15 Dec 2008, 08:10
 vid Verbosity in development Joined: 05 Sep 2003 Posts: 7105 Location: Slovakia vid xorpd: did you take into account probabilities of step sequences which go over and over same points? like moves to form "- - -" shape: right-rigtht-left-right-right right-left-right-right-left-right-right ... etc Shouldn't probability of these be added? And since there is infinite list of variations like these... sigh. I quess the originator of this puzzle didn't take it into account. 15 Dec 2008, 11:03
 Tomasz Grysztar Assembly Artist Joined: 16 Jun 2003 Posts: 7719 Location: Kraków, Poland Tomasz Grysztar bitRAKE wrote:I don't think the probabilities should sum to one. What the hell do you mean?! The probabilities MUST sum to one. Of course, since we are touching the infinity here, we are going to have some event that are possible, but still have 0 probability. It's like choosing random point from a plane. If you divide plane with a line into two parts, then probability of choosing a point in one of them is 1/2. But the probability of choosing precisely a (1,1) point, for example, is 0 (though it's still possible to get such outcome). Look also here. 15 Dec 2008, 11:43
 bitRAKE Joined: 21 Jul 2003 Posts: 2913 Location: [RSP+8*5] bitRAKE Tomasz Grysztar wrote: bitRAKE wrote:I don't think the probabilities should sum to one. What the hell do you mean?! The probabilities MUST sum to one. Sorry, I weave back and forth between reality and mathematics - which is often confusing - even to myself. In reality we never can run infinitely. So, the probability is larger than zero, but very small. That's why I never liked probability - now I wonder if it is possible to have infinite zero probabilities of events that can actually happen. My brute force program always did terminate, though. _________________¯\(°_o)/¯ unlicense.org 15 Dec 2008, 17:12
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First  Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum