Get money for playing games for free: string

Showing posts with label string. Show all posts

Saturday, September 23, 2017

String extracts in Perl with split match and regular expressions

Lately I had to solve the following issue:
extract process id (pid) and program name from the header line of pmap.

The strings can take these forms from simple to complex:

 123: cmd 123: cmd -x foo 123: /usr/bin/cmd 123: /usr/bin/cmd -x foo

and more complex with more parameters which are trickier to parse

 123: /usr/bin/cmd -x /home/foo 123: /usr/bin/cmd -x 456: -d /home/foo

i.e. very genereally speaking there is a pid followed by a colon and then a more or less complex command line where the program name can be fully qualified and carry a number of parameters. The last example deliberately introduces the digit and colon again as parameters.

Here is a try to express the string more verbally as a sequence of

a number of digits

a colon

a tab

a program name, optionally qualified

optionally: an arbitrary number of space separated parameters (could me multiple spaces)

There a various solutions to this in Perl and here Ill show two.

 # Example string $str = "123: /usr/bin/cmd -x /home/foo"; # ^ should be a tab here # First I split the string using an optional colon :* # and a sequence of white space s+ as field delimiters. # This will give me the pid and the program name and strip of the parameters ($pid,$cmd) = split /:*s+/,$str; # In case of a fully qualified program nane # everything up to the last slash needs to be removed $cmd =~ s/.*///; print "pid = $pid X cmd = $cmd ";

Always looking for more concise code I wondered whether these two lines couldnt be shortened. Here is a one liner which requires explanation of course.

 # Example string $str = "123: /usr/bin/cmd -x /home/foo"; # ^ should be a tab here # I try to match the following reqular expression # a sequence of digits (d+) which will become $1 if successful # a colon and a tab # an optional sequence of characters ending in slash (S+/)* # which will become $2 # a sequence of characters (S+) which will become $3 # The remainder of the string is not important as # we anchor the regular expression at the beginning. $str =~ /^(d+): (S+/)*(S+)/ ; print "pid = $1 X cmd = $3 ";

For easier readability I would have preferred the first code but when taking a deeper look I found some flaws in it namely the handling of incorrect strings. Assume this string below where the colon is missing and a string sits between pid and program name

 $str = "123 xyz /usr/bin/cmd -x 456: /home/foo";

The codes will result in

 # Code 1 pid = 123 xyz /usr/bin/cmd -x 456 X cmd = foo # Code 2 pid = /home/ X cmd =

In both cases the split happens at the wrong place with unforeseeable results.
I can use the second code though to its advantage by applying a check.

 if( $str =~ /^(d+): (S+/)*(S+)/ ) { print "pid = $1 X cmd = $3 "; }

i.e. only when the regular expression is really matched I will use its values. The check gives me assurance.
I cant do this with the split in the first code other than doing a post-check by checking whether the pid really consists of digits etc. which would increase the code.

So I decided to use the regular expression in my code since it is still fairly readable by extracting just three parts of the overall string.
Would I want to extract more, say five or eight components, I probably would fall back to the split and a subsequent validity check.

download file now

Sun dogs Bow String Bridge on Raisin River

Sun dogs over St. Lawrence

Bow bridge, Raisin River

download file now

String matching algorithms implementation in Erlang

1. Naive algorithm

 -module(naive). 
 -export([naive_string_matcher/2]). 
 naive_string_matcher(T,P)-> 
 N = length(T), 
 M = length(P), 
 if 
 M=<M -> 
 Iterations = N - M +1, 
 check_similarity(Iterations,T,P,M,N); 
 true -> 
 {error,invalid} 
 end. 
 check_similarity(0,T,P,M,N)-> 
 {ok,complete}; 
 check_similarity(Iterations,T,P,M,N)-> 
 Sublist = lists:sublist(T,Iterations,M), 
 if 
 P == Sublist -> 
 io:format("~p == ~p ~n", [Iterations,Sublist]), 
 check_similarity(Iterations-1,T,P,M,N); 
 true -> 
 check_similarity(Iterations-1,T,P,M,N) 
 end.

sdsdsad.

2. Rabin Karp algorithm

 -module(rabin_karp). 
 -compile(export_all). 
 -define(PRIME,3). 
 get_matching_index([],_MatchingList)-> 
 {ok,-1}; 
 get_matching_index(_InputList,[])-> 
 {ok,-1}; 
 get_matching_index(InputList,MatchingList)-> 
 case get_hash_value(lists:reverse(MatchingList), ?PRIME, 0)of 
 {ok,HashValue}-> 
 Sublist = lists:sublist(InputList,1,length(MatchingList)), 
 case get_hash_value(lists:reverse(Sublist), ?PRIME, 0)of 
 {ok,SublistHashValue}-> 
 if 
 HashValue==SublistHashValue -> 
 if 
 Sublist==MatchingList-> 
 {ok,3}; 
 true-> 
 check_hash_matching(InputList,MatchingList,HashValue,length(InputList),length(MatchingList), 
 2,length(InputList)-length(MatchingList)-1,SublistHashValue,Sublist) 
 end; 
 true -> 
 check_hash_matching(InputList,MatchingList,HashValue,length(InputList),length(MatchingList), 
 2,length(InputList)-length(MatchingList)-1,SublistHashValue,Sublist) 
 end; 
 _ -> 
 {ok,-1} 
 end; 
 _ -> 
 {ok,-1} 
 end. 
 check_hash_matching(_InputList,_MatchingList,_MatchingHash,_InputLength,_MatchingLength,_Index,0,_PreviousHashValue,_PreviousSublist)-> 
 {ok,-1}; 
 check_hash_matching(InputList,MatchingList,MatchingHash,InputLength,MatchingLength,Index,Limit,PreviousHashValue,PreviousSublist)-> 
 io:format("{InputList,MatchingList,MatchingHash,InputLength,MatchingLength,Index,Limit,PreviousHashValue,PreviousSublist} : ~p~n", 
 [{InputList,MatchingList,MatchingHash,InputLength,MatchingLength,Index,Limit,PreviousHashValue,PreviousSublist}]), 
 case lists:sublist(InputList,Index,MatchingLength) of 
 []-> 
 io:format("Sublist empty. ~n",[]), 
 {ok,-1}; 
 Sublist -> 
 io:format("Sublist : ~p~n",[Sublist]), 
 case get_hash_value(PreviousSublist,Sublist,PreviousHashValue,?PRIME)of 
 {ok,HashValue}-> 
 io:format("SublistHashValue : ~p~n",[HashValue]), 
 if 
 HashValue==MatchingHash -> 
 if 
 Sublist==MatchingList-> 
 {ok,Index}; 
 true-> 
 check_hash_matching(InputList,MatchingList,MatchingHash,InputLength,MatchingLength,Index+1,Limit,HashValue,Sublist) 
 end; 
 true -> 
 check_hash_matching(InputList,MatchingList,MatchingHash,InputLength,MatchingLength,Index+1,Limit,HashValue,Sublist) 
 end; 
 _ -> 
 io:format("get_hash_value/4 error ~n",[]), 
 {ok,-1} 
 end 
 end. 
 %% For direct hash value calculation. 
 get_hash_value([Char|T],Prime,Sum)-> 
 io:format("{Char,T,Prime,Sum} : ~p~n",[{Char,T,Prime,Sum}]), 
 case get_ascii_value(Char) of 
 {ok,Ascii}-> 
 get_hash_value(T,Prime,Sum+Ascii*math:pow(Prime,length(T))); 
 _ -> 
 {error,error} 
 end; 
 get_hash_value([],_Prime,Sum)-> 
 io:format("Sum : ~p~n",[Sum]), 
 {ok,Sum}. 
 %% For rotating hash value calculation, using previous hash value. 
 get_hash_value([FirstChar|_ ],CurrentCharList,HashValue,Prime)-> 
 io:format("{FirstChar,CurrentCharList,HashValue,Prime} : ~p~n",[{FirstChar,CurrentCharList,HashValue,Prime}]), 
 case get_ascii_value(FirstChar) of 
 {ok,AsciiFirst} -> 
 io:format("AsciiFirst : ~p~n",[AsciiFirst]), 
 case get_ascii_value(lists:last(CurrentCharList)) of 
 {ok,AsciiLast} -> 
 io:format("AsciiLast : ~p~n",[AsciiLast]), 
 NewHashValue = (HashValue-AsciiFirst)/Prime + AsciiLast*math:pow(Prime,length(CurrentCharList)-1), 
 io:format("NewHashValue : ~p~n",[NewHashValue]), 
 {ok,NewHashValue}; 
 _ -> 
 {error,error} 
 end; 
 _ -> 
 {error,error} 
 end. 
 get_ascii_value(Char)-> 
 if 
 is_atom(Char)-> 
 [Ascii]=atom_to_list(Char), 
 {ok,Ascii}; 
 is_list(Char)-> 
 [Ascii]=Char, 
 {ok,Ascii}; 
 is_integer(Char)-> 
 Ascii=Char, 
 {ok,Ascii}; 
 true -> 
 {error,error} 
 end.

3. Knuth�Morris�Pratt(KMP) Pattern Matching algorithm
Will be available soon...

download file now

String Arrays in Vala

String Arrays are simply bunches of strings grouped together

string[] apples = {"red delicious", "granny smith", "macintosh", "gala", "fuji"}

They look like Python lists, but they are not. They often dont work like lists (you cannot slice them), but they work *really* fast. They are useful if you have a data set that is (mostly) immutable...you can append to it, but I havent found a way to delete strings from the array without copying everything else into a new array.

Here is a demo program showing how to

Create a string array
Append a string to an array
Match a string in an array
Determine the index of the matched string
Retrieve a string from the array (non-destructively)
Replace a string with another withing an array
Concatenate the array into a single string (for printing)

// string_array.vala

// If a in b
void if_a_in_b ( string a, string[] b, string b_name ) {
 if (a in b) { 
 stdout.printf("Found %s in %s ", a, b_name); 
 }
 else {
 stdout.printf("%s not Found in %s ", a, b_name);
 }
 return;
}


// One way to print an array
void print1 (string[] a, string a_name) {
 stdout.printf("Array %s: ", a_name);
 foreach (string item in a) {
 stdout.printf("%s, ", item);
 }
 stdout.printf(" ");
 return;
}

// Another way to print an array
void print2 (string[] a, string a_name) {
 string a_string = string.joinv(", ", a);
 stdout.printf("Array %s : %s ", a_name, a_string);
 return;
}

// Index of an item in an array
void index_array (string[] a, string a_name, string match) {
 // Record the index of all matches
 int[] indexes = {};
 int i;
 for (i = 0; i < a.length; i++) {
 if (a[i] == match) {
 indexes += i;
 }
 }
 // Print the results
 if (indexes.length == 0) {
 stdout.printf("Indexing %s: %s not found ", a_name, match);
 }
 else if (indexes.length == 1) {
 stdout.printf("Indexing %s: %s found at position %d ", 
 a_name, match, indexes[0]); 
 }
 else if (indexes.length == 2) {
 stdout.printf("Indexing %s: %s found at positions %d and %d ", 
 a_name, match, indexes[0], indexes[1]); 
 }
 else {
 stdout.printf("Indexing %s: %s found at positions ", 
 a_name, match);
 // Convert ints to a strings
 int j;
 for (j = 0; j < indexes.length; j++) {
 if ( j < (indexes.length - 1)) {
 stdout.printf("%d, ", indexes[j]);
 }
 else {
 stdout.printf("and %d. ", indexes[j]);
 }
 }
 }
 return;
}



void arrays () {
 // Create two string arrays 
 string[] orange = { "fred", "joe", "allen", "steve" };
 string[] blue = { "jane", "sam", "ellie", "terri" };

 // Test contents of each array
 if_a_in_b ("fred", orange, "Orange");
 if_a_in_b ("fred", blue, "Blue");

 // Length of an array
 stdout.printf("List length: %i ", orange.length);

 // Item from an array
 stdout.printf("Orange item #2: %s ", orange[1]);

 // Replace one string in an array
 blue[2] = "pamela";

 // Determine the index (location) of a string in an array
 index_array(blue, "blue", "pamela");

 // Append one string to an array 
 blue += "stacy";

 // Print an array
 print1(orange, "orange");
 print2(blue, "blue");

 return;
}


// Main
public static void main() {
 arrays ();
 stdout.printf("Hello, World ");
 return;
 }

Compile with a simple valac string_array.vala

download file now

Get money for playing games for free

Saturday, September 23, 2017

String extracts in Perl with split match and regular expressions

String extracts in Perl with split match and regular expressions

Monday, August 28, 2017

Sun dogs Bow String Bridge on Raisin River

Sun dogs Bow String Bridge on Raisin River

Thursday, August 3, 2017

String matching algorithms implementation in Erlang

String matching algorithms implementation in Erlang

1. Naive algorithm

Tuesday, August 1, 2017

String Arrays in Vala

String Arrays in Vala