Skip to content

Instantly share code, notes, and snippets.

@glenbot
Created September 7, 2018 03:46
Show Gist options
  • Save glenbot/69b2584ba94e498c5cfdd8ba8b905499 to your computer and use it in GitHub Desktop.
Save glenbot/69b2584ba94e498c5cfdd8ba8b905499 to your computer and use it in GitHub Desktop.
ACSL 2018 Compressed Lists Problem
#!/usr/bin/env python
"""
http://www.acsl.org/17-18/allstar/2.%20Compressed%20Lists.pdf
"""
import fileinput
from collections import Counter
def compress_list(_list, frequency, out=None):
if out is None:
out = set([])
frequency_check_list = [x[1] for x in _list if x[0] == frequency]
for i in frequency_check_list:
out.add(i)
try:
terms = [_list.pop(0), _list.pop(0)]
except IndexError:
out = sorted(''.join(out))
out = ''.join(out)
if not out:
out = 'NONE'
return out
frequency_total = 0
letters = ''
for term in terms:
_frequency, _letters = term
frequency_total += _frequency
letters += _letters
compressed = (frequency_total, ''.join(sorted(letters)))
_list.append(compressed)
_list = sorted(_list, key=lambda x: (x[0], x[1]))
return compress_list(_list, frequency, out)
def run(string, frequency):
counter = Counter(string)
frequency_list = list(zip(counter.values(), counter.keys()))
sorted_list = sorted(frequency_list, key=lambda x: (x[0], x[1]))
print(compress_list(sorted_list, frequency))
if __name__ == '__main__':
for line in fileinput.input():
string, frequency = line.split()
if string.startswith('#'):
continue
print(string, frequency)
run(string, int(frequency))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment