Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge #8 (challenges for both beginners and experts)
New Posts  All Forums:Forum Nav:

Programming Challenge #8 (challenges for both beginners and experts) - Page 3

post #21 of 42
Okay, thanks. smile.gif
post #22 of 42
Quote:
Originally Posted by JacP3 View Post

Sounds like a lot of fun to try and do! But I am confused as to how you can get the program to find real words, rather than just random letters to fill in the gaps. I use Liberty Basic, and I am also learning C++. Sorry if this sounds like a stupid question, I am 12 and haven't done programming for quite a while.

That's a great question!

You need to use a dictionary file. One is provided for you in the OP.
It contains a list of English (in this case) words.

You can loop through the file one word at a time and use that as your fill in, instead of random letters.
post #23 of 42
Thread Starter 
A one line solution (easy challenge) for the Linux nerds: (Click to show)
Code:
pattern="??t??m"; grep -iw `echo $pattern | sed 's/\?/./g'` english.0 | grep -Pv "[']"
post #24 of 42
edit: Finished offline version.
Quote:
C#
Offline Version

Crossword Solver (Hardest).zip 45k .zip file

Code is included in ZIP (open with any text editor or IDE).
*Requires .NET 4.0 (Windows XP SP3 or higher).
*Requires data files located here:


A Pile of Code (Click to show)
Code:
using System;
using System.Collections.Generic;
using System.Windows.Forms;
using System.IO;
using System.Linq;
using System.Net;

namespace Crossword_Solver
{
    public partial class frmMain : Form
    {
        string FileNameDict = "dict.txt";
        string FileNameThes = "thes.txt";
        
        List<string> DictWords = new List<string>();
        List<string> ThesWords = new List<string>();

        #region Class: Answer
        private class Answer
        {
            public Answer()
            {
                Match = -1;
            }

            public string Word { get; set; }
            public double Match { get; set; }

            public string MatchString()
            {
                return (Match == -1) ? "N/A" : Match.ToString("N0") + "%";
            }
        }
        #endregion

        #region Constructor
        public frmMain()
        {
            InitializeComponent();
        }
        #endregion

        #region Form => Load
        private void frmMain_Load(object sender, EventArgs e)
        {
            tbInput.Text = Properties.Settings.Default.LastSearch;
            tbInputHint.Text = Properties.Settings.Default.LastHint;

            try
            {
                DictWords = File.ReadAllLines(FileNameDict).ToList();                
                ThesWords = File.ReadAllLines(FileNameThes).ToList();
            }
            catch(Exception ex)
            {
                MessageBox.Show(ex.Message, "Error", MessageBoxButtons.OK, MessageBoxIcon.Error);
                Environment.Exit(-1);
            }
        }
        #endregion

        #region Form => Closing
        private void frmMain_FormClosing(object sender, FormClosingEventArgs e)
        {
            Properties.Settings.Default.LastSearch = tbInput.Text;
            Properties.Settings.Default.LastHint = tbInputHint.Text;
            Properties.Settings.Default.Save();
        }
        #endregion

        #region Button Help => Click
        private void btnHelp_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Crossword Solver" + Environment.NewLine +
                            "© Kenny Parker, 2013. All rights reserved." + Environment.NewLine + Environment.NewLine +
                            "Enter in any word with missing letters to show all posibilities." + Environment.NewLine +
                            "Replace empty letters with \"?\"." + Environment.NewLine + 
                            "Example: pr_g_am = pr?g?am ",
                            "Help", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }
        #endregion

        #region Button HelpHint => Click
        private void btnHelpHint_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Crossword Solver" + Environment.NewLine +
                "© Kenny Parker, 2013. All rights reserved." + Environment.NewLine + Environment.NewLine +
                "Enter in any hint that is provided to you." + Environment.NewLine +
                "This might narrow the word results down even further!",
                "Help", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }
        #endregion

        //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

        #region Button Search => Click
        private void btnSearch_Click(object sender, EventArgs e)
        {
            FindAnswer();
        }
        #endregion

        #region FindAnswer
        private void FindAnswer()
        {
            btnSearch.Enabled = false;
            lvOutput.Items.Clear();

            var words = new List<Answer>();

            words = SearchWords(tbInput.Text);

            if (words.Count < 1)
            {
                lvOutput.Items.Add("No matches found!");
            }
            else
            {
                if (!string.IsNullOrWhiteSpace(tbInputHint.Text))
                    MatchWords(words);

                words.ForEach(word => lvOutput.Items.Add(new ListViewItem(new string[] { word.Word, word.MatchString() })));

                lvOutput.Columns[1].ListView.Sorting = SortOrder.Descending;
            }

            btnSearch.Enabled = true;
        }
        #endregion

        #region SearchWords
        private List<Answer> SearchWords(string input)
        {
            var wordMatches = new List<Answer>();

            input = tbInput.Text.ToLower();

            //Loop over all dictionary words.
            for (int w = 0; w < DictWords.Count; w++)
            {
                //Exclude any words that aren't same length.
                if (DictWords[w].Length == input.Length)
                {
                    DictWords[w] = DictWords[w].ToLower();

                    int letterMatches = 0;

                    //Loop over each character in dictionary word.
                    for (int l = 0; l < DictWords[w].Length; l++)
                    {
                        if ((input[l] == '?' || DictWords[w][l] == input[l]) && char.IsLetter(DictWords[w][l])) letterMatches++;
                    }

                    if (letterMatches == input.Length) wordMatches.Add(new Answer { Word = DictWords[w] });
                }
            }

            return wordMatches;
        }
        #endregion

        #region MatchWords
        private List<Answer> MatchWords(List<Answer> words)
        {           

            //Format the given hint.
            var hints = tbInputHint.Text.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);

            //Loop over every possible word answer.
            for (int w = 0; w < words.Count; w++)
            {
                string thesMatch = "";

                //Search thesaurus for any lines that have the word in it.
                foreach (var thesWord in ThesWords)
                {
                    if (thesWord.Contains(words[w].Word)) thesMatch += thesWord;
                }

                int match = 0;

                //Search all thesaurus lines for hint.
                foreach (var hint in hints)
                {
                    if (thesMatch.Contains(hint))
                    {
                        match++;
                    }
                }
                
                words[w].Match = (((double)match / (double)hints.Length) * 100.0);                
            }

            return words;
        }
        #endregion        
    }
}

This one uses an API call to a thesaurus website and looks for hint matches.
If you leave the hint blank, it won't match but still show possible word answers.

I only have a free API account, so that limits me to 1,000 calls per day (each possible word = 1 call).
So please don't just spam the program with the hint box filled in.
You can spam it all you want with the hint box empty though.

Quote:
C#
Online Version

Crossword Solver (Hardest).zip 167k .zip file

Code is included in ZIP (open with any text editor or IDE).
*Requires .NET 4.0 (Windows XP SP3 or higher).

A Pile of Code (Click to show)
Code:
using System;
using System.Collections.Generic;
using System.Windows.Forms;
using System.IO;

using System.Linq;

using System.Net;

namespace Crossword_Solver
{
    public partial class frmMain : Form
    {
        string FileNameDic = "dic.txt";
        //string FileNameDef = "def.txt";

        //These are my personal keys. Don't use them anywhere else.
        //string OldTheKey = "73771fa2acccd3e59376ebee56264f7b";
        //string DicKey = "5be9fbe2-1d64-4c1d-b86e-272378c895bb";
        string TheKey = "33fbec67-d850-43b5-ab43-55898984295a";

        List<string> DicWords = new List<string>();
        List<string> Definitions = new List<string>();

        #region Class: Answer
        private class Answer
        {
            public Answer()
            {
                Match = -1;
            }

            public string Word { get; set; }
            public double Match { get; set; }

            public string MatchString()
            {
                return (Match == -1) ? "N/A" : Match.ToString("N0") + "%";
            }
        }
        #endregion

        #region Constructor
        public frmMain()
        {
            InitializeComponent();
        }
        #endregion

        #region Form => Load
        private void frmMain_Load(object sender, EventArgs e)
        {
            tbInput.Text = Properties.Settings.Default.LastSearch;
            tbInputHint.Text = Properties.Settings.Default.LastHint;

            try
            {
                DicWords = File.ReadAllLines(FileNameDic).ToList();
                //Using web instead.
                //Definitions = File.ReadAllLines(FileNameDef).ToList();
            }
            catch(Exception ex)
            {
                MessageBox.Show(ex.Message, "Error", MessageBoxButtons.OK, MessageBoxIcon.Error);
                Environment.Exit(-1);
            }
        }
        #endregion

        #region Form => Closing
        private void frmMain_FormClosing(object sender, FormClosingEventArgs e)
        {
            Properties.Settings.Default.LastSearch = tbInput.Text;
            Properties.Settings.Default.LastHint = tbInputHint.Text;
            Properties.Settings.Default.Save();
        }
        #endregion

        #region Button Help => Click
        private void btnHelp_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Crossword Solver" + Environment.NewLine +
                            "© Kenny Parker, 2013. All rights reserved." + Environment.NewLine + Environment.NewLine +
                            "Enter in any word with missing letters to show all posibilities." + Environment.NewLine +
                            "Replace empty letters with \"?\"." + Environment.NewLine + 
                            "Example: pr_g_am = pr?g?am ",
                            "Help", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }
        #endregion

        #region Button HelpHint => Click
        private void btnHelpHint_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Crossword Solver" + Environment.NewLine +
                "© Kenny Parker, 2013. All rights reserved." + Environment.NewLine + Environment.NewLine +
                "Enter in any hint that is provided to you." + Environment.NewLine +
                "This might narrow the word results down even further!",
                "Help", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }
        #endregion

        //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

        #region Button Search => Click
        private void btnSearch_Click(object sender, EventArgs e)
        {
            FindAnswer();
        }
        #endregion

        #region FindAnswer
        private void FindAnswer()
        {
            btnSearch.Enabled = false;
            lvOutput.Items.Clear();

            var words = new List<Answer>();

            words = SearchWords(tbInput.Text);

            if (words.Count < 1)
            {
                lvOutput.Items.Add("No matches found!");
            }
            else
            {
                if (!string.IsNullOrWhiteSpace(tbInputHint.Text))
                    MatchWords(words);

                words.ForEach(word => lvOutput.Items.Add(new ListViewItem(new string[] { word.Word, word.MatchString() })));

                lvOutput.Columns[1].ListView.Sorting = SortOrder.Descending;
            }

            btnSearch.Enabled = true;
        }
        #endregion

        #region MatchWords
        private List<Answer> MatchWords(List<Answer> words)
        {
            var hints = tbInputHint.Text.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);

            for (int w = 0; w < words.Count; w++)
            {
                var html = new WebClient()
                    .DownloadString("http://www.dictionaryapi.com/api/v1/references/thesaurus/xml/" + words[w].Word + "?key=" + TheKey);

                int match = 0;

                foreach (var hint in hints)
                {
                    if (html.Contains(hint))
                    {
                        match++;
                        break;
                    }
                }
                
                words[w].Match = (((double)match / (double)hints.Length) * 100.0);                
            }

            return words;
        }
        #endregion

        #region SearchWords
        private List<Answer> SearchWords(string input)
        {
            var wordMatches = new List<Answer>();

            input = tbInput.Text.ToLower();

            for (int w = 0; w < DicWords.Count; w++)
            {
                if (DicWords[w].Length == input.Length)
                {
                    DicWords[w] = DicWords[w].ToLower();

                    int letterMatches = 0;

                    for (int l = 0; l < DicWords[w].Length; l++)
                    {
                        if ((input[l] == '?' || DicWords[w][l] == input[l]) && char.IsLetter(DicWords[w][l])) letterMatches++;
                    }                    

                    if (letterMatches == input.Length) wordMatches.Add(new Answer {Word = DicWords[w]});
                }
            }

            return wordMatches;
        }
        #endregion
    }
}

Edited by kennyparker1337 - 5/30/13 at 12:29pm
post #25 of 42
Thread Starter 
Good work there mate. And nice job finding those APIs (both the online and offline one).

Have you considered using multiple data sources to expand and refine your results? My version used both dictionary definitions as well as a thesaurus. The theory being that a thesaurus would (hopefully) pick up on the alternative words that might be used in the clues, but the definitions (and accompanying example sentences) hopefully caught some of the other keywords that were also likely to be used in the crossword clues.
post #26 of 42
Quote:
Originally Posted by Plan9 View Post

Good work there mate. And nice job finding those APIs (both the online and offline one).

Have you considered using multiple data sources to expand and refine your results? My version used both dictionary definitions as well as a thesaurus. The theory being that a thesaurus would (hopefully) pick up on the alternative words that might be used in the clues, but the definitions (and accompanying example sentences) hopefully caught some of the other keywords that were also likely to be used in the crossword clues.

Yea I was just too lazy.

I'm currently in the process of getting a new job.

I'll get around to it in a bit.
post #27 of 42
Thread Starter 
Quote:
Originally Posted by kennyparker1337 View Post

Yea I was just too lazy.

I'm currently in the process of getting a new job.

I'll get around to it in a bit.

Don't even get me started on being busy. I'm currently in the process of doing two jobs (one of which is already full time work), keeping an eye on my wife who's been throwing up all week and making frequent visits to the vets because my youngest cat has managed to break a leg. And all that while recovering from a back operation - so sitting and bending hurts. Needless to say that this month has been hell. (it's also why I've had so little patience on OCN lately redface.gif )

Anyhow, you don't need to revise your code on my behalf. I was just making conversation (since nobody seemed the least be interested in my submissions (I'm just being flippant here - that wasn't actually a complaint smile.gif ), i might as well chat about yours tongue.gif )
Edited by Plan9 - 5/30/13 at 4:11pm
post #28 of 42
Here's my go at Medium:
Code:
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;

vector<string> dictionaryWords;

string sanitise(string dirty)
{
        for (int i = 0; i < dirty.length(); i++)
        {
                if (!isalpha(dirty[i]))
                        dirty.erase(i, 1);

                dirty[i] = tolower(dirty[i]);
        }

        return dirty;
}

bool readDictionaryToRAM()
{
        ifstream dictionaryFile("english.0");

        if(dictionaryFile.is_open())
        {
                while(dictionaryFile.good())
                {
                        string tempLine;
                        getline(dictionaryFile, tempLine);
                        dictionaryWords.push_back(sanitise(tempLine));
                }

                dictionaryFile.close();
        }
        else
        {
                return false;
        }

        return true;
}

void matchWord(string word)
{
        for(int i = 0; i < dictionaryWords.size(); i++)
        {
                if(dictionaryWords[i].length() != word.length())
                        continue;

                bool goodWord = true;
                string curWord = dictionaryWords[i];

                for(int j = 0; j < word.length(); j++)
                {
                        if(word[j] == '?')
                                continue;

                        char curChar = curWord[j];
                        if(tolower(word[j]) != curChar && goodWord)
                                goodWord = false;
                }

                if(goodWord)
                {
                        cout << dictionaryWords[i] << endl;
                }
        }
}

int main()
{
        cout << "----------------------" << endl;
        cout << "---Crossword Solver---" << endl;
        cout << "--------By FiX--------" << endl;
        cout << "----------------------" << endl;

        cout << "Loading wordlist 'english.0' into RAM";
        
        if(!readDictionaryToRAM())
        {
                cout << "...failed." << endl;
                getchar();
                return 1;
        }

        cout << "...done!" << endl;

        while(true)
        {
                string currentWord;
                cout << "Please enter your word, using '?' to represent missing characters: ";
                cin >> currentWord;

                matchWord(currentWord);
        }

        //Stop the app from closing instantly
        getchar();
        return 0;
}
    
CPUMotherboardGraphicsGraphics
FX-8350 Asus Crosshair V MSI GTX460 Hawk 1gb MSI GTX460 Hawk 1gb 
RAMHard DriveHard DriveHard Drive
Kingston HyperX 8gb (2x4gb) Crucial M4 64GB Samsung F3 1TB Western Digital 320GB 
CoolingOSMonitorMonitor
Custom WC Windows 7 Ultimate X64 Dell E2311H Dell E2311H 
MonitorKeyboardPowerCase
LH 23EN43 Ducky Year of the Dragon 2012 SilverStone Strider 1000W-P Corsair 800D 
Audio
Asus Xonar Essence STX 
  hide details  
Reply
    
CPUMotherboardGraphicsGraphics
FX-8350 Asus Crosshair V MSI GTX460 Hawk 1gb MSI GTX460 Hawk 1gb 
RAMHard DriveHard DriveHard Drive
Kingston HyperX 8gb (2x4gb) Crucial M4 64GB Samsung F3 1TB Western Digital 320GB 
CoolingOSMonitorMonitor
Custom WC Windows 7 Ultimate X64 Dell E2311H Dell E2311H 
MonitorKeyboardPowerCase
LH 23EN43 Ducky Year of the Dragon 2012 SilverStone Strider 1000W-P Corsair 800D 
Audio
Asus Xonar Essence STX 
  hide details  
Reply
post #29 of 42
Python 2.7
medium
and I made sure there were no non alpha characters Warning: Spoiler! (Click to show)
Code:
#!/usr/bin/python
from Tkinter import *
exclude =['1','2','3','4','5','6','7','8','9','0',\
              '.',',','+','-','*','/','[',']','{','}',\
              '\\','!','@','#','$','%','^','&','*','(',\
              ')','_','+','=','-',';',':',"'",'"','|',\
              '`','~']
a=0
new = []

wordlist= open('english.0')
words = wordlist.read().splitlines()
wordlist.close()    

while a < len(words):
    s=False
    for b in exclude:
        if b in words[a]:
            s=True
            break
    if not s:
      new.append(words[a].lower())
    a += 1
  
def check():
    length_found = []
    pos=[]
    
    find_word = wordbox.get()
    find_word = find_word.lower()
    box.destroy()
    
    for a in new:
      if len(a) == len(find_word):
          length_found.append(a)
    
    for a in range(len(find_word)):
        if find_word[a] != '?':
          pos.append(a)
    temp = length_found[:]
    
    for b in pos:
        for a in range(len(length_found)):
          if length_found[a][b] != find_word[b]:
            x = temp.index(length_found[a])
            del temp[x]
        length_found=temp[:]

    a=0
    while a < len(temp):
      text.insert(END, temp[a]+'\n')
      a+=1

root = Tk()
root.geometry('+500+150')
box = Toplevel(root)
box.geometry('300x75+500+50')
Label(box, text="Enter word, use ? for missing letters").pack()
wordbox = Entry(box, width=30)
wordbox.pack(padx=5)
button = Button(box,  text="OK", command=check)
button.pack(pady=5)
scrollbar = Scrollbar(root)
text = Text(root, height=15, width=30, font='helvetica 20')
scrollbar.pack(side=RIGHT, fill=Y)
text.pack(side=LEFT, fill=Y)
scrollbar.config(command=text.yview)
text.config(yscrollcommand=scrollbar.set)
mainloop(  )

Edited by tom.slick - 5/31/13 at 12:22pm
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
post #30 of 42
Quote:
Originally Posted by tom.slick View Post

Python 2.7
medium
and I made sure there were no non alpha characters Warning: Spoiler! (Click to show)
#!/usr/bin/python
from Tkinter import *
exclude =['1','2','3','4','5','6','7','8','9','0',\
'.',',','+','-','*','/','','{','}',\
'\\','!','@','#','$','%','^','&','*','(',\
')','_','+','=','-',';',':',"'",'"','|',\
'`','~']
a=0
new = []

wordlist= open('english.0')
words = wordlist.read().splitlines()
wordlist.close()

while a < len(words):
s=False
for b in exclude:
if b in words[a]:
s=True
break
if not s:
new.append(words[a].lower())
a += 1

def check():
length_found = []
pos=[]

find_word = wordbox.get()
find_word = find_word.lower()
box.destroy()

for a in new:
if len(a) == len(find_word):
length_found.append(a)

for a in range(len(find_word)):
if find_word[a] != '?':
pos.append(a)
temp = length_found[:]

for b in pos:
for a in range(len(length_found)):
if length_found[a] != find_word:
x = temp.index(length_found[a])
del temp[x]
length_found=temp[:]

a=0
while a < len(temp):
text.insert(END, temp[a]+'\n')
a+=1

root = Tk()
root.geometry('+500+150')
box = Toplevel(root)
box.geometry('300x75+500+50')
Label(box, text="Enter word, use ? for missing letters").pack()
wordbox = Entry(box, width=30)
wordbox.pack(padx=5)
button = Button(box, text="OK", command=check)
button.pack(pady=5)
scrollbar = Scrollbar(root)
text = Text(root, height=15, width=30, font='helvetica 20')
scrollbar.pack(side=RIGHT, fill=Y)
text.pack(side=LEFT, fill=Y)
scrollbar.config(command=text.yview)
text.config(yscrollcommand=scrollbar.set)
mainloop( )
Could you wrap it with the [code] tag?
The result will be this: Warning: Spoiler! (Click to show)
Code:
#!/usr/bin/python
from Tkinter import *
exclude =['1','2','3','4','5','6','7','8','9','0',\
              '.',',','+','-','*','/','[',']','{','}',\
              '\\','!','@','#','$','%','^','&','*','(',\
              ')','_','+','=','-',';',':',"'",'"','|',\
              '`','~']
a=0
new = []

wordlist= open('english.0')
words = wordlist.read().splitlines()
wordlist.close()    

while a < len(words):
    s=False
    for b in exclude:
        if b in words[a]:
            s=True
            break
    if not s:
      new.append(words[a].lower())
    a += 1
  
def check():
    length_found = []
    pos=[]
    
    find_word = wordbox.get()
    find_word = find_word.lower()
    box.destroy()
    
    for a in new:
      if len(a) == len(find_word):
          length_found.append(a)
    
    for a in range(len(find_word)):
        if find_word[a] != '?':
          pos.append(a)
    temp = length_found[:]
    
    for b in pos:
        for a in range(len(length_found)):
          if length_found[a][b] != find_word[b]:
            x = temp.index(length_found[a])
            del temp[x]
        length_found=temp[:]

    a=0
    while a < len(temp):
      text.insert(END, temp[a]+'\n')
      a+=1

root = Tk()
root.geometry('+500+150')
box = Toplevel(root)
box.geometry('300x75+500+50')
Label(box, text="Enter word, use ? for missing letters").pack()
wordbox = Entry(box, width=30)
wordbox.pack(padx=5)
button = Button(box,  text="OK", command=check)
button.pack(pady=5)
scrollbar = Scrollbar(root)
text = Text(root, height=15, width=30, font='helvetica 20')
scrollbar.pack(side=RIGHT, fill=Y)
text.pack(side=LEFT, fill=Y)
scrollbar.config(command=text.yview)
text.config(yscrollcommand=scrollbar.set)
mainloop()
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge #8 (challenges for both beginners and experts)