The Weird and The Wonderful

9-Sep-09 3:08

Was just asked to convert some VB6 code to C#.

The purpose of the code is to find anagrams. There is a database with a list of words. The input is a string of letters and the code is supposed to spit out any matching anagrams found in the word list.

The idea is to have a 'crossword puzzle' helper tool that can be downloaded from an ad-financed puzzle enthusiasts website, but the client felt it was too slow to use and wondered if C# might be faster.

This is what I found: All possible orders of letters in the input string are derived in a loop, then each one is searched against the database to see if it exists. As you might imagine, with anything except a very short input this yields gazzilions of combinations and takes forever (almost literally) to run.

The first thing I did was a run-once bit of code to sort the letters in each word in the database into alphabetical order, and stick that in as a key field.

To find an anagram, the letters in the input are also sorted into alphabetical order. We then match that to the indexed key field and pull out matching words in the blink of an eye.

The end result runs in milliseconds instead of centuries. Or as the client put it "That C#'s a bit faster than VB6, isn't it?"

Should I now point out that a downloadable C# app is not a good idea? Their user base (presumably little old ladies) would need the net framework on their Win98 PCs, and having downloaded once, they don't need to go back to click on the knitting pattern banner ads. It should run in a browser.

But what do I know? I'm just a stupid girl.

JustAStupidGurl

Jeroen De Dauw9-Sep-09 3:48

Jeroen De Dauw

9-Sep-09 3:48

Very amuzing Big Grin | :-D

The old algorithm does not hold into account possible typo's. Maybe it can be adapted to also check for every possible combination of 3 wrong characters in each word Big Grin | :-D

GSoC 2009 student for SMW!
---
My little forums: http://code.bn2vs.com
---
70 72 6F 67 72 61 6D 6D 69 6E 67 20 34 20 6C 69 66 65!

justastupidgurl9-Sep-09 4:05

9-Sep-09 4:05

Or make the input several MB.

It could then produce every possible C# source code file, not to mention every possible poem of that size.

Bound to be a few good ones Smile | :)

JustAStupidGurl

Jeroen De Dauw9-Sep-09 20:40

Jeroen De Dauw

9-Sep-09 20:40

lol!

Mind if I put that in my collection of epic quotes? Poke tongue | ;-P

GSoC 2009 student for SMW!
---
My little forums: http://code.bn2vs.com
---
70 72 6F 67 72 61 6D 6D 69 6E 67 20 34 20 6C 69 66 65!

justastupidgurl11-Sep-09 2:58

11-Sep-09 2:58

Go ahead

JustAStupidGurl

akidan11-Sep-09 7:27

akidan

11-Sep-09 7:27

? You seem reasonably intelligent to me... or was it tongue-in-cheek?

Ian Shlasko11-Sep-09 8:05

Ian Shlasko

11-Sep-09 8:05

Please adjust your sarcasm detector Smile | :)

Proud to have finally moved to the A-Ark. Which one are you in?
Developer, Author (Guardians of Xen)

justastupidgurl12-Sep-09 2:37

12-Sep-09 2:37

What do you think?

But then I'm JustAStupidGirl, so you never know.

JustAStupidGurl

ClementsDan11-Sep-09 17:48

ClementsDan

11-Sep-09 17:48

The impressiveness of (for example) a 87,178,291,200-element search space for 14-letter anagrams should have gotten the original author to use less permissiveness in choosing an algorithm. If he could miss such an obvious rectification for the problem, he doesn't deserve to earn any kind of certification in software development.

justastupidgurl12-Sep-09 2:19

12-Sep-09 2:19

JustAStupidGurl

dawmail33316-Sep-09 2:11

dawmail333

16-Sep-09 2:11

*Stab*

How to group by hour properly. [modified]

dojohansen15-Oct-09 1:25

dojohansen

15-Oct-09 1:25

Do point out that a downloadable C# app isn't the best idea. Why not just run it in asp.net? Even if the existing website is something else, like php, why not set up an asp.net server to run the anagram logic if nothing else? The site can then retrieve the anagrams (or even pre-rendered html) through ajax or some ajax-like mechanism and nobody has to download anything. Even people who have the framework installed may be somewhat sceptical to downloading and running executables directly from some small-name website. Though I guess if we look at how many people happily use things like TPB as their source of software my concern might seem exaggerated.

I've always been fascinated by the fact that somewhere in the digits of pi is a blue-ray encoded video with DTS surround sound of myself falling into a supermassive black hole, seeing past and future as I pass the event horizon, and then arriving at a concert where Mozart plays drums, Britney Spears plays a cello, Bono is a backing vocalist and the pope is making out with George Michael.

Brady Kelly20-Aug-09 22:33

Brady Kelly

20-Aug-09 22:33

I've just found a another report query by my favourite genii, which gives call volumns per hour. You see, datetime columns are once again frowned upon, so we store the call time formatted as 'hh:mm:ss', then we 'group' by the call time as follows:

, CASE WHEN Sum(CASE WHEN TimeText>='01:00:00' And TimeText<='01:59:59' THEN Cost ELSE 0 END) IS Null THEN 0 ELSE Sum(CASE WHEN TimeText>='01:00:00' And TimeText<='01:59:59' THEN Cost ELSE 0 END) END AS T1_2
, CASE WHEN Sum(CASE WHEN TimeText>='02:00:00' And TimeText<='02:59:59' THEN Cost ELSE 0 END) IS Null THEN 0 ELSE Sum(CASE WHEN TimeText>='02:00:00' And TimeText<='02:59:59' THEN Cost ELSE 0 END) END AS T2_3
, CASE WHEN Sum(CASE WHEN TimeText>='03:00:00' And TimeText<='03:59:59' THEN Cost ELSE 0 END) IS Null THEN 0 ELSE Sum(CASE WHEN TimeText>='03:00:00' And TimeText<='03:59:59' THEN Cost ELSE 0 END) END AS T3_4
, CASE WHEN Sum(CASE WHEN TimeText>='04:00:00' And TimeText<='04:59:59' THEN Cost ELSE 0 END) IS Null THEN 0 ELSE Sum(CASE WHEN TimeText>='04:00:00' And TimeText<='04:59:59' THEN Cost ELSE 0 END) END AS T4_5
, CASE WHEN Sum(CASE WHEN TimeText>='05:00:00' And TimeText<='05:59:59' THEN Cost ELSE 0 END) IS Null THEN 0 ELSE Sum(CASE WHEN TimeText>='05:00:00' And TimeText<='05:59:59' THEN Cost ELSE 0 END) END AS T5_6
, CASE WHEN Sum(CASE WHEN TimeText>='06:00:00' And TimeText<='06:59:59' THEN Cost ELSE 0 END) IS Null THEN 0 ELSE Sum(CASE WHEN TimeText>='06:00:00' And TimeText<='06:59:59' THEN Cost ELSE 0 END) END AS T6_7

For each of all 24 freaking hours. And, BTW, we don't need no steenkin' isnull() function either.

JUST IN: There are 48 of these CASE lines, 24 for incoming calls, and 24 for outgoing calls. Laugh | :laugh:

Last modified: 10mins after originally posted --

David Skelly21-Aug-09 0:49

David Skelly

21-Aug-09 0:49

Just as a matter of interest, assuming you are not in control of the database (i.e. you are constrained by the fact that the time is stored as a text string and you cannot change that fact), how would you implement this requirement? I've been scratching my head trying to think of the easiest, most elegant way to achieve it. I would probably try to take a substring of the TimeText to get the hour and then group by that. Does that work?

select time_hour as substring(TimeText, 1, 2), sum(Cost)
from MyTable
group by time_hour

I haven't tried that, it's just off the top of my head. Does it achieve the same end result?

Brady Kelly21-Aug-09 0:53

Brady Kelly

21-Aug-09 0:53

Something very close works like a dream:

select 
	  isnull(sum(case when Call = 1 then Cost else 0 end), 0) as Incoming
	, isnull(sum(case when Call = 2 then Cost else 0 end), 0) as Outgoing
	, left(TimeText, 2) as Hour
FROM 
CallRecords crd
group by 
	left(TimeText, 2)

ClementsDan21-Aug-09 15:22

ClementsDan

21-Aug-09 15:22

You don't need to check for nulls, because SUM will automatically exclude them.

Don't know why they wouldn't use a TIME column, unless they were using SQLite, but even there you can just do:

SELECT strftime('%H', TimeText) AS Hour, SUM(Cost) FROM MyTable GROUP BY Hour;

How to handle dates _properly_. [modified]

MaksimP25-Sep-09 10:07

MaksimP

25-Sep-09 10:07

select count(PK) Count, DatePart(hh,ColumnTime) Hour
from dbTable
group by DatePart(hh,dbColumnTime)

Brady Kelly20-Aug-09 12:31

Brady Kelly

20-Aug-09 12:31

First, you use a varchar(20) default '' to store a six char date in the form yymmdd. Users have the luxury of an extra fourteen chars to add willy nilly romantic annotations to the date. Savvy data entry clerks may even squeeze a well formed XHTML tag in there.

Then, when the huns appear over the next control-break horizon, and you need the real DateTime you promised them, you divide and conquer. A bunch of little two character numbers quickly evaporate into two character numbers. Except the year pair, '09'. In the shocking assault on decency everywhere, teh geinus grugru of date parsing expertly recognised that the '09' needed '20'. Why waste two innocent zeros and add '2000', when you can add '20', as in string conctratingation, but hey, strings are for physicists and yoyos, so lets just add 20.

In the following horrific, true life example of unprecedented savagery, our valiant knight takes a string value for detailLastDate; of '090722' and with a wave of a hanky and quickly stuffing a rabbit into a hat for distraction, presents The Date Parsing canon (emphasis mine):

DateTime time2 = new DateTime(int.Parse(20 + detailLastDate.Substring(0, 2)), int.Parse(detailLastDate.Substring(2, 2)), int.Parse(detailLastDate.Substring(4, 2)));

Isn't it wonderful how he can just add the integer 20 to the substring '09', and get a year value of 2009? I am forever in awe.

Last modified: 9hrs 10mins after originally posted --

Keith Barrow20-Aug-09 23:03

Keith Barrow

20-Aug-09 23:03

I suddenly feel lucky (see below)

supercat921-Aug-09 10:14

supercat9

21-Aug-09 10:14

Isn't it wonderful how he can just add the integer 20 to the substring '09', and get a year value of 2009? I am forever in awe.

Whether or not it was reasonable for programmers in the 80's and 90's to figure their code would be obsolete before the year 2000, I see no reason to believe that any code written today will not be obsolete before the year 2100. At least the programmer deserves credit for not trying to add punctuation to convert the string to mm-dd-yy form and doing an unadorned parse on that (which would succeed or fail depending upon locale).

Dan Neely21-Aug-09 10:41

Dan Neely

21-Aug-09 10:41

supercat9 wrote:
I see no reason to believe that any code written today will not be obsolete before the year 2100.

I strongly disagree. IF y2k and the last decade have taught us anything it's that crufty old code doesn't die, it just gets wrapped in interface translation layers to feed newer systems.

The European Way of War: Blow your own continent up.
The American Way of War: Go over and help them.

supercat924-Aug-09 11:05

supercat9

24-Aug-09 11:05

I strongly disagree. IF y2k and the last decade have taught us anything it's that crufty old code doesn't die, it just gets wrapped in interface translation layers to feed newer systems.

Code can be around for awhile, certainly, but from a user I/O perspective I don't see much point to using four-digit years for most purposes (from an internal-storage perspective, storing a year as two digits is generally silly with or without century-wrap issues). If an application is only going to deal with dates in the near future or recent past, there's no reason to require users to waste keystrokes typing a leading "20", nor is there any reason to waste space printing or displaying a "20" in front of years on paper or screen. If, seventy years from now, a printed document bears a date of 01-01-76, it will almost certainly be obvious whether the document was produced in the 1970's or 2070's. Even if there were no further improvements in printing technologies, the earliest possible ambiguities for documents printed on quality paper wouldn't occur until 2090 or so; even then, it should be obvious which documents were printed in 1990 and which ones were printed in 2090.