Programming Challenges - Page 10


Page 10 of 19 FirstFirst ... 67891011121314 ... LastLast
Results 136 to 150 of 279

Thread: Programming Challenges

  1. #136
    Join Date
    Jun 2003
    Posts
    173

    Bernoulli Challenge

    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.
    Attached Files Attached Files

  2. #137
    Join Date
    Dec 2003
    Location
    Phoenix, AZ
    Posts
    647
    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.
    "There's a big difference between "copy" and "use". It's exatcly the same
    issue whether it's music or code. You can't re-distribute other peoples
    music (becuase it's _their_ copyright), but they shouldn't put limits on
    how you personally _use_ it (because it's _your_ life)."

    --Linus Torvalds

  3. #138
    Join Date
    Jun 2003
    Posts
    173
    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.

  4. #139
    Join Date
    Jul 2003
    Posts
    28
    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
    Last edited by grady; 12-06-2003 at 03:18 PM.

  5. #140
    Join Date
    Dec 2003
    Location
    Colorado
    Posts
    149
    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.
    Last edited by GlennaclawZ; 12-09-2003 at 05:34 PM.
    Registered Linux User: #342515

    Slackware 10 - kernel 2.6.10

    AMD Athlon 3000+
    512 RAM pc2700
    NVIDIA GeForce2 Integrated

    www.rex-pro.com For life!!!

  6. #141
    Join Date
    Dec 2002
    Posts
    226
    Originally posted by grady
    Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications
    express the component as complex exponentials?
    Powered by Fedora Core

  7. #142
    Join Date
    May 2001
    Location
    Uh, I'm somewhere where I don't know where I am.
    Posts
    1,228
    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]
    Last edited by tecknophreak; 03-15-2004 at 03:40 PM.
    if (i_forgot && this_is_about_code)
    language = c++;

  8. #143
    Join Date
    Apr 2003
    Posts
    122
    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.
    "Did you ever notice how fast Windows runs? Neither did I."

  9. #144
    Join Date
    Feb 2003
    Location
    USA
    Posts
    458
    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!!!!
    . : My Blog : : System specs (scroll down) : : Screenshots : .

    "The world is like a giant puzzle; it's always easiest to fit where you belong."

  10. #145
    Join Date
    Dec 2002
    Location
    GA--United States
    Posts
    273

    GEEK Challenges

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

  11. #146
    Join Date
    Nov 2003
    Posts
    53
    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.
    Last edited by Lc3; 03-21-2004 at 05:16 PM.
    Whatever it is I'm asking no doubt someone will find the answer in some obvious place and accuse me of not STWFing or RTFMing.

    I swear I did, I'm just stupid.

  12. #147
    Join Date
    Apr 2001
    Location
    SF Bay Area, CA
    Posts
    14,936
    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.

  13. #148
    Join Date
    Aug 2002
    Location
    Cayman Islands
    Posts
    681
    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.
    Scotty: Captain, we din' can reference it!
    Kirk: Analysis, Mr. Spock?
    Spock: Captain, it doesn't appear in the symbol table.
    Kirk: Then it's of external origin?
    Spock: Affirmative.
    Kirk: Mr. Sulu, go to pass two.
    Sulu: Aye aye, sir, going to pass two.

  14. #149
    Join Date
    Mar 2001
    Posts
    729
    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.

  15. #150
    Join Date
    Apr 2001
    Location
    SF Bay Area, CA
    Posts
    14,936
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •