flat assembler
Message board for the users of flat assembler.

Index > Heap > Ponder This...

Author
Thread Post new topic Reply to topic
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
Post 10 Dec 2008, 04:41
View user's profile Send private message Visit poster's website Reply with quote
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 Sad
Post 10 Dec 2008, 10:35
View user's profile Send private message Reply with quote
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.
Post 10 Dec 2008, 16:30
View user's profile Send private message Visit poster's website Reply with quote
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?
Post 10 Dec 2008, 17:48
View user's profile Send private message Visit poster's website Reply with quote
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?

_
Post 10 Dec 2008, 19:30
View user's profile Send private message Visit poster's website Reply with quote
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)
Post 10 Dec 2008, 20:47
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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.
Post 11 Dec 2008, 02:36
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 12 Dec 2008, 21:30
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
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
Post 13 Dec 2008, 08:24
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
Xorpd! wrote:
This seems quite straightforward to me.
Very Happy 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
Post 15 Dec 2008, 08:10
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 15 Dec 2008, 11:03
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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?! Wink
The probabilities MUST sum to one. Smile

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.
Post 15 Dec 2008, 11:43
View user's profile Send private message Visit poster's website Reply with quote
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?! Wink
The probabilities MUST sum to one. Smile
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. Very Happy

_________________
¯\(°_o)/¯ unlicense.org
Post 15 Dec 2008, 17:12
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.