Cold Code Challenge - Random Large Integer Sorting Edition

Objective

Solve an algorithmic problem involving sorting an array of random unique large integers, and return a specific compressed part of the output. The solution that consumes the least energy wins.

Problem

Advent of Energy: You are given an array of random unique integers, and you need to sort them in non-decreasing order. Instead of outputting the entire sorted array, your task is to calculate the sum of all elements in the sorted sequence, where each element is multiplied by its position index (starting from 0).

Input:

A random array of unique integers of size up to 1,000,000, with values represented as 64-bit signed integers, ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.

Output:

Calculate the sum of all elements in the sorted array, where each element is multiplied by its position index (starting from 0), and print this sum.

Constraints

Execution Time Limit: The solution must terminate within 30 seconds for all inputs. Solutions that do not complete before the timeout will be discarded.
Platform: All submissions will be run on a standardized hardware setup (Intel® Core™ i9-13900H) with Ubuntu 22.04 for fair comparison of energy consumption.
Language Support: Submissions can be made in C, C++, Python, Go, Rust, Scheme, Racket, or Assembly.
Energy Profiling Tool: Solutions will be evaluated using Intel's RAPL or similar energy measurement tools.
Submission Requirements: Each submission must be a single source file. Participants must also provide the command line used to build the executable binary, which must rely only on packages and dependencies available in the Ubuntu 22.04 package repository.
Implementation Restrictions: The sorting algorithm must be an original implementation, and participants are not allowed to use existing sorting library functions (e.g., sorted() in Python or std::sort in C++). However, performance libraries such as NumPy, OpenBLAS, SIMD intrinsics, etc., may be used for optimization.
Submission Requirements: Each submission must be a single source file. Participants must also provide the command line used to build and run the solution, which must rely only on packages and dependencies available in the Ubuntu 22.04 package repository.

Submission Limit

Participants are allowed to submit their solution up to three times. The first two submissions can be used to get feedback on execution time and energy consumption, and the third submission will be considered the final one.

Evaluation Criteria

Correctness: The sum must be computed correctly.
Energy Consumption: The average energy consumption will be recorded over multiple runs of various array size and content, and the solution with the lowest average energy wins. In case of close ties (taking into account noise from multiple runs), solutions will be ranked based on execution time as the second criterion.
Execution Time: The time limit for each execution is capped at 30 seconds.

Example Solution (Python - Sum Version with Integers)

import sys

def energy_efficient_sort(arr):
    sorted_arr = sorted(arr)
    # Calculate the sum of all elements, each multiplied by its position index (starting from 0)
    return sum(i * sorted_arr[i] for i in range(len(sorted_arr)))

if __name__ == "__main__":
    # Read input from file
    if len(sys.argv) != 2:
        print("Usage: python solution.py <input_file>")
        sys.exit(1)
    
    input_file = sys.argv[1]
    with open(input_file, 'r') as f:
        arr = [int(line.strip()) for line in f]
    
    result = energy_efficient_sort(arr)
    print(result)

Sample Input File

Create a text file named input.txt with each integer on a new line. For example:

You can then run the example solution with the command:

python3 solution.py input.txt

This last command should print:

2193160920

Use the following command to measure energy consumption:

perf stat -e power/energy-pkg/ python3 solution.py input.txt

Measurement Process

Run the Code: Each solution will be executed on the same hardware platform, with energy consumption measured using the profiling tool.
Energy Profiling Command: A script will manage the execution, ensuring energy usage is recorded accurately.

4.5 KiB Raw Permalink Blame History