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 7  

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 #61 of 306
The Challenge:
Create a program that takes a given list of scrambled words and searches a given word list and figures out what the scrambled words are.


Here are a few scrambled words that you can use to test with:
Code:
    hmyaaa
    lengod
    ouothns
    gitesnt
    nkpinu
    ikedoo
    pwtsaeee
    seengis
    shesinun
    brhoapeo
The attached file wordlist.txt contains a large list of words and the scrambled words above can be found in that file.


Like last challenge, you can either give the scrambled words to your program as parameters or from a file.

Creativity, efficiency and elegance are weighed to decide the winner.

Any language is welcome.


Deadline:
Wednesday August 7th at 5:00pm EST.

I'll continue to plan to post another challenge Thursday's at 8:00pm ish EST.


Post any questions you have.
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
post #62 of 306
Quote:
Originally Posted by dangerousHobo View Post
The Challenge:
Create a program that takes a given list of scrambled words and searches a given word list and figures out what the scrambled words are.


Here are a few scrambled words that you can use to test with:
Code:
    hmyaaa
    lengod
    ouothns
    gitesnt
    nkpinu
    ikedoo
    pwtsaeee
    seengis
    shesinun
    brhoapeo
The attached file wordlist.txt contains a large list of words and the scrambled words above can be found in that file.


Like last challenge, you can either give the scrambled words to your program as parameters or from a file.

Creativity, efficiency and elegance are weighed to decide the winner.

Any language is welcome.


Deadline:
Wednesday August 7th at 5:00pm EST.

I'll continue to plan to post another challenge Thursday's at 8:00pm ish EST.


Post any questions you have.
There are things that are not words in your wordlist.
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 #63 of 306
Attached is a zipped text file containing 172,000 actual words. We used it for a dictionary building program and it can serve as a stress test. I also attached a couple smaller dictionaries because a naive implementation will take an extremely long time on the 172,000 word dictionary
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 #64 of 306
Here's my entry

Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUFF_SIZE 1024

typedef struct List_Node_t{
char *word;
struct List_Node_t *next;
}ListNode;

typedef struct Trie_Node_t{
struct Trie_Node_t *children[26];
ListNode *head;
}TrieNode;


/* function prototypes */
void trim(char *string);
void insert(char *string, TrieNode *node);
void printScrambles(char *string, TrieNode *node);
int char_cmp(const void *c1, const void *c2);
void insertRec(char *word, char *sorted, TrieNode *node, int index);
void insertAtHead(ListNode **head, char *word);
void printRec(TrieNode *node, char *sorted, int index);

void printAll(TrieNode *node);

int main(int argc, char **argv){
//pathnames of input files
char *dictfile = "wordlist.txt", *listfile = "scrambles.txt";
FILE *infile; //handle to currently open file
char buffer[BUFF_SIZE]; //read buffer;
TrieNode *head = calloc(1, sizeof(TrieNode));

if(argc > 1){
dictfile = argv[1];
}
if(argc > 2){
listfile = argv[2];
}

infile = fopen(dictfile, "r");
if(!infile){
printf("Unable to open %s.  Exitingn");
exit(1);
}

//read words and insert into dictionary
while(fgets(buffer, BUFF_SIZE, infile)){
trim(buffer);
insert(buffer, head);
}

fclose(infile);
fopen(listfile, "r");
if(!infile){
printf("Unable to open %s.  Exitingn");
exit(1);
}

//find matches and print
while(fgets(buffer, BUFF_SIZE, infile)){
trim(buffer);
//printf("Unscrambling |%s|n", buffer);
printScrambles(buffer, head);
} 

return 0;
}

/* 
 * Trims non-letter characters from end of a string
 */
void trim(char *string){
char *ptr;
for(ptr = string; ((*ptr >= 'a') && (*ptr <= 'z')) || ((*ptr >= 'A') && (*ptr <= 'Z')); ptr++);
*ptr = '';
}

/*
 * inserts given word into trie
 */
void insert(char *string, TrieNode *node){
char *sorted = calloc(strlen(string) + 1, sizeof(char));
strcpy(sorted, string);
qsort(sorted, strlen(sorted), sizeof(char), char_cmp);

char *copy = calloc(strlen(string) + 1, sizeof(char));
strcpy(copy, string);

//printf("-Inserting |%s| |%s|n", copy, sorted);
insertRec(copy, sorted, node, 0);
}

/*
 * compares two characters
 * for qsort
 */
int char_cmp(const void *c1, const void *c2){
return (*((char *)c1) - *((char *)c2));
}

/*
 * recursive method that inserts a word into the trie
 */
void insertRec(char *word, char *sorted, TrieNode *node, int index){
if(!sorted[index]){
//printf("-Targer node found.  Insertingn");
insertAtHead(&(node->head), word);
free(sorted);
return;
}

int trieIndex = (sorted[index] < 'a') ? (sorted[index] - 'A') : (sorted[index] - 'a');
//printf("-Looking at letter |%c|, index |%d|n", sorted[index], trieIndex);
if(!(node->children[trieIndex])){
//printf("-No Node found, creating newn");
node->children[trieIndex] = calloc(1, sizeof(TrieNode));
}

insertRec(word, sorted, node->children[trieIndex], index+1);
}

/*
 * inserts word into head of linked list of ListNodes
 */
void insertAtHead(ListNode **head, char *word){
ListNode *node = calloc(1, sizeof(ListNode));
node->word = word;
node->next = *head;
*head = node;
}

/*
 * prints words matching given scramble
 */
void printScrambles(char *string, TrieNode *node){
//printf("Sorting/copying %sn", string);
char *sorted = calloc(strlen(string) + 1, sizeof(char));
strcpy(sorted, string);
//printf("String copiedn");
qsort(sorted, strlen(sorted), sizeof(char), char_cmp);
//printf("String sortedn");

printf("Matches for %s: ", string);
printRec(node, sorted, 0);
free(sorted);
}

/* 
 * recursive method to trawl trie for matches
 */
void printRec(TrieNode *node, char *sorted, int index){
//printf("Looking at |%s| index |%d| character |%c|n", sorted, index, sorted[index]);

if(!(sorted[index])){
if(!node->head){
printf("No matches foundn");
}else{
ListNode *ptr;
for(ptr = node->head; ptr; ptr = ptr->next)
printf("%s, ", ptr->word);

printf("n");
}
}else{
int trieIndex = (sorted[index] < 'a') ? (sorted[index] - 'A') : (sorted[index] - 'a');
if(node->children[trieIndex])
printRec(node->children[trieIndex], sorted, index+1);
else{
printf("No matches foundn");
return;
}
}
}

void printAll(TrieNode *node){
ListNode *ptr;
for(ptr = node->head; ptr; ptr = ptr->next){
printf("%sn", ptr->word);
}

int i;
for(i=0; i<26; i++){
if(node->children[i])
printAll(node->children[i]);
}
}
If no command line arguments are given it looks for words in wordlist.txt and targets in scrambles.txt. If one argument is given it assumes that the given filename specifies the dictionary to be used. If two arguments are given it assumes the given filename specifies a file containing words to unscramble.

It only works for words made from letters, but its fast as hell
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 #65 of 306
stop posting solutions so fast!
RAWR
(13 items)
 
Home Server
(11 items)
 
 
CPUMotherboardGraphicsRAM
i7-4790k msi z97 gaming 7 gtx 760 4gb 32GB GSkill  
Hard DriveHard DriveCoolingOS
Kingston HyperX 3K 120GB SSD Hitachi 2TB Cooler Master Hyper 212+ Windows 8.1 Pro 
MonitorKeyboardPowerCase
Vizio M492-b2 Logitech Wireless  Corsair HX620 NZXT Phantom White 
Mouse
Logitech Wireless 
  hide details  
RAWR
(13 items)
 
Home Server
(11 items)
 
 
CPUMotherboardGraphicsRAM
i7-4790k msi z97 gaming 7 gtx 760 4gb 32GB GSkill  
Hard DriveHard DriveCoolingOS
Kingston HyperX 3K 120GB SSD Hitachi 2TB Cooler Master Hyper 212+ Windows 8.1 Pro 
MonitorKeyboardPowerCase
Vizio M492-b2 Logitech Wireless  Corsair HX620 NZXT Phantom White 
Mouse
Logitech Wireless 
  hide details  
post #66 of 306
This is what I came out with last night using my word list. I'll try going through and seeing if it'll work with the others. I wrote it in perl too but its not 100% complete.

Code:
#!/usr/bin/env ruby

unless ARGV[0] 
    puts "Usage: ruby wordsort.rb [word_1 word_2 ...]"
    exit 0
end

scram_words = ARGV.compact.map {|x| x.split(//).sort.join}

File.open("wordlist.txt").each do |word|
    word.chop!
    scram_words.each {|scram| p word if word.split(//).sort.join == scram}
end
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
post #67 of 306
Attached is a file containing ~10K scrambled words. The words are in both 42K-words.txt and 172K-words.txt
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 #68 of 306
Updated code handle the input being two files

Code:
#!/usr/bin/env ruby


unless ARGV.size == 2
    puts "Usage: ruby wordsort.rb scram_file wordlist_file"
    exit 0
end

scram = Array.new
File.open(ARGV[0]).each do |word|
    scram << word.chop.split(//).sort.join
end

File.open(ARGV[1]).each do |word|
    word.chop!
    (0...scram.size).each { |i| 
        if word.split(//).sort.join == scram[i]
            p word 
            scram.delete_at i
            break
        end
    }
end
Using my wordlist and a scrambled list of 10 words:
Code:
time ruby wordsort.rb scram.txt wordlist.txt         
real    0m0.082s
user    0m0.076s
sys     0m0.000s
Using the big list: (haha kind of sad)
Code:
 
time ruby wordsort.rb shuffle.txt 172K-words.txt   
real    35m27.748s
user    30m21.790s
sys     0m5.708s
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
post #69 of 306
A few changes for improvements
Still nothing to impressive..

Code:
#!/usr/bin/env ruby

unless ARGV.size == 2
    puts "Usage: ruby wordsort.rb scram_file wordlist_file"
    exit 0
end

scram = Array.new
real = Array.new

File.open(ARGV[0]).each do |word|
    scram << word.chop.split(//).sort.join
end

File.open(ARGV[1]).each do |word|
    real << word.chop    
end

scram.sort!
real.sort!

real.each do |word|
    sword = word.split(//).sort.join
    (0...scram.size).each do |i| 
        break if sword[0] < scram[i][0]
        if sword == scram[i]
            p word 
            scram.delete_at i
            break
        end
    end
end
Code:
time ruby wordsort.rb scram.txt wordlist.txt         
real    0m0.024s
user    0m0.024s
sys     0m0.000s
Code:
time ruby wordsort.rb shuffle.txt 172K-words.txt   
real    10m55.095s
user    10m54.685s
sys     0m0.376s
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
BlackMesa
(14 items)
 
  
CPUMotherboardGraphicsRAM
Phenom II x6 Gigabyte XFX RF460 16gb G.Skill 
Hard DriveHard DriveOSMonitor
OCZ Vertex2 Sata II Coorsair Force GS Sata III Debian (testing) Shimian 27" 
KeyboardMouse
Filco w/ blue cherries Who needs a mouse? 
  hide details  
post #70 of 306
Quote:
Originally Posted by dangerousHobo View Post
Updated code handle the input being two files

Using my wordlist and a scrambled list of 10 words:
Code:
time ruby wordsort.rb scram.txt wordlist.txt         
real    0m0.082s
user    0m0.076s
sys     0m0.000s
Using the big list: (haha kind of sad)
Code:
 
time ruby wordsort.rb shuffle.txt 172K-words.txt   
real    35m27.748s
user    30m21.790s
sys     0m5.708s
Rofl - yeah that's the problem with the easy way. It has to check every shuffled word against every word in the dictionary.

I used a trie for this, which is actually kinda nifty. A trie is a tree where the head node represents an empty string. Hanging off of that are 26 nodes (one for each letter). The first node corresponds to a string containing 'a' as the first letter. Hanging off of that are 26 nodes, where the first node represents a string containing 'aa', the second represents 'ab', and so on. The end result is that when you're matching a shuffled word, it doesn't depend on the number of words you're checking against, only the length of the shuffled word. It takes just as long to find the word using a dictionary of 10 words as it does with a dictionary of 10 million words.
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  
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)