Sprawdzanie nieskazitelnego bitu


28

Napisz program / funkcję, która przyjmuje dwie liczby całkowite z zakresu od 0 do 255 włącznie i zwraca, czy binarne formy liczb są dokładnie o jeden bit inne.

Na przykład 1 i 0 mają formy binarne 00000001i 00000000, które są nieco od siebie oddzielone. Podobnie 152 i 24010011000i 000011000dlatego zwracają wartość true.

Jednak twój kod musi być nieskazitelny , tak aby jeśli jakiś bit w twoim programie został odwrócony, powinien generować błąd. Na przykład, jeśli twój program był jednobajtowya(01100001), to wszystkie 8 możliwych zmodyfikowanych programów:

á ! A q i e c `

musi zgłosić błąd. Upewnij się, że modyfikujesz bajty (np. áTam, gdzie faktycznie reprezentuje bajt 225 , a nie rzeczywisty znak dwóch bajtów á).

Przypadki testowe:

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

Zasady:

  • Podaj strukturę testową, która może zweryfikować, że twój program jest właściwie nieskazitelny, ponieważ będzie wiele możliwych programów (liczba bajtów * 8), lub też pełny dowód nieskazitelności.
    • Należy upewnić się, że program jest prawidłowy, przed wysłaniem go.
  • Dane wyjściowe muszą być zgodne z prawdą / falseyem (obie strony są w porządku), albo dwie wyraźne wartości bez błędów
  • Błędy mogą dotyczyć środowiska wykonawczego, kompilatora, interpretera itp.

7
Jeśli ktoś szuka sposobu na wygenerowanie wszystkich możliwych wariantów swojego rozwiązania, ten program Japt powinien (ktoś powinien dokładnie sprawdzić) wykonać zadanie: petershaggynoble.github.io/Japt-Interpreter/...
Shaggy

4
Oto także w Pythonie: Wypróbuj online!
TFeld

Funkcje nie są dozwolone, ponieważ wspomniałeś o programie?
Kevin Cruijssen

5
@KevinCruijssen Podałem, że przesyłanie funkcji jest w porządku
Jo King

4
Ten komentarz ma więcej +1s niż większość moich ostatnich rozwiązań! : \
Shaggy

Odpowiedzi:


16

Python 2 , 35 bajtów

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

Wypróbuj online!

Używa testu potęgi dwóch n&-n==n, eliminując n==0fałszywie dodatni.

Dla porównania są to pary jednoznakowych operatorów binarnych, które są nieco od siebie oddalone, co czyni je trudnymi w użyciu:

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

Na szczęście, &i ^nie należą do nich.

Zauważ też, że ==może stać się <=i +może stać się postacią komentarza #.


Python 2 , 41 bajtów

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

Wypróbuj online!

Biorąc TFeld lambda a,b:bin(a^b).count('1')==1 i czyniąc go nieskazitelnym, zmieniając 1 na +Truei ==na is. Dzięki Jo King za 1 bajt.


9

Python 2 , 72 67 50 bajtów

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

Wypróbuj online!

-5 bajtów, dzięki Jo King


Zwraca True/ Falseza truey / falsey.

Program jest w zasadzie taki sam jak lambda a,b:bin(a^b).count('1')==1, ale bez liczb i innych znaków, które działają po odwróceniu bitów.

Działa, upewniając się, że prawie wszystko jest nazwaną funkcją (wszystkie są całkiem nieskazitelne)

Nieskazitelny test na końcu przerzuca jeden bit (za każdy bit) i wypróbowuje funkcję na wejściu. Jeśli to działa (poprawne lub nie), ta odmiana jest drukowana. Brak drukowanych programów = nieskazitelna funkcja.


8

Java 8, 68 61 56 45 bajtów

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

-11 bajty dzięki @EmbodimentOfIgnorance , zastępując stałą java.awt.Font.BOLD z -~(a^a).

Wypróbuj online.

Wyjaśnienie:

Najkrótszą funkcją podstawową byłoby:

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

Wypróbuj online.

Jest to modyfikowane, więc nie ma cyfry =ani jednego z +/*operandów do obliczeń numerycznych (więc+ przypadku konkatenacji ciągów jest w porządku):

+""I .equalssą przez porównanie String.equals(String)zamiast int==int.
UWAGA: Integer.equals(int)może być użyte tutaj, ale byłoby więcej bajtów, ponieważ zarówno .bitCounti java.awt.Font.BOLDsą prymitywne intzamiast Integer-obiektów, więc konieczne new Integer(...)byłoby dodatkowe przekształcenie jednego z dwóch na Integer-obiekt, zanim będziemy mogli użyć .equals.


(int) Math.log (Math.E) ma 21 bajtów
data


@ExpiredData Dzięki, właściwie właśnie znalazłem krótszą stałą java.awt.Font.BOLD, ale Twój Objects.equalsgolf jest fajny, dzięki!
Kevin Cruijssen

@ExpiredData Właściwie Objectsjest częścią java.util.importu, więc obawiam się, że muszę dodać to do liczby bajtów, dzięki czemu 69 bajtów .. :(
Kevin Cruijssen

3
Czy -~(a^a)działałoby za 1?
Embodiment of Ignorance

7

C (gcc) , 56 bajtów

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

Wypróbuj online!

Zwraca, 0jeśli para różni się o 1, w przeciwnym razie niezerowa. Nieco niezwykłe dla C, chyba że uważasz, że powróciEXIT_SUCCESS jeśli para różni się o 1, w przeciwnym razie inna wartość.

Używa sizeof((char)d))do uzyskania stałej1 w nieskazitelny sposób, jednocześnie zmuszając nazwę funkcji do nieskazitelności.

Następnie XORs to 1 z liczbą popartą XOR argumentów. Na szczęście ^symbol jest łatwy do utrzymania w czystości, podobnie jak bardzo długi identyfikator__builtin_popcount .

Tymczasem oto skrypt używany do testowania rozwiązania:

#!/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

Który korzysta z ./flipbitnarzędzia, które napisałem, którego źródłem jest po prostu:

#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;
}

Trudne fragmenty to:

  • Białe znaki: wszystkie białe znaki (w tym znaki nowej linii) mają nieskazitelne bliźniaki, które będą działać podobnie
  • Porównanie: =nie działa dobrze, ponieważ może być porównaniem w każdym przypadku, w którym mogłoby się pojawić. Podobnie -nie działa dobrze. A zatem^ służy do zapewnienia równości z 1.
  • Nazwy zmiennych: f koliduje z b, więc zamiast tego musiał użyć d jako nazwy funkcji.

Jak zachować ^nieskazitelność operatora? Jeśli bity na tym zostały zmienione, co powstrzyma go przed przekształceniem się w innego operatora? To nadal się kompiluje, ale po prostu daje złą odpowiedź. Czy coś tu nie rozumiem co do znaczenia słowa „dziewiczy”?
Cody Gray

4
Odwracając tylko jeden bit, ^można go zmienić tylko na dowolny _\ZVN~Þznak lub na niedrukowalny znak w punkcie kodowym 30. ~jest jedynym z nich, który jest operatorem, ale jest tylko operatorem jednoargumentowym.
Niepowiązany ciąg

1
Lub nawet użyj __LINE__zamiast sizeof(char). Myślę, że można założyć, że twoja funkcja będzie w pierwszej linii pliku .c. Lub nawet unixjest zdefiniowany na 1 w TIO i prawdopodobnie w większości innych Linuksa.
Cyfrowy uraz

2
Głównym powodem rozmiaru char-casted jest dupieczenie do źródła w jak najmniejszej liczbie bajtów. W przeciwnym razie d(lub jakkolwiek nazwiesz funkcję) można po prostu zmienić i kod nadal będzie działał. Nawet (__LINE__)jeśli d();nie zadziała, ponieważ d();można go zmienić na dowolną inną literę i nadal będzie się kompilować, ponieważ funkcja nigdy nie musi być wywoływana, dlatego nie jest połączona.
LambdaBeta

1
@LambdaBeta Jeśli nazwa funkcji ulegnie zmianie, wówczas wystąpi błąd łącza, nawet jeśli d nie jest autoreferencyjne. Osobiście uważam, że to wystarczy.
Digital Trauma

7

R , 38 37 bajtów

-1 bajt dzięki Nickowi Kennedy'emu.

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

Wypróbuj online! (Podziękowania dla Giuseppe za prawidłowe skonfigurowanie TIO.)

Dowód, że jest nieskazitelny (przy użyciu kontrolera Nicka Kennedy'ego ).

Wykazuje 0 dla falsey i dodatnią wartość dla prawdy, co rozumiem, jest dopuszczalne, ponieważ R zinterpretuje je jako False i True.

Objaśnienie: bitwXor(a,b)podaje (jako liczbę całkowitą) bitowy XOR między ai b. Aby sprawdzić, czy jest to potęga 2, sprawdź, czy jego log w bazie 2 jest liczbą całkowitą. Funkcja dpoispodaje funkcję gęstości prawdopodobieństwa rozkładu Poissona: jej wartość wynosi 0 dla wartości niecałkowitych i coś dodatniego dla nieujemnych liczb całkowitych. TJest tam, ponieważ dpoiswymaga drugiego argumentu (żadnych pozytywnych prawdziwe dzieła i Tjest interpretowane jako 1).

Jeśli nalegamy na wyprowadzanie różnych wartości, następująca wersja wyśle ​​FAŁSZ lub PRAWDA w 42 bajtach (dzięki Giuseppe za -8 bajtów):

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

i jest również nieskazitelny . Wypróbuj online!


2
Dobra robota, jeśli chodzi o uzyskanie czegoś znacznie mniejszego niż mój! Można wymienić piz Tzapisać bajt (wciąż nietknięty). Twoje TIO nie odpowiada w tej chwili twojej odpowiedzi.
Nick Kennedy

@NickKennedy Thanks! (I dzięki za napisanie kodu, aby sprawdzić, czy jest nieskazitelny!). TIO, z którym się łączyłem, to zmodyfikowana wersja, która sprawdza wszystkie przypadki testowe. Dodam TIO do rzeczywistego kodu, ale nie mogę wymyślić, jak sprawić, by TIO działało poprawnie z dwoma wywołaniami do scan(); Masz pomysł? (Kod działa dobrze na komputerze.)
Robin Ryder

2
@NickKennedy Może coś takiego? za dopasowanie TIO i kodu?
Giuseppe

@Giuseppe Cudownie, dziękuję!
Robin Ryder

1
Twoja druga wersja mogłaby Fzamiast tego używać exp(-Inf), podobnie jak Nick T:-)
Giuseppe

6

R , 83 bajty

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

Wypróbuj online!

Dowód, że jest to nieskazitelne

Praca wokół faktu, że as.integer, as.doubleitd. Są tylko nieco z dala od is.integer, is.doubleitd. Był najtrudniejszy kawałek. Ostatecznie najlepszym rozwiązaniem było użycie sum(T^el(.[-T])jako sposobu zarówno wygenerowania jednego, jak i sprawdzenia, as.doubleczy zwrócił wektor długości> 1. Opakowanie tma poradzić sobie z faktem, że inaczej identicalmoże się stać ide~tical.


5

Julia 0,7 , 20 bajtów

(a,b)->ispow2(ab)

Wypróbuj online!

Oto nieskazitelny walidator, który próbuje uruchomić każdą zmodyfikowaną anonimową funkcję dla niektórych danych wejściowych i żadna z nich nie powiedzie się. Zauważ, że kod ma wielobajtowy znak Unicode, a niektóre możliwe dane wyjściowe z odwracania bitów nie są nawet uwzględnione, ponieważ generują one niepoprawne ciągi UTF-8.


xi ysą trochę oddzielone, więc uważam, że to kontrprzykład. yi xrównież przy nieco 1 9i 6odpowiednio.
Data wygasła

Cholera, myśląc o skomplikowanych rzeczach, absolutnie tęskniłem za najprostszą. Mamy nadzieję, że zmiana zmiennych to naprawi.
Kirill L.


4

C # (interaktywny kompilator Visual C #) , 128 101 77 70 61 74 bajtów

-27 bajtów dzięki Ascii-Only

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

Wypróbuj online!

Musisz być dość kreatywny, aby uzyskać liczby w C # bez literałów. Używa tylko operatora ^. Zmienne a, b są od siebie oddalone o więcej niż 1 bit, a wszystko inne jest słowem kluczowym / nazwą.


nie trzeba liczyć bitów - wystarczy sprawdzić, czy jest to potęga 2 między 1 a 128
tylko ASCII

@ Tylko ASCII Powodzenia, sprawdzamy to w rozsądnej liczbie bajtów, gdy nie możemy używać liczb całkowitych ani +/*=do operacji matematycznych lub sprawdzania poprawności. ;)
Kevin Cruijssen

@KevinCruijssen C # też ma wyliczenia :(. Damnit
tylko ASCII


1
O_o inny -24. btw już nie używasz+
tylko ASCII

3

JavaScript (ES6 w trybie ścisłym), 61 bajtów

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

Wypróbuj online! lub Upewnij się, że wszystkie zmodyfikowane programy są nieprawidłowe


O rany, nie zdawałem sobie sprawy, że kliknąłem link do kodu golfowego i zobaczyłem tę odpowiedź z kontekstu i prawie miałem zawał serca. Na przykład OMG NO
Marie

4
@Marie Uwaga! Możesz patrzeć na ten kod tylko z certyfikowanymi okularami golfowymi. W przeciwnym razie może poparzyć siatkówkę. : p
Arnauld


1

MATLAB, 37 bajtów

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

Przepraszamy, brak linku do TIO, ponieważ nie mogę zmusić pakietu testowego do pracy pod Octave. Dzięki @ExpiredData za pomocne komentarze.

Zestaw testowy:

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)


@ExpiredData Dzięki za sugestię. numelZamiast tego wybrałem MATLAB , ponieważ mój zestaw testów nie działa w Octave.
Sanchises

38 bajtów może .. nie ma licencji Matlab, ale powinno działać
Data wygasła

1
@ExpiredData Dzięki, można faktycznie zrobić jeden bajt lepiej eye!
Sanchises

1
@ExpiredData Wiem, że jestem bardzo zła na Octave. Ale użycie programu Python w komentarzach OP jest przydatne, aby sprawdzić, czy możesz wprowadzić nową postać bez problemów.
Sanchises

1

Perl 6 , 77 43 bajtów

Dzięki Jo King za -33 bajty.

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

Jest to równoważne z

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

1został przepisany jako elems([""]). 2został przepisany jako sum(elems([""]),elems([""])); elems(["",""])może wydawać się działać, ale elems([""-""])jest również poprawny i wydaje się, że zawiesza tester.

Wypróbuj online!


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.