flat assembler
Message board for the users of flat assembler.

 Index > Heap > Ponder This...
Author
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)
_|_|_|_|_|_
|_|_|_|_|
|_|_|
|

_|_   _|
|

_ _ _    |
|
|
_
|_|

_       |_
|_       |

_ _     |
|    |_

_________________
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:
_
|_

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
; reset lattice
lea edx,[lattice]
jnc .loop
...
...accurate to within ±2^-18 with my PRNG.

_________________
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.

_________________