programming challenges

Recommended Posts

i was thinking of posting a programming challange a month, both to help people sharpen their skills and to get some conversation going.

would there be interest in this?

if so; here's my first programming challenge.

most computer people know how to convert numbers to binary, but ternary computers are also possible.

my task for you is to write a program that can convert a decimal number to a ternary (base 3), and then be able to preform basic operations with two such numbers; addition, subtraction, multiplication, and division.

for extra points, also convert a decimal to balanced ternary, and have similar operations with them.

Share on other sites

Java:

public class Ternary
{
private String num ;

public Ternary ( )
{
num = "0" ;
}

public Ternary ( String n )
{
num = n;
}

public void set ( String n )
{
num = n;
}

public String get ( )
{
return new String ( num ) ;
}

public parseDecimal ( int d )
{
num = "" ;

if ( d == 0 )
{
num = "0" ;
}

int m = 1, b = 3 ;

while ( d > 0 )
{
num += ((d%10)*(b^m)) ;
m++ ;
d /= 10 ;
}
}
}


Share on other sites

I've got one . . . . implement the Riemann $\zeta$ function over GPU .. . . use any method you wish but the result should be a colour animation of some sort!

Share on other sites

I've got one . . . . implement the Riemann $\zeta$ function over GPU .. . . use any method you wish but the result should be a colour animation of some sort!

I think your programming challenge is "implement the Riemann $\zeta$ function",

Implementing a Riemann Zeta function is not a simple challenge, Analytical models require Combinatorics when it comes to Computability

unless if one would implement an existing computational algorithm from papers .. like this one

Share on other sites

I left it fairly open to interpretation, but regardless feel free to not challenge yourself!

Share on other sites

Let's simplify it to this, implement this algorithm

Edited by khaled
Share on other sites

As you wish, but over GPU and graphically!

Share on other sites

A solution written in R

convert.ternary <- function(int) {

unit.factor <- 1
mult.factor <- 1
total <- 0
ternary <- 0

while (mult.factor <= int) {
temp <- trunc((int-total)/mult.factor) %% 3
total <- total + temp
ternary <- ternary + (temp * unit.factor)
unit.factor <- unit.factor * 10
mult.factor <- mult.factor * 3
}
return(ternary)
}



Share on other sites

much better than Java!

+1

all I have is a base64 converter . . . . which is irrelevant, so I won't post it . . .

Share on other sites

much better than Java!

+1

Although loops in R are much less efficient

all I have is a base64 converter . . . . which is irrelevant, so I won't post it . . .

I believe my function is generalizable to any base, just replace the 3's with the desired base (or a replace with a variable for user input)

Share on other sites

correction... it would work given an arbitrary number of numeric symbols to pick from.

Share on other sites

Although loops in R are much less efficient

I believe my function is generalizable to any base, just replace the 3's with the desired base (or a replace with a variable for user input)

Since when is being cool about being efficient?

Share on other sites

Here is my first programming challenge,

#include <stdio.h>

int main ( )
{
int X = 0;

if ( X != X )
{
printf ( "impossible can happen" );
}

return 0;
}


The challenge is simple, modify the code above, such that the condition ( X != X ) return TRUE, "impossible can happen" will print,

-------------------------------------------

Here is my second programming challenge,

#include <stdio.h>

void swap ( int * A, int * B )
{
}

int main ( )
{
int A = 1, B = 2;

printf ( " A = %d, B = %d \n", A, B );

swap ( &A, &B );

printf ( " A = %d, B = %d \n", A, B );

return 0;
}


modify the code above, implement the swap function that swap values of A and B, BUT DO NOT DEFINE A NEW\TEMP VARIABLE !

-----------------------------------------

.. good luck

Share on other sites

the second one was fairly simple; still not sure about the first. i have a couple ideas bouncing around though.

swap( int a, int b){

a = a^b

b = a^b

a = a^b

}

here's my next challenge.

find the smallest composite n, for which the base value 2 gives a false positive of the robin miller test.

the robin miller prime test is as follows.

take a odd number, n. subtract 1, and divide by 2 until odd, call this number d. call the number of divisions S.

if:

b^d != -1 or 1 mod n

or

if:

b^(2^r *d) != -1 mod n for 0 < r <= s

then n is composite.

else n is probably prime.

in other words find the first composite probably prime base 2.

Share on other sites

I really like your challenge phillip1882, I will have to add it to my list of things to do between terms--your challenge, the challenge that I posted, and a blog post on the infeasibility of 'Self-Generating Darius Windmills' or windmills whose magnet is the earth . . . .

Rabin-Miller Primality Test: Composite Numbers Which Pass It

F. Arnault

Mathematics of Computation

Vol. 64, No. 209 (Jan., 1995), pp. 355-361

Stable URL: http://www.jstor.org/stable/2153340

I don't see how khaled's first challenge is at all feasible without modifying the compiler itself???

Share on other sites

I don't see how khaled's first challenge is at all feasible without modifying the compiler itself???

It's possible using 1 line of code, here it is in case you're curious

#include <stdio.h>
#include<math.h>

int main ( )
{
float X = sqrt(-1);

if ( X != X )
{
printf ( "impossible can happen" );
}

return 0;
}


Explanation: in the IEEE standard $\sqrt{-1}$ is considered undefined, and undefined numbers in

the IEEE are never equal, even though the code of undefined is the same

the second one was fairly simple; still not sure about the first. i have a couple ideas bouncing around though.

swap( int a, int b){

a = a^b

b = a^b

a = a^b

}

your code doesn't work, because a^b is "a power b" in $\mathbb{Z}$, here is the solution

int xor (int x, int y)
{
return (x ^= y);
}

void swap (int a, int b)
{
a = xor (a, b);
b = xor (a, b);
a = xor (a, b);
}


Share on other sites

Well you got me khaled . . . next time I'll try thinking 'inside' the box! ;-)

Share on other sites

Well you got me khaled . . . next time I'll try thinking 'inside' the box! ;-)

you mean "outside" the box, although I still wonder since when the box exist

I love philosophical challenges, since I'm a philosopher .. I'm not good with mathematics and equations,

but I'm good with logic .. and so, I will give you a hard one

Question: Can unsolvable problems be solved ?

Hints:

- Why would someone say that this problem is unsolvable

- Do you know what is a Paradox

- "the only barber in the town, he only shave those who don't shave themselves", "does the barber shave himself ?"

Edited by khaled
Share on other sites

but your code is doing exactly the same thing mine is, only more abstractly!

i was well aware in c that a^b = xor(a, b)

any way....

interesting solution for problem #1.

here's the way i was thinking of solving it.

#include <stdio.h>
int increment(int val){
static int x = 0;
x += 1;
return x;
}
int main ( )
{
int X = 0;

if ( increment(X) != increment(X))
{
printf ( "impossible can happen" );
}

return 0;
}


which should in theory print the statement.

Edited by phillip1882
Share on other sites

but your code is doing exactly the same thing mine is, only more abstractly!

i was well aware in c that a^b = xor(a, b)

any way....

interesting solution for problem #1.

here's the way i was thinking of solving it.

#include <stdio.h>
int increment(int val){
static int x = 0;
x += 1;
return x;
}
int main ( )
{
int X = 0;

if ( increment(X) != increment(X))
{
printf ( "impossible can happen" );
}

return 0;
}


which should in theory print the statement.

Two things,

1. [edited] your solution is correct

2. The second puzzle stated that the condition should not be changed, the condition is: X != X

which seem impossible algebraically, but not according to undefined numbers in IEEE standard

.. good luck, try the question I posted

Edited by khaled
Share on other sites

i went to www.ideone.com and ran the following in both c and c++

#include <stdio.h>
int main(){
int x = 7;
int y = 3;
int z = x^y;
printf("%d \n",z);
z = y^x;
printf("%d \n",z);
return 0;
}


and got

4

4

here's my coding challenge to you. xor 5 variables together on the same line with the ^ symbol, no side function.

Edited by phillip1882
Share on other sites

i went to www.ideone.com and ran the following in both c and c++

#include <stdio.h>
int main(){
int x = 7;
int y = 3;
int z = x^y;
printf("%d \n",z);
z = y^x;
printf("%d \n",z);
return 0;
}


and got

4

4

here's my coding challenge to you. xor 5 variables together on the same line with the ^ symbol, no side function.

Your code is current, that's +1 for you .. I think I was mis-confused by old compilers, but it's good that they modified it

Create an account

Register a new account