4
\$\begingroup\$

Codegolf the hamming code (with distance equals 3)!

The sequence looks like this: 0, 7, 25, 30, 42, 45, 51, 52, 75, 76, 82, 85, 97, 102, 120, 127, 385, 390, 408, 415, 427, 428, 434, 437, 458, 461, 467, 468, 480, 487, 505, 510, 642, 645, 667, 668, 680...

Task

Given n output the first n items in OEIS sequence A075926. Your program should work for any integer n where 0 <= n < 2^15. This sequence is known as the sequence of hamming codewords with distance being 3.

Rules:

  • Post both an ungolfed version of your code (or an explatation), and the golfed version, so that other people can understand how it works
  • If your program is written in a language with a compiler, specify which compiler and the compiler settings you used. Non-standard language features are allowed as long as it compiles with the compiler you specified, and the compiler was created prior to this question

Sequence Definition: Given a distance 3 hamming codeword k, the variants of k are k itself, and any nonnegative integer that can be produced by flipping one of k's bits. The nth hamming codeword is the smallest nonnegative integer that doesn't share a variant with any preceeding distance 3 hamming codeword. Here are the first twenty d-3 hamming codewords in binary:

0, 111, 11001, 11110, 101010, 101101, 110011, 110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111, 110000001, 110000110, 110011000, 110011111, 110101011

Ungolfed C++ code to produce sequence:

//Flips the nth bit
size_t flipN(size_t val, int bit) {
    return val ^ (1ull << bit);
}
void Hamming(size_t n) {
    int bits_to_use = 20;
    //This vector keeps track of which numbers are crossed off
    //As either hamming codewords or their variants.
    std::vector<bool> vect(1ull << bits_to_use, false);
    size_t pos = 0;
    size_t val = 0;
    while(val <= n) {
        //Checks to see that pos hasn't been crossed off
        if(vect[pos]) goto loopend;
        for(int i=0; i < bits_to_use; ++i)
        {
            if(vect[flipN(pos, i)]) goto loopend;
            //Checks to see that none of the variants
            //of pos have been crossed off
        }
        //If both those conditions are satisfied, output pos
        //As the next hamming codeword
        cout << pos << endl;
        //Here we cross off all the variants
        vect[pos] = true;
        for(int i=0; i < bits_to_use; ++i)
        {
            vect[flipN(pos, i)] = true;
        }
        ++val;
        loopend:
        ++pos;
    }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ No; they're very different sequences. The Hamming Numbers question is for oeis.org/A051037 \$\endgroup\$ – J. Antonio Perez Aug 18 '17 at 17:24
  • 5
    \$\begingroup\$ Am I the only on that doesn't understand the task? :P \$\endgroup\$ – Mr. Xcoder Aug 18 '17 at 17:32
  • 3
    \$\begingroup\$ @JorgePerez You should be able to explain this algorithm and give examples \$\endgroup\$ – J42161217 Aug 18 '17 at 17:36
  • 4
    \$\begingroup\$ The sequence is defined neither here nor on the OEIS page. \$\endgroup\$ – Leaky Nun Aug 18 '17 at 17:43
  • 2
    \$\begingroup\$ "Post both an ungolfed version of your code, and the golfed version, so that other people can understand how it works" What does ungolfed Pyth or Jelly look like? I suggest you ask for an explanation instead. :) \$\endgroup\$ – Stewie Griffin Aug 18 '17 at 17:50
2
\$\begingroup\$

Pyth, 34 21 19 bytes

Special Thanks to @LeakyNun for golfing off half of my solution!

u+Gf.Am<2sjxdT2G0QY

Try it here or Check out the test Suite.


Alternative, 19-byte solutions (Try one here):

u+Gf-Zm<2sjxdT2GZQY
u+Gf-0m<2sjxdT2G0QY
u+Gf.Am<2sjxdT2GZQY
\$\endgroup\$
  • \$\begingroup\$ 21 bytes \$\endgroup\$ – Leaky Nun Aug 18 '17 at 18:18
  • \$\begingroup\$ 19 bytes \$\endgroup\$ – Leaky Nun Aug 18 '17 at 18:20
  • \$\begingroup\$ @LeakyNun Thanks again, editing \$\endgroup\$ – Mr. Xcoder Aug 18 '17 at 18:21
2
\$\begingroup\$

Python 2, 98 97 bytes

-1 byte thanks to Mr. Xcoder

x=input()
l=[]
i=0
while len(l)<x:s=any(bin(i^n).count('1')<3for n in l);i+=s;l+=[i]*-~-s
print l

Try it online!

Straightforward implementation, using xor to calculate the hamming distance.
The inner loop is equivalent to :

if any(bin(i^n).count('1')<3 for n in l):
   i+=1
else:
   l.append(i)
\$\endgroup\$
  • \$\begingroup\$ (1-s) is -~-s (97 bytes) \$\endgroup\$ – Mr. Xcoder Aug 18 '17 at 17:53

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.