3 ms·

couldn't help myself, I think 3-5 min grid = [ [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9

by 6510 2y ago

couldn't help myself, I think 3-5 min grid = [ [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] ] foo = function(x,y,num){ if (grid[x][y] == num) return true; if (grid[x+1] && grid[x+1][y] == num) return true; if (grid[x+2] && grid[x+2][y] == num) return true; if (grid[y+1]){ if (grid[x][y + 1] == num) return true; if (grid[x+1] && grid[x+1][y+1] == num) return true; if (grid[x+2] && grid[x+2][y+1] == num) return true; } if (grid[y+2]){ if (grid[x][y+2] == num) return true; if (grid[x+1] && grid[x+1][y+2] == num) return true; if (grid[x+2] && grid[x+2][y+2] == num) return true; } return false; } alert(foo(1,2,3)); alert(foo(1,2,30)); humm worked first try, probably something wrong with it.. https://jsfiddle.net/ycx159kg/ https://jsfiddle.net/ycx159kg/ 13 min later... round2 = function(x,y,num){ return grid.slice(x,x+3).map(g=>g.slice(y,y+3)).flat().includes(num); }

HeyLaughingBoy 2y ago
And that reminded me that some people were nervous about doing the nested loop solution so asked if they could "brute force" it and we would accept that. Interview stress is a thing after all. I'm intrigued by the slice/map solution. It would have been perfectly acceptable if you could explain what the functions did. In fact, it would have led to very probing conversations: my usual interview partner and me had a deep interest in elegant solutions.
- 6510 2y ago
  grid.slice(x,x+3) Turns the 10x10 array into a 3x10 discarding the rows before and after the target rows. If the second value in slice is larger than the length it slices to the end. It could be a 2x10 or 1x10 but lets pretend it is 3. .map(g=>g.slice(y,y+3)) Does the same with each row making it into a 3x3 (or 2x3 or 1x1 etc) .flat() Turns the 3x3 into a flat array of up to 9 values. .includes(num) tests if the flat sliced array include num.
CyberDildonics 2y ago
In your example the first dimension returns a pointer to a row, then the next is the offset into that row so your lookup needs to be grid[y][x] Also you seem to be bounds checking for 0s, but to do that in the first dimension you need null pointers to pad your row selection and a second set of 0s at the end of your rows. It's interesting that both you and the person you replied to used arrays of arrays which is the very first mistake everyone makes in graphics programming when trying to make a 2D array or and image. A much better way is to have a single contiguous array and use buf[y*width + x] to lookup into the one dimension buffer.
- bubblyworld 2y ago
  It's only much better if you care about cache misses, right? I think for a 10x10 array we can safely ignore performance concerns.
  - CyberDildonics 2y ago
    It's only much better if you care about cache misses, right? No, not at all. There are cache misses and simplicity, but think about when an 1k image is on the heap. You have to allocate a buffer of pointers for each row then you have do a thousand individual heap allocations to get all your rows. Now think about an image with rgba channels. Technically this is a 3d image with one short dimension. Are you going to allocate a buffer of a thousand pointers, then off of each one allocate a buffer of a thousand more pointers so that you can ultimately do another 1 million heap allocations, all 16 bytes for each rgba pixel? There is no upside and all downsides, which is why it is never ultimately done this way, though it is an almost universal mistake when people do multi-dimensional arrays for the first time.
    - bubblyworld 2y ago
      Yeah, I hear you, my point was just that we know the constraints up front and it doesn't matter in this case. Sometimes it's convenient to not have to pass around the length and do one or more multiplies with every index.
- 2y ago

by 6510 2y ago

HeyLaughingBoy 2y ago

And that reminded me that some people were nervous about doing the nested loop solution so asked if they could "brute force" it and we would accept that. Interview stress is a thing after all. I'm intrigued by the slice/map solution. It would have been perfectly acceptable if you could explain what the functions did. In fact, it would have led to very probing conversations: my usual interview partner and me had a deep interest in elegant solutions.

6510 2y ago
grid.slice(x,x+3) Turns the 10x10 array into a 3x10 discarding the rows before and after the target rows. If the second value in slice is larger than the length it slices to the end. It could be a 2x10 or 1x10 but lets pretend it is 3. .map(g=>g.slice(y,y+3)) Does the same with each row making it into a 3x3 (or 2x3 or 1x1 etc) .flat() Turns the 3x3 into a flat array of up to 9 values. .includes(num) tests if the flat sliced array include num.

CyberDildonics 2y ago

In your example the first dimension returns a pointer to a row, then the next is the offset into that row so your lookup needs to be grid[y][x] Also you seem to be bounds checking for 0s, but to do that in the first dimension you need null pointers to pad your row selection and a second set of 0s at the end of your rows. It's interesting that both you and the person you replied to used arrays of arrays which is the very first mistake everyone makes in graphics programming when trying to make a 2D array or and image. A much better way is to have a single contiguous array and use buf[y*width + x] to lookup into the one dimension buffer.

bubblyworld 2y ago
It's only much better if you care about cache misses, right? I think for a 10x10 array we can safely ignore performance concerns.
- CyberDildonics 2y ago
  It's only much better if you care about cache misses, right? No, not at all. There are cache misses and simplicity, but think about when an 1k image is on the heap. You have to allocate a buffer of pointers for each row then you have do a thousand individual heap allocations to get all your rows. Now think about an image with rgba channels. Technically this is a 3d image with one short dimension. Are you going to allocate a buffer of a thousand pointers, then off of each one allocate a buffer of a thousand more pointers so that you can ultimately do another 1 million heap allocations, all 16 bytes for each rgba pixel? There is no upside and all downsides, which is why it is never ultimately done this way, though it is an almost universal mistake when people do multi-dimensional arrays for the first time.
  - bubblyworld 2y ago
    Yeah, I hear you, my point was just that we know the constraints up front and it doesn't matter in this case. Sometimes it's convenient to not have to pass around the length and do one or more multiplies with every index.
2y ago