mmensik Haskell oneliner:
main = do interact (concat . (\[p,q]->zipWith (\x y-> [x,y]) p q) . lines)
Elmex90s Using list comprehension in Haskell
mingle :: String -> String -> String mingle a b = concat [[x, y] | (x, y) <- zip a b]
naderghanbari Thinking along the same lines here with Scala:
println { val List(p, q) = stdin.getLines.take(2).toList (p, q).zipped flatMap (List(_, _)) }
But I still like the Haskell solution better. Comprehensions are much more intiuitive in Haskell. Comprehensions in Scala are type-homogenous, Scala 3 will hopefully take care of this. This is a topic for somewhere else though.
blubberdiblub My Racket solution:
#lang racket (define (mingle p q) (let iter ([accu empty] [p (string->list p)] [q (string->list q)]) (if (empty? p) (list->string (reverse accu)) (iter (cons (first q) (cons (first p) accu)) (rest p) (rest q))))) (define p (read-line)) (define q (read-line)) (displayln (mingle p q))
Suggestions for improvement welcome.
fraburnham Has anyone, using clojure, used a high order function to solve this? I was getting timeouts until I stopped using them. I'm curious to know if I'm just using the high order functions inefficiently. If you have such a solution please PM me.
abhiranjan Hi @fraburnham, btw you can access clojure submission in the contest here.
rishat Same. At first, I tried
reduceandmapalong withstrbut had the last test failed. The next thing I did was change from map/reduce to simple loop andrecur, and everything worked fine. Still not quite certain why the latter bears lower complexity, though.
mangosmoothie this worked for me
(println (apply str (reduce (fn [acc [a b]] (conj acc a b)) [] (map list (read-line) (read-line)))))This works too:
(println (apply str (mapcat list (read-line) (read-line)))
denis631 wanted to show my Clojure solution
(defn string-mingling [a b] (->> (mapcat list (seq a) (seq b)) (apply str))) (println (string-mingling (read-line) (read-line)))
khrak I have passed all testcases beside 9 and 10. I'm using substring function, readLine and print, I think for large inputs some of this methods doesn't work properly. Could you help me?
abhiranjan Hi @bolean, in java/scala, the complexity of
s1.concat(s2)ors1 + s2is O(M + N) where M and N are the respective String lengths, instead of O(1).khrak Oh, thanks I didn't know that, but still I got runtime error for those test cases and can that be caused by this reason?
abhiranjan For each addition operation, a new memroy block of N+M size is allocated. Probably due to this, you are running short of memory, leading to memory limit exceeded.
khrak Mmm, I think I guess the point. I'm starting to like scala more. ^_^
ronagrawal Thanks. It will be great if you could mention the above detail in Editorial Section also. I had solved the problem using different approach. I would have missed this information if I had not read discussion board.
ronagrawal Scala does tail recursion optimisation at compile-time and the recursive function is transformed into a loop by the compiler I was wondering why the following solution says "Run Time Error"
@tailrec def mingle(p : String, q : String, acc : String = "" ) : String = { if(p.isEmpty) acc else mingle(p.tail,q.tail,acc+p.head+q.head)}
Is it because of same reason ?
ranjithrajd use StringBuilder for concat operation in scala
srakshit code is working fine in my terminal. I feel you missed to import. import scala.annotation.tailrec
khrak I have modified this code several times but I always get TLE for las test case. I don't know why, when I use List[Char], to my mind when I use ch :: list this executes in O(list.length) time and can I do this adding in constant time or how can I make my code faster?
abhiranjan Did you try it in reverse order :)
khrak you mean list :: ch ? When I wrote list :: ch1 :: ch2 I didn't compile then I thought It's wrong in scala. I don't have much experience in scala, It's almost a week I code in it
abhiranjan Something like
def f(p: List[Char], q: List[Char]) : List[Char] = { if (p.isEmpty) List() else (p.head :: q.head :: f1 (p.tail, q.tail)) }PS: Almost all the challenges are designed such that you don't need mutable variables to solve them.
khrak Thank you it finally accepted. I'll check for differences those codes to understand what was the problem. Thank you again
serhii_nesteruk Hello! I wonder why is this solution is better than mine:
def recursiveZip(l1: List[Char], l2: List[Char], acc: List[Char]): List[Char] = { if(l1.isEmpty) acc else recursiveZip(l1.tail, l2.tail, acc ++ List(l1.head, l2.head)) }It is tail recursive function, list concatenation has linear complexity
PRASHANTB1984 many compilers are optimized for tail-recursion which makes such functions less inefficient than one would normally expect them to be. For example, the tailRec keyword in Scala.
abhiranjan @serhii_nesteruk,
::has constant complexity, while++is linear.
In your code you are applying++n times. First on the list of length 1, then 2, then 3, and so on. So overall complexity will beO(1) + O(2) + ... + O(n-1) ~= O(n^2)serhii_nesteruk thanks for the explanation!
ronagrawal [deleted]blowkj This is the solution that I eventually came up with and it still times out on test case 10. Interestingly, a simple for loop which prints out the characters of the strings also times out on that case and is about twice as long in execution on test case 9. On my local machine, I get stack overflow way before the execution time problem. Any suggestions?
abhiranjan Hi @blowkj, sorry can't find your solution.
Common source of long execution is the complexity of
+operator (or append method) for strings. It's of Appending two strings, one of length N, other of M, is of complexityO(N+M). Here it's repeatitive addition, so it can be of quadratic complexity.blowkj Sorry, I meant the onbe that you posted. Here is my version: def Mingle(P:List[Char],Q:List[Char]):List[Char] = { if(P.isEmpty)return List() return P.head :: Q.head :: Mingle(P.tail,Q.tail) }
def main(args: Array[String]) { val P = readLine().toList val Q = readLine().toList println(Mingle(P,Q).mkString) }Note that I don't use the + operator. Thanks,
blowkj OK, got it now. Googling on tail recursion helped.
kourouklides Hi @abhiranjan
I have the same issue (using F sharp).
However, the last two cases timed-out. On a standard laptop they work just fine.
abhiranjan Hi, sorry I missed this one. You can access other F# accepted solutions at leaderboard. Please feel free to refer them.
dingma129 A scala solution using
flatMapval s: String = scala.io.StdIn.readLine.trim val t: String = scala.io.StdIn.readLine.trim println((s,t).zipped.flatMap{List(_,_)})
bilna_p what is the complexity of this code
val p = scala.io.StdIn.readLine() val q = scala.io.StdIn.readLine() val r = p.zip(q).map(x => x._1 + "" + x._2).mkString("")
jaihindhreddy interleavemakes this trivial in Clojure.(println (apply str (interleave (read-line) (read-line))))
weozUA Scala solution
val f = () => scala.io.StdIn.readLine println(f().zip(f()).flatten{case(a,b) => List(a,b)}.mkString(""))
naderghanbari This is cool but note that you are using the
flattenin a way that you normally shouldn't which might confuse people from other functional languages.This is one of the caveats of the Scala standard library (related to implicit parameters and implicit conversion)
It's better to use
flatMapinsteadval p = f() val q = f() val result = (p, q).zipped flatMap (List(_, _))
Note that the final
resultis a collection ofChars and there's no need to callmkStringon it.Here's my complete answer:
println { val List(p, q) = stdin.getLines.take(2).toList (p, q).zipped flatMap (List(_, _)) }
johanirvall F# has a nifty
zipfunction for sequences:Seq.zip (System.Console.ReadLine()) (System.Console.ReadLine()) |> Seq.iter (fun (a,b) -> printf "%c%c" a b)
krark You don't even need zip, if you use iter2:
let p = System.Console.ReadLine() |> Seq.toList let q = System.Console.ReadLine() |> Seq.toList let r p q = List.iter2 (printf "%c%c") p q r p qjohanirvall Very true, but I beg to differ: I prefer
ziphere instead of creating two separate lists ,'-)
Sort 31 Discussions, By:
Please Login in order to post a comment