code-golf-in-ruby-KRUG-2024

Code golf

in Ruby

⛳

Radosław Bułat [github] [discord] KRUG, 17.09.2024

Before we start…

Agenda

What is code golf?
Out first challenge
Magic moments
Where to golf?
Summary

What is the code golf?

Code golf is a discipline

in which we solve programming challenges

using the fewest characters possible.

Just like in real golf we want to reach the goal ⛳ with as few strokes 🏌 as possible.

The most important criteria are:

correctness
code length (the less the better)

Our first challenge

Write a code that takes a string and returns first word that is repeated.

Words are separated by spaces and are all lowercase.

"dom kot pies okno żyrandol pies dom szafa" -> "pies"
 ---     ----               ---- ---

Let’s start with ungolfed version.

def first_repeating_word(string)
  words = string.split
  seen = {}

  words.find do |word|
    if seen[word]
      true
    else
      seen[word] = true
      false
    end
  end
end

first_repeating_word(
  "dom kot pies okno żyrandol pies dom szafa"
) #=> "pies"

183 bytes

This is our starting point.

Let’s see how much we can shrink it!

Let’s apply golf tricks one by one.

Use single letter names for everything.

first_repeating_word -> f string -> s words -> a word -> w

def f(s)
  a = s.split
  h = {}

  a.find do |w|
    if h[w]
      true
    else
      h[w] = true
      false
    end
  end
end

128 bytes

Remove unnecessary spaces.

h = {}

h={}

do |w|

do|w|

etc.

def f(s)
a=s.split
h={}
a.find do|w|
if h[w]
true
else
h[w]=true
false
end
end
end

82 bytes

Use `{}` blocks instead of `do end`.

a.find do|w|
end

a.find{|w|
}

def f(s)
a=s.split
h={}
a.find{|w|
if h[w]
true
else
h[w]=true
false
end
}
end

78 bytes

Do not use variables

if they are not needed.

a=s.split
a.find{|w|

s.split.find{|w|

def f(s)
h={}
s.split.find{|w|
if h[w]
true
else
h[w]=true
false
end
}
end

74 bytes

Use `?:` ternary if operator instead of `if else end`.

if condition
  expression1
else
  expression2
end

condition ? expression1 : expression2

def f(s)
h={}
s.split.find{|w|
h[w]?true:(h[w]=true;false)
}
end

64 bytes

Use lambda `->` instead of method definition.

def f(s)
end

f=->s{}

f=->s{
h={}
s.split.find{|w|
h[w]?true:(h[w]=true;false)
}
}

60 bytes

Remove unnecessary new lines.

Other new lines replace with `;`

(just for convenience ;-))

f=->s{h={};s.split.find{|w|h[w]?true:(h[w]=true;false)}}

56 bytes

Use shorter truthy expressions than `true` literal.

Everything except false and nil is treated as true in conditions.

0
1
"f"
:f
{}
[]
# all are truthy

f=->s{h={};s.split.find{|w|h[w]?1:(h[w]=1;false)}}

50 bytes

Use shorter falsy expressions than `false` literal.

!0
!1
!"f"
!:f
!{}
![]
# all are falsy

Is there a 1 character expression which evaluates to `falsy` value?

p

???

Kernel#p

p(1) # prints 1, returns 1
p()  # prints nothing, returns nil
p    # prints nothing, returns nil

f=->s{h={};s.split.find{|w|h[w]?1:(h[w]=1;p)}}

46 bytes

Use `_1`, `_2` block variables

f=->s{h={};s.split.find{h[_1]?1:(h[_1]=1;p)}}

45 bytes

Now the fun begins!

h[_1]?1:(h[_1]=1;p)

h[_1]?1:!h[_1]=1

f=->s{h={};s.split.find{h[_1]?1:!h[_1]=1}}

42 bytes

h[_1]?1:!h[_1]=1

h[_1]||!h[_1]=1

f=->s{h={};s.split.find{h[_1]||!h[_1]=1}}

41 bytes

h[_1]||!h[_1]=1

!h[_1]=!h[_1]

f=->s{h={};s.split.find{!h[_1]=!h[_1]}}

39 bytes

h={};

->s,**h{} # use ruby keyword arguments

f=->s,**h{s.split.find{!h[_1]=!h[_1]}}

38 bytes

h[_1]=!h[_1]

nil^1  #=> true
true^1 #=> false

h[_1]=h[_1]^1
h[_1]^=1

f=->s,**h{s.split.find{!h[_1]^=1}}

34 bytes

Before vs After

def first_repeating_word(string)
  words = string.split
  seen = {}

  words.find do |word|
    if seen[word]
      true
    else
      seen[word] = true
      false
    end
  end
end

f=->s,**h{s.split.find{!h[_1]^=1}}

Evolution of solutions

f=->s{h={};s.split.find{|w|h[w]?true:(h[w]=true;false)}}
f=->s{h={};s.split.find{|w|h[w]?1:(h[w]=1;false)}}
f=->s{h={};s.split.find{|w|h[w]?1:(h[w]=1;p)}}
f=->s{h={};s.split.find{h[_1]?1:(h[_1]=1;p)}}
f=->s{h={};s.split.find{h[_1]?1:!h[_1]=1}}
f=->s{h={};s.split.find{h[_1]||!h[_1]=1}}
f=->s{h={};s.split.find{!h[_1]=!h[_1]}}
f=->s,**h{s.split.find{!h[_1]=!h[_1]}}
f=->s,**h{s.split.find{!h[_1]^=1}}

Conclusions

We ended up with short and quite cryptic but functionally the same code.

Doesn’t it sound like a fun?

The alphabet

Single character strings

"a"
"?"
"ę"

?a    #=> "a"
??    #=> "?"
?ę    #=> "ę"

SIDEQUEST

Can you parse this?

(Ruby can)

?????:??

?? ? ?? : ??

"?" ? "?" : "?" #=> "?"

Array#join

[1,2,3,4].join    #=> "1234"
[1,2,3,4].join"x" #=> "1x2x3x4"

[1,2,3,4]*''      #=> "1234"
[1,2,3,4]*"x"     #=> "1x2x3x4"

[1,2,3,4]*?x      #=> "1x2x3x4"

Array#uniq

a=[1,2,3,1,2]

a.uniq

a&a
a|a
a|[]

n+1, n-1

n+1
n-1

-~n
~-n

What’s the point?

m*(n+1)
m*-~n

Why it works?

~ negates (flips) all bits

5 (dec) is 0000 0101 (bin)

~5 (dec) is 1111 1010 (bin)

which is exactly -6 in two’s complement representation

-(-6) == 6 == 5+1

Operator methods

"%f"%(1.0+0.5)

"%f".%1.0+0.5

reduce:*

[1,2,3,4].reduce:*    #=> 24

eval [1,2,3,4]*?*     #=> 24

There are many more things like this.

Discovering them is just fun!

Magic moments

The story of one challenge

Levenshtein Distance

https://code.golf/levenshtein-distance#ruby

$ ruby solver.rb "foo fo" "bar na"
1
2

Usually means one of:

the problem is simple to solve
the solution is available publicly
there is a built-in

1st and 2nd were eliminated.

Searching in the source code I found a method

DidYouMean::Levenshtein.distance("foo", "fo") #=> 1

That lead me to 52 bytes solution

$*.map{p DidYouMean::Levenshtein.distance *_1.split}

I was about to stop here but…

…I found this

$ cd ~/.rbenv/versions/3.1.0/lib/ruby
$ grep -Ri levenshtein .
(...)
./3.1.0/rubygems/text.rb:
# Vendored version of DidYouMean::Levenshtein.distance from \
the ruby/did_you_mean gem @ 1.4.0

Vendored version of DidYouMean::Levenshtein.distance
                    --------------------------------

It looked like the code in my solution

🤔

Then I checked this…

…and this

file rubygems/text.rb is autoloaded
path to the file is in $"[20]
the file contains the longest part of the code

This is what I came up with

eval"$*.map{p#{IO.read$"[20],34,1280}*_1.split}"

IO.read$"[20],34,1280

" DidYouMean::Levenshtein.distance "

eval"$*.map{p DidYouMean::Levenshtein.distance *_1.split}"

😈

$*.map{p DidYouMean::Levenshtein.distance *_1.split}

52 bytes

eval"$*.map{p DidYouMean::Levenshtein.distance *_1.split}"

48 bytes

Unfortunately in the current version of rubygems the text.rb file is no longer autoloaded. This solution doesn’t work anymore.

How to get started?

The best way is…

…to challenge your friends!

Where to golf?

code.golf - hidden solutions, rankings, many languages
codegolf.stackexchange.com - public solutions
codingame.com - private clashes
golf.shinh.org - very oldschool but many public solutions

Summary

Technically, code golf is all about shortening code.

However, to achieve this we have to explore different solutions and push language features to the limits.

At the same time, having full control over the code.

Although in a specific way, it creates great conditions for expanding knowledge about the language and its intricacies.

Thank you!

Wait!

I have 2 challenges for you

Challenge 1

Write a Ruby program that prints all numbers of regular trams in Kraków in ascending order.

Regular trams: 1 3 4 5 8 9 10 11 13 14 17 18 19 20 21 22 24 49 50 52

$ ruby tramwaje.rb
1
3
4
5
(...)
13
24
49
50
52

Challenge 2

Write a Ruby program that prints how many times the bugle call (hejnał) is played in a given time range within a 24-hour day. The bugle call is played every full hour.

$ ruby hejnal.rb 17:00 21:00
5

$ ruby hejnal.rb 17:01 21:00
4

$ ruby hejnal.rb 17:01 20:59
3

$ ruby hejnal.rb 17:01 17:40
0

$ ruby hejnal.rb 00:00 23:59
24

There are no cases like 17:00 00:00. The second time is always >= the first time.

Solutions (files) send to radek.bulat@gmail.com with title “KRUG golf #1”.

Deadline: 31.09.2024