Binary Transmission Glitch

Computer Science Level 4

A binary message, 24 digits long, is being transmitted via a satellite from the USA to Australia. This message is being sent 1 digit at a time. However, after a some digits have passed, a glitch causes all the digits after it has activated to revert to their counterpart (1 becomes 0 and 0 becomes 1) whilst being sent. This is the message received in Australia:

111010101000111001100111

If there were originally 12 1's and 12 0's in the transmission (there are 14 1's and 10 0's now), in how many places could the glitch have started to affect the transmission?


The answer is 10.

Sharky Kesa by Sharky Kesa , 19, United Kingdom

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Brock Brown
Mar 23, 2016

Python 3: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
s = '111010101000111001100111'
message = [bool(int(c)) for c in s]
print(message)
def glitch(bit_id):
    glitched = message[:]
    for place in range(bit_id, len(message)):
        glitched[place] = not glitched[place]
    return glitched[:]
def possible(bit_id):
    return sum(glitch(bit_id)) == 12
count = 0
for bit_id in range(len(message)):
    if possible(bit_id):
        count += 1
        print('Malfunction possible at bit', bit_id + 1)
        print(''.join([str(int(i)) for i in glitch(bit_id)]))
print("Answer:", count)

⟹ \implies 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
 
Malfunction possible at bit 3
110101010111000110011000
Malfunction possible at bit 5
111001010111000110011000
Malfunction possible at bit 7
111010010111000110011000
Malfunction possible at bit 9
111010100111000110011000
Malfunction possible at bit 11
111010101011000110011000
Malfunction possible at bit 15
111010101000110110011000
Malfunction possible at bit 17
111010101000111010011000
Malfunction possible at bit 19
111010101000111001011000
Malfunction possible at bit 21
111010101000111001101000
Malfunction possible at bit 23
111010101000111001100100
Answer: 10

⟹ 10 \implies \boxed{10}

8 Helpful 0 Interesting 0 Brilliant 0 Confused

A comparatively shorter version: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
def flip(a):
    return ''.join([str(int(not int(a[i]))) for i in range(len(a))])
n='111010101000111001100111'
count=0
for i in range(len(n)+1):
    k=n[:i]+flip(n[i:])
    if k.count('0')==12:
        print('Malfunction possible since bit',i+1,'with original message',k)
        count+=1
print('\nAnswer =',count)

Prasun Biswas - 5 years, 2 months ago
展豪 張
Mar 23, 2016

There are 14 1's and 10 0's now, but originally it's 12 each.
So we have to change 2 1's, or 3 1's 1 0's,......
Group the bits up:
1110101010001110011001[11] <- group these first, so we can change them into 00
[11][10][10][10][10][0011][10][01][10][01][11] <- except for the first and the last groups, all the others contain equal number of 0's and 1's. This means that any space between consecutive ']' and '[' can be a possible place.
11*10*10*10*10*0011*10*01*10*01*11 <- counting the stars (which mark the possible places), there are 10 of them.
Answer is 10.



4 Helpful 0 Interesting 0 Brilliant 0 Confused

Why did you group [0011] if the problem says 12 each? My thought was 2 1´s. We build a group. From that point, we begin to match. Shouldn´t it be 11 possible places? Can we have a nibble[0011] with binaries? Another interesting thing i found out is that once we group them and start working out with bitwise operators (and) we come up with :[ 1 0 0 0 ] [0 0 1 0 ] [ 0 0 0 1]= 8+2+1=11.

Leonardo Bagno - 1 year, 4 months ago
Abdelhamid Saadi
Mar 25, 2016

Python: 

1
2
3
4
5
6
7
8
 
def glitch():
    a = 10
    res = 0
    for x in list('111010101000111001100111111010101000111001100111'):
        a += 1 if x == '1' else -1
        if a == 12 :
            res += 1
    return res

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Mathieu Guinin
Apr 8, 2016 
1
2
3
4
5
6
7
8
 
x = 0b111010101000111001100111
n = 14
c = 0
while (x):
    n += 1 - 2*(x & 1)
    c += n == 12
    x >>= 1
print(c)

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Soumava Pal
Mar 31, 2016

This was a cute little problem:

Here is my code: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
>>> def f(s):
        c=[0,0]
        for i in s:
            if i=='0':
            c[0]+=1
        elif i=='1':
            c[1]+=1
        return c

>>> s='111010101000111001100111'
>>> c=0
>>> for i in range(len(s)):
        m=f(s[:i+1])
        if m[1]-m[0]==2:
            c+=1


>>> c
10
>>>

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...