Generate a custom pattern number sequence in one go

Question

I'd like to generate the following number sequence in one go using a functional initialization construct:

Array(0, 0, 0, 0, 3, 3, 6, 6, 9, 9, ..., n*3, n*3)

One way is to do:

Array.fill[Int](2)(0) ++ Array.tabulate(4)(_*3)

but I'd need to double each value of the second part of the construct i.e. to get 0, 0 then 3, 3 etc. How can I duplicate the values of the second construct?

I also couldn't figure out a mathematical function that would generate such sequence.

I assume Scala supports integer division? If so, you can divide the index by 2 before multiplying by 3; that will map from 0 and 1 to 0, from 2 and 3 to 3, from 4 and 5 to 6, etc — ruakh, Jan 24 '20 at 19:00

Dima · Answer 1 · 2020-01-24T19:35:14.927

5

Array(0,0) ++ (0 to 2*n).map(_ / 2 * 3)

edited Jan 24 '20 at 19:35

answered Jan 24 '20 at 19:32

Dima

39,570
6
44
70

SkyWalker · Answer 2 · 2020-01-24T19:16:58.457

2

This is a possible solution using flatMap:

Array.fill[Int](2)(0) ++ Array.tabulate(4)(_*3).flatMap(x => Array(x, x))

edited Jan 24 '20 at 19:16

answered Jan 24 '20 at 19:00

SkyWalker

13,729
18
91
187

score 2 · Answer 3 · answered Jan 24 '20 at 19:00

2

You can do this:

def create(n: Int): Array[Int] =
  Array.tabulate(n)(i => Array.fill(if (i == 0) 4 else 2)(3 * i)).flatten

However, Arrays are not the best data type for flattening.

answered Jan 24 '20 at 19:00

Luis Miguel Mejía Suárez

21,686
3
28
45

score 2 · Accepted Answer · answered Jan 24 '20 at 19:16

2

Consider tail-recursive solution for single pass

def pattern(n: Int): List[Int] = {
  @tailrec def run(n: Int, acc: List[Int]): List[Int] = {
    n match {
      case 0 => 0 :: 0 :: 0 :: 0 :: acc
      case i => run(i - 1, (i * 3) :: (i * 3) :: acc)
    }
  }
  run(n-1, Nil)
}

answered Jan 24 '20 at 19:16

Mario Galic

47,285
6
56
98

@SkyWalker note that when I mean that **Arrays** were not the best data type for `flattening`. I meant that you could / should use something like this. – Luis Miguel Mejía Suárez Jan 24 '20 at 19:22
1

It works "backwards" which allows us to prepend an element to a `List` in constant time. – Mario Galic Jan 24 '20 at 19:23

score 2 · Answer 5 · answered Jan 24 '20 at 20:22

jmh benchmark of answers

@State(Scope.Benchmark)
@BenchmarkMode(Array(Mode.Throughput))
class So59902144 {
  def Luis(n: Int) = Array.tabulate(n)(i => Array.fill(if (i == 0) 4 else 2)(3 * i)).flatten
  def Dima(n: Int) = Array(0,0) ++ (0 until 2*n).map(_ / 2 * 3)
  def SkyWalker(n: Int) = Array.fill[Int](2)(0) ++ Array.tabulate(n)(_*3).flatMap(x => Array(x, x))
  def MarioGalic(n: Int) =  {
    @tailrec def run(n: Int, acc: List[Int]): List[Int] = {
      n match {
        case 0 => 0 :: 0 :: 0 :: 0 :: acc
        case i => run(i - 1, (i * 3) :: (i * 3) :: acc)
      }
    }
    run(n-1, Nil)
  }

  val n = 10000
  @Benchmark def _Luis = Luis(n)
  @Benchmark def _Dima = Dima(n)
  @Benchmark def _SkyWalker = SkyWalker(n)
  @Benchmark def _MarioGalic = MarioGalic(n)
}

sbt "jmh:run -i 5 -wi 2 -f 1 -t 1 -prof gc bench.So59902144"

[info] Benchmark                   Mode   Cnt        Score       Error   Units
[info] So59902144._Dima            thrpt    5     5178.171 ±   837.780   ops/s
[info] So59902144._Luis            thrpt    5     3649.262 ±   309.027   ops/s
[info] So59902144._MarioGalic      thrpt    5    10926.546 ±  3587.691   ops/s
[info] So59902144._SkyWalker       thrpt    5     6088.413 ±   474.100   ops/s

Wuhu, I was the slowest, which is a great because I was sure that `flatten` was a really bad idea. And it shows that if used correctly, **Lists** can be really performant. — Luis Miguel Mejía Suárez, Jan 24 '20 at 20:51
@SkyWalker Credit goes to Travis Brown's [excelent answer](https://stackoverflow.com/a/59600699/5205022) which demonstrates how to do these measurements. — Mario Galic, Jan 25 '20 at 21:38

Generate a custom pattern number sequence in one go

5 Answers5

Linked