{}
// 2026-01-12
package eu.zrbj.socc;
public class SOCC14_Signal_from_Noise
{
public static final int EXPECTED_CHECKSUM = 2293; // for unit testing
public static final int MAX_VECTOR_LENGTH = 30;
/// whether to print the sequence information for each input vector; if not then the code will be run repeatedly
/// in order to show the speed-up when the bytecode gets jitted to native code instead of being interpreted
public static boolean g_PrintSequenceInfo = false;
public static void main (String[] ignored_args)
{
final int REPETITIONS = g_PrintSequenceInfo ? 1 : 7;
for (var round = 1; round <= REPETITIONS; ++round)
{
var t0 = System.nanoTime();
var input_string = CHALLENGE_INPUT_TEXT;
var input_chars = input_string.toCharArray();
var input_vector = new int[MAX_VECTOR_LENGTH];
int n = 0, checksum = 0;
for (int tail = 0, end = input_string.length(), head; tail < end; tail = head + 1, ++n)
{
head = input_string.indexOf('\n', tail);
if (head < 0)
head = end;
var newline_start = head - (head > tail && input_string.charAt(head - 1) == '\r' ? 1 : 0);
var value_count = parse_input_vector_(input_chars, tail, newline_start, input_vector);
insertion_sort_(input_vector, value_count);
var result = signal_from_noise_(input_vector, value_count);
checksum += result.Min() + result.Max();
if (g_PrintSequenceInfo)
System.out.println("#" + (n + 1) + ": " + result);
}
System.out.printf("%7.3f ms for %d sequences; checksum = %d%n", (System.nanoTime() - t0) / 1e6, n, checksum);
}
}
/// values that characterise a signal sequence, packaged as a record in order to facilitate unit testing
record SequenceInfo (int Min, int Max, int Dup, int Gap) { }
static SequenceInfo signal_from_noise_ (int[] sorted_values, int value_count)
{
int min = 0, dup = 0, gap = 0, best_min = 0, best_dup = 0, best_gap = 0, best_max = 0;
// the shortest legit signal sequence has length 3, so setting this to 2 helps skipping noise more efficiently
var best_score = 2;
var previous_value = sorted_values[0];
for (var i = 1; i < value_count; ++i)
{
var current_value = sorted_values[i];
var delta = current_value - previous_value;
previous_value = current_value;
switch (delta)
{
case 1: continue;
case 0: if (dup == 0) { dup = i; continue; } else break;
case 2: if (gap == 0) { gap = i; continue; } else break;
}
// the current sequence cannot be extended (although part of it may get recycled);
// if it can beat the high score and is compliant then set it as new best candidate
var score = i - min;
if (score > best_score && dup != 0 && gap != 0)
{
best_score = score;
best_min = min;
best_dup = dup;
best_gap = gap;
best_max = i - 1;
}
// the new current subsequence may recycle parts of the subsequence that just got retired
if (delta == 0) // implies dup != 0
{
// the sequence acquired a new dupe, so cut away everything before the old dupe
min = dup;
dup = i;
if (gap < min)
gap = 0;
}
else if (delta == 2) // implies gap != 0
{
// the sequence acquired a new gap, so cut away everything before the old gap
min = gap;
gap = i;
if (dup < min)
dup = 0;
}
else // unbridgeable gap -> nothing to recycle; restart candidate sequence from here
{
min = i;
dup = gap = 0;
}
}
// we may have a signal sequence that goes right up to the end of the sorted vector
var last_score = value_count - min;
if (last_score > best_score && dup != 0 && gap != 0)
{
best_min = min;
best_dup = dup;
best_gap = gap;
best_max = value_count - 1;
}
return new SequenceInfo(
sorted_values[best_min],
sorted_values[best_max],
sorted_values[best_dup],
sorted_values[best_gap] - 1 );
}
static void insertion_sort_ (int[] values, int value_count)
{
for (var i = 1; i < value_count; ++i)
{
var v = values[i];
var j = i;
do
{
var w = values[j - 1];
if (w <= v)
break;
values[j] = w;
}
while (--j > 0);
values[j] = v;
}
}
static int parse_input_vector_ (char[] s, int line_start, int line_end, int[] values)
{
if (line_end < line_start + 3 || s[line_start] != '[') // minimal valid input is '[0]'
{
return 0;
}
var i = line_start;
char c = s[++i];
for (int value_count = 0, limit = values.length; value_count < limit; )
{
var sign = 1;
if (c == '-')
{
sign = -1;
c = s[++i];
}
var digit = (char) (c - '0');
if (digit > 9)
break;
var value = (int) digit;
c = s[++i];
digit = (char) (c - '0');
if (digit <= 9)
{
value = value * 10 + digit;
c = s[++i];
digit = (char) (c - '0');
if (digit <= 9)
{
value = value * 10 + digit;
c = s[++i];
}
}
values[value_count++] = sign * value;
if (c == ']')
return value_count;
if (c != ',')
break;
if ((c = s[++i]) == ' ')
c = s[++i];
}
throw new IllegalArgumentException("invalid input or too many values");
}
// language level too low for text blocks at codingshuttle (at ideone, too, but they do not even support records)
@SuppressWarnings("TextBlockMigration")
static final String CHALLENGE_INPUT_TEXT =
"""
[135, 68, 67, 57, 56, 62, 63, 66, 62, 188, 65, 59, 64, 2, 55, 60, 69, 61, 70]
[-26, 274, -34, -38, -44, -37, -28, -183, -128, -249, -42, -43, -35, -36, -32, -33, -30, -39, -25, -41, -285, -25, -29, -31, -27, 132]
[288, 182, -57, -22, -181, -231, -24, -23, -28, -25, -26, -72, -29, -29, -21, -30]
[-81, -73, -85, 72, 2, -77, -80, -83, -77, -82, -86, -154, -92, -87, -74, -76, -78, -88, -90, -84, -79, -89, -75]
[261, 39, 37, 43, 49, 46, 248, 50, 31, 111, 32, 36, 199, 38, 40, 35, 44, 42, 35, 33, -221, 41, 193, 34, 48, 47]
[55, 44, 49, 52, 43, 43, 51, 56, 50, 54, 53, 48, 45, 46]
[84, 89, 91, -150, 87, 92, 80, 79, 95, 84, 82, 83, 90, -85, 94, 81, 88, 85, 243, 93, 251]
[-6, -7, -13, 266, 153, 93, 0, -10, -5, 62, -5, -9, -8, -14, 175, -11]
[144, -54, -47, -46, -6, -50, -134, -48, 69, -55, 232, -44, -72, -243, -49, -45, -44, -52, -51]
[91, 96, 92, 97, -64, 94, 90, 274, 92, 93, 100, 99, 95]
[-246, 73, -134, 78, 72, 79, 71, 32, 70, -197, 179, 64, 66, 67, 75, 77, 74, 65, -72, 36, 68, 69, 64, 80, 184]
[-77, -142, 28, 86, 295, 84, -260, 79, -199, 90, 91, 93, 87, -253, 89, 83, 93, -33, 161, 81, 244, 92, 82, 88, 85]
[37, 57, 69, -176, 66, 53, -286, 259, -284, 63, 65, 59, 62, -31, 67, 68, -277, 68, 60, 64, 58, 120]
[52, 47, 50, 56, 58, 57, 11, 57, 55, 45, 51, 54, -161, 101, 175, 59, 46, 48, 267, 24, 128, 130, -61, 53]
[-69, -61, -65, 228, -66, -70, -64, -63, -60, -62, -61, -59, -68]
[33, 36, 27, 31, 29, -207, 222, 32, 25, 182, 35, 30, 34, 26, 35, 104]
[-205, 90, -225, 89, -292, 97, 87, -56, 94, -119, 89, 88, -237, 98, 166, 147, 91, 99, 96, -17, 95, 93]
[-90, -77, -87, -78, -205, -83, -142, 86, -91, -295, -88, -81, 257, 254, -92, -89, -29, -86, -82, -79, -88, -80, -84]
[-196, -206, -80, -23, -17, -26, -22, -16, -167, -21, 245, -14, 221, -25, -27, -19, -27, -18, -20, -15]
[-67, 33, 62, 57, 52, 10, -87, 54, -205, 56, -31, 53, 59, 58, 53, 270, 60, 55]
[62, -66, 190, 49, 53, -164, 56, -197, 61, 52, 55, 60, 59, 54, 57, 143, 64, 50, 63, 54, 51]
[-186, -232, 9, 12, 13, 17, 214, 14, 17, 16, 7, 10, 15, 11]
[-203, -6, -14, -181, -7, -10, -13, -5, -50, -12, -8, -2, -3, -106, -9, 234, -4, -5]
[60, 55, 61, 54, 63, 126, 57, 59, 67, 56, 64, 69, 68, 70, 62, 53, -108, 58, 68, 66]
[16, 15, 12, -255, 109, 18, 19, 10, 20, 8, 13, 14, 18, -56, -250, 7, 23, 167, 17, -248, 11, 21, 9]
[26, -120, 23, 22, 31, 21, -271, -162, 30, 34, 80, 34, 36, 35, 32, 33, -39, 270, 37, 29, 145, 90, 28, 25, 27]
[-42, -116, -33, -52, -117, -37, -49, -35, -167, -39, -36, -41, -50, -49, -45, -83, -34, 82, -47, 51, -90, -48, -44, -43, -40, -277, -46, -38, 28]
[-13, -15, -12, -18, -19, -12, 57, -10, -11, -14, -17, 75]
[86, 89, 93, 88, 87, 87, 91, 84, 92, 85]
[-79, 295, -215, 110, -217, 112, 101, 105, 103, 106, -104, 99, 112, -145, 109, 111, -128, 108, 104, 107, -263, 102, -223]
[70, 94, 100, 89, 88, -158, 87, 98, 104, 297, 88, 92, 101, 91, 93, 102, 103, 96, 95, 90, 226, 289, 99]
[283, 86, 85, -51, 89, 96, -180, -254, 94, -185, 95, 93, 100, 90, 91, 87, 151, 101, -120, 98, 102, 92, 18, 94, 88, 97, 179]
[-19, 130, 91, -26, -23, 66, -39, 177, -22, 241, -24, 259, -28, -20, 201, -25, -16, -27, -18, -17, -22, -218]
[-59, -240, 289, -60, -52, -51, -58, -55, -61, -63, -57, -56, -52, -53, -81, 209, -54, -164, -35, 189, -50]
[109, 91, 94, -83, 95, 184, -274, 96, 93, 92, 83, 46, 82, 97, 83, 204, -56, 228, 84, 90, 86, 87, 89, 127, 85]
[-44, 105, 130, 97, -41, -48, -49, -45, 264, -46, -200, -41, -43, 65, -57, -115, -52, -42, -53, -55, 187, -56, 130, -51, -50, -47]
[53, 69, 64, 72, 63, 68, 56, 71, 69, 57, 58, 65, 62, 66, 107, 59, 70, 54, 55, 61, 67]
[-65, 222, -59, -67, -62, -57, -64, -55, -56, -63, -54, 6, -54, -53, -256, 29, -60, 207, -66, -58]
[0, -4, 0, -122, 6, -1, -2, 2, 7, 5, 4, -6, 1, 3, -5, 278]
[26, -68, 15, 10, -145, 22, 24, -295, 16, 14, 40, 13, 14, 9, -274, 19, 23, 12, 18, 20, 194, 17, 25, -68, 11]
[-60, -53, -55, -161, -263, -62, -61, -56, -52, -151, -59, 5, 175, -57, -55, -58]
[57, 49, 58, 46, 53, 51, 56, 50, -294, 52, 55, 56, 48, 47, 45]
[-69, -77, -70, 42, -82, -256, 148, -71, 158, -72, -239, -74, -79, -81, -48, -73, -75, -101, 21, -76, -80, -132, -72]
[263, 98, 97, -115, 102, 93, -171, 100, 219, 100, 106, 104, 95, 96, 105, -36, 99, 94, -144, 103, 92, 31]
[22, 187, 40, -244, -125, 39, 34, 112, -282, 27, 33, 23, 31, 38, -99, 37, 36, 25, 35, -63, 26, -187, 29, 30, -70, 28, 24, 25]
[-27, -31, -33, 284, -30, -26, 163, -32, -34, 73, -29, -32, -36, -35, 198]
[74, 80, 77, -142, 73, 53, 69, 68, 190, 74, -200, -220, 75, 67, 70, 72, -278, 76, 256, 122, 71, 79]
[-28, -31, -30, -32, -21, -22, -43, -265, -63, 36, -29, -20, -23, -18, 89, -25, -33, -27, -107, -266, -66, -22, -17, -26, -19]
[-56, -61, -65, -64, -61, -58, -55, -67, 221, -59, -68, -62, -63, -57, -60, -69, -54, -53]
[-30, -39, -24, -34, -35, -36, -27, -25, -23, 120, -32, -29, -17, -31, -40, -37, -40, -38, -28, -41, -33]
[124, -35, -44, -264, -47, -209, -104, -278, -34, -42, -41, -46, -40, -45, -42, -37, -43, 53, -71, -38, -48, -39]
[22, 19, 20, 15, 21, 17, 13, 16, 158, 18, 20]
[168, 130, 169, 42, 43, 80, 48, 41, 37, 35, 45, 40, -66, 43, 70, 221, 50, 44, 36, 46, 38, -17, 47, 39]
[-276, 102, 96, 104, 254, -263, 99, 98, 101, 105, 109, 107, 109, 106, 97, 103, 100, 85, -68, -123, -45, -149]
[98, -24, 104, 39, 41, 53, 40, 55, 248, 54, 242, 45, 27, 52, 43, 48, 50, 41, 116, 56, 46, 44, 42, 51, 47]
[-276, 52, 56, 50, 47, 55, 138, 51, 48, 46, 55, 53, 59, 58, 54, 57, 49, 44]
[37, 39, 42, 39, -208, -18, 38, 46, -121, 43, 44, -138, 48, 45, 40, 47]
[66, 69, 166, -261, -33, 60, 62, -95, 65, 201, 67, 59, 68, 108, 66, 63, 70, 61, 244, 175, -255, -250]
[-128, -15, -8, -15, -5, -16, -190, 281, 40, -9, -17, -14, -152, -10, -11, -13, -193, -12, 165, -18, -7, -77]
[257, -24, 100, -27, 62, -201, -37, -19, -22, -33, -21, -23, -25, -26, -36, -20, -34, -30, -105, -36, -31, -28, -35, -32]
[8, 1, 8, 2, -1, 9, 0, 5, 3, -2, 6, 4, -92, -96, 269]
[38, -45, 32, 28, 24, 36, -21, 37, 34, 39, 29, 35, -218, 236, 27, 31, 26, 207, 294, -29, 37, -137, 25, 30]
[-25, -18, 152, -24, 119, 103, 14, -17, -20, -18, -21, -19, -22, -26, -160, -27, -28]
[67, 80, 77, 76, 68, 75, 84, 176, 71, 72, 74, 85, -56, 81, 78, 210, 75, 86, 83, 69, 79, 70, 73]
[-80, -79, 30, -83, -235, -85, -79, -78, 194, -82, -11, 90, -89, -90, -86, -196, 235, -274, -81, 181, -88, -87]
[-88, -90, 35, -97, -95, -96, 35, -93, -99, -92, -94, -98, -89, -97]
[-36, -32, -31, -33, -26, -30, -24, -27, -23, -99, -179, -25, -35, -37, 279, -28, 245, -35, -34, -206]
[49, 39, 45, 81, 43, 48, 53, -143, 51, 231, 198, 50, 47, 41, 44, 47, -245, 46, 42, 40]
[-22, -32, -21, -33, -27, -19, -29, -31, -23, -17, 127, -30, -28, -293, -268, -20, -173, -63, -15, -25, -83, -24, -65, -33, -26, 272, -16]
[-65, -57, 117, -64, -58, -66, -61, -63, -56, -69, 272, -62, -55, -60, -67, -23, -55, -68]
[-29, -33, -38, -36, -39, -25, -25, -40, -32, -34, -24, -31, -41, -288, -26, -28, -35, -37, -142, -27, -23]
[-6, 3, 4, -4, 0, -5, -7, -11, 228, 92, 9, 5, -9, 204, -10, -2, -129, 4, -12, -194, -8, 2, -1, 241, -13, 127, -210, 198, -3, -14]
[112, 109, 237, 116, 104, 100, 108, 102, 101, 106, 103, 110, 107, 114, 117, 115, 83, 99, 114, 113, 111]
[14, 5, -104, 9, 15, 11, 6, 12, -258, 11, 13, 47, 8, 7, -232]
[23, 27, 31, 81, -80, 35, 124, 30, 25, 29, 22, 37, 26, 32, 28, 34, 33, 36, 36, 21, 20]
[-49, -44, -47, -38, -31, -50, -37, -36, -35, -48, -46, -40, -152, -41, -32, -43, -37, -42, -33, -39, -34]
[-1, -69, -70, -67, -76, -66, -76, -61, -65, -77, -68, 194, 161, -71, -74, -78, -73, -72, 81]
[-24, -31, -144, -28, -27, 143, -24, -34, -35, -22, 248, -32, -103, -29, -20, 124, -30, -33, 185, 115, 223, -26, -91, -36, -21, -97, -23]
[-58, -56, -54, -53, -49, -57, 65, -59, -60, -49, -52, -61, -62, -55, -50]
[58, 50, 57, 53, 54, 51, 48, 52, 23, 55, 56, 53, -49]
[63, 58, 57, 123, 56, 54, 55, 29, 57, -190, -211, 62, 60, 61, 64, 52, -138, 59, 79, -181, 51]
[81, -17, -163, 88, 89, 83, 90, 82, 291, 79, 84, 84, 92, 80, 70, 50, 96, 94, 131, 87, 86, 85, 91, 95, -202, -300, 93, 98, 146]
[-73, -74, -66, -65, -75, 175, -72, -69, -76, -72, -67, -70, -68, -64]
[86, 125, 80, 84, 92, 83, 89, 77, 96, 81, 91, 87, 84, 88, 97, 133, 98, 90, 93, 85, 94, 78, 50, 82]
[-153, 26, 221, 33, 25, 32, 29, 35, 30, 34, -96, 259, 27, 22, 38, 21, 28, 7, 203, 31, 37, -279, -215, 22, 257, 36, 23]
[95, 89, 92, -175, 80, 13, 88, 85, 83, 84, 90, 80, 93, 82, 81, 94, 86, 91]
[-22, -237, -24, -216, -13, 220, -21, 84, -14, -19, -13, -16, -30, -20, -17, -12, -11, -25, -23, -18, -244]
[-8, -6, -10, -12, -9, -3, -5, -13, 4, -2, 1, 6, -109, -11, 5, 3, 251, -13, 0, -4, -7, 2]
[-10, -2, -218, 2, -257, 0, -1, -201, -3, 1, -8, -4, -13, -13, -20, 278, -5, 5, -196, -11, -6, -7, -9]
[9, 9, 11, 182, 8, -184, 298, -279, 30, 7, 2, 10, -298, 3, 12, -137, 13, 5, 4, 46]
[81, -196, 75, 72, -146, 84, -111, 73, 83, 269, -184, 78, -50, 80, 71, 74, -122, 139, 77, 135, 77, 79, 76, -107]
[-14, -30, -28, -24, -16, -23, -13, 207, -20, -18, -25, -27, -15, -29, 12, -19, -17, -15, -26, -21]
[-92, -94, -88, -90, -84, -89, -91, -80, -76, -82, -75, -87, -77, -6, -91, -79, -83, -78, -85, -93, -286, -86]
[74, 235, 42, 27, 72, 75, 68, 76, 79, 70, 69, 75, 78, 73, 77]
[-127, -35, -24, -33, 188, -34, -27, -29, -37, -27, -25, -38, -23, -28, -30, -207, -31, -36, -32]
[-257, 85, 88, 79, 134, 0, 91, 74, 82, 76, 72, 38, 73, 78, 90, 80, 86, 84, -177, 75, 73, 89, 187, 83, -72, 81, 234, 87]
[154, 31, -114, -196, 174, -268, 20, 22, 29, 27, 25, 21, 30, 23, 28, 24, 26, 20, 33]
[-57, -89, -278, -82, -91, -86, -88, -251, -87, 69, -82, 54, -96, -94, -92, -84, -164, -95, 36, -90, 60, -85, -83, 273]
[-43, -174, -40, -39, -42, -35, -40, -37, -217, -41, -44, -205, -38]
[-68, 169, -78, -74, -63, -239, -69, -72, -64, 243, -81, 224, -76, -79, -77, -67, -75, -73, 112, -81, -71, -70, -65, -66, -50]
""";
}