1
$\begingroup$

I'm numbering generated files with two digits 00-99 and I want to retain the last 50. The algorithm should tell me the number of the current file that I'm about to save and which of the previous files to remove.

If I scale it down to a toy version with one digits, here's how I want it to behave.

  1. As long as there are fewer than 5 files, we can just add files. This is represented in the first block below.
  2. Once there are 5 previous files, the oldest one should be deleted. This is trivial as long as we haven't reached the maximum number, here 9. This is represented in the second block below.
  3. Once the highest numbers has been reached, the numbering should roll around, and here is where things get tricky. See the third block below.
__prev__    __curr__   __drop__  
<no files>     0         null
0              1         null
0 1            2         null
0 1 2          3         null
0 1 2 3        4         null

0 1 2 3 4      5          0 
1 2 3 4 5      6          1
2 3 4 5 6      7          2
3 4 5 6 7      8          3
4 5 6 7 8      9          4

5 6 7 8 9      0          5
6 7 8 9 0      1          6
7 8 9 0 1      2          7
8 9 0 1 2      3          8
9 0 1 2 3      4          9

Some pseudocode to illustrate my progress:

if length(prev) < 5
   curr = length(prev)
   drop = null

else

if 9 not in prev
   curr = (1+max(prev)) mod(10)
   drop = curr-5

if 9 in prev

... and this is where I'm stuck. I've experimented with subtracting 10 from each element in prev.

I'm sure it's trivial and that It'll hit me when I least expect it. I also have a nagging feeling I'll find an expression that generalizes both cases (with and without max in prev).

$\endgroup$
3
  • 1
    $\begingroup$ Try adding five instead of subtracting five. More generally, instead of subtracting $a$, add $10-a$ (or $100-a$ etc). $\endgroup$ Apr 2, 2020 at 14:23
  • $\begingroup$ Your title didn't make sense to me -- is there any way to clarify it? $\endgroup$ Apr 2, 2020 at 15:18
  • $\begingroup$ Yuval: I think that's kinda what I'm doing. I'm adding a to every x > a/2 $\endgroup$
    – mappo
    Apr 3, 2020 at 6:13

3 Answers 3

2
$\begingroup$

What you have been trying to implement is a first-in-first-out(FIFO) fixed-sized data structure, which is commonly called a circular queue, circular buffer, cyclic buffer or ring buffer.

In addition to the requirement of circular queue, you want the numbers rolling around an interval such as from 0 to 99. Since all the numbers in use are contiguous, it is enough to use just two numbers, the smallest of them and the largest of them to represent them.

In fact, since the number of files is a constant once the maximum number of files have been reached, it is enough if we keep track of the count of all numbers ever used. So we can construct a much simplified special implementation of the circular queue.

Similarly to your code, we should use the modulo technique. Here is a simple and fully-working Javascript implementation. Both get operation and update operation runs in $O(1)$.

// From 0 to limit-1 are all usable numbers.
// At any moment, at most maximumKept numbers can be retained.
// For example, if we use 00-99 to parametrize names of at most 50 files,
// we should use createCircularQueue(100, 50).
function CreateCircularQueue(limit, maximumKept) {
    this.limit = limit;
    this.kept = maximumKept;

    this.count = 0;  // count of all numbers ever used.

    // return the number to remove and the next available number.
    this.get = function () {
        if (this.count <= this.kept - 1) {
            return [null, this.count];
        }
        else {
            const next = this.count % this.limit;
            let toRemove = next - this.kept;

            return [toRemove + ((toRemove >= 0) ? 0 : this.limit), next];
        }
    };

    this.update = function () {
        this.count += 1;  // this will NOT overflow before 2**53-1=9007199254740991.
    }

}

The above implementation works for all possible integer pairs limit >= maximumKept. In particular, it works even if limit is maximumKept.

Here is a sample usage:

function myLog(wantedNumbers) {
    console.log("number to remove: " + wantedNumbers[0]
        + "    next number to use: " + wantedNumbers[1])
}

let cq = new CreateCircularQueue(5, 3);
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
$\endgroup$
6
  • $\begingroup$ "let toRemove " could be "const Remove". "let cq" could be "const cq". $\endgroup$
    – John L.
    Apr 4, 2020 at 4:21
  • $\begingroup$ For the original problem, we can do let cq = new CreateCircularQueue(100, 50); for(let i = 0; i < 201; i++) { console.log(cq.get()); cq.update();}; $\endgroup$
    – John L.
    Apr 4, 2020 at 17:48
  • $\begingroup$ You can play my solution here online, where a solution that tracks the start and the end numbers, CreateCircularQueue2is presented as well. $\endgroup$
    – John L.
    Apr 4, 2020 at 17:59
  • $\begingroup$ this.count += 1; If we were super cautious, we could replace this with this.count = (this.count + 1) % ( this.limit * 2); (and rename count). However, we then lose the count of total numbers that have been produced. $\endgroup$
    – John L.
    Apr 4, 2020 at 18:07
  • $\begingroup$ Awesome answer, John L. - thank you! I should have realized that it was a form of FIFO. Great to know that it has a name. Beautiful example too! Thanks $\endgroup$
    – mappo
    Apr 6, 2020 at 7:17
1
$\begingroup$

It's funny how explaining a problem makes you approach it differently (rubber duck, anyone?).

I think I've managed to cobble together the behaviour that I'm looking for. The idea is that if the list contains the last number (i.e. n-1, here 9), n is added to every number greater than n/2.

Now, Javascript is definately not my first language, so please be kind and try to see the idea rather than the mess that is my js ...

Play with it here or just take in the view below. Of course I'd be grateful for a better solution.

function roll(n) {
  const half = n/2 ;
  const last = n-1 ;
  var iter = half * 3 ;
  var prev = [] ;
  var curr = null ;
  var drop = n ;
  var temp ;

  while(iter--) {
    console.log(prev) ;
    curr = prev.length ;
    if (curr < half) {
      prev = update(prev,curr,drop) ;
      continue ;
    }
    temp = [].concat(prev) ;
    if (temp.includes(last)) {
      for (var t=0 ; t<temp.length ; t++) {
        if (temp[t] < half)
          temp[t] += n ;
      }
    }
    drop = Math.min.apply(null, temp) % n ;
    curr = Math.max.apply(null, temp) + 1 ;
    curr %= n ;
    prev = update(prev,curr,drop) ;
  }
}

function update(p,c,d) {
  for (var i=0 ; i<p.length ; i++) {
    if (p[i] == d)
      p.splice(i,1) ;
  } 
  p.push(c) ;
  return p ;
}

roll(10) ;
$\endgroup$
1
$\begingroup$

The behavior of the modulo function in many programming languages is a bit quirky, and might depend on the sign of the argument. However, if you compute $a \bmod b$ for positive $a,b$, you will get an answer in the range $0,\ldots,b-1$.

Now suppose we want to compute a difference $x-y \pmod{b}$, and our goal is to obtain an answer in the range $0,\ldots,b-1$. We can assume that $x,y$ are in the same range. If $y > x$, then $x - y$ would be negative, and so we might get a negative answer. To prevent that, we can compute $x + (b-y)$ instead. This will always give the correct answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.