Skip to content

Instantly share code, notes, and snippets.

@GlulkAlex

GlulkAlex/Least_common_multiple.ipynb

Last active June 3, 2016 17:41
Show Gist options
  • Save GlulkAlex/3ef9d0ed32250192e6dc436662d1e125 to your computer and use it in GitHub Desktop.
Save GlulkAlex/3ef9d0ed32250192e6dc436662d1e125 to your computer and use it in GitHub Desktop.
Download ZIP
Least_common_multiple
Raw
gcd.scala
object Solution extends App{
import scala.annotation.tailrec
import scala.io.StdIn
import scala.util.{Try, Success, Failure}
import scala.math.pow//{abs, pow, ceil, floor}
/*
The first 168 prime numbers (all the prime numbers less than 1000) are:
*/
//prime_LT1000.sliding(10, 10).map(_.toList.mkString(",")).mkString(",\n")
val primes_LT1000: Stream[Int] = Stream(
2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997
)
def direct_Trial_Divisions_Primes_Search(
up_To: Int = 1000
): List[Int] = {
///> work as expected, when primes in ascending order
@annotation.tailrec
def loop(
candidate: Int,
prime: Int,
// filtered | restricted by previously found primes
primes: List[Int],
limit: Int,
is_Condition: Boolean
): Boolean = {
if (
prime >= limit ||
primes.isEmpty
) {
///> base case 1
//condition = true
is_Condition
} else if (candidate % prime == 0) {
///> base case 2
//condition = false
false
} else {
///> recursive step
loop(
candidate = candidate,
prime = primes.head,
primes = primes.tail,
limit = limit,
is_Condition = is_Condition
)
}
}
// must be sorted in ascending order
var primes_List: List[Int] = List(2)
var test_limit: Int = 1
var condition: Boolean = true
for (candidate <- 3 to up_To by 1) {
// scala> math.pow(3, 0.5).toInt
// res2: Int = 1
//scala> math.pow(4, 0.5)
//res1: Double = 2.0
test_limit = math.pow(candidate, 0.5).toInt
condition = true
if (false) {
// work as expected
// not-filtered | restricted by previously found primes
for (trail_Val <- 2 to (test_limit + 1) by 1) {
if (candidate % trail_Val == 0) {
condition = false
//break
}
}
}
if (true) {
// work as expected
// filtered | restricted by previously found primes
condition = loop(
candidate = candidate,
prime = primes_List.head,
primes = primes_List.tail,
limit = test_limit + 1,
is_Condition = true//condition
)
}
if (condition) {
// append ?
//primes_List = candidate +: primes_List
primes_List = primes_List :+ candidate
}
}
/*
scala> (100 to 1 by -1).take(20).sorted
res11: scala.collection.immutable.IndexedSeq[Int] = Vector(
81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)
*/
//return
//primes_List.sorted
primes_List
}
def prime_Factorization(
//error: reassignment to val
number: Int,
//error: reassignment to val
prime_Factors_Map: Map[Int, Int] = Map.empty[Int, Int],
is_Debug_Mode: Boolean = false
): Map[Int, Int] = {
var primes_List: List[Int] = direct_Trial_Divisions_Primes_Search(number + 1)
var condition: Boolean = true
var get_Prime: Option[Int] = None
var factors_Map: Map[Int, Int] = prime_Factors_Map
var current_Val: Int = number
if (primes_List.contains(current_Val)) {
factors_Map = factors_Map + (current_Val -> 1)
} else {
for (prime <- primes_List) {
condition = true
while (current_Val > 1 && condition) {
if (current_Val % prime == 0) {
get_Prime = factors_Map.get(prime)
/*
if (get_Prime.nonEmpty) {
///> works as expected
///> but how pick max prime power from previous calls
//if (prime_Factors_Map.contains(prime)) {
prime_Factors_Map[prime] += 1
prime_Factors_Map = prime_Factors_Map + (prime -> (get_Prime.get + 1))
} else {
prime_Factors_Map = prime_Factors_Map + (prime -> 1)
}
*/
get_Prime match {
case Some(v) => factors_Map = factors_Map + (prime -> (v + 1))
case _ => factors_Map = factors_Map + (prime -> 1)
}
current_Val = current_Val / prime
} else {
condition = false
}
}
}
}
//return
factors_Map
}
def least_Common_Multiple(
///> Set[Int] may be better
//factors: List[Int],
factors: Array[Int],
is_Debug_Mode: Boolean = false
): Int = {
var max_Prime_Powers_Map = Map.empty[Int, Int]
var get_Prime: Option[Int] = None
var lcm: Int = 1
var number_Factors_Map = Map.empty[Int, Int]
for (number <- factors) {
number_Factors_Map = prime_Factorization(number)//, Map.empty[Int, Int])
if (max_Prime_Powers_Map.isEmpty || max_Prime_Powers_Map.size == 0) {
max_Prime_Powers_Map = number_Factors_Map
} else {
/*
scala> for ((k, v) <- myMap) yield (k, v)
res15: scala.collection.immutable.Map[String,String] = Map(MI -> Michigan, OH -> Ohio, WI -> Wisconsin)
*/
for ((k, v) <- number_Factors_Map) {
get_Prime = max_Prime_Powers_Map.get(k)
get_Prime match {
case Some(p) => if (p < v) {
max_Prime_Powers_Map = max_Prime_Powers_Map + (k -> v)
}
// None
case _ => max_Prime_Powers_Map = max_Prime_Powers_Map + (k -> v)
}
}
}
}
for ((k, v) <- max_Prime_Powers_Map) {
lcm = lcm * math.pow(k, v).toInt
}
//return
lcm
}
///> '#::' is crutial for lazy evaluation, not just append '+:' <- fail
def mult(step: Int, state: Int): Stream[Int] = state #:: mult(step, state + step)
class Mult(seed: Int) {
var accum: Int = seed
def next: Int = {
val current_State: Int = accum
accum += seed
current_State
}
}
def inc_By(seed: Int): Int => Int = (step: Int) => seed + step
def add_Next(s: => Int)(a: => Int) = s + a
///> work as expected
def min_Common_Mult_4_Pair(
int_1: Int,
int_2: Int
): Int = {
var while_Guard: Int = 100000
var generator_1: Mult = new Mult(seed = int_1)
var generator_2: Int => Int = inc_By(seed = int_2)
var val_1: Int = generator_1.next
var val_2: Int = generator_2(int_2)
if (val_1 == val_2) {
//return
val_1
} else {
while (val_1 != val_2 && while_Guard > 0) {
while_Guard -= 1
if (val_1 > val_2) {
val_2 = generator_2(val_2)
} else /*if (val_1 < val_2)*/ {
val_1 = generator_1.next
}
}
//return
val_1
}
}
///> work as expected
def find_Pair_Min_Common_Int(
int_1: Int,
int_2: Int
): Int = {
var while_Guard: Int = 100000
var stream_1: Stream[Int] = mult(step = int_1, state = int_1)
var stream_2: Stream[Int] = mult(step = int_2, state = int_2)
var val_1 = stream_1.head
var val_2 = stream_2.head
if (val_1 == val_2) {
//return
val_1
} else {
while (val_1 != val_2 && while_Guard > 0) {
while_Guard -= 1
if (val_1 > val_2) {
stream_2 = stream_2.tail
val_2 = stream_2.head
} else /*if (val_1 < val_2)*/ {
stream_1 = stream_1.tail
val_1 = stream_1.head
}
}
//return
val_1
}
}
def sequence_Min_Common_Miltiple(
int_List: Array[Int]
): Int = {
//min_Common_Miltiple
var m_C_M: Int = 1
/*
scala> (for (List(v1, v2) <- List(4,7,12,21,42).sliding(2,1)) yield (v1, v2)).toList
res15: List[(Int, Int)] = List((4,7), (7,12), (12,21), (21,42))
*/
for (Array(n1, n2) <- int_List.sliding(2, 1)) {
if (m_C_M > 1) {
//m_C_M = find_Pair_Min_Common_Int(m_C_M, n2)
m_C_M = min_Common_Mult_4_Pair(m_C_M, n2)
} else {
//m_C_M = find_Pair_Min_Common_Int(n1, n2)
m_C_M = min_Common_Mult_4_Pair(n1, n2)
}
}
//return
m_C_M
}
//gcd: [Int >: Double](a: Double, b: Double)Double
//@scala.annotation.tailrec
@tailrec
def gcd/*[Int >: Double]*/(a: Double, b: Double): Double = if (b == 0) {
///> base case
///> ??? a.abs ???
a
} else {
///> base case
// error: could not optimize @tailrec annotated method gcd:
// it is called recursively with different type arguments
gcd(b, a % b)
//gcd(b.toDouble, (a % b).toDouble) //{
//error: could not optimize @tailrec annotated method gcd:
// it contains a recursive call not in tail position
/*
b match {
case 0 => a
case _ => gcd(b, (a % b))
}
*/
}
/*
2 3 4
1,2 => 1:{1},2:{1,2}, dif:{2}, => 2
2,3 => 2:{1,2},3:{1,3}, dif:{2,3) => 2*3=6
6,4 => 6:{1,2,3,6},4:{1,2,4}, dif:{3,6,4) => 3*6*4 = 72 ???
expected (2'*3, 2'*2) => 2'*(2*3) == 12 ? intersect * difference ?
? primes only ?
Using prime factorizations
6,4 => 6:{1,2,3},4:{1,2,2}, common:{1,2} * dif:{3,2) => 1*2*3*2 = 12
*/
def find_Least_Common_Multiple(
factors: Array[Int],
is_Debug_Mode: Boolean = false
): Double = {
@tailrec
def iterator(
seq: Array[Int],
///> lcm
result_Accum: Double = 1
///> Map(1->Set(1?),2->Set(1,2?),3->Set(1,3?),4->Set(1,2,4?))
//factors_Map: Map[Int, Set[Int]]
): Double = {
if (seq.isEmpty) {
///> base case
result_Accum
} else {
///> recursive step
val current_Factor: Int = seq.head
val accum: Double = if (result_Accum == current_Factor){
result_Accum
} else /*if (result_Accum != current_Factor)*/ {
//(result_Accum.abs / gcd(current_Factor, result_Accum)) * current_Factor.abs
(result_Accum / gcd(result_Accum, current_Factor)) * current_Factor
}
/*
} else if (result_Accum < current_Factor) {
val remainder: Double = current_Factor % result_Accum
if (remainder == 0) {
current_Factor.toDouble
} else {
//current_Factor * result_Accum
/*
scala> (4.0 / 2).max(6.0 / 2)
res51: Double = 3.0
*/
//result_Accum * (current_Factor / remainder).min(result_Accum / remainder)
result_Accum * gcd(current_Factor, remainder)
}
} else /*if (result_Accum > current_Factor)*/ {
val remainder: Double = result_Accum % current_Factor
if (remainder == 0) {
result_Accum
} else {
//current_Factor * result_Accum
//current_Factor * (current_Factor / remainder).min(result_Accum / remainder)
current_Factor * gcd(current_Factor, remainder)
}
}
*/
iterator(
seq.tail,
accum
)
}
}
/*
iterations:
s:{4,7,12,21,42}
r:[]
p:{2}
4:4 % 2 == 0 => 4/2 = 2 % 2 == 0 => same p, s - 4 + 2
7:7 % 2 != 0 => 7 % 2 != 0 => next p, s | s + 7
12:12 % 2 == 0 => 12 / 2 = 6 % 2 == 0 => same p, s - 12 + 6
21:21 % 2 != 0 => 21 % 2 != 0 => next p, s | s + 21
42:42 % 2 == 0 => 42 / 2 = 21 % 2 != 0 => next p, s - 42 + 21
-> round checked && not all == 1 && at least one elem % 2 == 0 | same p
s:{2,7,6,21,21} => {2,7,6,21}
r:[2]
p:{2}
2: % p == 0 && == p => 1 <- stop checking it s - 2
7: % p != 0 => 7, next p needed, s
6: % p == 0 && != p => 6 / p = 3 % p != 0, next p needed, s - 6 + 3
///> duplicates => ??? use memorization ??? <- set
21: % p != 0 => 21, next p needed, s
21: % p != 0 => 21, next p needed, s
-> p checked, not all == 1, next p
s:{7,3,21,21} => {7,3,21}
r:[2,2]
p:{3}
7: % p != 0 => 7, next p needed, s
3: % p == 0, == p => 1, <- stop checking it, s - 3
21: % p == 0, != p => 21 / p = 7, % p => next p, s - 21 + 7
-> p checked, not all == 1, next p
s:{7,7} => {7}
r:[2,2,3]
p:{5}
7: % p != 0 => 7, next p, s
-> p checked, not all == 1, next p
s:{7}
r:[2,2,3]
p:{7}
7: % p == 0, == p => 1, <- stop checking it, s - 7
-> p checked, all == 1, Done
s:{}
r:[2,2,3,7].product = 84
p:{}
----------------------------------------------------
s_S:{2, 3, 4}
r_P:{}
ps:[2,..]
r_P:2
r_A:[]
n_P:t
*/
@tailrec
def loop(
seq_State: Set[Int],
round_Progress: Set[Int] = Set.empty[Int],
primes: Stream[Int],
round_Prime: Int = 2,
///> lcm's factors
///> head is ? current | last prime factor ?
///> changed once per round, when round_Progress.isEmpty => 100%
result_Accum: List[Int] = List(1),
//last_Checked: Boolean = false,
///> if all per round next p => true else false
///> if at least one per round same p => false else true
is_Next_Prime: Boolean = false,//true
is_Same_Prime: Boolean = true,
is_Debug_Mode: Boolean = false
): Double = {
if (
seq_State.isEmpty ||
primes.isEmpty
) {
///> base case
result_Accum.product.toDouble
} else {
///> recursive step
// until all of the numbers have been reduced to 1.
if (is_Debug_Mode) {
println(
s"""seq_State:${seq_State}""" +
s""",round_Progress:${round_Progress}""" +
s""",primes:${primes}""" +
s""",round_Prime:${round_Prime}""" +
s""",result_Accum:${result_Accum}""" +
s""",is_Next_Prime:${is_Next_Prime}"""
)
}
val (prime, primes_Left, next_Round, elem, not_Same_Prime/*, accum*/): (
Int,
Stream[Int],
Set[Int],
Int,
Boolean/*,
List[Int]*/
) = if (
round_Progress.isEmpty
) {
///> starting new (check | round) for (current) (same | next) prime
if (is_Debug_Mode) {println(s"""next round start ...""")}
if (is_Next_Prime) {
(primes.head, primes.tail, seq_State.tail, seq_State.head, true)
} else {
(round_Prime, primes, seq_State.tail, seq_State.head, true)
}
} else /*if (round_Progress.nonEmpty)*/{
(round_Prime, primes, round_Progress.tail, round_Progress.head, is_Next_Prime)
}
val (next_State, next_Prime, accum): (Set[Int], Boolean, List[Int]) = if (elem % prime == 0) {
val next_Result: List[Int] = if (not_Same_Prime) {
///> first time per round % p == 0
prime +: result_Accum
} else {
result_Accum
}
if (elem == prime || elem == 1) {
///> discard elem
(seq_State - elem, not_Same_Prime, next_Result)
} else /*if (elem != prime)*/{
val next_Elem_Val = elem / prime
///> discard old elem
///> add new elem
/*
scala> Set(2,4,3,7) - 4 + 1
res0: scala.collection.immutable.Set[Int] = Set(2, 3, 7, 1)
*/
if (is_Debug_Mode) {
println(
s"""Same Prime check: ${next_Elem_Val} % ${prime} == 0 is: ${next_Elem_Val % prime == 0}""")}
(seq_State - elem + next_Elem_Val, (next_Elem_Val % prime != 0), next_Result)
}
} else /*if (elem % prime != 0)*/{
if (elem == 1) {
///> discard elem
(seq_State - elem, not_Same_Prime, result_Accum)
} else {
(seq_State, not_Same_Prime, result_Accum)
}
}
if (is_Debug_Mode) {
println(
s""">>next_State:${next_State}""" +
s""",next_Round:${next_Round}""" +
s""",primes_Left:${primes_Left}""" +
s""",prime:${prime}""" +
s""",accum:${accum}""" +
s""",next_Prime:${next_Prime}"""
)
}
loop(
///> reduced by elements equal to 1
seq_State = next_State,
round_Progress = next_Round,
primes = primes_Left,
round_Prime = prime,
result_Accum = accum,
is_Next_Prime = next_Prime,
is_Debug_Mode = is_Debug_Mode
)
}
}
///> initialization
//iterator(factors)
loop(
seq_State = factors.toSet,
//round_Progress = seq_State,
primes = primes_LT1000,
round_Prime = 1,//2
//result_Accum
is_Next_Prime = true,
is_Debug_Mode = is_Debug_Mode
)
}
//): Int
///>>>*** unit test ***<<<///
// Print the greatest common divisor of numbers in input of size N.
// For each test case it is guaranteed that
// solution will not exceed <= 2 * 10^18 <- very big number
val is_Debug_Mode: Boolean = (
//true
false
)
val factors_Stream_Size_N: Int = Try(
StdIn.readInt()
) match {
case Success(f) => f // assert( f >= 2 && f <= 10)
case Failure(e) => /*println(e.getMessage)*/0
}
val factors_Stream: Array[/*Big*/Int] = Try(
StdIn.readLine()
) match {
case Success(str) => {
str
.split(" ")
// assert(_ >= 1 && _ <= pow(10, 6))
/*
scala> scala.math.pow(10, 6)
res64: Double = 1000000.0
*/
.map(_.toInt)
//.map(BigInt(_))
}
case Failure(e) => {
//println(e.getMessage)
//"" // <- default
//false
Array.empty[Int]
//List("-1")
//Array(BigInt(1))
}
}
///> ??? WTF ???
/*
scala> s.fold(1)(f)
<console>:13: error: type mismatch;
found : ((Int, Int)) => Int
required: (Int, Int) => Int
s.fold(1)(f)
*/
def f(p: (Int, Int)): Int = p match { case (a, b) => BigInt(a).gcd(b).toInt }
/*
test case 3-9 Terminated due to timeout
so, BigInt may be ?
*/
def min_Common_Multiple(
numbers: Array[Int]
): Int = {
/*"""
:param numbers:
:return:
"""*/
// preprocessing
//var numb_Map: Map[Int, Int] = (
// for (n <- numbers) yield (n -> n)).toMap
/*
scala> var i = -1
i: Int = -1
scala> val a_M = for (n <- Array(1,2,3,5,7,11,13)) yield {i += 1;(i, n, BigInt(n))}
a_M: Array[(Int, Int, scala.math.BigInt)] = Array(
(0,1,1), (1,2,2), (2,3,3), (3,5,5), (4,7,7), (5,11,11), (6,13,13))
scala> for (el <- a_M) {val (i, k, v) = el; a_M(i) = (i, k, v + 1)}
scala> a_M
res14: Array[(Int, Int, scala.math.BigInt)] = Array(
(0,1,2), (1,2,3), (2,3,4), (3,5,6), (4,7,8), (5,11,12), (6,13,14))
*/
var i: Int = -1
var numb_ArrayMap: Array[(Int, Int, scala.math.BigInt)] = (
for (n <- numbers) yield {
i += 1
(i, n, BigInt(n))
}
)
//var while_Guard: Int = 1000000 <- less then test 3-9 iterations
//var max_So_Far: Int = 0
var max_So_Far: BigInt = BigInt(0)
var is_All_Equal: Boolean = false
var is_Not_All_Equal: Boolean = true
//condition = true
//var balance: Int = 0
//var div_Float = 1.0
//var div_Int = 1
while (
is_Not_All_Equal //&&
//while_Guard > 0
) {
//while_Guard -= 1
// new round
// reset
//balance = 0
is_Not_All_Equal = true
is_All_Equal = true//false
/*
scala> val m = Map(1->"a",2->"b",3->"c")
m: scala.collection.immutable.Map[Int,String] = Map(1 -> a, 2 -> b, 3 -> c)
scala> for ((k, v) <- m) yield k
res5: scala.collection.immutable.Iterable[Int] = List(1, 2, 3)
scala> for ((k, v) <- m) yield v
res6: scala.collection.immutable.Iterable[String] = List(a, b, c)
scala> val a_M = for (n <- Array(1,2,3,5,7,11,13)) yield (n, BigInt(n))
a_M: Array[(Int, scala.math.BigInt)] = Array(
(1,1), (2,2), (3,3), (5,5), (7,7), (11,11), (13,13))
scala> for (el <- a_M) {val (k, v) = el; el = (k, v + 1)}
<console>:12: error: reassignment to val
for (el <- a_M) {val (k, v) = el; el = (k, v + 1)}
scala> a_M.zipWithIndex
res10: Array[((Int, scala.math.BigInt), Int)] = Array(
((1,1),0), ((2,2),1), ((3,3),2), ((5,5),3), ((7,7),4), ((11,11),5), ((13,13),6))
scala> for (el <- a_M.zipWithIndex) {val ((k, v), i) = el; a_M(i) = (k, v + 1)}
scala> a_M
res12: Array[(Int, scala.math.BigInt)] = Array(
(1,2), (2,3), (3,4), (5,6), (7,8), (11,12), (13,14))
*/
// mutation inside iterator ? <- OK
//for ((k, v) <- numb_Map) {
for (el <- numb_ArrayMap) {
val (i, k, v) = el//; a_M(i) = (i, k, v + 1)
if (v > max_So_Far) {
max_So_Far = v
//balance = -1
//is_Not_All_Equal = false//true
is_All_Equal = false
} else if (v == max_So_Far) {
// skip | pass
} else /*if (v < max_So_Far)*/ {
//balance = -1
//is_Not_All_Equal = false
is_All_Equal = false
if (max_So_Far % k == 0) {
// update
//numb_Map = numb_Map + (k -> max_So_Far)
} else /*if (max_So_Far % k != 0)*/ {
// update
max_So_Far = (max_So_Far / k + 1) * k
//numb_Map = numb_Map + (k -> max_So_Far)
}
//numb_Map = numb_Map + (k -> max_So_Far)
numb_ArrayMap(i) = (i, k, max_So_Far)
}
}
// post check
// if unchanged
if (
//is_Not_All_Equal
is_All_Equal //||
//balance == 0
) {
is_Not_All_Equal = false
} else {
is_Not_All_Equal = true
}
}
//println("""while_Guard: ${}""".format(while_Guard))
//return
max_So_Far
.toInt
}
//val result: Int = {
val result: String = {
/*
scala> BigInt(3).gcd(5)
res5: scala.math.BigInt = 1
scala> BigInt(3).gcd(5).toInt
res6: Int = 1
scala> val s = Array(1, 2, 3, 4, 5)
s: Array[Int] = Array(1, 2, 3, 4, 5)
scala> s.fold(0)(BigInt(_).gcd(_).toInt)
res7: Int = 1
scala> s.reduce(BigInt(_).gcd(_).toInt)
res8: Int = 1
scala> s.reduceRight(BigInt(_).gcd(_).toInt)
res9: Int = 1
scala> s.fold(0)({case (a: Int,b: Int) => BigInt(a).gcd(b).toInt})
res18: Int = 1
scala> s.fold[Int](1)({case (a: Int,b: Int) => BigInt(a).gcd(b).toInt})
res19: Int = 1
scala> s.fold(1)((x: Int, y: Int) => f((x, y)))
res32: Int = 1
scala> s.fold(1)((a: Int, b: Int) => BigInt(a).gcd(b).toInt)
res34: Int = 1
scala> s.fold(1){case p => BigInt(p._1).gcd(p._2).toInt}
res36: Int = 1
*/
/*
factors_Stream
.fold[Int](1)//(_ + _)
// error: missing parameter type for expanded function ((x$2, x$3) => BigInt(x$2).gcd(x$3).toInt)
//(BigInt(_).gcd(_).toInt)
{ case (a: Int, b: Int) => BigInt(a).gcd(b).toInt}
*/
//484 CPU time limit exceeded (core dumped) "$@"
//find_Least_Common_Multiple(
///> alas, but fail
//least_Common_Multiple(
///> return (6) for {1, 3}
//sequence_Min_Common_Miltiple(
min_Common_Multiple(
factors_Stream//,
//is_Debug_Mode = false
)
// assert(
// result <=
// scala> 2 * scala.math.pow(10, 18)
// res44: Double = 2.0E18
//)
//.toInt
.toString
.takeWhile(_ != '.')
}
//assert(9875 == 2)
//println(s"""${result.mkString(" ")}""")
println(s"""${result}""")
if (is_Debug_Mode){
var test_result = direct_Trial_Divisions_Primes_Search()
var expected = 168
/*
scala> (1 to 100 by 1).take(20)
res10: scala.collection.immutable.Range = Range(
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
*/
assert( test_result.size == expected,
s"""test_result.size: ${test_result.size}, \ntest_result.take(20): ${test_result.take(20)}""")
println(
s"""test_result.size: ${result.size} == expected: ${expected}, \ntest_result.take(20): ${test_result.take(20)}""")
}
if (is_Debug_Mode){
var test_result = prime_Factorization(12)
var expected = Map(2 -> 2, 3 -> 1)
/*
*/
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
var test_result = find_Pair_Min_Common_Int(4, 6)
var expected = 12
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
var test_result = min_Common_Mult_4_Pair(4, 6)
var expected = 12
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
//var test_result = sequence_Min_Common_Miltiple(List(4,7,12,21,42))
var test_result = sequence_Min_Common_Miltiple(Array(4,7,12,21,42))
var expected = 84
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
if (is_Debug_Mode){
//var test_result = sequence_Min_Common_Miltiple(List(4,7,12,21,42))
var test_result = min_Common_Multiple(Array(4,7,12,21,42))
var expected = 84
assert( test_result == expected,
s"""test_result: ${test_result} != expected: ${expected}""")
println(
s"""test_result: ${test_result} == expected: ${expected}""")
}
}
Display the source blob
Display the rendered blob
Raw
Least_common_multiple.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"collapsed": true
},
"outputs": [
{
"data": {
"text/plain": [
"(2.6457513110645907, 2.6457513110645907, 2, 2, 2, 1, 2, 3)"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import math\n",
"\n",
"#abs()\n",
"#math.fabs(x)\n",
"#math.floor(x)\n",
"#math.sqrt(x)\n",
"#**\n",
"#math.pow(x, y)\n",
"7 ** 0.5, math.sqrt(7), math.floor(7 ** 0.5), math.floor(math.sqrt(7)), int(7 ** 0.5), int(3 ** 0.5), int(4 ** 0.5), 3 ** 1"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(2.3333333333333335, True)"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\"\"\" test limit \"\"\"\n",
"7 / (math.floor(math.sqrt(7)) + 1), 7 / (math.floor(math.sqrt(7)) + 1) < math.sqrt(7)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"next(iter(range(3, 10, 1)))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(3, 4, 5, 6, 7, 8, 9, 'Done')"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"it = iter(range(3, 10, 1))\n",
"next(it, \"Done\"),next(it, \"Done\"),next(it, \"Done\"),next(it, \"Done\"),next(it, \"Done\"),next(it, \"Done\"),next(it, \"Done\"),next(it, \"Done\")"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def direct_Trial_Divisions_Primes_Search(up_To: int = 1000):\n",
" \"\"\"\n",
" \n",
" :param up_To: \n",
" :return: \n",
" \"\"\"\n",
" # must be sorted in ascending order\n",
" primes_List = [2]\n",
" test_limit = None\n",
" condition = True\n",
" \n",
" for candidate in range(3, up_To, 1):\n",
" pass\n",
" # int(3 ** 0.5) == 1\n",
" # int(4 ** 0.5) == 2\n",
" test_limit = int(candidate ** 0.5)\n",
" condition = True\n",
" if False:\n",
" # work as expected\n",
" # not-filtered | restricted by previously found primes\n",
" for trail_Val in range(2, test_limit + 1, 1):\n",
" pass\n",
" if candidate % trail_Val == 0:\n",
" pass\n",
" condition = False\n",
" \n",
" break\n",
" \n",
" if True:\n",
" # work as expected\n",
" # filtered | restricted by previously found primes\n",
" for prime in primes_List:\n",
" pass\n",
" if prime >= (test_limit + 1):\n",
" \n",
" break\n",
"\n",
" if candidate % prime == 0:\n",
" pass\n",
" condition = False\n",
" \n",
" break\n",
" \n",
" if condition:\n",
" pass\n",
" primes_List.append(candidate)\n",
" \n",
" \n",
" return primes_List#None"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"\"\"\"\n",
"from functools import reduce\n",
"\n",
"# Primes < 1000\n",
"print(list(filter(None,map(lambda y:y*reduce(lambda x,y:x*y!=0,\n",
"map(lambda x,y=y:y%x,range(2,int(pow(y,0.5)+1))),1),range(2,1000)))))\n",
"\"\"\"\n",
"None"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"len(result): 168 == 168, result[:20]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]\n"
]
}
],
"source": [
"### unit test ###\n",
"result = direct_Trial_Divisions_Primes_Search()\n",
"expected = 168\n",
"# import unittest\n",
"# assertEqual(a, b)\n",
"assert len(result) == expected, \"\"\"len(result): {}, result[:20]: {}\"\"\".format(len(result), result[:20])\n",
"print(\"\"\"len(result): {} == {}, result[:20]: {}\"\"\".format(len(result), expected, result[:20]))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def prime_Factorization(\n",
" number: int,\n",
" # mutable -> once changed affect next call result\n",
" prime_Factors_Map: dict = dict(),\n",
" is_Debug_Mode: bool = False\n",
" ) -> dict:\n",
" \"\"\"\n",
" \n",
" :param number: \n",
" :param prime_Factors_Map: \n",
" :param is_Debug_Mode: \n",
" :return: \n",
" \"\"\"\n",
" primes_List = direct_Trial_Divisions_Primes_Search(number + 1)\n",
" condition = True\n",
" \n",
" if number in primes_List:\n",
" prime_Factors_Map[number] = 1\n",
" else:\n",
" pass\n",
" for prime in primes_List:\n",
" pass\n",
" condition = True\n",
" \n",
" while number > 1 and condition:\n",
" if number % prime == 0:\n",
" #get_Prime = prime_Factors_Map.get(prime, None)\n",
" #if get_Prime:\n",
" # works as expected\n",
" # but how pick max prime power from previous calls \n",
" if prime in prime_Factors_Map:\n",
" prime_Factors_Map[prime] += 1\n",
" else: \n",
" prime_Factors_Map[prime] = 1 \n",
" \n",
" number = number / prime \n",
" else:\n",
" condition = False\n",
" \n",
" \n",
" return prime_Factors_Map"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{2: 2, 3: 1}"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"### unit test ###\n",
"prime_Factorization(12, dict())"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"\"\"\"\n",
"from: `https://en.wikipedia.org/wiki/Least_common_multiple`\n",
"Example\n",
"What is the LCM of 4 and 6?\n",
"Multiples of 4 are:\n",
"Stream(n, n + n, n + n + n, ...)\n",
"Stream(n * 1, n * 2, n * 3, ...)\n",
"ni = n + nj, j = i - 1, i > 0\n",
"4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...\n",
"and the multiples of 6 are:\n",
"6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...\n",
"Common multiples of 4 and 6 are \n",
"simply the numbers that are in both lists:\n",
"12, 24, 36, 48, 60, 72, ....\n",
"So, \n",
"from this list of \n",
"the first few common multiples \n",
"of the numbers 4 and 6, \n",
"their least common multiple is 12.\n",
"\"\"\"\n",
"def find_Least_Common_Multiple(\n",
" factors: list,\n",
" is_Debug_Mode: bool = False\n",
" ) -> int:\n",
" max_Prime_Powers_Map = dict()\n",
" number_Factors_Map = dict()\n",
" get_Prime = None\n",
" lcm = 1\n",
" \n",
" for number in factors:\n",
" pass\n",
" number_Factors_Map = prime_Factorization(number, dict())\n",
" if max_Prime_Powers_Map == dict() or len(max_Prime_Powers_Map) == 0:\n",
" max_Prime_Powers_Map = number_Factors_Map\n",
" else:\n",
" for (k, v) in number_Factors_Map.items():\n",
" pass\n",
" get_Prime = max_Prime_Powers_Map.get(k, None)\n",
" if get_Prime:\n",
" if get_Prime < v:\n",
" max_Prime_Powers_Map[k] = v\n",
" else:\n",
" max_Prime_Powers_Map[k] = v\n",
" \n",
" for (k, v) in max_Prime_Powers_Map.items():\n",
" lcm = lcm * (k ** v)\n",
" \n",
" #return (max_Prime_Powers_Map, lcm)\n",
" #return max_Prime_Powers_Map\n",
" return lcm"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: 84 == expected: 84\n"
]
}
],
"source": [
"### unit test ###\n",
"test_List = [4,7,12,21,42] \n",
"test_Set = set(test_List)\n",
"result = find_Least_Common_Multiple(test_Set)\n",
"expected = 84\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"### unit test ###\n",
"direct_Trial_Divisions_Primes_Search()"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'one' in {'one': 1, 'two': 2, 'three': 3}"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(True, False, True)"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"dict() == {}, dict() == {1: 1}, {} == {}"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('two', 2), ('one', 1), ('three', 3)]"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[(k, v) for (k, v) in {'one': 1, 'two': 2, 'three': 3}.items()]"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sum({'one': 1, 'two': 2, 'three': 3}.values())"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"def multiple(step: int, state: int = 0) -> int:\n",
" while True:\n",
" state += step\n",
" \n",
" yield state"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(4, 8, 12, generator, function)"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"### unit test ###\n",
"n = 4\n",
"gen_4 = multiple(n)\n",
"next(gen_4, \"Empty\") , next(gen_4, \"Empty\"), next(gen_4, \"Empty\"), type(gen_4), type(find_Least_Common_Multiple)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [],
"source": [
"def find_Min_Common_Int(\n",
" stream_1,\n",
" stream_2\n",
") -> int:\n",
" while_Guard = 100000\n",
" \n",
" val_1 = next(stream_1, None)\n",
" val_2 = next(stream_2, None)\n",
" if val_1 == val_2:\n",
" return val_1\n",
" else:\n",
" while val_1 != val_2 and while_Guard > 0:\n",
" while_Guard -= 1\n",
" \n",
" if val_1 > val_2:\n",
" pass\n",
" val_2 = next(stream_2, None)\n",
" \n",
" else:#elif val_1 < val_2:\n",
" pass\n",
" val_1 = next(stream_1, None)\n",
" \n",
" \n",
" #return (val_1, val_2)#None\n",
" return val_1"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: 21 == expected: 21\n"
]
}
],
"source": [
"### unit test ###\n",
"test_Gen_4 = multiple(4)\n",
"test_Gen_6 = multiple(12)\n",
"result = find_Min_Common_Int(test_Gen_4, test_Gen_6)\n",
"expected = (12, 12)\n",
"test_Gen_7 = multiple(7)\n",
"test_Gen_3 = multiple(3)\n",
"result = find_Min_Common_Int(test_Gen_7, test_Gen_3)\n",
"expected = 21#(21, 21)\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"([[4, 7], [7, 12], [12, 21], [21, 42]], [[4, 7], [7, 12], [12, 21], [21, 42]])"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"### unit test ###\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"expected = 84\n",
"([test_List[el:(el + 2)] for el in range(0, len(test_List) - 1, 1)], \n",
"[test_List[indx:(indx + 2)] for (indx, el) in enumerate(test_List) if indx < len(test_List) - 1])"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"84"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pairs = [test_List[el:(el + 2)] for el in range(0, len(test_List) - 1, 1)]\n",
"lcd = None\n",
"\n",
"for (n1, n2) in pairs:\n",
" if lcd:\n",
" pass\n",
" lcd = find_Min_Common_Int(multiple(lcd), multiple(n2))\n",
" else:\n",
" pass\n",
" lcd = find_Min_Common_Int(multiple(n1), multiple(n2))\n",
" \n",
"lcd"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"def min_Common_Multiple(\n",
" numbers: list\n",
") -> int:\n",
" \"\"\"\n",
" \n",
" :param numbers: \n",
" :return: \n",
" \"\"\"\n",
" # preprocessing\n",
" numb_Map = {n: n for n in numbers}#dict()\n",
" if False:\n",
" for n in numbers:\n",
" numb_Map[n] = n\n",
" \n",
" while_Guard = 100000\n",
" max_So_Far = 0\n",
" #is_All_Equal = 0\n",
" is_Not_All_Equal = True\n",
" #condition = True\n",
" balance = 0\n",
" div_Float = 1.0\n",
" div_Int = 1\n",
" \n",
" while is_Not_All_Equal and while_Guard > 0:\n",
" while_Guard -= 1\n",
" # round\n",
" # reset\n",
" is_Not_All_Equal = True\n",
" balance = 0\n",
" # mutation inside iterator ?\n",
" for (k, v) in numb_Map.items():#.values():\n",
" pass\n",
" if v > max_So_Far:\n",
" max_So_Far = v\n",
" balance = -1\n",
" elif v == max_So_Far:\n",
" pass\n",
" else:#elif v < max_So_Far:\n",
" pass\n",
" balance = -1\n",
" div_Float = max_So_Far / k\n",
" div_Int = max_So_Far // k\n",
" if div_Float == div_Int:\n",
" # update\n",
" #numb_Map[k] = div_Int * k\n",
" numb_Map[k] = max_So_Far\n",
" else:#if div_Float > div_Int:\n",
" # update\n",
" max_So_Far = (div_Int + 1) * k\n",
" numb_Map[k] = max_So_Far\n",
" \n",
" # post check\n",
" if balance == 0:\n",
" is_Not_All_Equal = False\n",
" else:\n",
" is_Not_All_Equal = True\n",
" \n",
" print(\"\"\"while_Guard: {}\"\"\".format(while_Guard))\n",
" #return numb_Map#None\n",
" return max_So_Far"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"while_Guard: 99996\nresult: 84 == expected: 84\n"
]
}
],
"source": [
"### unit test ###\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"test_Set = set(test_List)\n",
"result = min_Common_Multiple(test_Set)\n",
"expected = 84\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1.75, 1, float, int)"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"7 / 4, 7 // 4, type(7 / 4), type(7 // 4)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('abc', True, False, False)"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\"AbC\".lower(), \"AbC\".isalpha(), \" \".isalpha(), \"7\".isalpha()"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(26,\n {'a',\n 'b',\n 'c',\n 'd',\n 'e',\n 'f',\n 'g',\n 'h',\n 'i',\n 'j',\n 'k',\n 'l',\n 'm',\n 'n',\n 'o',\n 'p',\n 'q',\n 'r',\n 's',\n 't',\n 'u',\n 'v',\n 'w',\n 'x',\n 'y',\n 'z'})"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"pangram = \"The quick brown fox jumps over the lazy dog\"\n",
"pangram_Set = set(pangram.lower())\n",
"pangram_Set.discard(\" \")\n",
"\n",
"len(pangram_Set), pangram_Set"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('a', 97, 'z', 122)"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"chr(97), ord('a'), chr(122), ord('z')"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['a',\n 'b',\n 'c',\n 'd',\n 'e',\n 'f',\n 'g',\n 'h',\n 'i',\n 'j',\n 'k',\n 'l',\n 'm',\n 'n',\n 'o',\n 'p',\n 'q',\n 'r',\n 's',\n 't',\n 'u',\n 'v',\n 'w',\n 'x',\n 'y',\n 'z']"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[chr(code_Point) for code_Point in range(ord(\"a\"), ord(\"z\") + 1, 1)]"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['T',\n 'h',\n 'e',\n 'o',\n 'p',\n 't',\n 'i',\n 'o',\n 'n',\n 'a',\n 'l',\n 's',\n 'i',\n 'g',\n 'n',\n 'm',\n 'a',\n 'y',\n 'b',\n 'e',\n 'o',\n 'r',\n 'a',\n 's',\n 'i',\n 'g',\n 'n',\n 'h',\n 'a',\n 's',\n 'n',\n 'o',\n 'e',\n 'f',\n 'f',\n 'e',\n 'c',\n 't',\n 'o',\n 'n',\n 't',\n 'h',\n 'e',\n 'v',\n 'a',\n 'l',\n 'u',\n 'e',\n 'p',\n 'r',\n 'o',\n 'd',\n 'u',\n 'c',\n 'e',\n 'd']"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test_Str = \"The optional sign may be '+' or '-'; a '+' sign has no effect on the value produced.\"\n",
"\"\"\"\n",
"Note that filter(function, iterable) is equivalent to \n",
"the generator expression (item for item in iterable if function(item))\n",
"\"\"\"\n",
"list(filter(lambda x: x.isalpha(), test_Str))"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'T',\n 'a',\n 'b',\n 'c',\n 'd',\n 'e',\n 'f',\n 'g',\n 'h',\n 'i',\n 'l',\n 'm',\n 'n',\n 'o',\n 'p',\n 'r',\n 's',\n 't',\n 'u',\n 'v',\n 'y'}"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result_Set = {a for a in test_Str if a.isalpha()}\n",
"result_Set"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(2, 147)"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(1071 // 462, 1071 - 2 * 462)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"\"\"\"\n",
"Example:\n",
" the greatest common divisor of 1071 and 462\n",
" |Step k\t| Equation |\tQuotient and remainder |\n",
" |0\t |1071 = q0 * 462 + r0\t|q0 = 2 and r0 = 147 | 2 = 1071 // 462, 147 = 1071 - 2 * 462\n",
" |1\t |462 = q1 * 147 + r1 |q1 = 3 and r1 = 21 |\n",
" |2\t |147 = q2 * 21 + r2 |q2 = 7 and r2 = 0 <- ends with 21 |\n",
"\"\"\"\n",
"def gcd_By_Mod(\n",
" a: int, \n",
" b: int\n",
") -> int:\n",
" \"\"\"\n",
" # qk - quotient\n",
" # rk - remainder of rk−1 and rk−2\n",
" # abs(rk) < abs(rk-1)\n",
" # rk = rk−2 mod rk−1\n",
" # a = q0 * b + r0\n",
" # b = q1 * r0 + r1\n",
" # r0 = q2 * r1 + r2\n",
" # r1 = q3 * r2 + r3\n",
" # ...\n",
" # rk−2 = qk * rk−1 + rk\n",
" # ...\n",
" # until rk == 0\n",
" # if a < b, \n",
" # the initial quotient q0 equals zero, and \n",
" # the remainder r0 is a. \n",
" # Thus, \n",
" # rk is smaller than its predecessor rk−1 for all k ≥ 0.\n",
"I \n",
" :param a: \n",
" :param b: \n",
" :return: \n",
" \"\"\"\n",
" #t = None\n",
" \n",
" while b != 0:\n",
" #t = b \n",
" #b = a % b \n",
" #a = t \n",
" (a, b) = (b, a % b)\n",
" \n",
" \n",
" return a"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: [1, 1, 3, 21] == expected: [1, 1, 3, 21]\n"
]
}
],
"source": [
"### unit test ###\n",
"import math\n",
"\n",
"\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"#test_Set = set(test_List)\n",
"result = [gcd_By_Mod(v, test_List[i + 1]) for (i, v) in enumerate(test_List) if i < len(test_List) - 1]\n",
"expected = [math.gcd(test_List[i], test_List[i + 1]) for i in range(0, len(test_List) - 1, 1)]\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"def gcd_By_Subtraction(\n",
" a: int, \n",
" b: int\n",
") -> int:\n",
" \"\"\"\n",
" for non-negative arguments\n",
" :param a: \n",
" :param b: \n",
" :return: \n",
" \"\"\"\n",
" assert a >= 0 and b >= 0\n",
" \n",
" while a != b:\n",
" if a > b:\n",
" a = a - b \n",
" else:\n",
" b -= a \n",
" \n",
" return a"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: [1, 1, 3, 21] == expected: [1, 1, 3, 21]\n"
]
}
],
"source": [
"### unit test ###\n",
"import math\n",
"\n",
"\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"#test_Set = set(test_List)\n",
"result = [gcd_By_Subtraction(v, test_List[i + 1]) for (i, v) in enumerate(test_List) if i < len(test_List) - 1]\n",
"expected = [math.gcd(test_List[i], test_List[i + 1]) for i in range(0, len(test_List) - 1, 1)]\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"# @tailrec\n",
"def recursive_GCD_By_Mod(\n",
" a: int, \n",
" b: int\n",
") -> int:\n",
" if b == 0:\n",
" # base case\n",
" return a\n",
" else:\n",
" # recursive step\n",
" return recursive_GCD_By_Mod(b, a % b)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: [1, 1, 3, 21] == expected: [1, 1, 3, 21]\n"
]
}
],
"source": [
"### unit test ###\n",
"import math\n",
"\n",
"\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"#test_Set = set(test_List)\n",
"result = [recursive_GCD_By_Mod(v, test_List[i + 1]) for (i, v) in enumerate(test_List) if i < len(test_List) - 1]\n",
"expected = [math.gcd(test_List[i], test_List[i + 1]) for i in range(0, len(test_List) - 1, 1)]\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(-315, -1.4666666666666666, 168, 21, 8.0, 147)"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\"\"\"\n",
"if rk−1 > 0:\n",
" rk−2 = (qk + 1) * rk−1 + ek\n",
" ek = rk-2 / ((qk + 1) * rk−1)\n",
"else:#if rk−1 < 0:\n",
" rk−2 = (qk − 1) * rk−1 + ek\n",
" ek = rk-2 / ((qk - 1) * rk−1)\n",
" \n",
"gcd(1071, 462) <- no more then 3 iteration step expected\n",
"1071 = 2 * 462 + 147 \n",
" rk-2 qk rk-1 ek \n",
"0: 1071 = (2 + 1) * 462 + (-315)\n",
" -315 < 0 => \n",
"1: 462 = ((-1) - 1) * (-315) + 168\n",
" 168 > 0 => \n",
"2: -315 = (1 + 1) * 168 + 21\n",
" 21 > 0 => \n",
"3: 168 = (8 + 1) * 21 + (-21) <- abs(e2) == abs(e3) and r1 % r2 == 0 <- stop condition ?\n",
" endless circle ?\n",
" -21 < 0 => \n",
"4: 21 = ((-1) - 1) * (-21) + 21\n",
"\n",
"-> something wrong here,\n",
"it does not look like it converges faster \n",
"like |rk| ≤ |rk−1| / 2\n",
"at each step.\n",
"\"\"\"\n",
"((1071 - (2 + 1) * 462), 462 / -315, -2 * -315 - 462, -315 + 2 * 168, 168 / 21, 462 - 315)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [],
"source": [
"# The binary GCD algorithm, also known as Stein's algorithm\n",
"def binary_GCD_Recursive(\n",
" a: int, \n",
" b: int\n",
") -> int:\n",
" \"\"\"\n",
" for non-negative arguments\n",
" :param a: \n",
" :param b: \n",
" :return: \n",
" \"\"\"\n",
" assert a >= 0 and b >= 0\n",
" \n",
" if (a == b):\n",
" # basic case\n",
" return a\n",
"\n",
" if (a == 0):\n",
" # basic case\n",
" return b\n",
"\n",
" if (b == 0):\n",
" # basic case\n",
" return a\n",
"\n",
" # look for factors of 2\n",
" if (~a & 1): # a % 2 == 0:\n",
" # a is even\n",
" if (b & 1): # b is odd\n",
" return binary_GCD_Recursive(a >> 1, b)\n",
" else: # both a and b are even\n",
" return binary_GCD_Recursive(a >> 1, b >> 1) << 1\n",
"\n",
" if (~b & 1): \n",
" # a is odd, b is even\n",
" return binary_GCD_Recursive(a, b >> 1)\n",
"\n",
" # reduce larger argument\n",
" if (a > b):\n",
" return binary_GCD_Recursive((a - b) >> 1, b)\n",
"\n",
"\n",
" return binary_GCD_Recursive((b - a) >> 1, a)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: [1, 1, 3, 21] == expected: [1, 1, 3, 21]\n"
]
}
],
"source": [
"### unit test ###\n",
"import math\n",
"\n",
"\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"#test_Set = set(test_List)\n",
"result = [binary_GCD_Recursive(v, test_List[i + 1]) for (i, v) in enumerate(test_List) if i < len(test_List) - 1]\n",
"expected = [math.gcd(test_List[i], test_List[i + 1]) for i in range(0, len(test_List) - 1, 1)]\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def binary_GCD_Iterative(\n",
" a: int, \n",
" b: int\n",
") -> int:\n",
" \"\"\"\n",
" for non-negative arguments\n",
" :param a: \n",
" :param b: \n",
" :return: \n",
" \"\"\"\n",
" assert a >= 0 and b >= 0\n",
" \n",
" # :int\n",
" shift = None\n",
"\n",
" # GCD(0,b) == b; GCD(a,0) == a, GCD(0,0) == 0 \n",
" if (a == 0): \n",
" return b\n",
" if (b == 0): \n",
" return a\n",
" \n",
" # Let shift := lg K, \n",
" # where K is the greatest power of 2\n",
" # dividing both a and b.\n",
" shift = 0\n",
" while ((a | b) & 1) == 0:\n",
" a >>= 1\n",
" b >>= 1\n",
" shift += 1\n",
" \n",
" while ((a & 1) == 0):\n",
" a >>= 1\n",
" \n",
" # From here on, a is always odd. \n",
" while (b != 0):# post condition\n",
" # remove all factors of 2 in b -- they are not common \n",
" # note: b is not zero, \n",
" # so while will terminate \n",
" while ((b & 1) == 0): # Loop X \n",
" b >>= 1\n",
"\n",
" # Now a and b are both odd. \n",
" # Swap if necessary so a <= b,\n",
" # then \n",
" # set b = b - a (which is even). \n",
" # For bignums, \n",
" # the swapping is just pointer movement, and \n",
" # the subtraction can be done in-place. \n",
" if (a > b):\n",
" # Swap a and b.\n",
" # : int \n",
" #t = b\n",
" #b = a\n",
" #a = t\n",
" (b, a) = (a, b)\n",
" \n",
" # Here b >= a.\n",
" b = b - a \n",
" \n",
" \n",
" # restore common factors of 2 \n",
" return a << shift"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: [1, 1, 3, 21] == expected: [1, 1, 3, 21]\n"
]
}
],
"source": [
"### unit test ###\n",
"import math\n",
"\n",
"\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"#test_Set = set(test_List)\n",
"result = [binary_GCD_Iterative(v, test_List[i + 1]) for (i, v) in enumerate(test_List) if i < len(test_List) - 1]\n",
"expected = [math.gcd(test_List[i], test_List[i + 1]) for i in range(0, len(test_List) - 1, 1)]\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [],
"source": [
"def merge(\n",
" numb_A: int,\n",
" numb_B: int\n",
" ) -> int: \n",
" assert type(numb_A) is int\n",
" assert type(numb_B) is int\n",
" # preprocessing\n",
" max_So_Far = 0\n",
" is_All_Equal = False\n",
" is_Not_All_Equal = True\n",
" state_A = numb_A \n",
" state_B = numb_B \n",
" while_Guard = 1000\n",
" \n",
" def play_Round(\n",
" increment: int, \n",
" state: int,\n",
" round_Max: int\n",
" ) -> (int, int):\n",
" \"\"\"\n",
" mutate passed arguments\n",
" :param increment: \n",
" :param state: \n",
" :param max_So_Far: \n",
" :return: \n",
" \"\"\"\n",
" if (state > round_Max) :\n",
" round_Max = state\n",
" #is_All_Equal = false \n",
" return (state, round_Max)\n",
" elif (state == round_Max):\n",
" pass\n",
" return (state, round_Max)\n",
" else: #if (state < max_So_Far):\n",
" #is_All_Equal = false \n",
" \n",
" if (round_Max % increment == 0) :\n",
" # update\n",
" state = round_Max\n",
" return (state, round_Max)\n",
" else: #if (max_So_Far % k != 0):\n",
" # update\n",
" round_Max = (round_Max // increment + 1) * increment\n",
" state = round_Max \n",
" return (state, round_Max)\n",
" \n",
" \n",
" while (\n",
" is_Not_All_Equal and\n",
" while_Guard > 0\n",
" ) :\n",
" while_Guard -= 1\n",
" \n",
" # new round\n",
" # reset\n",
" is_Not_All_Equal = True\n",
" is_All_Equal = True\n",
" \n",
" (state_A, max_So_Far) = play_Round(\n",
" increment = numb_A, \n",
" state = state_A,\n",
" round_Max = max_So_Far\n",
" )\n",
" assert type(state_A) is int\n",
" assert type(max_So_Far) is int\n",
" (state_B, max_So_Far) = play_Round(\n",
" increment = numb_B, \n",
" state = state_B,\n",
" round_Max = max_So_Far\n",
" )\n",
" assert type(state_B) is int\n",
" assert type(max_So_Far) is int\n",
" # post check\n",
" # if unchanged\n",
" if (\n",
" #is_All_Equal\n",
" state_A == state_B\n",
" ):\n",
" # break\n",
" is_Not_All_Equal = False\n",
" else:\n",
" # continue\n",
" is_Not_All_Equal =True\n",
"\n",
" #print(\"\"\"state_A: {}, state_B: {}\"\"\".format(state_A, state_B))\n",
" #print(\"\"\"while_Guard: {}\"\"\".format(while_Guard))\n",
" return max_So_Far"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"state_A: 12, state_B: 12\nwhile_Guard: 997\nresult: 12 == expected: 12\n"
]
}
],
"source": [
"### unit test ###\n",
"import math\n",
"\n",
"\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"#test_Set = set(test_List)\n",
"result = merge(4, 6)\n",
"expected = 12\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [],
"source": [
"def conquer(\n",
" numb_A: int,\n",
" numb_B: int\n",
" ) -> int: \n",
" assert type(numb_A) is int\n",
" assert type(numb_B) is int\n",
" \n",
" def play_Turn(\n",
" increment: int, \n",
" state: int,\n",
" round_Max: int\n",
" ) -> (int, int):\n",
" \"\"\"\n",
" mutate passed arguments\n",
" :param increment: \n",
" :param state: \n",
" :param max_So_Far: \n",
" :return: \n",
" \"\"\"\n",
" if (state > round_Max) :\n",
" round_Max = state\n",
" #is_All_Equal = false \n",
" return (state, round_Max)\n",
" elif (state == round_Max):\n",
" pass\n",
" return (state, round_Max)\n",
" else: #if (state < max_So_Far):\n",
" #is_All_Equal = false \n",
" \n",
" if (round_Max % increment == 0) :\n",
" # update\n",
" state = round_Max\n",
" return (state, round_Max)\n",
" else: #if (max_So_Far % k != 0):\n",
" # update\n",
" round_Max = (round_Max // increment + 1) * increment\n",
" state = round_Max \n",
" return (state, round_Max)\n",
" \n",
" \n",
" #def while_Loop(\n",
" #def play_Round(\n",
" #@tailrec\n",
" def play_Game(\n",
" inc_A: int,\n",
" inc_B: int, \n",
" a_State: int,\n",
" b_State: int,\n",
" #game_Max\n",
" result_Accum: int,\n",
" game_Guard: int = 1000# > 0\n",
" ) -> int:\n",
" # new round\n",
" if (\n",
" a_State == b_State or game_Guard == 0\n",
" ):\n",
" # base case\n",
" # Done\n",
" return result_Accum\n",
" else:\n",
" # recursive step\n",
" # continue\n",
" # reset\n",
" (next_A_State, turn_1_Max) = play_Turn(\n",
" increment = inc_A, \n",
" state = a_State,\n",
" round_Max = result_Accum\n",
" )\n",
" (next_B_State, turn_2_Max) = play_Turn(\n",
" increment = inc_B, \n",
" state = b_State,\n",
" round_Max = turn_1_Max\n",
" )\n",
" \n",
" \n",
" return play_Game(\n",
" inc_A = inc_A,\n",
" inc_B = inc_B, \n",
" a_State = next_A_State,\n",
" b_State = next_B_State,\n",
" result_Accum = turn_2_Max,\n",
" game_Guard = game_Guard - 1\n",
" )\n",
" \n",
"\n",
" #print(\"\"\"state_A: {}, state_B: {}\"\"\".format(state_A, state_B))\n",
" #print(\"\"\"while_Guard: {}\"\"\".format(while_Guard))\n",
" ###>>>*** initialize\n",
" return play_Game(\n",
" inc_A = numb_A,\n",
" inc_B = numb_B, \n",
" a_State = numb_A,\n",
" b_State = numb_B,\n",
" result_Accum = 0,\n",
" game_Guard = 1000\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [],
"source": [
"def divide(\n",
" numbers: list# of int\n",
" ) -> int:\n",
" if (numbers == [] or len(numbers) == 0) :\n",
" # non-expected base case\n",
" return 1\n",
" elif (len(numbers) == 1) :\n",
" # base case\n",
" return numbers[0]\n",
" #elif (len(numbers) == 2) :\n",
" # special base case\n",
" #merge(numbers[0], numbers[1])\n",
" else :\n",
" # recursive step\n",
" # general base case\n",
" n_Len = len(numbers)\n",
" # starting from zero index\n",
" part_1 = numbers[:n_Len // 2]\n",
" part_2 = numbers[n_Len // 2:] \n",
" #int_A = divide(part_1)\n",
" #int_B = divide(part_2)\n",
" #assert type(int_A) is int\n",
" #assert type(int_B) is int\n",
" \n",
" ###>>>*** work as expected\n",
" #return merge(divide(part_1), divide(part_2))\n",
" #return merge(int_A, int_B)\n",
" \n",
" return conquer(divide(part_1), divide(part_2))"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(2, 1, [4, 7], [12, 21, 42], [4], [7], False, True)"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(5 // 2, 2 // 2, [4,7,12,21,42][:5 // 2], [4,7,12,21,42][5 // 2:], [4,7][:2 // 2], [4,7][2 // 2:], 5 is int, type(5) is int )"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"result: 84 == expected: 84\n"
]
}
],
"source": [
"### unit test ###\n",
"test_List = [4,7,12,21,42] \n",
"#test_List = [4,7,12,21] \n",
"test_Set = set(test_List)\n",
"#TypeError: 'set' object is not subscriptable\n",
"#result = divide(test_Set)\n",
"result = divide(test_List)\n",
"expected = 84\n",
"assert result == expected, \"\"\"result: {} != {}\"\"\".format(result, expected)\n",
"print(\"\"\"result: {} == expected: {}\"\"\".format(result, expected))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
""
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2.0
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment