28
\$\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.
\$\endgroup\$
  • 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\$ – Shaggy Apr 8 at 9:57
  • 4
    \$\begingroup\$ Here's one in Python as well: Try it online! \$\endgroup\$ – TFeld Apr 8 at 10:02
  • \$\begingroup\$ Functions aren't allowed, since you mentioned program? \$\endgroup\$ – Kevin Cruijssen Apr 8 at 10:32
  • 5
    \$\begingroup\$ @KevinCruijssen I've specified that function submissions are ok \$\endgroup\$ – Jo King Apr 8 at 10:34
  • 4
    \$\begingroup\$ That comment has more +1s than the majority of my recent solutions! :\ \$\endgroup\$ – Shaggy Apr 11 at 21:34

14 Answers 14

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.

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

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

\$\endgroup\$
  • \$\begingroup\$ (int)Math.log(Math.E) is 21 bytes \$\endgroup\$ – Expired Data Apr 8 at 11:27
  • 1
    \$\begingroup\$ 59 bytes \$\endgroup\$ – Expired Data Apr 8 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\$ – Kevin Cruijssen Apr 8 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\$ – Kevin Cruijssen Apr 8 at 11:35
  • 3
    \$\begingroup\$ Would -~(a^a) work for 1? \$\endgroup\$ – Embodiment of Ignorance Apr 8 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.
\$\endgroup\$
  • \$\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\$ – Cody Gray Apr 9 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\$ – Unrelated String Apr 9 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\$ – Digital Trauma Apr 9 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\$ – LambdaBeta Apr 9 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\$ – Digital Trauma Apr 9 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!

\$\endgroup\$
  • 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\$ – Nick Kennedy Apr 9 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\$ – Robin Ryder Apr 9 at 21:20
  • 2
    \$\begingroup\$ @NickKennedy Maybe something like this? for getting the TIO and the code to match? \$\endgroup\$ – Giuseppe Apr 9 at 21:37
  • \$\begingroup\$ @Giuseppe Wonderful, thanks! \$\endgroup\$ – Robin Ryder Apr 9 at 21:40
  • 1
    \$\begingroup\$ your second version could use F instead of exp(-Inf), along the same lines as Nick's T :-) \$\endgroup\$ – Giuseppe Apr 9 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.

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

\$\endgroup\$
  • \$\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\$ – Expired Data Apr 8 at 14:36
  • \$\begingroup\$ Damn, while thinking about complex things, I absolutely missed the simplest one. Hopefully, changing the variables will fix it. \$\endgroup\$ – Kirill L. Apr 8 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!

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

\$\endgroup\$
  • \$\begingroup\$ you don't need to count bits - checking if it's a power of 2 between 1 and 128 inclusive is enough \$\endgroup\$ – ASCII-only Apr 8 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\$ – Kevin Cruijssen Apr 8 at 12:00
  • \$\begingroup\$ @KevinCruijssen C# has enums too :(. damnit \$\endgroup\$ – ASCII-only Apr 8 at 12:00
  • 1
    \$\begingroup\$ 101? \$\endgroup\$ – ASCII-only Apr 8 at 12:03
  • 1
    \$\begingroup\$ O_o another -24. btw you no longer use + \$\endgroup\$ – ASCII-only Apr 8 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

\$\endgroup\$
  • \$\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\$ – Marie Apr 8 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\$ – Arnauld Apr 8 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.

\$\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)
\$\endgroup\$
  • \$\begingroup\$ 41 bytes \$\endgroup\$ – Expired Data Apr 9 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\$ – Sanchises Apr 9 at 12:01
  • \$\begingroup\$ 38 bytes maybe.. not got a matlab license but should work \$\endgroup\$ – Expired Data Apr 9 at 12:21
  • 1
    \$\begingroup\$ @ExpiredData Thanks, one can actually do one byte better with eye! \$\endgroup\$ – Sanchises Apr 9 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\$ – Sanchises Apr 9 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!

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

JavaScript (Node.js), 20 bytes

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

Try it online!

validator by Arnauld, modified (not use strict)

\$\endgroup\$
  • \$\begingroup\$ @JoKing Should be fixed. Pasted wrong url.. \$\endgroup\$ – tsh Aug 8 at 6:52

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.