The Bone Orchard

Personal Rating: Hard

For this coding challenge you have a web interface where you can test your code:

The requirements are explained quite well with the example. Below you can see my first attempt to solve this:

import sys

controlValues = sys.stdin.readline()
boneValuesRaw = sys.stdin.readline()
boneCount = int(controlValues.split(' ')[0])
tradeTarget = int(controlValues.split(' ')[1])
boneValues = []
for i in boneValuesRaw.split(' '):
    boneValues.append(i)

results = []

# calculate answer
for i in range(boneCount):
    for j in range(i+1, boneCount):
        if int(boneValues[i]) + int(boneValues[j]) == tradeTarget:
            tempresults = []
            tempresults.append(int(boneValues[i]))
            tempresults.append(int(boneValues[j]))
            tempresults.sort()
            if tempresults not in results:
                results.append(tempresults)

results = sorted(results,key=lambda x: (x[0],x[1]))

final = ""
print(len(results))
for i in range(len(results)):
    final = final + "("
    final = final + str(results[i][0])
    final = final + ","
    final = final + str(results[i][1])
    final = final + ") "
print(final)

This scipt worked offline, but the web page complained that the code was too slow. After a lot of googling and some AI assistance, this is what I came up with:

import sys

controlValues = list(map(int, input().split()))
boneValues = list(map(int, input().split()))
target = controlValues[1]

seen = set(boneValues)
results = set()

for value in boneValues:
    missingValue = target - value
    if missingValue in seen and value <= missingValue:
        results.add((value, missingValue))

results = sorted(results)
final = ""

for a, b in results:
    final += f"({a},{b}) "

print(len(results))
print(final.strip())

This script does the same task, but is much more efficient. While the first scripts time efficiency was O(n^2), this script can work with O(n). That is because it does not test every possible combination of two values, but rather goes through the values once and stores the ones that have been tested and the ones that fit the required combination along the way. Using a set instead of a list enables automatic deduplication.