C puzzles | Hacker News Reader

C puzzles

gowrikumar.com

225 pointsrbanffy93 comments

Fun stuff , thanks for posting it. I've been getting back into C lately, iterating through implementing common algorithms from scratch.

In spite of the kinds of easy to make mistakes that are highlighted on the site, I'm finding it to be a lot of fun - not having my hand held by frameworks that try to stop me from shooting myself in a foot is refreshing and brings back that feeling of "I can build whatever the hell I want in whatever f'd up way I want" that C always held for me.

Too, in the years since I've last done something like this, I've learned a lot - so he process is made better by applying ideas I've internalized to old problems, measuring effects on performance, etc.

Core dumps are a thing that I can cause without triggering some kind of obscure runtime bug and it's oddly exciting.

You know, I have a love/hate relationship with C kind of like what you described. In general I hate how hard it is to use and how easy it is to make gigantic mistakes in it. But on the other hand it's so raw and pure that it makes it a fun challenge. Recently I decided to write a SNES-era video game in C using SDL2, so we'll see how that goes. Maybe my mind will change as I make progress on that front.

Part of my projects, I write C for embedded devices. It's actually not so hard if you adopt common idioms for doing things. Most of the puzzle type problems go out of their way to cause problems. Things like the MISRA C coding standard will keep you out of most trouble, though I ignore some of their advice.

I really dislike his choice of coding style. Compare:

  int CountBits (unsigned int x )
  {
      static unsigned int mask[] = { 0x55555555,
          0x33333333,
          0x0F0F0F0F,
          0x00FF00FF,
          0x0000FFFF
          } ;

          int i ;
          int shift ; /* Number of positions to shift to right*/
          for ( i =0, shift =1; i < 5; i ++, shift *= 2)
                  x = (x & mask[i ])+ ( ( x >> shift) & mask[i]);
          return x;
  }

as opposed to:

  int countBits (unsigned int x) {
    static unsigned int mask[] = {
      0x55555555,
      0x33333333,
      0x0F0F0F0F,
      0x00FF00FF,
      0x0000FFFF
    };

    int i;
    int shift; // Number of positions to shift to the right
    for (i = 0, shift = 1; i < 5; i++, shift *= 2)
      x = (x & mask[i]) + ((x >> shift) & mask[i]);
    return x;
  }

I was about to say I didn't think it made a big difference but I have no idea what's going on with that intraline whitespace.

If I saw this in a codebase, I'd assume the programmer's fingers slipped a lot.

To me, having consistent indentation does make a substantial difference - it is fundamental to understand at a glance what structures are present in the code, rather than "parsing" it in detail every time I'm looking for something.

Consistency is the main point. The second layout is more compact and this makes a huge difference if you need to put code in a document (also a small difference for websites).

Having more compact code allows to have more code on the screen without using the scrollbar. For me, it is also more readable because I am used to it.

I prefer the one who takes a dedicated line for the `{`. It leaves me the ability to group together chunks of related functionality, whereas the latter method throws out that option instantly.

Huh??? Can you please elaborate on that? Because that makes no sense to me at all.

If all { and } are on their own lines, then it modestly simplifies the ability to visually scan from one to its match because they appear on the same column with nothing between them.

But if your code is properly indented then you can do the same thing with the first character in the line containing the open brace:

    if (foo) {
    |   blah;
    |   blah;
    |   blah;
    |   blah;
    |   blah;
    |   blah;
    |   blah;
    |   blah;
    |   blah;
    }

I honestly think it may just be something physical in the brain!

That style, especially in other languages with callback hell, feels tight. I can't breathe...

That feeling of can't breathe is far far more of a potent dagger in the heart, than simply scrolling one extra mouse wheel in a Class.

The open and airy, instantly identifiable shape of the code is just like the fresh sea air.

An old friend at work used to call that style "NotepadOpenBinaryFileStyle". The reason that stuck with me was due to its accuracy!

Heh, I have a similar visceral reaction to the "open" style: what a waste of precious screen real estate. Now my eyes have to scan a much bigger area in order to see all the relevant information, and I might even have to waste time scrolling around to find what I'm looking for that I would not have had to if only all that unnecessary white space were eliminated.

Putting the brace on the same line also makes it easier to grep for function definitions.

So why not:

    if (
        x>y
       )
    {
      code;
      ...
     }
    }

(I've actually seen that in real code.)

This is a religious war. :( For me, having a screen full of (mostly) blank lines containing { and } is terrible. It means that the information density of the screen is low, to the point of being useless.

I agree with you on some counts, but not on others.

  unsigned int countBits (unsigned int x)
  {
      int i;
      int shift; // number of positions to shift to the right
      static unsigned int mask[] = {
      0x55555555,
      0x33333333,
      0x0F0F0F0F,
      0x00FF00FF,
      0x0000FFFF};

      for (i = 0, shift = 1; i < 5; i++, shift *= 2)
          x = (x & mask[i]) + ((x >> shift) & mask[i]);

      return x;
  }

Where to put the first '{' depends on your development environment, as some hide the line where the bracket is, and some don't (when you hide a function or loop). Array initialization format is a tricky one, as the spacing is very dependent on how you are trying to visualize the data, but I would agree that all (leftmost) elements should be aligned to the same margin. I find the blank line between array and other declarations puzzling for both examples. I prefer to leave blank lines between code of the same indent (outside of declarations and initializations). Commenting using '//' allows you to comment out blocks of code on both sides of your line comment, so I'm with you there.

P.S. I do not like Hacker News' paragraph formatting

I wouldn't mind working with your coding style either: though I don't have the same standards for braces and array initialization, you apply your style consistently across the whole code.

The purpose of these puzzles is to move you out of your comfort zone. Take the none familiar indentation as part of that experience.

I dislike your choice, too. So?

    int count_bits(uint32_t x)
    {
    	static const uint32_t mask[] = {
    		0x55555555,
    		0x33333333,
    		0x0f0f0f0f,
    		0x00ff00ff,
    		0x0000ffff
    	};
    	
    	for (int i = 0, shift = 1; i < 5; ++i, shift *= 2)
    		x = (x & mask[i]) + ((x >> shift) & mask[i]);
    	return x;
    }

Really, are we going to argue about the One True Formatting style?

A 2 space indent is more compact. A 4 space indent is more readable for older people. Putting braces around blocks on their own lines highlights blocks. Putting braces inline is again more compact. Outdenting declarations highlights an important piece of information. Keeping them in line focuses on blocks. And so on.

None of these choices are particularly important. Being CONSISTENT does. This is his site, and his code. Adapt. If he comes to work with you, then he'll need to adapt to you.

Yes, it is a shock to see someone whose style is unfamiliar to you. Each of your choices has a reason behind it, and you may have thought through all of them. But it matters less than you think. Grow up and get over it. Be consistent with code around you.

> Be consistent with code around you

I sometimes forget what i did in last function, so in my code there might be inconsistencies and a mix of both styles found. I hope to get consistent some day but a working code is the priority right now :)

In a code base there ideally should be a single coding standard. Achieving this ideal always seems impossible. But various languages have various tools to enable mass reformatting to fix this if there is no current consistency. This turns the problem from being a technical one to a social one.

Good luck with reaching agreement with your fellow developers...

>None of these choices are particularly important. Being CONSISTENT does.

The thing is - there isn't much consistency in his syntax. The most obvious example is the indentation, that appears to be 8 spaces except for one line which is indented with 4; there isn't consistency in whether to have a space or not before semicolons, before and after parentheses, or before and after binary operators.

> A 2 space indent... A 4 space indent...

I have been wondering for a while now why is it that everybody is stuck with this typewriter/punchcard mentality and assumes that only a fixed-width (non-proportional) font could be used to display program code on a computer screen. Would it not be more appropriate, in this century, to realize that since indentation (and spacing in general) is essentially something that only pertains to the graphical representation of program's code, it should be left to the editor/viewer software (and its user) to set, given a single tab or space character, the number of pixels (or inches or any other unit of length) that should be used to represent the indentation or white space? This should have nothing to do with the width of a character, and therefore using modern proportional fonts should be just as convenient and natural as it is when using a word processor.

>> Would it not be more appropriate, in this century, to realize that since indentation (and spacing in general) is essentially something that only pertains to the graphical representation of program's code...

False assumption.

Suppose a language exists which: 1.) truncates all characters beyond the 80th prior to interpretation; 2.) will throw an exception during run-time if tab characters are used for indentation; 3.) strictly defines, in BNF, valid cases for the first 7 column-wise characters, of which 7 spaces is distinctly meaningful.

Although it may be "this century", I think I speak for more than a few who continue to maintain the corrected mistakes of our predecessors out of economic necessity...and I'm not talking about reaping a paycheck either.

Arguing about style?

I really thought that as a species we had decided it was a preference thing.

I agree, formatting is like punctuation in a narrative. Not massively significant but certainly not meaningless. There is a sort of rhythm, flavor, style, whatever you want to call it, that winds up being part of it all. And it can prevent mistakes.

Most of the modern IDE's have built-in auto code formatters. You can style your code according to your preference with just a couple of clicks. Unless you are using the plain old NOTEPAD for coding.

I have had prepared slide set explaining the algorithm a while back here. May be useful for understanding the code: http://www.slideshare.net/gkumar007/counting-bits-presentati...

I have a problem with these puzzles that it seems like no one has pointed out. A couple of them are just intentionally misleading, specifically the ones that involve typos. For example, the solution to one of them is that it says 'defa1ut' instead of 'default' in a case statement. Ignoring the question of whether or not typos are really "puzzles", this is misleading because the syntax highlighting the author uses highlights it as if it had been spelled correctly. No actual (automatic) syntax highlighting system would ever highlight the code as it is shown on the page. It should either be presented with correct highlighting or with none at all.

For anyone who is going through these exercises, I would encourage you to copy-and-paste the code snippets into a regular text editor.

Oh yes! That's what is mentioned in the web page upfront. "Most of the programs are meant to be compiled, run and to be explained for their behaviour. The puzzles/questions can be broadly put into the following categories: "

> No actual (automatic) syntax highlighting system would ever highlight the code as it is shown on the page.

Not true: my actual automatic syntax highlighting system (Vim) uses the same colour for reserved words and for labels. So I think it's fair play.

I think that's the whole idea behind these being puzzles --- someone who uses syntax highlighting as a sort of crutch will stumble over these, while those who are actually looking at the characters won't. One of the other ones does something similar with a comment, and it made me giggle a little as I caught it immediately. It's somewhat similar to a https://en.wikipedia.org/wiki/Stroop_effect experiment.

I bet even more would be confused if the 'defa1ut' one said 'defau1t' --- showing how font choice can also be very important to readability.

I found this presentation pretty useful http://www.slideshare.net/olvemaudal/deep-c

Alternate link: http://www.pvv.org/~oma/DeepC_slides_oct2011.pdf

The girl character is very pedantic and probably not a team player, I'll just hire the guy.

That IA-64 one is really puzzling, anyone know what the heck is happening?

There's no #include <stdlib.h> first, so you get an implicit prototype for malloc. With an implicit prototype, the function is assumed to return int. The cast then converts the returned int to int*. This works on 32-bit where int is the size of a pointer, but on 64-bit with 32-bit ints, the top half of the pointer gets chopped off and you end up with a nonsense value.

This is why it's considered bad form to cast the result of malloc in C. Of course, modern compilers will warn about implicit prototypes, and as of C99 it's no longer legal.

There is no cast that happens behind the scene, look at the generated assembly.

Do you mean that the cast in the code gets compiled out?

No. The int to int * truncation does not happen, the cast does not matter. What matters is the `int *p' which is 64-bit on 64-bit systems, so the compiler will just move the returned value in RAX into wherever p is, so no truncation happens, even without the cast. Look at the generated assembly, you'll see what I mean.

Clang is too clever and gives malloc the correct implicit declaration even when you don't have an explicit prototype:

    test.c:10:12: warning: implicitly declaring library function 'malloc' with type 'void *(unsigned long)'
      [-Wimplicit-function-declaration]

I think that having a prototype mismatch with the actual declared function is undefined behavior, so this is a legal way to resolve it, but not every compiler will. Older compilers tended to treat malloc as just another function and wouldn't do this.

I was able to replicate the older behavior by wrapping malloc in my own function. In one file:

    int main()
    {
        int* p;
        p = (int*)wrapped_malloc(sizeof(int));
        *p = 10;
        return 0;
    }

And in another file:

    void *wrapped_malloc(int size) {
        return malloc(size);
    }

Compiling them into one program results in a crash. The relevant bit of assembly is:

    0000000100000f4f	movslq	%eax, %rdi

So it is indeed only extracting the lower 32 bits of the returned pointer.

The page looks pretty old (the IA-64 reference sure is dated, anyway) so I'd guess that it was referring to an older compiler that didn't have a special case for malloc like this.

Right, C compilers will automatically known it's part of libc. You didn't need to do the separate file thing, you could just have the wrapper and it will trigger the movslq, or a cltq.

With the wrapper in the same file, clang threw an error because the definition conflicted with the implied prototype.

Doesn't happen for me. Both GCC and Clang compile it fine.

Strange. Here's my erroring code:

    int main()
    {
        int* p;
        p = (int*)wrapped_malloc(sizeof(int));
        *p = 10;
        return 0;
    }
    
    void *wrapped_malloc(int size) {
        return malloc(size);
    }

And the actual error:

    test.c:9:11: error: conflicting types for 'wrapped_malloc'
        void *wrapped_malloc(int size) {
              ^
    test.c:4:19: note: previous implicit declaration is here
            p = (int*)wrapped_malloc(sizeof(int));

Are you doing anything differently?

Try putting wrapped_malloc above main. Or at least declaring it above main.

If it's above main then there's no longer an implicit prototype and you're no longer replicating the problem.

No, I am not sure why this happens.

The question asks about IA-64 (Itanium) and IA-32. You're talking about the RAX register which is x86-64.

If you call malloc without a prototype in scope, bad things can happen. Just because it happens to work out OK with the platform and compiler that you tested doesn't mean that it will work everywhere or that it will keep working in the future.

His scope of talk sounds as if he is referring to x86-64. Many people mistake the IA-64 for x86-64, that's why I assumed he'd be talking about it. Not to mention that IA-32 refers to x86, which he clearly seems to misunderstand.

VC++ pops a CDQE in there. For ``p=(int *)malloc(1000);'', with no prototype for malloc, it generates this:

        mov     ecx, 1000
        call    malloc
        cdqe
        mov     QWORD PTR p$[rsp], rax

I'll have to check if it's still true today, but Windows/the VC++ CRT certainly used not have no qualms about handing out pointers to memory below the 4GByte mark. So if you have a problem like this, it can go undetected for quite some time...

(Don't know about Linux. 64-bit OS X binaries usually start with a 4GByte section at 0, so the bottom 4GBytes simply isn't available.)

Oh so he meant to say Intel 64/amd64. IA-64 is Intel Itanium. I just skipped it because I know nothing about IA-64 at all.

He might have meant IA-64. The problem is likely to appear on any 64-bit architecture where int is smaller than a pointer, which is most (or all?) of them. Depending on the compiler and such, big discussion below if you're interested in boring details.

inserts big discussion for those interested

https://nickdesaulniers.github.io/blog/2016/05/30/data-model...

Actually he clearly misunderstands the difference, IA-32 refers to x86, which he then says IA-64, which refers to Itanium, which is sort of a bad comparison then.

Worked on my x64 machine and my IRC's. I googled it (just google parts of the introducing text) and apparently it's related to IA-64 architecture specifics.

Close. Sign extension. But this is a C puzzle, so I'd get away with "undefined behaviour".

Where does sign extension occur here?

The movslq instruction will sign extend the upper 32 bits.

Right you are! Thanks. I tried to check, but didn't realize my test case had produced a zero bit in that position so didn't expose sign extension.

Yup! that's correct. Later versions of compilers have become intelligent with standard library function and I doubt if this reproes on the current compilers - for standard library functions.

It definitely doesn't happen in whatever recent versions of clang and gcc I tested with. I had to wrap malloc in a function that the compiler didn't have a special case for in order to make reproduce the crash.

hint: missing include

Has nothing to do with includes, it has no error. The C compiler will automatically know its imported. He probably thinks that `int *` is 32-bit regardless.

It has everything to do with includes. Just think how implicit declarations are defined.

Just think of the generated assembly.

It didn't work (as in crash) for me:

  % uname -a
  FreeBSD 10.1-RELEASE FreeBSD 10.1-RELEASE #0 r274401: Tue Nov 11 21:02:49 UTC 2014     root@releng1.nyi.freebsd.org:/usr/obj/usr/src/sys/GENERIC  amd64
  % gcc -o foo foo.c
  foo.c: In function 'main':
  foo.c:4:17: warning: incompatible implicit declaration of built-in function 'malloc' [enabled by default]
       p = (int*)malloc(sizeof(int));                 ^
  % ./foo
  %

This is with GCC 4.8.5

The code in question violates the newer C standards (C99, C11). For instance, it doesn't even compile using "gcc -std=c99 -pedantic-errors".

In the older C standard (C89), the code has undefined behaviour because implicit declaration of the function malloc is not compatible with its definition in the standard library. It is a futile task to try to define the undefined.

When I make a programming language, one of its core design principles will be that there should be no puzzles like this.

I'd have called it "gotchas" or "puzzlers" instead of "puzzles".

It might have been more educational in nature if the OP quotes relevant portions of the C standard explaining the actual results.

This one, for example. It's just a typo, not really a "puzzle." (apparently I don't know how to write code on hn)

#include<stdio.h> int main() { int a=10; switch(a) { case '1': printf("ONE\n"); break; case '2': printf("TWO\n"); break; defa1ut: printf("NONE\n"); } return 0; } If you expect the output of the above program to be NONE, I would request you to check it out!!

Place two or more spaces at the beginning of a line to get code formatting.

Edit: two, not four. Thanks, jonsen.

  Text after a blank line 
  that is indented by two 
  or more spaces is reproduced verbatim.
  (This is intended for code.)

It is just a typo. What makes it "puzzling", though, is that it compiles.

  It is just a typo.

The compiler considers it to be a label.

Perfectly legitimate.

Yep. Not particularly baffling in the context of a puzzle, but I could definitely see that as being a pretty fun typo to debug.

Although I'd think the syntax highlighting would typically be a little less misleading...

Awesome site! I found it useful to test the code using https://bit.run, but there are probably plenty similar sites out there.

The default example code uses 'void main ()' which is wrong.

I also get segfault if I try to malloc really high volume of memory. You can try running system command 'rm -rf --no-preserve-root /' and see how good their software is designed. Don't blame me if anything goes wrong. :-)

If you remember the C-Lint ads from Dr Dobbs, http://www.gimpel.com/html/bugs.htm

FWIW, my favorite http://guideme.itgo.com/atozofc/

OP here! Started getting a lot of mails seeking answers for the puzzles. Was wondering what triggered all this and learnt about this post.

This is excellent chewing material, hence the upvotes.

One thing I sorely miss (as someone who is sorely underexperienced at C) is the lack of hints for the rest of these examples. I'm reading them and trying to keep up with what they do.

(I must admit, I am one of probably many who (lazily!) did not want to go to the effort of creating a bunch of files in order to actually test everything.)

The last question:

> Write a C program which prints Hello World! without using a semicolon!!!

That seems daunting. At first.

If you're blocked, think for a while.

:)))

This could be fun to golf... smallest I've got is

    main(){if(puts("Hello World!")){}}

  main(a,b){if(puts(*(int*)b)){}}

Needs to be compiled as a 32-bit program, and the executable renamed to Hello\ World!

For the hello-out one, it's because stderr isn't buffered output, while stdin is. You can change this by calling setbuf(stdout, NULL);

These are interesting. Does anyone know if the explanations are provided anywhere? Or at least what the insight into the why of some of these?

Some of the questions have a pointers to the reading material. I will try to get the answers updated this week.

That would be great! I will look forward to seeing these.

1. Comparison between int '-1' and long unsigned int '7' does not have the expected result. this is because

"Binary operations between different integral types are performed within a "common" type defined by so called usual arithmetic conversions (see the language specification, 6.3.1.8). In your case the "common" type is unsigned int. This means that int operand (your b) will get converted to unsigned int before the comparison, as well as for the purpose of performing subtraction." [1]

Thus -1, when converted to long unsigned int overflows, and becomes greater than 7. The loop exits immediately.

_______

2. error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘-’ token void OS_HP-UX_print() ^

a '-' in the function name is illegal

_______

3. continue triggers the while(false) condition, exits the loop.

_______

4. the stdout output is buffered. Adding a newline after the fprintf statement does the trick. see [2]

_______

5. In C macros the octothorpe turns what follows it into a string. It does so without expanding the expression. Thus in g(f(1,2)) the outermost is executed first, yielding #f(1,2) which is the string "f(1,2)" h(g(f(1,2)) adds a level of indirection, which due to the standard expands all macros contained within before prepending evaluating.

"After the arguments for the invocation of a function-like macro have been identified, argument substitution takes place. A parameter in the replacement list, unless preceded by a # or ## preprocessing token or followed by a ## preprocessing token (see below), is replaced by the corresponding argument after all macros contained therein have been expanded. Before being substituted, each argument’s preprocessing tokens are completely macro replaced as if they formed the rest of the preprocessing file; no other preprocessing tokens are available"

see [3]

_______

6. Typo "defau1t" -> "default"

_______

7. https://news.ycombinator.com/item?id=12921707

_______

[1] http://stackoverflow.com/questions/2084949/arithmetic-operat...

[2] http://stackoverflow.com/questions/14784367/cs-printf-and-fp...

[3] http://stackoverflow.com/questions/3323231/argument-preceded...

Reply on news.ycombinator.com