dimanche 6 décembre 2015

Elm - list of random numbers without duplicates

I am making a game in elm and trying to randomly place N evil robots on a grid with ROWS x COLS cells.

What I would like is a List (Int, Int) pairs that specifies where to place the N robots.

I can make a List of coordinate pairs with

makeGrid : Seed -> List (Int, Int)
makeGrid seed = 
  let gen = list n <| pair (int 0 rows) (int 0 cols)
in 
  fst (generate gen seed)

That's fine. But if I want to generate a list of unique pairs?

Should I do the imperative solution where I keep a Set of my things and loop through adding until I have enough?

Maybe something like this (probably wrong, didn't check it in the REPL):

makeN : Int -> Seed -> (List (Int, Int), Seed)
makeN n seed = 
  let gen = list n <| pair (int 0 rows) (int 0 cols)
in 
  generate gen seed

makeGrid : List(Int, Int) -> Seed -> Int -> List (Int, Int)
makeGrid partial seed n =
  case of List.length partial 
    n -> partial
    current -> 
      let (new_elems, new_seed) = makeN (n - current) seed
      makeGrid Set.toList (Set.fromList <| append partial new_elems) new_seed n

This feels off. I've thought of 3 alternatives:

  1. Make my grid a list of ROWS * COLS coordinate pairs with type List (Int, Int), then shuffle it, and take the first N pairs in the list to place my robots on. This seems very concise and clean, but inefficient/bad if the number of unique points I need is much smaller than my grid, and if my grid is big (as Fisher-Yates is O(n log(n)) I think).

  2. Use something like this package to sample from my grid without replacement, but I need to change my grid into an Array and it looks like it does a lot of splitting and splicing Array operations, which look costly.

  3. Use the JS FFI to implement this in a 4 line JS loop.

None of these solutions feel good, is there something I'm missing? I'm probably going to just change the game mechanics to that each cell has a probability P of having a robot on it, so that it's simpler to implement.




Aucun commentaire:

Enregistrer un commentaire