Programming Challenges

233 readers

1 users here now

Welcome to the programming.dev challenge community!

Three challenges will be posted every week to complete

Tuesday (Easy)
Thursday (Medium)
Saturday (Hard)

Easy challenges will give 1 point, medium will give 2, and hard will give 3. If you have the fastest time or use the least amount of characters you will get a bonus point (in ties everyone gets the bonus point)

Exact duplicate solutions are not allowed and will not give you any points. Submissions on a challenge will be open for a week.

A leaderboard will be posted every month showing the top people for that month

founded 1 year ago

MODERATORS

Ategon

[Easy] String Compression (self.challenges)

submitted 1 year ago* (last edited 1 year ago) by Ategon to c/challenges

20 comments fedilink hide all child comments

Given a string, compress substrings of repeated characters in to a format similar to aaa -> a3

For example for the string aaabbhhhh33aaa the expected output would be a3b2h432a3

You must accept the input as a command line argument (entered when your app is ran) and print out the result

(It will be called like node main.js aaaaa or however else to run apps in your language)

You can use the solution tester in this post to test you followed the correct format https://programming.dev/post/1805174

Any programming language may be used. 1 point will be given if you pass all the test cases with 1 bonus point going to whoevers performs the quickest and 1 for whoever can get the least amount of characters

To submit put the code and the language you used below

People who have completed the challenge:

@[email protected] - N/A - 84 chars (javascript)
@[email protected] - 0.011s - 385 chars (python)
@[email protected]
- 0.003s - 487 chars (c) (fastest)
- 0.01s - 60 chars (javascript) (shortest)
@[email protected] - 0.005s - 530 chars (rust)
@[email protected] - 0.191s - 566 chars (python)
@[email protected] - 0.053s - 359 chars (factor) If you submitted in factor, ruby, cobol, etc. itll take me a bit longer to check since I havent set up running those yet. Should be soon

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 2 points 1 year ago* (last edited 1 year ago) (1 children)

My solution (runs in O(n) time, but so do all the other solutions so far as far as I can tell):

from itertools import pairwise

def main(s: str) -> str:
    characters = [None] + list(s) + [None]
    transitions = []
    for (_, left), (right_idx, right) in pairwise(enumerate(characters)):
        if left != right:
            transitions.append((right_idx, right))
    repeats = [(stop - start, char) for (start, char), (stop, _) in pairwise(transitions)]
    return ''.join(f'{char}{length}' for length, char in repeats)

if __name__ == '__main__':
    from argparse import ArgumentParser
    parser = ArgumentParser()
    parser.add_argument('s')
    print(main(parser.parse_args().s))

Runthrough:
'aaabb' -> [None, 'a', 'a', 'a', 'b', 'b', None] -> [(1, 'a'), (4, 'b'), (6, None)] -> [(4 - 1, 'a'), (6 - 4, 'b')]

Golfed (just for fun, not a submission):

import sys
from itertools import pairwise as p
print(''.join(c+str(b-a)for(a,c),(b,_)in p([(i,r)for i,(l,r)in enumerate(p([None,*sys.argv[1],None]))if l!=r])))

[–] Ategon 2 points 1 year ago* (last edited 1 year ago)

8/8 test cases passed
time taken: 0.191s
characters: 566