Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
more examples in 99-problems
  • Loading branch information
prakashk committed May 6, 2013
1 parent 4b171a7 commit b5b6bec
Show file tree
Hide file tree
Showing 9 changed files with 2,401 additions and 0 deletions.
54 changes: 54 additions & 0 deletions t/099-problems/26.t
@@ -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();
2,135 changes: 2,135 additions & 0 deletions t/099-problems/27.t

Large diffs are not rendered by default.

51 changes: 51 additions & 0 deletions t/099-problems/28.t
@@ -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();
21 changes: 21 additions & 0 deletions t/099-problems/31.t
@@ -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();
15 changes: 15 additions & 0 deletions t/099-problems/32.t
@@ -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();
19 changes: 19 additions & 0 deletions t/099-problems/33.t
@@ -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();
26 changes: 26 additions & 0 deletions t/099-problems/34.t
@@ -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();
31 changes: 31 additions & 0 deletions t/099-problems/35.t
@@ -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();
49 changes: 49 additions & 0 deletions t/099-problems/36.t
@@ -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();

0 comments on commit b5b6bec

Please sign in to comment.