programming challenges

[phillip1882]

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.

[khaled]

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 ;
           }
     }
}

[Xittenn]

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

[khaled]

I've got one . . . . implement the Riemann [math] \zeta [/math] 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 [math] \zeta [/math] 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

[Xittenn]

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

[khaled]

Let's simplify it to this, implement this algorithm

 

 

Source: http://people.math.sfu.ca/~pmenz/thesis.pdf

Edited March 20, 2012 by khaled

[Xittenn]

As you wish, but over GPU and graphically!

[ecoli]

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)
}

[Xittenn]

much better than Java!

 

+1

 

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

[ecoli]

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)

[ecoli]

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

[Xittenn]

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?

[khaled]

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 )
{
     // write your code here
}

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

[phillip1882]

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.

[Xittenn]

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

Published by: American Mathematical Society

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???

[khaled]

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 [math]\sqrt{-1}[/math] 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 [math]\mathbb{Z}[/math], 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);
}

[Xittenn]

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

[khaled]

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 March 27, 2012 by khaled

[phillip1882]

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 March 27, 2012 by phillip1882

[khaled]

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 March 28, 2012 by khaled

[phillip1882]

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 March 28, 2012 by phillip1882

[khaled]

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