John's Blog
Everyone and his dog has a 'blog these days, right? So why not me? If you are interested in anything I'm saying, great! Let's talk about it! (Leave comments.) If not, try one of my other links. Better yet, why are you wasting your time staring at your computer screen, go do something real!
Let me know if you'd like to be to be updated whenever I post a new article. It won't happen every day!
Automatic Sudoku Puzzle Generation
Wednesday, August 01, 2007
In a meeting today, while the focus was on what others were doing, I entertained myself by thinking about how you would go about creating Sudoku puzzles. I started by creating a 2x2 (easy), then a standard 3x3, using a simple pattern of sequences. That led to thoughts of the general steps required to create any N x N Sudoku, herewith.(Click title to read more...)My initial 3x3 pattern was:
123 456 789
234 567 891
345 678 912
456 789 123
567 891 234
678 912 345
789 123 456
891 234 567
912 345 678
You see the pattern? First row is in order, each next row starts with the next higher digit than the last.
Then I realized that an easy way to create variations on this is to swap any single row or column within the same large square, which as far as I could tell will not cause a violation of the rules. Finally, you don't really have to start the first row in order, as long as you always shift each subsequent row by one place.
In general, then, here are the steps I've come up with for generating any valid combination for an N x N puzzle, which could be implemented by computer algorithm:
- Generate row 1 in random order
- For rows 2 through N^2, take previous row and shift left or right one place (consistently)
- When finished generating rows, shuffle single rows or columns within the same large square as desired
Some notes: For larger puzzles than 3x3, you must go to letters of the alphabet. This can take you up to 5x5, maybe even 6x6 if you also include numeric digits. Above 6x6, you'd have to include puncuation, which seems kind of silly.
Implementation of this algorithm is left as an exercise to the reader. But if you do, let me know and I'll link to it. ;-)
0 comments
Querying a database with wildcards
Tuesday, June 12, 2007
Occasionally I have a need to look up something in a database where one or more fields may contain a wildcard. For example, here is a table you could use to see what to call a shape given some of its properties:| nbr_of_sides | sides_equal | angles_equal | shape_name |
|---|---|---|---|
| 3 | * | * | Triangle |
| 4 | Y | * | Square |
| 4 | N | Y | Rectangle |
| * | * | * | Polygon |
So, how do you look something up in this table?
(Click title to find out...)
First, note that in this example, I am using the * character as the wildcard, forcing all columns to be a character type even if they otherwise look like numbers. There are some others ways to do it, but you have to be careful. See below for details. I chose '*' because it is easily recognized as a wildcard in many situations.
You will probably want to put this query into a procedure or function, so that you can reuse it and just pass each set of inputs. Let's say in this example we are passing the number of sides and the two "equal" parameters. We'll call them p_nbr_of_sides, p_sides_equal, p_angles_equal. Using these parameters, your query can be as easy as this:
SELECT shape_name FROM shapes
WHERE nbr_of_sides IN ( p_nbr_of_sides, '*' )
AND sides_equal IN ( p_sides_equal, '*' )
AND angles_equal IN ( p_angles_equal, '*' )
ORDER BY nbr_of_sides DESC, sides_equal DESC, angles_equal DESC
That's it!
How does it work? Easy. For each input parameter, you are selecting rows where the corresponding table column either matches that input, or is the wildcard. So you could potentially match multiple rows, some more specific than others. That's where the ORDER BY clause comes in. Because '*' (and most other punctuation) has a lower sort value than numbers and letters, we tell it to sort the results DESCENDING, to ensure that more specific matches are listed first. This is like Google returning search results in order of most likely to less likely. This ensures that the first row of multiples (if any) is always the most specific, thus the one we want. Try it for several variations of input and see for yourself!
In your procedure, then, just return the results from the first row and discard the others. Syntax for all this will vary by database platform, and so is intentionally left as an exercise to the reader.
So what about that '*' as the wildcard? There are some drawbacks. As noted above, you may not want to force all your columns to be character type if the specific values are all numbers. You might be tempted to just use NULL, but I'm not sure how that will be treated in the ORDER BY, and it may well vary by platform, so I would advise against that. The '*' may also not be the greatest choice if you expect that your column could start with other punctuation, some of which sorts lower than the asterisk. (See any ASCII table for actual values.) This shows that a series of spaces may actually be the best value for character fields, since the space is lowest sorting printable character.
The bottom line is that any non-NULL "special" value will do, as long as it sorts lower than any of your expected actual values. For numeric columns, if you know you will only have non-zero positive values (like in this example), 0 would do. Or some negative low number such as -9999999.
Hope you found this helpful.
0 comments
Finding the last day of week before a given date
Wednesday, June 06, 2007
Occasionally I need to derive the formula to find the last (whatever day of week) before a given day, such as the previous Sunday or the previous Monday. I do this so infrequently that I always forget where I have already done it or what the formula is, so I usually derive from scratch every time. I could Google for it, but I figure that would take about as long as deriving it would. But, now that I've done it yet again, maybe if I put it in my blog, I'll be able to find it easily the next time. Or maybe it will even help others who might find it by Googling, maybe you! (Click title to read more...)I'm trying to keep this language-independent, but there need to be some givens:
- You have a function in your language to return a day of the week as a number. In this case, I'm assuming 0 = Sunday to 6 = Saturday, which is the standard for C and its derivative languages like Perl and PHP. Alternately, the MS Excel function WEEKDAY returns 1 = Sunday to 7 = Saturday by default, so you would implement this formula in Excel by simply subtracting 1 where the variable w is used. (I used Excel to test this.)
- You need a modulo function. In C, Perl, PHP, etc., this is the binary operator %, so that's what I use here. MS Excel and some others use the function MOD( n, m ) instead.
Given Variables:
- w = Day of Week (DOW) number of the date you are starting from, such as today. This will be 0 - 6 as described above.
- e = DOW number of the date you are trying to go back to, such as 0 to find the previous Sunday, 1 to find the previous Monday, etc.
We want to find the number of days between our starting day and the day we are going back to:
Difference in days (d) = w - e. The sticky point is that we need to provide for "wrapping around" to the prior week. To do this, we add 7 and then modulo the result by 7:
d = ( w - e + 7 ) % 7
Now we just subtract this number of days from the current day. How this is done depends on your language.
In languages that represent date/times as a number, with the whole part being the day and the decimal part being the time, you can just subtract as a number. For example, in my MS Excel testing spreadsheet, if the starting date (maybe today) is in cell A1, and I'm going back to the previous Monday (DOW 1), the formula is:
=A1 - MOD( WEEKDAY( A1) - 1 - 1 + 7, 7 )
Note that we subtracted 1 from the WEEKDAY function to make it 0-6 instead of 1-7, and used Excel's MOD function.
In a language such as C, where timestamps are represented as number of seconds since a fixed time (like Jan 1 1970, the Unix epoch start), just take d and multiple it by seconds in a day, 86400, and subtract that from the starting day to find the finish day.
Or, your language may have a date difference function where you can specify the number of days.
Hope you found this helpful!
Labels: computer
2 comments
