Programming Challenges

I have a new challenge for everybody. This program was one that I had to write for a computer science class and requires a little mathematics background. (Though which a little intuition it can be figured out) I included it in a seperate file as there are a few restrictions. This program calculates and outputs the Bernoulli Coefficients for some k which is between 1 and 15. I have explained what a Bernoulli Coefficient is in the text file attached. This program can be completed using iterative loops and once you find a relation for B(j,k) from S(n,k) is pretty simple. However, this program is extremely slow when using numbers larger than say 15 for k. For even more of a challenge, find a dynamic programming algorithm which will compute the numbers even faster (I do believe this exists, but I don't know it right now). If you have any questions about the program you can PM me. Good Luck



[NOTE]
I know people have asked for less mathematical challenges in the past, but the truth is that programming is based mostly on mathematical ideas and theory. Therefore we cannot get away from math in programming. The most interesting ideas and challenges in Programming really come from the mathematics behind it.

Here's a neat little challenge with a history.

When my USMC Reserve unit was activated and sent to Iraq recently, I was forced over into that big sandbox with them. From there I ended up in the 6ESB S-2 shop. That's right kids, military intelligence. Of course, that meant I did absolutely nothing for 20 hours out of every day. However, I teamed up with out Intel Chief Sgt. Knight and we came up with the hardware for a microwave relay to FSSG. That means we had internet access! Since he was a CS student and I had done some java coding, we decided to download the jdk. Next, we stumbled upon the challenge I will present to you. However, I cannot tell you how to complete it because Sgt. Knight and I never got around to it. He was just a second year student and the extent of my programming revolves around CMP/JBoss where I actually don't write any real code I simply spend hours writing xml documents that tell the container precisely how to blow my code bits right through my foot at a high rate of speed. I digress........Here is the challenge.

You are a knight on a standard chess board (8x8). At what positions on the board can you start moving using normal knight moves and touch each square on the board exactly once?

That means there are several positions from which you can start (64), and the knight piece moves 2 up and 1 over, or 1 up and 2 over. Whichever square it lands on is now off limits to land on again. From which squares on the grid is this possible?

Once you have conquered that, try it with a 12X12 chessboard or a 16X16 chessboard.

If anyone has posted this before in this thread, I am sorry but I haven't had the time to browse the thread cover to cover.

Hey, I did that, it is sometimes called the Knight's Tour. I actually did it for some class using either FRIL or LISP can't remember which. If I find my code I will post it here. There is another similar problem that I did. This was the 8 Queens Problem. Basically on an 8X8 chess board how could you place eight queens onto the board so that no queen was attacked by any other queen on the board.

Quote:

---

Originally posted by soccerplayer
Here is a holiday challege for you guys...someone write a quick duckhunt type program in c++ where your goal is to shoot santa ( or if youd like buddha, reindeer, etc...) make either the mouse or keyboard do the actual shooting, whatever you guys would like. lets just see if anyone has some holiday programming spirit.

---

Press 'g' to turn off gravity. press 'esc' to exit. you lose 50 points if you don't click a duck by the time it goes off the screen. You get points proportional to the horizontal speed of the duck if you do click it, and you still get points for clicking a duck after you've clicked him but a decreasing amount each succesive click. The code for the glfont, glstring, and xwindow libraries isn't included so you can't compile the main file. An executable is included. I just gutted a copy of a program I was working on and added the code to make this game, so the code (and the game) isn't pretty. The game is best played at 1024x768 with an opengl driver. You also need to keep the window maximized or else ducks are generated off screen. I forgot to scale the velocities according to your screen resolution so they are going to move across your screen at x pixels/sec regardless of how wide your screen is. Sorry.

game

Quote:

---

Originally posted by voidinit


You are a knight on a standard chess board (8x8). At what positions on the board can you start moving using normal knight moves and touch each square on the board exactly once?

Once you have conquered that, try it with a 12X12 chessboard or a 16X16 chessboard.

If anyone has posted this before in this thread, I am sorry but I haven't had the time to browse the thread cover to cover.

---

dude... thats easy I did it last year in my sophmore CS class... you

let me see if I can find the code...


import java.awt.geom.*;
import java.util.*;
import java.util.Random;
public class knightJourney
{
private int[][] grid = new int[7][7];
private ArrayList moves;
private int numMoves;
private Point2D.Double knight;
public knightJourney()
{
moves = new ArrayList();
moves.add(new Point2D.Double(1, 1));
knight = (Point2D.Double)moves.get(1);
}

public ArrayList possMoves(int positionX, int positionY)
{
Point2D.Double space;
space = new Point2D.Double(positionX + 1, positionY - 2);
moves.add(space); space = new Point2D.Double(positionX + 2, positionY - 1);
moves.add(space);
space = new Point2D.Double(positionX + 2, positionY + 1);
moves.add(space);
space = new Point2D.Double(positionX + 1, positionY + 2);
moves.add(space);
space = new Point2D.Double(positionX - 1, positionY + 2);
moves.add(space);
space = new Point2D.Double(positionX - 2, positionY + 1);
moves.add(space);
space = new Point2D.Double(positionX - 2, positionY - 1);
moves.add(space);
space = new Point2D.Double(positionX - 1, positionY - 2);
moves.add(space);
return moves;
}

public ArrayList testMoves(int x, int y)
{
ArrayList possibleMoves = possMoves(x, y);
for(int i = 0; i <= possibleMoves.size(); i++)
for(int k = 0; k <= possibleMoves.size(); k++)
if(possibleMoves.get(k) != moves.get(k))
possibleMoves.remove(k);
return possibleMoves;
}

public Point2D.Double pickMove()
{
Random random = new Random();
ArrayList possibleMoves = testMoves(b, c);
Point2D.Double a = possibleMoves.get(random.nextInt(possibleMoves.siz e()));
Point2D.Double b = (double)a.getX();
Point2D.Double c = (double)a.getY();
Point2D.Double move = new Point2D.Double();
move = (Point2D.Double)possibleMoves.get(random.nextInt(p ossibleMoves.size()));
moves.add(move);
return move;
}

public void move(Point2D.Double a)
{
moves.add(a);
knight = a;
}

public int[][] printGrid()
{
return grid;
}
}

...sorry I dont know how to add textfiles...

just copy it and paste it in your compiler and run it... but you do need a tester for it.

Quote:

---

Originally posted by grady
Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications

---

express the component as complex exponentials?

Got a new one, should be quite simple, however, this one requires speed mostly. Open a file full of unsigned shorts(2 bytes) strip off the top 4 bits of those bytes and place in a new file, or overwrite the last file with this.

I've gotten 600 MB in 40 seconds using a drive which gives me 40 MB/s for hdparm -t. So using C++, hmm, I've gotten 15 MB/s. I'm sure someone can kill this. :)

[edit]yeah, screw c++, c gets me 18.4 MB/s[/edit]

i think this might be a neat one, someone correct me if im mistaken. Given a 2 dimensional shape of N equal sides, and fixed diameter, compute the vaule of N required to approximate PI to 3 decimal places.

That one sounds good.

What I did with Python just to get used to general syntax (or to brush up and clear out the cobwebs :) ) was calculate things like prime numbers and sequences like Fibonnacci. Easy, simple things. Best of all, they're USEFUL!!!!

Check out the GEEK Challenges at http://www.osix.net. It's an interesting site over all.

Did i arrive too late for the swap two variable without a temp var challenge? anyway here's my soln. Some other solutions suggested might cause overflows but this one will work with any two integers and it remarkably efficient :P

int a = 4;
int b = 2;

switch (a) {
case -2147483648:

switch (b) {
case -2147483648:

a = -2147483648;
b = -2147483648;

break;
case -2147483647:

a = -2147483647;
b = -2147483648;

break;

// etc... (to 2147483647)

}

break;
case -2147483647:

switch (b) {
case -2147483648:

a = -2147483648;
b = -2147483647;

break;
case -2147483647:

a = -2147483647;
b = -2147483647;

break;

// etc... (to 2147483647)

}

break;

// etc... (to 2147483647)

}

Now don't go stealing my code for profit now ;)


New challenge;

Write an application capable of passing the turing test. Bonus points if it can compose and opera, clean your room or cure cancer. The program should be small enough to fit on your basic model of a PIC microcontroler and be written entirly in ASM.

annnnnd go.

Quote:

---

Originally posted by Lc3
this one will work with any two integers and it remarkably efficient :P

---

Um... no it isn't... ;)

First, it would require, at MINIMUM, 16 billion gigabytes of code space (since it'll be at least one byte for each value of a and b, that's 4 billion, squared, possibilities).

Second, switches don't jump directly to the proper case, or at least not necessarily. They function the same as an if-else structure if you have the break; statements in there, and the assembly that gcc outputs is very similar also (basically, it evaluates each case and compares it to the switched value, executes the first that matches, and keeps executing code until it sees a break or the end of the switch). So it's actually extremely inefficient. Something like:

Code:

---

a^=b;
b^=a;
a^=b;

---

(which I think was posted already) will work for all combinations of 32-bit values, and will be much faster than running through 4 billion possibilities for b, finding the right one, then running through 4 billion possibilities for a, then assigning the proper results to each variable. ;)

Quote:

---

Originally posted by Lc3
New challenge;

Write an application capable of passing the turing test. Bonus points if it can compose and opera, clean your room or cure cancer. The program should be small enough to fit on your basic model of a PIC microcontroler and be written entirly in ASM.

annnnnd go.

---

You first. :D

Quote:

---

Originally posted by bwkaz
Second, switches don't jump directly to the proper case, or at least not necessarily. They function the same as an if-else structure if you have the break; statements in there, and the assembly that gcc outputs is very similar also (basically, it evaluates each case and compares it to the switched value, executes the first that matches, and keeps executing code until it sees a break or the end of the switch

---

Wow...you sure about that? All the time I've assumed that a switch statement used some sort of jump table array thing. (That was my reason why you couldn't do "real" tests in there, other than "is it a certain integer?")

I've never actually seen the assembly output, but it just made so much sense I didn't bother to check. :D

Well, actually no, I'm not positive.

But the jump table would be absolutely gigantic with a switch that looks like this:

Code:

---

switch(tempvar) {
    case 0:  break;
    case INT_MAX: break;
}

---

You'd need one entry in the table for 0, and another one for INT_MAX, which would make the table be INT_MAX+1 elements long. A gigantic waste of INT_MAX-1 ints. :)