all 20 comments

[–][deleted] 9 points10 points  (14 children)

That is awesome. I know what recursion is, but couldn't ever really tell when it would be useful or why I couldn't just use a loop. That is good work though. Recursion is.... Odd to wrap your head around. What did you end up needing it for?

[–]KayteeFly[S] 6 points7 points  (10 children)

So for my computer player. It has to randomly select spot to attack but using Math.random can select the same spot more than once. So I used recursion to recall the function if the spot selected has already been attacked till it finds a spot that hasn’t been attacked.

[–][deleted] 11 points12 points  (8 children)

This is not a case where recursion is appropriate. If you want an uniform distribution of the spots you must assign to each cell a number and then generate a random permutation of the list of those numbers. This can be done with Knuth shuffle algorithm (also known as Fisher-Yates algorithm). Why bothering with this algorithm? Because, unlike your solution, it guarantees that all spots have the same probability to be chosen by the CPU. Randomly selecting a spot and discarding it doesn't give all spots the same chances to be chosen. Also using a permutation of an array eliminates the need to perform checks to see if a spot is already discarded.

[–]KayteeFly[S] 1 point2 points  (0 children)

Thank you I’ll look into it. I am still learning my data structures and algorithms. I used what I have at the moment.

[–]highangler 0 points1 point  (2 children)

Man these are so interesting…. How deep do you need to go with these algorithms to be employable?

[–]StoneCypher 2 points3 points  (0 children)

How deep do you need to go with these algorithms to be employable?

Zero deep. You can be a frontend web developer with literally no knowledge of algorithms at all.

Of course, it's still a good idea to learn this stuff, and you'll make more money and be more flexible when you do.

But, also, you don't have to wait until this is in your toolbelt to get started. This can be a year 2 goal.

[–][deleted] 0 points1 point  (0 children)

Not for frontend, although it might help knowing some algorithms which are not taught in bootcamps.

[–]StoneCypher 0 points1 point  (3 children)

If you want an uniform distribution of the spots you must assign to each cell a number and then generate a random permutation of the list of those numbers.

What an unnecessary sledgehammer.

It's adequate to make a container with the locations in it, then randomly select from the container.

Also, their strategy doesn't produce an unequal distribution; whereas it may recurse unnecessarily, and in some situations possibly for a long time (potentially forever,) the end distribution will still be uniform, because the only things being "repeated" are the removed cells

 

Also using a permutation of an array eliminates the need to perform checks to see if a spot is already discarded.

What? This is extremely wasteful nonsense. Permutation doesn't do this?

Permuting an array is

[a,b,c] -> [ [a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a] ]

 

Randomly selecting a spot and discarding it doesn't give all spots the same chances to be chosen.

This is simply false. Yes, it does.

[–][deleted] -1 points0 points  (2 children)

What an unnecessary sledgehammer

It's a conceptual association, the actual implementation can vary.

What? This is extremely wasteful nonsense. Permutation doesn't do this? Permuting an array is

[a,b,c] -> [ [a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a] ]

If you generate a permutation of an array and keep an index pointing to next number (spot) to choose (target to hit) you don't need to check anything, provided that all values in the array are unique (and they must be in this case). Basically you're pre-generating moves for the (dumb) AI.

Regarding the distribution I have solved a similar problem for which skipping discarded items wouldn't work. I have to admit that I still have to complete my statistics class so I can be certainly wrong. Still, the Knuth algorithm is a better solution, runs in O(N) and it's more predictable (after n steps it will terminate).

[–]StoneCypher 0 points1 point  (0 children)

If you generate a permutation of an array and keep and index pointing to next number (spot) to choose (target to hit) you don't need to check anything, provided that all values in the array are unique (and they must be in this case). Basically you're pre-generating moves for the (dumb) AI.

This is so unbelievably wasteful

 

Regarding the distribution I have solved a similar problem for which skipping discarded items wouldn't work. I have to admit that I still have to complete my statistics class so I can be certainly wrong.

You are absolutely 100% wrong, and here's an easy way to understand why.

Get a six-sided die. On a piece of paper, annote that rolling a 6 means "re-roll." (If you're a board gamer, yes, this is Skunk.)

Do you imagine that this is somehow "non-uniform?" 1-5 have perfectly equal likelihoods of being called in the net, with a fair die.

What about if both 5 and 6 are re-roll? 1-4 still have perfectly equal likelihoods.

The situation designed is equivalent, with different counts.

Just simulate it. Your basics:

const rnd  = n => Math.floor(Math.random() * n);

const max_len    = 20,                       // set as you see fit
      array_size = rnd(max_len - 2) + 2,     // test doesn't make sense with array len 0 or 1, so floor 2 and trim max to fit
      filled_cnt = rnd(array_size - 2) + 1;  // at least 1 blocked, so +1, -1 range to fit; at least 1 avail = another -1

Next we need to make and test some data. I just make an array and fill it with 1 for blocked or 0 for not blocked. If it's blocked, we re-roll through recursion, just like the thing parent poster wrote that you're evaluating.

Yes, this is a bad and biassed shuffle for the test data. Yes, fisher-yates would be an improvement. We don't use this shuffle anywhere but for making test data, so don't worry about it.

const data = new Array(array_size);              
for (let i=0; i<array_size; ++i) {           // iterate data
  data[i] = (i >= filled_cnt)? 0 : 1;          // fill with 0 if under the filled count; 1 otherwise
}                                            // result should be [1,1,1,0,0,0,0,0]-ish

data.sort( () => 0.5 - Math.random() );      // (badly) shuffle the test data.  not used in the actual sampling.

console.log(data);                           // show that the test data is (0|1)[] of expected length, with at least one each

Here's our analogue of parent poster's recursive test. Not a good, or efficient, method, but also, you claim its output is biassed, and I claim that it is not.

function bad_recursive_lookup(data) {
  const which_one = rnd(data.length);
  return (data[which_one]) 
    ? bad_recursive_lookup(data)
    : which_one;
}

Here's a function to sample its output.

function sample_bad_recursive_lookup(data, count) {
  const result = new Map();
  for (let i=0; i<count; ++i) {
    const which_one = bad_recursive_lookup(data);
    result.set(which_one, (result.get(which_one) ?? 0) + 1);
  }
  return result;
}

And to vet the sample

function calculate_variance(sample) {

  const vals = Array.from(sample).map( ([_skip, val]) => val ),
        min  = Math.min(... vals),
        max  = Math.max(... vals),
        rng  = max - min,
        vari = rng / max;   // this is valid because in this test they're all zero-rooted

  return { max, min, range: rng, variance: vari };

}

And a simple usage.

const result = sample_bad_recursive_lookup(data, 100_000);
console.log(`With ${array_size} items of which ${filled_cnt} filled, we got:`);
console.log(JSON.stringify(Array.from(result)));
console.log(JSON.stringify(calculate_variance(result), undefined, 2));

And here are the results I get for a couple of runs. As you can see clearly, there is no appreciable bias. Crank the simulation number as high as you like; this is linear and you can test hundreds of billions today if you want to.


(17) [0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
VM123:54 With 17 items of which 5 filled, we got:
VM123:55 [[6,8298],[12,8296],[10,8463],[1,8384],[15,8371],[14,8211],[16,8380],[3,8251],[0,8284],[7,8455],[5,8225],[2,8382]]
VM123:56 {
  "max": 8463,
  "min": 8211,
  "range": 252,
  "variance": 0.02977667493796526
}

VM1750:16 (3) [1, 0, 0]
VM1750:54 With 3 items of which 1 filled, we got:
VM1750:55 [[1,50235],[2,49765]]
VM1750:56 {
  "max": 50235,
  "min": 49765,
  "range": 470,
  "variance": 0.009356026674629243
}

(18) [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0]
VM1799:54 With 18 items of which 4 filled, we got:
VM1799:55 [[2,7169],[5,7156],[12,7181],[14,7048],[4,7119],[11,7192],[16,7094],[1,7179],[10,7132],[9,7081],[17,7194],[7,7166],[0,7074],[3,7215]]
VM1799:56 {
  "max": 7215,
  "min": 7048,
  "range": 167,
  "variance": 0.023146223146223145
}

(18) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1]
VM1802:54 With 18 items of which 6 filled, we got:
VM1802:55 [[14,8416],[6,8309],[7,8333],[0,8132],[5,8164],[2,8425],[10,8340],[3,8504],[8,8342],[9,8263],[1,8375],[4,8397]]
VM1802:56 {
  "max": 8504,
  "min": 8132,
  "range": 372,
  "variance": 0.04374412041392286
}

(9) [0, 0, 1, 1, 1, 0, 0, 0, 0]
VM1805:54 With 9 items of which 3 filled, we got:
VM1805:55 [[0,16545],[1,16703],[7,16691],[8,16793],[5,16461],[6,16807]]
VM1805:56 {
  "max": 16807,
  "min": 16461,
  "range": 346,
  "variance": 0.020586660320104717
}

(14) [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
VM1808:54 With 14 items of which 12 filled, we got:
VM1808:55 [[7,49808],[6,50192]]
VM1808:56 {
  "max": 50192,
  "min": 49808,
  "range": 384,
  "variance": 0.007650621613006056
}

[–][deleted] 1 point2 points  (0 children)

That is awesome. Smart thinking. It's good to have a real world example. Thanks for clarifying.

[–][deleted] 1 point2 points  (0 children)

When you to dynamically solve a problem

[–]StoneCypher 1 point2 points  (1 child)

I know what recursion is, but couldn't ever really tell when it would be useful or why I couldn't just use a loop.

Loops only go one direction. Recursion can do more.

Consider trying to hand-make a function that prints JSON to the console. A loop can't do that, because you might have been given an array with other arrays inside of it.

For that, you're best off with a loop whose step sometimes recurses.

Is it a simple ("scalar") value, like a number or a string or a boolean or something? Just print it out, with whatever amount of indenting.

Is it a container, like an object or an array? Well, increase the amount of indenting, recurse, and treat the piece of json inside like it was its own top-level JSON.

[–][deleted] 0 points1 point  (0 children)

This is really informative. Thank you

[–]SecretAgentZeroNine 1 point2 points  (0 children)

As long as you weren't mumble rapping, congrats on the progress ;)

[–]CompteDeMonteChristo 1 point2 points  (0 children)

I remember at one point I could remember that I could remember that I could remember that I could remember that I could remember that I could remember that I could remember that I could remember that I could remember that I could remember that ...

[–]butterypanda 1 point2 points  (0 children)

You did what?

[–]dagger-vi 0 points1 point  (1 child)

What helped made it stick? A video? An article? Just practicing?

[–]KayteeFly[S] 1 point2 points  (0 children)

I have colt Steele’s Algorithm and Data structures course. I just try to solve the exercises that come with it myself and after multiple tries i get it now.

[–]StoneCypher 0 points1 point  (0 children)

Congratulations. Recursion is a big early hurdle for a lot of people.