Overclock.net banner

Programming Challenges!

11083 Views 98 Replies 22 Participants Last post by  ToastedZergling
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.


Enter a string: cat

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:


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.
See less See more
1 - 4 of 99 Posts
#2, done in LISP


(define (sumEvenFib maxValue)
    (define (fibIteration a b sum)
         (cond ((> b  maxValue) sum)
               ((even? b) (fibIteration b (+ a b) (+ sum b)))
               (else (fibIteration b (+ a b) sum))))
    (fibIteration 1 1 0))

(sumEvenFib 40000000)
#3 done in LISP. Its kind of ugly, but I wanted to show how you can treat functions like variables in LISP


(sumFactorials 4000000)

(define (sumFactorials maxNum)
    (sumFactIter 0 3))

(define (sumFactIter sum count)
            (cond ((= count
                      (sigma (lambda x (factorial (remainder x 10))) 
                   (sumFactIter (+ sum count) (+ count 1)))
                  ((= count maxNum) sum)
                  (else sumFactIter sum (+ count 1))))

(define (sigma function next condition m)
    (if (condition m)
         (+ (function m)
            (sigma function condition next (next m)))))

(define (factorial x)
    (if (= x 1) 
        (* x (factorial (- 1 x)))))

(define (nextNum y)
     (quotient y 10))

(define (zero? m)
    (= m 0))
See less See more

Originally Posted by Manyak
View Post

out of all the programming languages out there, LISP was one of the last ones I expected to see in this thread - right down there with BCPL

Lisp/Scheme is really a fun language if you take the time to learn it. It may look a little odd with all the parentheses, but once you get past that it begins to look really beautiful.
See less See more

Originally Posted by timw4mail
View Post

Now someone should do one in FORTRAN...

You ask and I deliver. I think this is how to do the Fibonacci program in FORTRAN:

      A = 1
      B = 1
      SUM = 0
      DO 15, ITER = 1, 40000000
            TEMP = A
            A = B
            B = B + TEMP
            IF(MOD(B, 2) .EQ. 0)
                  SUM = SUM + B
            END IF

      WRITE(*,*) SUM             
It was not actually all that difficult for something this simple, other than it yelling at you the entire time.

Hmm, How about Verilog:

module Fibonacci;

integer a, b, sum, temp;
a = 1;
b = 1;
sum = 0;

      temp = a;
      a = b;
      b = b + temp;
      if((b % 2) == 0)
             sum = sum + b;

ARM assembly?

      MOV R0, #1                  @a
      MOV R1, #1                  @b 
      MOV R2, #0                  @sum, R3, R4 is temp
      MOV R5, #40000000     @number of repetitions

      MOV R0, R1
      ADD R1, R1, R3
      MOV R4, R1

EVEN: SUBS R4, R4, #2 
      BMI EVEN

      BNE IF

      ADD R2, R2, R1
IF:   SUBS R5, R5, #1
      BNE LOOP
Now I haven't actually tested any of these, but they should work.
See less See more
1 - 4 of 99 Posts
This is an older thread, you may not receive a response, and could be reviving an old thread. Please consider creating a new thread.