1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
|
package align2;
import java.util.Arrays;
public class Solver {
public static final long bruteForce(int[] offsets, int[] lengths, int chunk, int minLists, int maxTotalLength){
int bits=offsets.length;
int max=(1<<bits)-1;
for(long i=0; i<=max; i++){
long x=evaluate(offsets, lengths, chunk, i);
}
assert(false);
return 0;
}
public static final void findWorstGreedy(final int[] offsets, final int[] lengths,
final int chunk, final int[] lists, int[] r){
assert(r!=null && r.length==2);
long min=Long.MAX_VALUE;
int worstIndex=-1;
for(int i=0; i<lists.length; i++){
long value=valueOfElement(offsets, lengths, 1f, chunk, lists, i);
if(value<min){
if(min<EARLY_TERMINATION_SCORE){//Can speed up greedy algo
r[0]=i;
r[1]=(value<Integer.MIN_VALUE ? Integer.MIN_VALUE : value>Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)value);
return;
}
min=value;
worstIndex=i;
}
}
// if(min>0){worstIndex=-1;}
r[0]=worstIndex;
r[1]=(min<Integer.MIN_VALUE ? Integer.MIN_VALUE : min>Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)min);
}
public static final void findWorstGreedy(final int[] offsets, final int[] lengths,
final float[] weights, final int chunk, final int[] lists, int[] r){
assert(r!=null && r.length==2);
long min=Long.MAX_VALUE;
int worstIndex=-1;
for(int i=0; i<lists.length; i++){
// for(int i=lists.length-1; i>=0; i--){
long value=valueOfElement(offsets, lengths, weights[i], chunk, lists, i);
if(value<min){
if(min<EARLY_TERMINATION_SCORE && i!=0){//Can speed up greedy algo
r[0]=i;
r[1]=(value<Integer.MIN_VALUE ? Integer.MIN_VALUE : value>Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)value);
// System.out.print(".");
return;
}
min=value;
worstIndex=i;
}
}
// if(min>0){worstIndex=-1;}
r[0]=worstIndex;
r[1]=(min<Integer.MIN_VALUE ? Integer.MIN_VALUE : min>Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)min);
}
public static long valueOfElement(final int[] offsets, final int[] lengths, float keyWeight,
final int chunk, final int[] lists, int index){
final int numlists=lists.length;
if(numlists<1){return 0;}
final int prospect=lists[index];
if(lengths[prospect]==0){return -999999;}
long valuep=POINTS_PER_LIST+(POINTS_PER_LIST*2/lists.length)+((POINTS_PER_LIST*10)/lengths[prospect]);
long valuem=POINTS_PER_SITE*lengths[prospect];
if(prospect==0 || (prospect==offsets.length-1)){
valuep+=BONUS_POINTS_FOR_END_LIST;
}
if(numlists==1){
valuep+=(POINTS_FOR_TOTAL_LIST_WIDTH+POINTS_PER_BASE1)*chunk;
return ((long)(valuep*keyWeight))+valuem;
}
final int first=lists[0];
final int last=lists[numlists-1];
//Offsets of elements to the left and right of the prospect
// final int offL=(prospect==first ? - : offsets[lists[index-1]]);
// final int offP=offsets[prospect];
// final int offR=(prospect==last ? offsets[offsets.length-1] : offsets[lists[index+1]]);
// assert(offL<=offP);
// assert(offP<=offR);
// assert(offL<offR) : "\noffsets.length="+offsets.length+", lengths.length="+lengths.length+"\n"+
// ", chunk="+chunk+", lists.length="+lists.length+", index="+index+"\n"+
// ", offL="+offL+", offR="+offR+", prospect="+prospect+", first="+first+", last="+last+"\n"+
// ", valuep="+valuep+", valuem="+valuem+", weight="+keyWeight+"\n"+
// "offsets = "+Arrays.toString(offsets)+"\tlengths = "+Arrays.toString(lengths)+"\nlists = "+Arrays.toString(lists)+"\n";
final int offL=(prospect==first ? -1 : offsets[lists[index-1]]);
final int offP=offsets[prospect];
final int offR=(prospect==last ? offsets[offsets.length-1]+1 : offsets[lists[index+1]]);
assert(offL<=offP);
assert(offP<=offR);
assert(offL<offR) : "\noffsets.length="+offsets.length+", lengths.length="+lengths.length+"\n"+
", chunk="+chunk+", lists.length="+lists.length+", index="+index+"\n"+
", offL="+offL+", offR="+offR+", prospect="+prospect+", first="+first+", last="+last+"\n"+
", valuep="+valuep+", valuem="+valuem+", weight="+keyWeight+"\n"+
"offsets = "+Arrays.toString(offsets)+"\tlengths = "+Arrays.toString(lengths)+"\nlists = "+Arrays.toString(lists)+"\n";
int oldLeftSpace=offP-offL;
int oldRightSpace=offR-offP;
int newSpace=offR-offL;
// int oldLeftSpace=Tools.max((offP-offL)-1, 0)+1;
// int oldRightSpace=Tools.max((offR-offP)-1, 0)+1;
// int newSpace=Tools.max(offR-offL;
long spaceScore=((oldLeftSpace*oldLeftSpace+oldRightSpace*oldRightSpace)-(newSpace*newSpace))*MULT_FOR_SPACING_PENALTY;
assert(spaceScore>0) : "\n"+spaceScore+", "+oldLeftSpace+", "+oldRightSpace+", "+newSpace+"\n"+
Arrays.toString(offsets)+"\nprospect="+prospect+"\n";
valuep+=spaceScore;
int uniquelyCovered;
if(prospect==first){
uniquelyCovered=offR-offP; //Technically, -1 should be added
}else if(prospect==last){
uniquelyCovered=offP-offL; //Technically, -1 should be added
}else{
int a=offL+chunk;
int b=offR-a;
uniquelyCovered=(b>0 ? b : 0);
}
if(prospect==first || prospect==last){
valuep+=(POINTS_PER_BASE1+POINTS_FOR_TOTAL_LIST_WIDTH)*uniquelyCovered;
}else{
valuep+=POINTS_PER_BASE1*uniquelyCovered;
}
return ((long)(valuep*keyWeight))+valuem;
}
public static int[] toBitList(final int key){
final int numlists=Integer.bitCount(key);
final int[] lists=new int[numlists];
for(int i=0, ptr=0; ptr<numlists; i++){
if((masks32[i]&key)!=0){
lists[ptr]=i;
ptr++;
}
}
return lists;
}
public static int[] toBitList(final long key){
final int numlists=Long.bitCount(key);
assert(numlists>0);
final int[] lists=new int[numlists];
for(int i=0, ptr=0; ptr<numlists; i++){
if((masks[i]&key)!=0){
lists[ptr]=i;
ptr++;
}
}
return lists;
}
public static long evaluate(int[] offsets, int[] lengths, final int chunk, final long key){
long score=0;
final int[] lists=toBitList(key);
final int numlists=lists.length;
final int first=lists[0];
final int last=lists[numlists-1];
score+=numlists*POINTS_PER_LIST;
for(int i=0; i<numlists; i++){
int list=lists[i];
score+=POINTS_PER_SITE*lengths[list];
}
if(first==0){score+=BONUS_POINTS_FOR_END_LIST;}
if(last==offsets.length-1){score+=BONUS_POINTS_FOR_END_LIST;}
score+=(POINTS_FOR_TOTAL_LIST_WIDTH*(offsets[last]-offsets[first]+chunk));
//TODO: Special case both ends
for(int i=1; i<numlists; i++){
int list1=lists[i-1];
int list2=lists[i];
int space=offsets[list2]-offsets[list1];
int uncovered=space>chunk ? space-chunk : 0;
score+=MULT_FOR_SPACING_PENALTY*(space*space);
score-=POINTS_PER_BASE1*uncovered;
}
if(first>0){
long x=offsets[first];
score+=MULT_FOR_SPACING_PENALTY*(x*x);
score-=POINTS_PER_BASE1*x;
}
if(last<(offsets.length-1)){
long x=offsets[offsets.length-1]-offsets[last];
score+=MULT_FOR_SPACING_PENALTY*(x*x);
score-=POINTS_PER_BASE1*x;
}
return score;
}
public static final int BASE_POINTS_PER_SITE=-50; //Used to set POINTS_PER_SITE
public static long POINTS_PER_SITE=-50; //TODO: Make private with a get() and set() function
public static final long MULT_FOR_SPACING_PENALTY=-30;
public static long EARLY_TERMINATION_SCORE=(POINTS_PER_SITE*2000); //TODO: Should be set dynamically
public static final long POINTS_PER_LIST=30000;
public static final long POINTS_PER_BASE1=6000; //Points for a base covered once
public static final long POINTS_PER_BASE2=1000;//POINTS_PER_BASE1/4; //Points for a base covered twice
public static final long BONUS_POINTS_FOR_END_LIST=40000; //Extra points for the first and last list
public static final long POINTS_FOR_TOTAL_LIST_WIDTH=5500; //multiplier for distance between first and last list
public static final long[] masks=new long[64];
public static final int[] masks32=new int[32];
static{
for(int i=0; i<masks.length; i++){masks[i]=(1L<<i);}
for(int i=0; i<masks32.length; i++){masks32[i]=(1<<i);}
}
}
|
