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)))
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]
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.
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.
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 ,'-)
penman My haskell solution
import Data.List main = interact $ concat . transpose . lines
abratashov Elixir solution of the "String Mingling"
defmodule Solution do l1 = IO.gets("") |> String.trim |> String.codepoints l2 = IO.gets("") |> String.codepoints List.zip([l1, l2]) |> Enum.map(fn {x, y} -> x <> y end) |> Enum.join |> IO.puts end
mitchel0022 My haskell solution
f :: [String] -> String f [x,y] = foldl1 (++) $ zipWith (\x y -> [x] ++ [y]) x y main = interact $ f . lines
dhirajhimani In Scala :-
line1.zip(line2).foldLeft("")((a,b) => { a + b._1 + b._2 })
def mutate(p:List[Char], q:List[Char]): String = (p,q) match { case (a, Nil) => a mkString case (Nil, b) => b mkString case (Nil, Nil) => "" case (a, b) => a.head.toString + b.head.toString + mutate(a.tail, b.tail) }
Sort 27 Discussions, By:
Please Login in order to post a comment