29
\$\begingroup\$

Write a program/function that takes two integers in the range \$0\$ to \$255\$ inclusive, and returns whether the binary forms of the numbers are exactly one bit different.

For example, \$1\$ and \$0\$ have binary forms 00000001 and 00000000, which are one bit apart. Similarly, \$152\$ and \$24\$ are 010011000 and 000011000, so they return true.

However, your code must be pristine, such that if any one bit in your program is flipped, it should throw an error. For example, if your program was the single byte a (01100001), then all the 8 possible modified programs:

á ! A q i e c `

must throw an error. Make sure you are modifying by bytes (e.g. the á up there is actually representing the byte \$225\$, not the actual two byte character á).

Test cases:

0,1 => Truthy 1,0 => Truthy 152,24 => Truthy 10,10 => Falsey 10,11 => Truthy 11,12 => Falsey 255,0 => Falsey

Rules:

  • Provide a testing framework that can verify that your program is properly pristine, since there will be a lot of possible programs (number of bytes*8), or else a complete proof of pristineness.
    • Please make sure your program is valid before you post it.
  • Output needs to be either truthy/falsey (either way around is fine), or else two distinct non-error values
  • Errors can be runtime, compiler, interpreter etc.
Improve this question
\$\endgroup\$
3
  • 7
    \$\begingroup\$ If anyone's looking for a way to generate all possible variations of their solution, this Japt programme should (someone please double check) do the job: petershaggynoble.github.io/Japt-Interpreter/… \$\endgroup\$ Commented Apr 8, 2019 at 9:57
  • 4
    \$\begingroup\$ Here's one in Python as well: Try it online! \$\endgroup\$ Commented Apr 8, 2019 at 10:02
  • \$\begingroup\$ I'm trying to think of a way to make Pristine machine code. If a bit is flipped in a register field, it just reads the wrong register without crashing. Perhaps the code could checksum itself. Without that requirement x86 can do this in two instructions (xor and popcnt) \$\endgroup\$ Commented Apr 13, 2020 at 5:56

14 Answers 14

Reset to default
16
\$\begingroup\$

Python 2, 35 bytes

lambda a,b:(a^b)&-(a^b)in[a^b or[]]

Try it online!

Uses the power-of-two check n&-n==n, eliminating the n==0 false positive.

For reference, these are the pairs of one-char binary operators that are one bit apart, making them hard to use:

+ / - / * + % - < | < >

Fortunately, & and ^ are not among these.

Also note that == can become <=, and + can become the comment character #.

Python 2, 41 bytes

lambda a,b:bin(a^b).count(`+True`)is+True

Try it online!

Taking TFeld's lambda a,b:bin(a^b).count('1')==1 and making it pristine by changing the 1's to +True and == to is. Thanks to Jo King for 1 byte.

Improve this answer
\$\endgroup\$
0
9
\$\begingroup\$

Python 2, 72 67 50 bytes

lambda a,b:sum(map(int,'{:b}'.format(a^b)))is+True

Try it online!

-5 bytes, thanks to Jo King

Returns True/False for for truthy/falsey.

The program is basically the same as lambda a,b:bin(a^b).count('1')==1, but without numbers and other chars which work when bit-flipped.

Works by making sure that almost everything is a named function (which are all quite pristine)

The pristine test at the end flips a single bit (for every bit), and tries the function on an input. If that works (correct or not), that variation is printed. No printed programs = pristine function.

Improve this answer
\$\endgroup\$
0
8
\$\begingroup\$

Java 8, 68 61 56 45 bytes

a->b->(a.bitCount(a^b)+"").equals(-~(a^a)+"")

-11 bytes thanks to @EmbodimentOfIgnorance, replacing constant java.awt.Font.BOLD with -~(a^a).

Try it online.

Explanation:

The shortest base function would be:

a->b->a.bitCount(a^b)==1

Try it online.

This is modified so there isn't a digit, =, nor one of the +/* operands in it for numeric calculations (so the + for String-concatenation is fine):

The +"" and .equals are to compare by String.equals(String) instead of int==int.
NOTE: Integer.equals(int) could be used here, but would be more bytes, since both the .bitCount and java.awt.Font.BOLD are primitive int instead of Integer-objects, so an additional new Integer(...) would be required to transform one of the two to an Integer-object, before we could use the .equals.

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ (int)Math.log(Math.E) is 21 bytes \$\endgroup\$ Commented Apr 8, 2019 at 11:27
  • 1
    \$\begingroup\$ 59 bytes \$\endgroup\$ Commented Apr 8, 2019 at 11:28
  • \$\begingroup\$ @ExpiredData Thanks, actually just found a shorter constant with java.awt.Font.BOLD, but your Objects.equals is a nice golf, thanks! \$\endgroup\$ Commented Apr 8, 2019 at 11:31
  • \$\begingroup\$ @ExpiredData Actually, Objects is part of the java.util. import, so I have to add that to the byte-count I'm afraid, making it 69 bytes.. :( \$\endgroup\$ Commented Apr 8, 2019 at 11:35
  • 3
    \$\begingroup\$ Would -~(a^a) work for 1? \$\endgroup\$ Commented Apr 8, 2019 at 18:43
7
\$\begingroup\$

C (gcc), 56 bytes

d(a,b){return(sizeof((char)d))^__builtin_popcount(a^b);}

Try it online!

Returns 0 if the pair differ by 1, non-zero otherwise. Slightly unusual for C, unless you consider it returning EXIT_SUCCESS if the pair differ by 1, any other value otherwise.

Uses sizeof((char)d)) to produce the constant 1 in a pristine way while also forcing the function name to be pristine.

It then XORs that 1 with the popcount of the XOR of the arguments. Luckily the ^ symbol is easy to keep pristine, as is the very long identifier __builtin_popcount.

Meanwhile, here is the script used to test the solution:

#!/bin/bash SOURCE_FILE=$1 FOOT_FILE=$2 TMP_SRC=temp.c LENGTH="$(wc -c <"$SOURCE_FILE")" BITS=$((LENGTH*8)) cat "$SOURCE_FILE" >"$TMP_SRC" cat "$FOOT_FILE" >>"$TMP_SRC" if gcc -w $TMP_SRC -o t.out >/dev/null 2>&1; then if ./t.out; then echo "Candidate solution..." else echo "Doesn't even work normally..." exit fi else echo "Doesn't even compile..." exit fi for i in $(seq 1 $BITS); do ./flipbit "$i" <"$SOURCE_FILE" >"$TMP_SRC" cat "$FOOT_FILE" >>"$TMP_SRC" if gcc -w $TMP_SRC -o t.out >/dev/null 2>&1; then echo "Testing flipped bit $i:" cat "$TMP_SRC" ./t.out >/dev/null 2>&1 STATUS=$? if [ "$STATUS" -eq 0 ]; then echo "It works!" exit elif [ "$STATUS" -eq 1 ]; then echo "It doesn't work..." exit else echo "It crashes" fi fi done

Which uses the ./flipbit tool I wrote whose source is simply:

#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int bittoflip = atoi(argv[1]) - 1; int ch; while ((ch = fgetc(stdin)) != EOF) { if (bittoflip < 8 && bittoflip >= 0) { putchar(ch ^ (1 << bittoflip)); } else { putchar(ch); } bittoflip -= 8; } return 0; }

The tricky bits were:

  • Whitespace: All whitespace (including newlines) have pristine twins that will work similarly
  • Comparison: = doesn't work well, since it can be a comparison in every case it could appear. Similarly - doesn't work well. Thus ^ is used to assert equality with 1.
  • Variable names: f would clash with b, so had to use d as the function name instead.
Improve this answer
\$\endgroup\$
9
  • \$\begingroup\$ How do you keep the ^ operator pristine? If the bits on that were changed, what's to stop it from becoming a different operator? This would still compile, but would just give you the wrong answer. Am I misunderstanding something about the meaning of the word "pristine" here? \$\endgroup\$ Commented Apr 9, 2019 at 0:50
  • 4
    \$\begingroup\$ By flipping only one bit, ^ can only be changed into any one of _\ZVN~Þ or the unprintable character at codepoint 30. ~ is the only one of those which is an operator, but it's only a unary operator. \$\endgroup\$ Commented Apr 9, 2019 at 6:33
  • 1
    \$\begingroup\$ Or even use __LINE__ instead of sizeof(char). I think its fine to assume that your function will be on line 1 of your .c file. Or even unix is defined to 1 on TIO, and probably most other Linux. \$\endgroup\$ Commented Apr 9, 2019 at 15:50
  • 2
    \$\begingroup\$ The main reason for the char-casted sizeof is to get d baked into the source in the fewest bytes possible. Otherwise d (or whatever you name the function) can just be changed and the code will still work. Even (__LINE__) with d(); wont work because d(); can be changed to any other letter and it will still compile since the function never has to be called, thus isn't linked. \$\endgroup\$ Commented Apr 9, 2019 at 15:53
  • 1
    \$\begingroup\$ @LambdaBeta If the name of the function changes, then there will be a link error, even if d is not self-referential. I think this is sufficient, personally. \$\endgroup\$ Commented Apr 9, 2019 at 16:49
7
\$\begingroup\$

R, 38 37 bytes

-1 byte thanks to Nick Kennedy.

dpois(log2(bitwXor(scan(),scan())),T)

Try it online! (Thanks to Giuseppe for setting up the TIO properly.)

Proof that it is pristine (using Nick Kennedy's checker).

Outputs 0 for falsey, and a positive value for truthy, which I understand is acceptable since R will interpret these as False and True.

Explanation: bitwXor(a,b) gives (as an integer) the bitwise XOR between a and b. To check whether it is a power of 2, check whether its log in base 2 is an integer. The function dpois gives the probability density function of the Poisson distribution: its value is 0 for non-integer values, and something positive for non-negative integers. The T is there because dpois requires a second argument (any positive real works, and T is interpreted as 1).

If we insist on outputting to distinct values, the following version outputs FALSE or TRUE in 42 bytes (thanks to Giuseppe for -8 bytes):

dpois(log2(bitwXor(scan(),scan())),T)%in%F

and is also pristine. Try it online!

Improve this answer
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Well done on getting something so much smaller than mine! You could replace pi with T to save a byte (still pristine). Also your TIO doesn’t correspond to your answer at the moment. \$\endgroup\$ Commented Apr 9, 2019 at 20:12
  • \$\begingroup\$ @NickKennedy Thanks! (And thanks for writing the code to check it is pristine!). The TIO I linked to is a modified version that checks all the test cases. I'll add a TIO to the actual code, but I can't figure out how to get TIO to run properly with two calls to scan(); do you have an idea? (The code works fine on a computer.) \$\endgroup\$ Commented Apr 9, 2019 at 21:20
  • 2
    \$\begingroup\$ @NickKennedy Maybe something like this? for getting the TIO and the code to match? \$\endgroup\$ Commented Apr 9, 2019 at 21:37
  • \$\begingroup\$ @Giuseppe Wonderful, thanks! \$\endgroup\$ Commented Apr 9, 2019 at 21:40
  • 1
    \$\begingroup\$ your second version could use F instead of exp(-Inf), along the same lines as Nick's T :-) \$\endgroup\$ Commented Apr 9, 2019 at 21:40
6
\$\begingroup\$

R, 83 bytes

t(identical(sum(.<-as.double(intToBits(Reduce(bitwXor,scan())))),sum(T^el(.[-T]))))

Try it online!

Proof that this is pristine

Working around the fact that as.integer, as.double etc. are only a bit away from is.integer, is.double etc. was the hardest bit. In the end, using sum(T^el(.[-T]) as a way of both generating a one and checking that as.double has returned a >1 length vector was the best I could do. The wrapping t is to handle the fact that otherwise identical can become ide~tical.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Julia 0.7, 20 bytes

(a,b)->ispow2(a⊻b)

Try it online!

Here is a pristine validator that tries running each modified anonymous function against some input, and neither passes successfully. Note that the code has a multi-byte unicode character, and some possible outputs from bit flipping are not even included, as those produce invalid UTF-8 strings.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ x and y are one bit apart, so I believe this is a counter example. y and x are also 1 bit off 9 and 6 respectively. \$\endgroup\$ Commented Apr 8, 2019 at 14:36
  • \$\begingroup\$ Damn, while thinking about complex things, I absolutely missed the simplest one. Hopefully, changing the variables will fix it. \$\endgroup\$ Commented Apr 8, 2019 at 14:39
5
\$\begingroup\$

C# (Visual C# Interactive Compiler), 37 bytes

a=>b=>a!=b&((a^b)&-(a^b)).Equals(a^b)

The a=>b=> part cannot be changed, or else the function is invalid.

In a!=b, the = cannot be changed since int cannot be converted to bool.

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

C# (Visual C# Interactive Compiler), 128 101 77 70 61 74 bytes

-27 bytes thanks to Ascii-Only 

a=>b=>{var d=Math.Log(a^b,(int)Math.E);return d.Equals((int)Math.Abs(d));}

Try it online!

You have to be quite creative to get numbers in C# without using literals. Only uses ^ operator. Variables a,b are all more than 1 bit away from each other and everything else is a keyword/name.

Improve this answer
\$\endgroup\$
12
  • \$\begingroup\$ you don't need to count bits - checking if it's a power of 2 between 1 and 128 inclusive is enough \$\endgroup\$ Commented Apr 8, 2019 at 11:57
  • \$\begingroup\$ @ASCII-only Good luck checking that in a reasonable number of bytes when we can't use integers nor +/*= for mathematical or validating operations. ;) \$\endgroup\$ Commented Apr 8, 2019 at 12:00
  • \$\begingroup\$ @KevinCruijssen C# has enums too :(. damnit \$\endgroup\$ Commented Apr 8, 2019 at 12:00
  • 1
    \$\begingroup\$ 101? \$\endgroup\$ Commented Apr 8, 2019 at 12:03
  • 1
    \$\begingroup\$ O_o another -24. btw you no longer use + \$\endgroup\$ Commented Apr 8, 2019 at 12:26
3
\$\begingroup\$

JavaScript (ES6 in strict mode), 61 bytes

(y,z,e)=>eval(`(y${(e='^=z)*!(y&~-y)')!='^=z)*!(y&~-y)'||e}`)

Try it online! or Make sure that all modified programs are wrong

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Oh my gosh I didnt realize I clicked a code golf link and saw this answer out of context and almost had a heart attack. Like, OMG NO \$\endgroup\$ Commented Apr 8, 2019 at 14:15
  • 4
    \$\begingroup\$ @Marie Caution! You can only stare at this code with certified golf glasses. Otherwise, it may burn your retina. :p \$\endgroup\$ Commented Apr 8, 2019 at 14:32
2
\$\begingroup\$

Groovy, 47 36 bytes

a,b->a.bitCount(a^b).equals(-~(a^a))

Try it online!

Adapted version of Kevin Cruijssen's Java answer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

MATLAB, 37 bytes

@(c,e)eq(nnz(de2bi(bitxor(c,e))),eye)

Sorry, no TIO link, because I can't get the test suite to work under Octave. Thanks @ExpiredData for some helpful comments.

Test suite:

program = '@(c,e)eq(nnz(de2bi(bitxor(c,e))),eye)'; number_of_characters = nnz(program); success = []; for character_counter = 0 : number_of_characters for bit_no = 1:8 prog_temp = program; if(character_counter > 0) prog_temp(character_counter) = bitxor(double(prog_temp(character_counter)),2^(bit_no-1)); elseif(bit_no<8) % Test the unmodified program once continue end try eval(prog_temp); eval('ans(2,3)'); disp(prog_temp) success(end+1)=1; catch success(end+1)=0; end end end assert(nnz(success)==1)
Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ 41 bytes \$\endgroup\$ Commented Apr 9, 2019 at 10:34
  • \$\begingroup\$ @ExpiredData Thanks for the suggestion. I went for a MATLAB numel instead, because my test suite does not seem to be working in Octave. \$\endgroup\$ Commented Apr 9, 2019 at 12:01
  • \$\begingroup\$ 38 bytes maybe.. not got a matlab license but should work \$\endgroup\$ Commented Apr 9, 2019 at 12:21
  • 1
    \$\begingroup\$ @ExpiredData Thanks, one can actually do one byte better with eye! \$\endgroup\$ Commented Apr 9, 2019 at 12:24
  • 1
    \$\begingroup\$ @ExpiredData I know, I'm very annoyed at Octave too. But using the Python program in the OP comments is handy to see if you can introduce a new character without problems. \$\endgroup\$ Commented Apr 9, 2019 at 12:57
1
\$\begingroup\$

Perl 6, 77 43 bytes

Thanks to Jo King for -33 bytes.

{elems(i)eq(sum [+^](@_).polymod(+@_ xx*))}

This is equivalent to

{1 eq(sum [+^](@_).polymod(2 xx*))}

1 was rewritten as elems([""]). 2 was rewritten as sum(elems([""]),elems([""])); elems(["",""]) might seem to work but elems([""-""]) is also valid and seems to hang the tester.

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

JavaScript (Node.js), 20 bytes

b=>d=>[i=d^b][i--&i]

Try it online!

validator by Arnauld, modified (not use strict)

Improve this answer
\$\endgroup\$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.