use the following search parameters to narrow your results:
e.g. subreddit:pics site:imgur.com dog
subreddit:pics site:imgur.com dog
advanced search: by author, sub...
~1 user here now
Links:
My old programming problem
submitted 1 year ago by fschmidt from self.programming
view the rest of the comments →
[–]trident765 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 0 fun2 insightful - 1 fun - 1 year ago (6 children)
This problem has no solution. The cards added to the top of the deck makes the shuffling of one size deck too different from the other. So there is no pattern that can be observed and exploited.
Of course, I am sure a Silicon Valley scum will be able to solve this by applying some bizarre mathematical trick. But knowledge of these mathematical tricks has little use in the real world.
I had a friend who was good at solving these types of problems but he a dumbass when it came to common sense. First he lost a bunch of money by investing in obscure cryptocurrencies. And when psychopaths took over my department at work he was completely oblivious to what was happening. He embraced liberalism with all his heart, and believed that those who spread disinfo about the vaccine are a threat to society.
[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 0 fun2 insightful - 1 fun - 1 year ago (5 children)
Of course there is a solution. And while a little math is needed, the core insight isn't mathematical.
This problem served me well while western culture was still sane. I got good programmers by using it. But it is no longer useful because the main issue with programmers now is values, not out-of-the-box thinking.
[–]trident765 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - 1 year ago (3 children)
Ok I solved it by recognizing that the result of shuffling n times is the mapping indices to perform n shuffles. So I precomputed the first n shuffles (I used 400000 for n), and then bulk shuffled the fast way that I just described until I got a result that was in the precomputed shuffles.
[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - 1 year ago (2 children)
What answer did you get? If the answer is 400001 then how would you find it?
[–]trident765 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - 1 year ago (1 child)
I got 5812104600.
If the answer is 400001 then how would you find it?
After the 2nd bulk shuffle the deck would be at the 800000th shuffle. If the answer is 400001, then the 800000th shuffle will be identical to the 399999th shuffle, so I will find the 800000th (399999th) shuffle in the precomputed table, and then this would tell me to subtract 800000 - 399999 = 400001.
Here is my code:
https://pastebin.com/YTjL9d1i
[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - 1 year ago (0 children)
I see. My solution is different. Each card follows some path through the deck and returns to its original position. Each card in a path takes the same number of shuffles to return to its original position. So the solution is the least common multiple of the lengths of all the paths in the deck.
local Luan = require "luan:Luan.luan" local error = Luan.error local range = Luan.range or error() local Math = require "luan:Math.luan" local min = Math.min or error() local Number = require "luan:Number.luan" local long = Number.long or error() local Io = require "luan:Io.luan" local print = Io.print or error() local function lcm(x,y) local rtn = x while rtn % y ~= 0 do rtn = long(rtn + x) end return rtn end local function shuffles(n_cards,i_cut) local map = {} do local n = min( i_cut, n_cards - i_cut ) for i in range( 0, n - 1 ) do local j = n_cards - 2*i map[ i_cut - i ] = j map[ n_cards - i ] = j - 1 end if n == i_cut then for i in range( 1, n_cards - 2*i_cut ) do map[ i_cut + i ] = i end else for i in range( 1, i_cut - n ) do map[i] = i end end end local a = {} for i in range(1,n_cards) do a[i] = true end local rtn = 1 for i in range(1,n_cards) do if a[i] then local n = 0 local j = i while a[j] do a[j] = false n = n + 1 j = map[j] end rtn = lcm(rtn,n) end end return rtn end print( shuffles(1002,101) )
view the rest of the comments →
[–]trident765 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 0 fun2 insightful - 1 fun - (6 children)
[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 0 fun2 insightful - 1 fun - (5 children)
[–]trident765 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - (3 children)
[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - (2 children)
[–]trident765 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - (1 child)
[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 0 fun3 insightful - 1 fun - (0 children)