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. 