Recreational coding thread

[root]

In this thread: anyone can share a programming problem and we will post solutions. The goal is to find solutions with impressive characteristics such as performance or brevity. This can be interpreted as recreational optimization or code golf.

Your first question (I will provide an example answer if there are no biters):

How would you locate gaps in a list of integers?

Example use case: determining which IDs have been deleted from a database

Example input: [1,3,4,5,8,9]

Example output: [2,6,7]

(Yes, this does not detect gaps at the tail of the list.)

[root]

Here is a naive implementation: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ce526c0085e7ca3ddda57d6a753ffe16

This iterates over the array several times when it should only be required to iterate once. Feel free to use any language or introduce your own problems!

Edited November 11, 2022 by root
added link

[Chauke]

function get_missing_ids(a) {
  var res = []
  var max = Math.max(...a);
  for (i = 1; i < max; i++) {
    var found = false
    a.forEach(element => {
      if (i == element) found = true
    });
    if (found == false) res.push(i)
  }
  return res
}

var a = [1, 3, 4, 5, 8, 9]
console.log(get_missing_ids(a))

[wacked]

$ python3 updatedsec.py
1
10
7
5
4
Missing:
2
3
6
8
9

from sys import stdin
arr = []
for x in stdin:
    arr.append(int(x))
arr = sorted(arr)
print("Missing:")
for i in range(len(arr)-1):
    if arr[i+1] - 1 != arr[i]:
        for x in range(arr[i]+1, arr[i+1]):
            print(x)

 

[root]

Here is an implementation that uses (I think) two iterations, one to sort and then one for the gap detection. The gap detection algorithm should be O(n) rather than O(n^2) like my last implementation.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f773c1d153eb55a2f0d07d0d71e9bb18

Edited November 13, 2022 by root