- New Logic/Math Puzzles - BrainDen.com

superprismatic · November 2, 2010

I have take a 1000-long bit stream which

satisfies the following 11 relations

(S_i is the i^th bit of the bit stream):

S_i + S_i+11 = S_i+48 (mod 2)

S_i + S_i+22 = S_i+96 (mod 2)

S_i + S_i+44 = S_i+192 (mod 2)

S_i + S_i+30 = S_i+275 (mod 2)

S_i + S_i+244 = S_i+297 (mod 2)

S_i + S_i+214 = S_i+341 (mod 2)

S_i + S_i+88 = S_i+384 (mod 2)

S_i + S_i+60 = S_i+550 (mod 2)

S_i + S_i+488 = S_i+594 (mod 2)

S_i + S_i+428 = S_i+682 (mod 2)

S_i + S_i+176 = S_i+768 (mod 2)

and performed the following modification

on it:

Each bit has either been flipped (with

probability 0.35) or left as is (with

probability 0.65) independently of the

other bits. The resulting stream is:

00010000110111101011001000011000010110000101001001
00011100000010100101001101010110011011101111101110
10100101010010000101111011101011010110001111001000
10010110100111100111110110000101000010010101100100
10010001010110110101010110111001010011011111111001
11101001111101111001000111010100111100101010001111
11100011011101010001110010000011111101011100101010
00110010110110001101001001000000100001110101001010
10000010011110001111111100100110010010000110110111
11110010111110101100000000111011010011001101010001
10100000001011001000100111101010001000001000001001
10111001111110001111101001100001011010010100110000
01110000101001111000111000111011010000110111011110
01100101001100000101111010100000101000111100001000
10000111110100001111000010100100101111001100011110
00101010110010010110100100100101011010100000110101
01011000001011001111010111001110100101000010111110
00001101100101100011100000110010010010111110001010
01010001000000011100000000011110010110101011001100
10011100001101100011100100011101001000010111001101
[/code]

Find the original stream.

araver · November 2, 2010

First, it seems that only 3 equations are non-redundant:
S_i + S_i+11 = S_i+48 (mod 2)
S_i + S_i+30 = S_i+275 (mod 2)
S_i + S_i+214 = S_i+341 (mod 2)

superprismatic · November 2, 2010

First, it seems that only 3 equations are non-redundant:
S_i + S_i+11 = S_i+48 (mod 2)
S_i + S_i+30 = S_i+275 (mod 2)
S_i + S_i+214 = S_i+341 (mod 2)

Yes, but I don't know how that helps solve the problem.

bushindo · November 3, 2010

Nice puzzle

This is what I have


1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0

0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 0

1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1

0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1

0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1

0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1

0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1

0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 0 1

1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1

1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0

1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0

1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1

1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0

0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0

1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1

1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0

1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1

Edited November 3, 2010 by bushindo

superprismatic · November 3, 2010

Nice puzzle
This is what I have

1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0
0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 0
1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1
0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1
0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1
0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1
0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1
0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 0 1
1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0
1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0
1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1
1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0
0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0
1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1
1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0
1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1

Spot on! Please tell us how you approached the problem. I can think of several ways which may work, but I only checked out one of them.

bushindo · November 3, 2010

Spot on! Please tell us how you approached the problem. I can think of several ways which may work, but I only checked out one of them.

Thanks for posting that puzzle. I really enjoy working on it, as I do with all your puzzles. I approach it in the following manner:

I first write a function that takes in a current guess of the solution, which is a 1000-dimensional binary vector S, and a string index i, and computes how many of 22 possible relations are true with respect to i. For instance, for the first two relations, I compute to see if

S[ i ] + S[ i + 11] = S[ i + 48 ]
S[ i - 48 ] + S[ i - 48 + 11] = S

Of course, for all i, not all 22 relations can be computed since some indices may fall outside of the array. I then compute p, which is the proportion of times we get true statements out of the possible relationships for i.

Some calculations will show that for S equal to the noisy stream given in the OP, if S was not flipped, then p, assuming that we get an average of 15 valid relations, is roughly normally distributed with mean .545 and standard error .033. If S was flipped, then p is normally distributed with mean .456 and standard error .033.

At this point, I let S be equal to the original stream, iterate through S and flip the bits with low p using the following pseudo-code
S = original stream

loop iter from 1 to 10

	loop i from 1 to 1000

		compute p[i] given S

		if p[i] < .456

			flip S[i]

		end

	end

end
This code converges in 8 iterations. It can probably converge faster if we put weights on the relationships in computing p. I am interested in your method. How did you approach this problem?

Edited November 3, 2010 by bushindo

superprismatic · November 3, 2010

Thanks for posting that puzzle. I really enjoy working on it, as I do with all your puzzles. I approach it in the following manner:
I first write a function that takes in a current guess of the solution, which is a 1000-dimensional binary vector S, and a string index i, and computes how many of 22 possible relations are true with respect to i. For instance, for the first two relations, I compute to see if

S[ i ] + S[ i + 11] = S[ i + 48 ]
S[ i - 48 ] + S[ i - 48 + 11] = S

Of course, for all i, not all 22 relations can be computed since some indices may fall outside of the array. I then compute p, which is the proportion of times we get true statements out of the possible relationships for i.

Some calculations will show that for S equal to the noisy stream given in the OP, if S was not flipped, then p, assuming that we get an average of 15 valid relations, is roughly normally distributed with mean .545 and standard error .033. If S was flipped, then p is normally distributed with mean .456 and standard error .033.

At this point, I let S be equal to the original stream, iterate through S and flip the bits with low p using the following pseudo-code

S = original stream
loop iter from 1 to 10
loop i from 1 to 1000
compute p[i] given S
if p[i] < .456
flip S[i]
end
end
end
This code converges in 8 iterations. It can probably converge faster if we put weights on the relationships in computing p. I am interested in your method. How did you approach this problem?

OK, here goes:

Looking at bit i and the first of the 11 relationships, we can make
three estimates for bit i (except when indices fall outside [1,1000]):

S[ i ] + S[ i + 11] = S[ i + 48] which is S[ i ] = S[ i + 11 ] + S[ i + 48 ]
S[ i-11] + S[ i ] = S[ i + 48 - 11] which is S[ i ] = S[ i - 11 ] + S[ i + 37 ]
S[ i - 48 ] + S[ i - 48 + 11] = S which is S[ i ] = S[ i - 48 ] + S[ i - 37 ]

So, from these equations and knowing that the garble probability, we can
get three estimates for what bit i was in the original stream.
Together with the other 10 relationships, we can get at most 33
estimates for that bit. I combined these estimates (which were
in the form of the probability that the bit was originally a 1)
by multiplying their respective odds. If the resulting odds for being
a 1 is greater than 1, I estimate that the original bit was a 1,
otherwise, I estimate it as a 0.

I know that all the probabilities are not independent of one another,
but who cares? It's my experience that this slop is not very important.

The number of the original equations which are satisfies went up.
So, I re-iterate this process until all the original equations are
satisfied. It took 8 iterations (like yours -- coincidence?).
The number of correct bits were originally 651. They grew like
this: 704, 766, 810, 855, 909, 966, 998, 1000. I should have just
counted hits (like you did) instead of doing that probability stuff.
It would have been simpler to code.

Other possible approaches:

My favorite other idea (which I have not tried) is a discreet hill-climb.
We'll try to minimize the number of times those 11 relations are not
satisfied for all possible placements of the relations in the stream.
So, just try flipping small sets of bits until our object function
decreases. Iterate on this. With a little ingenuity this could be
turned into a Genetic Algorithm.

araver · November 3, 2010

Yes, but I don't know how that helps solve the problem.

It does not actually. I did not know at the time

was to estimate the number of possibilities for your input sequence hopefully get something friendlier than 2^48 I saw from the first equation.
Actually, only the first and fourth are independent, but this does not help much. Only reduces to 2^46 possibilities.
In fact, the more equations may be the better, see aproach below.

1101010011000001011100000101110001111101010100111

1011111010000111001001110110110111000111010100111

0000111101111000100100101010111010110110110111001

1001011111011011110011100011000010100001000001110

1001001101010100100101100111000100110110100101000

0110111111001110001111111000101100101110010101100

0011110001100100110011011111001100111101010011110

0011010000010110101010000011001010001011001111101

0000001010101110011110001101011011111110011010000

1110001011010001100111100100101101111011110001100

1101110001000111100010110010101010010001011011101

1100000000111101101111110100001111001100110111000

0101101110001111010000100100101001011011011001000

0100001100111010001000010010001011110100110100011

0010010001100110011011010000100011110000100000000

0010111000011100010101010001100111100000011100001

1001100101101001001101000011010011001100001010101

1010000110010001001001001010101100110101010110010

0101000101101000111110100000001111111000001110010

0010110101110001110010111000010001100001000110011

01000110010110111101

Iterate through string, compute for each bit: how many relations are bad / nr of relations in = degree of "badness". Get an overall maximum of the degree of badness. Flip all bits which are near to the maximum badness degree (fixed distance from the degree). Rinse, clean and repeat. Tried idea first with only a few equations and a lot of rounds. Always got myself stuck in local optimum that does not converge to a global optimum (i.e. less than say 350+10 flips. More equations = better the conversion in terms of rounds. Played a little with the no of rounds and the fixed distance to the degree, and it worked. My code's not pretty though, lazy means a lot of copy-paste and some excel pre-processed code
It gets with 529 flips to the solution, in 12 rounds. Only 349 are necessary flips, the other being flipped back as it approached the solution. Could not find another solution nowhere near this optimum.

		

		 int[] a;

		 int counter;

		 int maxcounter = 350;

		 int[] b;

		 int[] c;

		 double[] d;

		a = new int[1000];

		a[0]=0;a[1]=0;a[2]=0;a[3]=1;a[4]=0;a[5]=0;a[6]=0;a[7]=0;a[8]=1;a[9]=1;a[10]=0;a[11]=1;a[12]=1;a[13]=1;a[14]=1;a[15]=0;a[16]=1;a[17]=0;a[18]=1;a[19]=1;a[20]=0;a[21]=0;a[22]=1;a[23]=0;a[24]=0;a[25]=0;a[26]=0;a[27]=1;a[28]=1;a[29]=0;a[30]=0;a[31]=0;a[32]=0;a[33]=1;a[34]=0;a[35]=1;a[36]=1;a[37]=0;a[38]=0;a[39]=0;a[40]=0;a[41]=1;a[42]=0;a[43]=1;a[44]=0;a[45]=0;a[46]=1;a[47]=0;a[48]=0;a[49]=1;a[50]=0;a[51]=0;a[52]=0;a[53]=1;a[54]=1;a[55]=1;a[56]=0;a[57]=0;a[58]=0;a[59]=0;a[60]=0;a[61]=0;a[62]=1;a[63]=0;a[64]=1;a[65]=0;a[66]=0;a[67]=1;a[68]=0;a[69]=1;a[70]=0;a[71]=0;a[72]=1;a[73]=1;a[74]=0;a[75]=1;a[76]=0;a[77]=1;a[78]=0;a[79]=1;a[80]=1;a[81]=0;a[82]=0;a[83]=1;a[84]=1;a[85]=0;a[86]=1;a[87]=1;a[88]=1;a[89]=0;a[90]=1;a[91]=1;a[92]=1;a[93]=1;a[94]=1;a[95]=0;a[96]=1;a[97]=1;a[98]=1;a[99]=0;a[100]=1;a[101]=0;a[102]=1;a[103]=0;a[104]=0;a[105]=1;a[106]=0;a[107]=1;a[108]=0;a[109]=1;a[110]=0;a[111]=0;a[112]=1;a[113]=0;a[114]=0;a[115]=0;a[116]=0;a[117]=1;a[118]=0;a[119]=1;a[120]=1;a[121]=1;a[122]=1;a[123]=0;a[124]=1;a[125]=1;a[126]=1;a[127]=0;a[128]=1;a[129]=0;a[130]=1;a[131]=1;a[132]=0;a[133]=1;a[134]=0;a[135]=1;a[136]=1;a[137]=0;a[138]=0;a[139]=0;a[140]=1;a[141]=1;a[142]=1;a[143]=1;a[144]=0;a[145]=0;a[146]=1;a[147]=0;a[148]=0;a[149]=0;a[150]=1;a[151]=0;a[152]=0;a[153]=1;a[154]=0;a[155]=1;a[156]=1;a[157]=0;a[158]=1;a[159]=0;a[160]=0;a[161]=1;a[162]=1;a[163]=1;a[164]=1;a[165]=0;a[166]=0;a[167]=1;a[168]=1;a[169]=1;a[170]=1;a[171]=1;a[172]=0;a[173]=1;a[174]=1;a[175]=0;a[176]=0;a[177]=0;a[178]=0;a[179]=1;a[180]=0;a[181]=1;a[182]=0;a[183]=0;a[184]=0;a[185]=0;a[186]=1;a[187]=0;a[188]=0;a[189]=1;a[190]=0;a[191]=1;a[192]=0;a[193]=1;a[194]=1;a[195]=0;a[196]=0;a[197]=1;a[198]=0;a[199]=0;a[200]=1;a[201]=0;a[202]=0;a[203]=1;a[204]=0;a[205]=0;a[206]=0;a[207]=1;a[208]=0;a[209]=1;a[210]=0;a[211]=1;a[212]=1;a[213]=0;a[214]=1;a[215]=1;a[216]=0;a[217]=1;a[218]=0;a[219]=1;a[220]=0;a[221]=1;a[222]=0;a[223]=1;a[224]=1;a[225]=0;a[226]=1;a[227]=1;a[228]=1;a[229]=0;a[230]=0;a[231]=1;a[232]=0;a[233]=1;a[234]=0;a[235]=0;a[236]=1;a[237]=1;a[238]=0;a[239]=1;a[240]=1;a[241]=1;a[242]=1;a[243]=1;a[244]=1;a[245]=1;a[246]=1;a[247]=0;a[248]=0;a[249]=1;a[250]=1;a[251]=1;a[252]=1;a[253]=0;a[254]=1;a[255]=0;a[256]=0;a[257]=1;a[258]=1;a[259]=1;a[260]=1;a[261]=1;a[262]=0;a[263]=1;a[264]=1;a[265]=1;a[266]=1;a[267]=0;a[268]=0;a[269]=1;a[270]=0;a[271]=0;a[272]=0;a[273]=1;a[274]=1;a[275]=1;a[276]=0;a[277]=1;a[278]=0;a[279]=1;a[280]=0;a[281]=0;a[282]=1;a[283]=1;a[284]=1;a[285]=1;a[286]=0;a[287]=0;a[288]=1;a[289]=0;a[290]=1;a[291]=0;a[292]=1;a[293]=0;a[294]=0;a[295]=0;a[296]=1;a[297]=1;a[298]=1;a[299]=1;a[300]=1;a[301]=1;a[302]=1;a[303]=0;a[304]=0;a[305]=0;a[306]=1;a[307]=1;a[308]=0;a[309]=1;a[310]=1;a[311]=1;a[312]=0;a[313]=1;a[314]=0;a[315]=1;a[316]=0;a[317]=0;a[318]=0;a[319]=1;a[320]=1;a[321]=1;a[322]=0;a[323]=0;a[324]=1;a[325]=0;a[326]=0;a[327]=0;a[328]=0;a[329]=0;a[330]=1;a[331]=1;a[332]=1;a[333]=1;a[334]=1;a[335]=1;a[336]=0;a[337]=1;a[338]=0;a[339]=1;a[340]=1;a[341]=1;a[342]=0;a[343]=0;a[344]=1;a[345]=0;a[346]=1;a[347]=0;a[348]=1;a[349]=0;a[350]=0;a[351]=0;a[352]=1;a[353]=1;a[354]=0;a[355]=0;a[356]=1;a[357]=0;a[358]=1;a[359]=1;a[360]=0;a[361]=1;a[362]=1;a[363]=0;a[364]=0;a[365]=0;a[366]=1;a[367]=1;a[368]=0;a[369]=1;a[370]=0;a[371]=0;a[372]=1;a[373]=0;a[374]=0;a[375]=1;a[376]=0;a[377]=0;a[378]=0;a[379]=0;a[380]=0;a[381]=0;a[382]=1;a[383]=0;a[384]=0;a[385]=0;a[386]=0;a[387]=1;a[388]=1;a[389]=1;a[390]=0;a[391]=1;a[392]=0;a[393]=1;a[394]=0;a[395]=0;a[396]=1;a[397]=0;a[398]=1;a[399]=0;a[400]=1;a[401]=0;a[402]=0;a[403]=0;a[404]=0;a[405]=0;a[406]=1;a[407]=0;a[408]=0;a[409]=1;a[410]=1;a[411]=1;a[412]=1;a[413]=0;a[414]=0;a[415]=0;a[416]=1;a[417]=1;a[418]=1;a[419]=1;a[420]=1;a[421]=1;a[422]=1;a[423]=1;a[424]=0;a[425]=0;a[426]=1;a[427]=0;a[428]=0;a[429]=1;a[430]=1;a[431]=0;a[432]=0;a[433]=1;a[434]=0;a[435]=0;a[436]=1;a[437]=0;a[438]=0;a[439]=0;a[440]=0;a[441]=1;a[442]=1;a[443]=0;a[444]=1;a[445]=1;a[446]=0;a[447]=1;a[448]=1;a[449]=1;a[450]=1;a[451]=1;a[452]=1;a[453]=1;a[454]=0;a[455]=0;a[456]=1;a[457]=0;a[458]=1;a[459]=1;a[460]=1;a[461]=1;a[462]=1;a[463]=0;a[464]=1;a[465]=0;a[466]=1;a[467]=1;a[468]=0;a[469]=0;a[470]=0;a[471]=0;a[472]=0;a[473]=0;a[474]=0;a[475]=0;a[476]=1;a[477]=1;a[478]=1;a[479]=0;a[480]=1;a[481]=1;a[482]=0;a[483]=1;a[484]=0;a[485]=0;a[486]=1;a[487]=1;a[488]=0;a[489]=0;a[490]=1;a[491]=1;a[492]=0;a[493]=1;a[494]=0;a[495]=1;a[496]=0;a[497]=0;a[498]=0;a[499]=1;a[500]=1;a[501]=0;a[502]=1;a[503]=0;a[504]=0;a[505]=0;a[506]=0;a[507]=0;a[508]=0;a[509]=0;a[510]=1;a[511]=0;a[512]=1;a[513]=1;a[514]=0;a[515]=0;a[516]=1;a[517]=0;a[518]=0;a[519]=0;a[520]=1;a[521]=0;a[522]=0;a[523]=1;a[524]=1;a[525]=1;a[526]=1;a[527]=0;a[528]=1;a[529]=0;a[530]=1;a[531]=0;a[532]=0;a[533]=0;a[534]=1;a[535]=0;a[536]=0;a[537]=0;a[538]=0;a[539]=0;a[540]=1;a[541]=0;a[542]=0;a[543]=0;a[544]=0;a[545]=0;a[546]=1;a[547]=0;a[548]=0;a[549]=1;a[550]=1;a[551]=0;a[552]=1;a[553]=1;a[554]=1;a[555]=0;a[556]=0;a[557]=1;a[558]=1;a[559]=1;a[560]=1;a[561]=1;a[562]=1;a[563]=0;a[564]=0;a[565]=0;a[566]=1;a[567]=1;a[568]=1;a[569]=1;a[570]=1;a[571]=0;a[572]=1;a[573]=0;a[574]=0;a[575]=1;a[576]=1;a[577]=0;a[578]=0;a[579]=0;a[580]=0;a[581]=1;a[582]=0;a[583]=1;a[584]=1;a[585]=0;a[586]=1;a[587]=0;a[588]=0;a[589]=1;a[590]=0;a[591]=1;a[592]=0;a[593]=0;a[594]=1;a[595]=1;a[596]=0;a[597]=0;a[598]=0;a[599]=0;a[600]=0;a[601]=1;a[602]=1;a[603]=1;a[604]=0;a[605]=0;a[606]=0;a[607]=0;a[608]=1;a[609]=0;a[610]=1;a[611]=0;a[612]=0;a[613]=1;a[614]=1;a[615]=1;a[616]=1;a[617]=0;a[618]=0;a[619]=0;a[620]=1;a[621]=1;a[622]=1;a[623]=0;a[624]=0;a[625]=0;a[626]=1;a[627]=1;a[628]=1;a[629]=0;a[630]=1;a[631]=1;a[632]=0;a[633]=1;a[634]=0;a[635]=0;a[636]=0;a[637]=0;a[638]=1;a[639]=1;a[640]=0;a[641]=1;a[642]=1;a[643]=1;a[644]=0;a[645]=1;a[646]=1;a[647]=1;a[648]=1;a[649]=0;a[650]=0;a[651]=1;a[652]=1;a[653]=0;a[654]=0;a[655]=1;a[656]=0;a[657]=1;a[658]=0;a[659]=0;a[660]=1;a[661]=1;a[662]=0;a[663]=0;a[664]=0;a[665]=0;a[666]=0;a[667]=1;a[668]=0;a[669]=1;a[670]=1;a[671]=1;a[672]=1;a[673]=0;a[674]=1;a[675]=0;a[676]=1;a[677]=0;a[678]=0;a[679]=0;a[680]=0;a[681]=0;a[682]=1;a[683]=0;a[684]=1;a[685]=0;a[686]=0;a[687]=0;a[688]=1;a[689]=1;a[690]=1;a[691]=1;a[692]=0;a[693]=0;a[694]=0;a[695]=0;a[696]=1;a[697]=0;a[698]=0;a[699]=0;a[700]=1;a[701]=0;a[702]=0;a[703]=0;a[704]=0;a[705]=1;a[706]=1;a[707]=1;a[708]=1;a[709]=1;a[710]=0;a[711]=1;a[712]=0;a[713]=0;a[714]=0;a[715]=0;a[716]=1;a[717]=1;a[718]=1;a[719]=1;a[720]=0;a[721]=0;a[722]=0;a[723]=0;a[724]=1;a[725]=0;a[726]=1;a[727]=0;a[728]=0;a[729]=1;a[730]=0;a[731]=0;a[732]=1;a[733]=0;a[734]=1;a[735]=1;a[736]=1;a[737]=1;a[738]=0;a[739]=0;a[740]=1;a[741]=1;a[742]=0;a[743]=0;a[744]=0;a[745]=1;a[746]=1;a[747]=1;a[748]=1;a[749]=0;a[750]=0;a[751]=0;a[752]=1;a[753]=0;a[754]=1;a[755]=0;a[756]=1;a[757]=0;a[758]=1;a[759]=1;a[760]=0;a[761]=0;a[762]=1;a[763]=0;a[764]=0;a[765]=1;a[766]=0;a[767]=1;a[768]=1;a[769]=0;a[770]=1;a[771]=0;a[772]=0;a[773]=1;a[774]=0;a[775]=0;a[776]=1;a[777]=0;a[778]=0;a[779]=1;a[780]=0;a[781]=1;a[782]=0;a[783]=1;a[784]=1;a[785]=0;a[786]=1;a[787]=0;a[788]=1;a[789]=0;a[790]=0;a[791]=0;a[792]=0;a[793]=0;a[794]=1;a[795]=1;a[796]=0;a[797]=1;a[798]=0;a[799]=1;a[800]=0;a[801]=1;a[802]=0;a[803]=1;a[804]=1;a[805]=0;a[806]=0;a[807]=0;a[808]=0;a[809]=0;a[810]=1;a[811]=0;a[812]=1;a[813]=1;a[814]=0;a[815]=0;a[816]=1;a[817]=1;a[818]=1;a[819]=1;a[820]=0;a[821]=1;a[822]=0;a[823]=1;a[824]=1;a[825]=1;a[826]=0;a[827]=0;a[828]=1;a[829]=1;a[830]=1;a[831]=0;a[832]=1;a[833]=0;a[834]=0;a[835]=1;a[836]=0;a[837]=1;a[838]=0;a[839]=0;a[840]=0;a[841]=0;a[842]=1;a[843]=0;a[844]=1;a[845]=1;a[846]=1;a[847]=1;a[848]=1;a[849]=0;a[850]=0;a[851]=0;a[852]=0;a[853]=0;a[854]=1;a[855]=1;a[856]=0;a[857]=1;a[858]=1;a[859]=0;a[860]=0;a[861]=1;a[862]=0;a[863]=1;a[864]=1;a[865]=0;a[866]=0;a[867]=0;a[868]=1;a[869]=1;a[870]=1;a[871]=0;a[872]=0;a[873]=0;a[874]=0;a[875]=0;a[876]=1;a[877]=1;a[878]=0;a[879]=0;a[880]=1;a[881]=0;a[882]=0;a[883]=1;a[884]=0;a[885]=0;a[886]=1;a[887]=0;a[888]=1;a[889]=1;a[890]=1;a[891]=1;a[892]=1;a[893]=0;a[894]=0;a[895]=0;a[896]=1;a[897]=0;a[898]=1;a[899]=0;a[900]=0;a[901]=1;a[902]=0;a[903]=1;a[904]=0;a[905]=0;a[906]=0;a[907]=1;a[908]=0;a[909]=0;a[910]=0;a[911]=0;a[912]=0;a[913]=0;a[914]=0;a[915]=1;a[916]=1;a[917]=1;a[918]=0;a[919]=0;a[920]=0;a[921]=0;a[922]=0;a[923]=0;a[924]=0;a[925]=0;a[926]=0;a[927]=1;a[928]=1;a[929]=1;a[930]=1;a[931]=0;a[932]=0;a[933]=1;a[934]=0;a[935]=1;a[936]=1;a[937]=0;a[938]=1;a[939]=0;a[940]=1;a[941]=0;a[942]=1;a[943]=1;a[944]=0;a[945]=0;a[946]=1;a[947]=1;a[948]=0;a[949]=0;a[950]=1;a[951]=0;a[952]=0;a[953]=1;a[954]=1;a[955]=1;a[956]=0;a[957]=0;a[958]=0;a[959]=0;a[960]=1;a[961]=1;a[962]=0;a[963]=1;a[964]=1;a[965]=0;a[966]=0;a[967]=0;a[968]=1;a[969]=1;a[970]=1;a[971]=0;a[972]=0;a[973]=1;a[974]=0;a[975]=0;a[976]=0;a[977]=1;a[978]=1;a[979]=1;a[980]=0;a[981]=1;a[982]=0;a[983]=0;a[984]=1;a[985]=0;a[986]=0;a[987]=0;a[988]=0;a[989]=1;a[990]=0;a[991]=1;a[992]=1;a[993]=1;a[994]=0;a[995]=0;a[996]=1;a[997]=1;a[998]=0;a[999]=1;

b=new int[1000];

		for(int i=0;i<1000;i++) b[i]=a[i];

		c=new int[1000];

		d=new double[1000];


		int i,j,k,l;


		int flip=0;

		for (j=0;j<12;j++)

		{

			double max=.0;

			System.out.println("Round "+j);

			int need=0;

			for (i=0;i<1000;i++)

			{

				int nr=0;

				c[i]=0;

				if (48+i<1000&&(a[48+i]+a[i]+a[i+11])%2==1)						{c[i]++;}

				if (48<i&&(a[48+i-48]+a[i-48]+a[i+11-48])%2==1)					{c[i]++;}

				if (11<i&&48+i-11<1000&&(a[48+i-11]+a[i-11]+a[i+11-11])%2==1)	{c[i]++;}


				if (275+i<1000&&(a[30+i]+a[i]+a[i+275])%2==1)					{c[i]++;}		

				if (275<i&&(a[30+i-275]+a[i-275]+a[i+275-275])%2==1)			{c[i]++;}

				if (i>30&&275-30+i<1000&&(a[30+i-30]+a[i-30]+a[i+275-30])%2==1)	{c[i]++;}

				//Si + Si+22 = Si+96 (mod 2)	

				if (96+i<1000&&(a[22+i]+a[i]+a[i+96])%2==1)					{c[i]++;}		

				if (96<i&&(a[22+i-96]+a[i-96]+a[i+96-96])%2==1)			{c[i]++;}

				if (i>22&&96-22+i<1000&&(a[22+i-22]+a[i-22]+a[i+96-22])%2==1)	{c[i]++;}



//				Si + Si+44 = Si+192 (mod 2)	

				if (192+i<1000&&(a[44+i]+a[i]+a[i+192])%2==1)					{c[i]++;}		

				if (192<i&&(a[44+i-192]+a[i-192]+a[i+192-192])%2==1)			{c[i]++;}

				if (i>44&&192-44+i<1000&&(a[44+i-44]+a[i-44]+a[i+192-44])%2==1)	{c[i]++;}


//				Si + Si+244 = Si+297 (mod 2)	

				if (297+i<1000&&(a[244+i]+a[i]+a[i+297])%2==1)					{c[i]++;}		

				if (297<i&&(a[244+i-297]+a[i-297]+a[i+297-297])%2==1)			{c[i]++;}

				if (i>244&&297-244+i<1000&&(a[244+i-244]+a[i-244]+a[i+297-244])%2==1)	{c[i]++;}


//				Si + Si+214 = Si+341 (mod 2)	

				if (341+i<1000&&(a[341+i]+a[i]+a[i+214])%2==1)						{c[i]++;}

				if (341<i&&(a[341+i-341]+a[i-341]+a[i+214-341])%2==1)					{c[i]++;}

				if (214<i&&341+i-214<1000&&(a[341+i-214]+a[i-214]+a[i+214-214])%2==1)	{c[i]++;}


//				Si + Si+88 = Si+384 (mod 2)	

				if (384+i<1000&&(a[384+i]+a[i]+a[i+88])%2==1)						{c[i]++;}

				if (384<i&&(a[384+i-384]+a[i-384]+a[i+88-384])%2==1)					{c[i]++;}

				if (88<i&&384+i-88<1000&&(a[384+i-88]+a[i-88]+a[i+88-88])%2==1)	{c[i]++;}


//				Si + Si+60 = Si+550 (mod 2)	

				if (550+i<1000&&(a[550+i]+a[i]+a[i+60])%2==1)						{c[i]++;}

				if (550<i&&(a[550+i-550]+a[i-550]+a[i+60-550])%2==1)					{c[i]++;}

				if (60<i&&550+i-60<1000&&(a[550+i-60]+a[i-60]+a[i+60-60])%2==1)	{c[i]++;}


//				Si + Si+488 = Si+594 (mod 2)	

				if (594+i<1000&&(a[594+i]+a[i]+a[i+488])%2==1)						{c[i]++;}

				if (594<i&&(a[594+i-594]+a[i-594]+a[i+488-594])%2==1)					{c[i]++;}

				if (488<i&&594+i-488<1000&&(a[594+i-488]+a[i-488]+a[i+488-488])%2==1)	{c[i]++;}


//				Si + Si+428 = Si+682 (mod 2)	

				if (682+i<1000&&(a[682+i]+a[i]+a[i+428])%2==1)						{c[i]++;}

				if (682<i&&(a[682+i-682]+a[i-682]+a[i+428-682])%2==1)					{c[i]++;}

				if (428<i&&682+i-428<1000&&(a[682+i-428]+a[i-428]+a[i+428-428])%2==1)	{c[i]++;}


//				Si + Si+176 = Si+768 (mod 2)	

				if (768+i<1000&&(a[768+i]+a[i]+a[i+176])%2==1)						{c[i]++;}

				if (768<i&&(a[768+i-768]+a[i-768]+a[i+176-768])%2==1)					{c[i]++;}

				if (176<i&&768+i-176<1000&&(a[768+i-176]+a[i-176]+a[i+176-176])%2==1)	{c[i]++;}



					if (48+i<1000)						{nr++;}

					if (48<i)					{nr++;}

					if (11<i)	{nr++;}


					if (275+i<1000)					{nr++;}		

					if (275<i)			{nr++;}

					if (i>30&&275-30+i<1000)	{nr++;}

					//Si + Si+22 = Si+96 (mod 2)	

					if (96+i<1000)					{nr++;}		

					if (96<i)			{nr++;}

					if (i>22&&96-22+i<1000)	{nr++;}



//					Si + Si+44 = Si+192 (mod 2)	

					if (192+i<1000)					{nr++;}		

					if (192<i)			{nr++;}

					if (i>44&&192-44+i<1000)	{nr++;}


//					Si + Si+244 = Si+297 (mod 2)	

					if (297+i<1000)					{nr++;}		

					if (297<i)			{nr++;}

					if (i>244&&297-244+i<1000)	{nr++;}


//					Si + Si+214 = Si+341 (mod 2)	

					if (341+i<1000)						{nr++;}

					if (341<i)					{nr++;}

					if (214<i&&341+i-214<1000)	{nr++;}


//					Si + Si+88 = Si+384 (mod 2)	

					if (384+i<1000)						{nr++;}

					if (384<i)					{nr++;}

					if (88<i&&384+i-88<1000)	{nr++;}


//					Si + Si+60 = Si+550 (mod 2)	

					if (550+i<1000)						{nr++;}

					if (550<i)					{nr++;}

					if (60<i&&550+i-60<1000)	{nr++;}


//					Si + Si+488 = Si+594 (mod 2)	

					if (594+i<1000)						{nr++;}

					if (594<i)					{nr++;}

					if (488<i&&594+i-488<1000)	{nr++;}


//					Si + Si+428 = Si+682 (mod 2)	

					if (682+i<1000)						{nr++;}

					if (682<i)					{nr++;}

					if (428<i&&682+i-428<1000)	{nr++;}


//					Si + Si+176 = Si+768 (mod 2)	

					if (768+i<1000)						{nr++;}

					if (768<i)					{nr++;}

					if (176<i&&768+i-176<1000)	{nr++;}


				d[i]=(double)nr;

				if(nr>0 && c[i]/d[i]>max) max=c[i]/d[i];

				//System.out.println(c[i]/d[i]+"\t");

				need+=c[i];

			}

			System.out.println("Need "+need);

			for (i=0;i<1000;i++)

			{

				if(d[i]>0&&Math.abs(c[i]/d[i]-max)<0.2) 

				{

					flip++;

					a[i]=1-a[i];

				}

			}

			System.out.println("Flips "+flip);

		}

		int count=0;

		for(i=0;i<1000;i++) 

			if(b[i]!=a[i]) count++;

		System.out.println("Differences "+count);

		for(i=0;i<1000;i++)

			System.out.print(a[i]);

	}

araver · November 3, 2010

Some calculations will show that for S equal to the noisy stream given in the OP, if S was not flipped, then p, assuming that we get an average of 15 valid relations, is roughly normally distributed with mean .545 and standard error .033. If S was flipped, then p is normally distributed with mean .456 and standard error .033.

This code converges in 8 iterations. It can probably converge faster if we put weights on the relationships in computing p.

OK, here goes:
The number of the original equations which are satisfies went up.
So, I re-iterate this process until all the original equations are
satisfied. It took 8 iterations (like yours -- coincidence?).
The number of correct bits were originally 651. They grew like
this: 704, 766, 810, 855, 909, 966, 998, 1000. I should have just
counted hits (like you did) instead of doing that probability stuff.
It would have been simpler to code.

Both algorithms appear to arrive to a solution much easier than my code, converging without much trouble...

Seems that my greedy thinking was just lucky then. It initially converged in about 1000 rounds and since it flipped bits all at once without any independence check, I actually broke many relations on the way to a solution (as I watched the global "Need" variable).

superprismatic · November 3, 2010

Both algorithms appear to arrive to a solution much easier than my code, converging without much trouble...

Seems that my greedy thinking was just lucky then. It initially converged in about 1000 rounds and since it flipped bits all at once without any independence check, I actually broke many relations on the way to a solution (as I watched the global "Need" variable).

My response to bushindo included an idea similar to yours. I never tried it, though. I hope both of you enjoyed this problem. I really like to solve problems with algorithms that I design myself. I'll bet there are several people on Brainden like me as well. I'll try to put some more of them up here.

Sign In

Question

superprismatic

Link to comment

Share on other sites

9 answers to this question

Recommended Posts

araver

Link to comment

Share on other sites

superprismatic

Link to comment

Share on other sites

bushindo

Link to comment

Share on other sites

superprismatic

Link to comment

Share on other sites

bushindo

Link to comment

Share on other sites

superprismatic

Link to comment

Share on other sites

araver

Link to comment

Share on other sites

araver

Link to comment

Share on other sites

superprismatic

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members

Browse

Activity