20
\$\begingroup\$

To increase data safety at our company, we are planning to start using Gray code numbers (where successive values differ by only one bit) instead of classical binary ones.

Please help us to make a program that converts numbers to Gray code (single number to single number), but the program needs to be safe as well. This means that each successive byte of the program can differ at most by one bit.

Here is a code from Wikipedia for conversion (ungolfed and "unsafe"):

uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

This code does following: Input number is bit shifted to the right by one bit and then there is performed exclusive or with original number. Example with input 123:

Binary representation of 123 is 1111011b, after shift right the number is 0111101b. After performing exclusive or between those two numbers the result is 1000110b, which is 70 in decimal.

Example inputs, outputs:

0, 0
1, 1
123, 70
255, 128
11, 14

Example of safe programs:

a

bcbcbc
!!!
h()
bcg

Example of unsafe programs:

abc
OP
\$\endgroup\$
7
  • 3
    \$\begingroup\$ Please explain converts numbers to gray code, perhaps with a worked example. Also, gray should be capitalized, as it's a proper noun \$\endgroup\$
    – Luis Mendo
    Jun 19 at 17:44
  • \$\begingroup\$ Fixed the capitalization, but I don't really understand what do you mean by explaining as the code for conversion is already there. \$\endgroup\$
    – Jiří
    Jun 19 at 17:55
  • 3
    \$\begingroup\$ I didn't see the code is commented. Still, a description in text, preferably with and example, would be better \$\endgroup\$
    – Luis Mendo
    Jun 19 at 18:01
  • 1
    \$\begingroup\$ Added the description with example, hope I wrote it good enough. \$\endgroup\$
    – Jiří
    Jun 20 at 13:19
  • 1
    \$\begingroup\$ I really hope to see a solution in javascript, but it seems quite impossible though. I've made some progress, but you cannot have return or =>. ] is also quite troublesome since you can only have } after it. \$\endgroup\$
    – newbie
    Jun 21 at 0:31

4 Answers 4

15
\$\begingroup\$

Incident, 100 bytes

@``aaqscbjnNFNLllnjnnfdlLDDdeEDLHJJBBbfd`bcCK[SCGGEGFFB@@HIIKCAIMM]UQAEMmikKJHXxzz{{kcCAackjzZ[[{sqq

Try it online!

I/O is done by character (actually byte) code, because Incident is a horrible low-level tarpit with no numeric I/O routines. The program can handle numbers greater than 255 by using multiple characters (enter the number you want in little-endian base 256).

Explanation

In Incident, the tokens are not fixed by the language but rather defined by the program – any substring of the program that appears exactly 3 times is a token, unless it's contained within another token or overlaps another token. Additionally, the actual bytes that make up a token don't matter – just how the copies of the tokens are arranged relative to the other tokens.

In this program, I picked single-byte tokens to implement the program, choosing the bytes that represent them in order to get an approximate "only one bit changes from one byte to the next" property, and added extra bytes (that appear more or fewer than 3 times) as comments in order to make the property perfect. Thus, every occurrence of a byte in ]eimQSUxXZ fNs cCn is a comment, because it appears 1, 2, or 4 times respectively. (I had to double one of the ns to "detokenise" n; other padding characters added to maintain the one-bit-at-a-time property naturally ended up being used 1, 2 or 4 times.) The actual choice of bytes to represent the tokens, and positions of the padding bytes, was mostly done via a computer search (and the algorithm wasn't optimal, so this is probably golfable, but I haven't found anything better so far).

Removing the comments gives us the following 72-byte program, whose token arrangement was chosen by hand:

@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq

Incident programs are generally very hard to explain, so I'm going to attempt to explain this one by highlighting subsets of characters and explaining what they do. I think I've covered the whole program here, but in a program as unreadable as this one (and which was partially computer-generated, so I didn't entirely write it myself), it's quite possible that I've missed something.

Starting the program, and the first two bits of input

@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
@     b               HJJBBb  b         @@H          k  Hzz{{k  k

Incident reads standard input a bit at a time (which is the only reason why writing this program is remotely viable in Incident – it's normally a horrible language for just about anything). If the three uses of a token are split as a lone token and a touching pair (e.g. @@@), that represents a jump from the single token to the double token, so the program starts by jumping from the @ at the start to @@.

To do input (the usual way, at least), the program must run into the middle of the three occurrences of a token, without ever hitting the first or last use. H here therefore reads the first bit (the least significant bit of the input number), and jumps to the first or last H accordingly.

In either case, we then cross over a couple of jump labels (JJBB or zz{{). For a backwards jump (which all of JBz{ are), it's safe to do this; control just moves past the jump label, like you'd expect for a jump label. (This is not safe for a forwards jump – you're encountering the middle of three uses without ever hitting the first or last, which is interpreted as an attempt to read input rather than an attempt to move past a jump label.)

This part of the program finishes by reading the second bit of input, using b or k based on whether the first bit read was a 0 or a 1 bit. Control flow is thus sent to one of four locations, based on the two most recent bits read.

Output subroutines

@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
      bj                      bK                     kK         kj
       j  lljdl                                                  j
                               K           IIKAI      K
             d  DDdED       d                 A MMAEM         A
         L     L   E L           GGEG              E

The outer uses (first and last) of any given token are basically subroutine calls, with the middle use being the entry and exit point from the subroutine (i.e. running the first or last token will jump to the middle, and then returning to the middle will return to just after the token you called it from).

We want to output 0 if we read two 0s or two 1s. We want to output 1 if we read 01 or 10. Output in Incident is done by calling a subroutine using the token that's the centremost token in the entire program (which for this program is E; the L token is dead code, with none of its uses ever reached, and it exists only to push the centre of the program over an E); its left call point outputs a 0 bit as a side effect, and its right call point outputs a 1 bit as a side effect. So we have a d subroutine that outputs 0 bits, and an A subroutine that outputs 1 bits, both via calling E. Because subroutines have their entry and exit points in the same place, we wrap each of them in a backwards jump to allow control flow to return to the point from which they were called.

Each Incident subroutine must be called from exactly 2 points in the program, but we have three locations that want to output 0 bits (and three locations that want to output 1 bits). The usual way to fix this is with helper/wrapper subroutines that contain nothing but a call to another subroutine, here j and K; j outputs 0 bits by calling d, and K outputs 1 bits by calling A. These wrapper subroutines use up one of the call points of the subroutine they're calling, but provide two (an increase of one call point), so this technique makes it possible to call d and A from three points each.

In order to convert regular little-endian binary to Gray code, we basically need to output, for each bit, the XOR of that bit with the previous bit. The program has jumped to one of four locations based on whether the two bits we just read are 00, 01, 10, or 11; and each of these locations immediately calls an output subroutine to output 0, 1, 1, or 0 respectively.

Moving from one bit to the next

@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
       jF                BBb         FFB
                               K[                          {{k     [[{
                       JJ  b                          KJ
                                                         zz  k   jz

After we've produced our output, we need to move onto the next bit. The output of the binary-to-Gray conversion only ever depends on the most recent two bits, so we effectively just need to jump to the same location that the H which reads the first bit does – after producing output after a 0 bit, we need to jump to the b that handled input after a 0 bit is read, and after producing output after a 1 bit, we need to jump to the k that handled input after a 1 bit is read.

This is almost very straightforward, just using jumps to return to the relevant part of the program. After reading 10 or 11, we can do exactly that (using J and z respectively as the jump labels) – those are backward jumps, so control flow can safely pass over their jump labels. After reading 00 or 01, though, we would need to jump forward in the program rather than backward jumps, and control flow can't pass over a forward jump label safely. So instead, we need to jump forwards to an arbitrary point in the code, and then backwards to the point we actually need, allowing the two control flows to merge safely. This is done with F then B after reading 00, and [ then { after reading 01.

This handles most of the program – the situation we're in after reading, say, 1110 is identical to the situation we're in after reading 10, except that we've output two bits already (but there's no need to remember which two bits they were, because those never become relevant later).

Ending the program

@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
 ``                        bd`
   aa                                                        kAa
     q                                                                qq

Eventually, we reach the end of the input, causing an end-of-file condition. Incident handles end of file by not jumping at all – it just falls through from the input instruction to the next instruction. To convert binary to Gray codes, we need to handle this by outputting a copy of the most recently input bit (because the most significant bit of the input is output directly in addition to being XORed with the bit below), then quitting the program.

If the most recently read bit was a 0 bit, so we're using b to read input, then we fall through to d (which outputs 0 bits), then use ` to jump back to the start of the program. Likewise, if we read a 1 bit and thus used k to read input, we fall through to A to output a 1 bit and a to jump back to the start of the program. In either case, q jumps to the end of the program and exits.

This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). You could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. However, it would make the program as a whole longer, because the centre of the program would be in the wrong place, and you'd need much more padding to push it over an E in order to do output properly.

\$\endgroup\$
1
  • \$\begingroup\$ High effort answers indeed! \$\endgroup\$
    – Jonah
    Jun 20 at 13:00
10
\$\begingroup\$

05AB1E, 11 bytes

;3ss{Ƶ}]\\^

Try it online or verify all test cases.

The core program without the would have been 2 bytes:

;^

Try it online or verify all test cases.

Explanation:

Explanation of the core program:

;    # Halve the (implicit) input
 ^   # Implicitly truncate it to an integer, and bitwise-XOR it with the
     # (implicit) input
     # (after which the result is output implicitly)

The idea is to add no-ops between them without changing the functionality. I started by creating a generator to get all 05AB1E character-pairs that differ by a single bit. Before the ^, only \ and V seemed reasonable candidates (\ discards the top of the stack; and V pops the top of the stack and saves it in variable Y). From there it was kinda trial-and-error to see what characters I could use. Because the ; and ^ differ by 4 bits, at least that many no-op bytes in between are necessary. Although I have the feeling the byte-count can still be improved perhaps, 9 no-op bytes to toggle 4 specific bits isn't too bad I guess.

Explanation of the new program:

;           # Halve the (implicit) input-integer
            # No-ops:
 3          #  Push 3
  s         #  Swap the two values on the stack
   s        #  Swap them back
    {       #  Sort the digit(s) of 3
     Ƶ}     #  Push compressed integer 226
       ]    #  Close all open if-statements and loops
        \   #  Discard the top of the stack (the 226)
         \  #  Discard the top again (the 3)
          ^ # Implicitly truncate the halved input to an integer, and bitwise-XOR
            # it with the (implicit) input
            # (after which the result is output implicitly)

(See this 05AB1E tip (section How to compress large integers?) to understand why Ƶ} is 226.)

The bytes in 05AB1E's codepage of ;3ss{Ƶ}]\\^ are:

;  00111011
       v
3  00110011
    v
s  01110011
s  01110011
       v
{  01111011
        v
Ƶ  01111111
         v
}  01111101
     v
]  01011101
          v
\  01011100
\  01011100
         v
^  01011110
\$\endgroup\$
7
\$\begingroup\$

Jelly, 4 bytes

HL\^

A monadic Link that accepts an integer and yields a list of one integer. ...Or a full program that accepts an integer and prints the result.

The code's bytes only change by one bit each time, as required:

Byte Hex Binary
H 48 01001000
L 4C 01001100
\ 5C 01011100
^ 5E 01011110

Try it online!

How?

The shortest code that starts with H (halve) and ends with ^ (XOR the input) for which the code in between has no adverse effect while fulfilling the source-code restriction of only changing by at most one bit from byte to byte.

HL\^ - Link: integer, N
H    - halve N                    -> N/2
  \  - cumulative reduce with:
 L   -   length                   -> [N/2]
   ^ - (floor to integer) XOR (N) -> [floor(N/2) XOR N]

Note

:2 (integer divide by two) seems like a reasonable start as the bytes already only differ by one bit, but the next available bytes (Ø"036:rḶ) don't really help us advance.

\$\endgroup\$
6
\$\begingroup\$

Brainfuck, 425 421 bytes

-4 bytes thanks to @Jiří

,()9;{[YIMm-/?>?;+*:>?;+*(8<<=}]_^~>?;{[YIMm-/?>>?;+*(8<<=?;{[YIMm-/?>>?=-/?>?;+*(8<=}]_^~>>?;{[YIMm-/?>>>>?;+*(8<<=}]}|<<<<=}]_^~>>>?;{[YIMm-=<<<=?;+*:>>>?=}]}|>>>?;{[YIMm-=}]}|<<<<<<<=-/?;{[[Z^~>>>>>>?;{[Z^~>>>?=}]_OKk++;{[YIMm-=<<<=}]}|<<<=-=}]_^~>?=}]_^~>>>?;{[ZXx|<=}]_^~>?;{[[Z^~>?;{[Z^~>?=-=<=-=}]_^~>?;{[ZXx|<<<<<<=?;+*:>>>>>>?;{[YIMm-=}]]_^~>?=}]_OKk+;{[ZXx|<=?;{[ZXx|<<<=?;++*:>>>?=-=}]}|<<=}]_^~>>?=}]}|<<<=?/.

Attempt This Online!

Thanks to this answer for the XOR algorithm and to this answer for the division by 2.

Expanded code:

,

duplicate the input in two cells
[->+>+<<]

>

divide n by two
    [ 0 
        -
        >>+ set marker 2
        << 0
        [->>->+<] dec marker inc n/2
        >> 2 or 4
        [->>>>+<<] 
        <<<<
    ]
    >>>
    [-<<<+>>>]
    

set temp cell to zero
>>>[-]

<<<<<<<

xor
-[[>>>>>>[>>>]++[-<<<]<<<-]>]>>>[<]>[[>[>-<-]>[<<<<<<+>>>>>>[-]]>]+[<[<<<++>>>-]<<]>>]

<<<.

The code has been made safe with this program. I invite anyone who's better at golfing in Brainkfuck than me to use it to make shorter solutions!

\$\endgroup\$
1
  • \$\begingroup\$ You have <<>> in your code, so you can golf it down by 4 bytes. \$\endgroup\$
    – Jiří
    Jun 20 at 21:49

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.