 # Programming Challenges!

10913 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.

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.

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):
- Go to JAIL
Chance (10/16 cards):
- 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 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.

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.
1 - 20 of 99 Posts

#### decompiled

· Registered
Joined
·
1,033 Posts
Code:

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);
}``````

• Manyak

#### Elitester

· Registered
Joined
·
235 Posts
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.

· Registered
Joined
·
1,033 Posts
LOL

#### Manyak

Joined
·
12,254 Posts
Discussion Starter · ·

Quote:
 Originally Posted by Elitester 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

Joined
·
14,563 Posts
Is it cheating to use OpenSSL?

#### Manyak

Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by error10 Is it cheating to use OpenSSL?
LOL, kind of defeats the whole purpose don't you think?

#### dangerousHobo

Joined
·
4,010 Posts
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

Joined
·
4,010 Posts
Fibonacci sums

Code:
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

Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by dangerousHobo 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.

#### dangerousHobo

Joined
·
4,010 Posts
Factional sum

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

int
factorial(int num) {
int i = num--;
while ( num > 0 ) {
i *= num--;
}
return i;
}

int
main(int argc, char *argv[]) {
int num = 0;
int qnt;
int sum;

while ( num < 4000000 ) {
qnt = num;
sum = 0;
while ( qnt > 0 ) {
sum += factorial(qnt % 10);
qnt = qnt / 10;
}

if (sum == num) {
printf("%d ", num);
}
num++;
}
printf("n");
return 0;
}``````

#### decompiled

· Registered
Joined
·
1,033 Posts
Code:

Code:
``````/* String Permutation */
/* Decompiled - Overclock.net */

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
// Prompt
System.out.println("Enter a string: ");
// Get the value entered
String input = in.nextLine();

// Lower case Output
input = input.toLowerCase();

// Calculate all possible permutations !N
permute("", input);
}

private static void permute(String a, String b) {
// Size of string
int size = b.length();

if (size == 0)
System.out.println(a);
else {
for (int i = 0; i < size; i++)
// Recursive call
permute(a + b.charAt(i), b.substring(0, i)
+ b.substring(i + 1, size));
}
}
}``````

#### Manyak

Joined
·
12,254 Posts
Discussion Starter · ·
4 / 9 completed

Awesome!

#### decompiled

· Registered
Joined
·
1,033 Posts
I was about to do the date calculation in PL/SQL but I forget that the UFC has a big event tonight =).

#### dangerousHobo

Joined
·
4,010 Posts
Quote:
 Originally Posted by decompiled I was about to do the date calculation in PL/SQL but I forget that the UFC has a big event tonight =).
Yeah! I watched it tonight at bdubs and saw the new Bond!

Joined
·
5,512 Posts
#2, done in LISP

Code:

Code:
``````(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)``````

Joined
·
5,512 Posts
#3 done in LISP. Its kind of ugly, but I wanted to show how you can treat functions like variables in LISP

Code:

Code:
``````(sumFactorials 4000000)

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

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

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

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

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

(define (zero? m)
(= m 0))``````

#### BiG O

Joined
·
4,576 Posts
Quote:
 Originally Posted by The Bartender Paradox #3 done in LISP. Its kind of ugly, but I wanted to show how you can treat functions like variables in LISP Code: Code: ``````(sumFactorials 4000000) (define (sumFactorials maxNum) (sumFactIter 0 3)) (define (sumFactIter sum count) (cond ((= count (sigma (lambda x (factorial (remainder x 10))) nextNum zero? number)) (sumFactIter (+ sum count) (+ count 1))) ((= count maxNum) sum) (else sumFactIter sum (+ count 1)))) (define (sigma function next condition m) (if (condition m) 0 (+ (function m) (sigma function condition next (next m))))) (define (factorial x) (if (= x 1) 1 (* x (factorial (- 1 x))))) (define (nextNum y) (quotient y 10)) (define (zero? m) (= m 0))``````
lol LISP. Impressive.

#### Manyak

Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by BiG O lol LISP. Impressive.
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

#### metala

· Registered
Joined
·
1,225 Posts
Challenge: RSA
Language: PHP-CLI (Zend engine 2 + GMP extension)
Time wasted: Lots.. (~2 hours)

Code:
Code:
``````[CODE]
#!/usr/bin/php
<?php
/**
* RSA keys generation and simple crypt/decrypt
* metala <Marin Ivanov> - Overclock.net
*
*/

\$stdin = fopen('php://stdin', 'r');
\$stdout = fopen('php://stdout', 'w');
\$stderr = fopen('php://stderr', 'w');

abstract class RSA
{
static public function generateKeys(\$p = null, \$q = null)
{
if (!\$p || !gmp_prob_prime(\$p)) {
\$random = rand(100,9764)*9977664;
\$p = gmp_nextprime(\$random);
}
if (!\$q || !gmp_prob_prime(\$q)) {
\$random = rand(100,9764)*9977664;
\$q = gmp_nextprime(\$random);
}
\$n = gmp_mul(\$p, \$q);

\$fi = gmp_mul(gmp_sub(\$p, 1), gmp_sub(\$q, 1));
\$random = gmp_init(rand(23, 60));
\$e = gmp_div_q(gmp_mul(\$fi, \$random), 100);
\$gcdext = gmp_gcdext(\$e, \$fi);
\$d = \$gcdext['s'];
\$i = gmp_init(1);
while (gmp_cmp(gmp_gcd(\$e, \$fi), 1) != 0
|| gmp_cmp(\$d, 0) < 0
) {
\$gcdext = gmp_gcdext(\$e, \$fi);
\$d = \$gcdext['s'];
}
return array(\$n, \$e, \$d);
}
static public function encrypt(\$m, \$e, \$n)
{
return gmp_powm(\$m, \$e, \$n);
}
static public function decrypt(\$c, \$d, \$n)
{
return gmp_powm(\$c, \$d, \$n);
}
}

list(\$n, \$pub, \$priv) = RSA::generateKeys();
fwrite(\$stdout, 'n: '.gmp_strval(\$n).PHP_EOL);
fwrite(\$stdout, 'Public key: '.gmp_strval(\$pub).PHP_EOL);
fwrite(\$stdout, 'Private key: '.gmp_strval(\$priv).PHP_EOL.PHP_EOL);
fwrite(\$stdout, 'Enter message (number) to encrypt: ');
\$c = RSA::encrypt(\$input, \$pub, \$n);
fwrite(\$stdout, 'Encrypted message: '.gmp_strval(\$c).PHP_EOL);
\$nm = RSA::decrypt(\$c, \$priv, \$n);
fwrite(\$stdout, 'Decrypted ecrypted message: '.gmp_strval(\$nm).PHP_EOL);
?>``````
[/CODE]
I have error and sometimes \$d is not generated and the script returns an error, but it's 1/8 of the time. I'm kind of tried of all this. It took me like 2 hours to complete this and to read about "Modular multiplicative inverse" and the way to cope with "extended Euclidean algorithm".

I can say it's written from scratch and I haven't used any code sources

Quote:
 [email protected]:~/php\$ ./test.php n: 4871223152157154760299 Public key: 925532398883244883711 Private key: 2212633051444377131191 Enter message (number) to encrypt: 4567 Encrypted message:3147453702166190746057 Decrypted ecrypted message:4567
 Originally Posted by Manyak Choose p=1009 and q=3643. Find the sum of all values of e, 1