Skip to content

Instantly share code, notes, and snippets.

@GlulkAlex

GlulkAlex/string_Compression.scala

Last active May 5, 2016 12:58
Show Gist options
  • Save GlulkAlex/183ec116621c146c344ae3785be89291 to your computer and use it in GitHub Desktop.
Save GlulkAlex/183ec116621c146c344ae3785be89291 to your computer and use it in GitHub Desktop.
Download ZIP
Functional Programming: Recursion, Divide and Conquer, String Parsing, Scala
Raw
string_Compression.scala
object Solution {
def main(args: Array[String]) {
/* Enter your code here.
Read input from STDIN.
Print output to STDOUT.
Your class should be named Solution
*/
///>>> it seems that something faster than O(N) needed
///> QuickSortMerge may be ? O(N * log(N)) ???
/*
aaabaaaaccaaaaba => a3ba4c2a4ba
-> top-down
"aaabaaaa" + "ccaaaaba"
"aaab" + "aaaa" + "ccaa" + "aaba"
"aa" + "ab" + "aa" + "aa" + "cc" + "aa" + "aa" + "ba"
-> ground-up
"a2", "ab", "a2", "a2", "c2", "a2", "a2", "ba"
"a2" + "ab", "a2" + "a2", "c2" + "a2", "a2" + "ba"
"a3b", "a4", "c2a2", "a2ba"
"a3b" + "a4", "c2a2" + "a2ba"
"a3ba4", "c2a4ba"
"a3ba4" + "c2a4ba"
"a3ba4c2a4ba" == "a3ba4c2a4ba" <- Done
...
so, for each chunk .head & .last -> needed
case class Chunk(
head: Char
, head_Count: Int = 1
, body: String = ""
, last: Option[Char] = None
, last_Count: Int = 0)
"a2" -> Chunk(head = 'a', head_Count = 2) == Chunk(a,2,,None,0)
"a3b" -> Chunk(head = 'a', 3, "", Some('b'), 1) == Chunk(a,3,,Some(b),1)
"a3ba4" -> Chunk(head = 'a', 3, "b", Some('a'), 4) == Chunk(a,3,b,Some(a),4)
...
Merge step:
Cases:
"a2" + "ab" => "a3b"
Chunk(a,2,,None,0) + Chunk(a,1,,Some(b),1) => Chunk(a,3,,Some(b),1) ->
if (
c_1.last_Count == 0 ||
//c_1.body == "" || // <- 1st is .last then .body
c_1.last.isEmpty ) &&
c_2.last.nonEmpty &&
c_2.body == "" &&
c_1.head == c_2.head
merged.head_Count = c_1.head_Count + c_2.head_Count
merged.body = c_2.body
merged.last = c_2.last
merged.last_Count = c_2.last_Count
"a2" + "a2" => "a4"
Chunk(a,2,,None,0) + Chunk(a,2,,None,0) => Chunk(a,4,,None,0) ->
if (
c_1.last_Count == 0 ||
c_1.body == "" ||
c_1.last.isEmpty ) &&
c_1.head == c_2.head
merged.head_Count = c_1.head_Count + c_2.head_Count
merged.body = c_2.body
merged.last = c_2.last
merged.last_Count = c_2.last_Count
"c2" + "a2" => "c2a2"
Chunk(c,2,,None,0) + Chunk(a,2,,None,0) => Chunk(c,2,,Some(a),2) ->
if (
c_1.last_Count == 0 ||
c_1.body == "" ||
c_1.last.isEmpty ) &&
c_1.head != c_2.head
merged.head_Count = c_1.head_Count
merged.body = c_2.body
merged.last = c_2.last
merged.last_Count = c_2.last_Count
"c2a2" + "a2ba" => "c2a4ba"
Chunk(a,2,,None,0) + Chunk(b,1,,None,0) => Chunk(a,3,,Some(b),1) ->
if (c_1.last_Count == 0 (|| c_1.body == "") || c_1.last.isEmpty ) && c_1.head == c_2.head
merged.head_Count = c_1.head_Count + c_2.head_Count
merged.body = c_2.body
merged.last = c_2.last
merged.last_Count = c_2.last_Count
"a3ba4" + "c2a4ba" => "a3ba4c2a4ba"
Chunk(a,3,b,Some(a),4) + Chunk(c,2,a4b,Some(a),1) => Chunk(a,3,ba4{c2a4b,Some(a),1}) ->
if (c_1.last_Count > 0 || c_1.body != "" || c_1.last.nonEmpty ) && c_1.last != c_2.head
merged.head_Count = c_1.head_Count
merged.body = c_1.body + c_1.last + (c_1.last_Count > 1 | "") + c_2.body
merged.last = c_2.last
merged.last_Count = c_2.last_Count
*/
import scala.annotation.tailrec
import scala.io.StdIn
import scala.util.{Try, Success, Failure}
val is_Debug_Mode: Boolean = (
//true
false
)
/*val test_Cases_Total: Int = (
scala.io.StdIn
//.readInt()
.readLine()
)*/
/**/
//val msg: String = scala.io.StdIn.readLine()
//scala.collection.immutable.Stream[Char] = Stream(1, ?)
//val msg: Stream[Char] = scala.io.StdIn.readLine().toStream
val msg: Try[Stream[Char]] = Try(
StdIn.readLine(
//"Message to deflate:\n"
).toStream
)
/*msg match {
case Success(v) => Success(v)
case Failure(e) => e.getMessage
}*/
if (is_Debug_Mode) {
//println(s"""test_Cases_Total:${test_Cases_Total}""")
println(s"""msg:${msg}""")
}
/*
Contract:
(.head != .last if .head.nonEmpty && .body == "" | .isEmpty) &&
body.head != .head &&
body.last != .last
if .last exist / .nonEmpty => .head exist / .nonEmpty
if .body exist / .nonEmpty =>
(.head exist / .nonEmpty && .last exist / .nonEmpty) ||
(.head .isEmpty && .last .isEmpty)
*/
case class Chunk(
//head: Char
head: Option[Char] = None
, head_Count: Int = 0//1
, body: String = ""
, last: Option[Char] = None
, last_Count: Int = 0
) {
//Auxiliary Constructor
/*def this(
//error: ambiguous reference to overloaded definition
head: Option[Char] = None
, head_Count: Int = 0//1
, body: String = ""
, last: Option[Char] = None
, last_Count: Int = 0
) {
///> Contract validation
this(head, head_Count, body, last, last_Count)
}*/
def empty_Count(count: Int): String = if (count > 0) {
count.toString
} else {
""
}
def mkString: String = "" + head.getOrElse("") +
more_Then_2_Str(head_Count) +
body +
last.getOrElse("") +
more_Then_2_Str(last_Count)
override def toString: String = "" + head.getOrElse("") + empty_Count(head_Count) + "." +
body + "." +
last.getOrElse("") + empty_Count(last_Count)
///> Contract validation
// assert
if (body != "") {
///> this part fails for Test Case #9 - 12
if (is_Debug_Mode) {
assert(
(head.nonEmpty && last.nonEmpty) || (head.isEmpty && last.isEmpty)
, s"""Contract violation -> .head: ${head} or .last: ${last} isEmpty""" +
s""" when .body: ${body} is nonEmpty"""
)
}
} else {
/*if (head.nonEmpty && body == "" && head == last) {
if (is_Debug_Mode) {
println(s"""Contract violation -> .head: ${head} == .last: ${last}""")
}
}*/
if (
//is_Debug_Mode
true
) {
assert(
head.nonEmpty && head != last
, s"""Contract violation -> .head: ${head} == .last: ${last}""" +
s""" when .body: ${body} isEmpty"""
)
}
}
}
def more_Then_2_Str(counter: Int): String = if (counter > 1) {counter.toString} else {""}
/*
cases:
".." + ".." => ".."
".a3b." + ".c5." => ".." <- unexpected case
...
"a2.." + ".." => "a2.."
".." + "a2.." => "a2.."
...
"a2.." + "a3.." => "a5.."
"a2.." + "b3.." => "a2..b3"
...
"a2.." + "a1..b1" => "a3..b1"
"a2.." + "c1..b1" => "a2.c.b1"
...
p13.. + p4.s3i4.z3 => p17.s3i4.z3
r13.. + p4.s3i4.z3 => r13.p4s3i4.z3
...
p4.s3i4.z3 + z1.. => p4.s3i4.z4
p4.s3i4.z3 + y1.. => p4.s3i4z3.y1
...
"a2..b1" + "b3.." => "a2.b4"
"a2..b1" + "c1.." => "a2.b.c1"
...
"a2..b3" + "a1..b1" => "a2.b3a.b1"
"a2..b3" + "b1..c1" => "a2.b4.c1"
...
"a2.c.b3" + "b1..c1" => "a2.cb4.c1"
"a2.c.a3" + "b1..c1" => "a2.ca3b.c1"
...
"a2..b3" + "b1.a4.c1" => "a2.b4a4.c1"
"a2..b3" + "c1.a4.b1" => "a2.b3ca4.b1"
...
"a2.c.b3" + "b1.a5.c1" => "a2.cb4a5.c1"
"a2.c.b3" + "a1.b5.c1" => "a2.cb3ab5.c1"
*/
def merge(
/*left_Part: String
,right_Part: String
): Left[String, Chunk] = {*/
/*left: Right[String, Chunk]
,right: Right[String, Chunk]
): Right[String, Chunk] = {*/
//left: Either[String, Chunk]
//,right: Either[String, Chunk]
left_Part: Chunk
,right_Part: Chunk
//): Either[String,Chunk] = {
): Chunk = {
//val Right(left_Part)/*: Chunk*/ = left
//val Right(right_Part)/*: Chunk*/ = right
(left_Part, right_Part) match {
///> ".." + ".." => ".."
case (Chunk(None, 0, "", None, 0), Chunk(None, 0, "", None, 0)) => {
if (is_Debug_Mode) {println(s""".. + .. => ..: ${left_Part} + ${right_Part}""")}
left_Part // right_Part
}
case (Chunk(None, 0, l_B, None, 0), Chunk(None, 0, r_B, None, 0)) => {
///> ".a3b." + ".c5." => ".." <- unexpected case
if (is_Debug_Mode) {println(s""".a3b. + .a3b. => ?.?.?: ${left_Part} + ${right_Part}""")}
assert(left_Part.head.nonEmpty && right_Part.head.nonEmpty, "unexpected merge case")
Chunk(None, 0, "", None, 0)
}
//case BodyWarper(b) if b != "b1" => b
case (Chunk(Some(l_H), l_H_C, "", None, 0), Chunk(None, 0, "", None, 0)) => {
///> "a2.." + ".." => "a2.."
if (is_Debug_Mode) {println(s"""a2.. + .. => a2..: ${left_Part} + ${right_Part}""")}
left_Part
}
case (Chunk(None, 0, "", None, 0), Chunk(Some(r_H), r_H_C, "", None, 0)) => {
///> ".." + "a2.." => "a2.."
if (is_Debug_Mode) {println(s""".. + a2.. => a2..: ${left_Part} + ${right_Part}""")}
right_Part
}
case (Chunk(Some(l_H), l_H_C, "", None, 0), Chunk(Some(r_H), r_H_C, "", None, 0)) => {
///> "a2.." + "a3.." => "a5.."
///> "a2.." + "b3.." => "a2..b3"
val result = if (l_H == r_H) {
if (is_Debug_Mode) {print(s"""a2.. + a3.. => a5..: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = left_Part.head_Count + right_Part.head_Count
,body = ""//right_Part.body
,last = None//right_Part.last
,last_Count = 0//right_Part.last_Count
)
} else {
if (is_Debug_Mode) {print(s"""a2.. + b3.. => a2..b3: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = left_Part.head_Count
,body = ""
,last = right_Part.head
,last_Count = right_Part.head_Count
)
}
if (is_Debug_Mode) {print(s""" = ${result}\n""")}
result
}
case (Chunk(Some(l_H), l_H_C, "", None, 0), Chunk(Some(r_H), r_H_C, "", Some(r_L), r_L_C)) => {
///> "a2.." + "a1..b1" => "a3..b1"
///> "a2.." + "c1..b1" => "a2.c.b1"
if (l_H == r_H) {
if (is_Debug_Mode) {println(s"""a2.. + a1..b1 => a3..b1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C + r_H_C
,body = ""//right_Part.body
,last = right_Part.last
,last_Count = r_L_C
)
} else {
if (is_Debug_Mode) {println(s"""a2.. + c1..b1 => a2.c.b1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = r_H +
more_Then_2_Str(r_H_C)
,last = right_Part.last
,last_Count = r_L_C
)
}
}
case (Chunk(Some(l_H), l_H_C, "", Some(l_L), l_L_C), Chunk(Some(r_H), r_H_C, "", None, 0)) => {
///> "a2..b1" + "b3.." => "a2.b4"
///> "a2..b1" + "c1.." => "a2.b.c1"
if (l_L == r_H) {
if (is_Debug_Mode) {println(s"""a2..b1 + b3.. => a2.b4: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
,body = ""//right_Part.body
,last = right_Part.head
,last_Count = l_L_C + r_H_C
)
} else {
if (is_Debug_Mode) {println(s"""a2..b1 + c1.. => a2.b.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_L +
more_Then_2_Str(l_L_C)
,last = right_Part.head
,last_Count = r_H_C
)
}
}
case (
Chunk(Some(l_H), l_H_C, "", None, 0),
Chunk(Some(r_H), r_H_C, r_B, Some(r_L), r_L_C))
if r_B != "" => {
///>p13.. + p4.s3i4.z3 => p17.s3i4.z3
///>r13.. + p4.s3i4.z3 => r13.p4s3i4.z3
if (l_H == r_H) {
if (is_Debug_Mode) {println(s"""p13.. + p4.s3i4.z3 => p17.s3i4.z3: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C + r_H_C
,body = r_B
,last = right_Part.last
,last_Count = r_L_C
)
} else {
if (is_Debug_Mode) {println(s"""r13.. + p4.s3i4.z3 => r13.p4s3i4.z3: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = r_H + more_Then_2_Str(r_H_C) + r_B
,last = right_Part.last
,last_Count = r_L_C
)
}
}
case (
Chunk(Some(l_H), l_H_C, l_B, Some(l_L), l_L_C),
Chunk(Some(r_H), r_H_C, "", None, 0)) if l_B != "" => {
///> p4.s3i4.z3 + z1.. => p4.s3i4.z4
///> p4.s3i4.z3 + y1.. => p4.s3i4z3.y1
if (l_L == r_H) {
if (is_Debug_Mode) {println(s"""p4.s3i4.z3 + z1.. => p4.s3i4.z4: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
,body = l_B
,last = left_Part.last
,last_Count = l_L_C + r_H_C
)
} else {
if (is_Debug_Mode) {println(s"""p4.s3i4.z3 + y1.. => p4.s3i4z3.y1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_B + l_L + more_Then_2_Str(l_L_C)
,last = right_Part.head
,last_Count = r_H_C
)
}
}
case (
Chunk(Some(l_H), l_H_C, "", Some(l_L), l_L_C),
Chunk(Some(r_H), r_H_C, "", Some(r_L), r_L_C)) => {
///> "a2..b3" + "a1..b1" => "a2.b3a.b1"
///> "a2..b3" + "b1..c1" => "a2.b4.c1"
if (l_L == r_H) {
if (is_Debug_Mode) {println(s"""a2..b3 + a1..b1 => a2.b3a.b1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_L + more_Then_2_Str(l_L_C + r_H_C)
,last = right_Part.last
,last_Count = r_L_C
)
} else {
if (is_Debug_Mode) {println(s"""a2..b3 + b1..c1 => a2.b4.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_L + more_Then_2_Str(l_L_C) + r_H + more_Then_2_Str(r_H_C)
,last = right_Part.last
,last_Count = r_L_C
)
}
}
case (
Chunk(Some(l_H), l_H_C, l_B, Some(l_L), l_L_C),
Chunk(Some(r_H), r_H_C, "", Some(r_L), r_L_C)) if l_B != "" => {
///> "a2.c.b3" + "b1..c1" => "a2.cb4.c1"
///> "a2.c.a3" + "b1..c1" => "a2.ca3b.c1"
if (l_L == r_H) {
if (is_Debug_Mode) {println(s"""a2.c.b3 + b1..c1 => a2.cb4.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_B + l_L + more_Then_2_Str(l_L_C + r_H_C)
,last = right_Part.last
,last_Count = r_L_C
)
} else {
if (is_Debug_Mode) {println(s"""a2.c.a3 + b1..c1 => a2.ca3b.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_B + l_L + more_Then_2_Str(l_L_C) + r_H + more_Then_2_Str(r_H_C)
,last = right_Part.last
,last_Count = r_L_C
)
}
}
case (
Chunk(Some(l_H), l_H_C, "", Some(l_L), l_L_C),
Chunk(Some(r_H), r_H_C, r_B, Some(r_L), r_L_C)) if r_B != "" => {
///> "a2..b3" + "b1.a4.c1" => "a2.b4a4.c1"
///> "a2..b3" + "c1.a4.b1" => "a2.b3ca4.b1"
if (l_L == r_H) {
if (is_Debug_Mode) {println(s"""a2..b3 + b1.a4.c1 => a2.b4a4.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_L + more_Then_2_Str(l_L_C + r_H_C) + r_B
,last = right_Part.last
,last_Count = r_L_C
)
} else {
if (is_Debug_Mode) {println(s"""a2..b3 + c1.a4.b1 => a2.b3ca4.b1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = l_H_C
// total count > 1
,body = l_L + more_Then_2_Str(l_L_C) + r_H + more_Then_2_Str(r_H_C) + r_B
,last = right_Part.last
,last_Count = r_L_C
)
}
} case _ => {
///> "a2.c.b3" + "b1.a5.c1" => "a2.cb4a5.c1"
///> "a2.c.b3" + "a1.b5.c1" => "a2.cb3ab5.c1"
/*if (
left_Part.head.nonEmpty &&
left_Part.body != "" &&
left_Part.last.nonEmpty &&
right_Part.head.nonEmpty &&
right_Part.body != "" &&
right_Part.last.isEmpty
)*/
if (left_Part.last == right_Part.head) {
if (is_Debug_Mode) {println(s"""a2.c.b3 + b1.a5.c1 => a2.cb4a5.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = left_Part.head_Count
// total count > 1
,body = left_Part.body +
left_Part.last.getOrElse("") +
more_Then_2_Str(left_Part.last_Count + right_Part.head_Count) +
right_Part.body
,last = right_Part.last
,last_Count = right_Part.last_Count
)
} else {
if (is_Debug_Mode) {println(s"""a2.c.b3 + a1.a5.c1 => a2.cb3ab5.c1: ${left_Part} + ${right_Part}""")}
Chunk(
head = left_Part.head
,head_Count = left_Part.head_Count
// total count > 1
,body = left_Part.body +
left_Part.last.getOrElse("") +
more_Then_2_Str(left_Part.last_Count) +
right_Part.head.getOrElse("") +
more_Then_2_Str(right_Part.head_Count) +
right_Part.body
,last = right_Part.last
,last_Count = right_Part.last_Count
)
}
}
}
}
//An infix type T1 op T2 ?
// tuple ?
def divide(
//source_Str: String
source_Str: Chunk
//): Either[String, Chunk] = {
///> so, actual result must be contained in the Chunk.body
///> + may be one last merge to use nonempty Chunk.head & Chunk.last ???
): Chunk = {
/*
val Right(r) = divide("!")
r: Chunk = Chunk(a,3,b,Some(a),4)
*/
//val source_Str_Length: Int = source_Str.length
val source_Str_Length: Int = source_Str.body.length
//if (is_Debug_Mode) {println(s"""dividing ...""")}
if (is_Debug_Mode) {println(s"""dividing source_Str_Length: ${source_Str_Length} ...""")}
/*
source_Str_Length: 3
source_Str_Length: 1
source_Str_Length: 0 ...
java.lang.StackOverflowError
*/
if (
source_Str_Length > 2 &&
source_Str.head.isEmpty
//source_Str.head.nonEmpty
) {
///>>> Merge step
///> actual / final result
//5 / 2 -> res22: Int = 2
//5 / 2.0 -> res23: Double = 2.5
//"0123456789".take(5)
//"0123456789".drop(5)
if (is_Debug_Mode) {
println(s"""merging ... """ +
s"""${Chunk(body = source_Str.body.take(source_Str_Length / 2))}""" +
s""" with ${Chunk(body = source_Str.body.drop(source_Str_Length / 2))}""")}
merge(
divide(
//source_Str.take(source_Str_Length / 2)
Chunk(body = source_Str.body.take(source_Str_Length / 2))
) /*match {
///> '"" + ' for inferred type cast
case Right(Chunk(h, h_C, b, Some(l), l_C)) => Left("" + h + h_C + b + l + l_C)
case Right(Chunk(h, h_C, b, None, _)) => Left("" + h + h_C + b)
case Left(str) => Left(str)
}*/
,divide(
//source_Str.drop(source_Str_Length / 2)
Chunk(body = source_Str.body.drop(source_Str_Length / 2))
) /*match {
///> '"" + ' for inferred type cast
case Right(Chunk(h, h_C, b, Some(l), l_C)) => Left("" + h + h_C + b + l + l_C)
case Right(Chunk(h, h_C, b, None, _)) => Left("" + h + h_C + b)
case Left(str) => Left(str)
}*/
)
} else if (source_Str_Length == 2) {
///>>> base case
//val List(head, last) = source_Str.toList
//scala> val (a, b) = (c_1.body.head, c_1.body.tail.head)
//a: Char = O
//b: Char = K
val (head, last) = (source_Str.body.head, source_Str.body.tail.head)
if (is_Debug_Mode) {println(s"""head: ${head}, last: ${last}""")}
//Right(Chunk('a',3,"b",Some('a'),4))
/*
var List(a, b) = "AB".toList
a: Char = A
b: Char = B
scala> "ab".endsWith("a")
res27: Boolean = false
scala> "ab".endsWith("b")
res28: Boolean = true
"aaabbc".dropWhile(_ == 'a')
res30: String = bbc
*/
if (
head == last
//source_Str.head == source_Str.tail.head
//source_Str.head == source_Str.last
//source_Str.endsWith(source_Str.head)
//source_Str(0) == source_Str(1)
) {
if (is_Debug_Mode) {println(s"""Chunk(head, 2): ${Chunk(Some(head), 2)}""")}
//Right(Chunk(head, 2))
Chunk(Some(head), 2)
} else { //if (head != last)
if (is_Debug_Mode) {println(
s"""Chunk(head, 1, "", Some(last), 1): ${Chunk(Some(head), 1, "", Some(last), 1)}""")}
//Right(Chunk(head, 1, "", Some(last), 1))
Chunk(Some(head), 1, "", Some(last), 1)
}
} else if (source_Str_Length == 1) {
///>>> base case
///> source_Str.body.length == 1
//Right(Chunk(source_Str.head))
//if (source_Str.head.nonEmpty) {
//if (is_Debug_Mode) {println(s"""Chunk(source_Str.head): ${Chunk(source_Str.head)}""")}
//Chunk(source_Str.head)
//} else {
if (is_Debug_Mode) {println(s"""Chunk(source_Str.head): ${Chunk(Some(source_Str.body.head), 1)}""")}
//Chunk(Some(source_Str.body.head), 1)
Chunk(Some(source_Str.body.head), 1, "", None, 0)
//}
} else {//if (source_Str_Length <= 0) {
///>>> base case ??? <- nonEmpty Char
///>>> non merge case -> instant result return
///> so, actual result must be contained in the Chunk.body
//if (is_Debug_Mode) {println(s"""Left(source_Str) == ''""")}
if (is_Debug_Mode) {
println(s"""source_Str_Length: ${source_Str_Length} => ${Chunk(body = source_Str.body)}""")}
//Left(source_Str)
//Chunk(body = source_Str.body)
//Chunk()
Chunk(None, 0, "", None, 0)
}
}
// O(N)
@tailrec
//scala.annotation.tailrec
def parse_Str(
source_Str: String
//,last_Char_Counter: Int = 0
,char_Sequense_Length: Int = 0
///> accum.last
,last_Char: Option[Char] = None//Char//String = ""
,accum: String = ""
///> local log switch
,is_Debug_Mode: Boolean = false
): String = {
/*
cases:
.head.nonEmpty //&& .tail.nonEmpty//.tail.head.nonEmpty
//.head == .tail.head
accum.isEmpty
char_Sequense_Length += 1
//accum += .head
accum.nonEmpty
accum.last == .head// == .tail.head
char_Sequense_Length += 1
accum.last != .head
char_Sequense_Length == 0
accum += .head
char_Sequense_Length > 0
accum += accum.last + char_Sequense_Length
char_Sequense_Length = 0
//.head.nonEmpty && .tail.isEmpty//.tail.head.isEmpty
.head.isEmpty // => && .tail.head.isEmpty
.head == .tail.head
char_Sequense_Length == 0
accum += accum.last
char_Sequense_Length > 0
accum += accum.last + char_Sequense_Length
//char_Sequense_Length = 0
=> accum
*/
if (source_Str.isEmpty) {
if (is_Debug_Mode) {println(s"""source_Str.isEmpty""")}
if (is_Debug_Mode) {println(s"""accum: ${accum}, char_Sequense_Length: ${char_Sequense_Length}""")}
if (char_Sequense_Length <= 1) {
if (is_Debug_Mode) {println(s"""char_Sequense_Length == 0""")}
// result
accum + last_Char.getOrElse("")
} else {//if (char_Sequense_Length > 1)
if (is_Debug_Mode) {println(s"""char_Sequense_Length > 0""")}
// result
accum + last_Char.getOrElse("") + char_Sequense_Length
}
} else {//if (source_Str.nonEmpty)
if (is_Debug_Mode) {println(s"""source_Str.nonEmpty""")}
if (is_Debug_Mode) {println(s"""accum: ${accum}, char_Sequense_Length: ${char_Sequense_Length}""")}
/*var next_Last_Char_Counter = 0
var next_Last_Char = ""
var next_Accum = ""*/
/*if (accum.isEmpty) {
if (is_Debug_Mode) {println(s"""accum.isEmpty""")}
// recursion
parse_Str(source_Str.tail, char_Sequense_Length + 1, Some(source_Str.head), accum)
} else { //if (accum.nonEmpty)
if (is_Debug_Mode) {println(s"""accum.nonEmpty""")}*/
if (last_Char == Some(source_Str.head)) {
if (is_Debug_Mode) {println(s"""last_Char:${last_Char} == Some(source_Str.head:${source_Str.head})""")}
// recursion
//if (last_Char.nonEmpty)
//parse_Str(source_Str.tail, char_Sequense_Length + 1, last_Char, accum)
parse_Str(source_Str.tail, char_Sequense_Length + 1, Some(source_Str.head), accum)
} else {//(last_Char != source_Str.head)
if (is_Debug_Mode) {println(s"""last_Char:${last_Char} != Some(source_Str.head:${source_Str.head})""")}
if (char_Sequense_Length <= 1) {
if (is_Debug_Mode) {println(s"""char_Sequense_Length <= 1""")}
// recursion
parse_Str(source_Str.tail, 1, Some(source_Str.head), accum + last_Char.getOrElse(""))
} else {//if (char_Sequense_Length > 0)
if (is_Debug_Mode) {println(s"""char_Sequense_Length > 1""")}
// recursion
parse_Str(
source_Str.tail
, 1
, Some(source_Str.head)
, accum + last_Char.getOrElse("") + char_Sequense_Length)
}
}
//}
}
}
// O(N)
def parse_Str_2(
//source_Str: String
//msg: String
msg: Stream[Char]
): String = {
//import scala.util.{Try, Success, Failure}
var result: String = ""
var char_Sequense_Length: Int = 0
var last_Char: Option[Char] = None
//var char: Char = '\n'
/**/
for {
char <- msg
//char <- scala.io.StdIn.readLine()
} {/**/
//while(condition) {
/*do {
//statement(s)
try {
char = scala.io.StdIn.readChar()
println(s"""char: ${char}""")
} catch {
case ex: java.io.EOFException => {
println(s"""java.io.EOFException: ${result}""")
char = '\n'
}
case ex: java.lang.StringIndexOutOfBoundsException => {
println(s"""java.lang.StringIndexOutOfBoundsException: ${result}""")
char = '\n'
}
} */
//} while( condition )
if (last_Char == Some(char)) {
if (is_Debug_Mode) {println(s"""last_Char:${last_Char} == Some(char:${char})""")}
char_Sequense_Length += 1
//last_Char = Some(char)
} else {//(last_Char != source_Str.head)
if (is_Debug_Mode) {println(s"""last_Char:${last_Char} != Some(char:${char})""")}
result += last_Char.getOrElse("")
if (char_Sequense_Length <= 1) {
if (is_Debug_Mode) {println(s"""char_Sequense_Length <= 1""")}
//char_Sequense_Length = 1
//last_Char = Some(char)
//result += last_Char.getOrElse("")
} else {//if (char_Sequense_Length > 0)
if (is_Debug_Mode) {println(s"""char_Sequense_Length > 1""")}
//char_Sequense_Length = 1
//last_Char = Some(char)
//result += last_Char.getOrElse("") + char_Sequense_Length
result += char_Sequense_Length
}
char_Sequense_Length = 1
last_Char = Some(char)
}
} //while( char != '\n' )
result += last_Char.getOrElse("")
if (char_Sequense_Length <= 1) {
if (is_Debug_Mode) {println(s"""char_Sequense_Length == 0""")}
// result
//result += last_Char.getOrElse("")
} else {//if (char_Sequense_Length > 1)
if (is_Debug_Mode) {println(s"""char_Sequense_Length > 0""")}
// result
//result += last_Char.getOrElse("") + char_Sequense_Length
result += char_Sequense_Length.toString()
}
result
}
///>>>*** unit test ***<<<///
import scala.util.Random
//trait Generator[+T] {
//val rand = new java.util.Random
//def generate = rand.nextInt()
//def interval(lo: Int, hi: Int) : Generator[Int] = for { X <- integers } yield lo + x % (hi - lo)
val rand = new Random()
//rand: scala.util.Random = scala.util.Random@dfd3711
//scala> rand.nextInt(2)
//res12: Int = 0 | 1 <- boolean generator
//scala> (97 + rand.nextInt(122-97+1)).toChar
//res27: Char = a
def a_z_Random: Char = {
val a_Byte: Byte = 'a'.toByte
val z_Byte: Byte = 'z'.toByte
(a_Byte + rand.nextInt(z_Byte - a_Byte + 1)).toChar
}
/// 1≤length(msg)≤10^5
case class String_Compression(input_Str: String = "aaa", expected_Result: String = "a3")
@tailrec
def make_Test_String(
length_Limit: Int = 100//rand.nextInt(length_Limit)
,result_Accum: String = ""//String_Compression = String_Compression("", "")
): String = {
//): String_Compression = {
if (length_Limit <= 0) {
///> base case
result_Accum
} else {
///> recursion
val current_Char: Char = a_z_Random
val char_Repetition: Int = rand.nextInt(length_Limit)
//scala> (1 to 5 + 1).map(_ => 'a')
//res28: scala.collection.immutable.IndexedSeq[Char] = Vector(a, a, a, a, a, a)
//scala> (1 to 5 + 1).map(_ => 'a').mkString
//res29: String = aaaaaa
//scala> (1 to 5 + 1).map(_ => "a").fold[String]("")(_ + _)
//res56: String = aaaaaa
val str_Chunk: String = (1 to char_Repetition + 1).map(_ => current_Char).mkString
make_Test_String(
length_Limit - 1 - char_Repetition
,result_Accum + str_Chunk
)
}
}
val result_Chunk: Chunk = divide(Chunk(body = msg.getOrElse(Stream('!')).mkString))
//val result_String: String = result_Chunk.mkString
val result: String = /*"" + result_Chunk.head.getOrElse("") +
more_Then_2_Str(result_Chunk.head_Count) +
result_Chunk.body +
result_Chunk.last.getOrElse("") +
more_Then_2_Str(result_Chunk.last_Count)*/
result_Chunk.mkString
/*
cases:
"a2.." + ".." => "a2.."
".." + "a2.." => "a2.."
...
"a2.." + "a3.." => "a5.."
"a2.." + "b3.." => "a2..b3"
...
"a2.." + "a1..b1" => "a3..b1"
"a2.." + "c1..b1" => "a2.c.b1"
...
"a2..b1" + "b3.." => "a2.b4"
"a2..b1" + "c1.." => "a2.b.c1"
...
"a2..b3" + "a1..b1" => "a2.b3a.b1"
"a2..b3" + "b1..c1" => "a2.b4.c1"
...
"a2.c.b3" + "b1..c1" => "a2.cb4.c1"
"a2.c.a3" + "b1..c1" => "a2.ca3b.c1"
...
"a2..b3" + "b1.a4.c1" => "a2.b4a4.c1"
"a2..b3" + "c1.a4.b1" => "a2.b3ca4.b1"
...
"a2.c.b3" + "b1.a5.c1" => "a2.cb4a5.c1"
"a2.c.b3" + "a1.b5.c1" => "a2.cb3ab5.c1"
*/
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2), Chunk(None, 0, "", None, 0))
//val expected = Chunk(Some('a'), 2) //> OK
//val (t_C_1, t_C_2) = (Chunk(None, 0, "", None, 0), Chunk(Some('a'), 2))
//val expected = Chunk(Some('a'), 2) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('b'), 1), Chunk(Some('b'), 2))
//val expected = Chunk(Some('b'), 3) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", None, 0), Chunk(Some('a'), 1, "", Some('b'), 1))
//val expected = Chunk(Some('a'), 3, "", Some('b'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", None, 0), Chunk(Some('c'), 1, "", Some('b'), 1))
//val expected = Chunk(Some('a'), 2, "c", Some('b'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", Some('b'), 1), Chunk(Some('b'), 3, "", None, 0))
//val expected = Chunk(Some('a'), 2, "", Some('b'), 4) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", Some('b'), 1), Chunk(Some('c'), 3, "", None, 0))
//val expected = Chunk(Some('a'), 2, "b", Some('c'), 3) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", Some('b'), 3), Chunk(Some('a'), 1, "", Some('b'), 1))
//val expected = Chunk(Some('a'), 2, "b3a", Some('b'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", Some('b'), 3), Chunk(Some('b'), 1, "", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "b4", Some('c'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "c", Some('b'), 3), Chunk(Some('b'), 1, "", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "cb4", Some('c'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "c", Some('a'), 3), Chunk(Some('b'), 1, "", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "ca3b", Some('c'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", Some('b'), 3), Chunk(Some('b'), 1, "a4", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "b4a4", Some('c'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "", Some('b'), 3), Chunk(Some('c'), 1, "a4", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "b3ca4", Some('c'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "c", Some('b'), 3), Chunk(Some('b'), 1, "a5", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "cb4a5", Some('c'), 1) //> OK
//val (t_C_1, t_C_2) = (Chunk(Some('a'), 2, "c", Some('b'), 3), Chunk(Some('a'), 1, "b5", Some('c'), 1))
//val expected = Chunk(Some('a'), 2, "cb3ab5", Some('c'), 1) //> OK
///> p13.. + p4.s3i4.z3 <- (was | were) missing case shape / pattern
//val (t_C_1, t_C_2) = (Chunk(Some('p'), 13, "", None, 0), Chunk(Some('p'), 4, "s3i4", Some('z'), 3))
//val expected = Chunk(Some('p'), 17, "s3i4", Some('z'), 3) //> OK
///> t1.x2.u1 + u5.. => t1.x2.u6 <- (was | were) missing case shape / pattern
val (t_C_1, t_C_2) = (Chunk(Some('t'), 1, "x2", Some('u'), 1), Chunk(Some('u'), 5, "", None, 0))
val expected = Chunk(Some('t'), 1, "x2", Some('u'), 6)
val m_T_1 = merge(t_C_1, t_C_2)
if (is_Debug_Mode) {println(s"""merge(${t_C_1}, ${t_C_2}): ${m_T_1}""")}
if (is_Debug_Mode) {assert(m_T_1 == expected, s"""expected: ${expected}""")}
if (is_Debug_Mode) {
(0 to 9).foreach(v => {
val t_S: String = make_Test_String(rand.nextInt(100) + 1)
val exp_R: String = parse_Str(t_S)
val act_R: String = divide(Chunk(body = t_S)).mkString
println(s"""test_String_${v}: ${t_S}""")
assert(act_R == exp_R, s"""actual: ${act_R} != ${exp_R} expected""")
println(s"""compressed: ${act_R}""")
}
)
}
//println(parse_Str(msg.mkString))
//println(parse_Str_2(msg.getOrElse(Stream('!'))))
///> it pass Test Case #9 & 15 -> not time is up alert
//println(divide(msg.getOrElse(Stream('!')).mkString))
if (is_Debug_Mode) {println(s"""result_Chunk: ${result_Chunk}""")}
if (is_Debug_Mode) {println(s"""result_Chunk: ${result_Chunk.mkString}""")}
println(result)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment