StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My idea is to have a queue of cards to be played. The queue is shuffled and then played one at a time until emptied. As each card is being played, if the card was played less than m turns ago add it to the end of the queue and pick the next card. Once the queue is emptied it can be filled again and reshuffled. An array can be used to keep track of what turn a card was last played at. This runs O(1) per song on average.</p> <p>Here's my solution in F#.</p> <pre><code>let deal (deck : _[]) m = let played = Array.create (deck.Length) (-m) let rec subDeal (cards : Queue<_>) i = seq { if cards.Count = 0 then yield! subDeal (shuffledQueue deck) i else let card = cards.Dequeue() if i - played.[card] > m then played.[card] <- i yield card else cards.Enqueue card yield! subDeal cards (i + 1) } subDeal (shuffledQueue deck) 1 </code></pre> <p>Some test data for a deal of 0 .. 7 with m = 4.</p> <pre><code>[|3; 1; 4; 0; 2; 6; 5; 4; 0; 2; 3; 6; 1; 5; 0; 1; 2; 6; 4; 3; 5; 2; 0; 6; 3; 4; 5; 1; 6; 0; 3; 2; 5; 4; 1; 3; 5; 2; 0; 6; 1; 4; 2; 5; 3; 4; 0; 1; 6; 5; 2; 4; 3; 0; 6; 1; 3; 5; 6; 2; 4; 1; 0; 5; 2; 6; 3; 1; 4; 0; 2; 6; 1; 4; 0; 5; 3; 2; 1; 0; 5; 6; 4; 3; 2; 1; 3; 0; 5; 6; 4; 3; 1; 2; 0; 5; 6; 4; 3; 0; ...|] // card number and the number of occurrences of said card [|(3, 286); (6, 286); (5, 285); (0, 286); (1, 285); (4, 286); (2, 286)|] // longest time before each card is repeated [|11; 11; 11; 11; 12; 11; 11|] </code></pre> <p>Full test program.</p> <pre><code>open System open System.Collections.Generic let rnd = new Random() let shuffle cards = let swap (a: _[]) x y = let tmp = a.[x] a.[x] <- a.[y] a.[y] <- tmp Array.iteri (fun i _ -> swap cards i (rnd.Next(i, Array.length cards))) cards cards let shuffledQueue cards = let queue = new Queue<_>() cards |> shuffle |> Array.iter (fun x -> queue.Enqueue x) queue let deal (deck : _[]) m = let played = Array.create (deck.Length) (-m) let rec subDeal (cards : Queue<_>) i = seq { if cards.Count = 0 then yield! subDeal (shuffledQueue deck) i else let card = cards.Dequeue() if i - played.[card] > m then played.[card] <- i yield card else cards.Enqueue card yield! subDeal cards (i + 1) } subDeal (shuffledQueue deck) 1 let size = 7 let deck = Array.init size (fun i -> i) let cards = deal deck 4 let getMaxWait seq value = Seq.fold (fun (last, count) test -> if test = value then (0, count) else (last + 1, max (last+1) count) ) (0, 0) seq |> snd let test = cards |> Seq.take 2000 test |> Seq.take 200 |> Seq.toArray |> printfn "%A" test |> Seq.countBy (fun x -> x) |> Seq.toArray |> printfn "%A" deck |> Seq.map (fun x -> getMaxWait test x) |> Seq.toArray |> printfn "%A" Console.ReadLine() |> ignore </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload