Quote:Original post by The Reindeer EffectYes but that doesn't work. Try it on the simple example of (1,2,3,4,100). Only one is above average, but it would say that all of them are.
Solution in linear space but with no explicit data structures(define (foo input) (let ((average #f)) (let loop ((n 0) (total 0)) (let ((i (input))) (if (= i -1) (begin (set! average (/ total n)) 0) (let ((val (loop (+ n 1) (+ total i)))) (+ val (if (> i average) 1 0))))))))
int above_average_rec(int (*f)(), int n, float* avg) { int above; int x = f(); if (x == -1) { *avg = *avg / n; return 0; } *avg = *avg + x; above = above_avg_rec(f,n+1,avg); if (x < *avg) return above; return above + 1;}int above_average(int (*f)()) { float avg; return above_average_rec(f,0,&avg);}Quote:Original post by ToohrVyk
If the stack is assumed to be of infinite size, then a linear-space C solution would be:
*** Source Snippet Removed ***
Nitage: it could also be assumed that the input can be read twice, which does indeed make the problem trivial. It makes the solution trivial: in fact, the first reaction to the problem in the absence of any constraints is to "loop twice". If the same approach is also possible when constraints are applied, what is the point of the problem? Moreover, what is the point of restricting the existence of arrays, stacks, lists and similar data structures if the simplest thing that could possibly work didn't need them anyway? The basic premise of a puzzle is that the straightforward solution does not work, so you have to look for something more complex. I am reluctant to make the assumption that a puzzle question is, in fact, just a silly question.
Quote:Original post by NitageSeeing as the puzzle is either impossible or trivially easy, I'd say that you don't have to make any assumptions to realise that it's a silly question.
Quote:Original post by Zahlman
Guys, seriously. Don't be dense. There are only a few possible sets of assumptions.
Assumptions 1: constant space required, stream can only be read once. This is provably impossible, and the proof was given right near the beginning of the thread.
Assumptions 2: constant space required, stream can be read more than once. This is trivial: read the stream twice, calculating the average the first time and counting the above-average values the second time.
Assumptions 3: constant space not required (but we can't use an explicit variable-size data structure), stream can only be read once. This is trivial (well, almost): recurse to put all the values onto the program stack, summing them on the way up; at the end of stream, determine the average (you will have passed the current sum and recursion depth all the way up), and then return all the way back, each time passing back a structure holding just the average (so you can keep track of it) and the number of above-average values found so far (such a structure surely does not qualify as "an array, list, vector, stack, etc."; we could alternately put the average value into a global variable once known).
Assumptions 4: constant space not required (but we can't use an explicit variable-size data structure), stream can be read more than once. This is trivial: Use either method 2 or method 3.
Quote:Original post by Nitage
Seeing as the puzzle is either impossible or trivially easy, I'd say that you don't have to make any assumptions to realise that it's a silly question.
Quote:Original post by Zahlman
Guys, seriously. Don't be dense. There are only a few possible sets of assumptions.
Assumptions 1: constant space required, stream can only be read once. This is provably impossible, and the proof was given right near the beginning of the thread.
Assumptions 2: constant space required, stream can be read more than once. This is trivial: read the stream twice, calculating the average the first time and counting the above-average values the second time.
Assumptions 3: constant space not required (but we can't use an explicit variable-size data structure), stream can only be read once. This is trivial (well, almost): recurse to put all the values onto the program stack, summing them on the way up; at the end of stream, determine the average (you will have passed the current sum and recursion depth all the way up), and then return all the way back, each time passing back a structure holding just the average (so you can keep track of it) and the number of above-average values found so far (such a structure surely does not qualify as "an array, list, vector, stack, etc."; we could alternately put the average value into a global variable once known).
Assumptions 4: constant space not required (but we can't use an explicit variable-size data structure), stream can be read more than once. This is trivial: Use either method 2 or method 3.
Quote:Original post by Semion_N
The link you gave me above is not the mathematical proof it's just the definition of the problem, mathematical proof that the problem is unsolvable is to exhibit one case which shows that the problem is unsolvable.
and if you wantr to prove that the problem is solvable you should show that all the cases is TRUE.
