Stack Overflow: Printing 1 to 1000 in C | Hacker News Reader

Stack Overflow: Printing 1 to 1000 in C

stackoverflow.com

284 pointsnumeromancer97 comments

Open articleView on HN

... without conditionals.

Cute puzzle, nice to see some inventive torturing of C, and various dialects that people believe are C.

and various dialects that people believe are C.

To be fair, the SO question specifies "using C or C++", not just C.

True. At a glance I'm suspicious that some might truly be in neither, but I'm not really bothered to check.

Any Language Lawyers around?

Without specifying dialect (ANSI C, C99, etc.), I believe "valid C" really only means "some C compiler somewhere will accept it without generating errors".

Someone claims the second answer "obviously" isn't C, which I don't understand. GCC 4.5.2 compiles it without complaint.

Is pointer arithmetic not allowed? Or calling main()?

I'm not sure pointer arithmetic on function pointers is standard C. Using the -pedantic flag, gcc 4.5.2 does give a "warning: pointer to a function used in subtraction".

The paragraph on pointer differences (ANSI C99 6.5.6§9) states that : "both shall point to elements of the same array object, or one past the last element of the array object […] The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t".

So, for an array of function pointer that would be legal behaviour, but for pointers to plain functions, it is undefined behaviour.

When I was in high school I thought I could implement shared libraries for DOS/DJGPP by subtracting function pointers to each function I wanted to export and dumping the intervening data to disk. I quickly realized that the code was not position independent, and that other segments (like strings) were not being exported. I also discovered Linux, and thus abandoned the idea.

It has to do with getting an int from pointer arithmetic on function pointers. IIRC, there's no guarantee that a function pointer will even fit in any specific kind of int. On this computer, sizeof(&main) is 8, sizeof(int) is 4.

Function pointers are all kinds of iffy - you can't translate them to void *, for instance (this makes total sense if you consider the fact that C programs may run on embedded devices with separate RAM/ROM addressing schemes). I'm not sure about arithmetic, but I'd expect it to be undefined.

If you do want to put a (non-function) pointer into an integer, convert to (C99) [u]intptr_t. Of course, that does not have to be defined...

Really? I didn't know that. Shows how much I have still to learn about C.

A program I'm writing now uses void* as a generic function pointer, which I cast to different function signatures as required depending on usage. I'm guessing that's considered harmful, is there a better or more idiomatic way to do this?

I believe there is not a standard way to do what you are doing. However, in common implementations of C, you'll only have trouble if some of your functions have a different calling convention than others — stdcall, say, or fastcall, or Pascal calling convention, or far vs. near calls on 16-bit x86. I assume you can avoid that with a union with one member for each calling convention, but I've never tried it.

Architectures where code pointers are bigger than data pointers are fairly exotic, I think. The AS/400 might be an example, I'm not sure. However! You can avoid that particular problem by using (void* )(void) as your generic function pointer type, rather than simply void *.

Pretty much the only standard way to do this involves something like "void (fp)(void arg)" or "void (*fp)(va_list ap)" and generous casting.

That said, this is not that likely to be a problem in practice on Unix machines (Windows has more than one calling convention - I have no idea how much of a problem that is.)

It's guaranteed that function pointers survive a round-trip conversion to other function pointer types - so you can just use a type like `void (*fp)()` as a "generic" container, making sure that it's cast back to the correct type before use.

I was about to point out that pointers are supposed to fit in intptr_t, but you're right -- there probably isn't a specification for function pointers (it's too late for me to feel like checking the spec). I will add, though, that on Linux on common 32- and 64-bit CPUs an unsigned long will always fit a pointer (excluding the possibility that ucLinux has been ported to a Harvard architecture or other "non-traditional" machine).

Subtracting function pointers doesn't have to have any meaning.

Tiny C (from 2006, 5 years old) gives:

   function pointer expected

MS C 6 (from 1998, 13 years old) gives

   error C2296: '-' : illegal, left operand has type 'void (__cdecl *)(int )'

Turbo C 2.01 (from 1988, 23 years old) gives:

   Size of structure or array not known in function

etc.

I think the really clean solution (as far as I know, at least it works with all the compilers I've mentioned) is:

http://news.ycombinator.com/item?id=2323771

Anything that has 'void main' isn't quite up to snuff, to begin with.

"nice to see some inventive torturing of C"

What ever happened to the IOCCC? (International Obfuscated C Coding Contest, ioccc.org)

My favorite response:

The real answer is "don't work there".

>> The real answer is "don't work there

, if you have to ask this question ;-)"

A comment on the question says: "Why do interview questions always want you to write code that you shouldn't realistically write in application?"

To prepare you for the code they shouldn't realistically have in production. Oh.

Previously posted and discussed: http://news.ycombinator.com/item?id=2062058

how about a simple implementation in Forth?

  : o         dup . cr 1+               ;
  : t         o o o o o  o o o o o      ;
  : h         t t t t t  t t t t t      ;
  : thousand  h h h h h  h h h h h drop ;

  1 thousand

one of the c solutions took that approach [http://stackoverflow.com/questions/4568645/printing-1-to-100...]

Unsurprisingly, its author worked at Forth, Inc., long ago.

The original question is unclear. What is a 'loop' and what is a 'conditional'?

Tail-recursive calls (like the linked solution uses, though C compilers usually do not implement 'proper' tail calls) or short-cut conditionals might not look like but are still loops or conditionals.

So, why the answer is funny it does not answer the original question.

though C compilers usually do not implement 'proper' tail calls

With optimizations turned on, gcc turns a tail recursive function into the equivalent of a for loop.

.. which I've lately found out the hard way: Code of mine randomly crashed and valgrind told me it's due to use of unintiliazed memory. An awful lot of time later (i.e. one valgrind --track-origins=yes run) I know that it's from function foo's stack space. Which contains one local variable which is clearly assigned at the beginning. _Much_ later I find out that the problem is in bar, tail-called by foo.

At least now I know that latest gcc can do tail-call optimizations.

  #include <stdio.h>
  #define print printf("%d\n", n++);
  #define times2(x) x x
  #define times5(x) x x x x x
  #define pow3(x,f) x(x(x(f)))
  
  int main() {
    int n = 1;
  
    pow3(times2, pow3(times5, print));
    
    return 0;
  }

How would you do the same in other languages? It would be interesting to see the same question answered in Python, Perl, Java, etc. etc. Just as a fun thought exercise, and not to get into language flamewars.

1.upto 1000 {|n| puts n} # ruby ftw

Isn't "upto" a loop? The idea, IIRC, is to print the numbers without loops and conditionals.

1.upto(10).class => Enumerator

That's like doing:

  #define NOT_A_LOOP(x) while(x)

Enumerator is just Ruby object goo over a loop.

More like:

#include someone_else_did_it_so_we_dont_know(x)

Just as those other answers in C relied on GOTOs somewhere.

It "can be" implemented recursively. If you're going to be pedantic about this (and who doesn't love being pedantic?) you need to be very careful about your definitions, because regardless of what you write you're going to have jump instructions in the finally-executed machine code. If you say that you can't have a loop "anywhere", you're limited to recursion, and then what will you do when someone comes along and points out that recursion and looping are ultimately equivalent? This is one of those cases where examining the boundary too closely makes it dissolve under the scrutiny, and it's better just to smile and nod and play along (and have fun arguing).

puts ((1..1000).to_a.join("\n"))

Which, of course, is passing the buck to Range#to_a

1+!1000

No stinking loops!

1 + til 1000 No stinking distinction between monadic/dyadic usage of array operators!

Here's a solution in Python, using pretty much the same logic as the top vote-getter on Stack Overflow:

    def f(a):
        print a
        print a+1
        {999: int}.get(a,f)(a+2)

    f(1)

Note, I had to count by twos, because when I counted by ones, I got a "maximum recursion limit exceeded" error.

Basically, the concept is to call f recursively, until you get to 999 (and had printed 999 and 1000), at which time you call some non-recursive function (I call "int").

At 999, the inner-called f function terminates, leading to the unwinding of the stack (each previous f function terminating), and then the program ends.

This statement is the hard one to understand:

        {999: int}.get(a,f)(a+2)

Basically, it's saying "Look up 'a' in this hard-coded dictionary that only has one value in it - for 999. If 'a' isn't found (as it won't be most of the time), set the look-up value to the function called 'f'. Otherwise, set the look-up value to the function called 'int'. In either case, call that looked-up value, passing the parameter of a+2."

Does this fit the criteria for python:

    print str(range(1,1001)).strip('[]').replace(', ','\n')

Edit: added missing [ as pointed out below

no! For one thing, it still prints out an opening '[' before 1. Second of all, relying on the structure of the string representation of an array is just silly. Perhaps:

    print "\n".join(map(str, range(1,1001)))

    print "\n".join(str(i) for i in range(1,1001))

Heh, I forgot about join but that for is still a loop right? :)

Or else you could just:

    for i in range(1,1000):
        print i

Plus relying on the string representation of a list isn't silly it as it doesn't change. I just didn't know if range would meet the criteria or not.

Will this count for solution? :)

    MAX = 1000

    def execute_if_not_equals(value, other, &block)
      noop = lambda {}
      [block, noop][value / other].call
    end

    def print(i)
      execute_if_not_equals(i, MAX) do
        puts(i + 1)
        print(i + 1)
      end
    end

    print(0)

[edit]: updated to not use != operator which is probably a cheat.

An Erlang solution:

    f() -> f(1).
    f(1001) -> ok;
    f(N) -> io:fwrite("~p~n", [N]), f(N + 1).

How about this Python solution:

    z="0123456789"
    print map(lambda x:int("".join(x))+1,zip(sorted(zip(*z)[0]*100),
              sorted(zip(*z)[0]*10)*10,
              zip(*z)[0]*100))

Only downside is that it prints as a list (so it has the format of [1,2,3..])

  ('\n').join(map(str, [1,2,3]))

Even better Python variation: Prints 1 to 1000 and quits:

    from __future__ import print_function 
    z="0123456789"
    map(print,map(lambda x: int("".join(x))+1,zip(sorted(z*100),
                      sorted(z*10)*10, z*100)))

The way it works is to create 3 strings, one for each digit-place. The first digit, when counting from 000 to 999, is 100 zeros, followed by 100 ones, followed by 100 twos, etc. That is represented by

    sorted(z*100)

The middle digit is 10 zeros, 10 ones, etc... and repeat this 10 times. So this is

    sorted(z*10)*10.

The least significant digit is represented by a string that just counts and starts over. it's 1000 characters long: "0123456789012345..." and represented by

    z*100.

I define an unnamed function (using lambda), that does the following: Join the three digits, make it an int, and add 1. So the result of this is a list of numbers from 1 to 1000. In other words,

    map(lambda x:  int("".join(x))+1,zip(sorted(z*100),
                              sorted(z*10)*10, z*100)))

is about the same as if I just used range(1,1001)

Then I map it to the new print function that is available in Python 3.0, or with the import statement.

A simpler version would use range, but that seems a little too simple:

    from __future__ import print_function 
    map(print,range(1,1000))

Now that I think about it, this last one is the right answer!

Haskell:

    mapM_ (putStrLn . show) [1..1000]

actually, can be done more simply as:

mapM_ print [1..1000]

but yeah, ...haskell +1 for that :D

Clojure: (map println (range 1 1001))

Is there a better way than this for scheme (racket)?

  (map (lambda (n)
       (displayln n))
     (cdr (build-list 1001 values)))

http://pleac.sourceforge.net/ - Perl cookbook examples translated to other languages, and links to similar translation challenges.

For this specific task, I think the shortest Perl, as I've mentioned in http://news.ycombinator.com/item?id=2326372 is just

   $,="\n"; print 1..1000

Javascript, validity depends on how exactly do you define conditions and loops:

  var items = [];
  var rec = function(item) {
      var func = [];
      func[true] = function(item) { items.push(item); [item-1].map(rec); };
      func[false] = function(item) {};
      return func[Boolean(item)](item);
  };
  var item = [1000];
  item.map(rec);
  console.log(items.reverse().join(','));

Won't do in browsers due to recurssion limit but change [1000] to [10] and you'll see it works.

Wow, HN must have a pretty large readership. Note that before this got posted on HN today my SO score from the solution was pretty static, for weeks. All of a sudden it's sprung up 300 points.

If I learned one thing from the experience it is that often the popularity of something is not a measure of how "correct" it is. It's often a measure of the compromises you are prepared to make, and also how "appealing" it is.

FWIW, thanks HN. I actually read about the question right here in the first place!

By the way, the "correct" version was added by someone else. Posts to whoever added it.

Just because I haven't seen it mentioned yet, here's a solution using gcc's computed goto feature:

  #include <cstdio>
  int main(int argc, char** argv) {
    void* labels[2] = { &&doing, &&done };
    int i = 1;
  doing:
    printf("%d\n", i++);
    goto *labels[i / 1001];
  done:
    return 0;
  }

Still consider goto harmful? (Well yeah, so do I generally. But hey...)

I just learned a little more about C thanks to this. Compiling does cause a warning, though:

gcc printy.c printy.c: In function ‘main’: printy.c:4: warning: return type of ‘main’ is not ‘int’

It's an abuse of the standard (c90 and c99). main is supposed to return int and take either no arg or two args, but I think a lot of legacy code violates this, so most compilers let you off with a warning. That said, "-Wall -Werror" are two useful things to always add to your gcc invokation.

It's things like this which convince me that I am never going to pass an interview at a decent tech place. When I attempt to write solutions to things like this I make a million mistakes and can never quite get there.

My idea was to create a buffer of 1000 bytes and recursively call a function while each byte is dereferenced until it finally hits a byte which causes a segfault... but I just can't get it working.

The function pointer solution is genius...

I'd say:

#include<stdio.h>

void output(x) { int y; printf("%i\n", x); y = 1 / (1000 - x); output(x + 1); }

int main() { output(1); }

With gcc on Linux it has the added bonus of "Floating Point Exception", don't know if that disqualifies it.

EDIT: Nevermind, I got it:

#include<stdio.h>

int output(x) { printf("%i\n", x); (x >= 1000 ) || output(x + 1); return 1; }

int main() { output(1); }

My favorite is: system("/usr/bin/seq 1000");

Only thing is, the interviewer would ask, "How would this work in Windows?"

>the interviewer would ask, "How would this work in Windows?"

Cygwin?

//https://gist.github.com/870150

(function(max){ new Array(max + 1).join(' ').replace(/\s/g, function(c, i){ console.log(i + 1); }) })(1000)

Well, what do you think about

int main(void) { printf(" 1 2 3 4 5 6 7 8"); return 0; }

I bet that 1000 was in binary and he was obviously checking the guy's CQ ( compSci Quotient)

Obvious, but passing arguments to this will cause it to break.

One other mod: (j/1000) could be replaced with (j>999) which is still non conditional, but faster.

Well, just move the logic into its own function.

        #include <stdio.h>
        #include <stdlib.h>

        void pr(int j) {
                printf("%d\n", j);
                (pr + (exit - pr)*(j/1000))(j+1);
        }

        int main(int argc, char** argv) {
                pr(1);
                return 0;
        }

I like it this way, it compiles on the compilers where the parent's doesn't (see http://news.ycombinator.com/item?id=2323964), I believe it fits to all standards, doesn't depend on any undefined behavior, it doesn't assume any convenient type size, it doesn't call exit, it doesn't crash and also it doesn't use any relational operators. It even uses only two arithmetic operators, and only on integers.

    #include <stdio.h>
    #include <stdlib.h>

    int pk( int i )
    {
        static int (*v[])( int ) = { pk, abs };
        printf( "%d\n", i );
        return v[ i/1000 ]( i+1 );
    }

    int main( void )
    {
        pk( 1 );
        return 0;
    }

And interestingly enough Perl version can be almost the same, only without declarations:

  use POSIX;

  sub pk
  {
    print "$_[0]\n";
    return ( \&pk, \&fabs )[ $_[0] / 1000 ]( $_[0] + 1 );
  }

  pk( 1 );

FWIW, there's no need to use a library.

    perl -e '($pk=sub { print "$_[0]\n"; ($pk, sub{}) [$_[0]/1000] ($_[0]+1) }) -> (1)'

Thanks. Of course (just for the readers who don't know) even much shorter Perl doesn't have "loops" (in C sense) fits the requirements and works:

  $,="\n"; print 1..1000

I don't know if it can be made shorter. My previous example was (also for the readers who don't know that) to demonstrate the "C inspired" features in Perl and almost 1-1 mapping to the C solution, minus declarations.

printf("1 To 1000");

Writing "a + condition * (b - a)" is just a math cheat to make a ternary operator. So isn't this a conditional itself?

printf("1 10 11 100 101 110 111 1000");

Using the preprocessor

http://pastebin.com/Gxia1aBV

Nice. Linear interpolation of C functions.

Bad HN title.

printf "numbers from 1 to 1000 without using any loop or conditional statements. Don't just write the printf() or cout statement 1000 times.\n How would you do that using C or C++?"

too lazy to write it, but you could easily write a ruby script which writes a C program to a file. The ruby script loops to 1000. the C program is around 1000 lines long, prints one number per line. the ruby script compiles and runs the c script. problem solved?

This might be from some clever and lazy programmer.. lol

291 printf("numbers from 1 to 1000");jondavidjohn Dec 31 '10 at 7:07

Too bad the site is currently too slow for me to close as "not a real question".

It was tried when it was new[1].

To me, abuse of vote to close is up there with deletionism on Wikipedia as making no sense, particularly in this case.

[1]: http://stackoverflow.com/posts/4568645/revisions

Deletion-ism makes perfect sense, it maintains a high signal to noise ratio.

My problem with this is that filters (e.g. search, tagging, ranking) give the same result without destroying information which is not, strictly speaking, noise.

No they don't, noise drowns out signal, see Google's problem with spam and splogs.

more like a high ratio of one person's preferred signal to other signals

By that metric, spam is signal because some people (spammers) want it.

They don't want it, they want people to see it.

Few people would have problems with the deletion of true "noise" -- obnoxious and indecipherable solve-my-homework questions or obvious trolls.

But why delete a programming-related question with lots of healthy discussion and where people are enjoying themselves? Or, for that matter, a wikipedia page that is well-written and accurate, but only of interest to a small percent of people?

Not at all! It's fine to have an article on a topic that is only of interest to a small percentage of people, as long as those people have high edit counts on wikipedia.

Reply on news.ycombinator.com