Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Browse files
Browse the repository at this point in the history
more examples in 99-problems
- Loading branch information
Showing
9 changed files
with
2,401 additions
and
0 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,54 @@ | ||
# P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list. | ||
|
||
# In how many ways can a committee of 3 be chosen from a group | ||
# of 12 people? We all know that there are C(12,3) = 220 | ||
# possibilities (C(N,K) denotes the well-known binomial | ||
# coefficient). For pure mathematicians, this result may be | ||
# great. But we want to really generate all the possibilities. | ||
|
||
# Example: | ||
|
||
# moe> combinations(3, ['a', 'b', 'c', 'd', 'e', 'f']) | ||
# [['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'b', 'e'], ...] | ||
|
||
use Test::More; | ||
|
||
sub concat(@a, @b) { | ||
@b.each(-> ($x) { @a.push($x) }); | ||
@a | ||
} | ||
|
||
sub combinations($n, @list) { | ||
if ($n == 1) { | ||
@list.map(-> ($x) { [$x] }); | ||
} | ||
elsif (@list.length <= $n) { | ||
[@list]; | ||
} | ||
else { | ||
concat( | ||
combinations($n - 1, @list.tail) | ||
.map( | ||
-> (@c) { | ||
[@list.head, @c].flatten | ||
} | ||
), | ||
combinations($n, @list.tail) | ||
) | ||
} | ||
} | ||
|
||
ok(combinations(3, ['a', 'b', 'c', 'd', 'e', 'f']) | ||
.eqv([["a", "b", "c"], ["a", "b", "d"], ["a", "b", "e"], ["a", "b", "f"], | ||
["a", "c", "d"], ["a", "c", "e"], ["a", "c", "f"], | ||
["a", "d", "e"], ["a", "d", "f"], | ||
["a", "e", "f"], | ||
["b", "c", "d"], ["b", "c", "e"], ["b", "c", "f"], | ||
["b", "d", "e"], ["b", "d", "f"], | ||
["b", "e", "f"], | ||
["c", "d", "e"], ["c", "d", "f"], | ||
["c", "e", "f"], | ||
["d", "e", "f"]]), | ||
"... P26"); | ||
|
||
done_testing(); |
Large diffs are not rendered by default.
Oops, something went wrong.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,51 @@ | ||
# P28 (**) Sorting a list of lists according to length of sublists. | ||
|
||
# a) We suppose that a list contains elements that are lists | ||
# themselves. The objective is to sort the elements of the list | ||
# according to their length. E.g. short lists first, longer lists | ||
# later, or vice versa. | ||
|
||
# Example: | ||
|
||
# moe> lsort([['a', 'b', 'c'], ['d', 'e'], ['f', 'g', 'h'], ['d', 'e'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o']]) | ||
# [['o'], ['d', 'e'], ['d', 'e'], ['m', 'n'], ['a', 'b', 'c'], ['f', 'g', 'h'], ['i', 'j', 'k', 'l']] | ||
|
||
# b) Again, we suppose that a list contains elements that are | ||
# lists themselves. But this time the objective is to sort the | ||
# elements according to their length frequency; i.e. in the | ||
# default, sorting is done ascendingly, lists with rare lengths | ||
# are placed, others with a more frequent length come later. | ||
|
||
# Example: | ||
|
||
# moe> lsort_freq([List('a', 'b', 'c'], ['d', 'e'], ['f', 'g', 'h'], ['d', 'e'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o'])) | ||
# [['a', 'b', 'c'], ['f', 'g', 'h'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o'], ['d', 'e'], ['d', 'e']] | ||
|
||
# Note that in the above example, the first two lists in the | ||
# result have length 4 and 1 and both lengths appear just | ||
# once. The third and fourth lists have length 3 and there are two | ||
# list of this length. Finally, the last three lists have length | ||
# 2. This is the most frequent length. | ||
|
||
use Test::More; | ||
|
||
sub lsort(@list) { | ||
@list.sort(-> ($a, $b) { $a.length <=> $b.length }) | ||
} | ||
|
||
sub lsort_freq(@list) { | ||
my %freq = {}; | ||
@list.each(-> ($l) { %freq{~$l} = +%freq{~$l} + 1; }); | ||
|
||
# second criterion added to fix the ordering of same-frequency lists | ||
@list.sort(-> ($a, $b) { %freq{~$a} <=> %freq{~$b} || ~$a cmp ~$b }); | ||
} | ||
|
||
my @list = [['a', 'b', 'c'], ['d', 'e'], ['f', 'g', 'h'], ['d', 'e'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o']]; | ||
my @sorted_1 = [['o'], ['d', 'e'], ['d', 'e'], ['m', 'n'], ['a', 'b', 'c'], ['f', 'g', 'h'], ['i', 'j', 'k', 'l']]; | ||
my @sorted_2 = [['a', 'b', 'c'], ['f', 'g', 'h'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o'], ['d', 'e'], ['d', 'e']]; | ||
|
||
ok(lsort(@list).eqv(@sorted_1), "... P28-1"); | ||
ok(lsort_freq(@list).eqv(@sorted_2), "... P28-2"); | ||
|
||
done_testing(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,21 @@ | ||
# P31 (**) Determine whether a given integer number is prime. | ||
|
||
# moe> is_prime(7) | ||
# true | ||
|
||
use Test::More; | ||
|
||
# simplistic, not-very-efficient prime-checker | ||
sub is_prime($number) { | ||
if ($number < 2) { | ||
false | ||
} | ||
else { | ||
!((2..($number.sqrt.Int)).first(-> ($f) { $number % $f == 0 }).defined) | ||
} | ||
} | ||
|
||
is(is_prime(7), true, "... P31-1"); | ||
is(is_prime(28), false, "... P31-2"); | ||
|
||
done_testing(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,15 @@ | ||
# P32 (**) Determine the greatest common divisor of two positive integer numbers. | ||
# Use Euclid's algorithm. | ||
|
||
# moe> gcd(36, 63) | ||
# 9 | ||
|
||
use Test::More; | ||
|
||
sub gcd($a, $b) { | ||
$b == 0 ? $a : gcd($b, $a % $b) | ||
} | ||
|
||
is(gcd(36, 63), 9, "... P32"); | ||
|
||
done_testing(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,19 @@ | ||
# P33 (*) Determine whether two positive integer numbers are coprime. | ||
# Two numbers are coprime if their greatest common divisor equals 1. | ||
|
||
# moe> is_coprime_to(35, 64) | ||
# true | ||
|
||
use Test::More; | ||
|
||
sub gcd($a, $b) { | ||
$b == 0 ? $a : gcd($b, $a % $b) | ||
} | ||
|
||
sub is_coprime_to($a, $b) { | ||
gcd($a, $b) == 1 | ||
} | ||
|
||
is(is_coprime_to(35, 64), true, "... P33"); | ||
|
||
done_testing(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,26 @@ | ||
# P34 (**) Calculate Euler's totient function phi(m). | ||
|
||
# Euler's so-called totient function phi(m) is defined as the | ||
# number of positive integers r (1 <= r <= m) that are coprime to | ||
# m. | ||
|
||
# moe> totient(10) | ||
# 4 | ||
|
||
use Test::More; | ||
|
||
sub gcd($a, $b) { | ||
$b == 0 ? $a : gcd($b, $a % $b) | ||
} | ||
|
||
sub is_coprime_to($a, $b) { | ||
gcd($a, $b) == 1 | ||
} | ||
|
||
sub totient($n) { | ||
(1..($n-1)).grep(-> ($m) { is_coprime_to($m, $n) }).length | ||
} | ||
|
||
is(totient(10), 4, "... P34"); | ||
|
||
done_testing(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,31 @@ | ||
# P35 (**) Determine the prime factors of a given positive integer. | ||
# Construct a flat list containing the prime factors in ascending order. | ||
|
||
# moe> prime_factors(315) | ||
# [3, 3, 5, 7] | ||
|
||
use Test::More; | ||
|
||
# from P31 | ||
# simplistic, not-very-efficient prime-checker | ||
sub is_prime($number) { | ||
if ($number < 2) { | ||
false | ||
} else { | ||
!((2..($number.sqrt.Int)).first(-> ($f) { $number % $f == 0 }).defined) | ||
} | ||
} | ||
|
||
sub prime_factors($number) { | ||
my $factor = (2..(($number/2).Int)).first(-> ($f) { $number % $f == 0 && is_prime($f) }); | ||
if ($factor.defined) { | ||
[$factor, prime_factors(($number/$factor).Int)].flatten | ||
} | ||
else { | ||
[$number.Int] | ||
} | ||
} | ||
|
||
ok(prime_factors(315).eqv([3, 3, 5, 7]), "... P35"); | ||
|
||
done_testing(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,49 @@ | ||
# P36 (**) Determine the prime factors of a given positive integer (2). | ||
# Construct a list containing the prime factors and their multiplicity. | ||
|
||
# moe> prime_factor_multiplicity(315) | ||
# [(3 => 2), (5 => 1), (7 => 1)] | ||
|
||
# Alternately, use a Map for the result. | ||
|
||
# moe> prime_factor_multiplicity(315) | ||
# {3 => 2, 5 => 1, 7 => 1} | ||
|
||
use Test::More; | ||
|
||
# from P31 | ||
# simplistic, not-very-efficient prime-checker | ||
sub is_prime($number) { | ||
if ($number < 2) { | ||
false | ||
} else { | ||
!((2..($number.sqrt.Int)).first(-> ($f) { $number % $f == 0 }).defined) | ||
} | ||
} | ||
|
||
# from P35 | ||
sub prime_factors($number) { | ||
my $factor = (2..(($number/2).Int)).first(-> ($f) { $number % $f == 0 && is_prime($f) }); | ||
if ($factor.defined) { | ||
[$factor, prime_factors(($number/$factor).Int)].flatten | ||
} else { | ||
[$number.Int] | ||
} | ||
} | ||
|
||
sub prime_factor_multiplicity($number) { | ||
my %freq = {}; | ||
prime_factors($number).each(-> ($n) { %freq{~$n} = +%freq{~$n} + 1; }); | ||
%freq; | ||
} | ||
|
||
my %pfm_315 = prime_factor_multiplicity(315); | ||
|
||
# .eqv method should work for hashes too | ||
# ok(%pfm_315.eqv({3 => 2, 5 => 1, 7 => 1}), "... P36"); | ||
|
||
is(%pfm_315{'3'}, 2, "... P36-1"); | ||
is(%pfm_315{'5'}, 1, "... P36-2"); | ||
is(%pfm_315{'7'}, 1, "... P36-3"); | ||
|
||
done_testing(); |