Can't solve this in Haskell and even Clojure

แชร์
ฝัง
  • เผยแพร่เมื่อ 6 พ.ย. 2024

ความคิดเห็น • 103

  • @milyvean
    @milyvean 3 ปีที่แล้ว +116

    Hey there, I just found you because of the amazing youtube algorithm that recommended your video. I just wanted to say that you are absolutely genius, you are able to explain concepts in such a welcoming and easy-to-grab way while enjoying the thing you probably love the most. I couldn't imagine anything more interesting as your videos on a boring wednesday evening. I absolutely respect that and I really hope you make it one day because you deserve so much more! Never have I seen such a kind, interesting and amazing person on this side of youtube. Please keep it up and continune to enjoy what you do! ❤ sincerely millie

  • @rafaelgil6895
    @rafaelgil6895 3 ปีที่แล้ว +30

    Around 36:00 100% agree! Why not do something if you type "help"? Heck, they could just add a "help" function on the namespace when starting the REPL. BTW, the function you were looking for is called "doc" and it takes the function as a parameter.

  • @diegorocha2186
    @diegorocha2186 3 ปีที่แล้ว +23

    This was a 1 2 3 code session btw. 1 problem, 2 Programming Paradigm and 3 languages. Very Naice!!!

  • @Hemigoblin
    @Hemigoblin 2 ปีที่แล้ว +21

    I really like how you keep zooming in and out to keep the code and the structure clear and readable. It’s even more impressive that you’re doing it live. Your video is better than many, many slideshows in its presentation.
    I’m curious to know if you ever solved the problem in Clojure after reading the comments.

  • @VitHealthing
    @VitHealthing 3 ปีที่แล้ว +68

    I don't know clojure but i guess you shouldn't remove namespace declaration when pasting you code on 55:32 Your solution is actually passes all tests

    • @TsodingDaily
      @TsodingDaily  3 ปีที่แล้ว +57

      Yeah, I also think the problem was in me removing the namespace. Unfortunately I only realized that after I uploaded the video. :D Oh well...

    • @LucasVieira42
      @LucasVieira42 3 ปีที่แล้ว +37

      I was like screaming at the monitor :(

    • @AyamineMISC
      @AyamineMISC 8 หลายเดือนก่อน

      @@TsodingDailyThis is a classic programming moment

    • @csbnikhil
      @csbnikhil 7 หลายเดือนก่อน +1

      But shouldn't Codewars take care of that? Not putting it an editable area, or prepending the namespace on submit, to avoid user oopsies like this?

  • @asdqwe4427
    @asdqwe4427 2 ปีที่แล้ว +3

    I just watched the first 19 minutes and I am amazed. Truly elegant code and the way you explained it actually made me able to grasp it!

  • @JustMaiyak
    @JustMaiyak 3 ปีที่แล้ว +24

    "Seems to be working, seems to be twerking" > words to live by. Amazing session as per usual 🤘

  • @MessageKyle
    @MessageKyle 3 ปีที่แล้ว +10

    My dude I took a haskell course and hated it because it didn't make sense and I never understood it but your haskell vids are making me feel like I'm breaking through

    • @vikingthedude
      @vikingthedude 2 ปีที่แล้ว +2

      Don't take a haskell course. Just learn you a haskell and miso on the yesod

  • @lhpaoletti
    @lhpaoletti ปีที่แล้ว +4

    Technically it's not exponential growth. It's polynomial growth. In this specific case it's quadratic growth. Haha, sorry for the technicality XD! Great vid

  • @sfyire
    @sfyire 3 ปีที่แล้ว +17

    This was a difficult watch as someone who uses Clojure
    I'm glad other people here in the comments pointed out the issue

    • @amasonofnewreno1060
      @amasonofnewreno1060 2 ปีที่แล้ว +10

      You are joking right? I was heavily impressed how quick he was on his feet.

  • @straightwhitewhale3533
    @straightwhitewhale3533 3 ปีที่แล้ว +31

    21:56 they'll send you to Siberia for that joke.

    • @TsodingDaily
      @TsodingDaily  3 ปีที่แล้ว +45

      I was born in Siberia lol

  • @eukaryote0
    @eukaryote0 3 ปีที่แล้ว +3

    Dude! You got a new haircut AND a new youtube channel. And I have been checking for the new videos on the old channel not knowing that your switched. Finally I found you )

  • @AntonioNoack
    @AntonioNoack 2 ปีที่แล้ว +4

    I am at 9:00 currently, but quickly wrote
    n=8
    x=5 // full queue length
    c=x // backup for x ^^
    while(n>=x){
    n-=x
    x*=2 // queue doubles
    }
    n = (n*c/x)|0 // find which one is at n-th place in a x-long queue
    in JavaScript, n is n, x is the number of names
    n will become the result
    pretty easy, and in-place :)

    • @JanilGarciaJr
      @JanilGarciaJr 2 ปีที่แล้ว

      Similar solution, in Scala. Instead of tracking the length of queue before doubling, it keeps track of the full size of the queue (lastElement), the size of the current section of the queue (queueSize) and the how many elements of each type there are in the current iteration.
      ```
      def nth(n: Long): String = {
      val names = Vector("Sheldon", "Leonard", "Penny", "Rajesh", "Howard")
      val index = n - 1
      def go(lastElement: Long, queueSize: Long, sectionSize: Long): Int =
      if (index < lastElement) {
      val midSectionPosition = queueSize - (lastElement - index)
      (midSectionPosition / sectionSize).toInt
      } else
      go(lastElement + queueSize * 2, queueSize * 2, sectionSize * 2)
      names(go(names.size, names.size, 1))
      }
      ```

    • @JanilGarciaJr
      @JanilGarciaJr 2 ปีที่แล้ว +2

      And this solution uses math to solve the problem:
      def nth(n: Long): String = {
      val names = Vector("Sheldon", "Leonard", "Penny", "Rajesh", "Howard")
      val index = n - 1
      val iteration = Math.ceil(Math.log(n / 5.0 + 1.0) / Math.log(2.0)).toInt
      val sectionSize = 1

  • @epgui
    @epgui 2 ปีที่แล้ว +3

    Step 1: Let the highest power of 2 that is less than or equal to 'n' be called 'a'.
    Step 2: Let (2*a - a) / (n - a) be called 'r'
    Step 3: 'r' is approx= index_of_answer / 5

    • @epgui
      @epgui 2 ปีที่แล้ว

      You can find the analytical answer more or less this way, but I haven't bothered to think through the indexing scheme. The general idea is that: n = (5 * Σ 2^i for i=0..a) + (n - a)

    • @ianliu88
      @ianliu88 2 ปีที่แล้ว +6

      ​@@epgui I have worked out the analytical solution to be:
      Let p = len(names), k = ceil(log2(n/p + 1)) - 1; then the name will be names[(n - p*(2**k-1) - 1) // 2**k]

  • @ElPikacupacabra
    @ElPikacupacabra ปีที่แล้ว +1

    The solution can be computed directly. There's no need for a queue algorithm. Probably not as educational for the average coder who's practicing data structures rather than math. ( If you're curious about the "mathy" solution, use the geometric series sum, and you should get that the n-th name is in the m-th run of length 5*2^(m+1), where m = ceil(log2(n/5 +1)) - 2, and you can work your way from there by computing first n - 5(2^(m+1) -1) and then dividing by 2^(m+1) to know where in that run you are.)

  • @beauteetmusculation8191
    @beauteetmusculation8191 3 ปีที่แล้ว +2

    Watched the Haskell version, it was actually great. Thanks!

  • @hanshofman
    @hanshofman 3 ปีที่แล้ว +7

    Emacs Org-Babel mode is a literate programming tool (aka. active document), which can embed multiple programming languages, inlcuding R, in one document. Another popular literate programming tool for statisticians is the Sweave document, which can embed only R code.

  • @qorzzz9252
    @qorzzz9252 3 ปีที่แล้ว +20

    Why would you simulate the process when there a constant time equation for this (which should be obvious).
    These sort of brute-force methods are exactly what these algorithm challenges are trying to teach you NOT to do. It is trying to train people to find patterns and identify the equation(s) that produce said pattern.

    • @awabqureshi814
      @awabqureshi814 2 ปีที่แล้ว +3

      cause it's fun

    • @wondays654
      @wondays654 2 ปีที่แล้ว

      Elaborate

    • @vikingthedude
      @vikingthedude 2 ปีที่แล้ว +2

      "which should be obvious" wouldn't that be a nice world to live in

  • @ivans3806
    @ivans3806 3 ปีที่แล้ว +9

    21:57 got me exhaling sharply out of my nose... "Lenin gay" LOL

  • @RecursiveTriforce
    @RecursiveTriforce 3 ปีที่แล้ว +9

    Here's a short "constant" time solution in python.
    def who_is_next(names, r):
    r -= 1
    l = len(names)

    # redundant but shortens while to 2 iterations max
    skip_n = r.bit_length() - l.bit_length() - 1
    if skip_n > 0:
    r = (r+l >> skip_n) - l

    while r >= l:
    r = r-l >> 1

    return names[r]

    • @JohnPeel_Dgby
      @JohnPeel_Dgby 2 ปีที่แล้ว

      Here's another Python example =)
      from math import log2, trunc
      from typing import List
      def who_is_next(names: List[str], n: int) -> str:
      duplicates = 2 ** trunc(log2((n - 1) / 5 + 1))
      return names[((n - 1) - ((duplicates - 1) * 5)) // duplicates]
      if __name__ == '__main__':
      assert who_is_next(['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard'], 1) == 'Sheldon'
      assert who_is_next(['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard'], 6) == 'Sheldon'
      assert who_is_next(['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard'], 52) == 'Penny'
      assert who_is_next(['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard'], 1802) == 'Penny'
      assert who_is_next(['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard'], 10010) == 'Howard'

    • @vikingthedude
      @vikingthedude 2 ปีที่แล้ว

      @@JohnPeel_Dgby would you please explain. Thanks!

    • @JohnPeel_Dgby
      @JohnPeel_Dgby ปีที่แล้ว

      @@vikingthedude Oof, this was a while ago.
      It looks like I was calculating the number of duplicates that would exist after n iterations, then just calculating the index of the name that would be.
      Not sure I could explain it better unless I rewatch the video =)

  • @alxjones
    @alxjones ปีที่แล้ว

    We just want the nth element of the sequence 0, 1, 2, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, ... where 0.1.2.3.4 are indices for a = ["Sheldon, "Leonard", ... ]
    The first group ends after 5, the second group ends after 5*3, the third group ends after 5*7, so the kth group ends after g(k) = 5*(2^k - 1). We can then consider a position n to be a pair (k, d), where k is the last group you passed and d is the distance you are into the next group. If you have this info, then d/2^k is the value at your position, and so a[d/2^k] is the solution.
    To get d, just take n - g(k). To get k, just solve n = g(k) and round down -- k = floor(log_2(1 + n/5)).
    Obviously, we can extend this to work with any list of names by using passing in a list of names and using the length of that list instead of hard-coding the number 5.
    As a python one-liner --- lambda a, n: a[ (n - len(a)*(2**floor(log2(1 + n/len(a))) - 1)) // 2**floor(log2(1 + n/len(a))) ]
    As more reasonable python ---
    ```
    def get_name_at_position(names, position):
    number_of_groups_passed = floor(log2(1 + position/len(names)))
    index_of_current_group = len(names)*(2**number_of_groups_passed - 1)
    position_in_current_group = position - index_of_current_group
    repetitions_per_name = 2**number_of_groups_passed
    return names[position_in_current_group // repetitions_per_name]
    ```

  • @dudusami89
    @dudusami89 3 ปีที่แล้ว +5

    pog FUNctional programming guys

  • @Bublerkin
    @Bublerkin หลายเดือนก่อน

    // O(1) solution in C#:
    static string GetNthPersonName(string[] names, int n) {
    int groupNumber = (int)(Math.Log((double)n / names.Length + 1) / Math.Log(2));
    return names[(int)((n - (int)(Math.Pow(2, groupNumber) - 1) * names.Length) / Math.Pow(2,groupNumber))]; }

  • @CodeWeaver
    @CodeWeaver 3 ปีที่แล้ว +6

    The infinite list solution is so lovely and elegant, but even if CodeWars allowed you to write in Haskell, I'm pretty sure it would time out trying to solve the third test case in the problem statement, much less anything bigger. You'd have to solve it the way you did in C++, or with some sort of closed form math.
    Mine, in Haskell, ended up looking a lot like ujjawal's below.
    Kinda curious how long it would take me to implement your C++ solution in Haskell without explicit recursion but still doing this kind of dynamic programming.

    • @JustMaiyak
      @JustMaiyak 3 ปีที่แล้ว +6

      As a matter of fact, Haskell handles the third case effortlessly. Give it a try and time it !

    • @CodeWeaver
      @CodeWeaver ปีที่แล้ว +4

      I cannot imagine why I thought this was not doable in Haskell. Even two years ago I should have been able to do this. And on revisiting this, and seeing I wrote such a blanket dumb comment, I'm posting _again_ to rectify this. (See my standalone additional comment).

  • @computationaltrinitarianism
    @computationaltrinitarianism 2 ปีที่แล้ว +2

    The problem on CodeWars has been removed for copyright infringement, lol.

    • @TsodingDaily
      @TsodingDaily  2 ปีที่แล้ว +4

      lol (Note to myself: don't mess with the Coca-Cola Company...)

    • @dolorsitametblue
      @dolorsitametblue ปีที่แล้ว

      @@TsodingDaily 'Cola' as a beverage is not copyrighted, it's either Warner Bros who copyrighted series of names from "The Big Bang Theory"?! LOOL.
      Or CodeWars removed it to avoid encouraging use of mass media references which COULD be copyrighted or otherwise problematic for the site.
      Edit: "Double Cola" is a real US company name🤦

  • @errelin1326
    @errelin1326 9 หลายเดือนก่อน

    I like how you mentioned RLE out of thin air. I just unable to do that. I'm jealous LOL

  • @jonseltzer321
    @jonseltzer321 3 ปีที่แล้ว +36

    Do you really start using a language without going to the official site at all? I see this sort of thing all the time. People start using libraries with zero effort to understand how something is supposed too be used. The result, every time, is disaster and then the developer claims the library (language) is bad. It's not the software, it's the user.

    • @funprog
      @funprog ปีที่แล้ว +1

      He forgot the first import of core, small problem

  • @thegeniusfool
    @thegeniusfool 3 ปีที่แล้ว +4

    Lenin Gay is a classic!

  • @nerdicon4822
    @nerdicon4822 2 ปีที่แล้ว +2

    i think you dont double the number each cola you just add one to the number of people of the same name
    like :
    a,b => b,a,a => a,a,b,b => a,b,b,a,a .. ..
    plz correct me if am wrong
    the problem was removed from codewars

  • @agustinpizarro
    @agustinpizarro 3 ปีที่แล้ว +1

    I subscribed when i saw that you have nim installed :)

    • @dolorsitametblue
      @dolorsitametblue ปีที่แล้ว +2

      It's sad that this install is from ~3 years ago and he used it on stream, maybe, 3 times?

  • @ahoyiski2468
    @ahoyiski2468 ปีที่แล้ว

    O(1) solution:
    m = floor(log_2(1 + n / 5))
    person_index = floor(n / 2^m + 5 • (2^m -1) / (2^(m + 1) - 2^m))

    • @ayaya-ayaya
      @ayaya-ayaya 11 หลายเดือนก่อน

      I thought about that too but I'm not sure if floating point errors won't be the killer here. Especially when log2 input is exactly a power of 2.

  • @cassandradawn780
    @cassandradawn780 2 ปีที่แล้ว +1

    wars* (in description)
    but the typo is funny lmao

  • @freedom_aint_free
    @freedom_aint_free ปีที่แล้ว

    Considering that just of person double at a time, and that it does occur instantaneously taking no time at all, we can write this problem as a recursive function:
    N = number of persons at a 'step' s (remember not a physics approach, the process takes no time!), the base case at step "s = 0" N = 5 persons, so
    N(s) = N(s0) + 1 (the constant one being because just one person gets doubled at a time)
    N(0) = N(s0)+1, initially (N at step 0) the number of persons is 5, so at the step 1:
    N(1) = N(0) + 1 = 5 + 1 = 6 (When Sheldon drunk that double-cola and him and his double goes to the end of the queue)
    N(2) = 6 + 1 = 7 (when Leonard does the same and him and his double goes to the end).
    N(3) = 7 + 1 = 8 (When Penny met the same fate of her colleagues)
    It's interesting to note that, in the video at 0:25 where the text is displayed, the queue seems to be reversed in relation to what the text actually says...

  • @pinniporker
    @pinniporker ปีที่แล้ว

    I attempted to implement this in a math formula and failed. Lesson learned: To solve a math problem, write a computer program that solves it for you like Tsoding did.

  • @casperes0912
    @casperes0912 2 ปีที่แล้ว +1

    Feel like there must be a constant time solution here

    • @ZapOKill
      @ZapOKill 2 ปีที่แล้ว

      there is... log & mod are your frinds

  • @siteted2013
    @siteted2013 11 หลายเดือนก่อน

    2:50 Does the queue really grow exponentially? I think that if we have +1 to size on each iteration, it grows linearly

    • @wchen2340
      @wchen2340 10 หลายเดือนก่อน

      it grows exponentially on every full pass of the queue. per drink its +1. i bet theres a neat one liner that uses both terms along with some modulo magic that solves for n but i just cant wrap my head around this right now :-/

  • @barrybrown4729
    @barrybrown4729 3 ปีที่แล้ว +2

    Why could it not be solved in haskell?

    • @agnishom
      @agnishom 3 ปีที่แล้ว +2

      It could. Codewars just wouldn't accept it

  • @colorkral4723
    @colorkral4723 ปีที่แล้ว

    getting a " λ> take 1 groups [: Out of memory" error
    when trying to display the groups in GHCI... code is identical... not sure why i cant seem to group = map (Group) 1 to names then display groups

    • @colorkral4723
      @colorkral4723 ปีที่แล้ว

      even gettiing rid of the array still produces the OOM error...
      module Main where
      data Group = Group
      { groupSize :: Int
      , groupName :: String
      } deriving Show
      main :: IO ()
      main = undefined
      baseNumber = 1
      name = "Sheldon2"
      group :: Group
      group = Group baseNumber name
      ----
      printing groups produces the error
      ----
      the hard part i'm having with haskell is getting a reliable environment set up

    • @colorkral4723
      @colorkral4723 ปีที่แล้ว

      group not groups

  • @ynav949
    @ynav949 ปีที่แล้ว +1

    i love zozing sessions

  • @halyph
    @halyph 10 หลายเดือนก่อน

    “Lenin Gay” is the best

  • @vladlu6362
    @vladlu6362 2 ปีที่แล้ว

    Well, you are given a list of names.
    So I'm guessing you just do this in Rust (I'm not proficient, sorry):
    fn main() {
    let names = vec![Sheldon, Leonard, Rajesh, Howard, Penny];
    who_is_next(names, 23)
    }
    fn who_is_next(names: Vec, pos:u32) -> String{
    names[pos % names.len()]
    }
    Right? If it's the one after that, you just have to check if it doesn't overflow. If it does overflow, it's just subtracting the overflow value by the length. This should only happen in one of len cases, so bigger the list the less times you have that condition happening.

  • @JannisAdmek
    @JannisAdmek ปีที่แล้ว

    doube and give it to the next person

  • @Rene-tu3fc
    @Rene-tu3fc 3 ปีที่แล้ว +1

    33:54 is priceless. I wholeheartedly agree with your take

  • @s1gm4_4c4d3my
    @s1gm4_4c4d3my 3 ปีที่แล้ว

    Fun fuct: I can run minecraft with openjdk

  • @viniciusataidedealbuquerqu2837
    @viniciusataidedealbuquerqu2837 2 ปีที่แล้ว +4

    Lenin gay ROFL

  • @Firstorder66
    @Firstorder66 8 หลายเดือนก่อน

    infinite data structure just store data on a file

  • @CodeWeaver
    @CodeWeaver ปีที่แล้ว +1

    I'm revisiting this. I can't believe i ever thought this wasn't sensibly done in Haskell. I could do this in Haskell, Racket, Clojure, heck, I could do this in C# Linq with some extra jiggerypokery. Anything where there's either a lazy list, or the ability to fake one, which is everywhere.
    names = ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard" ]
    startingQueue = zip names $ repeat (1::Integer)
    foreverColas startState = allColas
    where
    allColas = startState ++ map (\(name,c) -> (name,2*c)) allColas
    accumulatedColas = scanl1 (\(_,acc_c) (name,c) -> (name,acc_c+c))
    nthCola [] _ = undefined
    nthCola qs n = fst . head . dropWhile (\(_,c) -> n>c) $ qs
    Not only solveable, but without using any recursion (except for, by data structure, the tying-the-knot of generating the infinite queue... that's it).
    _Given_ that Tsoding even pulled up the way to do lazy lists by doing the fib example, I'm a little surprised he declared it unsolvable. At this point.
    I don't know what the test case was anymore that I thought was stupidly too big to solve, but seeing as this runs in logarithmic time because of the doubling of the counts, I put in a billion and it solved almost instantly.
    "Penny"
    At 5 quadrillion, I get
    "Rajesh"

    • @CodeWeaver
      @CodeWeaver ปีที่แล้ว

      Evaluated with
      nthCola (accumulatedColas . foreverColas $ startingQueue) 5000000000000000
      as I forgot I left my main out.

  • @gagansrai8137
    @gagansrai8137 3 ปีที่แล้ว +5

    lenin gay hahaa

  • @azai.mp4
    @azai.mp4 2 ปีที่แล้ว

    Since people are posting their solutions, here's mine (Python 3.8):
    who_is_next=w=lambda n,r:n[r-1]if r>1)

  • @Hemigoblin
    @Hemigoblin 2 ปีที่แล้ว

    53:51 I wish I had another like.

  • @ori61511
    @ori61511 3 ปีที่แล้ว

    very cool

  • @chrisalexthomas
    @chrisalexthomas 3 ปีที่แล้ว +6

    lol @ codeworse

  • @telnobynoyator_6183
    @telnobynoyator_6183 2 ปีที่แล้ว

    CodeWorse x)

  • @Корнійчук-в4п
    @Корнійчук-в4п 2 ปีที่แล้ว +2

    lenin gay????

  • @fr3fou
    @fr3fou 3 ปีที่แล้ว

    thumbnail mirrored monkaS

  • @JamesJones-zt2yx
    @JamesJones-zt2yx 3 ปีที่แล้ว +2

    Do all the Sheldons replicate, or just the one who drinks the double cola?

    • @ghpu
      @ghpu 3 ปีที่แล้ว

      Just the first one, but then it's the turn of the second one so in the end they all double (if n is large enough).

    • @stewartzayat7526
      @stewartzayat7526 2 ปีที่แล้ว

      @@ghpu even if n is large enough, still only about half of them got the chance to double

  • @defini7
    @defini7 ปีที่แล้ว

    21:58 kinda sus

  • @GenesisAkaG
    @GenesisAkaG 2 ปีที่แล้ว

    Isn't this solvable with constant space? Just
    for (a = 1; a*queue.length < n ;a*=2) {n -= queue.length*a}
    return queue[Math.ceil(2*n/a*queue.length)]

  • @dashl5069
    @dashl5069 3 ปีที่แล้ว +5

    was the problem with the clojure solution just that you deleted the (ns cola.core) line?

    • @LucasVieira42
      @LucasVieira42 3 ปีที่แล้ว +2

      I was like, damn he ctrl a + ctrl v too fast, he will never find out

    • @DrewIsFail
      @DrewIsFail 3 ปีที่แล้ว +1

      Yes, that's what the error message was telling him.

  • @BigBeesNase
    @BigBeesNase 3 ปีที่แล้ว +2

    Using Leiningen is the right way to go about Clojure. Just put the lein.bat in your path. I personally use Clojure extension for vs code to support REPL based development which starts the REPL in the background and then everything feels like the way you do with Haskell or maybe better as I don't have to switch to REPL. You can evaluate the code as you go to see the result.
    P.S. Haskel like version in Clojure - gist.github.com/Vikasg7/fc3cbe491822da00f250aeb326deb366