gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

OffTopic > Programming problem: multiple array removals!!!

#114159 - keldon - Thu Jan 04, 2007 7:13 pm

The problem of the domain was dealing with managing the falling of blocks in Tetris. If you clear a line, then all of the above lines will have to fall down. However if you extend this to a bigger domain you can consider a single array where you are removing a number of elements from it and you want to output the offsets that the new array will have. For example if you have a 10 element array and you are removing the 7th element (starting from 0) then elements 7,8, and 9 will be offset by 1

Input begins with the size of the array followed by the number of elements to be removed; the elements to be removed are given on the next line seperated by a space. So for this example you have:

// sample input
10 1
7
// sample output
0 0 0 0 0 0 0 1 1 1

Here is another example where elements 0,1,3, 5 and 8 are removed
// sample input
20 5
0 1 3 5 8
// sample output
2 3 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

To make things more complicated the array size can be 2000000, the list of numbers to remove are not ordered, and this is a time critical task; so all solutions are limited to 10 seconds of execution!!! Leway is allowed for slower processors; just as a guideline to the complexity of the problem you.

Here is the generator code so that you could try out your own data. I would advise all those who are not sure of their solutions speed to change the Size, and also note that the lower the ration of Size:Removed the longer this takes to generate problems.

Note that I have created a problem creator/solver at http://thedrugzone.co.uk/LaMightySolution.jar , copy it to your desktop as it creates its output files in the same directory!
Code:
// Generator.java
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;


public class Generator {
   /** number of elements removed from array */
   public static final int Removed = 5000000;
   
   /** size of array */
   public static final int Size = 10000000;
   
   public static void main ( String argv [] ) throws FileNotFoundException {
      if ( Size < Removed ) {
         System.out.println ("Recompile with Size > Removed");
      }
      
      boolean [] b = new boolean [Size];
      int numbers[] = new int[Removed];
      
      System.out.println("Generating problem!");
      
      for ( int i = 0; i < Size; i ++ ) b[i]=true;
      
      int total = 0;
      while ( total < Removed){
         int rand = (int)(Math.random() * (double)Size);
         rand = (rand==Size)?rand-1 : rand;
         
         if ( b[rand] ){
            b[rand] = false;
            numbers[total++] = rand;
         }
      }
      
      PrintWriter out = new PrintWriter(new FileOutputStream ("problem.txt"));
      out.println(Size + " " + Removed);
      for ( int i = 0; i < Removed; i ++ ) {
         out.print(numbers[i] + (i==Removed-1?"":" "));
         if ( i%1000 == 0 ) out.flush();
      }
      out.close();
      
      System.out.println("Problem saved as problem.txt");
      
      
   }
}

#114168 - gauauu - Thu Jan 04, 2007 9:20 pm

While there might be some "tricky" solutions that do things faster, wouldn't the relatively straightforward solution be nearly optimal? It's O(n) + whatever your sort requires (probably O(n log n)ish. although the n in that case is the list to be removed, which certainly cuts things down in most practical cases). This is untested, but illustrates the general principle....

Code:

//this pretends memory management doesn't need to exist....
int* getOffsets(int totalNum, int numRemoved, int * removed)
{
   //get these bad boys in order
   int* list = doSomeFastSort(removed, numRemoved);

   int offsets[totalNum - numRemoved];

   //ctr keeps track of how big offset so far, also which
   //item we are in the removed list (it's the same thing)
   int ctr = 0;
   int * offsetPos = (int*)offsets;

   for (int i = 0; i < numRemoved; i++)
   {

      int todo = list[i] - ctr;

      for (int j = 0; j < todo; j++)
      {
         *offsetPos++ = ctr;
      }

      ctr++;
   }

   //fill in the rest of the values
   int todo = numRemoved - ctr;

   for (int j = 0; j < todo; j++)
   {
      *offsetPos++ = ctr;
   }

   return offsets;
}


#114176 - tepples - Thu Jan 04, 2007 11:36 pm

I thought of a similar solution that involves pushing the line numbers into a priority queue and then popping them out one by one (at every offsetPos++). This is equivalent to gauauu's solution where doSomeFastSort == heapsort.

I can see how the specification for this programming puzzle might suit some variants of the Soviet Mind Game. The problem here is that it doesn't match up for all variants, including variants that have shown up in more than one Tetris brand product. Apart from the naive solution of moving blocks down by exactly n rows if n lines have been cleared beneath them, there are at least two other common types of gravity after line clear in falling block puzzle games. Carbon Engine (basis for TOD) implements "sticky", while Lockjaw Engine (basis for post-TOD games) implements all three types as of version 0.28.

But there's another application of this code: the output data format is exactly that used by HDMA to the Y offset of text backgrounds on the GBA and DS, where the list of numbers is the list of scanlines to skip.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#114186 - keldon - Fri Jan 05, 2007 1:45 am

Well one thing to remember is the knock on effect produced by nearby removals. For example if you remove both the elements at 0,1,2 and 3, then the first offset will be 4. And yes, the solution is O(N); that is why it is possible to do it with a size of 10'000'000 in around 10 seconds.

I never knew of any other application for this type of code, the thought had not crossed my mind; despite the scenario I wrote. Well I have other problems that are interesting (but not created by me):

Q1: Arrange all of the numbers from 1-15 so that the sum of two adjacent cells is always a perfect square

Q2: In the tree-like pattern shown below, the number in every circle form the second row upwards is the sum of the two numbers in the two circles below it. All the circles have different positive whole numbers

[the bottom of the tree is 2,4,1,7,3]

(a) How should the five circles at the bottom row be numbered so that when all the others are filles in as above, the top circles has the least possible number. Remember, no two circles should have the same number

(b) Find numbers for the base so that the top circles is a specific number, say 91. Again, there should be no repetitions.

I looked at this one and found that if you label the base as a,b,c,d,e that the top of the tree is a+4b+6c+4d+e

Q4: Here is a short list of numbers having a common difference (of 43):

if we read down the list in columns we read:
1 2 7 1 9 2 5

On the same system (but not a difference of 43, what list of numbers gives:
1 1 1 8 2 5 9 7 2 7 2 ?