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 Int64
s, 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.