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\$
9
  • 5
    \$\begingroup\$ No; they're very different sequences. The Hamming Numbers question is for oeis.org/A051037 \$\endgroup\$ Aug 18, 2017 at 17:24
  • 5
    \$\begingroup\$ Am I the only on that doesn't understand the task? :P \$\endgroup\$
    – Mr. Xcoder
    Aug 18, 2017 at 17:32
  • 3
    \$\begingroup\$ @JorgePerez You should be able to explain this algorithm and give examples \$\endgroup\$
    – ZaMoC
    Aug 18, 2017 at 17:36
  • 4
    \$\begingroup\$ The sequence is defined neither here nor on the OEIS page. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2017 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\$ Aug 18, 2017 at 17:50

2 Answers 2

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\$
3
  • \$\begingroup\$ 21 bytes \$\endgroup\$
    – Leaky Nun
    Aug 18, 2017 at 18:18
  • \$\begingroup\$ 19 bytes \$\endgroup\$
    – Leaky Nun
    Aug 18, 2017 at 18:20
  • \$\begingroup\$ @LeakyNun Thanks again, editing \$\endgroup\$
    – Mr. Xcoder
    Aug 18, 2017 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\$
1
  • \$\begingroup\$ (1-s) is -~-s (97 bytes) \$\endgroup\$
    – Mr. Xcoder
    Aug 18, 2017 at 17:53

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .