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)))
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("")
patrick_ce Mine looked similar:
val first = scala.io.StdIn.readLine() val second = scala.io.StdIn.readLine() println( first zip second flatMap { case (x, y) => s"$x$y"} mkString("") )
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.
soltankara hi, here is my elixir solution
defmodule M do def mingle(l1, l2) do mingle(l1, l2, "") end def mingle([], [], str), do: IO.puts str def mingle([h1 | t1], [h2 | t2], str) do mingle(t1, t2, str <> h1 <> h2) end def main() do l1 = IO.gets("") |> String.trim |> String.codepoints l2 = IO.gets("") |> String.trim |> String.codepoints mingle(l1, l2) end end M.main
nitinpatel278 Using recursion:
mingle "" "" = "" mingle p q = (head p) : (head q) : mingle (tail p) (tail q) main = do p <- getLine q <- getLine putStrLn $ mingle p q
pedrosqueiroga did this pass? Without tail recursion, common-lisp fails at 9 and 10 (heap exhausted). And even with tail recursion, it fails at 10 because of the time limit, so I had to use a map, and no recursion, even though this is in the "recursion" section!!
nitinpatel278 Haskell solution did pass all the test cases. I don't know much about tail recursion to comment on that.
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(_,_)})
jaihindhreddy interleavemakes this trivial in Clojure.(println (apply str (interleave (read-line) (read-line))))
Sort 33 Discussions, By:
Please Login in order to post a comment