this post was submitted on 23 Aug 2023
4 points (100.0% liked)

Programming Challenges

235 readers
1 users here now

Welcome to the programming.dev challenge community!

Three challenges will be posted every week to complete

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
4
[Easy] String Compression (programming.dev)
submitted 1 year ago* (last edited 1 year ago) by [email protected] to c/[email protected]
 

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:

all 15 comments
sorted by: hot top controversial new old
[–] [email protected] 2 points 1 year ago* (last edited 1 year ago) (1 children)

Factor:


USING: kernel strings command-line namespaces math.parser sequences io ;
IN: l

: c ( s -- C )
  "" swap
  [ dup empty? not ] [
    dup dup dup first '[ _ = not ] find drop
    dup not [ drop length ] [ nip ] if
    2dup tail
    [ number>string [ first 1string ] dip append append ] dip
  ] while drop
;

MAIN: [ command-line get first c print ]

Benchmark using compiled binary:

$ hyperfine "./compress/compress aaabbhhhh33aaa"

Benchmark 1: ./compress/compress aaabbhhhh33aaa
  Time (mean ± σ):       3.6 ms ±   0.4 ms    [User: 1.4 ms, System: 2.2 ms]
  Range (min … max):     3.0 ms …   6.0 ms    575 runs
[–] [email protected] 1 points 1 year ago* (last edited 1 year ago) (1 children)
  • 8/8 test cases passed
  • Time taken: 0.163 seconds
  • Characters: 359

I ran it using factor.com -run (path to file)

If theres a better way let me know, first time using factor

[–] [email protected] 1 points 1 year ago (1 children)

Thanks! Yeah to use the optimized compiler to create a faster runnable binary, I've put instructions on the first challenge: https://programming.dev/comment/1980496

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

new time taken: 0.053 seconds

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

Factor:

(command-line) last [ ] group-by [ length 48 + swap ] assoc-map "" concat-as print

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

Bun, technically prints it to the console: throw[...Bun.argv[2].matchAll(/(.)+?(?!\1)/g)].map(([a,c])=>c+a.length).join("")

Breaks if there are more than 9 repeats or if you don't supply an argument.

[–] [email protected] 2 points 1 year ago* (last edited 1 year ago)
  • 8/8 test cases passed
  • no runtime stats since I couldnt use the solution checker to check it (had to do manually)
  • Characters: 84
[–] [email protected] 2 points 1 year ago (1 children)

Python:

import sys

input_string = sys.argv[1]

compressed_string = ''
last_letter = ''
letter_count = 0

for letter in input_string:
    if letter != last_letter:
        if last_letter != '':
            compressed_string += last_letter + str(letter_count)
            letter_count = 0
        last_letter = letter
    letter_count += 1
compressed_string += last_letter + str(letter_count)

print(compressed_string)

[–] [email protected] 1 points 1 year ago* (last edited 1 year ago)
  • 8/8 test cases passed
  • time taken: 0.011s
  • characters: 385
[–] [email protected] 1 points 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])))

[–] [email protected] 2 points 1 year ago* (last edited 1 year ago)
  • 8/8 test cases passed
  • time taken: 0.191s
  • characters: 566
[–] [email protected] 1 points 1 year ago (1 children)
[–] [email protected] 1 points 1 year ago
  • 8/8 test cases passed
  • Time: 0.005s
  • Characters: 530
[–] [email protected] 1 points 1 year ago

My broken brain just goes "but how would a decompressor know if '3101' was originally '30' or 101 '3's in a row?"