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
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.
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.
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
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 :)
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)) } ```
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
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 )
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.
@@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 =)
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.
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.)
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.
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
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)
@@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]
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.
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).
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] ```
@@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🤦
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
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
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...
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.
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 :-/
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.
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
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
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"
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
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
Totally agree 👍 great videos . Hope to discuss ocaml method to...
"Seems to be working, seems to be twerking" > words to live by. Amazing session as per usual 🤘
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.
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
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...
I was like screaming at the monitor :(
@@TsodingDailyThis is a classic programming moment
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?
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.
This was a 1 2 3 code session btw. 1 problem, 2 Programming Paradigm and 3 languages. Very Naice!!!
21:56 they'll send you to Siberia for that joke.
I was born in Siberia lol
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!
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
Don't take a haskell course. Just learn you a haskell and miso on the yesod
This was a difficult watch as someone who uses Clojure
I'm glad other people here in the comments pointed out the issue
You are joking right? I was heavily impressed how quick he was on his feet.
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 :)
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))
}
```
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
21:57 got me exhaling sharply out of my nose... "Lenin gay" LOL
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 )
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.
He forgot the first import of core, small problem
JavaScript developers are literally this, they use a thousand libraries they how to write by themselves, they’re not good developers
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]
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'
@@Dgby714 would you please explain. Thanks!
@@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 =)
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.
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.)
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.
cause it's fun
Elaborate
"which should be obvious" wouldn't that be a nice world to live in
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
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)
@@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]
Watched the Haskell version, it was actually great. Thanks!
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.
As a matter of fact, Haskell handles the third case effortlessly. Give it a try and time it !
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).
@@CodeWeaverwhy were u revisiting after a 2 year gap
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]
```
// 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))]; }
The problem on CodeWars has been removed for copyright infringement, lol.
lol (Note to myself: don't mess with the Coca-Cola Company...)
@@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🤦
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
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
Actually .... - 🤓
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...
pog FUNctional programming guys
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))
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.
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.
I like how you mentioned RLE out of thin air. I just unable to do that. I'm jealous LOL
2:50 Does the queue really grow exponentially? I think that if we have +1 to size on each iteration, it grows linearly
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 :-/
Feel like there must be a constant time solution here
there is... log & mod are your frinds
Lenin Gay is a classic!
Why could it not be solved in haskell?
It could. Codewars just wouldn't accept it
wars* (in description)
but the typo is funny lmao
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.
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
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
group not groups
33:54 is priceless. I wholeheartedly agree with your take
I subscribed when i saw that you have nim installed :)
It's sad that this install is from ~3 years ago and he used it on stream, maybe, 3 times?
“Lenin Gay” is the best
i love zozing sessions
Do all the Sheldons replicate, or just the one who drinks the double cola?
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).
@@ghpu even if n is large enough, still only about half of them got the chance to double
doube and give it to the next person
infinite data structure just store data on a file
Fun fuct: I can run minecraft with openjdk
53:51 I wish I had another like.
thumbnail mirrored monkaS
1:20 lol
21:58 kinda sus
lol @ codeworse
lenin gay hahaa
Lenin gay ROFL
very cool
lenin gay????
CodeWorse x)
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"
Evaluated with
nthCola (accumulatedColas . foreverColas $ startingQueue) 5000000000000000
as I forgot I left my main out.
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)
was the problem with the clojure solution just that you deleted the (ns cola.core) line?
I was like, damn he ctrl a + ctrl v too fast, he will never find out
Yes, that's what the error message was telling him.
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
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)]