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.
