C puzzles

http://www.gowrikumar.com/c/index.php

by rbanffy • 10 years ago

225 93 10 years ago

gowrikumar.com

sitkack• 10 years ago

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

CapacitorSet4• 10 years ago

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

zerocrates• 10 years ago

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.

Cyph0n• 10 years ago

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

CapacitorSet4• 10 years ago

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.

Fifer822• 10 years ago

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.

lisper3• 10 years ago

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

adekok• 10 years ago

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.

nickff• 10 years ago

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

CapacitorSet4• 10 years ago

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.

babo• 10 years ago

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

exprF2• 10 years ago

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

btilly2• 10 years ago

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.

mkagenius• 10 years ago

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 :)

CapacitorSet4• 10 years ago

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.

Koshkin• 10 years ago

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.

mfukar2• 10 years ago

Arguing about style?

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

UhUhUhUh• 10 years ago

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.

rationalhero• 10 years ago

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.

gowrikumar5• 10 years ago

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...

GrinningFool• 10 years ago

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.

sdegutis• 10 years ago

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.

keithnz• 10 years ago

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.

adamnemecek• 10 years ago

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

0xmohit3• 10 years ago

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

swah• 10 years ago

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

0xmohit3• 10 years ago

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.

ohyoutravel• 10 years ago

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

mikeash11• 10 years ago

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

Edit: two, not four. Thanks, jonsen.

fisherjeff2• 10 years ago

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

hatsunearu2• 10 years ago

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

mikeash11• 10 years ago

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.

asamy4510• 10 years ago

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

innocenat• 10 years ago

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.

mfukar2• 10 years ago

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

gowrikumar5• 10 years ago

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.

bnmfsd• 10 years ago

hint: missing include

asamy4510• 10 years ago

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.

exprF2• 10 years ago

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

jandrese• 10 years ago

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

mnay• 10 years ago

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.

xigency• 10 years ago

The last question:

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

That seems daunting. At first.

colanderman• 10 years ago

If you're blocked, think for a while.

almata• 10 years ago

:)))

defgeneric• 10 years ago

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

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

chartreusek• 10 years ago

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

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

ptrkrlsrd• 10 years ago

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

pksadiq• 10 years ago

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. :-)

amptorn• 10 years ago

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

bogomipz2• 10 years ago

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?

gowrikumar5• 10 years ago

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

bogomipz2• 10 years ago

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

Orangeair• 10 years ago

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.

gowrikumar5• 10 years ago

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: "

wzdd• 10 years ago

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.

userbinator• 10 years ago

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.

chronolitus• 10 years ago

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...

gowrikumar5• 10 years ago

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

i336_• 10 years ago

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.)

_RPM• 10 years ago

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);

johnx123-up• 10 years ago

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

C puzzles

Related Stories