[Codewars #46] Mixbonacci (5kyu)

[Codewars #46] Mixbonacci (5kyu) 문제 풀이

Posted by karais89 on January 23, 2019

Instructions

링크

This is the first of my “-nacci” series. If you like this kata, check out the zozonacci sequence too.

Task

  1. Mix -nacci sequences using a given pattern p.
  2. Return the first n elements of the mixed sequence.

Rules

  1. The pattern p is given as a list of strings (or array of symbols in Ruby) using the pattern mapping below (e. g. [‘fib’, ‘pad’, ‘pel’] means take the next fibonacci, then the next padovan, then the next pell number and so on).
  2. When n is 0 or p is empty return an empty list.
  3. If the length of p is more than n repeat the pattern.

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
            0 1 2 3 4
----------+------------------
fibonacci:| 0, 1, 1, 2, 3 ...
padovan: | 1, 0, 0, 1, 0 ...
pell: | 0, 1, 2, 5, 12 ...

pattern = ['fib', 'pad', 'pel']
n = 6
# ['fib', 'pad', 'pel', 'fib', 'pad', 'pel']
# result = [fibonacci(0), padovan(0), pell(0), fibonacci(1), padovan(1), pell(1)]
result = [0, 1, 0, 1, 0, 1]

pattern = ['fib', 'fib', 'pel']
n = 6
# ['fib', 'fib', 'pel', 'fib', 'fib', 'pel']
# result = [fibonacci(0), fibonacci(1), pell(0), fibonacci(2), fibonacci(3), pell(1)]
result = [0, 1, 0, 1, 2, 1]

Sequences

  • fibonacci : 0, 1, 1, 2, 3 …
  • padovan: 1, 0, 0, 1, 0 …
  • jacobsthal: 0, 1, 1, 3, 5 …
  • pell: 0, 1, 2, 5, 12 …
  • tribonacci: 0, 0, 1, 1, 2 …
  • tetranacci: 0, 0, 0, 1, 1 …

Pattern mapping

  • ‘fib’ -> fibonacci
  • ‘pad’ -> padovan
  • ‘jac’ -> jacobstahl
  • ‘pel’ -> pell
  • ‘tri’ -> tribonacci
  • ‘tet’ -> tetranacci

If you like this kata, check out the zozonacci sequence.

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
using System;
using System.Numerics;
using System.Collections.Generic;

namespace Solution
{
  public static class Kata
  {
    // non-recursive
    // Dynamic Programming 
    public static BigInteger Fibonacci(int n)
    {
      if (n < 2)
      {
        return n;
      }
      
      BigInteger[] arr = new BigInteger[n + 1];
      arr[0] = 0;
      arr[1] = 1;
  
      for (int i = 2; i <= n; i++)
      {
        arr[i] = arr[i - 1] + arr[i - 2];
      }
      return arr[n];    
    }
    
    // a(n) = a(n-2) + a(n-3) with a(0)=1, a(1)=a(2)=0. 
    public static BigInteger Padovan(int n)
    {
      if (n == 0)
      {
        return 1;
      }
      
      if (n <= 2)
      {
        return 0;
      }
      
      BigInteger[] arr = new BigInteger[n + 1];
      arr[0] = 1;
      arr[1] = 0;
      arr[2] = 0;
  
      for (int i = 3; i <= n; i++)
      {
        arr[i] = arr[i - 2] + arr[i - 3];
      }
      return arr[n];      
    }
    
    // a(n) = a(n-1) + 2*a(n-2), with a(0) = 0, a(1) = 1. 
    public static BigInteger Jacobstahl(int n)
    {
      if (n < 2)
      {
        return n;
      }
      
      BigInteger[] arr = new BigInteger[n + 1];
      arr[0] = 0;
      arr[1] = 1;
  
      for (int i = 2; i <= n; i++)
      {
        arr[i] = arr[i - 1] + 2 * arr[i - 2];
      }
      return arr[n];   
    }
        
    // a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2). 
    public static BigInteger Pell(int n)
    {    
      if (n < 2)
      {
        return n;
      }
      
      BigInteger[] arr = new BigInteger[n + 1];
      arr[0] = 0;
      arr[1] = 1;
  
      for (int i = 2; i <= n; i++)
      {
        arr[i] = 2 * arr[i - 1] + arr[i - 2];
      }
      return arr[n];  
    }
    
    // a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=0, a(2)=1. 
    public static BigInteger Tribonacci(int n)
    {
      if (n == 0 || n == 1)
      {
        return 0;
      }
      
      if (n == 2)
      {
        return 1;
      }
      
      BigInteger[] arr = new BigInteger[n + 1];
      arr[0] = 0;
      arr[1] = 0;
      arr[2] = 1;
  
      for (int i = 3; i <= n; i++)
      {
        arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
      }
      return arr[n];   
    }
    
    // a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) with a(0)=a(1)=a(2)=0, a(3)=1. 
    public static BigInteger Tetranacci(int n)
    {
      if (n < 3)
      {
        return 0;
      }
      
      if (n == 3)
      {
        return 1;
      }
      
      BigInteger[] arr = new BigInteger[n + 1];
      arr[0] = 0;
      arr[1] = 0;
      arr[2] = 0;
      arr[3] = 1;
      
      for (int i = 4; i <= n; i++)
      {
        arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3] + arr[i - 4];
      }
      return arr[n];   
    }
    
    public static void ShowConsole(string head, Func<int, BigInteger> func, int n)
    {      
      Console.Write(head + " : ");      
      for (int i = 0; i < n; i++)
      {
        Console.Write(" " + func(i));      
      }
      Console.WriteLine();    
    }
        
    public static BigInteger[] Mixbonacci(string[] pattern, int length)
    {
    /*
      ShowConsole("fib", Fibonacci, 10);
      ShowConsole("pad", Padovan, 10);
      ShowConsole("jac", Jacobstahl, 10);
      ShowConsole("pel", Pell, 10);
      ShowConsole("tri", Tribonacci, 10);
      ShowConsole("tet", Tetranacci, 10);
    */
      if (length == 0 || pattern == null || pattern.Length == 0)
      {
        return new BigInteger[] {};     
      }
    
      Dictionary<string, int> boancciCounts = new Dictionary<string, int>();
      boancciCounts["fib"] = 0;
      boancciCounts["pad"] = 0;
      boancciCounts["jac"] = 0;
      boancciCounts["pel"] = 0;
      boancciCounts["tri"] = 0;
      boancciCounts["tet"] = 0;
      
      Dictionary<string, Func<int, BigInteger>> boancciFuncs = new Dictionary<string, Func<int, BigInteger>>();
      boancciFuncs["fib"] = Fibonacci;
      boancciFuncs["pad"] = Padovan;
      boancciFuncs["jac"] = Jacobstahl;
      boancciFuncs["pel"] = Pell;
      boancciFuncs["tri"] = Tribonacci;
      boancciFuncs["tet"] = Tetranacci;
      
            
      BigInteger[] mixbonaccis = new BigInteger[length];             
      for (int i = 0; i < length; i++)
      {        
        string key = pattern[i % pattern.Length];     
        mixbonaccis[i] = boancciFuncs[key](boancciCounts[key]++);
      }
       
      return mixbonaccis;
    }
  }
}
  • 여러가지 점화식이 있는 함수들로 수를 표현하면 되는 문제.
  • 여러가지 규칙의 함수들이 있다.
  • 사실 문제 자체는 재귀 함수를 사용하는 방식이 가장 풀기 쉬운 방식인데, 스택 문제와 퍼포먼스 문제 때문에 해당 방법은 사용하면 안되는 듯 하다.
  • Func 까지 써가면서 품..
  • 재귀함수가 아닌 다이나믹 프로그래밍 방식을 사용함 (배열 사용)
  • 쓸데없이 길어지는 느낌이 없지 않아 있다.

Best Practices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using System.Numerics;
using System.Collections.Generic;
namespace Solution
{
  public static class Kata
  {
    private static readonly Dictionary<string, IEnumerable<BigInteger>> GeneratorMapping =
      new Dictionary<string, IEnumerable<BigInteger>>() {
      {"fib", FibonacciGenerator()},
      {"pad", PadovanGenerator()},
      {"jac", JacobstahlGenerator()},
      {"tet", TetranacciGenerator()},
      {"tri", TribonacciGenerator()},
      {"pel", PellGenerator()}
    };

    public static BigInteger[] Mixbonacci(string[] pattern, int length)
    {
      if (pattern.Length == 0 || length == 0)
      {
        return new BigInteger[] { };
      }

      var res = new List<BigInteger>() { };
      var gens = new Dictionary<string, IEnumerator<BigInteger>>();
      var patLength = pattern.Length;

      for (var i = 0; i < patLength; i++)
      {
        var v = pattern[i];
        gens[v] = GeneratorMapping[v].GetEnumerator();
      }

      for (var i = 0; i < length; i++)
      {
        var gen = gens[pattern[i % patLength]];
        gen.MoveNext();
        res.Add(gen.Current);
      }

      return res.ToArray();

    }

    public static IEnumerable<BigInteger> FibonacciGenerator()
    {
      var a = new BigInteger(0);
      var b = new BigInteger(1);
      BigInteger x;
      while (true)
      {
        yield return a;
        x = a;
        a = b;
        b = x + a;
      }
    }

    public static IEnumerable<BigInteger> PadovanGenerator()
    {
      var a = new BigInteger(1);
      var b = new BigInteger(0);
      var c = new BigInteger(0);
      BigInteger x;
      BigInteger y;
      while (true)
      {
        yield return a;
        x = a;
        y = b;
        a = b;
        b = c;
        c = x + y;
      }
    }

    public static IEnumerable<BigInteger> JacobstahlGenerator()
    {
      var a = new BigInteger(0);
      var b = new BigInteger(1);
      BigInteger x;
      while (true)
      {
        yield return a;
        x = a;
        a = b;
        b = 2 * x + b;
      }
    }


    public static IEnumerable<BigInteger> PellGenerator()
    {
      var a = new BigInteger(0);
      var b = new BigInteger(1);
      BigInteger x;
      while (true)
      {
        yield return a;
        x = a;
        a = b;
        b = x + 2 * b;
      }
    }

    public static IEnumerable<BigInteger> TribonacciGenerator()
    {
      var a = new BigInteger(0);
      var b = new BigInteger(0);
      var c = new BigInteger(1);
      BigInteger x, y, z;
      while (true)
      {
        yield return a;
        x = a; y = b; z = c;
        a = b; b = c;
        c = x + y + z;
      }
    }

    public static IEnumerable<BigInteger> TetranacciGenerator()
    {
      var a = new BigInteger(0);
      var b = new BigInteger(0);
      var c = new BigInteger(0);
      var d = new BigInteger(1);
      BigInteger x, y, z, j;
      while (true)
      {
        yield return a;
        x = a; y = b; z = c; j = d;
        a = b; b = c; c = d;
        d = x + y + z + j;
      }
    }
  }
}
  • IEnumerable 특성을 이용해서 해결.