osu!mania foo.bar

main.py

# Notes are represented by a bitmap:
# [column1, column2, column3, column4]
# [1      , 2      ,  4     , 8      ]
# e.g. a [13] chord has 1+4 = 5 as a value

##### #####

# A pattern is vibruh if
# * All jack notes are 1 index apart
# * There are >= 4 notes in the same column one after another
# * As long as 1 column satisfies the above, it is vibruh

# Translated into bitmap conditions, it means that
# 4 consecutive entries in an array should share a common bit,
# i.e. arr[i] & arr[i+1] & arr[i+2] & arr[i+3] > 0

# The naive algorithm would be to try and find the first index `i`
# where the above would be true, but iterating over lists in Python
# and checking for out of bounds seems annoying...
# (I don't do Python professionally please help)

# Therefore, the alternative is to keep track of a cursor:
# if it manages to last 4 times in a row above 0, then the pattern is vibruh
# if the end of the array is reached, then it is not vibruh

##### #####

# A pattern is manip if
# * All 4 columns have the same amount of notes
# * The gap between each successive note in each column must be <= 2
# * They are not vibruh

# Bitwise, we want to check for gaps of >2 to exit early
# That's essentially the same as vibruh but reversed (^15)

# We also have to keep track of the column balance,
# which can be done through xor'ing an accumulator
# and checking whether it's balanced in the end
# (either all 0s or 1s, so either 0 or 15, or x mod 15 = 0)

##### #####

# Additional optimization notes:
# * Avoiding array access at all costs (i.e. using x in arr instead of x in range(1, len(arr))) saves frames,
#   even with the extra loop iteration required. `for x in arr[1:]:` works and saves further frames,
#   but that involves cloning the list which is relatively costly, so we'd like to stay with `for x in arr`...
#   so we have to handle a special case to actually initialize variables
# * Booleans can just work as numbers as is (0 or 1) and the int() function has overhead
# * We can exit early for Vibruh, but Manip requires full iteration for note balance checks.
#   Therefore, since Vibruh early exits tend to be on the slight minority, it might be possible to gain time
#   through parallelization, advanced array reducing magic or in general, things that would bypass the requirement
#   of simple sequential iteration... which is hard to do because value-in-a-row checks have to be sequential.
#   I did not explore that route in the solution below (especially since any substantial improvement I reckon
#   might require SIMD, which seems to fall outside the scope of the rules... at least I haven't found any
#   built-in libraries that would allow me to play with it).

def solution(arr):
  first_pass = 1
  for x in arr:
    if first_pass:
      first_pass = 0
      vibruh_cursor = balance_cursor = x
      vibruh_count = x > 0
      blank_cursor = x ^ 15
      blank_count = blank_cursor > 0
    else:
      vibruh_cursor &= x
      if vibruh_cursor:
        if vibruh_count == 3:
          return 'Vibruh Gang'
        vibruh_count += 1
      else:
        vibruh_cursor = x
        vibruh_count = x > 0
      
      if blank_count != 3:
        balance_cursor ^= x
        blank_cursor &= x ^ 15
        if blank_cursor:
          blank_count += 1
        else:
          blank_cursor = x ^ 15
          blank_count = blank_cursor > 0
  return '' if blank_count == 3 or balance_cursor % 15 else 'Manip Gang'