wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> 1 TO 100 and 100 to 1
        
(Message started by: raghuram on Jan 11^th, 2004, 9:39am)

Title: 1 TO 100 and 100 to 1
Post by raghuram on Jan 11^th, 2004, 9:39am

Try this:

Write a C++ program to print numbers from 1 to 100 and then 100 to 1 without using using loops, conditions like "if","else" etc.

Remember that recursion is not a solution since we would be using 'if'.

Title: Re: 1 TO 100 and 100 to 1
Post by towr on Jan 11^th, 2004, 10:29am

heh.. well..
I'll keep it short, just fill in the blanks yourself ;)

cout << 1 << 2 << 3 .... << 99 << 100
<< 100 << 99 << .... << 3 << 2 << 1 ;

You could also do something recursive, without if's by using the preprocessor, and templates..
(I'd have to brush up on that material first though..)

Title: Re: 1 TO 100 and 100 to 1
Post by towr on Jan 11^th, 2004, 11:11am

Code:

#include <iostream>

template<int i>
class P
{
public:
P()
{
std::cout << i << std::endl;
P<i+1>();
std::cout << i << std::endl;
}
};

class P<100>
{
public:
P()
{
std::cout << 100 << std::endl;
std::cout << 100 << std::endl;
}
};

int main()
{
P<1>();
}

compile with the option -ftemplate-depth-100 if your template depth isn't default 100 or greater

I also tried with a function template, but for some reason it won't work. So function objects it is then..

Title: Re: 1 TO 100 and 100 to 1
Post by towr on Jan 11^th, 2004, 11:22am

I don't know why I make it so difficult for myself.. This is much easier..

Code:

int p(int i, int j)
{
std::cout << i << std::endl;
(i-j) && p(i+1,j);
std::cout << i << std::endl;
}

int main()
{
p(1,100);
}

Who needs IFs anyway..

Title: Re: 1 TO 100 and 100 to 1
Post by Dudidu on Jan 14^th, 2004, 12:44am

on 01/11/04 at 11:22:38, towr wrote:

Code:

int p(int i, int j)
{
std::cout << i << std::endl;
(i-j) && p(i+1,j);
std::cout << i << std::endl;
}

int main()
{
p(1,100);
}

towr, I don't see why this code even works ???:
What does this line ('(i-j) && p(i+1,j);') do? and why will the program stop when it reaches to 100 ?
Waiting for your reply...

Title: Re: 1 TO 100 and 100 to 1
Post by towr on Jan 14^th, 2004, 2:13am

C and C++ don't really distinguish between booleans and integers, and they are lazy evaluators.
So on encountering a logical AND they will evaluate the first argument, and if it is false than the whole expression must be false, regardless of the second argument. Which is why, being lazy, they don't evaluate it.
In the end A&&B is equivalent if(A) B;
I suppose I could have used an implication as well (!A || B) as there is no difference here unless you do anything with the return value

To be honest I'd expected the compiler to at least want the function to explicitly return some value. But probably there's an implicit one, whatever it is though, it too is irrelevant, since the value of the expression (i-j)&&p(i+1,j) isn't used. So wether it be true or false, who cares..

One other thing to note
Unlike the arguments of a function, which may not be evaluated in the order you wrote them (moreso, they are usually evaluated in reverse order, try some f(i,i++) to check it out), operands of logical operators are guaranteed to be evaluated from left to right (unless they're irrelevant). Which you can neatly abuse in some cases.

In the end though, I think it is computationally more efficient to use an if-statement. At best the compiler will recognize A&&B is the same. Though to be sure I ought to look at the assembly code it compiles to..

Title: Re: 1 TO 100 and 100 to 1
Post by TenaliRaman on Jan 14^th, 2004, 2:18am

I hope towr doesn't mind me replying for him.

Dudidu,
the logic is very simple(not to mention cute and innovative as well),
the statement (i-j) && p(i+1,j) is a (true-false statement).
The next statement after this will be executed if and only if the truth value of this statement is determined.

Note that as long as (i-j)!=0 , the function p(i+1,j) will be called so that its value could be determined. As soon as (i-j) becomes zero , the compiler proceeds ahead without checking the value of p(i+1,j). (Smart trick this one!!)

What happens next is potential backtracking... to print 100 to 1.

This is a beautiful code towr!!!!! 8)

Title: Re: 1 TO 100 and 100 to 1
Post by towr on Jan 14^th, 2004, 2:26am

on 01/14/04 at 02:18:41, TenaliRaman wrote:

I hope towr doesn't mind me replying for him.

heh, nor after me ;)

Quote:

This is a beautiful code towr!!!!! 8)

Thanx..
It's not that special though, these are tricks most people learn if they ever have to write source codes that are as short as possible, which goes for many players in a MOO (where you generally have very limited quota, like 10 or 50k to start with).

Title: Re: 1 TO 100 and 100 to 1
Post by Dudidu on Jan 14^th, 2004, 2:35am

on 01/14/04 at 02:18:41, TenaliRaman wrote:

the logic is very simple...

TenaliRaman Thx,
I didn't pay enough attention to think how '(i-j) && p(i+1,j)' is evaluated :(.
P.S. - Very Nice !!!, towr.

Title: Re: 1 TO 100 and 100 to 1
Post by Barukh on Jan 14^th, 2004, 4:16am

The easiest way to check towr's last solution is to compile and run it - it works.

What I would like to point your attention to - is that the same code may be trivially modified to get a program in C. It also works perfectly well. But raghuram asked for the C++ code... Was it written deliberately to indicate that the C code won't do that - let the author speak. And also:

Quote:

Remember that recursion is not a solution since we would be using 'if'.

I tend to agree, because - even if we don't see 'if' at the C++ level - we will see its equivalent at one or more intermidiate levels.

In that sense, the first towr's solution (using templates) is more correct, since it doesn't use any run time recursion. By the way, when I presented this riddle to my friend (he is considered here as C++ guru), he immediately gave the template solution.

Nice puzzle, raghuram!

Title: Re: 1 TO 100 and 100 to 1
Post by raghuram on Jan 15^th, 2004, 8:44am

Barukh, You guessed it right. I deliberately meant C++ as I was expecting a solution without recursion. There's indeed a solution without recursion and such a solution works only in C++. This solution does not need any templates at all.The solution given by Towr is really good but it can be done using an equivalent 'C' code as well.

Here's a big hint:
[hide]Think about constructors and destructors.
[/hide]

Title: Re: 1 TO 100 and 100 to 1
Post by TenaliRaman on Jan 15^th, 2004, 9:38am

Raghuram,
I personally appreciate innovative answers and i feel both of towr's solution were well within the specified rules of the problem. (Note that it said not to use 'if' and not that the problem mustn't be done using recursion).

Anyways,
this is your expected answer i feel,

Code:

#include<iostream.h>
int count=0;
class dummy
{
public:
dummy()
{
count++;
cout<<count;
}

~dummy()
{
cout<<count;
count--;
}
};

int main()
{
dummy d[100];
return 0;
}

Title: Re: 1 TO 100 and 100 to 1
Post by towr on Jan 15^th, 2004, 10:10am

[edit]Gah, a half an hour gap, and I don't notice someone else's beaten me to the punch..
ah well..[/edit]

Well, maybe this suits you better..
Though I'm not thouroughly convinced it works in every flavour C++ (I have some doubts about the order in which the destructors are called, and also about how the vector is filled)
But it works in g++ 3.0

(of course there's a hidden loop here, and probably in every solution except the first I gave, which is simply explicitly throwing all the number to the out stream)

Code:

#include <iostream>
#include <vector>

class P
{
static int c;
int d;

public:
P(int i)
:d(c++)
{ std::cout << d << std::endl; }

P(P const &_)
:d(c++)
{ std::cout << d << std::endl; }

~P()
{ std::cout << (101-d) << std::endl; }
};

int P::c = 1;

int main()
{
std::vector<P> p(99, P(1));
}

I'll go see if I can find any other solutions..

Title: Re: 1 TO 100 and 100 to 1
Post by Barukh on Jan 19^th, 2004, 12:03am

Here's another solution which doesn't have this destructor order problem.

Code:

#include <cstdlib>
#include <iostream>

void F_pf(int n) { cout << n << endl; }
void F_pb(int n) { cout << (201-n) << endl; }
void F_ex(int n) { exit(0); }

typedef void (*pF) (int);

pF FP[3] = {F_pf, F_pb, F_ex}; // Pointers to functions

struct T {
static int n;

T(void)
{
FP[ (n-1) / 100 ]( n );
n++;
T t;
}
};

int T::n = 1;

main()
{
T t;
}

Although implemented as a C++ program, it may be easily re-written in C using recursion - and still (IMHO) without using loops and conditional statements!