Open Side Menu Go to the Top
Register
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

02-26-2014 , 02:54 PM
I think we'll have to agree to disagree on that.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:00 PM
Quote:
Originally Posted by jjshabado
I think we'll have to agree to disagree on that.
Agree. It's just not that simple. Often nested loops/ifs make the code cleaner. The question is whether the pieces are logically connected. The above pasted code is a horrible place to split the nested for loop into separate functions. Related pieces of code should be together.

Some people love short functions. I prefer choosing the function length based on the situation. Sometimes you need a 50 line function. Splitting it will do nothing to improve readability. If the piece of code is not currently being reused there is no point in arbitrarily breaking up a long function. Now , if the function is doing multiple conceptually separate tasks then it's often better to split it up.

Also it's really important to write functions at the proper level of abstraction. Low level details and high level function calls should not be mixed in the same function.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:00 PM
Quote:
Originally Posted by jjshabado
I think we'll have to agree to disagree on that.
that's fine, but honestly i am just curious: does your nested for loop solution read clearer to you than the ruby 1 liner?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:02 PM
Quote:
Originally Posted by gaming_mouse
that's fine, but honestly i am just curious: does your nested for loop solution read clearer to you than the ruby 1 liner?
I find Ruby unreadable regardless of the number of lines of code I'm looking at.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:04 PM
Quote:
Originally Posted by gaming_mouse
that's fine, but honestly i am just curious: does your nested for loop solution read clearer to you than the ruby 1 liner?
No, but I think the nested loop implementation in this is a lot clearer than your JS implementation.

It's not fair to compare JS to ruby IMO.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:09 PM
Quote:
Originally Posted by gaming_mouse
that's fine, but honestly i am just curious: does your nested for loop solution read clearer to you than the ruby 1 liner?
Sort of?

The ruby 1 liner is clearer to people that have a really good understanding of Ruby functions and I would only ever use it if I was more experienced with Ruby than I am now and if I was only working with other Ruby experts.

Since that seems not that likely I would probably still break up the ruby code.

5 chained function calls don't seem inherently clearer to me than 5 lines of single function calls or a loop around a function call.

But similar to others, I find the 2-for loop solution significantly cleaner than the other JS solutions posted.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:12 PM
Quote:
Originally Posted by jjshabado
But similar to others, I find the 2-for loop solution significantly cleaner than the other JS solutions posted.
It's not apples to apples though - it solves the easier problem.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:13 PM
thanks, one more question out of curiosity: do you use map, forEach and reduce much in your own js code?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:17 PM
Quote:
Originally Posted by gaming_mouse
thanks, one more question out of curiosity: do you use map, forEach and reduce much in your own js code?
map and foreach - yes. reduce - no.

Although my job revolves around Hadoop - so I'm not really a stranger to map and reduce concepts.

Edit: I have nothing against reduce, I've just never found it a very common thing that I have to do.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:20 PM
Btw, the problem as stated is good for interviews but bad for internet nerd fights. Make the computation lazy so that it will work with N^2 in the billions and still return the array instantly, compute results on demand but still amortize to same time complexity when you iterate over the array.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:41 PM
candy, i don't see any way you could avoid having all N^2 numbers in memory at some point, since you have to have one of each randomly distributed across all the cells, and even if you are filling the cells on demand you have to keep track of which have been filled so you don't re-use the same number. but maybe i'm a bad internet nerd?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:53 PM
Quote:
Originally Posted by gaming_mouse
candy, i don't see any way you could avoid having all N^2 numbers in memory at some point, since you have to have one of each randomly distributed across all the cells, and even if you are filling the cells on demand you have to keep track of which have been filled so you don't re-use the same number. but maybe i'm a bad internet nerd?
Assuming that all you care is that every result be computed and you're willing to wait till it's done, you're correct. But sometimes we care about the order in which things are computed and may not even care about some results. And you may need some results back quickly. For example, you may need the following to run instantly:

var arr = makeRandom2DArray(50000);

var n1 = arr(15325, 32455);
var n2 = arr(8634, 24423);
var n3 = arr(34342, 5454);
var n4 = arr(1264, 3);

maybe you're done after this. Or maybe you need all results eventually, but need specific results before your application appears frozen. Now, it's equally easy to make things super-efficient for the sparse case where only a few results are ever used. But a naive implementation of the sparse/lazy array will be terrible if the user needs everything.

The hard problem is how do you go smoothly from the sparse to dense such that on an amortized and asymptotic basis, you haven't made it any worse than the naive implementation.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 03:59 PM
Hey for us simpletons who don't have the big words good - can you please expand on what 'amortized', 'asymptotic' and 'naive' mean to you in this context?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 04:35 PM
Quote:
Originally Posted by suzzer99
Hey for us simpletons who don't have the big words good - can you please expand on what 'amortized', 'asymptotic' and 'naive' mean to you in this context?
Asymptotic here means ignoring constant factors and focusing on growth as input size gets large. For example, merge sort, at O(n log n) is said to be asymptotically faster than insertion sort at O(n^2) which means for any given input on any particular machine insertion sort may be faster than merge sort, but regardless of setup, once you get to a large enough input, merge sort is going to be always faster than insertion sort.

http://en.wikipedia.org/wiki/Analysis_of_algorithms

Amortized simply means analyzing time complexity over an entire sequence of operations.

http://en.wikipedia.org/wiki/Amortized_analysis

Naive is just something a reasonable person would first gravitate towards. In this case, a naive lazy/sparse solution would involve issuing random numbers to requests, keeping tracking of them (as keys in a sparse array or hash for fast lookup as well as values in a separate cache so that multiple requests would return the same value), and just retrying until you have unique number. This obviously runs into a problem at the end as it's going to take forever to issue the last few remaining random numbers.

http://stackoverflow.com/questions/2...lementation-is
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 05:11 PM
Quote:
Originally Posted by candybar
But a naive implementation of the sparse/lazy array will be terrible if the user needs everything.
Quote:
The hard problem is how do you go smoothly from the sparse to dense such that on an amortized and asymptotic basis, you haven't made it any worse than the naive implementation.
Forgot I used the word naive twice. The first naive implementation refers to the hypothetical sparse/lazy implementation I had in mind. The second refers to actual solutions posted here, which are only naive from this hypothetical perspective of very large N's.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 05:14 PM
lets not forget that map is simply an abstraction on a for loop, so while you save on loc, you don't gain anything in computing space.

I personally prefer jj's solution for the simple reason of clarity. Probably be easier to examine and decompose and modify , though matrix operations, if I recall correctly , are np hard.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 05:47 PM
Quote:
Originally Posted by daveT
I personally prefer jj's solution for the simple reason of clarity.
For the second time, jj's solution does not do the same thing as gaming_mouse's - it just puts random numbers in a 2d-array, whereas gm's does a Fisher-Yates shufffle to create a unique list.

Quote:
Probably be easier to examine and decompose and modify , though matrix operations, if I recall correctly , are np hard.
Not sure what you meant to say, but matrix and NP-hard have nothing to do with each other.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 05:50 PM
Quote:
Originally Posted by muttiah
I find Ruby unreadable regardless of the number of lines of code I'm looking at.
Ruby is many things but unreadable isn't one of them. Imo it's one of the most readable languages.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 05:53 PM
Quote:
Originally Posted by daveT
lets not forget that map is simply an abstraction on a for loop, so while you save on loc, you don't gain anything in computing space.
no one is forgetting that and it's not an argument.

"let's not forget that C is just an abstraction over assembly commands, so you don't gain anything in computing space...." etc.

readability, at heart, is about mapping code onto natural mental concepts. all the other stuff (simplicity, brevity, etc) falls out of that, and it's possible to have simple or concise code that is nonetheless difficult to read. what something like "map" gives you is the ability to capture the concept of "hey, i want to do *this* to all of these things, i don't care how." you are of course free to argue this point, but that is a lot closer to how i think naturally than "first i want to take the first thing, and do this to it, and then i want to take the second thing, and do this to it, and so on."
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 06:19 PM
Since I wield a (CSP) hammer and this problem sounds like a nail...I'll provide the "wicked hard" part in Prolog:

Code:
all_distinct(FlattenedMatrix)
Guess it kind of depends on what you mean by random. I'd be totally fine just creating 0..N in order or a set of 0..N and shuffling it as proposed but it would be neat to be able to fill in one number at a time for kicks i.e. provide some numbers for some positions and fill the rest with the remaining distinct random numbers. That's obviously also possible by other means such as remembering the positions, creating a new random array and find the numbers and swap spaces.

Don't really see the benefit of converting to nxn form until you need that or want some specific matrix operations or the like so a list should do just fine.

Since it's nxn it should be easy enough to index the list i.e. just convert that [x,y] to the appropriate index. My gut says that this approach of keeping the simple data structure and do some conversion on the operations would be faster overall.

Last edited by clowntable; 02-26-2014 at 06:39 PM.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 06:29 PM
Meh, the problem is not nearly as interesting as I thought, here's a lazy version, zero-based and not thoroughly tested.

Code:
function lazyFisherYates(n) {
  var rand = function(n) { return Math.floor(Math.random() * n); };
  var fixed = 0, deck = [], index2DeckIndex = [];
  var get = function (i) { return (deck[i] === undefined ? i : deck[i]); };
  var swap = function (i, j) {
    var temp = get(i);
    deck[i] = get(j);
    deck[j] = temp;
  };
  return function(i) {
    if (i >= n || i < 0) return undefined;
    if (index2DeckIndex[i] !== undefined) return deck[index2DeckIndex[i]];
    else {
      swap(fixed, rand(n - fixed - 1) + fixed);
      index2DeckIndex[i] = fixed;
      return deck[fixed++];
    }
  };
}

function lazy2DArray(n) {
  var arr = lazyFisherYates(n*n);
  return function (i, j) {
    return arr(i * n + j);
  };
}

function printFunctional2DArray(arr, n) {
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < n; j++) {
      console.log("arr[" + i + ", " + j + "] = " + arr(i, j));
    }
  }
}

printFunctional2DArray(lazy2DArray(4), 4);
printFunctional2DArray(lazy2DArray(7), 7);

var arr = lazy2DArray(40000);
console.log(arr(2412,12324));
console.log(arr(8788,32324));
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 06:42 PM
Quote:
Originally Posted by clowntable
Since it's nxn it should be easy enough to index the list i.e. just convert that [x,y] to the appropriate index. My gut says that this approach of keeping the simple data structure and do some conversion on the operations would be faster overall.
Good point. I guess it would depend on the exact use case, but you're right this does seem to make way more sense for most uses.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 08:54 PM
Btw for the record I think the ruby version is super clear as long as you know what each method does. It's a great example of composing a bunch of small solutions to a problem to solve a larger problem.

I think a random general imperative programmer with little functional experience would be able to see what it's doing for the most part. The only non-obvious one is each_slice but given the inputs and the output you could probably guess at what it does without looking at the docs.

I'd be curious what the javascript underscore version looks like.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 09:18 PM
Quote:
Originally Posted by Shoe Lace

I'd be curious what the javascript underscore version looks like.
the shuffled full array is just "_.shuffle(_.range(25))". they don't appear to have anything like each_slice, so you'd have to write your own. i guess underscore doesn't mess with array prototype, so you have that inverse right to left flow with nested parens instead of the more natural left to right flow with dots you get with the ruby objects. i think there are other libraries which will fix that though.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
02-26-2014 , 09:26 PM
Yeah, I took a look at it.

Came up with this without much testing to confirm if it's correct tho:
http://jsfiddle.net/9PWTu/

Fiddled it because of the underscore dependency.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote

      
m