From d27319e533ab17da0918ef1400b2a661a644d55e Mon Sep 17 00:00:00 2001
From: Charles Cabergs <me@cacharle.xyz>
Date: Thu, 24 Jun 2021 15:34:19 +0200
Subject: problem 74 in julia

---
 julia/062-cubic_permutations.jl     |  2 +-
 julia/074-digit_factorial_chains.jl | 55 +++++++++++++++++++++++++++++++++++++
 julia/112-bouncy_numbers.jl         |  4 +--
 3 files changed, 58 insertions(+), 3 deletions(-)
 create mode 100644 julia/074-digit_factorial_chains.jl

diff --git a/julia/062-cubic_permutations.jl b/julia/062-cubic_permutations.jl
index 08c07fc..84cb413 100644
--- a/julia/062-cubic_permutations.jl
+++ b/julia/062-cubic_permutations.jl
@@ -17,7 +17,7 @@ const PERMUTATIONS_COUNT = 5
 
 for n in countfrom(2)
     cube = n ^ 3
-    key = sort(collect(string(cube)))
+    key = sort(digits(cube))
     if !haskey(cache, key)
         cache[key] = [cube]
     else
diff --git a/julia/074-digit_factorial_chains.jl b/julia/074-digit_factorial_chains.jl
new file mode 100644
index 0000000..e045592
--- /dev/null
+++ b/julia/074-digit_factorial_chains.jl
@@ -0,0 +1,55 @@
+###
+# Digit factorial chains
+# Problem 74
+#
+# The number 145 is well known for the property that the sum of the factorial of its digits
+# is equal to 145:
+# 1! + 4! + 5! = 1 + 24 + 120 = 145
+# Perhaps less well known is 169, in that it produces the longest chain of numbers that
+# link back to 169; it turns out that there are only three such loops that exist:
+# 169 → 363601 → 1454 → 169
+# 871 → 45361 → 871
+# 872 → 45362 → 872
+# It is not difficult to prove that EVERY starting number will eventually get stuck in a
+# loop. For example,
+# 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
+# 78 → 45360 → 871 → 45361 (→ 871)
+# 540 → 145 (→ 145)
+# Starting with 69 produces a chain of five non-repeating terms, but the longest non-
+# repeating chain with a starting number below one million is sixty terms.
+# How many chains, with a starting number below one million, contain exactly sixty non-
+# repeating terms?
+###
+
+
+const DIGIT_FACTORIALS = Dict(
+    n => factorial(n)
+    for n in 0:9
+)
+
+digit_factorial_sum(n) = sum(DIGIT_FACTORIALS[d] for d in digits(n))
+
+# 46s without cache
+# 3s with cache
+cache = Dict()
+function digit_factorial_chain_length(n)
+    if haskey(cache, n)
+        return cache[n]
+    end
+    # put n in the cache to triger cache hit when we encounter n again (when the same cycle starts)
+    # pretty neat
+    cache[n] = 0
+    cache[n] = 1 + digit_factorial_chain_length(digit_factorial_sum(n))
+    return cache[n]
+end
+
+const CYCLE_LENGTH = 60
+const MAX_NUMBER = 1_000_000 - 1
+
+result = count(
+    ==(CYCLE_LENGTH),
+    digit_factorial_chain_length(n) for n in 1:MAX_NUMBER
+)
+
+println(result)
+
diff --git a/julia/112-bouncy_numbers.jl b/julia/112-bouncy_numbers.jl
index 4877ed9..ab136ca 100644
--- a/julia/112-bouncy_numbers.jl
+++ b/julia/112-bouncy_numbers.jl
@@ -20,8 +20,8 @@
 using Base.Iterators
 
 function is_bouncy(n)
-    s = collect(string(n))
-    !(issorted(s) || issorted(s, rev=true))
+    ds = digits(n)
+    !(issorted(ds) || issorted(ds, rev=true))
 end
 
 const RATIO = 0.99
-- 
cgit