diff options
| -rw-r--r-- | challenge-074/duncan-c-white/README | 88 | ||||
| -rwxr-xr-x | challenge-074/duncan-c-white/perl/ch-1.pl | 53 | ||||
| -rwxr-xr-x | challenge-074/duncan-c-white/perl/ch-2.pl | 86 |
3 files changed, 180 insertions, 47 deletions
diff --git a/challenge-074/duncan-c-white/README b/challenge-074/duncan-c-white/README index 8f0971a5c6..57d2a79ea6 100644 --- a/challenge-074/duncan-c-white/README +++ b/challenge-074/duncan-c-white/README @@ -1,58 +1,52 @@ -Task 1: "Trailing Zeroes +Task 1: "Majority Element -You are given a positive integer $N (<= 10). +You are given an array of integers of size $N. -Write a script to print number of trailing zeroes in $N!. +Write a script to find the majority element. If none found then print -1. +The majority element in a list is the element, if any, that appears more than +floor(size_of_list/2) TIMES. Example 1 -Input: $N = 10 -Output: 2 as $N! = 3628800 has 2 trailing zeroes -Example 2 -Input: $N = 7 -Output: 1 as $N! = 5040 has 1 trailing zero + Input: @A = (1, 2, 2, 3, 2, 4, 2) + Output: 2, as 2 appears 4 times in the list - more than floor(7/2)==3 TIMES. -Example 3 -Input: $N = 4 -Output: 0 as $N! = 24 has 0 trailing zero +Example 2 + Input: @A = (1, 3, 1, 2, 4, 5) + Output: -1 as none of the elements appears more than floor(6/2)==3 TIMES. " -My notes: ok. Very easy. fact and "while mod 10 == 0 inc & div 10" -See also ch-1a.pl, which TABULATES n, n! and trailing-zeroes(n!).. - -Task 2: "Lines Range - -You are given a text file name $file and range $A - $B where $A <= $B. - -Write a script to display lines range $A and $B in the given file. -Example -Input: - - $ cat input.txt - L1 - L2 - L3 - L4 - ... - ... - ... - ... - L100 - -$A = 4 and $B = 12 - -Output: - - L4 - L5 - L6 - L7 - L8 - L9 - L10 - L11 - L12 +My notes: ok. Very easy. + + +Task 2: "FNR Character + +You are given a string $S. + +Write a script to print the series of first non-repeating character (left -> right) for the given string. Print # if none found. + +Example 1 + Input: $S = 'ababc' + Output: 'abb#c' + Pass 1: 'a', the FNR character is 'a' + Pass 2: 'ab', the FNR character is 'b' + Pass 3: 'aba', the FNR character is 'b' + Pass 4: 'abab', no FNR found, hence '#' + Pass 5: 'ababc' the FNR character is 'c' + +Example 2 + Input: $S = 'xyzzyx' + Output: 'xyzyx#' + Pass 1: 'x', the FNR character is 'x' + Pass 2: 'xy', the FNR character is 'y' + Pass 3: 'xyz', the FNR character is 'z' + Pass 4: 'xyzz', the FNR character is 'y' + Pass 5: 'xyzzy', the FNR character is 'x' + Pass 6: 'xyzzyx', no FNR found, hence '#' " -My notes: ok. Seems even easier. I/O and a line number count (let's use $.) +My notes: why is the FNR of "ab" (in pass 2) 'b' rather than 'a'? Last non-repeating +character would be more like it. Basically: in each pass, take substr(1,len PASS) and then +remove each LAST char if it's duplicated earlier in the substring, otherwise that's the FNR. +If the string is empty, no FNR, print #. diff --git a/challenge-074/duncan-c-white/perl/ch-1.pl b/challenge-074/duncan-c-white/perl/ch-1.pl new file mode 100755 index 0000000000..723b1c994b --- /dev/null +++ b/challenge-074/duncan-c-white/perl/ch-1.pl @@ -0,0 +1,53 @@ +#!/usr/bin/perl +# +# Task 1: "Majority Element +# +# You are given an array of integers of size $N. +# +# Write a script to find the majority element. If none found then print -1. +# The majority element in a list is the element, if any, that appears more than +# floor(size_of_list/2) TIMES. +# +# Example 1 +# +# Input: @A = (1, 2, 2, 3, 2, 4, 2) +# Output: 2, as 2 appears 4 times in the list - more than floor(7/2)==3 TIMES. +# +# Example 2 +# +# Input: @A = (1, 3, 1, 2, 4, 5) +# Output: -1 as none of the elements appears more than floor(6/2)==3 TIMES. +# " +# +# My notes: ok. Very easy. +# + +use strict; +use warnings; +use feature 'say'; +#use Function::Parameters; +#use Data::Dumper; + +die "Usage: majority-element list_of_values\n" if @ARGV==0; +my @list = @ARGV; + +my $len = @list; +my $half = int($len/2); +#say "len=$len, half=$half"; + +# convert list to bag (frequency hash) +my %freq; +$freq{$_}++ foreach @list; + +my $found = 0; +foreach my $k (keys(%freq)) +{ + $found = $k if $freq{$k} > $half; +} +if( $found ) +{ + say "$found (appears $freq{$found} times, more than $half)"; +} else +{ + say "-1"; +} diff --git a/challenge-074/duncan-c-white/perl/ch-2.pl b/challenge-074/duncan-c-white/perl/ch-2.pl new file mode 100755 index 0000000000..fe129575a3 --- /dev/null +++ b/challenge-074/duncan-c-white/perl/ch-2.pl @@ -0,0 +1,86 @@ +#!/usr/bin/perl +# +# Task 2: "FNR Character +# +# You are given a string $S. +# +# Write a script to print the series of first non-repeating character (left -> right) for the given string. Print # if none found. +# +# Example 1 +# Input: $S = 'ababc' +# Output: 'abb#c' +# Pass 1: 'a', the FNR character is 'a' +# Pass 2: 'ab', the FNR character is 'b' +# Pass 3: 'aba', the FNR character is 'b' +# Pass 4: 'abab', no FNR found, hence '#' +# Pass 5: 'ababc' the FNR character is 'c' +# +# Example 2 +# Input: $S = 'xyzzyx' +# Output: 'xyzyx#' +# Pass 1: 'x', the FNR character is 'x' +# Pass 2: 'xy', the FNR character is 'y' +# Pass 3: 'xyz', the FNR character is 'z' +# Pass 4: 'xyzz', the FNR character is 'y' +# Pass 5: 'xyzzy', the FNR character is 'x' +# Pass 6: 'xyzzyx', no FNR found, hence '#' +# " +# +# My notes: why is the FNR of "ab" (in pass 2) 'b' rather than 'a'? Last non-repeating +# character would be more like it. Basically: in each pass, take substr(1,len PASS) and then +# remove each LAST char if it's duplicated earlier in the substring, otherwise that's the FNR. +# If the string is empty, no FNR, print #. +# + +use strict; +use warnings; +use feature 'say'; +use Function::Parameters; +#use Data::Dumper; + +# +# my $result = fnrpass($s); +# Given a substring $s, perform one FNR pass and return a single +# character - the last-most non-repeating character in $sub, or '#' if +# all chars in $s repeat. +# +fun fnrpass( $s ) +{ + my @list = split( //, $s ); + + # convert each char of $s to bag (frequency hash) - same code was in ch-1! + my %freq; + $freq{$_}++ foreach @list; + + foreach my $ch (reverse @list) + { + return $ch if $freq{$ch}==1; + } + return '#'; +} + + +# +# my $fnr = fnr($string); +# Find the First (Last) Non-repeating char string, +# as described above. +# +fun fnr( $string ) +{ + my $len = length($string); + my $result = ''; + foreach my $i (1..$len) + { + my $sub = substr($string,0,$i); # take first $i chars + $result .= fnrpass($sub); + } + return $result; +} + + + +die "Usage: first(last)-non-repeating-char string\n" unless @ARGV==1; +my $string = shift; + +my $fnr = fnr($string); +say "fnr: ", $fnr; |