# Programming Challenges!

10802 98
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 - 19 of 19 Posts

#### 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

#### 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?

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

#### Manyak

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

Awesome!

#### 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

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by metala I think you should fix: to: or It took me hours to understand what you mean, and I now understand how directly unconcealed was used, unconcealed is used as a synonym of unchanged. PS. After hours of thinking, the only way I found to check every possible e and every possible m for this e. That's why I'll try to do it in C, but some other day.
oops - that's a pretty big typo on my part!!

But yeah, unconcealed = unhidden = unencrypted = unchanged.

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
great work guys

^^That sum of even numbers is incorrect though. Follow the variables through the 1st loop:
y starts at 2
y becomes 4
z becomes 0+4

"2" is skipped!

a better loop would be:

Code:
Code:
``````int sum = 0;
for (int num = 0; num < 40000; num+=2)
{
sum+=num;
}
cout << sum;``````

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by Weedvender How do you guy do these things!? I can barely do this in math class.
believe it or not, programming them is actually easier than solving them on paper

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by Action Trey! Can we get some more challenges?
Sure, I'll start writing some up

I'll have them posted by tomorrow.

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by i_ame_killer_2 Question: What is gcd? Greatest common divider? and what is mod? Is it modulus (%)? I dont get the bold part either, lol
yes and yes

And the bold part are intervals:

[0, n-1]
is the same as
0 < x < n-1

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by rabidgnome229 Technically [0, n-1] is 0 <= x <= n-1. 0 < x < n-1 is (0, n-1). Not sure if that matters for the challenge
oops.....yeah its <=, not <.

I guess I'm not a morning person no matter how hard I try

But yeah it would matter. Well, the algorithm would work fine until you had to encrypt the number 0 or n-1, then I guess depending on your code it would either skip it, lock up, or give you some other weird behavior.

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by im_not_an_artard any new challenges on the way?
yeah sorry...been a hectic week for me, I've been slacking on all my homework and projects this semester and now I'm cramming everything into the last week

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by i_ame_killer_2 Guys, How do you calculate 545^503 in C++?

Code:

Code:
``````#include <math.h>

pow(545, 503);``````

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Then try

#include <cmath>

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Oh, lol.

First try using unsigned __int64, and if that's still not big enough then use a 'bignum' compatible library, like this one.

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
5 more puzzles have been added to the first post, and they should be a bit harder than the first set. Enjoy

#### Manyak

·
Joined
·
12,254 Posts
Discussion Starter · ·
Quote:
 Originally Posted by error10 Backtracking Sudoku looks interesting, though it hardly seems efficient. I could probably solve it by hand before the computer finishes. I think I'll try something else if you don't mind.
Sure thing, if its better then why not?

Though I'm not sure how much faster you can get it, a good backtracking algorithm can do it in under 1s. I'd still like to see what you come up with though

·