18
\$\begingroup\$

A parity bit, is one of the simplest forms of a checksum. First, you have to pick the parity, even or odd. Let's say we pick even. Now, we need a message to transmit. Let's say our message is "Foo". This is written in binary as:

01000110 01101111 01101111

Now, we count the total number of 1's in there, which is 15. Since 15 is an odd number, we must add one extra bit to the end of our message, and we will now have an even number of 'on' bits. This last added bit is known as the "parity bit". If we had picked an odd parity for our checksum, we would have to add an extra '0' so that the number of on bits remains odd.

The challenge:

You must write a program or function that determines what the correct parity bit for a string is. Your program must take two inputs:

  • A string, s. This is the message that the checksum will be calculated on. This will be restricted to the 95 printable ASCII characters.

  • A character or single character string p, that will either be e for even parity, or o for odd parity.

and produce a truthy-falsey value representing the correct parity bit. Truthy if it's a 1, and falsey if it's a 0.

Builtins that count the number of "on" bits in a string or character are not allowed. For example, a function f that does this: f('a') == 3 or f('foo') == 16 is banned. Anything else, such as base conversion, is fair game.

Test IO:

(without the quotes)
s: "0"
p: 'e'
output: 0

s: "Foo"
p: 'e'
output: 1

s: "Hello World!"
p: 'o'
output: 0

s: "Alex is right"
p: 'e'
output: 1

s: "Programming Puzzles and Code-Golf" 
p: 'e'
output: 0

s: "Programming Puzzles and Code-Golf" 
p: 'o'
output: 1

This is codegolf, so standard loopholes apply, and the shortest answer in bytes wins.

Leaderboard

var QUESTION_ID=78569,OVERRIDE_USER=31716;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • 10
    \$\begingroup\$ Rather annoyingly, o has even parity. \$\endgroup\$ – Neil Apr 25 '16 at 23:36
  • \$\begingroup\$ Can you clarify "Builtins that count the number of "on" bits in a string or character are not allowed." a bit better? What about built-in base conversion? Etc.. \$\endgroup\$ – orlp Apr 25 '16 at 23:46
  • \$\begingroup\$ @DrGreenEggsandHamDJ Comments on Stack sites are volatile and subject to disappear without warning for no reason, at any capable user's whim. As a result, it's highly encouraged that specs integral to the challenge be in the post itself, not the comment section. \$\endgroup\$ – cat Apr 26 '16 at 2:00
  • 1
    \$\begingroup\$ @cat For example, in python: str(int(s, 2)).count('1')? No, I wouldn't consider that to be a single builtin function that violates that rule. Does my edit make it more clear? \$\endgroup\$ – DJMcMayhem Apr 26 '16 at 2:08
  • 1
    \$\begingroup\$ @cat As far as I'm concerned char == single_char_string. I also edited that into the post. \$\endgroup\$ – DJMcMayhem Apr 26 '16 at 19:10

23 Answers 23

9
\$\begingroup\$

MATL, 8 7 bytes

8\hBz2\

Try it online! Or verify all test cases at once.

8\    % Implicitly take first input ('e' or 'o'), and compute modulo 8. Inputs 'e' and 'o' 
      % give 5 or 7 respectively, which have an even or odd number of `1` bits resp.
h     % Implicitly take second input, and concatenate
B     % Convert to binary. Gives 2D array, with one row for each original entry 
z     % Number of nonzero values in that 2D array
2\    % Modulo 2, i.e. compute parity
\$\endgroup\$
9
\$\begingroup\$

Java, 97 bytes

Because, ya know, Java.

(s,c)->{boolean e=1>0;for(int i:s.getBytes())while(i>0){if(i%2==1)e=!e;i/=2;}return c=='o'?e:!e;}

This is a lambda for a BiFunction<String, Character, Boolean>.

e and o appear to be reversed in the return statement because apparently my logic was backwards.

\$\endgroup\$
5
\$\begingroup\$

Python 2, 51 bytes

lambda s,p:`map(bin,map(ord,p+s))`[9:].count('1')%2

This is based on an idea of Sp3000 to count 1's in the string representation of the list of character codes in binary rather than summing for each character.

The new trick is to handle e and o in this as well. If e was odd and o even, we could just prepend the parity bit to the string before doing the count (flipping them because '1' is Truthy). Unfortunately, they are not. But, if we remove all but their last two bits, it's now true.

e 0b11001|01
o 0b11011|11 

This is done by removing the first 9 character of the string representation.

['0b11001|01', 
\$\endgroup\$
  • \$\begingroup\$ Wow, that's a really neat way of handling eo! \$\endgroup\$ – Sp3000 Apr 27 '16 at 3:17
4
\$\begingroup\$

Jelly, 9 8 bytes

OBFSḂ⁼V}

Try it online!

O         convert each character in argument 1 (left arg) to its codepoint (ord)
 B        convert to binary (list of 0s and 1s)
  F       flatten
   S      sum the entire list, giving the number of 1s in the entire string
    Ḃ     mod 2 (take the last bit)
       }  now, with the second (right) argument...
      V   eval with no arguments. This returns...
            1 for e because it expands to 0e0 (i.e., does 0 exist in [0])
            0 for o because it expands to 0o0 (0 OR 0, false OR false, false)
     ⁼    test equality between the two results

Thanks to Dennis for a byte!

\$\endgroup\$
  • 1
    \$\begingroup\$ I was myself trying to come up with a Jelly answer, but those chaining rules ellude me :-) \$\endgroup\$ – Luis Mendo Apr 26 '16 at 0:40
  • 2
    \$\begingroup\$ @LuisMendo I'm in the same boat; this is my first Jelly answer after having been trying to learn it for... way too long :P \$\endgroup\$ – Doorknob Apr 26 '16 at 0:41
  • \$\begingroup\$ That V}... that one was really cool!!! (Dennis is a real golfer) +1 It beat every attempt of mine. \$\endgroup\$ – Erik the Outgolfer Oct 13 '16 at 12:53
4
\$\begingroup\$

C, 62 bytes

  • 12 bytes saved thanks to @LevelRiverSt and @TonHospel.

XOR has the nice property that it can be used to reduce strings down to one char, while preserving parity.

f(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;}

Ideone.

\$\endgroup\$
  • 1
    \$\begingroup\$ 27030>>((p^p>>4)&15)&1 should calculate the parity of p and is even 1 byte shorter \$\endgroup\$ – Ton Hospel Apr 26 '16 at 8:51
  • 1
    \$\begingroup\$ The space in char *s is uneeded \$\endgroup\$ – Ton Hospel Apr 26 '16 at 9:21
  • 2
    \$\begingroup\$ 62 bytes: f(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;} The %3 will always return 0 for a 0, but may return 1 or 2 for a 1. This is acceptable under the rules: truthy if it's a 1 \$\endgroup\$ – Level River St Apr 26 '16 at 9:29
  • 1
    \$\begingroup\$ 27030>>((p^p>>4)&15)&1. Well, err, obviously. ;-) \$\endgroup\$ – Digital Trauma Apr 26 '16 at 15:02
  • \$\begingroup\$ @LevelRiverSt Brilliant! thanks! \$\endgroup\$ – Digital Trauma Apr 26 '16 at 15:17
4
\$\begingroup\$

Python, 58 57 bytes

lambda s,p:sum(bin(ord(c)).count("1")for c in s)&1!=p>'e'
\$\endgroup\$
  • 1
    \$\begingroup\$ 53 (Python 2 only): lambda s,p:`map(bin,map(ord,s))`.count('1')%2^(p>'e') \$\endgroup\$ – Sp3000 Apr 26 '16 at 8:02
  • \$\begingroup\$ You can save a byte with !=p>'e'. \$\endgroup\$ – xnor Apr 26 '16 at 8:59
  • \$\begingroup\$ Wait, my byte-save doesn't actually work because Python treats it as a chained inequality. \$\endgroup\$ – xnor Apr 26 '16 at 9:07
  • \$\begingroup\$ lambda s,p:`map(bin,map(ord,p+s))`[8:].count('1')%2 \$\endgroup\$ – xnor Apr 26 '16 at 9:11
  • \$\begingroup\$ @xnor Just post your own answer. \$\endgroup\$ – orlp Apr 26 '16 at 9:32
3
\$\begingroup\$

Pyth, 12 bytes

q@"oe"sjCz2w

Test suite.

         z    take a line of input
        C     convert to int
       j  2   convert to base 2, array-wise (so, array of 0s and 1s)
      s       sum (count the number of ones)
 @"oe"        modular index into the string to get either "o" or "e"
q          w  test equality to second line of input
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 84 72 bytes

(s,p)=>(t=p>'e',[...s].map(c=>t^=c.charCodeAt()),t^=t/16,t^=t/4,t^t/2)&1

Bit twiddling turned out to be shorter than converting to base 2 and counting 1s.

\$\endgroup\$
2
\$\begingroup\$

Perl, 29 bytes

Includes +2 for -p

Run with the input on STDIN as parity character space string, e.g.

parity.pl <<< "p Programming Puzzles and Code-Golf"

parity.pl

#!/usr/bin/perl -p
$_=unpack"B*",$_|b;$_=1&y;1;
\$\endgroup\$
2
\$\begingroup\$

J, 27 bytes

'oe'&i.@[=[:~:/^:2@#:3&u:@]

Usage

   f =: 'oe'&i.@[=[:~:/^:2@#:3&u:@]
   'e' f '0'
0
   'e' f 'Foo'
1
   'o' f 'Hello World!'
0
   'e' f 'Alex is right'
1
   'e' f 'Programming Puzzles and Code-Golf'
0
   'o' f 'Programming Puzzles and Code-Golf'
1
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 69 bytes

(s,p)=>[...s].map(c=>{for(n=c.charCodeAt();n;n>>=1)r^=n&1},r=p>"e")|r
\$\endgroup\$
1
\$\begingroup\$

PowerShell v2+, 91 bytes

/me cries in a corner

param([char[]]$a,$b)$b-eq'o'-xor(-join($a|%{[convert]::toString(+$_,2)})-replace0).length%2

Yeah ... so, base conversion is not a strong suit for PowerShell. The conversion from input string to binary representation $a|%{[convert]::toString(+$_,2)} is 32 bytes in and of itself ...

Takes input $a and $b, explicitly casting $a as a char-array in the process. We then check whether $b is -equal to o, and -xor that with the other half of the program. For that part, we take the input string $a, pipe it through a loop to convert each letter to binary, -join all those together to form one solid string, and -replace all the 0s with nothing. We then count the .length of that string and take it mod-2 to determine if it's even or odd, which will conveniently be either 0 or 1, perfect for the -xor.

Will return True or False accordingly. See test cases below:

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "0" e
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Foo" e
True

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Hello World!" o
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Alex is right" e
True

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Programming Puzzles and Code-Golf" e
False

PS C:\Tools\Scripts\golfing> .\generate-parity-bit.ps1 "Programming Puzzles and Code-Golf" o
True
\$\endgroup\$
1
\$\begingroup\$

Factor, 85 bytes

For some reason I couldn't wrap my head around this one until a few minutes ago, when I simplified (and maybe shortened?) the code.

[ "e" = [ even? ] [ odd? ] ? [ [ >bin ] { } map-as concat [ 49 = ] count ] dip call ]

? is like a ternary operator: it tests the truthiness of the third stack item, and either selects the true value or the false value.

It's roughly equivalent to the following C-like pseduocode:

void* parity_tester_function = strcmp(p, "e") ? (void *) even?  // it's a function pointer (I think)
                                              : (void *) odd? ;

The rest of the code is pretty simple:

[                       ! to count a string's set bits:
    [ >bin ] { } map-as ! get the binary of each character, and map as an array, because you can't have stringy data nested in another string (that's called a type error)
    concat              ! { "a" "B" } concat -> "aB"
    [ 49 = ] count      ! count items in the resulting string which match this condition (in this case, the condition we're testing is whether the character has the same code point as "1")
] dip                   ! take the above function pointer off the stack, apply this anonymous function to the now-top of the stack, then restore the value after the quotation finishes.
                        ! in other words, apply this quotation to the second-to-top item on the stack
call                    ! remember that conditionally chosen function pointer? it's on the top of the stack, and the number of sets bits is second.
                        ! we're gonna call either odd? or even? on the number of set bits, and return the same thing it does.
\$\endgroup\$
1
\$\begingroup\$

IA-32 machine code, 15 bytes

Hexdump:

0f b6 c2 40 32 01 0f 9b c0 3a 21 41 72 f6 c3

Assembly code:

    movzx eax, dl;
    inc eax;
repeat:
    xor al, [ecx];
    setpo al;
    cmp ah, [ecx];
    inc ecx;
    jb repeat;
    ret;

This is a function that receives its first argument (string) in ecx and second argument (char) in dl. It returns the result in eax, so it's compatible with the fastcall calling convention.

This code bends the rules when it uses the setpo instruction:

Builtins that count the number of "on" bits in a string or character are not allowed

This instruction sets al to the parity bit calculated by the previous instruction - so I have these two nitpicks on the rules:

  • It doesn't count the number of "on" bits - it calculates the parity bit directly!
  • Technically, it's the previous instruction (xor) that calculates the parity bit. The setpo instruction only moves it to the al register.

These semantic details out of the way, here is the explanation on what the code does.

The representations of the characters are:

'e' = 01100101
'o' = 01101111

If we add 1 to them, they happen to have just the right parity:

'e' + 1 = 01100110 (odd parity)
'o' + 1 = 01110000 (even parity)

So we XOR all the characters of the string, initializing al to these values, which gives the answer.


The first instruction is movzx eax, dl instead of the more obvious (and shorter) mov al, dl, because I want to have the number 0 in a register (ah in this case) in order to be able to compare it in the right order (0, [ecx] rather than [ecx], 0).

\$\endgroup\$
1
\$\begingroup\$

Julia, 58 47 45 40 bytes

f(s,p)=(p>'e')$endof(prod(bin,s)∩49)&1

This is a function that accepts a string and a character and returns an integer.

To get the number of ones in the binary representation, we first apply the bin function to each character in the string, which gives us an array of binary strings. Then reduce them into one using prod (since * is string concatenation in Julia) and take the set intersection of that string and the character code for 1, which gives us a string of ones. The last index of that string is the number of ones. We XOR this with 1 if the provided character is o and 0 otherwise, then get the parity using bitwise AND 1.

Try it online! (includes all test cases)

Saved 18 bytes thanks to Dennis!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 15, 13 bytes

Code:

€ÇbSOÈ„oe²k<^

Example Input:

Programming Puzzles and Code-Golf
o

Example Output:

1

Explanation:

€                 # for each char in string
 Ç                # get ascii value
  b               # convert to binary
   S              # split to single chars (ex: '1101' to '1','1','0','1')
    O             # sum
     È            # check if even
      „oe         # push string "oe"
         ²        # push 2nd input (p)
          k       # get 1-based index of p in "oe"
           <      # decrease (to get either 0-based index)
            ^     # xor with result of È

Thanks to Adnan for saving 2 bytes.

\$\endgroup\$
  • \$\begingroup\$ Wow, very nice! You can golf off two bytes by using the ² command. This automatically pushes the second input on top of the stack. Also, two-char strings can be shortend using . So "oe" is equivalent to . For 13 bytes: €ÇbSOÈ„oe²k<^ :) \$\endgroup\$ – Adnan Apr 27 '16 at 12:39
  • \$\begingroup\$ 05AB1E also uses CP-1252 encoding, so each character here is 1 byte :). \$\endgroup\$ – Adnan Apr 27 '16 at 12:40
  • \$\begingroup\$ @Adnan: Thanks! Used notepad++ for the bytecount and just assumed that it counted chars :P \$\endgroup\$ – Emigna Apr 27 '16 at 13:11
0
\$\begingroup\$

Ruby, 57 bytes

If 0 was falsey in Ruby, the == could probably be switched to just -, or there could be other optimizations, but it isn't.

->s,b{s.gsub(/./){$&.ord.to_s 2}.count(?1)%2==(b>?i?0:1)}
\$\endgroup\$
0
\$\begingroup\$

Retina, 102 bytes

Takes the string on the first line, and the letter on the second line. Uses ISO 8859-1 encoding.

[12478abdghkmnpsuvyzCEFIJLOQRTWX#%&)*,/;=>@[\]^| ](?=.*¶)
1
[^1](?=.*¶)
0
^(0|10*1)*¶o|^0*1(0|10*1)*¶e

Try it online

The character class on the first line matches any character with an odd number of ones in the binary representation.

Description of how even/odd detection with regex works here.

\$\endgroup\$
0
\$\begingroup\$

Octave, 56 bytes

f=@(s,p) mod(sum((i=bitunpack([s p]))(1:length(i)-5)),2)

The bitunpack function, for ASCII characters, returns them in little-endian order. So by putting the parity flag at the end of our string, unpacking the whole thing, and dropping the last 5 bits, we can then sum up the whole thing mod 2 for our ultimate answer.

Usage:

octave:137> f('Hello World!', 'o')
ans = 0
octave:138> f('Hello World!', 'e')
ans =  1
\$\endgroup\$
0
\$\begingroup\$

 Common Lisp, 87

(lambda(s p)(=(mod(reduce'+(mapcar'logcount(map'list'char-code s)))2)(position p"oe")))
  • Sum the logcount of char-codes of s.
  • The remainder of this, when divided by 2, is compared to the position of the parity argument p in the string "oe" (either 0 or 1). For example, if there are 4 ones, the remainder is zero. If p is o, then no additional bit should be added, and the test return false.

Pretty-printed

(lambda (s p)
  (= (mod (reduce '+ (mapcar 'logcount (map 'list 'char-code s))) 2)
     (position p "oe")))
\$\endgroup\$
0
\$\begingroup\$

Java, 91 bytes

(s,c)->{s+=c%8;int e=1;for(int i:s.getBytes())while(i>0){if(i%2==1)e^=1;i/=2;}return e==0;}

I did the same as @CAT97, but stripped some characters by using the modulo 8 and concatenate of @Luis Mendo and the use of int instead of boolean.

This is a lambda for a BiFunction<String, Character, Boolean>.

\$\endgroup\$
0
\$\begingroup\$

Matlab, 49 bytes

f=@(x,p)mod(sum(sum(dec2bin(x)-'0'))+(p-'e'>0),2)

where:

  • x is the input string;
  • p is 'e' for even parity and 'o' for the odd one.

For example:

>> f('Programming Puzzles and Code-Golf','e')

ans =

     0
\$\endgroup\$
0
\$\begingroup\$

Bash and unix tools (72 bytes)

f(){ bc<<<"$(xxd -b<<<"$2$1"|cut -b9-64|tail -c +7|tr -dc 1|wc -c)%2" }

Excepts s as the first and p as the second argument. Fortunately the last 3 bits of o and e has odd and even parity respectively.

xxd -b        print the concatenation of `p` and `s` in binary
cut -b9-64    parse xxd output
tail -c +7    keep only the last 3 bits of `p`
tr -dc 1      keep only the `1`s
wc -c         count them
bc ...%2      modulo two

Supplying the input via <<< adds a line feed character, but the parity of \n is even, so it is not a problem.

\$\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.