Ruby Quiz - Challenge #8 - Base32 Alphabet - Convert the Super "Sekretoooo" 240-Bit CryptoKitties Genome to Kai Notation - Annipurrsary!


(Gerald Bauer) #1

Hello,

  It's Friday. Ruby Quiz time! Join us. Let's keep going with a new
Ruby Quiz [1] every Friday. Here we go:

Challenge #8 - Base32 Alphabet - Convert the Super "Sekretoooo"
240-Bit CryptoKitties Genome to Kai Notation - Annipurrsary!

Annipurrsary! Let's celebrate one year of CryptoKitties -
yes, more than one million cute little cartoon cats on the blockchain.

Let's convert the super "sekretoooo" kitty genome - that is, a 240-bit
integer number
where every 5-bit block is a gene - into the base32 (2^5=32) kai notation.

Q: What's base32 kai notation?

Kai notation (named to honor [Kai
Turner](https://medium.com/@kaigani/the-cryptokitties-genome-project-on-dominance-inheritance-and-mutation-b73059dcd0a4)
who deciphered the kitties genome)
is a base58 variant / subset for decoding the 240-bit integer into 5-bit blocks.
Each 5-bit block is a gene with 32 possible traits.
The 240-bit genome breaks down into 12 groups of 4 (x 5-bit) genes
(that is, 12 x 4 x 5-bit = 240 bits)
Example:

Kai |Binary |Num|Kai |Binary |Num|Kai |Binary |Num|Kai
Binary |Num|
-------|-------|---|-------|-------|---|-------|-------|---|-------|-------|---|
**1** | 00000 | 00 | **9** | 01000 | 08 | **h** | 10000 |16 | **q**
11000 |24 |
**2** | 00001 | 01 | **a** | 01001 | 09 | **i** | 10001 |17 | **r**
11001 |25 |
**3** | 00010 | 02 | **b** | 01010 | 10 | **j** | 10010 |18 | **s**
11010 |26 |
**4** | 00011 | 03 | **c** | 01011 | 11 | **k** | 10011 |19 | **t**
11011 |27 |
**5** | 00100 | 04 | **d** | 01100 | 12 | **m** | 10100 |20 | **u**
11100 |28 |
**6** | 00101 | 05 | **e** | 01101 | 13 | **n** | 10101 |21 | **v**
11101 |29 |
**7** | 00110 | 06 | **f** | 01110 | 14 | **o** | 10110 |22 | **w**
11110 |30 |
**8** | 00111 | 07 | **g** | 01111 | 15 | **p** | 10111 |23 | **x**
11111 |31 |

Note: The digit-0 and the letter-l are NOT used in kai.

Base58 is a group of binary-to-text encoding schemes used to represent large integers as alphanumeric text.
It is similar to Base64 but has been modified to avoid both non-alphanumeric characters
and letters which might look ambiguous when printed [e.g. 1 and l, 0 and o].
It is therefore designed for human users who manually enter the data,
copying from some visual source, but also allows easy copy
and paste because a double-click will usually select the whole string.

[-- Base58 @ Wikipedia](https://en.wikipedia.org/wiki/Base58)

Let's get coding, for an example:


# A 240-bit super "sekretoooo" integer genome

# hexadecimal (base 16)
genome = 0x4a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce
# decimal (base 10)
genome = 512955438081049600613224346938352058409509756310147795204209859701881294
# binary (base 2)
genome = 0b010010100101001010010011000111001110010000001000010111000001010010111101110011100000000101001010000000110001100010000100\
           011010100000110010000000100011000110000000101001010010100110001100010100101000110100101000010010100101011011100111001110

Let's convert from decimal (base 10) to hexadecimal (base 16 - 2^4)
and binary (base 2 that is, 0 and 1):

p genome    # printed as decimal (base 10) by default
# => 512955438081049600613224346938352058409509756310147795204209859701881294

p genome.to_s(16)
# => "4a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce"

p genome.to_s(2)
# => "10010100101001010010011000111001110010000001000010111000001010010111101110011100000000101001010000000110001100010000100\
#     011010100000110010000000100011000110000000101001010010100110001100010100101000110100101000010010100101011011100111001110"

bin = '%0240b' % genome     # note: adds leading zeros - to_s(2) does not
p bin.size
# => 240
p bin
# => "010010100101001010010011000111001110010000001000010111000001010010111101110011100000000101001010000000110001100010000100\
#     011010100000110010000000100011000110000000101001010010100110001100010100101000110100101000010010100101011011100111001110"

hex = '%060x' % genome     # note: adds leading zeros - to_s(16) does not
p hex.size
# => 60
p hex
# => 60
# => "4a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce"

And finally:

kai = kai_encode( genome )   ## number to base32 kai notation
p kai
# => "aaaa788522f2agff16617755e979244166677664a9aacfff"

The challenge: Code a `kai_encode` method that passes the RubyQuizTest :slight_smile: [2].

def kai_encode( num )
  # ...
end

For the starter level 1 turn
super "sekretoooo" kitty genome 240-bit integer numbers
into base 32 (2^5) kai notation.

For the bonus level 2 pretty print and format
the base 32 (2^5) kai notation in groups of four e.g.
turn:

    "aaaa788522f2agff16617755e979244166677664a9aacfff"

into

    "aaaa 7885 22f2 agff 1661 7755 e979 2441 6667 7664 a9aa cfff"

def kai_fmt( kai )
  # ...
end

Start from scratch or, yes, use any library / gem you can find.

To qualify for solving the code challenge / puzzle you must pass the test:

```
require 'minitest/autorun'

class RubyQuizTest < MiniTest::Test

···

################################
  # test data
  def genomes
     [
       [0x00004a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce,
        "aaaa 7885 22f2 agff 1661 7755 e979 2441 6667 7664 a9aa cfff"]
     ]
  end

  #############
  # tests
  def test_kai_encode
    genomes.each do |pair|
      num = pair[0]
      exp_value = pair[1].gsub(' ','') # note: remove spaces

      assert_equal exp_value, kai_encode( num )
    end
  end # method test_kai_encode

  def test_kai_fmt
    genomes.each do |pair|
      kai = pair[1].gsub(' ','') # remove spaces
      exp_value = pair[1]

      assert_equal exp_value, kai_fmt( kai )
    end
  end # method test_kai_fmt

end # class RubyQuizTest
```

Post your code snippets on the "official" Ruby Quiz Channel,
that is, the ruby-talk mailing list right here.

Happy data wrangling and genome genetics bits & bytes slicing with Ruby.

[1] https://github.com/planetruby/quiz/tree/master/008
[2] https://github.com/planetruby/quiz/blob/master/008/test.rb


(Delton Ding) #2

One-line solution with Ruby:

def kai_encode(num)
num.to_s(2).rjust(240, '0').scan(/.{5}/).map {|n|
'123456789abcdefghijklmnopqrstuvwx'[n.to_i(2)]}.join
end

def kai_fmt(kai)
kai.scan(/.{4}/).join(' ')
end

kai_encode(0x00004a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce)
# => "aaaa788522f2agff16617755e979244166677664a9aacfff"
kai_fmt(kai_encode(0x00004a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce))
# => "aaaa 7885 22f2 agff 1661 7755 e979 2441 6667 7664 a9aa cfff"

···

On 2018/12/08 1:01 AM, Gerald Bauer wrote:

Hello,

  It's Friday. Ruby Quiz time! Join us. Let's keep going with a new
Ruby Quiz [1] every Friday. Here we go:

Challenge #8 - Base32 Alphabet - Convert the Super "Sekretoooo"
240-Bit CryptoKitties Genome to Kai Notation - Annipurrsary!

Annipurrsary! Let's celebrate one year of CryptoKitties -
yes, more than one million cute little cartoon cats on the blockchain.

Let's convert the super "sekretoooo" kitty genome - that is, a 240-bit
integer number
where every 5-bit block is a gene - into the base32 (2^5=32) kai notation.

Q: What's base32 kai notation?

Kai notation (named to honor [Kai
Turner](https://medium.com/@kaigani/the-cryptokitties-genome-project-on-dominance-inheritance-and-mutation-b73059dcd0a4)
who deciphered the kitties genome)
is a base58 variant / subset for decoding the 240-bit integer into 5-bit blocks.
Each 5-bit block is a gene with 32 possible traits.
The 240-bit genome breaks down into 12 groups of 4 (x 5-bit) genes
(that is, 12 x 4 x 5-bit = 240 bits)
Example:

>Kai |Binary |Num|Kai |Binary |Num|Kai |Binary |Num|Kai
>Binary |Num|
>-------|-------|---|-------|-------|---|-------|-------|---|-------|-------|---|
> **1** | 00000 | 00 | **9** | 01000 | 08 | **h** | 10000 |16 | **q**
> 11000 |24 |
> **2** | 00001 | 01 | **a** | 01001 | 09 | **i** | 10001 |17 | **r**
> 11001 |25 |
> **3** | 00010 | 02 | **b** | 01010 | 10 | **j** | 10010 |18 | **s**
> 11010 |26 |
> **4** | 00011 | 03 | **c** | 01011 | 11 | **k** | 10011 |19 | **t**
> 11011 |27 |
> **5** | 00100 | 04 | **d** | 01100 | 12 | **m** | 10100 |20 | **u**
> 11100 |28 |
> **6** | 00101 | 05 | **e** | 01101 | 13 | **n** | 10101 |21 | **v**
> 11101 |29 |
> **7** | 00110 | 06 | **f** | 01110 | 14 | **o** | 10110 |22 | **w**
> 11110 |30 |
> **8** | 00111 | 07 | **g** | 01111 | 15 | **p** | 10111 |23 | **x**
> 11111 |31 |

Note: The digit-0 and the letter-l are NOT used in kai.

Base58 is a group of binary-to-text encoding schemes used to represent large integers as alphanumeric text.
It is similar to Base64 but has been modified to avoid both non-alphanumeric characters
and letters which might look ambiguous when printed [e.g. 1 and l, 0 and o].
It is therefore designed for human users who manually enter the data,
copying from some visual source, but also allows easy copy
and paste because a double-click will usually select the whole string.

[-- Base58 @ Wikipedia](https://en.wikipedia.org/wiki/Base58)

Let's get coding, for an example:


# A 240-bit super "sekretoooo" integer genome

# hexadecimal (base 16)
genome = 0x4a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce
# decimal (base 10)
genome = 512955438081049600613224346938352058409509756310147795204209859701881294
# binary (base 2)
genome = 0b010010100101001010010011000111001110010000001000010111000001010010111101110011100000000101001010000000110001100010000100\
           011010100000110010000000100011000110000000101001010010100110001100010100101000110100101000010010100101011011100111001110

Let's convert from decimal (base 10) to hexadecimal (base 16 - 2^4)
and binary (base 2 that is, 0 and 1):

p genome    # printed as decimal (base 10) by default
# => 512955438081049600613224346938352058409509756310147795204209859701881294

p genome.to_s(16)
# => "4a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce"

p genome.to_s(2)
# => "10010100101001010010011000111001110010000001000010111000001010010111101110011100000000101001010000000110001100010000100\
#     011010100000110010000000100011000110000000101001010010100110001100010100101000110100101000010010100101011011100111001110"

bin = '%0240b' % genome     # note: adds leading zeros - to_s(2) does not
p bin.size
# => 240
p bin
# => "010010100101001010010011000111001110010000001000010111000001010010111101110011100000000101001010000000110001100010000100\
#     011010100000110010000000100011000110000000101001010010100110001100010100101000110100101000010010100101011011100111001110"

hex = '%060x' % genome     # note: adds leading zeros - to_s(16) does not
p hex.size
# => 60
p hex
# => 60
# => "4a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce"

And finally:

kai = kai_encode( genome )   ## number to base32 kai notation
p kai
# => "aaaa788522f2agff16617755e979244166677664a9aacfff"

The challenge: Code a `kai_encode` method that passes the RubyQuizTest :slight_smile: [2].

def kai_encode( num )
  # ...
end

For the starter level 1 turn
super "sekretoooo" kitty genome 240-bit integer numbers
into base 32 (2^5) kai notation.

For the bonus level 2 pretty print and format
the base 32 (2^5) kai notation in groups of four e.g.
turn:

    "aaaa788522f2agff16617755e979244166677664a9aacfff"

into

    "aaaa 7885 22f2 agff 1661 7755 e979 2441 6667 7664 a9aa cfff"

def kai_fmt( kai )
  # ...
end

Start from scratch or, yes, use any library / gem you can find.

To qualify for solving the code challenge / puzzle you must pass the test:

require 'minitest/autorun'

class RubyQuizTest < MiniTest::Test

  ################################
  # test data
  def genomes
     [
       [0x00004a52931ce4085c14bdce014a0318846a0c808c60294a6314a34a1295b9ce,
        "aaaa 7885 22f2 agff 1661 7755 e979 2441 6667 7664 a9aa cfff"]
     ]
  end

  #############
  # tests
  def test_kai_encode
    genomes.each do |pair|
      num       = pair[0]
      exp_value = pair[1].gsub(' ','')   # note: remove spaces

      assert_equal exp_value, kai_encode( num )
    end
  end # method test_kai_encode

  def test_kai_fmt
    genomes.each do |pair|
      kai       = pair[1].gsub(' ','') # remove spaces
      exp_value = pair[1]

      assert_equal exp_value, kai_fmt( kai )
    end
  end # method test_kai_fmt

end # class RubyQuizTest

Post your code snippets on the "official" Ruby Quiz Channel,
that is, the ruby-talk mailing list right here.

Happy data wrangling and genome genetics bits & bytes slicing with Ruby.

[1] https://github.com/planetruby/quiz/tree/master/008
[2] https://github.com/planetruby/quiz/blob/master/008/test.rb

Unsubscribe: <mailto:ruby-talk-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-talk>


(Frank J. Cameron) #3

Gerald Bauer wrote:

Challenge #8 - Base32 Alphabet - Convert the Super "Sekretoooo"
240-Bit CryptoKitties Genome to Kai Notation - Annipurrsary!

$ ruby -v lib/008.rb
ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-linux]
Run options: --seed 55765
# Running:
..
Finished in 0.001806s, 1107.3523 runs/s, 1107.3523 assertions/s.
2 runs, 2 assertions, 0 failures, 0 errors, 0 skips

$ cat lib/008.rb
require_relative '../008/test.rb'

class RubyQuizTest
  Encode = [(1..9),('a'..'k'),('l'..'x')].map(&:to_a).inject(&:+)

  # benchmark
  # 5_000.times: 0.462325 0.001169 0.463494 ( 0.504119)
  # 50000.times: 4.584615 0.003136 4.587751 ( 4.840367)
  # def kai_encode(num)
  # ('%0240b' % num)
  # .chars
  # .each_slice(5)
  # .map(&:join)
  # .map{|n| n.to_i(2)}
  # .map{|n| Encode[n]}
  # .join
  # end

  # benchmark
  # 5_000.times: 0.148790 0.000000 0.148790 ( 0.151831)
  # 50000.times: 1.490005 0.000987 1.490992 ( 1.581884)
  def kai_encode(num)
    num
    .to_s(2)
    .rjust(240, '0')
    .yield_self{|bs| (0..235).step(5).map{|i| bs[i,5]}}
    .map{|n| Encode[n.to_i(2)]}
    .join
  end

  def kai_fmt(kai)
    kai
    .chars
    .each_slice(4)
    .map(&:join)
    .join(' ')
  end
end

RubyQuizTest.new('fjc')


(Gerald Bauer) #4

Hello,

    Welcome Delton Ding to Ruby Quiz! Great solution. Keep it up.

    For reference here's my humble little code snippet / answer -
cut-n-paste from the world's 1st "standard" base32 / kai library / gem
[1] :)):

module Kai

  # See https://en.wikipedia.org/wiki/Base58
  ## Note: alphabet used for encoding
  ALPHABET = '123456789abcdefghijkmnopqrstuvwx'
  BASE = ALPHABET.length ## 32 chars/letters/digits

  # Converts a base10 integer to a base32 string.
  def self.encode( num )
    buf = String.new
    while num >= BASE
      mod = num % BASE
      buf = ALPHABET[mod] + buf
      num = (num - mod)/BASE
    end
    ALPHABET[num] + buf
  end

  def self.fmt( kai )
    ## note: allow spaces; remove them all first
    kai = kai.gsub( ' ', '' )

    ## format in groups of four (4) separated by space
    ## e.g. ccac7787fa7fafaa16467755f9ee444467667366cccceede
    ## : ccac 7787 fa7f afaa 1646 7755 f9ee 4444 6766 7366 cccc eede
    kai.reverse.gsub( /(.{4})/, '\1 ').reverse.strip
  end
end

    Cheers. Prost.

[1] https://github.com/cryptocopycats/base32.kai.rb