The Crystal Programming Language Forum

Translate Ruby: arry.product -> Crystal

My vote for worst named Ruby method is ArraY::product because not only does it violate the principle of least surprises it makes no intuitive sense (OK, rant over).

Translating this to Crystal, I tried using zip but don’t get the same results, so I beseech the Crystal gurus thy divine knowledge. :thinking:

  def fN(n)
    return [0,1,2,3,4,5,6,7,8,9] if n==1
    return [0,11,22,33,44,55,66,77,88,99] if n==2
    a=[]; [0,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{ |g| a << g[0]*10**(n-1)+g[0]+10*g[1] }; return a
  end

The name will likely change, it will likely be cartesian_product.

There’s also an instance method here.

You can actually use the code you have above if you specify the array type:

  def fN(n)
    return [0,1,2,3,4,5,6,7,8,9] if n==1
    return [0,11,22,33,44,55,66,77,88,99] if n==2
    a=[] of Int32; [0,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{ |g| a << g[0]*10**(n-1)+g[0]+10*g[1] }; return a
  end

When I use zip (as below) I get partial correct output before it bombs.

def fN(n : Int32)
    return [0,1,2,3,4,5,6,7,8,9] if n == 1
    return [0,11,22,33,44,55,66,77,88,99] if n == 2
    a = [] of UInt64; [0,1,2,3,4,5,6,7,8,9].zip(fN(n-2)).each{|g| a << (g[0].to_u64 &* 10&**(n-1) + g[0].to_u64 &+ 10*g[1].to_u64).to_u64} 
    return a
  end

When I use product it doesn’t compile, with these error messages.
I haven’t figured out yet how to set the types to make it compile AND give the correct results.

  def fN(n : Int32)
    return [0,1,2,3,4,5,6,7,8,9] if n == 1
    return [0,11,22,33,44,55,66,77,88,99] if n == 2
    a = [] of UInt64; [0,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{|g| a << (g[0].to_u64 &* 10&**(n-1) + g[0].to_u64 &+ 10*g[1].to_u64).to_u64} 
    return a
  end
In fsharp2crystal.cr:11:45

 11 | a = [] of UInt64; [0,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{|g| a << (g[0].to_u64 &* 10&**(n-1) + g[0].to_u64 &+ 10*g[1].to_u64).to_u64} 
                                              ^------
Error: no overload matches 'Array(Int32)#product' with type (Array(Int32) | Array(UInt64))

Overloads are:
 - Array(T)#product(ary : Array(U))
 - Array(T)#product(enumerable : Enumerable, &block)
 - Enumerable(T)#product(initial : Number)
 - Enumerable(T)#product()
 - Enumerable(T)#product(initial : Number, &block)
 - Enumerable(T)#product(&block)
Couldn't find overloads for these types:
 - Array(Int32)#product(Array(UInt64))

This should work:

  def fN(n : Int32)
    return [0,1,2,3,4,5,6,7,8,9] of UInt64 if n == 1
    return [0,11,22,33,44,55,66,77,88,99] of UInt64 if n == 2
    a = [] of UInt64; ([0,1,2,3,4,5,6,7,8,9] of UInt64).product(fN(n-2)).each{|g| a << (g[0].to_u64 &* 10&**(n-1) + g[0].to_u64 &+ 10*g[1].to_u64).to_u64} 
    return a
  end

If you restrict the output type to what you expect (def fN(n : Int32) : Array(UInt64)), you can find type-related bugs like this earlier.

OK, almost got it. Going from:

return [0,11,22,33,44,55,66,77,88,99] if n == 2

to this:

return [0u64,11,22,33,44,55,66,77,88,99] if n == 2

solves that problem, so now it compiles and gives corrects results for the smaller values.
Now just have to correct the arithmetic overflows.

1 Like

I would not mix Int64 with Int32. Well, unless you want suboptimal performance.

System: Intel I7, 3.5GHz, 16GB, Linux 5.9.10, Crystal 0.35.1

I got it completely working and used htop to monitor system parameters:

  1. The Ruby version uses max of ~50% of mem; Crystal ~89%
  2. Crystal GC gives memory allocation warnings
  3. Best Ruby time was 443 secs; Crystal 43 secs

Would appreciate suggestions to make code faster and prettier.
Is it possible to set at constant as so?: constant ten = 10u64

Ruby

class PalNo
  def initialize(digit)
    @digit, @l, @dd = digit, 3, 11*digit
  end
  def fN(n)
    return [0,1,2,3,4,5,6,7,8,9] if n==1
    return [0,11,22,33,44,55,66,77,88,99] if n==2
    a=[]; [0,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{ |g| a << g[0]*10**(n-1)+g[0]+10*g[1] }; return a
  end
  def show(count, keep)
    to_skip, palcnt, pals = count - keep, 0, []
    while palcnt < count
      fN(@l-2).each{ |g| pal=@digit*10**(@l-1)+@digit+10*g;
      pals << pal if pal%(@dd)==0 && (palcnt += 1) > to_skip; break if palcnt - to_skip == keep }; @l+=1
    end
    print pals; puts
  end
end

start = Time.now

(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

puts (Time.now - start)

Crystal

class PalNo
  @digit : UInt64
  @dd : UInt64

  def initialize(digit : Int32)
    @digit, @l, @dd = digit.to_u64, 3, 11u64 * digit
  end
  def fN(n : Int32)
    return [0u64,1,2,3,4,5,6,7,8,9] if n == 1
    return [0u64,11,22,33,44,55,66,77,88,99] if n == 2
    a = [] of UInt64; [0u64,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{|g| a << g[0].to_u64 &* 10u64&**(n-1) &+ g[0].to_u64 &+ 10u64 &* g[1].to_u64 } 
    return a
  end
  def show(count, keep)
    to_skip, palcnt, pals = count - keep, 0, [] of UInt64
    while palcnt < count
      fN(@l-2).each{ |g| pal = @digit*10u64&**(@l-1) + @digit + 10u64 &* g
      pals << pal if pal % @dd == 0 && (palcnt += 1) > to_skip; break if palcnt - to_skip == keep }; @l+=1
    end
    print pals; puts
  end
end

start = Time.monotonic 

(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

puts (Time.monotonic - start).total_seconds

Crystal output

➜  palindromes crystal run --release fsharp2crystal.cr
[121, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 10901, 11011, 12221, 13431, 14641, 15851, 17171, 18381, 19591]
[242, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 20702, 21912, 22022, 23232, 24442, 25652, 26862, 28182, 29392]
[363, 3003, 3333, 3663, 3993, 31713, 33033, 36663, 300003, 303303, 306603, 309903, 312213, 315513, 318813, 321123, 324423, 327723, 330033, 333333]
[484, 4004, 4224, 4444, 4664, 4884, 40304, 42724, 44044, 46464, 48884, 400004, 401104, 402204, 403304, 404404, 405504, 406604, 407704, 408804]
[5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 50105, 51315, 52525, 53735, 54945, 55055, 56265, 57475, 58685, 59895]
[6006, 6336, 6666, 6996, 61116, 64746, 66066, 69696, 600006, 603306, 606606, 609906, 612216, 615516, 618816, 621126, 624426, 627726, 630036, 633336]
[7007, 7777, 77077, 700007, 707707, 710017, 717717, 720027, 727727, 730037, 737737, 740047, 747747, 750057, 757757, 760067, 767767, 770077, 777777, 780087]
[8008, 8448, 8888, 80608, 86768, 88088, 800008, 802208, 804408, 806608, 808808, 821128, 823328, 825528, 827728, 829928, 840048, 842248, 844448, 846648]
[9009, 9999, 94149, 99099, 900009, 909909, 918819, 927729, 936639, 945549, 954459, 963369, 972279, 981189, 990099, 999999, 9459549, 9508059, 9557559, 9606069]
####
[165561, 166661, 167761, 168861, 169961, 170071, 171171, 172271, 173371, 174471, 175571, 176671, 177771, 178871, 179971]
[265562, 266662, 267762, 268862, 269962, 270072, 271172, 272272, 273372, 274472, 275572, 276672, 277772, 278872, 279972]
[30366303, 30399303, 30422403, 30455403, 30488403, 30511503, 30544503, 30577503, 30600603, 30633603, 30666603, 30699603, 30722703, 30755703, 30788703]
[4473744, 4485844, 4497944, 4607064, 4619164, 4620264, 4632364, 4644464, 4656564, 4668664, 4681864, 4693964, 4803084, 4815184, 4827284]
[565565, 566665, 567765, 568865, 569965, 570075, 571175, 572275, 573375, 574475, 575575, 576675, 577775, 578875, 579975]
[60399306, 60422406, 60455406, 60488406, 60511506, 60544506, 60577506, 60600606, 60633606, 60666606, 60699606, 60722706, 60755706, 60788706, 60811806]
[72299227, 72322327, 72399327, 72422427, 72499427, 72522527, 72599527, 72622627, 72699627, 72722727, 72799727, 72822827, 72899827, 72922927, 72999927]
[80611608, 80622608, 80633608, 80644608, 80655608, 80666608, 80677608, 80688608, 80699608, 80800808, 80811808, 80822808, 80833808, 80844808, 80855808]
[95311359, 95400459, 95499459, 95588559, 95677659, 95766759, 95855859, 95944959, 96033069, 96122169, 96211269, 96300369, 96399369, 96488469, 96577569]
####
[17799771, 17800871, 17811871, 17822871, 17833871, 17844871, 17855871, 17866871, 17877871, 17888871]
[27799772, 27800872, 27811872, 27822872, 27833872, 27844872, 27855872, 27866872, 27877872, 27888872]
[3084004803, 3084334803, 3084664803, 3084994803, 3085225803, 3085555803, 3085885803, 3086116803, 3086446803, 3086776803]
[482282284, 482414284, 482535284, 482656284, 482777284, 482898284, 482909284, 483020384, 483141384, 483262384]
[57800875, 57811875, 57822875, 57833875, 57844875, 57855875, 57866875, 57877875, 57888875, 57899875]
[6084004806, 6084334806, 6084664806, 6084994806, 6085225806, 6085555806, 6085885806, 6086116806, 6086446806, 6086776806]
[7452992547, 7453223547, 7453993547, 7454224547, 7454994547, 7455225547, 7455995547, 7456226547, 7456996547, 7457227547]
[8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808]
[9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869]
####
[178788887871]
[278788887872]
[30878611687803]
[4833326233384]
[578789987875]
[60878611687806]
[74826144162847]
[80869688696808]
[96878077087869]
####
[17878799787871]
[27878799787872]
[3087876666787803]
[483333272333384]
[57878799787875]
[6087876996787806]
[7487226666227847]
[8086969559696808]
[9687870990787869]
####
[1787878888787871]
[2787878888787872]
GC Warning: Repeated allocation of very large block (appr. size 201330688):
        May lead to memory leak and poor performance
[308787855558787803]
[48333332623333384]
[5787878998787875]
GC Warning: Repeated allocation of very large block (appr. size 3200004096):
        May lead to memory leak and poor performance
[608787855558787806]
[748867523325768847]
[808696968869696808]
GC Warning: Repeated allocation of very large block (appr. size 805310464):
        May lead to memory leak and poor performance
[968787783387787869]
####

Also, I wasn’t aware that array.product(other) existed and equivalent to Ruby.
I knew about [1, 2, 3, 4, 5].product => 120, which is the more intuitive.

This method name in Ruby has also caused allot of debate to change for violating POLS.

My suggestion for a more intuitive|descriptive name is array.combine(other) or such.

Maybe try what I suggested? This gets you half the time and no warnings:

class PalNo
  @digit : UInt64
  @dd : UInt64

  def initialize(digit : Int32)
    @digit, @l, @dd = digit.to_u64, 3, 11u64 * digit
  end

  def fN(n : Int32)
    return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64 if n == 1
    return [0, 11, 22, 33, 44, 55, 66, 77, 88, 99] of UInt64 if n == 2
    a = [] of UInt64; [0u64, 1, 2, 3, 4, 5, 6, 7, 8, 9].product(fN(n - 2)).each { |g| a << g[0].to_u64 &* 10u64 &** (n - 1) &+ g[0].to_u64 &+ 10u64 &* g[1].to_u64 }
    return a
  end

  def show(count, keep)
    to_skip, palcnt, pals = count - keep, 0, [] of UInt64
    while palcnt < count
      fN(@l - 2).each { |g| pal = @digit*10u64 &** (@l - 1) + @digit + 10u64 &* g
      pals << pal if pal % @dd == 0 && (palcnt += 1) > to_skip; break if palcnt - to_skip == keep }; @l += 1
    end
    print pals; puts
  end
end

start = Time.monotonic

(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

puts (Time.monotonic - start).total_seconds

Changing just the arrays reduced the times from 44|45 secs to 37|38 secs.
Creating @ten = 10u64 and replacing all the 10u64 * xx , reduced times to 34|35 secs.
However, I still get the GC Warning message for the last|largest case.
Are you using 0.35.1, and how much memory does your system have?

New code

class PalNo
  @digit : UInt64
  @dd : UInt64
  @ten = 10u64

  def initialize(digit : Int32)
    @digit, @l, @dd = digit.to_u64, 3, 11u64 * digit
  end
  def fN(n : Int32)
    return [0,1,2,3,4,5,6,7,8,9] of UInt64 if n == 1
    return [0,11,22,33,44,55,66,77,88,99] of UInt64 if n == 2
    a = [] of UInt64; [0,1,2,3,4,5,6,7,8,9].product(fN(n-2)).each{|g| a << g[0].to_u64 &* @ten&**(n-1) &+ g[0].to_u64 &+ @ten &* g[1].to_u64 } 
    return a
  end
  def show(count, keep)
    to_skip, palcnt, pals = count - keep, 0, [] of UInt64
    while palcnt < count
      fN(@l-2).each{ |g| pal = @digit*@ten&**(@l-1) + @digit + @ten &* g
      pals << pal if pal % @dd == 0 && (palcnt += 1) > to_skip; break if palcnt - to_skip == keep }; @l+=1
    end
    print pals; puts
  end
end

start = Time.monotonic 

(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

puts (Time.monotonic - start).total_seconds

Also try this:

class PalNo
  @digit : UInt64
  @dd : UInt64

  def initialize(digit : Int32)
    @digit, @l, @dd = digit.to_u64, 3, 11u64 * digit
  end

  def fN(n : Int32)
    return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64 if n == 1
    return [0, 11, 22, 33, 44, 55, 66, 77, 88, 99] of UInt64 if n == 2
    a = [] of UInt64
    ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64).product(fN(n - 2)) do |g0, g1|
      a << g0.to_u64 &* 10u64 &** (n - 1) &+ g0.to_u64 &+ 10u64 &* g1.to_u64
    end
    return a
  end

  def show(count, keep)
    to_skip, palcnt, pals = count - keep, 0, [] of UInt64
    while palcnt < count
      fN(@l - 2).each do |g|
        pal = @digit*10u64 &** (@l - 1) + @digit + 10u64 &* g
        pals << pal if pal % @dd == 0 && (palcnt += 1) > to_skip
        break if palcnt - to_skip == keep
      end
      @l += 1
    end
    print pals; puts
  end
end

start = Time.monotonic

(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

puts (Time.monotonic - start).total_seconds

By the way, “product” is very intuitive for me, in math there’s cartesian product: https://en.wikipedia.org/wiki/Cartesian_product

You can halve the used memory (but increase the run time ~60% from @asterite’s version) by using Array.each_product:

Code
class PalNo
  ONE_DIGIT_PALINDROMES = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64
  TWO_DIGIT_PALINDROMES = [0, 11, 22, 33, 44, 55, 66, 77, 88, 99] of UInt64

  @digit : UInt64
  @dd : UInt64

  def initialize(digit : Int32)
    @digit = digit.to_u64
    @l = 3
    @dd = 11u64 * digit
  end

  def self.fN(n : Int32) : Array(UInt64)
    return ONE_DIGIT_PALINDROMES if n == 1
    return TWO_DIGIT_PALINDROMES if n == 2

    a = [] of UInt64
    Array.each_product(ONE_DIGIT_PALINDROMES, fN(n - 2), reuse: true) { |(outer, inner)| a << outer &* 10u64 &** (n - 1) &+ outer &+ 10u64 &* inner }
    return a
  end

  def show(count, keep)
    to_skip = count - keep
    palindrome_count = 0
    palindromes = [] of UInt64
    while palindrome_count < count
      PalNo.fN(@l - 2).each do |palindrome|
        pal = @digit*10u64 &** (@l - 1) + @digit + 10u64 &* palindrome

        if pal % @dd == 0 && (palindrome_count += 1) > to_skip
          palindromes << pal
        end

        if palindrome_count - to_skip == keep
          break
        end
      end
      @l += 1
    end
    print palindromes
    puts
  end
end

I also reformatted stuff for readability (to help me work on it), and I made the literal arrays into constants (which I’m not sure helps at all).

I also intend to see if I can lower the memory even more with a yielding method.

Yeh, but (unfortunately) the overwhelming number of people on the planet have never even had (or remember) calculus, let alone matrix algebra. But most (more) people know a product is the result of multiplication as a sum is to addition. You’re too educated @asterite. :blush:

OK, now I see what you were saying about how to initial arrays. Your new version time was consistently around 29.8|9 secs. However, when I added using @ten = 10u64 it was consistently a smidgen faster at 29.4|5 secs. And I’m still getting GC Warnings for the last case. But I’m impressed it went from an initial 47|48 secs down to 29.4|5 secs with just a few judicious changes.

As I always tell people - the divinity is in the details!

Another one:

class PalNo
  @digit : UInt64
  @dd : UInt64

  def initialize(digit : Int32)
    @digit, @l, @dd = digit.to_u64, 3, 11u64 * digit
  end

  def fN(n : Int32)
    return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64 if n == 1
    return [0, 11, 22, 33, 44, 55, 66, 77, 88, 99] of UInt64 if n == 2
    sub = fN(n - 2)
    a = Array(UInt64).new(sub.size*9)
    ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9] of UInt64).product(sub) do |g0, g1|
      a << g0.to_u64 &* 10u64 &** (n - 1) &+ g0.to_u64 &+ 10u64 &* g1.to_u64
    end
    a
  end

  def show(count, keep)
    to_skip, palcnt, pals = count - keep, 0, [] of UInt64
    while palcnt < count
      fN(@l - 2).each do |g|
        pal = @digit*10u64 &** (@l - 1) + @digit + 10u64 &* g
        pals << pal if pal % @dd == 0 && (palcnt += 1) > to_skip
        break if palcnt - to_skip == keep
      end
      @l += 1
    end
    print pals; puts
  end
end

start = Time.monotonic

(1..9).each { |digit| PalNo.new(digit).show(20, 20) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100, 15) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1000, 10) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(100_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(1_000_000, 1) }; puts "####"
(1..9).each { |digit| PalNo.new(digit).show(10_000_000, 1) }; puts "####"

puts (Time.monotonic - start).total_seconds

This one is 0.8|1 sec slower, so your former version is better (simpler and faster).

Hey @RespiteSage I did a quick test of your version, running it 5 times, and the max mem usage was consistently between 16.6% to 24% (still w/GC Warnings), and speed of 54.6|8 secs.

1 Like

OK, I’m finished with this (for now), and posted on Rosetta Code.
On a “quiet” system (idle mem: ~600MB-800MB) htop shows max of 22% of mem (~4GB+).

That pretty much matches what I was getting on my machine (same memory as yours, slower processor speed). I was getting ~8 GB of used memory and 30-ish seconds run time with asterite’s version.

Were you using 0.35.1, and were you also getting the GC: Warning messages?

How do you turnoff getting those warning messages?

I see product is going to be renamed probably cartesian_product for 1.0, so code will need updating when that change made.