5
\$\begingroup\$

For more information on Parity: Wikipedia

Challenge

Write a program that takes an input (stdin, argv, ect) of four nibbles and two parity nibbles. Your program should then test to see whether the 'block' is valid, using even parity; if it is then output 1. Then try to make any corrections, if correction is possible output the corrected block. If you cannot correct the block output -1. You can assume the parity nibbles are never corrupt.

To re-cap and clarify:

  • If the input is valid output 1.
  • If the input is invalid and fixable output the fixed block.
  • If the input is invalid and cannot be fixed output -1.
  • You can only edit bits if their respective row and column in the parity bit is incorrect.

Input Format:

<NIBBLE> <NIBBLE> <NIBBLE> <NIBBLE> <PARITY-Y> <PARITY-X>

So 1010 0111 1101 1011 1011 0111 Would look like:

Parity Block

Winning

This is : Smallest program wins.

Input and Output Examples

Input 1010 0111 1101 1011 1011 0111
Output 1
The Input is Valid

Input 1010 0011 1101 1011 1011 0111
Output 1010 0111 1101 1011
The Input was Invalid, but correctable

Input 1010 0001 1101 1011 1011 0111
Output -1 The Input was Invalid, and not correctable

\$\endgroup\$
  • \$\begingroup\$ So the parity nibbles are guaranteed to be correct? \$\endgroup\$ – Martin Ender May 28 '14 at 23:36
  • \$\begingroup\$ @m.buettner Yes, you can assume the parity nibbles are never corrupted \$\endgroup\$ – Harry Beadle May 28 '14 at 23:55
  • \$\begingroup\$ Does "correctable" mean correctable by flipping a single bit only? I could "correct" any input to match parity bits 0000 0000 for example, in more than one way. You can also correct your example 1011 0111 bits to nibbles 0000 1011 1011 1011, etc. I ask because you use the plural in "...try to make corrections..." \$\endgroup\$ – Geobits May 29 '14 at 0:26
  • 2
    \$\begingroup\$ You may want to add something to the effect of "You may only change a bit if that bit's row/column parity bit is incorrect." I'm still not convinced that outputs are unique for a given input, but that would definitely clarify it a bit. \$\endgroup\$ – Geobits May 29 '14 at 1:11
  • 7
    \$\begingroup\$ It is impossible to know for sure what the correct answer is. When a corruption is detected, it is possible that 5 bits are corrupted instead of only 1. \$\endgroup\$ – user12205 May 29 '14 at 1:13
3
\$\begingroup\$

Python 2, 387

I feel it's kinda long though. Do suggest improvements or any fixes...

i=raw_input()
z="""#h(a?(a&1)^h(a/2)~a@0
#y(i,m,l,c=0?h(i&m)|y(i>>l,m,l,c+1)*2~c<4@0
#p(i?y(i,4369,1)*16+y(i,15,4)
k=i.replace(" ","")
m=int(k[:16],2)
c=int(k[-8:],2)
#s(i?s(i>>4)+" "+bin(i&15^16)[3:]~i@"" 
#q(j=16):d=m^1<<j;!s(d)[1:]~p(d)==c@q(j-1)~j@-1
#f(?1~p(m)==c@q()"""
for k,l in("?","):!"),("!","return "),("@"," else "),("#","def "),("~","if "):z=z.replace(k,l)
exec z
print f()

Slightly ungolfed...

def y(i,m,l,c=0):
    h=lambda a:(a&1)^h(a/2)if a else 0 # Calculate how many set bits in i
    return h(i&m)|y(i>>l,m,l,c+1)*2if c<4 else 0 # Sets the parity bits accordingly recursively

p=lambda i:y(i,4369,1)*16+y(i,15,4) # Returns the y and x parity together

i="1010 0111 1101 1011 1011 0111"

k=i.replace(" ","") # Remove all spaces
m=int(k[:16],2)     # Extracts the matrix
c=int(k[-8:],2)     # Extracts the parities

s=lambda i:s(i>>4)+" "+bin(i&15^16)[3:]if i else"" 
# Converts from int to space separated hexas in binary

def f(i):
    if p(m)==c:return 1 # If calculated parities matches the test
    for i in range(16): # Else, for each of the 16 bits in the matrix
        d=m^1<<i        # xor it
        if p(d)==c:return s(d)[1:] # return the matrix if its parities matches the test
    return -1 # If all else fails, return -1


print f(i)
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 234 bytes

s=>(a=s.split` `,[...a.pop()].map((c,i)=>a[i]+=c),x=y=0,[...a].map((s,i)=>[...s].map((c,j)=>{x^=c<<i;y^=c<<j})),x&=15,y&=15,a.pop(),x|y?x-(x&-x)|y-(y&-y)?-1:[...a].map((s,i)=>s.slice(0,4).replace(/./g,(c,j)=>c^x>>i&y>>j&1)).join` `:1)

Save 21 bytes if an array of strings is an acceptable I/O format, or 46 bytes if a two-dimensional array of bits is acceptable. Explanation: The original string is split into blocks and then rearranged into an almost square formation:

DDDDX
DDEDX
DDDDX
DDDDX
YYYY

The row and column parities are then calculated, each setting the appropriate bit in the x and y variables, so for instance if the error was in the bit marked E it would set x to 2 and y to 4. (If the parity of the parity blocks was also provided, then it could also be checked, and an error in the parity blocks or indeed the parity bit itself could be detected. The two parity blocks should have the same parity, of course.)

s=>(                    String parameter
 a=s.split` `,          Split it into blocks
 [...a.pop()]           Remove the X parity block and loop over it
  .map((c,i)=>a[i]+=c), Append the X parity bits to the data blocks
 x=y=0,                 Initialise the X and Y parity
 [...a].map((s,i)=>     Loop over rows
  [...s].map((c,j)=>     and columns
   {x^=c<<i;y^=c<<j})),   updating the parity
 x&=15,y&=15,           Only bits 0-3 are important
 a.pop(),               Remove the Y parity block
 x|y?                   If there were parity errors
  x-(x&-x)|y-(y&-y)?-1:  If there were several errors then return -1
   [...a].map((s,i)=>     If there was one error then loop over blocks
    s.slice(0,4)           Removing the X parity bit
     .replace(/./g,(c,j)=>  Loop over bits
      c^x>>i&y>>j&1))        Flip the bit if it was the incorrect bit
    .join` `:              Join the blocks together
   1)                    Return 1 if there were no parity errors
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.