test.py

from collections import defaultdict, Counter
from pathlib import Path

import timeit


def sol_0():
    """1138 sec / 100 executions (11.38 sec / 1 execution)"""
    l_set = set(rooms) # O(n)
    for i in l_set:  # O(n), so O(n^2) if we take into consideration the rooms.count being called
        c = rooms.count(i)  # O(n)
        if c == 1:
            return i


def sol_1():
    """15.57 sec / 100 executions"""
    room_counts = dict()

    for room in rooms:  # O(n)
        # Trying to get the count of room `room`, if no element in dict .get returns 0
        room_counts[room] = room_counts.get(room, 0) + 1

    for room_no, count in room_counts.items():  # O(n)
        if count == 1:
            return room_no


def sol_2():
    """9.25 sec / 100 executions"""
    # A little optimisation to sol_1: defaultdict automatically creates
    # new int (with value 0) on an attempt to access nonexcistent element
    room_counts = defaultdict(int)

    for room in rooms:  # O(n)
        room_counts[room] += 1

    for room_no, count in room_counts.items():  # O(n)
        if count == 1:
            return room_no


def sol_3():
    """6.77 sec / 100 executions"""
    # Working with only one pass, not counting the number of rooms
    # If we looked at the room once - it goes into capitan_rooms
    # If we find the same room again - it is removed from capitan_rooms
    # and goes into tourist_rooms

    # At the end capitan_rooms should contain only one room

    # Adding/looking up/removing from the set is an O(1) operation

    capitan_rooms = set()
    tourist_rooms = set()

    for room in rooms:  # O(n)
        if room in capitan_rooms:  # O(1)
            capitan_rooms.remove(room)  # O(1)
            tourist_rooms.add(room)  # O(1)
        else:
            if room not in tourist_rooms:  # O(1)
                capitan_rooms.add(room)  # O(1)

    return capitan_rooms.pop()


def sol_4():
    """5.78 sec / 100 executions"""
    # Using standard lib tools usually is the fastest, because
    # it is heavily optimized and written in C
    # Counter counts elements, we take the list of most_common
    # and look at the last [-1] element - least common

    return Counter(rooms).most_common()[-1][0]  # O(n)

def sol_5():
    """3.31 sec / 100 executions"""
    # Slight reordering of operations in sol_3

    capitan_rooms = set()
    tourist_rooms = set()

    for room in rooms:  # O(n)
        if room not in tourist_rooms:  # O(1)
            if room in capitan_rooms:  # O(1)
                capitan_rooms.remove(room)  # O(1)
                tourist_rooms.add(room)  # O(1)
            else:
                capitan_rooms.add(room)  # O(1)

    return capitan_rooms.pop()

# testing with huge input03 file, Download it from hackerrank and remove first line


rooms = list(
    map(
        int,
        (Path.home() / 'Downloads' / 'input03.txt').read_text().split()
    )
)
print(f'sol_0 (1 execution): ', timeit.timeit(f'sol_0()', globals=globals(), number=1))
for i in range(1, 6):
    print(f'sol_{i} (100 executions: ', timeit.timeit(f'sol_{i}()', globals=globals(), number=100))