Radioactive Bit Checking

8

Note: This is the version of my previous challenge Pristine Bit Checking. This should be much more difficult than that one.

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 radiation-hardened, such that if any one bit in your program is flipped, it should still work correctly. For example, if your program was the single byte a (01100001), then all the 8 possible modified programs:

á ! A q i e c `

must still work correctly. 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:

With Truthy meaning they are different by one bit.

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 radiation-hardened, since there will be a lot of possible programs (number of bytes*8), or else a complete proof of validity.
    • Please make sure to double-check your program is valid before you post it.
  • Output can to be either truthy/falsey (either way around is fine), or else as one distinct value for truthy and the rest as falsey

Here is a helper program that can be used to produce all the variations of an inputted program.

Jo King

Posted 2019-08-08T02:09:34.567

Reputation: 38 234

4"should be much more difficult than that one" -- this is stating the matter lightly – Jonah – 2019-08-08T02:42:19.557

For the record, ignoring empty programs, this would be impossible in any language whose code must be valid UTF-8. – Ørjan Johansen – 2019-08-09T00:03:38.917

Answers

6

HTML + JavaScript, 210 bytes

<script>[d,b]=location.search.match(/[\d]([\d]*)?/g);1/b/d&&document.write([i=b^d][i--&i]+'<!-'+'-')</script></script>0<script>[d,b]=location.search.match(/\d+/g);document.body.innerHTML=[i=b^d][i&i-1]</script>

Open page with search parameters index.html?a=1&b=2.

Validation (Python + Selenium + Firefox)

# -*- coding: utf-8 -*-
from selenium import webdriver
import os
source = "<script>[d,b]=location.search.match(/[\d]([\d]*)?/g);1/b/d&&document.write([i=b^d][i--&i]+'<!-'+'-')</script></script>0<script>[d,b]=location.search.match(/\d+/g);document.body.innerHTML=[i=b^d][i&i-1]</script>"
filename = os.path.abspath("temp1.html")

browser = webdriver.Firefox()

def test(html, input_values, expected):
    with open(filename, "w", encoding="latin-1") as html_file:
        html_file.write(html)
    [a, b] = input_values
    browser.get("file:///" + filename + "?a=" + str(a) + "&b=" + str(b))
    text = browser.find_element_by_tag_name("body").text
    if text == "true" and expected == True: return True
    if text == "false" and expected == False: return True
    if text == "undefined" and expected == False: return True
    try:
        if int(text) != 0 and expected == True: return True
        if int(text) == 0 and expected == False: return True
    except: pass
    print(html, input_values, expected, text)

testcases = [
    [[1, 1], False],
    [[1, 2], False],
    [[1, 3], True],
]

fullTestcases = [
    [[0, 1], True],
    [[1, 0], True],
    [[152, 24], True],
    [[10, 10], False],
    [[10, 11], True],
    [[11, 12], False],
    [[255, 0], False],
]

def runAllTestcases(html, testcases):
    for testcase in testcases:
        test(html, *testcase)

runAllTestcases(source, fullTestcases)

for pos in range(len(source)):
    for flip in range(8):
        flip_char = chr(ord(source[pos]) ^ (2 ** flip))
        flip_source = source[0:pos] + flip_char + source[pos+1:]
        runAllTestcases(flip_source, testcases)
    print(pos, "/", len(source))

browser.quit()

Usage:

  • make sure you have python3 and firefox installed.
  • save this python code to your locale.
  • pip install selenium
  • download firefox web driver and put it in the same folder of this python source.
  • execute this validator and wait it finish.

How

If the modification is on the first time of script. The script will throw some errors (syntax error, undefined variable, etc.). And the second time of script will run correctly and overwrite the output.

If the modification is not on the first time of script. The script output

Learn some (useless) HTML knowledge

  • document.write insert HTML to current position. You should not output unbalanced HTML in usual. When unbalanced HTML is printed. It inserted as is. And following HTML are re-parsed. You may even insert something like <!-- to open a comment.
  • When trying to parse <head>, if HTML parser got anything should not be existed here, the <head> tag is closed immediately and a <body> is created.
  • When the tag is created, document.body is accessible.
  • <script> tag is closed by </script>. Anything between them are script. Script may not be valid, and that doesn't matter (doesn't break HTML).
  • Exception in previous <script> tag does not prevent the following 's execution.

tsh

Posted 2019-08-08T02:09:34.567

Reputation: 13 072

There must be some more golfing spaces. But I am tired to wait the validator... – tsh – 2019-08-08T06:17:46.957