Overclock.net - An Overclocking Community

Overclock.net - An Overclocking Community (https://www.overclock.net/forum/)
-   Coding and Programming (https://www.overclock.net/forum/142-coding-programming/)
-   -   Programming Challenges! (https://www.overclock.net/forum/142-coding-programming/411634-programming-challenges.html)

Manyak 11-14-2008 07:15 AM

The sticky hasn't been used in forever but I think its time we had one .

Even if you are just starting out programming, the questions cover a whole range of difficulty from beginner to advanced, so no matter what your level of programming you should be able to answer at least one or two.


And if enough people actually participate in this, I may make another one for some nice prizes



Beginner Questions

1: Permutations
Create a program that asks the user for a string, and lists all possible permutations of it.

Example:

Enter a string: cat
cat
cta
act
atc
tac
tca

2: Fibonacci Sums
Create a program that finds the sub of all even numbers in the Fibonacci sequence which do not exceed 4 million.

The Fibonacci sequence is determined by starting at 1 and 2 and adding all the previous numbers together, as such:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....

So add all the even numbers together that are less than 4,000,000

3: Factorial Sums
Find the sum of all numbers which are euqal to the sum of the fractorials of their digits. (Other than 1 and 2)

For example, look at the number 145.
1! + 4! + 5! = 1 + 24 + 120 = 145


Intermediate Questions

4: Sundays
Create a program that calculates the number of Sundays that were the 1st of a month in the 20th century

To be more specific, start the century as Jan 1 1900 and end it with Dec 31 1999.


5: Circular Primes
Create a program that calculates the number of circular primes under 1,000,000

A circular prime is a number where all rotations of the digits are prime numbers.

Example: 197, 971, and 719 are circular primes.


Advanced Questions

6: Monopoly
Create a program that will find the 3 most frequently landed on squares when using two 4-sided, 6-sided, and 8-sided dice.

Don't forget to take into account the Chance and Community Chest cards! Here's a list of the possible cards that affect a player's position:

Community Chest (2/16 cards):
- Advance to GO
- Go to JAIL
Chance (10/16 cards):
- Advance to GO
- Go to JAIL
- Go to next RR (x2)
- Go to next Utility
- Go to St. Charles Place
- Go to Illinois Ave.
- Go back 3 spaces
- Take a ride on the Reading Railroad
- Take a walk on the Boardwalk


7: Towers of Hanoi
Create a program that will ask the user for a number of rings and which tower to move them to, and display all the steps required to do so.

Such a classic programming problem!

The towers are as such:


The rules are that you can only move one ring at a time, and you can't place a bigger ring on top of a smaller ring.

To give you an example, the solution to 3 rings is as such:



Professional Questions

8: RSA Encryption
Find the most secure encryption

RSA encryption is based on the following procedure:

Generate two distinct primes p and q.
Compute n=pq and φ=(p-1)(q-1).
Find an integer e, 1<e<φ, such that gcd(e,φ)=1.

A message in this system is a number in the interval [0,n-1].
A text to be encrypted is then somehow converted to messages (numbers in the interval [0,n-1]).
To encrypt the text, for each message, m, c=m^e mod n is calculated.

To decrypt the text, the following procedure is needed: calculate d such that ed=1 mod φ, then for each encrypted message, c, calculate m=c^d mod n.

There exist values of e and m such that me mod n=m.
We call messages m for which me mod n=m unconcealed messages.

An issue when choosing e is that there should not be too many unconcealed messages.
For instance, let p=19 and q=37.
Then n=19*37=703 and φ=18*36=648.
If we choose e=181, then, although gcd(181,648)=1 it turns out that all possible messages
m (0<=m<=n-1) are unconcealed when calculating m^e mod n.
For any valid choice of e there exist some unconcealed messages.
It's important that the number of unconcealed messages is at a minimum.

Choose p=1009 and q=3643.
Find the sum of all values of e, 1<e<φ(1009,3643) and gcd(e,φ)=1, so that the number of unconcealed messages for this value of e is at a minimum. Then create a program that can encrypt and decrypt a file using those values.

=========================================

Round 2!

This time around, the problems will be slightly more advanced across the board. They should pose a little more of a challege


Beginner Questions

9: Very Large Prime
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^(6972593)−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^(p)−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^(7830457)+1.

Find the last ten digits of this prime number.


10: Crackless Wall

Consider the problem of building a wall out of 2x1 and 3x1 bricks (horizontal×vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".

For example, the following 9x3 wall is not acceptable due to the running crack shown in red:



There are eight ways of forming a crack-free 9x3 wall, written W(9,3) = 8.

Calculate W(32,10).


Intermediate Questions

11: Minimize Roman Numerals
The rules for writing Roman numerals allow for many ways of writing each number (see FAQ: Roman Numerals). However, there is always a "best" way of writing a particular number.

For example, the following represent all of the legitimate ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

The last example being considered the most efficient, as it uses the least number of numerals.

This text file contains 1000 numbers written in valid, but not necessarily minimal, Roman numerals.

Find the number of characters saved by writing each of these in their minimal form.


12: Sudoku

Write a program that allows the user to enter a sudoku puzzle, and uses a backtracking algorithm to solve it.

Each Sudoku has a unique solution that can be reached logically without guessing. Enter digits from 1 to 9 into the blank spaces. Every row must contain one of each digit. So must every column, as must every 3x3 square.

Visit http://www.websudoku.com/ for example puzzles if you are unfamiliar with it.

The basic principle of a backtracking algorithm, in regards to Sudoku, is to work forwards, one square at a time to produce a working Sudoku grid. When a problem occurs, the algorithm takes itself back one step and tries a different path. Essentially it's like walking through a maze with some golden thread and going back and forth down dead ends until you find the right way out. It's nearly impossible to produce a valid Sudoku by randomly plotting numbers and trying to make them fit. Likewise, backtracking with a random placement method is equally ineffective. Backtracking best works in a linear method. It is fast, effective and reliable if done correctly.


Advanced Questions

13: Barcodes

The goal is simple - write a program that can decode a barcode image (from a .bmp or .jpg) and give the UPC number that it represents.

This site has all the information you'll need about bar codes - including all the ASCII codes.

Hint: (select the line underneath to view)
You will need to use gray interpolation to find the edges of the bars.

decompiled 11-14-2008 08:57 PM

Code:
/* Towers of Hanoi */
/* Decompiled - Overclock.net */
#include <stdio.h>

int hanoi( int disks, int start, int finish, int temp );

int main()
{
  int disks, start, finish, temp;

  printf("Enter the number of disks: ");
  scanf("%d", &disks);
  printf("Enter the starting position ( 1 thru 3 ): ");
  scanf("%d", &start);
  printf("Enter the finishing position ( 1 thru 3 ): ");
  scanf("%d", &finish);
  printf("Enter the temporary position ( 1 thru 3 ): ");
  scanf("%d", &temp);

  hanoi(disks, start, finish, temp);

  return 0;
}

int hanoi( int disks, int start, int finish, int temp )
{
  if (disks > 0){
    hanoi( disks - 1, start, temp, finish );
    move( start, finish);
    hanoi( disks - 1, temp, finish, start );
  }
}

int move( int start, int finish )
{
  printf("move ");
  printf("%d", start);
  printf(" --> ");
  printf("%dn", finish);
}

Elitester 11-15-2008 10:45 AM

Jcreator is a program that helps people begin java. It comes with a JVM and debugger and stuff. We used it in our Intro to computer science class. It is free too! Its like a free version of dreamweaver for java.

decompiled 11-15-2008 12:05 PM

LOL

Manyak 11-15-2008 01:00 PM

Sweet, that's one question answered



Quote:
Originally Posted by Elitester View Post
Jcreator is a program that helps people begin java. It comes with a JVM and debugger and stuff. We used it in our Intro to computer science class. It is free too! Its like a free version of dreamweaver for java.
what? lol

error10 11-15-2008 01:18 PM

Is it cheating to use OpenSSL?

Manyak 11-15-2008 01:54 PM

Quote:
Originally Posted by error10 View Post
Is it cheating to use OpenSSL?
LOL, kind of defeats the whole purpose don't you think?

dangerousHobo 11-15-2008 03:12 PM

If you have any challenges then you can send them to myself or BFRD and we'll add them to the sticky challenges. The reason that was has been dead is because I didn't have any more fun ideas to go off of!

dangerousHobo 11-15-2008 03:27 PM

Fibonacci sums
Code:
/*
 Fibonacci sums
 dangeroushobo - Overclock.net
*/
#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char *argv[]) {
    int p1 = 1;
    int p2 = 2;
    int p;
    
    printf("%d, %d, ", p1, p2);
    while ( (p = p1 + p2) < 4000000 ) {
        printf("%d, ", p);
        p1 = p2;
        p2 = p;
    }
    return 0;
}

Manyak 11-15-2008 03:41 PM

Quote:
Originally Posted by dangerousHobo View Post
If you have any challenges then you can send them to myself or BFRD and we'll add them to the sticky challenges. The reason that was has been dead is because I didn't have any more fun ideas to go off of!
Ok, I've got a ton of them . Enough to go around for a few months or so at least.


All times are GMT -7. The time now is 02:26 AM.

Powered by vBulletin® Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

User Alert System provided by Advanced User Tagging (Pro) - vBulletin Mods & Addons Copyright © 2020 DragonByte Technologies Ltd.
vBulletin Security provided by vBSecurity (Pro) - vBulletin Mods & Addons Copyright © 2020 DragonByte Technologies Ltd.

vBulletin Optimisation provided by vB Optimise (Pro) - vBulletin Mods & Addons Copyright © 2020 DragonByte Technologies Ltd.