Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)
New Posts  All Forums:Forum Nav:

Programming Challenge (Out-of-Date) - Page 26  

Poll Results: Are you interested in participating in and/or helping organise and post these programming challenges?

 
  • 100% (2)
    I want to participate.
  • 0% (0)
    I want to contribute by helping posting and organise these challenges.
  • 0% (0)
    I'll only take part if other people are willing to participate.
  • 0% (0)
    I can help and participate - I love programming!
  • 0% (0)
    I do not wish to participate or help.
2 Total Votes  
post #251 of 306
Quote:
Originally Posted by xtascox View Post
I promise, I will find time to do another challenge.
You should they are fun . How goes OCNix?
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #252 of 306
Quote:
Originally Posted by Midpipps View Post
You should they are fun . How goes OCNix?
OCNix needs more man power
post #253 of 306
Hmm a new challenge going to stick with the easier ones for a little while to see if we can't get a few more people involved. this one should satisfy most people has sorting and has decently easy math.

Quote:
Number Chains

Given a number, we can form a number chain by
1. arranging its digits in descending order

2. arranging its digits in ascending order

3. subtracting the number obtained in (2) from the number obtained (1) to form a new number

4. and repeat these steps unless the new number has already appeared in the chain

Note that 0 is a permitted digit. The number of distinct numbers in the chain is the length of the chain. You are to write a program that reads numbers and outputs the number chain and the length of that chain for each number read.
The input consists of a sequence of positive numbers, all less than 10^9, each on its own line, terminated by 0. The input file contains at most 10 numbers.

The output consists of the number chains generated by the input numbers, followed by their lengths exactly in the format indicated below. After each number chain and chain length, including the last one, there should be a blank line. No chain will contain more than 1000 distinct numbers.

Sample Input

123456789
1234
444
0

Sample Output
Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 1234
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 4

Original number was 444
444 - 444 = 0
0 - 0 = 0
Chain length 2
Here is an example in case the write up is confusing.

Code:
Original number was 2134

1: arrange in ascending order  | 1234
2: arrange in descending order | 4321
3: subtract step 2 from step 1 | 4321 - 1234  = 3087

Repeat with new number of 3087
1: arrange in ascending order  | 0378
2: arrange in descending order | 8730
3: subtract step 2 from step 1 | 8730 - 0378 = 8352

Repeat this until the new number has already been seen as a calculate number
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #254 of 306
Here it is in scala.

Code:
def nc(inp:String, oldVal:List[Int], depth:Int) {    
  val big = inp.sorted.reverse.toInt
  val small = inp.sorted.toInt
  val newVal = big - small
  println(big + " - " + small + " = " + newVal + " at depth " + depth)
  if(oldVal.contains(newVal))
  { println("End of chain with depth " + depth);}
  else { nc(newVal.toString, newVal :: oldVal, depth+1) }
}

def compStr(inp:String) {  nc(inp, List(-1), 0); }

scala> compStr("123456789")
987654321 - 123456789 = 864197532 at depth 0
987654321 - 123456789 = 864197532 at depth 1
End of chain with depth 1

scala> compStr("444")      
444 - 444 = 0 at depth 0
0 - 0 = 0 at depth 1
End of chain with depth 1

scala> compStr("1234")
4321 - 1234 = 3087 at depth 0
8730 - 378 = 8352 at depth 1
8532 - 2358 = 6174 at depth 2
7641 - 1467 = 6174 at depth 3
End of chain with depth 3
Does anyone else's 8675309 get caught in a loop? Edit: fixed (Thanks Pipps)
Edited by impatient - 2/17/11 at 7:35am
post #255 of 306
man mine is ugly compared to Imps if there is a better way in java I do not know it.
Code:
import java.util.Arrays;
import java.util.Vector;
public class OCNTest {
public static void main(String [] args)
{
String startNumber = "8675309";
int chainLength = -1;
Vector<String> oldNumbers = new Vector<String>();
System.out.println("The original Number was " + startNumber);
while (oldNumbers.indexOf(startNumber) < 0){
chainLength += 1;
oldNumbers.add(startNumber);
char[] ascending = startNumber.toCharArray();
Arrays.sort(ascending);
String temp = new String(ascending);
startNumber = new String((Integer.parseInt(reverse(ascending)) - Integer.parseInt(temp)) + "");
System.out.println(reverse(ascending) + " - " + temp + " = " + startNumber + " depth=" + chainLength);
}
System.out.println("Chain length " + chainLength);
}

public static String reverse(char [] c){
for (int i = 0; i < (c.length/2); i ++){
char right = c[c.length - 1 - i];
c[c.length - 1 - i] = c[i];
c[i] = right;
}
return new String(c);
}
}
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
post #256 of 306
Pipps is on vacation this week, so I volunteered to post a problem. I found a fun problem in a Haskell book. I'm switching up the format a bit. I'm going to present the problem and have two possible different approaches in spoilers.

Quote:
Deciphering Caesar

The Caesar Shift Cipher is a way of encoding a string to hide the contents, by shifting the characters by a certain number of letters.

For example with a shift of one:

"YAY ROBOTS" -> "ZBZ SPCPUT"

For a shift of two:

"YAY ROBOTS" -> "ACA TQDQVU"

The challenge is, if given a block of text, encoded, how can you determine the shift size and get the original string.

Below are two links, one which contains the frequency of each letter in normal English and the other a list of the 2000 most common words in the English language(from who knows how long ago). I don't think either will help you out with "YAY ROBOTS" since neither yay or robots are in the 2000 most common words. They also have an unusual amount of different letters. For example, Y should appear with a frequency of 2%, whereas in the sample, it makes up 22% of the letters.

2000 most common words
Letter frequency

So.. the question is.. what does this text say?

SIO QCH U JLCTY. NBY ZYYFCHA IZ U DIV QYFF XIHY.



Build a program that can encode and decode strings, when passed a string and a shift number.

For example shiftMe("YAY ROBOTS", 1) should return "ZBZ SPCPUT"
And shiftMe("ZBZ SPCPUT", -1) should return "YAY ROBOTS"


Load the dictionary and see if you can find word matches when shifting. (If you're using YAY ROBOTS to test, add them ;p)





Build a function that will return the percentages of each letter as they are part of your string. For input, "ABCD", A->25% and B->25% and C->25%...

Learn some statistics. Wikipedia

In short, you will rotate the frequency list and see which shifted frequency table best fits with the frequency of letters in the sample.




As the size of the test data goes up, the more likely a match will occur.
EDIT: Just for the record, for frequency, the YAY ROBOTS won't work, but a shifted HURRAY ROBOTS will work just fine.






Edited by impatient - 3/3/11 at 10:49am
post #257 of 306
I wrote this during lunch last week. It does the frequency method and took a whole 19 lines of actual code.


Code:
//frequency of letters
val knownFreq = List(8.2f, 1.5f,2.8f,4.3f,12.7f,2.2f,2.0f,6.1f,7.0f,.2f,.8f,4.0f,2.4f,6.7f,7.5f,1.9f,.1f,6.0f,6.3f,9.1f,2.8f,1.0f,2.4f,.2f,2.0f,.1f);
val knFreq = knownFreq.zipWithIndex

//method to shift percentage estimates (for chi square test)
def shift(update : Map[Char,Float], sz:Int) : Map[Int,Float] = { for(i <- update) yield ((i._1.toInt - 97 + sz) % 26 -> i._2) }

//crack method
def crack(str:String): String =
{
  val original = str.toLowerCase
  //only include letters
  val sample = original.filter{i: Char => i != ' ' && i != '.' && i != ',' && i != '\\''}

  //get percentage each letter makes up of whole string
  var freq = (for(i <- sample.distinct) yield (i -> sample.count(_ == i).toFloat / sample.size)).toMap
  var bfData = Map[Double, Int]()

  /*
     loop that moves frequency generated above to try different letter values
  */
  for(i <- 0 to 25)
  {
    //actual shifting of frequency
    val mv = shift(freq, i)
    // (observed - expected)^2/ expected  
    val sumFit = (knFreq.map{ j => scala.math.pow( mv.getOrElse(j._2,0f) - j._1,2)/ j._1}).sum
    bfData = bfData + (sumFit -> i)
  }

  //best fit is the minimum of the sumFit value
  val bestFit = bfData.min._2
  println("Best guess at shift size is " + bestFit)

  //shift data the best fit number of letters
  //the shift function should be moved to its own method (the above shift should probably have a different name
  return original.map{ i =>  if(i != ' ' && i != '.' && i!= ',' && i != '\\'') { ((i -97 + bestFit) % 26 + 97).toChar;} else { i } }
}


More samples:
Code:
crack("YJGP, KP VJG EQWTUG QH JWOCP GXGPVU, KV DGEQOGU PGEGUUCTA HQT QPG RGQRNG VQ FKUUQNXG VJG RQNKVKECN DCPFU YJKEJ JCXG EQPPGEVGF VJGO YKVJ CPQVJGT, CPF VQ CUUWOG COQPI VJG RQYGTU QH VJG GCTVJ, VJG UGRCTCVG CPF GSWCN UVCVKQP VQ YJKEJ VJG NCYU QH PCVWTG CPF QH PCVWTG'U IQF GPVKVNG VJGO, C FGEGPV TGURGEV VQ VJG QRKPKQPU QH OCPMKPF TGSWKTGU VJCV VJGA UJQWNF FGENCTG VJG ECWUGU YJKEJ KORGN VJGO VQ VJG UGRCTCVKQP.");


crack("UFCL, GL RFC AMSPQC MD FSKYL CTCLRQ, GR ZCAMKCQ LCACQQYPW DMP MLC NCMNJC RM BGQQMJTC RFC NMJGRGAYJ ZYLBQ UFGAF FYTC AMLLCARCB RFCK UGRF YLMRFCP, YLB RM YQQSKC YKMLE RFC NMUCPQ MD RFC CYPRF, RFC QCNYPYRC YLB COSYJ QRYRGML RM UFGAF RFC JYUQ MD LYRSPC YLB MD LYRSPC'Q EMB CLRGRJC RFCK, Y BCACLR PCQNCAR RM RFC MNGLGMLQ MD KYLIGLB PCOSGPCQ RFYR RFCW QFMSJB BCAJYPC RFC AYSQCQ UFGAF GKNCJ RFCK RM RFC QCNYPYRGML.");

//warning... not english
crack("NQTGO KRUWO FQNQT UKV COGV, EQPUGEVGVWT CFKRKUKEKPI GNKV, UGF FQ GKWUOQF VGORQT KPEKFKFWPV WV NCDQTG GV FQNQTG OCIPC CNKSWC. WV GPKO CF OKPKO XGPKCO, SWKU PQUVTWF GZGTEKVCVKQP WNNCOEQ NCDQTKU PKUK WV CNKSWKR GZ GC EQOOQFQ EQPUGSWCV. FWKU CWVG KTWTG FQNQT KP TGRTGJGPFGTKV KP XQNWRVCVG XGNKV GUUG EKNNWO FQNQTG GW HWIKCV PWNNC RCTKCVWT. GZEGRVGWT UKPV QEECGECV EWRKFCVCV PQP RTQKFGPV, UWPV KP EWNRC SWK QHHKEKC FGUGTWPV OQNNKV CPKO KF GUV NCDQTWO");
Frequency clarification:

For the frequency solution, you use the chi square analysis to determine the best fitting data. It works surprisingly well, even for some non-english data.

The list given for letter frequency is the expected value. If you compare the expected value and the given value, the one that is closest overall, will have the lowest sum.

The formula is (observed-expected)^2/expected summed over all the frequencies.

For example if we have the sample text "fcf" and want to run through a couple iterations, here is what we have.
f's make up 66% of the values
and
c makes up 33% of the letters.

//abc frequency (expected values)
[8.2f, 1.5f,2.8f,4.3f,12.7f,2.2f,2.0f,6.1f,7.0f,.2f,.8f,4 .0f,2.4f,6.7f,7.5f,1.9f,.1f,6.0f,6.3f,9.1f,2.8f,1. 0f,2.4f,.2f,2.0f,.1f]

//observed values
Run one(shift 0):
[0,0,.33f,0,0,.66f, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] => 98.54167
Run two(shift 1):
[0,0,0,.33f,0,0,.66f, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] => 98.54806
Run three(shift 2):
[0,0,0,0,.33f,0,0,.66f, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] => 98.38160
...

As you can see, the frequencies are moving across the board. The proper shift is the run with lowest value when the function is applied. For a perfect match, the formula would return 0, since the expected and observed are the same (expected - observed)^2/expected == 0. For the above sample, a shift of 2 has the value of 98.38160979033131, which is the lowest of any values. So f+2 = h and c + 2 = e yields "heh" when shifted.
Edited by impatient - 3/7/11 at 9:44am
post #258 of 306
Hi,

This my attempt at using a dictionary method using C# - it's not just ugly, it's PUGLY and bloated. But...it works

Code:
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

static void Main(string[] args)
        {
SearchText("SIO QCH U JLCTY. NBY ZYYFCHA IZ U DIV QYFF XIHY.");
}

 private static void SearchText(string text)
        {
            int searchIndex = 0;            
            List<string> wordList = new List<string>();
            List<string> dictionaryList = new List<string>();
            List<int> foundIterations = new List<int>();
            while (searchIndex != 26)
            {
                string Result = ShiftText(text, searchIndex);                
                wordList = buildwordList(Result);
                dictionaryList = buildwordList("2000.txt", true);
                List<string> fI = new List<string>();
                bool foundMatch = false;
                foreach (string word in wordList)
                {
                    foreach (string dWord in dictionaryList)
                    { 
                        if (word == dWord)
                        {
                            foundMatch = true;
                            fI.Add(word);
                        }
                    }
                }
                if (foundMatch == true)
                {
                    Console.WriteLine("Match found:");
                    Console.WriteLine(Result);
                    Console.WriteLine("Iteration:" + searchIndex.ToString());
                    Console.WriteLine("Do you wish to see the matched words?");
                    System.ConsoleKey A = Console.ReadKey().Key;
                    if (A == ConsoleKey.Y)
                    {
                        Console.Write("\
");
                        foreach (string f in fI)
                        {
                            Console.Write(f + " ");
                        }
                        Console.Write("\
");
                        Console.WriteLine("Press any key.");
                        Console.ReadKey();
                    }

                }
                searchIndex = searchIndex + 1;
            
            }
            
            Console.WriteLine("End");
            Console.ReadKey();
        }


private static string ShiftText(string text, int shiftVal)
        {
            string textResult = "";
            string alphaBet = "abcdefghijklmnopqrstuvwxyz";
            char[] alphaChar = alphaBet.ToCharArray();            
            char[] charText = text.ToLower().ToCharArray();
            char nVal;
            List<char> charResult = new List<char>();
            foreach (char charVal in charText)
            {
                int alphaPosCount = 0;
                int foundPos = 0;
                bool foundVal = false;
                List<char> Results = new List<char>();
                foreach (char charTestVal in alphaChar)
                {
                    //Console.WriteLine(charVal.ToString() + " > " + charTestVal.ToString());
                    if (charVal == charTestVal)
                    {
                        foundPos = alphaPosCount;
                        foundVal = true;
                    }
                    
                    alphaPosCount = alphaPosCount + 1;
                }
                if (foundVal == true)
                {
                    int tVal = foundPos + shiftVal;
                    if (tVal > 25) tVal = (tVal - 26);
                     nVal = alphaChar[tVal];
                    //Console.WriteLine(charVal.ToString() + " is now " + nVal.ToString());
                    //Console.ReadKey();
                }
                else
                {
                     nVal = charVal;
                }
                charResult.Add(nVal);
                    
                
                
            }
            foreach (char charVal in charResult)
            {
                textResult = textResult + charVal;
            }
            //Console.Write("\
Process complete.");
            //Console.ReadKey();
            return textResult;
        }

       
        private static List<string> buildwordList(string wordList)
        {
            List<string> results = new List<string>();
            string[] Words = wordList.Split(' ');
            
            foreach (string word in Words)
            {
                results.Add(word);
                //Console.WriteLine(word);
            }
            //Console.ReadKey();
            return results;            
        }

        private static List<string> buildwordList(string fileName, bool fileLoadFlag)
        {
            System.IO.StreamReader file = new System.IO.StreamReader(fileName);
            List<string> results = new List<string>();
            string Res = file.ReadToEnd();
            string[] words = Res.Split('\
');
            foreach (string word in words)
            {   
                results.Add(word);
            }
            //Console.ReadKey();
            return results;
        }
post #259 of 306
After looking through this thread for the first time I've come to the conclusion that my education is seriously lacking...
OC Beast
(13 items)
 
  
CPUMotherboardGraphicsRAM
E8500 @4GHZ Gigabyte P45 4850x2 2GB IT LIVES! 4GB 
Hard DriveOptical DriveOSMonitor
500AAKS+250external CD-DVD combo windows 7 ultimate x64 26" 
KeyboardPowerCaseMouse
MC$ wireless 650w corsair antec 900 Logitech battlefield 2142 G5 
  hide details  
OC Beast
(13 items)
 
  
CPUMotherboardGraphicsRAM
E8500 @4GHZ Gigabyte P45 4850x2 2GB IT LIVES! 4GB 
Hard DriveOptical DriveOSMonitor
500AAKS+250external CD-DVD combo windows 7 ultimate x64 26" 
KeyboardPowerCaseMouse
MC$ wireless 650w corsair antec 900 Logitech battlefield 2142 G5 
  hide details  
post #260 of 306
Quote:
Originally Posted by ZTR1760 View Post
After looking through this thread for the first time I've come to the conclusion that my education is seriously lacking...
Nah they are alot of fun if I get time I would like to get back to posting these again. I have just been busy lately. I think if you actually sat down and did them you would get them pretty quickly alot of them sound harder then they actually are
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
    
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2 
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide 
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel 
Mouse Pad
RocketFish 
  hide details  
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
This thread is locked  
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)