The Crystal Programming Language Forum

Rosetta Code Chronicles #1

This is the first in a series sharing my knowledge, insights, and thoughts acquired from my trials, tribulations, and triumphs solving Rosetta Code tasks using Crystal. Hopefully, this will help the intrepid reader to make fewer mistakes (that I made for you), become more efficient, and have more fun coding in Crystal, to increase your programming happiness.

For housekeeping purposes, I’m using (current) Crystal 0.34 on a Linux laptop.

Largest number divisible by its digits

At time of writing (atw) I just finished the Largest number divisible by its digits which is a simple task, but entails a non-trivial level of coding and design considerations. I originally just did a direct translation for Ruby base 10 (its only original version).

My standard procedure is to look at the Ruby version and copy and tweak its syntax to Crystal. For this task I needed to make 3 changes.

#Ruby/Crystal
div          = 9876432.div(magic_number) * magic_number
div          = (9876432 // magic_number) * magic_number

#Ruby/Crystal
candidates   = div.step(0, -magic_number)
candidates   = div.step(to: 0, by: -magic_number)

#Ruby/Crystal
digits = c.digits                  # 12345 => [5, 4, 3, 2, 1]
digits = c.to_s.chars.map(&.to_i)  # 12345 => [1, 2, 3, 4, 5]

For the last case I didn’t need to reverse the digits because the algorithm didn’t require it, it just wants the digits.

  • Insight: Don’t just verbatim translate code, do the algorithm.

This was OK, but not much of a challenge. Looking at the other languages I noticed (just) a few did the largest hex number too, which was more interesting. I finally decided to do the Kotlin version (which I’ve never used) but the code’s syntax/operation was simple enough to decipher.

// version 1.1.4-3

fun Long.divByAll(digits: List<Char>) =
    digits.all { this % (if (it <= '9') it - '0' else it - 'W')  == 0L }

fun main(args: Array<String>) {
    val magic = 15L * 14 * 13 * 12 * 11
    val high = 0xfedcba987654321L / magic * magic
    for (i in high downTo magic step magic) {
        if (i % 16 == 0L) continue           // can't end in '0'
        val s = i.toString(16)               // always generates lower case a-f
        if ('0' in s) continue               // can't contain '0'
        val sd = s.toCharArray().distinct()
        if (sd.size != s.length) continue    // digits must be unique
        if (i.divByAll(sd)) {
            println("Largest hex number is ${i.toString(16)}")
            return
        }
    }
}

Just looking at the function name divByAll I knew all it was doing was determining if all a number’s digits evenly divided it. After looking at it awhile, and just before I started to do a literal translation, I said “I don’t need to all that” and performed it as below.

def divByAll(num, digits)
  digits.all? { |digit| num % digit.to_i(16) == 0 }
end

From the base 10 version I knew I could use that structure (no main routine needed), and created this first Crystal version, just to get it working.

def divByAll(num, digits)
  digits.all? { |digit| num % digit.to_i(16) == 0 }
end

magic = 15_i64 * 14 * 13 * 12 * 11
high = (0xfedcba987654321_i64 // magic) * magic

high.step(to: magic, by: -magic) do |i|
  next if i % 16 == 0           # can't end in '0'
  s = i.to_s(16)                # always generates lower case a-f
  next if s.includes?('0')      # can't contain '0'
  sd = s.chars.uniq
  next if sd.size != s.size     # digits must be unique
  if divByAll(i, sd)
    puts "Largest hex number is #{i.to_s(16)}"
    break
  end
end

This literal translation worked, needing only to explicitly make magic|high be Int64s, and a few other syntax equivalent operations. Now I could start making the code efficient.

The first thing that stood out are the 3 next lines, where two check for the same thing, a ‘0’ digit. Also, I like to make short if statements oneliners. So now the code became:

high.step(to: magic, by: -magic) do |i|
  s = i.to_s(16)               # always generates lower case a-f
  next if s.includes?('0')     # can't contain '0'
  sd = s.chars.uniq
  next if sd.size != s.size    # digits must be unique
  (puts "Largest hex number is #{i.to_s(16)}"; break) if divByAll(i, sd)
end

Now we’re down to 2 next lines, which (IMHO) should be combined, which also allows me to eliminate sd, producing the final full code below.

def divByAll(num, digits)
  digits.all? { |digit| num % digit.to_i(16) == 0 }
end

magic = 15_i64 * 14 * 13 * 12 * 11
high = (0xfedcba987654321_i64 // magic) * magic

high.step(to: magic, by: -magic) do |i|
  s = i.to_s(16)               # always generates lower case a-f
  next if s.includes?('0') || s.chars.uniq.size != s.size # need uniq non-zero digits
  (puts "Largest hex number is #{i.to_s(16)}"; break) if divByAll(i, s.chars)
end

Benchmarks showed this version was also (by a smidgen) the fastest.

Language comparisons shows the Crystal version is one of the shortest, and should be easy to understand for most people (for which I created a Ruby version afterwards).

This was a nice exercise that reveals some tangible insights:

  • determine the necessary operational code equivalents
  • don’t just literally translate, understand the desired outcomes first
  • create a working version first
  • tweak it to be more idiomatic, faster, pretty
  • test for speed, etc, between versions if necessary/desired

I hope this was helpful! I was fun for me. :smiley:

4 Likes

I have published some things in Rosetta Code and I would like to know which is the language that most complicates the conversion to Crystal. Translating libraries from NodeJS to Crystal has been a headache, but when I see Kotlin it looks very similar to Crystal in some ways.

Nice publication, by the way. Keep publishing the series!