-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem012.coffee
69 lines (60 loc) · 1.04 KB
/
problem012.coffee
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
{prime, primeFactors} = require './primes'
class Triangle
constructor: ->
@n = 1
@value = 1
next: ->
@n++
@value += @n
groupAndCount = (a)->
c = {}
for i in a
c[i] or= 0
c[i]++
r = []
(v for _k, v of c).sort()
mem = {}
hash = (a,n)->
a.join('.') + ":#{n}"
combinateV2 = (a, pos, n)->
h = hash(a[0...pos].sort(),n)
pos--
if !mem[h]?
if n == 0
mem[h] = 1
else if n < 0 or pos == -1
mem[h] = 0
else
k = a[pos]
l = if k < n then k else n
res = 0
for i in [0..l]
res += combinateV2(a, pos, n - i)
mem[h] = res
mem[h]
combinate = (a, pos, n)->
pos--
if n == 0
1
else if n < 0 or pos == -1
0
else
k = a[pos]
l = if k < n then k else n
res = 0
for i in [0..l]
res += combinate(a, pos, n - i)
res
findTheStuff = ->
t = new Triangle()
loop
candidate = t.next()
factors = groupAndCount(primeFactors(candidate))
n = 0
n += i for i in factors
total = 0
for i in [0..n]
total += combinate(factors, factors.length, i)
if total >= 500
return candidate
console.log findTheStuff()