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 10  

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 #91 of 306
Hm looks like fun. Looking forward to the next challenge.
post #92 of 306
k info for beginner
post #93 of 306
I know I'm a little late but I was intrigued by the dictionary programming challenge after I did the brute force approach and found it not finishing after 1/2 hour on my aging AthlonXP laptop. So I changed it to use a HashMap and now it only takes about 8 secs to print the results. That surprised me to say the least.
Code:
import java.io.*;
import java.util.*;

public class Words{
public static String sort(String word){
char[] cwd=word.toCharArray();
Arrays.sort(cwd);
return new String(cwd);
}
public static void main (String args[]){
if(args.length!=2){
              System.out.println("Usage: java Words [filename_scrambled_words] [filename_wordlist]");
System.exit(0);
}
File scrambled=new File(args[0]);
File wordlist=new File(args[1]);
if(!scrambled.isFile()){
System.out.println(scrambled+" Not a file!");
System.exit(0);                              
}
if(!wordlist.isFile()){
System.out.println(wordlist+" Not a file!");
System.exit(0);
}                                                           
try{
BufferedReader brScram=new BufferedReader(new FileReader(scrambled));
BufferedReader brWords=new BufferedReader(new FileReader(wordlist));
String scrWord,goodWord;
HashMap dictMap=new HashMap();
while((goodWord=brWords.readLine())!=null){
goodWord=goodWord.trim();
String sortedGood=sort(goodWord);
LinkedList el=new LinkedList();                                      
if(dictMap.get(sortedGood)!=null)
el=(LinkedList)(dictMap.get(sortedGood));
el.add(goodWord);
dictMap.put(sortedGood,el);
}
int count=0;                                                                             
while((scrWord=brScram.readLine())!=null){
scrWord=scrWord.trim();
System.out.println("nSearching for: "+scrWord+"--n");
System.out.println("      Found: "+dictMap.get(sort(scrWord))+"n");
count++;
}                                                                             
System.out.println("     Searched : "+count+" scrambled words");
brWords.close();
brScram.close();
}catch(Exception e){
System.out.println("      Could not read file(s)!!! Exiting......"+e); 
System.exit(0);
}
}
}

Edited by Djibrille - 3/12/09 at 12:41pm
I5 2500k
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel I5 2500K Gigabyte GA-Z68X-UD3H-B3 Asus Strix Geforce GTX 970 8GB Corsair XMS3 1600 CL9 
Hard DriveOptical DriveCoolingOS
1x OCZ Vertex 3 120GB boot + 2xWD 2TB Caviar SE... LG BD Rewriter Thermalright True Spirit Windows 7 x64 
MonitorKeyboardPowerCase
HP ZR2440w Thermaltake eSports Meka Corsair HX620 Corsair Carbide 500R 
MouseMouse PadAudio
Mionix Avior SK SteelSeries 4D Asus Xonar D1 
  hide details  
I5 2500k
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel I5 2500K Gigabyte GA-Z68X-UD3H-B3 Asus Strix Geforce GTX 970 8GB Corsair XMS3 1600 CL9 
Hard DriveOptical DriveCoolingOS
1x OCZ Vertex 3 120GB boot + 2xWD 2TB Caviar SE... LG BD Rewriter Thermalright True Spirit Windows 7 x64 
MonitorKeyboardPowerCase
HP ZR2440w Thermaltake eSports Meka Corsair HX620 Corsair Carbide 500R 
MouseMouse PadAudio
Mionix Avior SK SteelSeries 4D Asus Xonar D1 
  hide details  
post #94 of 306
Final version of my java program takes ~6 secs to print the results(the ruby solution presented earlier here takes almost 13 secs on my sistem):
Code:
import java.io.*;
import java.util.*;

public class Words{
public static String sort(String word){
char[] cwd=word.toCharArray();
Arrays.sort(cwd);
return new String(cwd);
}
public static void main (String args[]){
if(args.length!=2){
System.out.println("Usage: java Words [filename_scrambled_words] [filename_wordlist]");
System.exit(0);
}
File scrambled=new File(args[0]);
File wordlist=new File(args[1]);
if(!scrambled.isFile()){
System.out.println(scrambled+" Not a file!");
System.exit(0);                              
}
if(!wordlist.isFile()){
System.out.println(wordlist+" Not a file!");
System.exit(0);
}                                                           
try{
BufferedReader brScram=new BufferedReader(new FileReader(scrambled));
BufferedReader brWords=new BufferedReader(new FileReader(wordlist));
String scrWord,goodWord;
HashMap<String,LinkedList<String>> dictMap=new HashMap<String,LinkedList<String>>();
while((goodWord=brWords.readLine())!=null){
goodWord=goodWord.trim();
String sortedGood=sort(goodWord);
LinkedList<String> el=new LinkedList<String>();                                      
if(dictMap.get(sortedGood)!=null)
el=dictMap.get(sortedGood);
el.add(goodWord);
dictMap.put(sortedGood,el);
}
int count=0;                                                                             
while((scrWord=brScram.readLine())!=null){
scrWord=scrWord.trim();
System.out.println("nSearching for: "+scrWord+"--n");
System.out.println("      Found: "+dictMap.get(sort(scrWord))+"n");
count++;
}                                                                             
System.out.println("     Searched : "+count+" scrambled words");
brWords.close();
brScram.close();
}catch(Exception e){
System.out.println("      Could not read file(s)!!! Exiting......"+e); 
System.exit(0);
}
}
}
I would have liked to compare the speed with the c solution of rabidgnome's but I can't get it to compile with gcc on my linux OS(something about a blank character i'm too lasy to try and fix it as is quite hard to follow c code).
Edited by Djibrille - 3/12/09 at 1:08pm
I5 2500k
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel I5 2500K Gigabyte GA-Z68X-UD3H-B3 Asus Strix Geforce GTX 970 8GB Corsair XMS3 1600 CL9 
Hard DriveOptical DriveCoolingOS
1x OCZ Vertex 3 120GB boot + 2xWD 2TB Caviar SE... LG BD Rewriter Thermalright True Spirit Windows 7 x64 
MonitorKeyboardPowerCase
HP ZR2440w Thermaltake eSports Meka Corsair HX620 Corsair Carbide 500R 
MouseMouse PadAudio
Mionix Avior SK SteelSeries 4D Asus Xonar D1 
  hide details  
I5 2500k
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel I5 2500K Gigabyte GA-Z68X-UD3H-B3 Asus Strix Geforce GTX 970 8GB Corsair XMS3 1600 CL9 
Hard DriveOptical DriveCoolingOS
1x OCZ Vertex 3 120GB boot + 2xWD 2TB Caviar SE... LG BD Rewriter Thermalright True Spirit Windows 7 x64 
MonitorKeyboardPowerCase
HP ZR2440w Thermaltake eSports Meka Corsair HX620 Corsair Carbide 500R 
MouseMouse PadAudio
Mionix Avior SK SteelSeries 4D Asus Xonar D1 
  hide details  
post #95 of 306
I tried copy/pasting my solution and I got the same thing, I think the forum is formatting something badly. Attached to this post is the code (rename to .c)

Never got around to doing that hash table
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
It goes to eleven
(13 items)
 
  
CPUMotherboardGraphicsRAM
E6300 DS3 EVGA 8600GTS 2GB XMS2 DDR2-800 
Hard DriveOSMonitorKeyboard
1.294 TB Arch Linux/XP Samsung 226bw Eclipse II 
PowerCaseMouse
Corsair 520HX Lian-Li v1000B Plus G7 
  hide details  
post #96 of 306
I just did some tests on my laptop.
Best results on my Java program: ~4.4 secs(this happens from second run onwards, os must be doing some caching, probably the dict file that's what takes the most time)
Best result on Rabid's c program:~1,5 secs(same thing here -- not the first run)
Wow, 3 times faster, i never beleived the difference would be so big. I could probably make it a little faster by removing some of the printing statements but I dont think it will ever be near as fast. That's something for the java developpers to think about, they claimed only 30% slower code comparing to C(maybe C++ I dont quite remember).
Anyway thanks rabid for the code! Nicely done!
I5 2500k
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel I5 2500K Gigabyte GA-Z68X-UD3H-B3 Asus Strix Geforce GTX 970 8GB Corsair XMS3 1600 CL9 
Hard DriveOptical DriveCoolingOS
1x OCZ Vertex 3 120GB boot + 2xWD 2TB Caviar SE... LG BD Rewriter Thermalright True Spirit Windows 7 x64 
MonitorKeyboardPowerCase
HP ZR2440w Thermaltake eSports Meka Corsair HX620 Corsair Carbide 500R 
MouseMouse PadAudio
Mionix Avior SK SteelSeries 4D Asus Xonar D1 
  hide details  
I5 2500k
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel I5 2500K Gigabyte GA-Z68X-UD3H-B3 Asus Strix Geforce GTX 970 8GB Corsair XMS3 1600 CL9 
Hard DriveOptical DriveCoolingOS
1x OCZ Vertex 3 120GB boot + 2xWD 2TB Caviar SE... LG BD Rewriter Thermalright True Spirit Windows 7 x64 
MonitorKeyboardPowerCase
HP ZR2440w Thermaltake eSports Meka Corsair HX620 Corsair Carbide 500R 
MouseMouse PadAudio
Mionix Avior SK SteelSeries 4D Asus Xonar D1 
  hide details  
post #97 of 306
I always knew Java was slow, but 3x times? Wow, I'm glad I decided to dumb Java early.
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
post #98 of 306
Dude I ain't going to do your homework!
    
CPUMotherboardGraphicsRAM
T9400 2.53Ghz OC 2.85Ghz Asus ATI Mobility Radeon HD 3650 OC 780/500 4GB PC2-6400 OC 900Mhz 
Hard DriveOSMonitor
WD 320GB @5400 Vista 32bit Home Premium 14" WXGA+ 
  hide details  
    
CPUMotherboardGraphicsRAM
T9400 2.53Ghz OC 2.85Ghz Asus ATI Mobility Radeon HD 3650 OC 780/500 4GB PC2-6400 OC 900Mhz 
Hard DriveOSMonitor
WD 320GB @5400 Vista 32bit Home Premium 14" WXGA+ 
  hide details  
post #99 of 306
Where did that come from?
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
Damit
(13 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x4 965 Black MSI 790FX-GD70 Asus ATI 5850 4x2 GBs RipJaw DDR3 1066 MHz 
Hard DriveOptical DriveOSMonitor
RAID 0 500 GB WD Black Lite-On Blue Ray, Samsung DVD Arch Linux/Ubuntu 10.04 25.5" Samsung 
KeyboardPowerCaseMouse
PS2 by Compaq 750 Watt COOLER MASTER Elite RC-332-KKN1-GP Death Adder 
Mouse Pad
Custom 
  hide details  
post #100 of 306
Here's portions of my implementation of the "scrambled text" challenge. This C# implementation stores a dictionary of the list of scrambled words that have a given "weight." The large file test executes in NUnit in around ~1.3 seconds.

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

namespace Scrambled
{
    public class ScrambledWord : IScrambledWord
    {
        private String scrambledLetters;    // As read from stream
        private int weight;                 // Summation of the character values in scrambledLetters

        public ScrambledWord(String scrambledLetters)
        {
            this.scrambledLetters = scrambledLetters;
            this.weight = CalculateWeight(scrambledLetters);
        }

        public bool LettersMatch(String text)
        {
            if (text.Length != scrambledLetters.Length) return false;
            for (int i = 0; i < scrambledLetters.Length; i++)
            {
                int index = text.IndexOf(scrambledLetters[i]);
                if (index == -1)
                    return false;
                text = text.Remove(index, 1);
            }
            return true;
        }

        public String Letters
        {
            get { return scrambledLetters; }
        }

        public int Weight
        {
            get { return weight; }
        }

        public static unsafe int CalculateWeight(String text)
        {
            int weight = 0;
            fixed (char* str = text)
            {
                for (int i = 0; i < text.Length; i++)
                    weight += str[i];
            }
            return weight;
        }

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

namespace Scrambled
{
    public class ScrambledWordList : IScrambledWordList
    {
        IDictionary<int /*weight*/, List<IScrambledWord> /*words with same weight*/> wordList;

        public ScrambledWordList()
        {
            wordList = new Dictionary<int, List<IScrambledWord>>();
        }

        public ScrambledWordList(IWordStream stream)
        {
            wordList = new Dictionary<int, List<IScrambledWord>>();
            String word;
            while ((word = stream.ReadWord()) != null)
                AddScrambledWord(new ScrambledWord(word));
        }

        public bool ContainsWord(String text)
        {
            int textWeight = ScrambledWord.CalculateWeight(text);
            List<IScrambledWord> list;
            if (wordList.TryGetValue(textWeight, out list) == false)
                return false;
            return AnyWordLettersMatch(list, text);
        }

        public void Add(IScrambledWord sw)
        {
            AddScrambledWord((ScrambledWord)sw);
        }

        void AddScrambledWord(ScrambledWord sw)
        {
            List<IScrambledWord> list;
            if (wordList.TryGetValue(sw.Weight, out list) == false)
            {
                list = new List<IScrambledWord>();
                wordList.Add(sw.Weight, list);
            }
            list.Add(sw);
        }

        bool AnyWordLettersMatch(List<IScrambledWord> list, String text)
        {
            int matches = 0;
            foreach (IScrambledWord sw in list)
            {
                // There could be many scrambled words 
                // that match the supplied text.
                if (sw.LettersMatch(text) == true)
                {
                    ++matches;
                    // This is wicked slow:
                    //Console.WriteLine(sw.Letters + " is " + text);
                }
            }
            return matches == 0 ? false : true;
        }
    }
}
Code:
// snip...

        [Test]
        public void ContainsWord_matches_in_huge_word_list()
        {
            IScrambledWordList scrambledList = 
                ScrambledWordListFactory.CreateWordList(
                    WordStreamFactory.CreateWordStream(GetManifestResourceStream("UnitTest.Resources.shuffle.txt")));
            IWordStream ws = 
                WordStreamFactory.CreateWordStream(GetManifestResourceStream("UnitTest.Resources.172K-words.txt"));
            String word;
            int count = 0;
            while ((word = ws.ReadWord()) != null)
                count += scrambledList.ContainsWord(word) ? 1 : 0;
            Assert.AreEqual(12877, count);
        }

Edited by Spotswood - 3/19/09 at 6:15pm
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)