Printing 1 to 1000 without loop or conditionals | Hacker News Reader

Printing 1 to 1000 without loop or conditionals

stackoverflow.com

80 pointssolipsist51 comments

I think the whole approach with print5, print25 is the "correct" solution, but if I were interviewing I would give the best score to the person that gave system("/usr/bin/seq 1000"); as the answer.

The idea of building up by having something that prints 5, and then using that to build a print 25, and so on, is good.

That then inspires another question: given a function, foo(), that we wish to call exactly 1000 times, what is the way to do it in the least amount of code given that we are only allowed the following:

1. calling foo().

2. defining new functions, whose bodies consist entirely of calls to previously defined functions or to foo.

3. calling those new functions.

For computing amount of code, let's take it as 1 line per function call, and 1 line per function defined.

So, for example (in pseudocode):

    function foo_50
        foo
        foo
        ...
        foo

    foo_50
    foo_50
    ...
    foo_50

where there are 50 foo's in foo_50, and 20 calls to foo_50, would be a program of length 71. Breaking it down by powers of two:

    function foo_2
      foo
      foo

    function foo_4
      foo_2
      foo_2

    ...

    function foo_512
      foo_256
      foo_256

    foo_512
    foo_256
    foo_128
    foo_64
    foo_32
    foo_8

would have length 33.

Is that the best we can do? How about for a general N? How about writing a program that given N writes the optimal program in the above form for N?

I think the final output of a simple solution to your last question can always be just four lines.

    def bar(baz):
        baz()
        baz()

    bar(bar(bar(bar(foo)))) and bar(bar(foo)) and foo()

for N=21, for example. Actually, you can make it two lines if your goal is really to minimize LOC:

    def bar(baz): baz() and baz()

    bar(bar(bar(bar(foo)))) and bar(bar(foo)) and foo()

Whoops, `baz() and baz()` actually doesn't work, because foo may not return a truthy value (and bar definitely doesn't). One fix, which actually makes it even shorter, is just `baz(), baz()`.

Same goes for `bar(bar(...)) and bar()`; all the `and`s should be commands instead in my solution above. Of course, this is Python-specific.

s/commands/commas/g

This reminds me a bit of generating constants in BF: http://esolangs.org/wiki/Brainfuck_constants

I wouldn't as that's clearly not a C or C++ solution but a Unix one.

Since these questions always seem to be "Demonstrate you can cheat creatively, but in a way I approve of", I have to throw out "Print out the first 1,000 terms from a properly seeded random number generator. Discovery of the seed is a more interesting question, though fairly straightforward."

Doesn't that involve just as much looping as any other solution?

See, the trick is that while you don't approve, some others do.

They would? I don't follow. A random number generator only gives you one number at a time. The problem is still 'print X sequence without loops'. No answer has been given here, so there's no meaningful approval to be had.

It's not that using a random number generator is a cheat, it's that it is a (pointless?) lateral move rather than a solution.

You print the first 1000 terms. No loop was mentioned.

That's the cheat. You don't approve. Others might.

How do you print multiple terms out of a random number generator without a loop? That's my point. You haven't solved anything, cheat or not.

Recursion, compile-time code generation, templates, dispatching.

Pick whatever you like most.

I'm reminded of a scene from the movie Tin Cup. Kevin Costner challenges Don Johnson by saying something lime "have you ever won a tournament with just your 7 iron?"

Don replies with "why it never occurred to me to try".

This is exactly how I feel when I read something like this.

The ctor trick is genius. Compile-time loops (recursion counts as one) seems like a cheat. The dispatch table keyed on (i < 1000) is a straight-up cheat, as (obviously) is using the ternary or short-circuiting.

The task never said it had to stop at 1000.

    void f(int n){
       printf("%d\n",n);
       f(n+1);
    }

    int main(){
       f(1);
    }

Nor did it say all numbers from 1 to 1000:

  int main()
  {
    printf("13 47\n");
    return 0;
  }

My favorite uses a divide by zero to terminate an otherwise infinite recursion.

Actually the one that uses function pointers is by far the best, simplest way, and it doesn't segfault. Since x/1000 will always be floor(x/1000), once it reaches 1000 it calls nothing and exits cleanly.

This one (not mine):

    #include <stdio.h>

    void nothing(int);
    void next(int);
    void (*dispatch[2])(int) = {next, nothing};

    void nothing(int x) { }
    void next(int x)
    {
        printf("%i\n", x);
        dispatch[x/1000](x+1);
    }

    int main()
    {
        next(1);
        return 0;
    }

> The dispatch table keyed on (i < 1000) is a straight-up cheat

How so?

It's an if statement written differently.

If you want to get into language-lawyer mode, expressions are most certainly not conditional statements [in C]. But what's the use of arguing? "More gimmicky" answers don't count into solving a gimmicky problem? Who even keeps score?

edit: clarification, in true language-lawyer fashion.

The preprocessor hack does not compile to code that would decompile back to an if() statement. The i/1000 code does not compile to code that would decompile back to an if() statement. The ctor hack does not compile to code that would decompile back to a loop and an if statement. The i<1000 code, on the other hand, does compile down to code that decompiles back up to an if() statement; that's because it's just a compact way of writing an if() statement.

I'm not being a "language lawyer".

Well, neither C nor C++ are assembly, and vice versa. That's my usual response to this kind of "arguments", in every such question; boy do they come up a lot.

Regardless, I'll repeat it; maybe it'll stick this time:

  i < 0

is a conditional expression,

  if (i < 0) {}

is a conditional statement.

Also, while the above could be (mis)taken for C code;

  cmp eax, 0
  jl  foo

this one surely wouldn't.

And at this point I'll stop beating this particular horse.

How about if it was keyed on i/1000 instead of i<1000? Would that still be a hidden conditional?

No. Think about the generated assembly. One has a conditional branch, the other doesn't.

I strongly disagree on the ctor trick. While it's certainly ingenious, you're just reusing a loop, be it one implemented in the C++ runtime. It's little more than a glorified map.

I swear to god, I was tired of this argument before I even finished reading it. If you take your example to the extreme, you should consider that a processor also operates in a loop. Maybe every solution is a glorified series of iterations.

Nothing personal, but your argument is always used in these situations, for no good reason. Please learn where to draw the line.

> I swear to god, I was tired of this argument before I even finished reading it

I'm sorry if i tire you, but i think you misinterpreted what i said. Every solution will boil down to a loop, necessarily, so my point is it's useless to make distinctions like , "this solution is a bit cheating, but this one isn't". As long as it respects the requirements, eg no loop or conditional statements, it is no cheating.

> Nothing personal, but your argument is always used in these situations

I realize my original comment was oversimplifying things, but i fail to see which situations you are talking about. My argument, or what i originally wanted it to be, is that the line you draw between map and the constructor trick is extremely subjective. In such case, the only way to distinguish valid or invalid solutions is to refer to the original requirements.

> Please learn where to draw the line.

And please keep your condescending attitude to yourself. I perfectly know where to draw the line, and i still consider the limit tptacek made to be ridiculous. If you have any real argument to oppose me instead of sheer oversimplification and exaggeration, please proceed, but from what i see you just needed to vent, and in a rather unpleasant manner.

The way you phrased your original post gave me the impression you were dismissing the constructor solution for the same reason tptacek dismissed the rest. I certainly agree with your point, as you may have read elsewhere in the thread.

Other than that, I don't assume a patronizing attitude when I say that arbitrarily labeling solutions to such problems as "cheating" is an infuriatingly useless argument over semantics, and nothing more. Particularly so when such questions are used in the context of a job interview; how would you feel if an interviewer wrongly rejected your answer based on what he read on SO, and whose answer she trusted more?

PS. The situations I was referring to is the myriad of such questions on SO; a problem with absurd constraints imposed. They're fun, until 5 people come along and decide going around labeling answers as "cheating". The Stack Overflow meta site has quite a few comments on that phenomenon.

Okay well, so i feel like we're in a case of violent agreement, and it's probably my fault because i didn't take the time to write a proper comment in the first time.

My apologies.

Mine as well, I guess my comment was over the line.

I think the most interesting part is after the initial "this is dumb" and "don't work there" answers, it actually turned out to be a pretty interesting question.

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

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

Somehow the solutions that crash on exit are cheating too much. The above doesn't (obviously) compile to something which uses conditionals at the assembly level. This solution probably wouldn't be by the book. That takes a few more lines of code.

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

puts("10111000");

They are all in there, you just have to look a little.

To do it in base 10

  puts("1000200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900");

Holy crap, both those answers are genius.

My solution was:

#include <stdio.h>

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

int main(int argc,char argv) { return show(1); }

doesn't that violate the "w/o conditionals" part?

Technically, he's using relational operators if/else are conditionals that evaluate the boolean datatypes that result from the relational operation. Is it breaking the rule? Not really. Is it a loophole? Probably. The original question probably intended it to mean "no comparing" rather than "no conditional statements"

|| is conditional, not relational.

puts "numbers from 1 to 1000 without using any loop or conditional statements. Don't just write the printf() or cout statement 1000 times."

Like in eating without using your hands or mouth?

mapM_ print [1..1000]

Yay Haskell.

(Original question is for C/C++, so obviously this is a bogus answer.)

mapm_ is also looping construct.

'without using loops' is very ill defined. All solutions that in some way generate all integers up to a thousand need to include something we would, in English, refer to as 'a loop'. The ctor trick also contains 'a loop'. What solutions would you consider valid, without resulting in semantic squabbling over whether 'i < 1000' is a conditional or a condition and whether that matters?

Where's the loop in the array initialization? Where's the loop in "map"? That's why one's clever and the other's a cheat.

The loop in the array initialization is generated by the compiler for the static version, by the runtime for the dynamic allocation version. It's still a loop.

You're just re-using a loop already implemented in the runtime. That's quite the same thing as using map, though a tiny bit clever. But if you qualify map as cheat, well then the constructor trick is just a cleverer cheat.

Not entirely dissimilar in Ruby:

  p [*1..1000]

Or being anal about the formatting:

  puts [*1..1000].join ' '

Reply on news.ycombinator.com