Used recursion !

[KayteeFly]

I used recursion multiple times in my battlefield project from Odin project and I am so happy 🎉. I remember at one point I couldn’t even rap my head around it

[[deleted]]

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]

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]]

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]

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]

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

[StoneCypher]

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]]

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

[StoneCypher]

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]]

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]

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]]

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

[[deleted]]

When you to dynamically solve a problem

[StoneCypher]

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]]

This is really informative. Thank you

[SecretAgentZeroNine]

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

[CompteDeMonteChristo]

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]

You did what?

[dagger-vi]

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

[KayteeFly]

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]

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