1-4 lines, Ruby and Python


  • 20

    To identify each group, compute the modulo 26 difference between each letter in a word with the first letter in it.

    Note: Originally the problem required each group to be sorted. Not anymore. I now added adapted solutions but kept the old ones.

    Solution 1: Ruby with group_by

    def group_strings(strings)
      strings.group_by { |s| s.bytes.map { |b| (b - s[0].ord) % 26 } }.values
    end
    

    Old solutions:

    def group_strings(strings)
      strings.sort.group_by { |s| s.bytes.map { |b| (b - s[0].ord) % 26 } }.values
    end
    

    Can be a bit faster to group first and sort (each group) afterwards:

    def group_strings(strings)
      strings.group_by { |s| s.bytes.map { |b| (b - s[0].ord) % 26 } }.values.map &:sort
    end
    

    Solution 2: Python with groupby

    def groupStrings(self, strings):
        key = lambda s: [(ord(c) - ord(s[0])) % 26 for c in s]
        return [list(g) for _, g in itertools.groupby(sorted(strings, key=key), key)]
    

    Old solution:

    def groupStrings(self, strings):
        key = lambda s: [(ord(c) - ord(s[0])) % 26 for c in s]
        return [sorted(g) for _, g in itertools.groupby(sorted(strings, key=key), key)]
    

    Solution 3: Python with defaultdict

    def groupStrings(self, strings):
        groups = collections.defaultdict(list)
        for s in strings:
            groups[tuple((ord(c) - ord(s[0])) % 26 for c in s)] += s,
        return groups.values()
    

    Old solution:

    def groupStrings(self, strings):
        groups = collections.defaultdict(list)
        for s in strings:
            groups[tuple((ord(c) - ord(s[0])) % 26 for c in s)] += s,
        return map(sorted, groups.values())

  • 0

    Hi, Stefan. It seems that you are now practicing your golfing skills? :-)


  • 0

    Nah, these are really not golfing. In code golf you try to solve the problem in as few key strokes as possible, just like in real golf you try to get the ball into the hole in as few strokes as possible. And readability/efficiency don't matter.

    In the above solutions, I could save a lot of key strokes. Most of the space could be removed. There are variable names longer than one letter. And I hadn't even tried to look for clever dirty tricks to sqeeze out more strokes. Here's an actually golfed version of solution 3, for example:

    def groupStrings(self, S):
     g=collections.defaultdict(list)
     for s in S:g[`[(ord(c)-ord(s[0]))%26for c in s]`]+=s,
     return map(sorted,g.values())
    

    My above solutions are just straight-forward regular solutions. They might be Spartan programming, which I recently saw when I showed you Wikipedia's code golf article. But they don't compromise readability or efficiency. Except for one subtle thing in the Ruby solution. Can you find it? :-)


  • 0

    Hi, Stefan. I now see that your second Python solution is quite clear. Possibly I have first read your Ruby solution and the Java solution in another post and just got crazy about them since I cannot understand almost any of them :-)

    BTW, I know too little about Ruby and Spartan programming and just fail to find the subtle thing. Could you tell me :-)


  • 0

    Heh, I think for someone familiar with Ruby, Python and Java streaming, those solutions are pretty straight-forward and easy to understand :-)

    The subtle thing is a small compromise of efficiency. I sort first and group afterwards. It can be a bit faster to group first and sort (each group) afterwards. That could look like this (maybe I'll add it above):

    strings.group_by { |s| s.bytes.map { |b| (b - s[0].ord) % 26 } }.values.map &:sort

  • 0
    I

    Solution 2: Python with groupby may be improved a little bit by excluding the first char from the key

        key = lambda s: [(ord(c) - ord(s[0])) % 26 for c in s[1:]]
        return [sorted(g) for _, g in itertools.groupby(sorted(strings, key=key), key)]
    

  • 0

    No, then it fails for example ["", "a"].


  • 0
    I

    whether "" is a valid input is not well defined in the question. Right now it passes all tests


  • 0
    I

    I really enjoy reading your solutions.

    Could you tell me Solution 3: Python with defaultdict why you use

    groups[tuple((ord(c) - ord(s[0])) % 26 for c in s)] += s,
    

    instead of

    groups[tuple((ord(c) - ord(s[0])) % 26 for c in s)].append(s)

  • 1

    I often use += something,

    • because it's shorter
    • because it looks nicer if something is something big
    • to puzzle people and to teach them about the comma :-)

  • 0

    Yes, it passes the current tests, but the empty string is a completely normal string, so if it's not ruled out, I consider it valid input.


  • 0
    Z

    @StefanPochmann Hi, I have 2 issues:

    • What is the need for %26 in python tuple? I don't think %26 will affect the result at all.

    • += operator for defaultdict on my machine gives different result.

        from collections import defaultdict
        d = defaultdict(list)
        d[(1,2)] += '123'
        d[(1,2)] += '1'
        print(d.values())
      

      If I run the above code, it prints

        [['1', '2', '3', '1']]

  • 0
    Z

    @zhahaoyu

    1. z can be shift to a
    2. d[(1, 2)]+= '123' != d[(1,2)] += '123',

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.