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 4

post #31 of 42
Thread Starter 
Quote:
Originally Posted by tom.slick View Post

Python 2.7
medium
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( )

Nice work. Do you mind putting that inside code tags to preserve indentation please - particularly as python throws a wobbly if the indentation is wrong (me being a bit of a n00b at Python, it took me a while to re-indent everything when I pasted your code out laugher.gif )
Quote:
Originally Posted by tom.slick View Post

and I made sure there were no non alpha characters
I can still insert £ and © tongue.gif

You could fix that by checking the character code instead. eg since you're converting your words to lower case anyway, you know that all the valid characters are going to be between 97 (ord('a')) and 122 (ord('z')). But as I said before, good work smile.gif
Edited by Plan9 - 5/31/13 at 5:40am
post #32 of 42
Quote:
Originally Posted by Plan9 View Post


You could fix that by checking the character code instead. eg since you're converting your words to lower case anyway, you know that all the valid characters are going to be between 97 (ord('a')) and 122 (ord('z')). But as I said before, good work smile.gif

That's what happens at 3am, I'll fix it in a little while:thumb:

updated
Warning: Spoiler! (Click to show)
Code:
#!/usr/bin/python
from Tkinter import *
a=0
new = []

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

while a < len(words):
    s=False
    for b in range(97,123):
        if chr(b) not in words[a].lower() :
            s=False
            break
    if not s:
      new.append(words[a])
    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].lower() != find_word[b].lower():
            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 1:06pm
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 #33 of 42
medium:
python 2.7 one-liner (excluding the import)


when inlined:
Code:
import sys; print '\n'.join( [word for word in [y for y in [x.strip() for x in open('/tmp/english.0', 'r').readlines()] if reduce(min, [('a' <= char <= 'z') or ('A' <= char <= 'Z') for char in y])] if ( len(sys.argv[1]) == len(word) ) and reduce(min, [(sys.argv[1][idx] == '?' or sys.argv[1][idx] == word[idx]) for idx in range(len(word))]) ] )

human semi-readable:
Code:
def is_allowed(char):
  return ('a' <= char <= 'z') or ('A' <= char <= 'Z')

def is_valid_word(word):
  return reduce(min, [is_allowed(char) for char in word])

words = [y for y in [x.strip() for x in open('/tmp/english.0', 'r').readlines()] if is_valid_word(y)]

import sys
pattern = sys.argv[1]

def matches_at_idx(word, pattern, idx):
  return (pattern[idx] == '?' or pattern[idx] == word[idx])

def matches(word, pattern):
  return ( len(pattern) == len(word) ) and reduce(min, [matches_at_idx(word, pattern, idx) for idx in range(len(word))])

print '\n'.join( [word for word in words if matches(word, pattern)] )

pattern is a command line argument
stuff
(7 items)
 
  
CPUMotherboardGraphicsRAM
4790k gigabyte z97x-ud5h gtx 980ti ddr3 
Hard DriveOSMonitor
samsung evo 840 coolermaster hyper 212 evo windows 8.1 64bit 
  hide details  
Reply
stuff
(7 items)
 
  
CPUMotherboardGraphicsRAM
4790k gigabyte z97x-ud5h gtx 980ti ddr3 
Hard DriveOSMonitor
samsung evo 840 coolermaster hyper 212 evo windows 8.1 64bit 
  hide details  
Reply
post #34 of 42
Well to be fair... any and all solutions can be one-liners.

I think a one-liner implies it is also readable. tongue.gif
post #35 of 42
Quote:
Originally Posted by kennyparker1337 View Post

Well to be fair... any and all solutions can be one-liners.

I think a one-liner implies it is also readable. tongue.gif
Especially since the introduction of semicolons tongue.gif
post #36 of 42
Quote:
Originally Posted by 3930K View Post

Especially since the introduction of semicolons tongue.gif
be nice he only used one semicolon
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 #37 of 42
Quote:
Originally Posted by tom.slick View Post

Quote:
Originally Posted by 3930K View Post

Especially since the introduction of semicolons tongue.gif
be nice he only used one semicolon
I'm talking more about C based languages, not his post smile.gif
Edited by 3930K - 6/2/13 at 2:43am
post #38 of 42
Quote:
Originally Posted by 3930K View Post

I;m talking more about C based languages, not his post smile.gif
okay, then for the record you were being nice,biggrin.gif
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 #39 of 42
Seems no one here mentioned anything about tries so I created a simple implementation in Python. The trie is created as a next of maps where the key is a character and the value is the next trie (map). There is a special key which is the string "end" whose presence indicates the path from the root trie to the current trie forms a complete word. As such, the insert() and contains() methods are nearly identical. The search() method is a simple recursive DFS-eqsue search. It replaces a "?" character with a letter and calls itself recursively. If no "?" characters are found, it checks if the entire word is present in the trie and if so, appends it to a global results list.
Spoiler Code (Click to show)
Code:
#!/usr/bin/pypy

from sys import argv
from collections import deque
from string import letters

trie = {}
result = []

def insert(word):
    isalpha = True
    for x in word:
        isalpha = isalpha and x in letters
    if isalpha:
        current = trie
        for i in xrange(len(word)):
            if word[i] not in current:
                current[word[i]] = {}
            current = current[word[i]]
        current["end"] = True

def contains(word):
    current = trie
    for i in xrange(len(word)):
        if word[i] not in current:
            return False
        current = current[word[i]]
    return "end" in current

def search(word):
    chars = list(word)
    if "?" in chars:
        i = chars.index("?")
        for x in letters:
            next = list(chars)
            next[i] = x
            query = "".join(next)
            search(query)
    elif contains(word):
        result.append(word)

with open("words") as f:
    for line in f:
        word = line.strip()
        insert(word)

query = argv[1]
search(query)
for word in result:
    print word

Usage:
Code:
$ ./search.py c??e
cafe
cage
cake
[...]
Mythos
(16 items)
 
  
CPUMotherboardGraphicsRAM
Intel i7 4770k EVGA Z87 Stinger EVGA 780 Ti SC Corsair Vengeance LP 16GB (2 x 8GB) DDR3 1600 
Hard DriveHard DriveHard DriveCooling
Corsair Neutron GTX 240GB Samsung 850 EVO 250GB WD VelociRaptor (2x 300GB RAID 0) Corsair H75 
OSMonitorKeyboardPower
Windows 8.1 Pro (64-bit) Asus VG248QE Filco Majestouch 2 TKL (Cherry Black) Corsair CX600 (600W Bronze) 
CaseMouse
Fractal Node 304 Steelseries Sensei 
  hide details  
Reply
Mythos
(16 items)
 
  
CPUMotherboardGraphicsRAM
Intel i7 4770k EVGA Z87 Stinger EVGA 780 Ti SC Corsair Vengeance LP 16GB (2 x 8GB) DDR3 1600 
Hard DriveHard DriveHard DriveCooling
Corsair Neutron GTX 240GB Samsung 850 EVO 250GB WD VelociRaptor (2x 300GB RAID 0) Corsair H75 
OSMonitorKeyboardPower
Windows 8.1 Pro (64-bit) Asus VG248QE Filco Majestouch 2 TKL (Cherry Black) Corsair CX600 (600W Bronze) 
CaseMouse
Fractal Node 304 Steelseries Sensei 
  hide details  
Reply
post #40 of 42
Thread Starter 
nice solution
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)