Task: Print numbers from 1 to 1000 without using any loop or conditional statements. Don't just write the printf()
or cout
statement 1000 times.
How would you do that using C or C++?
#include <stdio.h>
typedef void (*fp) (int);
void stop(int i)
{
printf("\n");
}
void next(int i);
fp options[2] = { next, stop };
void next(int i)
{
printf("%d ", i);
options[i/1000](++i);
}
int main(void)
{
next(1);
return 0;
}
Using pointer arithmetic we can use automatic array initialization to 0 to our advantage.
#include <stdio.h>
void func();
typedef void (*fpa)();
fpa fparray[1002] = { 0 };
int x = 1;
void func() {
printf("%i\n", x++);
((long)fparray[x] + &func)();
}
void end() { return; }
int main() {
fparray[1001] = (fpa)(&end - &func);
func();
return 0;
}
For C++ lovers
int main() {
std::stringstream iss;
iss << std::bitset<32>(0x12345678);
std::copy(std::istream_iterator< std::bitset<4> >(iss),
std::istream_iterator< std::bitset<4> >(),
std::ostream_iterator< std::bitset<4> >(std::cout, "\n"));
}
template <int To, int From = 1>
struct printer {
static void print() {
cout << From << endl;
printer<To, From + 1>::print();
}
};
template <int Done>
struct printer<Done, Done> {
static void print() {
cout << Done << endl;
}
};
int main()
{
printer<1000>::print();
}
Preprocessor abuse!
#include <stdio.h>
void p(int x) { printf("%d\n", x); }
#define P5(x) p(x); p(x+1); p(x+2); p(x+3); p(x+4);
#define P25(x) P5(x) P5(x+5) P5(x+10) P5(x+15) P5(x+20)
#define P125(x) P25(x) P25(x+50) P25(x+75) P25(x+100)
#define P500(x) P125(x) P125(x+125) P125(x+250) P125(x+375)
int main(void)
{
P500(1) P500(501)
return 0;
}
The preprocessed program (see it with gcc -E input.c
) is amusing.
Nobody said it shouldn't segfault afterwards, right?
Note: this works correctly on my 64-bit Mac OS X system. For other systems, you will need to change the args to setrlimit and the size of spacechew accordingly. ;-)
(I shouldn't need to include this, but just in case: this is clearly not an example of good programming practice. It does, however, have the advantage that it makes use of the name of this site.)
#include <sys/resource.h>
#include <stdio.h>
void recurse(int n)
{
printf("%d\n", n);
recurse(n + 1);
}
int main()
{
struct rlimit rlp;
char spacechew[4200];
getrlimit(RLIMIT_STACK, &rlp);
rlp.rlim_cur = rlp.rlim_max = 40960;
setrlimit(RLIMIT_STACK, &rlp);
recurse(1);
return 0; /* optimistically */
}
This only uses O(log N) stack and uses McCarthy evaluation http://en.wikipedia.org/wiki/Short-circuit_evaluation as its recursion condition.
#include <stdio.h>
int printN(int n) {
printf("%d\n", n);
return 1;
}
int print_range(int low, int high) {
return ((low+1==high) && (printN(low)) ||
(print_range(low,(low+high)/2) && print_range((low+high)/2, high)));
}
int main() {
print_range(1,1001);
}
OpenMP version (non-ordered of course):
#include <iostream>
#include <omp.h>
int main(int argc, char** argv)
{
#pragma omp parallel num_threads(1000)
{
#pragma omp critical
{
std::cout << omp_get_thread_num() << std::endl;
}
}
return 0;
}
(Does not work with VS2010 OpenMP runtime (restricted to 64 threads), works however on linux with, e.g., the Intel compiler)
Here's an ordered version too:
#include <stdio.h>
#include <omp.h>
int main(int argc, char *argv[])
{
int i = 1;
#pragma omp parallel num_threads(1000)
#pragma omp critical
printf("%d ", i++);
return 0;
}
A C++ variant of the accepted answer from the supposed duplicate:
void print(vector<int> &v, int ind)
{
v.at(ind);
std::cout << ++ind << std::endl;
try
{
print(v, ind);
}
catch(std::out_of_range &e)
{
}
}
int main()
{
vector<int> v(1000);
print(v, 0);
}
I've reformulated the great routine proposed by Bill to make it more universal:
void printMe ()
{
int i = 1;
startPrintMe:
printf ("%d\n", i);
void *labelPtr = &&startPrintMe + (&&exitPrintMe - &&startPrintMe) * (i++ / 1000);
goto *labelPtr;
exitPrintMe:
}
UPDATE: The second approach needs 2 functions:
void exitMe(){}
void printMe ()
{
static int i = 1; // or 1001
i = i * !!(1001 - i) + !(1001 - i); // makes function reusable
printf ("%d\n", i);
(typeof(void (*)())[]){printMe, exitMe} [!(1000-i++)](); // :)
}
For both cases you can initiate printing by simply calling
printMe();
Has been tested for GCC 4.2.
template <int remaining>
void print(int v) {
printf("%d\n", v);
print<remaining-1>(v+1);
}
template <>
void print<0>(int v) {
}
print<1000>(1);
With macros!
#include<stdio.h>
#define x001(a) a
#define x002(a) x001(a);x001(a)
#define x004(a) x002(a);x002(a)
#define x008(a) x004(a);x004(a)
#define x010(a) x008(a);x008(a)
#define x020(a) x010(a);x010(a)
#define x040(a) x020(a);x020(a)
#define x080(a) x040(a);x040(a)
#define x100(a) x080(a);x080(a)
#define x200(a) x100(a);x100(a)
#define x3e8(a) x200(a);x100(a);x080(a);x040(a);x020(a);x008(a)
int main(int argc, char **argv)
{
int i = 0;
x3e8(printf("%d\n", ++i));
return 0;
}
x001(a)
is a macro that performs the given action once. x002(a)
performs x001(a)
twice, so it performs the action twice. x004(a)
performs x002(a)
twice, so it performs the given action 4 times. Things go on doubling until we define x3e8(a)
, which performs the action 1000 times (3e8 in hex). The action given is printf("%d\n", ++i)
, which increments i and then prints it. So when we pass it to x3e8()
, since macros aren't pass-by-value (unlike functions, which are), the action is repeated 1000 times, printing all the numbers from 1 to 1000.
#include<stdio.h>
int b=1;
int printS(){
printf("%d\n",b);
b++;
(1001-b) && printS();
}
int main(){printS();}
#include <stdio.h> int main(int argc, char **argv) { char oh_god_no[50]; if(atoi(argv[1])==1000) return 0; sprintf(oh_god_no,"python -c \"import os; print %d; os.system('./a.out %d\')\"",atoi(argv[1])+1,atoi(argv[1])+1); system(oh_god_no); }
It's also possible to do it with plain dynamic dispatch (works in Java too):
#include<iostream>
using namespace std;
class U {
public:
virtual U* a(U* x) = 0;
virtual void p(int i) = 0;
static U* t(U* x) { return x->a(x->a(x->a(x))); }
};
class S : public U {
public:
U* h;
S(U* h) : h(h) {}
virtual U* a(U* x) { return new S(new S(new S(h->a(x)))); }
virtual void p(int i) { cout << i << endl; h->p(i+1); }
};
class Z : public U {
public:
virtual U* a(U* x) { return x; }
virtual void p(int i) {}
};
int main(int argc, char** argv) {
U::t(U::t(U::t(new S(new Z()))))->p(1);
}
You can do it pretty simply using recursion and a forced error...
Also, pardon my horridly sloppy c++ code.
void print_number(uint number)
{
try
{
print_number(number-1);
}
catch(int e) {}
printf("%d", number+1);
}
void main()
{
print_number(1001);
}
How about another abnormal termination example. This time adjust stack size to run out at 1000 recursions.
int main(int c, char **v)
{
static cnt=0;
char fill[12524];
printf("%d\n", cnt++);
main(c,v);
}
On my machine it prints 1 to 1000
995
996
997
998
999
1000
Segmentation fault (core dumped)
Inspired by Orion_G's answer and reddit discussion; uses function pointers and binary arithmetic:
#include <stdio.h>
#define b10 1023
#define b3 7
typedef void (*fp) (int,int);
int i = 0;
void print(int a, int b) { printf("%d\n",++i); }
void kick(int a, int b) { return; }
void rec(int,int);
fp r1[] = {print, rec} ,r2[] = {kick, rec};
void rec(int a, int b) {
(r1[(b>>1)&1])(b10,b>>1);
(r2[(a>>1)&1])(a>>1,b);
}
int main() {
rec(b10,b3);
return 1;
}
Using macro compaction:
#include <stdio.h>
#define a printf("%d ",++i);
#define b a a a a a
#define c b b b b b
#define d c c c c c
#define e d d d d
int main ( void ) {
int i = 0;
e e
return 0;
}
Or still better:
#include <stdio.h>
#define a printf("%d ",++i);
#define r(x) x x x x x
#define b r(r(r(a a a a)))
int main ( void ) {
int i = 0;
b b
return 0;
}
manglesky's solution is great, but not obfuscated enough. :-) So:
#include <stdio.h>
#define TEN(S) S S S S S S S S S S
int main() { int i = 1; TEN(TEN(TEN(printf("%d\n", i++);))) return 0; }
After some tinkering I came up with this:
template<int n>
class Printer
{
public:
Printer()
{
std::cout << (n + 1) << std::endl;
mNextPrinter.reset(new NextPrinter);
}
private:
typedef Printer<n + 1> NextPrinter;
std::auto_ptr<NextPrinter> mNextPrinter;
};
template<>
class Printer<1000>
{
};
int main()
{
Printer<0> p;
return 0;
}
Later @ybungalobill's submission inspired me to this much simpler version:
struct NumberPrinter
{
NumberPrinter()
{
static int fNumber = 1;
std::cout << fNumber++ << std::endl;
}
};
int main()
{
NumberPrinter n[1000];
return 0;
}
My little contribution to this fabulous set of answers (it returns zero) :
#include <stdio.h>
int main(int a)
{
return a ^ 1001 && printf("%d\n", main(a+1)) , a-1;
}
Comma operator is FTW \o/
EDIT 2:
I removed undefined behaviors from code. Thanks to @sehe for notice.
No loops, recursions, conditionals and everything standard C ... (qsort abuse):
#include <stdio.h>
#include <stdlib.h>
int numbers[51] = {0};
int comp(const void * a, const void * b){
numbers[0]++;
printf("%i\n", numbers[0]);
return 0;
}
int main()
{
qsort(numbers+1,50,sizeof(int),comp);
comp(NULL, NULL);
return 0;
}
int numbers[0]
ok? I'd have expected that to be undefined behaviour in ++numbers[0]
? If you can explain why it should not be int numbers[1];
I'd be much obliged
++numbers[0]
is UB as well as sorting not existing 246 array elements with qsort is also UB. I just found empirically that when using int numbers[1]
and qsort(numbers+1,...
- output results in somewhat chaotic fashion.
Oct 27, 2011 at 18:10
int numbers[1]
and qsort(numbers+2
works i came with idea that somewhere in the sorting process memory at address one-past array is overwritten and thus using numbers[1]
and qsort(numbers+1)` or numbers[0]
and qsort(numbers+0)` results in incorrect list. This is my best guess.
Oct 27, 2011 at 18:45
reduced
the number of UB's by a negative amount. Cheers and thanks for explaining. I think (?) I sort of understand. (pun intended)
Don't know enough C(++) to write code, but you could use recursion instead of a loop. In order to avoid the condition you could use a datastructure which will throw an exception after the 1000th access. E.g. some kind of list with range checking where you increase/decrease the index on each recursion.
Judging from the comments there don't seem to be any rangechecking lists in C++?
Instead you could 1/n with n being a parameter to your recursive function, which gets reduced by 1 on each call. Start with 1000. The DivisionByZero Exception will stop your recursion
You don't really need anything more than basic string processing:
#include <iostream>
#include <algorithm>
std::string r(std::string s, char a, char b)
{
std::replace(s.begin(), s.end(), a, b);
return s;
}
int main()
{
std::string s0 = " abc\n";
std::string s1 = r(s0,'c','0')+r(s0,'c','1')+r(s0,'c','2')+r(s0,'c','3')+r(s0,'c','4')+r(s0,'c','5')+r(s0,'c','6')+r(s0,'c','7')+r(s0,'c','8')+r(s0,'c','9');
std::string s2 = r(s1,'b','0')+r(s1,'b','1')+r(s1,'b','2')+r(s1,'b','3')+r(s1,'b','4')+r(s1,'b','5')+r(s1,'b','6')+r(s1,'b','7')+r(s1,'b','8')+r(s1,'b','9');
std::string s3 = r(s2,'a','0')+r(s2,'a','1')+r(s2,'a','2')+r(s2,'a','3')+r(s2,'a','4')+r(s2,'a','5')+r(s2,'a','6')+r(s2,'a','7')+r(s2,'a','8')+r(s2,'a','9');
std::cout << r(r(s1,'a',' '),'b',' ').substr(s0.size())
<< r(s2,'a',' ').substr(s0.size()*10)
<< s3.substr(s0.size()*100)
<< "1000\n";
}
Neither loop nor conditional Statements and at least it doesn't crash on my machine :). Using with some pointer magic we have...
#include <stdlib.h>
#include <stdio.h>
typedef void (*fp) (void *, int );
void end(fp* v, int i){
printf("1000\n");
return;
}
void print(fp *v, int i)
{
printf("%d\n", 1000-i);
v[i-1] = (fp)print;
v[0] = (fp)end;
(v[i-1])(v, i-1);
}
int main(int argc, char *argv[])
{
fp v[1000];
print(v, 1000);
return 0;
}
I hate to break it, but recursion and looping are essentially the same thing at the machine level.
The difference is the use of a JMP/JCC versus a CALL instruction. Both of which have roughly the same cycle times and flush the instruction pipeline.
My favorite trick for recursion was to hand-code a PUSH of a return address and use JMP to a function. The function then behaves normally, and returns at the end, but to somewhere else. This is really useful for parsing faster because it reduces instruction pipeline flushes.
The Original Poster was probably going for either a complete unroll, which the template guys worked out; or page memory into the terminal, if you know exactly where the terminal text is stored. The latter requires alot of insight and is risky, but takes almost no computational power and the code is free of nastiness like 1000 printfs in succession.
#include <stdio.h>
#include <stdlib.h>
void print(int n)
{
int q;
printf("%d\n", n);
q = 1000 / (1000 - n);
print(n + 1);
}
int main(int argc, char *argv[])
{
print(1);
return EXIT_SUCCESS;
}
It will eventually stop :P
There are plenty of abnormal exits due to stack overflows so far, but no heap ones yet, so here's my contribution:
#include <cstdio>
#include <cstdlib>
#include <sys/mman.h>
#include <sys/signal.h>
#define PAGE_SIZE 4096
void print_and_set(int i, int* s)
{
*s = i;
printf("%d\n", i);
print_and_set(i + 1, s + 1);
}
void
sigsegv(int)
{
fflush(stdout); exit(0);
}
int
main(int argc, char** argv)
{
int* mem = reinterpret_cast<int*>
(reinterpret_cast<char*>(mmap(NULL, PAGE_SIZE * 2, PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, 0, 0)) +
PAGE_SIZE - 1000 * sizeof(int));
mprotect(mem + 1000, PAGE_SIZE, PROT_NONE);
signal(SIGSEGV, sigsegv);
print_and_set(1, mem);
}
Not very good practice, and no error checks (for obvious reasons) but I don't think that is the point of the question!
There are plenty of other abnormal termination options, of course, some of which are simpler: assert(), SIGFPE (I think someone did that one), and so on.
Should work on any machine that doesn't like 0 / 0. You could replace this with a null pointer reference if you need to. The program can fail after printing 1 to 1000, right?
#include <stdio.h>
void print_1000(int i);
void print_1000(int i) {
int j;
printf("%d\n", i);
j = 1000 - i;
j = j / j;
i++;
print_1000(i);
}
int main() {
print_1000(1);
}
Using recursion, conditionals can be substituted using function pointer arithmetic:
#include <stdio.h>
#include <stdlib.h> // for: void exit(int CODE)
// function pointer
typedef void (*fptr)(int);
void next(int n)
{
printf("%d\n", n);
// pointer to next function to call
fptr fp = (fptr)(((n != 0) * (unsigned int) next) +
((n == 0) * (unsigned int) exit));
// decrement and call either ``next'' or ``exit''
fp(n-1);
}
int main()
{
next(1000);
}
Note that there are no conditionals; n!=0
and n==0
are branchless operations. (Though, we perform a branch in the tail call).
printf
and print two numbers each time, no?:?
isn't a conditional statement (it's an expression)...