Showing posts with label match. Show all posts
Showing posts with label match. Show all posts

Friday, February 27, 2009

Subdomain Redirection Using htaccess And mod_rewrite On Apache For Linux Or Unix

Hey there,

Following up on yesterdays post on 301 redirects, which we realize is a tired subject, today we're going to take look at simple ways you can do regular/subdomain redirection using htaccess and "mod_rewrite" for Apache on Linux or Unix. And, while yesterday's subject matter (and perhaps even today's) may be somewhat generic, we're trying to even the balance here. Now that we're in the 500's on post count, we feel it would be a shame if somebody came here to learn something really cool and then couldn't find some other really basic information. As written previously, if this blog's subject matter were more limited this would be much easier to do. On the bright side, we'll probably never run out of things to write about :)

You can reference the basics of mod_rewrite syntax and rules on the link provided that points back to apache.org. While this page (or pages it links to within the same site), obviously, covers all the aspects of using Apache's "mod_rewrite," the style may not be suited to everyone. It's great information, but assumes some level of comfort that you may or may not already have regarding the subject matter.

In our few examples today (which won't cover much but should be explained with a good amount of detail), we're going to use a file named ".htaccess" (the dot at the beginning of the name is important!) placed in our web server's root folder (or base folder, etc) which contains the "mod_rewrite" rules. Our first example will implement the equivalent of a 3xx redirect using "mod_rewrite" instead of the more conventional methods. In order to implement this, just place the following content in your .htaccess file (assuming, again, that we want visitors to www.myxyz.com to be redirected to www.myotherxyz.com):

Options +FollowSymLinks
RewriteEngine On
RewriteBase /
Redirect 301 / http://www.myotherxyz.com


Looks familiar, yeah? We actually covered that yesterday, as it's one of the most basic rewrites you can do. We just added the "standard recommended" starting lines for your .htaccess file. Those top three lines aren't "always" necessary, which is why we didn't include them in yesterday's example.

Here's another example that shows you how to use "mod_rewrite"'s regular expression functionality to redirect from an htm(l) page on one web server to a page on another web server:

Options +FollowSymLinks
RewriteEngine On
RewriteBase /
RewriteRule ^(.+)\.htm$ http://www.myotherxyz.com/$1.html [R,NC]


This example doesn't do all that much more than the previous, but it "is" a lot more flexible. We'll walk through the RewriteRule, to see what it's doing (and, remember, all of the nitty-gritty can be found on Apache's mod_rewrite page). The line itself, if you're familiar with basic regular-expression syntax, isn't too hard to decipher. The characters that are special in the line are the following:

^ <-- The caret indicates that the match is anchoring to the start of the request.
. <-- The dot character is representative of "any" alphanumeric character (including spaces, tabs, goofy characters, etc). It matches "anything"
\ <-- The backslash character "escapes" special match characters. In this case, we're using it to represent a "real" dot, rather than the regular-expression dot described above.
+ <-- The plus symbol indicates that the character preceding it must exist one or more times if the match is to be considered a success
$ <-- The dollar sign is the opposite of the caret. It indicates that the match is anchored at the end of the request
() <-- Anything within parentheses (on the left-hand-side, or LHS, of the expression) is considered to be a "captured" part of the match. It can be referenced on the right hand side (or RHS) of the rewrite rule using the dollar sign. This sign, as shown above, means something completely different on the RHS of the equation.
$1, $2, $3, etc <-- the dollar-sign-plus-number on the RHS of the expression represents the content of an LHS match (within the parentheses, as written above). The first parentheses match on the LHS is represented by $1, the second by $2, etc.
[] <-- Within the match rule itself, the brackets indicate a range, or "class" (a term that doesn't seem correct, but is used in the mod_rewrite terminology) of characters. For instance [abcd] would match the letter a, b, c or d. At the end of the mod_rewrite rule (as its final component) the characters within it hold special significance and "do not" represent a range. You can use more than one and just separate them with commas. In the example above they say that:
R <-- We're doing a "R"edirect. You can add an equals sign and the proper number if you want to be specific. So, a 301 redirect would look like [R=301] and make our expression's end look like [R=301,NC]
NC <-- Even though N and C both have special meanings of their own (in the final part of the rewrite rule), when used together as a single entity they mean that the matching-rule should be "case insensitive" NC equal "No Case" if that helps ;)

And that's that one line. Explained with only 10 or 12 more ;) Basically, it matches any web server request (for an html page - a bit more than our other rule was looking for) and redirects it, like so:

ORIGINAL REQUEST: http://www.myxyz.com/iNdex.html (Sent to the web server as "/iNdex.html)
MATCHING RULES APPLIED: ^(/iNdex).html ==> http://myotherxyz.com//index.html

The double slashes are squashed into one by default, but you could remove them from the LHS of the match rule and make that "" "^(.+)\.htm$" into "^/(.+)\.htm$" - effectively removing the leading forward slash from the () parentheses match and its extrapolated value ($1) on the RHS.

The standard final argument indicators are listed on Apache's mod_rewrite page and below:

[R] Redirect. You can add an =301 or =302, etc, to change the type.
[F] Forces the url to be forbidden. 403 header
[G] Forces the url to be gone. 401 header
[L] Last rule. (You should use this on all your rules that don't link together)
[N] Next round. Rerun the rules again from the start
[C] Chains a rewrite rule together with the next rule.
[T] use T=MIME-type to force the file to be a mime type
[NS] Use if no sub request is requested
[NC] Makes the rule case insensitive
[QSA] Query String Append. Use to add to an existing query string
[NE] Turns off the normal escapes that are the default in the rewrite rule
[PT] Pass through to the handler (together with mod alias)
[S] Skip the next rule. S=2 skips the next 2 rules, etc
[E] E=var sets an enviroment variable that can be called by other rules


In our final example, if you want to redirect all sub-domains of a domain to another site (e.g. redirect home.myxyz.com to www.myxyz.com), you could do it like this:

Options +FollowSymLinks
RewriteEngine On
RewriteBase /
RewriteRule %{HTTP_HOST} ^([^.]+)\.myxyz\.com$ http://www.myotherxyz.com [NC,L]


The %{HTTP_HOST} variable is translated from the variable provided by the standard HTTP headers. The L in the final argument means that, if this match is made, it will be considered the last match and no more rules in your .htaccess file will be processed. In our small example this doesn't really make a difference, but it can help with flow control if you have multiple rules and want to quit matching if you match this condition.

Hopefully today's quick run-down has been helpful. Let us know - too much information, not enough, not-enough-of-some-but-too-much-of-another? We're always interested in hearing your thoughts :)

Cheers,

, Mike




Discover the Free Ebook that shows you how to make 100% commissions on ClickBank!



Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.

Thursday, September 18, 2008

Streamlined Perl Number Matching Script For Unix Or Linux

Hey There,

We'll, this week's been completely out-of-sequence. Today's post was slated for the day before yesterday and Tuesday's number pool script that was supposed to come out yesterday ended up getting published on Tuesday. If there's one thing we've learned this week, it's that my day job is starting to interfere with my hobbies ;)

On the bright side, we're finally getting around to wrapping up the two-parter we started on Monday with our uncondensed Number Matching Perl Script. The intent, with that post, was to show a working example of a simple Perl script (basically, matching numbers out of another file with a few option-based limitations imposed by the user) that was written off-the-cuff. Although it functioned, and worked pretty efficiently, it was a confusing mess to look at, and didn't include some options that it probably should have. To summarize, the aim of the follow up post (today's, at last) was going to be to reproduce that script in a more condensed format. This condensation (that just doesn't sound right, does it? But, I looked it up in the dictionary and the way in which I meant it was actually the first entry ;) would include addition of extra code to handle some needed functionality, as well as a few helpful comments and more logical ordering of all the parts. The end result, hopefully, is more scalable, so you won't have to dread all the extra typing and logical convolution involved in adding a seventh variable ;)

Again, we have the same fairly simple Perl script that will parse any file consisting of rows of numbers and print out matches meeting certain criteria. As noted before, you can visit the lamer version of this script from Monday and compare it with today's "better" version (or "less lame," depending on what kind of a person you are. Glass half full? Glass half empty? Glass too big? ;)

Again, the basic file format (for the input) should be a text file with lines like the following (note that this updated script will also take regular single digits and has an extra "-p" flag if you want to pad those with 0's):

host # cat file
01 02 03 04 05 09
5 18 19 45 33
33 55 666 88 23 12
...



Again, the script has 4 non-optional arguments that you'll be prompted for if you forget to enter any of them (with the additional, and optional, "-p" flag), like so:

host # ./match.pl
Error Encountered! Invalid or incomplete options!
Usage: ./better.pl -h highNumber -f statFile -n numberOfCombos -m mimimumCombos
[-p padSingleDigitsWithZeros]


A regular execution would look like this (we're removing duplicate match elements in a simple hash now, instead of building an increasingly lengthening logic knot - depending upon how you want to implement the match, it should be trivial, like adding \b or whatnot, to make the matches more exact so that 13 won't match 130):

host # ./match.pl -h 15 -f NUMFILE -n 3 -m 10 -p
12 matches 10 times:
7 8 9 10 11 12
109 110 111 112 113 114
115 116 117 118 119 120
121 122 123 124 125 126
127 128 129 130 131 132
211 212 213 214 215 216
307 308 309 310 311 312
409 410 411 412 413 414
511 512 513 514 515 516
607 608 609 610 611 612

13 matches 10 times:
13 14 15 16 17 18
109 110 111 112 113 114
127 128 129 130 131 132
133 134 135 136 137 138
139 140 141 142 143 144
211 212 213 214 215 216
313 314 315 316 317 318
409 410 411 412 413 414
511 512 513 514 515 516
613 614 615 616 617 618

15 matches 10 times:
13 14 15 16 17 18
115 116 117 118 119 120
145 146 147 148 149 150
151 152 153 154 155 156
157 158 159 160 161 162
211 212 213 214 215 216
313 314 315 316 317 318
415 416 417 418 419 420
511 512 513 514 515 516
613 614 615 616 617 618


And, when everything isn't equal, the output basically looks the same :)

host # ./match.pl -h 15 -f NUMFILE -n 3 -m 5 -p

01 02 matches 6 times:
97 98 99 100 101 102
199 200 201 202 203 204
301 302 303 304 305 306
397 398 399 400 401 402
499 500 501 502 503 504
601 602 603 604 605 606...


All in all, we only save about 50 lines of code (some of which is blank lines and comments), but the result should be a lot easier to manage and build upon.

Hope you enjoy the script and can find some use for it or its parts (like dealing with duplicates in multiple arrays, etc). You can never do enough matching ;)

Cheers,


Creative Commons License


This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/usr/bin/perl

#
# match.pl - Updated to last longer and taste better :)
#
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

use Getopt::Std;

%options = ();

# DIFF - Add -p option to pad 1-9
getopts("h:f:m:n:p", \%options);

if ( defined $options{m} && defined $options{h} && defined $options{f} && defined $options{n} ) {
$highnum = $options{h};
$combos = $options{n};
$statfile = $options{f};
$minmatch = $options{m};
if ( ! -f $statfile ) {
usage("File $options{f} Does Not Exist!");
} elsif ( $combos > 6 ) {
usage("Only Combos Up To 6 Please!");
}
} else {
usage("Invalid or incomplete options!");
}


open(FILE, "<$statfile");
@file = <FILE>;
close(FILE);

# DIFF - with -p, now have to differentiate
# DIFF - between straight and padded 1-9
for ( $lownum = 1; $lownum <= $highnum; $lownum++ ) {
if ( defined $options{p} && $lownum < 10 ) {
$padded_num = "0$lownum";
} else {
$padded_num = $lownum;
}
push(@numbers, "$padded_num");
}

# DIFF - Still not using a subroutine for this.
# Trying to stay away from arrays of array references, also
# for ease of understaning

@numbers1 = @numbers2 = @numbers3 = @numbers4 = @numbers5 = @numbers6 = "";
$one = $two = $three = $four = $five = $six = 1;
$start = 1;
while ( $start <= $combos ) {
if ( @numbers1 == 1 && $start == 1 ) {
@numbers1 = @numbers;
$one = 0;
} elsif ( @numbers2 == 1 && $start == 2 ) {
@numbers2 = @numbers;
$two = 0;
} elsif ( @numbers3 == 1 && $start == 3 ) {
@numbers3 = @numbers;
$three = 0;
} elsif ( @numbers4 == 1 && $start == 4 ) {
@numbers4 = @numbers;
$four = 0;
} elsif ( @numbers5 == 1 && $start == 5 ) {
@numbers5 = @numbers;
$five = 0;
} elsif ( @numbers6 == 1 && $start == 6 ) {
@numbers6 = @numbers;
$six = 0;
}
$start++;
}

foreach $cnum1 (@numbers1) {
foreach $cnum2 (@numbers2) {
foreach $cnum3 (@numbers3) {
foreach $cnum4 (@numbers4) {
foreach $cnum5 (@numbers5) {
foreach $cnum6 (@numbers6) {
@match = grep(/$cnum1/ && /$cnum2/ && /$cnum3/ && /$cnum4/ && /$cnum5/ && /$cnum6/, @file);
$match = @match;
if ( $match >= $minmatch ) {
undef %seen;
@success = grep(!$seen{$_}++, ($cnum1, $cnum2, $cnum3, $cnum4, $cnum5, $cnum6));
print "@success matches $match times:\n @match\n";
}
}
}
}
}
}
}

sub usage {
$message = shift;
print "Error Encountered! $message\n";
print "Usage: $0 -h highNumber -f statFile -n numberOfCombos -m mimimumCombos\n";
print "[-p padSingleDigitsWithZeros]\n";
exit(1);
}


, Mike




Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.

Wednesday, September 17, 2008

Revamped Perl Script To More Evenly Distribute Number Pool Match Odds

Hey There,

It's been noted (and I know that it's true) that the spread-system used in the last portion of our Perl script (posted yesterday in our entry regarding maximizing guaranteed matches) was somewhat uneven. The end result, of course, being that your given set-numbers from pool-numbers (3 from 5, 4 from 6, etc) guaranteed that the sets would be included in the generated pools, but (as was noticed by a few people, including myself) the downside (?) ends up being that the front-numbers are more heavily weighted. That is to say that, given a situation where you've got 6 balls drawn, you want to guarantee matches of 3 and you're using a number pool of 8 different numbers (1, 2, 3, 4, 5, 6, 7 and 8 - for example), the first 3 return a higher percentage of the time than the numbers at the other end of the spectrum.

I actually chose to go with this sort of distribution for a particular reason. Well, reasoning, anyway. My reasoning was this: If I rewrite the distribution so that it ends up being more "fair" (The best I could get was a somewhat even distribution that would guarantee any given match set would come up only once or twice), this would probably seem like a better deal, since the odds are "spread out." This is where I, possibly, view things a little bit differently. In our original setup, even though the front numbers are more heavily weighted, the end numbers are guaranteed to contain match sets that all come up at least once or twice. Really, you've got the same thing as the more "fair" method, except for two strong distinctions (aside from the fact that the distributions are unequal in comparative outcomes):

1. In the "fair" distribution, your end number matched-sets have approximately the same odds of returning as they do in the "unfair" distribution. In the "fair" distribution, your end numbers tend to go back and forth between 1 and 2 match-sets guaranteed. In the "unfair" distribution, your end numbers are almost always going to be only 1 match set guaranteed. In neither case should you ever be getting back 0 match sets.

2. In the "fair" distribution, your front number matched-sets have the same odds of returning as your end number matched sets (1, and no more than 2 times guaranteed). In the "unfair" distribution, you'll find several match sets that will return matched sets over 10 times, and then a few more at 9 and some more at 8, a good amount of 4's and 3's and then down to 1's. Basically, your front numbers will be weighted to match not "more often," but "more heavily" if they do hit.

The heavy distribution differential can be easily drawn out, like this (using currency as the currency ;):

a. Front numbers.

1. Fair distribution: Matched set 123 is drawn. We match it twice. Each payout on a matched set it 5 dollars. We've made 10 dollars.
2. Unfair distribution: Matched set 123 is drawn. We match it 11 times. Each payout on a matched set is 5 dollars. We've made 55 dollars.

b. End numbers

1. Fair distribution: Matched set 789 is drawn. We may match it twice (rather than just once). Each payout on a matched set it 5 dollars. We've made 10 dollars.
2. Unfair distribution: Matched set 789 is drawn. We match it once. Each payout on a matched set it 5 dollars. We've made 5 dollars.

So, yes, I have to agree that a difference does exist (and would actually love to find the most economic way to make both ends of the distribution weigh in at 8 to 11 returns without having to run up too many combinations (At a certain point your expenses outweigh your gains... not to mention that those gains are only "possible" and not real until you, maybe, get lucky ;)

Although we went over this previously, I'll repost some data, with slight variations, so that the full code for both the "fair" and "unfair" distributions are covered.

Enjoy :)



FAIR:


@ball_draw_pool = qw(12345 12346 12347 12348 12356 12357 12358 12367 12368 12378 12456 12457 12458 12467 12468 12478 12567 12568 12578 12678 13456 13457 13458 13467 13468 13478 13567 13568 13578 13678 14567 14568 14578 14678 15678 23456 23457 23458 23467 23468 23478 23567 23568 23578 23678 24567 24568 24578 24678 25678 34567 34568 34578 34678 35678 45678);
@rev_ball_draw_pool = qw(45678 35678 34678 34578 34568 34567 25678 24678 24578 24568 24567 23678 23578 23568 23567 23478 23468 23467 23458 23457 23456 15678 14678 14578 14568 14567 13678 13578 13568 13567 13478 13468 13467 13458 13457 13456 12678 12578 12568 12567 12478 12468 12467 12458 12457 12456 12378 12368 12367 12358 12357 12356 12348 12347 12346 12345);

@ball_trap_pool = qw(123 124 125 126 127 128 134 135 136 137 138 145 146 147 148 156 157 158 167 168 178 234 235 236 237 238 245 246 247 248 256 257 258 267 268 278 345 346 347 348 356 357 358 367 368 378 456 457 458 467 468 478 567 568 578
678);

foreach $smaller (@ball_trap_pool) {
@smaller = split("",$smaller);
foreach $larger (@ball_draw_pool) {
print "$larger =~ $smaller[0] && $larger =~ $smaller[1] && $larger =~ $smaller[2]\n";
if ( $larger =~ $smaller[0] && $larger =~ $smaller[1] && $larger =~ $smaller[2] ) {
$total_pool{$larger} .= $smaller;
last;
$|=1;
}
}
}
foreach $smaller (@ball_trap_pool) {
@smaller = split("",$smaller);
foreach $larger (@rev_ball_draw_pool) {
print "$larger =~ $smaller[0] && $larger =~ $smaller[1] && $larger =~ $smaller[2]\n";
if ( $larger =~ $smaller[0] && $larger =~ $smaller[1] && $larger =~ $smaller[2] ) {
$total_pool{$larger} .= $smaller;
last;
$|=1;
}
}
}
$counter = 1;
foreach $key (sort keys %total_pool ) {
$total_poolkey = length $total_pool{$key};
if ( $total_poolkey <= 6 ) {
next;
}
print "Game $counter: $key -- $total_pool{$key}\n";
$counter++;
}



UNFAIR


@ball_draw_pool = qw(12345 12346 12347 12348 12356 12357 12358 12367 12368 12378 12456 12457 12458 12467 12468 12478 12567 12568 12578 12678 13456 13457 13458 13467 13468 13478 13567 13568 13578 13678 14567 14568 14578 14678 15678 23456 23457 23458 23467 23468 23478 23567 23568 23578 23678 24567 24568 24578 24678 25678 34567 34568 34578 34678 35678 45678);

@ball_trap_pool = qw(123 124 125 126 127 128 134 135 136 137 138 145 146 147 148 156 157 158 167 168 178 234 235 236 237 238 245 246 247 248 256 257 258 267 268 278 345 346 347 348 356 357 358 367 368 378 456 457 458 467 468 478 567 568 578 678);

foreach $smaller (@ball_trap_pool) {
@smaller = split("",$smaller);
foreach $larger (@ball_draw_pool) {
print "$larger =~ $smaller[0] && $larger =~ $smaller[1] && $larger =~ $smaller[2]\n";
if ( $larger =~ $smaller[0] && $larger =~ $smaller[1] && $larger =~ $smaller[2] ) {
$total_pool{$larger} .= $smaller;
last;
$|=1;
}
}
}
$counter = 1;
foreach $key (sort keys %total_pool ) {
$total_poolkey = length $total_pool{$key};
if ( $total_poolkey <= 6 ) {
next;
}
print "Game $counter: $key -- $total_pool{$key}\n";
$counter++;
}


, Mike




Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.

Wednesday, September 10, 2008

Brain Teaser: Seemingly Random Number List Selection

Hey there,

We're just about done with this series of somewhat disjointed posts on number pools and guaranteed matches. Hopefully, each post in the series has been somewhat entertaining and far enough removed from the starting post that we kept up some sense of originality. It wasn't too hard (unless we screwed up ;) since there were so many unique concepts to cover within the realm of reaching the Objective of the original post. Please refer back to our post on number pools for definitions of all the major terms and a listing of the Objective (although that definition is repeated in a few other posts along the way).

We're just about at the end of the road, so I thought I'd make today's post a bit of a Brain Teaser. The answer to this is actually pretty interesting and (from my struggling with it) you'll either get it right away or it'll take you a good amount of time (kind of like the M I U Puzzle). I, for one, spent way too much time reading up on number sequences and probability. I'm not an engineering major, so I actually had to reference other materials to decipher the Greek alphabet notation. It was interesting for me (especially the insomniac in me), but not something I'd recommend doing unless you're really into it. One thing I noticed, although this is slightly off topic; when people see you sitting in your easy chair chugging diet Pepsi, popping Diphenhydramine and typing in your terminal window with your lap covered with shreds of paper with interpretive numeric scrawl written all over them, they tend to not ask too many questions. It's a great way to guarantee you'll have the evening to yourself ;)

Anyway; for this post's meat: The brain teaser we have today is pretty straightforward, by way of explanation. Here's the setup:

1. Like we did in our posts on deriving list permutations, sorting lists and sorting lists within lists (not necessarily in that order), we've generated a list of 56 5 digit lists using an 8 digit pool of numbers (1, 2, 3, 4, 5, 6, 7, 8). This list represents all possible permutations of the 8 digit list within 5 digit lists while "absolutely removing duplicates" (i.e. "1, 2, 3, 4, 5" and " 5, 3, 2, 4, 1" would be considered equal and would both be removed). That list of numbers follows here (Note that each line is numbered):

1 1 2 3 4 5
2 1 2 3 4 6
3 1 2 3 4 7
4 1 2 3 4 8
5 1 2 3 5 6
6 1 2 3 5 7
7 1 2 3 5 8
8 1 2 3 6 7
9 1 2 3 6 8
10 1 2 3 7 8
11 1 2 4 5 6
12 1 2 4 5 7
13 1 2 4 5 8
14 1 2 4 6 7
15 1 2 4 6 8
16 1 2 4 7 8
17 1 2 5 6 7
18 1 2 5 6 8
19 1 2 5 7 8
20 1 2 6 7 8
21 1 3 4 5 6
22 1 3 4 5 7
23 1 3 4 5 8
24 1 3 4 6 7
25 1 3 4 6 8
26 1 3 4 7 8
27 1 3 5 6 7
28 1 3 5 6 8
29 1 3 5 7 8
30 1 3 6 7 8
31 1 4 5 6 7
32 1 4 5 6 8
33 1 4 5 7 8
34 1 4 6 7 8
35 1 5 6 7 8
36 2 3 4 5 6
37 2 3 4 5 7
38 2 3 4 5 8
39 2 3 4 6 7
40 2 3 4 6 8
41 2 3 4 7 8
42 2 3 5 6 7
43 2 3 5 6 8
44 2 3 5 7 8
45 2 3 6 7 8
46 2 4 5 6 7
47 2 4 5 6 8
48 2 4 5 7 8
49 2 4 6 7 8
50 2 5 6 7 8
51 3 4 5 6 7
52 3 4 5 6 8
53 3 4 5 7 8
54 3 4 6 7 8
55 3 5 6 7 8
56 4 5 6 7 8


2. Using the technique we looked at in our post on determining maximum sets of lists within pools using binomial coefficients, we've deduced that, since we want to guarantee (within the lists in this list of lists) unique 3 digit combinations, we can do so most economically by selecting 8 of the 5 digit lists from the 56. This is not the exact formula we followed in the noted post (as it showed that the binomial coefficient of 8 over 3 is 56). In fairly loose terms, if we want to maximize the odds that we'll get any given 3 digit list (and not use all 56 lists, which works, but is expensive), we can do so with a minimum of 8 5 digit lists. Those 8 lists follow here:

1 2 3 4 6
1 2 3 5 8
1 2 4 7 8
1 3 6 7 8
1 4 5 6 7
2 3 4 5 7
2 5 6 7 8
3 4 5 6 8


3. Using the numbers from point 1 and 2, above, the following chart shows you at what line (in the list of 5 digit lists) each of the 8 lists we determined would give us the best odds of getting a maximum return on a 3 digit list match up.

2 1 2 3 4 6 1 2 3 4 6
7 1 2 3 5 8 1 2 3 5 8
16 1 2 4 7 8 1 2 4 7 8
30 1 3 6 7 8 1 3 6 7 8
31 1 4 5 6 7 1 4 5 6 7
37 2 3 4 5 7 2 3 4 5 7
50 2 5 6 7 8 2 5 6 7 8
52 3 4 5 6 8 3 4 5 6 8


4. Using the numbers from point 1 and 2, above, the following chart shows you at what line (in the list of 5 digit lists) each of the 20 lists we can also determine would give us the best odds of getting a maximum return on a 4 digit list match (We never covered this, but I just added it to give you some frame of reference if the above 3 points aren't enough - BTW, I generated this list because they weren't enough for me, so no offense intended :)

1 1 2 3 4 5 1 2 3 4 5
8 1 2 3 6 7 1 2 3 6 7
9 1 2 3 6 8 1 2 3 6 8
14 1 2 4 6 7 1 2 4 6 7
15 1 2 4 6 8 1 2 4 6 8
18 1 2 5 6 8 1 2 5 6 8
19 1 2 5 7 8 1 2 5 7 8
21 1 3 4 5 6 1 3 4 5 6
22 1 3 4 5 7 1 3 4 5 7
23 1 3 4 5 8 1 3 4 5 8
26 1 3 4 7 8 1 3 4 7 8
35 1 5 6 7 8 1 5 6 7 8
38 2 3 4 5 8 2 3 4 5 8
39 2 3 4 6 7 2 3 4 6 7
42 2 3 5 6 7 2 3 5 6 7
45 2 3 6 7 8 2 3 6 7 8
46 2 4 5 6 7 2 4 5 6 7
49 2 4 6 7 8 2 4 6 7 8
52 3 4 5 6 8 3 4 5 6 8
53 3 4 5 7 8 3 4 5 7 8


Now, here's the fun part. Considering that:

a) no matter how many times we do this using the exact parameters, the results (the lists and the placement of the 8 most economical choices) are totally consistent.
b) If we change anything (like make our list of "1, 2, 3, 4, 5, 6, 7, 8" into "1, 4, 3, 2, 5, 6, 7, 8") about our 8 digit list (assuming that we don't resort everything to numeric order before generating our 8 best 5 digit lists), the outcome will be affected in that the 8 lists will not only contain different numerals, but also end up matching at different numbered locations on master list of 56 lists.

Considering that, how am I determining where to place my 8 5 digit lists in relation to my 56 list list. Or, in other terms, how am I picking the 8 5 digit lists I feel will give me the best odds of matching a 3 digit combination of any 3 unique digits from the 8 digit list used to seed these 5 digit selections?

Think about it, but not too hard. This is only fun if you're having fun with it. If it starts to upset you, watch something violent, yet satisfying (like a good revenge flick), on television and get some sleep ;)

Cheers,

, Mike




Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.

Tuesday, September 9, 2008

Finding Overlapping Matches Using Perl's Lookahead Assertion Matching On Linux and Unix

Hey there,

Here's another topic that relates to our larger series on
number pools and guaranteed combinations within fixed lists
while still being worthy of having its own post. Regular expression matching with Perl for Linux or Unix is fairly simple at its most basic (as are most implementations of regular expression matching). Taken to its most remedial level, you can use a regular expression as a poor man's "grep" (and, oddly enough, the "re" in grep actually stands for regular expression). Although this use of regular expression pattern matching does have its place, it doesn't really merit use outside of tools designed to apply it in that manner and will suck all the joy right out of creating your own regular expressions. In many instances, a well thought-out regular expression can convince most non-technical people in the room that you're a computer genius who's brain possesses more synapses, forming more bridges and firing more rapidly than anyone's ever should. If you show someone something like "/word/" they're far less likely to be impressed ( unless they consider putting letters in between delimiters a Herculean challenge ;)

If you just up your game a little, you begin to see the power of regular expressions in Perl, and - every once in a while - find yourself in a state of utter confusion. Ironically, this is because most regular expression engines give you more than enough rope to get the job done (or is it just enough to hang yourself with? That's for later. We'll try to keep this post positive :)

Regular expression matching within Perl makes it very simple to find out if a certain pattern might appear within a certain expression. For instance, given the expression:

123456abc123456abc

You could construct a Perl regular expression to find out how many times the pattern "123456" occurs in that expression and then print all of those occurrences out in a very short script that you could just type at the command line with the -e switch (and the ending "g" option to your /REGEXP/ definition, which indicates that Perl should match the REGEXP as many times as it possibly can within the given expression - with some limitations, as we'll see below ):

host # perl -e '$variable = "123456abc123456abc"; @variable = $variable =~ /123456/g;print "@variable\n";'
123456 123456


And you can do the same thing to match all contiguous 2 digit numerals in your expression. This is where you'll get a result that you, perhaps, wouldn't expect or don't want:

host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /\d\d/g;print "@variable\n";'
12 34 56 12 34 56


While this is correct, per Perl's (and most other) regular expression parsing rules, you'll note that your expression only returns six sets of double digits (In order: 12, 34, 56, 12, 34, 56). This simple match functionality matches two digits and then moves on to the next two; effectively forgetting the 2 digits that bridge the first 2 digits to the second 2 digits. This is totally normal behaviour. Once the first 2 digits are matched, they are removed from the match pool and the process repeats on the, now, shorter string.

However, if you want (or need) to know how many contiguous 2 digit numerals appear in your expression, you would want to see output like this:

12 23 34 45 56 12 23 34 45 56

demonstrating that there are actually 10 matches on a regular expression looking for contiguous double digits within your expression. And, this can be done!

Using what is commonly referred to as a lookahead expression (or lookahead assertion), you can match all contiguous 2 digit numbers in your expression "correctly" (by which we mean that the overlapping matches won't get swallowed up or lost in the matching process). This command line will do just that for you:

host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d\d))/g;print "@variable\n";'
12 23 34 45 56 12 23 34 45 56


This sort of match is also called a zero-width assertion, meaning that the parentheses surrounding your regular expression (i.e. (?=YourRegularExpression)) don't do any capturing. In fact the "(?=)" part of the regular expression is built into Perl and defined as a zero width lookahead assertion. This means you can use it to match a pattern based on what comes after it. For instance the zero width lookahead assertion:

(?=\d)

would match a numeric character. But, it would specifically match when it was "following" something else. So if you had a string "abcdef3", this pattern - "(\w(?=\d))" - would match any alpha character followed by a numeric:

host # perl -e '$variable = "abcdef3"; @ variable = $variable =~ /(\w(?=\d))/;print "@variable\n";'
f

and, yes, "f" is the only character in our string followed by a number.

So, basically, our expression "(?=(\d\d))" is matching any zero width (starting from zero and incrementing by one as many times as possible - because of the "g" we tag on to the end of our matches to make them "greedy" ;) pattern followed by 2 digits or numeric characters. You can prove that the lack of a character to "lookahead" from (as in our expression "(?=(\d\d))" ) will default to zero, by seeing what happens if you tell the pattern that you're looking for two digits following a single digit with "\d(?=(\d\d))", like so:

host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /\d(?=(\d\d))/g;print "@variable\n";'
23 34 45 56 23 34 45 56


You only get a return of 8 sets, instead of 10, on this match because you've stated that the first double digit match must follow a single digit. Knowing what you know now (without getting into negative lookahead assertions or lookbehind/negative-lookbehind assertions), it should be fairly simple for you to determine the maximum amount of sets you can generate from a given pool without worrying about normal regular expression loss. You can say, with certainty, that the string "123456abc123456abc" contains 12 single digits, 10 sets of double digits, 8 sets of triple digits, 6 sets of quadruple digits, 4 sets of quintuple digits and 2 sets of sextuple digits.

Below is a quick table showing you those results. Note that rather than just adding another "\d" to each line, which would make it spill over the edges of the page (if it hasn't already), we use the "{n}" notation, where "n" equals both the highest and lowest number of occurrences of your pattern (you can use {n,m} notation to indicate lowest (n) and highest (m), but using {n} is the equivalent of using {n,m} with both "n" and "m" being identical and is, therefore, more economical ...quite unlike this sentence ;)

host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d{1}))/g;print "@variable\n";' >-- The {1} isn't necessary, but we left it in there for consistency's sake.
1 2 3 4 5 6 1 2 3 4 5 6
host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d{2}))/g;print "@variable\n";'
12 23 34 45 56 12 23 34 45 56
host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d{3}))/g;print "@variable\n";'
123 234 345 456 123 234 345 456
host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d{4}))/g;print "@variable\n";'
1234 2345 3456 1234 2345 3456
host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d{5}))/g;print "@variable\n";'
12345 23456 12345 23456
host # perl -e '$variable = "123456abc123456abc"; @ variable = $variable =~ /(?=(\d{6}))/g;print "@variable\n";'
123456 123456


If you've checked out yesterday's post on determining maximum pool sets and combine it with this primitive "overlap matching" method of weighted distribution accounting, you can see that our Objective is beginning to come into sight :)

Cheers,

, Mike




Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.

Sunday, May 18, 2008

Doing Search And Replace In Multiple Files With Unix and Linux Perl - Easy Or Hard?

Hey There,

For this weeks "Lazy Sunday" post we're going to take a look at the versatility of Perl on Linux or Unix. While I'm fairly certain there's little argument that it's the best tool for most "extraction" and "reporting" functions when used in complicated situations, it's always been more interesting to me because of the wide range of ways you can complete any sort of task.

Today we're going to take a look at two different ways to do search and replace in multiple files using strictly Perl. The first way will be obnoxiously long and the second way will be almost invisible ;)

For both situations, we'll assume that we have 15 files all in the same directory. We'll also assume that we're logged into our favorite flavour of Linux or Unix OS and, coincidentally, in the same directory as those files. All the files are text files and are humungous. And, finally, all of the files are stories where the main character's name is Waldo, they've never been published and the writer's had a change of heart and decided to name his main character Humphrey. It could happen ;)

1. The hard way (or, if you prefer, the long way):

We'll write a script to read in each file and scour it, line by line. For lines on which the name Waldo appears, we'll replace that with Humphrey. We're taking into account, also, that Waldo may be named more than once on any particular line and that the name Waldo may have accidentally been mistyped with a leading lowercase "w," which needs to be corrected. That script would look something like this:

#!/usr/bin/perl

#
# replace_waldo.pl - change Waldo to Humphrey in all files.
#
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

@all_files = `ls -1d *`;
$search_term = "Waldo";
$replace_term = "Humphrey";

foreach $file (@all_files) {
$got_one = 0;
chomp($file);
open(FILE, "<$file");
@file=<FILE>;
close(FILE);
foreach $line (@file) {
if ( $line =~ /Waldo/i ) {
$line =~ s/Waldo/Humphrey/gi;
$got_one = 1
}
}
if ( $got_one ) {
open(NEWFILE, ">$file.new");
print NEWFILE @file;
close(NEWFILE);
rename("$file.new", "$file");
}
}


2. The easy way (or, again, the short way):

Assuming the exact same convoluted situation, here's another way to do it (which we've covered in a bit more detail in this older post on using Perl like Sed or Awk):

From the command line we'll type:

host # perl -p -i -e 's/Waldo/Humphrey/gi' *

And we're done :)

Of course, the longer method is better suited for situations in which there are other extenuating circumstances. Or, perhaps, even more work to do. For the sort of limited situation we've laid out today, I will almost always go with the second method (Who wants pie? :)... Unless I have lots of time on my hands ;)

Cheers,

, Mike