Programming Challenge - Page 10 - Overclock.net

xtascox · 10-30-08

Hm looks like fun. Looking forward to the next challenge.

MrDanny · 02-19-09

k info for beginner

Djibrille · 03-12-09

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

Djibrille · 03-12-09

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

rabidgnome229 · 03-12-09

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

Djibrille · 03-13-09

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!

GodofGrunts · 03-15-09

I always knew Java was slow, but 3x times? Wow, I'm glad I decided to dumb Java early.

Asus Mobile · 03-15-09

Dude I ain't going to do your homework!

GodofGrunts · 03-15-09

Where did that come from?

Spotswood · 03-18-09

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

		Overclock.net - Overclocking.net > Software, Programming and Coding > Coding and Programming
Programming Challenge

02-19-09	#92 (permalink)
MrDanny New to Overclock.net Join Date: Feb 2009 Posts: 59 Rep: 4 Unique Rep: 13 Trader Rating: 0	k info for beginner

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)