martin.pernollet
BAN USERA solution in java to flip array dimensions. I think this was the actual question... little more difficult, but more fun and interesting.
Could not do better than O(i*j*k...)
public class MDAFlipDimensions {
public static void main(String[] args){
Object[] array = (Object[])Array.newInstance(Integer.class, 2, 3, 4);
System.out.println("init");
MDAFlipValue.explore((Object[])array, new MDAFlipValue.RandomInitializer());
MDAFlipValue.print(array);
MDAFlipDimensions fd = new MDAFlipDimensions();
Object[] flipped = fd.flip(array);
MDAFlipValue.print(flipped);
System.out.println("done");
}
public Object[] flip(Object[] array){
int dims = computeDimensions(array, 0);
int[] sizes = new int[dims];
computeSizes(array, 0, sizes);
// init dest
int[] flippedSizes = clone(sizes);
reverse(flippedSizes);
Object[] flippedArray = (Object[])Array.newInstance(Integer.class, flippedSizes);
// copy flipped
int[] path = new int[dims];
copyFlipped(array, 0, path, flippedArray);
return flippedArray;
}
// O(1)
protected int computeDimensions(Object[] array, int depth) {
if(array[0] instanceof Object[])
return computeDimensions((Object[])array[0], depth+1);
else
return depth+1;
}
// O(1)
protected void computeSizes(Object[] array, int depth, int[] sizes) {
sizes[depth] = array.length;
if(array[0] instanceof Object[])
computeSizes((Object[])array[0], depth+1, sizes);
}
// O(i*j*k*...)
protected void copyFlipped(Object[] src, int depth, int[] path, Object[] dest) {
for(int i=0; i<src.length; i++){
int[] myPath = clone(path); // O(1)
myPath[depth] = i;
Object cell = src[i];
if(cell instanceof Object[]){
// go recursively in sub array
copyFlipped((Object[])cell, depth+1, myPath, dest);
}
else{
// copy cell in destination array
insertFlipped(dest, myPath, (Integer)cell, 0);
}
}
}
// O(1)
// index is the position in src array: input[i,j,k] gives index {i,j,k}
protected void insertFlipped(Object[] newArray, int[] index, int value, int depth) {
int le = index.length-1;
int id = index[le-depth];
if(depth<le){
Object[] childArray = (Object[])newArray[id];
insertFlipped(childArray, index, value, depth+1);
}
else{
newArray[id] = value;
}
}
/* utils */
protected int[] clone(int[] array){
int[] clone = new int[array.length];
System.arraycopy( array, 0, clone, 0, array.length );
return clone;
}
protected void reverse(int[] array) {
int left = 0;
int right = array.length - 1;
while( left < right ) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
}
A solution in java to flip values:
public class MDAFlipValue {
public static void main(String[] args) {
Object[] array = (Object[])Array.newInstance(Integer.class, 2, 3, 4);
System.out.println("init");
explore((Object[])array, new RandomInitializer());
print(array);
System.out.println("flipping values");
explore((Object[])array, new ValueFlip());
print(array);
}
/* multidim array explore */
public static void explore(Object[] array, ArrayAction callback){
for(int i=0; i<array.length; i++){
Object cell = array[i];
if(cell instanceof Object[]){
explore((Object[])cell, callback);
}
else{
callback.cellAction(array, i);
}
}
}
public interface ArrayAction{
public void cellAction(Object[] parentArray, int index);
}
/* array edition */
public static class RandomInitializer implements ArrayAction{
Random random = new Random();
public void cellAction(Object[] parentArray, int index) {
parentArray[index] = random.nextInt(2); // 0 or 1
}
}
public static class ValueFlip implements ArrayAction{
public void cellAction(Object[] parentArray, int index) {
Object value = parentArray[index];
if(value instanceof Integer){
Integer v = (Integer) value;
if(v == 1)
parentArray[index] = 0;
else if(v == 0)
parentArray[index] = 1;
else
throw new IllegalArgumentException("unexpected value");
}
}
}
/* console output */
public static void print(Object[] array){
StringBuffer sb = new StringBuffer();
print(array, 0, sb);
System.out.println(sb.toString());
}
public static void print(Object[] array, int depth, StringBuffer sb){
for(int i=0; i<array.length; i++){
Object cell = array[i];
if(cell instanceof Object[]){
print((Object[])cell, depth+1, sb);
sb.append("\n");
}
else{
for (int j = 0; j < depth; j++)
sb.append(" ");
sb.append(cell + " ");
}
}
}
}
From a java perspective, we may say that:
A TreeSet is backed by a TreeMap, and TreeMap.Entry has the following fields:
K key;
V value;
Entry<K, V> left = null;
Entry<K, V> right = null;
Entry<K, V> parent;
boolean color = BLACK;
the memory weight is 3 references + 1 boolean = 3 bytes + 1 bit (assuming we work on a 32 bits computer)
HashMap.Entry has the following fields:
final K key;
V value;
Entry<K, V> next;
final int hash;
the memory weight is 1 reference + 1 integer = 2 bytes
An additional memory weight in HashMap is due to an array of buckets, each bucket being addressed by the actual Entry.hash (which is the key hashCode). As one usually wish to have a minimum number of entries per bucket, let's assume we have exactly one entry in each bucket. There will thus be an array of N references (N: number of entries) so one byte per entry.
So I see a single bit of difference per entry between a TreeSet and a HashMap.
But this is implementation dependent. If you don't need your tree entries to reference their parent, then you spare 1 reference in the tree entry, and thus the tree becomes cheaper.
I agree with that comment. I would also say that the conditions are conflicting:
- martin.pernollet February 27, 20132) Every element may repeat minimum 5 times [...]
3) 'a' can be swapped only 1 time [...]
I don't see how one can swap 'a' only one time if there are five randomly given 'a' instance.
Relaxing the number of swap constraint, the above solution is great.