Need explanation on a coding challenge

[abdulrahmanmhdanas]

I need to understand and absorb this challenge on codewars that is called Playing on a chessboard.
I tried to understand it but I could not understand it.
Here is the link to challenge if can help me:

Training on Playing on a chessboard

[m_hutley]

What have you tried, and what are you having trouble understanding?

[abdulrahmanmhdanas]

The challenge itself.

@abdulrahmanmhdanas

but I could not understand it.

I did not understand what the challenge want us to do !!

[m_hutley]

The challenge wants you to code a function, game, that takes one parameter N, and give the summed total value of an array NxN, where the value of each cell is defined by the function they have outlined in the description.

Challenge 1: What is the generalized form of the value of a cell? (If I am at Row 4, Column 12, what value goes in that cell, and why?)
Challenge 2: How do you add all of those fractions up?
Challenge 3: How do you simplify the resulting fraction at the end?

[m_hutley]

Or the secret Challenge 4: What is the generalized pattern of the answers to game(n)? (yes, there is one…)
(Note: Challenge 4 trivializes the actual point of the coding. So only do that one if you’re a math(s) nerd.)

[dresden_phoenix]

It seems to me, the challenge is asking you to write a function that will take single parameter , called ‘n’. This function will calculate the SUM of the values of a virtual ‘n by n’ grid ; the value of each cell in the grid is in itself calculated by the position of the celling the grid (hint : value= col/(col+row)). Because the value of each cell is a fraction they want the function to return an array where the first number is the numerator and the second the denominator–and you can skip the second number if it’s 1. (eg.: .5 = [1,2]; .75 = [3,4]; 3 =[3])

thats the gist of it. As far as "generalized solution go , think of it this way. There several ways to write fuctions the willl solve this challenge. you could hard code a grid (please dont!) but that would limit your function to the numbers you have painstakingly coded.

you could brute force it, iterating over each position and doing the division for each cell and keeping a running tally

you could do this recursively, utilizing the answer from the previous row to help you get the next one an summing those up

or you come up with a generalized formula rather than iterating or recursing though the cells.

hint ( note the sum of the numerators would be the same for each row: 1+2+3+…n; so rather than iterate that sum you could say numerator =( n*n+n)/2 … this gives an answerwith a bigO(1) , or what it’s usually referred to as constant time)

hope that helps

[m_hutley]

@dresden_phoenix

hint ( note the sum of the numerators would be the same for each row: 1+2+3+…n; so rather than iterate that sum you could say numerator =( n*n+n)/2

Woooooah there.
you can only sum the numerators if the denominators are the same… 1/2+4/5 is NOT 5/something! (Ex: There is no other term in the array with a denominator of 2 except the cell at 1,1.)

[m_hutley]

It’s been a week since the last post in this thread, so I thought i’d come back and toss out some of my thoughts, patterns, and how I came to a one-line solution.

Needless to say, this is a MAJOR spoiler for the coding challenge, and so i will be using spoiler tags judiciously throughout, especially when we get to what i dubbed “Challenge 4”.

The Naive Approach

So my first thought when looking at this problem was Challenge #1. Because the first thing I wanted to do was to get some code down that would ‘solve’ the problem, pretty much as I assume the challenge expects people to approach it - not simplified, no clever theories, just the brute force “give me the answer.”

So I need a matrix. The challenge tells me it’s an N x N matrix. Simple enough:

for(let i = 0; i < N; i++) {
  for(let j = 0; j < N; j++) {
   //Hmm... what goes here.
 }
}

(Before people cringe and hiss at me, this was a first pass, so a for loop is fine.)

But I need to figure out what goes into the middle bit. How are the cells of this matrix filled?

Challenge #1

Right, let’s take a look at the description of the challenge.

On the first row at the *bottom* we put numbers:
`1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9`
On row 2 (2nd row from the bottom) we have:
`1/3, 2/4, 3/5, 4/6, 5/7, 6/8, 7/9, 8/10`
On row 3:
`1/4, 2/5, 3/6, 4/7, 5/8, 6/9, 7/10, 8/11`
until last row:
`1/9, 2/10, 3/11, 4/12, 5/13, 6/14, 7/15, 8/16`

(The example is using N=8, so the ‘last’ row is row 8.)

What’s common here?
Well the numerators are always the same. 1,2,3…N.
My inner loop takes care of that. the numerator for a given cell is j.
But what about the denominators?
On row 1, the denominators start at 2, and go up by 1 until we get to 9.
On row 2, the denominators start at 3, and go up by 1 until we get to 10.
You should probably be able to see a pattern here, but perhaps it would be more clear if I wrote it this way:
For row 1, the denominators are (1+1), (1+2), (1+3)…(1+N)
For row 2, the denominators are (2+1), (2+2), (2+3)…(2+N)
So,
(Challenge 1 answer:)

For any given cell, [r,c] (which I out of habit called [i,j]), the numerator is c, and the denominator is r+c.

let matrix = [];
for(let i = 0; i < N; i++) {
  matrix[i] = [];
  for(let j = 0; j < N; j++) {
   matrix[i][j] = {"num":j, "denom": i+j}
 }
}

Challenge 2

So now we’ve got our matrix. How do we add them up?
The simplest way would be to convert them all to floats, sum the whole thing, and reconvert back to a fraction. It does potentially allow for rounding errors, though, so we would need to be careful. Alternatively, we could convert all the values to a common denominator, and then summing the numerators is trivial.
How do we get the denominators to be common? Well, the simplest/naivest way is going to be multiplying all of the denominators together. We know our denominators start at 2, and we know from Challenge #1 they go up to being the value in the ‘last’ cell of the matrix, which is N+N, so we can find that easily enough: (I’m going to get a little fancier this time, to avoid a for loop before some code grouse comes after me. You can do it with a for loop too.)

let common = Array.from({length: N+N}, (_,i) => i+2).reduce((a,c) => a*c,1);

Note: You will find this number gets very large very quickly. It’s not recommended for large values of N. But it’s the naive way of finding a common denominator. There are definitely better methods, which I highly recommend. Again, this was first-blush looking.

With a common denominator, you can convert any existing fraction to the common denominator by taking the common denominator, dividing it by the current denominator, and then multiplying the result by the numerator.

So lets say your common denominator was 120, and you’re currently trying to convert 2/3 into that denominator.
120 / 3 = 40.
2 * 40 = 80,
so the resulting properly converted fraction is 80/120.

Once every fraction in the matrix is converted, you can add all of the numerators up, stick it over the common denominator, and there’s your unsimplified answer.

So at this point, we have a naive version of the code:

Code notes: At this point, I stopped putting the denominator in the cells, because I was making all of the cells a common denominator; the only information that was different was the numerators.
Again, i’m using Array functions, you can do it with looping.

let matrix = [];
let common = Array.from({length: N+N}, (_,i) => i+2).reduce((a,c) => a*c,1);
for(let i = 0; i < N; i++) {
  matrix[i] = [];
  for(let j = 0; j < N; j++) {
   matrix[i][j] = (j+1)*(common/((i+1)+(j+1)));
 }
}
//Now, sum them.
let totalnum = matrix.reduce((a,c) => a+c.reduce((ia,ic) => ia+ic,0),0);

Challenge 3

So now we’ve got an unsimplified fraction, with a very large numerator. How can we simplify it?
We need to find the Greatest Common Divisor between the numerator and denominator.
This part gets a little bit math-y, but the long and the short of it is the following function:

let d = common;
let n = totalnum;
while(d) {
  let temp = d;
  d = n % d;
  n = temp;
}
//At the end of this loop, n is your GCD.

So using that, combining it with our previous code, we can return the final result:
Either a single value (if the denominator ends up being 1, it means the result is a whole number), or two values (a fraction, in the form of a two-value array).
This format is defined by the challenge.

let matrix = [];
let common = Array.from({length: N+N}, (_,i) => i+2).reduce((a,c) => a*c,1);
for(let i = 0; i < N; i++) {
  matrix[i] = [];
  for(let j = 0; j < N; j++) {
   matrix[i][j] = (j+1)*(common/((i+1)+(j+1)));
 }
}
let totalnum = matrix.reduce((a,c) => a+c.reduce((ia,ic) => ia+ic,0),0);
let d = common;
let n = totalnum;
while(d) {
  let temp = d;
  d = n % d;
  n = temp;
}
if (common / n == 1) { return [totalnum / n] }
else { return [totalnum / n, common / n] }

So how do we go from that 17 lines of code, and many large numbers that will threaten the integer limits as N gets bigger, how do I get to a single line function?

Challenge 4

This section will be entirely cloaked in spoiler tags, because it completely defeats the idea of the coding challenge. Procede at your own risk of spoilage.

So, that code is big, bulky, and naive. We can do better, using mathematics.
This path actually opened itself up to me shortly before attempting challenge 2. But the principles of the coding challenge being about coding did make me go ahead with the naive path eventually, what I started with was “What does this grid look like?”

So I laid out a 4x4.

R\C	1	2	3	4
1	1/2	2/3	3/4	4/5
2	1/3	2/4	3/5	4/6
3	1/4	2/5	3/6	4/7
4	1/5	2/6	3/7	4/8

And being a pattern-seeking human (most humans seek patterns as a natural behavior). I started noticing things.

R\C	1	2	3	4
1	1/2	2/3	3/4	4/5
2	1/3	2/4	3/5	4/6
3	1/4	2/5	3/6	4/7
4	1/5	2/6	3/7	4/8

My notes:
Everything on this diagonal can be simplified down to 1/2.
These cells add to 1.
So do these ones…
In fact, all of the cells added by putting a new layer onto this cube, add 1’s, because there is a mirror-position element that complements the other.
So… there must be some underlying mathematical principle at work here. A triangular shape through the matrix, with opposing sides adding to whole numbers.
If every value that ISN’T on the diagonal adds to 1, and the diagonal is always adding 1/2, then the only answers I can get are whole numbers, or some whole number + 1/2…

With that spark in my head, the next obvious leap was… “What sorts of values is this going to spit out for different values of N?”
So I started looking at small results.

If N is…	the answer is…
0	0
1	1/2
2	2
3	4 1/2
4	8
5	12 1/2

Confirming my last thought from the previous section. So what logic can we draw?

If the numbers are all either whole numbers, or some number divided by 2, then the result is some whole number, divided by 2.
What whole number would that be, for my previous table?

If N is…	the answer is…	…and the whole number is
0	0	0
1	1/2	1
2	2	4
3	4 1/2	9
4	8	16
5	12 1/2	25

For those who might not be able to discern the pattern, here’s the answer:

The whole numbers are the Square Numbers. 0 = 0*0, 1=1*1, 4 = 2*2, 9 = 3*3, 16 = 4*4, 25 = 5*5....
So, putting it all together, for any given N, the solution to the function game(n) is N^2 / 2.
When N is odd, this will be a fraction, with the numerator being (N^2/2) * 2, which simplifies to N^2, and the denominator being 2; when it is even, this will be a whole number.

And in code form, our one-line answer is:

return (n%2 == 0) ? [n**2/2] : [n**2,2];

[dresden_phoenix]

@m_hutley

Woooooah there.
you can only sum the numerators if the denominators are the same… 1/2+4/5 is NOT 5/something! (Ex: There is no other term in the array with a denominator of 2 except the cell at 1,1.)

Sorry if i confused anyone I wasnt saying that was the formula for the answer, just one of the patterns that could be observed and used to come up with generalized solution, without giving away the answer.

for the sake of whomever comes across this post the following is LITERALLY the notes from the SCRATCH PAD I used to solve this coding challenge:

1/2 + 2/3 + 3/4 + 4/5   =           =      /    ((n + 1)! / (i+1)!)
1/3 + 2/4 + 3/5 + 4/6   =
1/4 + 2/5 + 3/6 + 4/7   =
1/5 + 2/6 + 3/7 + 4/8   =
1/6 + 2/7 + 3/8 + 4/9   =
1/7 + 2/8 + 3/9 + 4/10  =

60+80+90+96 /(120) =
120+180+216+240 /(360) = 40 + 60 + 72 + 80 / (120) * 6

210 + 336 + 420 + 480 /(840) =   30+ 48 + 60+ 40          /(120) 7

OBSERVATIONS:
ADD THE DIAGONAL!!!
 y%x + x*y --- 
 
 
 1/2
 3/3
 6/4
 10/5
 10/6
 10/7
 9/8
 7/9
 4/10
 
 6 * 24
 12+16+18 =46/24
 (result inconclusive)
 =======================================
 
 1/2
 
 1/2 2/3
 1/3 2/4  (note corners cancel out!!! this is what i prolly noticed in the diagonals earlier!)
 
 1/2 2/3 3/4
 1/3 2/4 3/5
 1/4 2/5 3/6
 
 ... 
 
 1/2 2/3 3/4  4/5  5/6  6/7  7/8
 1/3 2/4 3/5  4/6  5/7  6/8  7/9
 1/4 2/5 3/6  4/7  5/8  6/9  7/10
 1/5 2/6 3/7  4/8  5/9  6/10 7/11
 1/6 2/7 3/8  4/9  5/10 6/11 7/12
 1/7 2/8 3/9  4/10 5/11 6/12 7/13
 1/8 2/9 3/10 4/11 5/12 6/13 7/14
 
 
 n=1  = 0.5
 n=2  = 2   (+1.5)
 n=3  = 4.5 (+2.5)
 n=4  = 8	(3.5)
 n=5  = 12.5 (4.5)
 n=6  = 18   (5.5)
 n=7  = 24.5 (6.5)

 
 OBSERVATIONS:
 • ALL FRACTIONS are halves!
 • Fractions occur only in  odd # inputs!
 • n-1 +1/2  =  increment over previous grid
 (solve with loop  recursion)


MATH SOLUTION:
 •  n*n/2

Again, this is NOT code, just the thinking pattern used when interpreting the challenge. Do note that I allowed my self to be partially off base, and then iterated closer to a correct solution:

1. Noticed that the numerator would add up to the same amount in each row

2. Thought i could solve the issue of adding fractions with different denominators using factorials ( too much trouble)

3. Noticed that , if arranged in a grid, a diagonal would include values with the same denominator, thus solving the first issue!

4. Noticed that the sum of a given grid(n) was the value of grid(n-1) + plus the sum lower and right edge cells of grid(n)
   4-a)Noticed the sum lower and right edge cells of grid(n) always add up to a whole number or a whole number +1/2
   4-b) calculated the increment to be: n-1 +1/2 over previous grid
   4-c) This suggested a loop/itterative solutions

5. Wrote pattern of solved grid values and increments

6. compared this to iterative solution (n-1 +1/2)… discarded

7. Compared increments in value(discarded)

8. Compared final values … (at first I thought I saw a linear increase every couple of rows, ie: n2 =2 (or x1) , n4=8 (or x2), n6=18 (or x3)…

9. Realized that was more of a logarithmic increment …suggesting n^2

10. Derived that the general formula would be n*n/2

Anyway, that’s rough outline of my “thought process”. I have put it on here in the hopes it will help anyone deconstruct the OP’ (or any any other )
code challenge. The take away should be don’t be afraid to approach a code challenge from several different directions. Keep some formulas handy, Draw graphs, put the expected outputs in tables, etc.

–PS
I just, saw that Hutley did a very nice break down as well.