{-|

Module      : PolyDivisors
Description : Find poly-divisors of a number
Copyright   : © Frank Jung, 2020
License     : GPL-3

Find poly-divisible numbers such that we use digits from 1 to 9, and the
first n digits are modulo n for all digits in the number.

I first read about puzzle in Matt Parkers book,
<https://www.penguin.com.au/books/things-to-make-and-do-in-the-fourth-dimension-9780141975863 Things to make and do in the fourth dimension>.

The poly divisors listed here are in descending order of performance.
i.e. @isPolyMod@ better than @isPolyMod'@ which is better than @isPolyMod''@

== Method

 * convert string input to int
 * permute a list of digits 1..9
 * filter modulo (length) for length digits

== Exploration

Investigate how to use a fold instead of recursion:

>>> x = 123456789
>>> n = length (show x)

>>> λ> map (\p -> x `div` 10^p ) [0..n-1]
[123456789,12345678,1234567,123456,12345,1234,123,12,1]

>>> λ> f x = let n = length (show x) in x `mod` n == 0
>>> λ> f 12
True

>>> λ> foldr (\x -> (&&) (f x)) True xs
False

== Examples

Load in GHCi:

>>> $ cabal repl
>>> λ> :load PolyDivisors

>>> λ> findPolyDiv 123
[123,321]

>>> λ> findPolyDiv 123456
[123654,321654]

>>> λ> findPolyDiv 123456789
[381654729]

-}

module PolyDivisors ( findPolyDiv
                    , isPolyMod
                    , isPolyMod'
                    , isPolyMod''
                    ) where

import           Data.List (permutations)

-- | Find poly-divisor of input string.
findPolyDiv :: Int -> [Int]
findPolyDiv :: Int -> [Int]
findPolyDiv = (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter Int -> Bool
isPolyMod ([Int] -> [Int]) -> (Int -> [Int]) -> Int -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [Int]
perms

-- | Permutations of argument.
perms :: Int -> [Int]
perms :: Int -> [Int]
perms Int
xs = (String -> Int) -> [String] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map String -> Int
forall a. Read a => String -> a
read (String -> [String]
forall a. [a] -> [[a]]
permutations (Int -> String
forall a. Show a => a -> String
show Int
xs))

-- | 'isPolyMod': Test number is modulo @n ... 1@.
isPolyMod :: Int -> Bool
isPolyMod :: Int -> Bool
isPolyMod Int
x = ((Int, Int) -> Bool -> Bool) -> Bool -> [(Int, Int)] -> Bool
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Bool -> Bool -> Bool
(&&) (Bool -> Bool -> Bool)
-> ((Int, Int) -> Bool) -> (Int, Int) -> Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, Int) -> Bool
isModLen) Bool
True [(Int, Int)]
xs
  where
    -- number of digits in input
    n :: Int
n = String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Int -> String
forall a. Show a => a -> String
show Int
x)
    -- list of x's reduced by factor of 10 for length of x as a string
    -- eg. 123 gives [(123, 3), (12, 2), (1,1)]
    xs :: [(Int, Int)]
xs = (Int -> (Int, Int)) -> [Int] -> [(Int, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (\Int
p -> (Int
x Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
10 Int -> Int -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
p, Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
p) ) [Int
0..Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
    -- Check tuple (x, n) is modulus 0
    -- ie. Is x mod n = 0?
    isModLen :: (Int, Int) -> Bool
    isModLen :: (Int, Int) -> Bool
isModLen (Int, Int)
xn = (Int -> Int -> Int) -> (Int, Int) -> Int
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> Int -> Int
forall a. Integral a => a -> a -> a
mod (Int, Int)
xn Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0

-- | @isPolyMod''@: Test number is modulo @n ... 1@.
isPolyMod' :: Int -> Bool
isPolyMod' :: Int -> Bool
isPolyMod' Int
x = (Int -> Bool) -> [Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) (Int -> Int -> [Int]
polyMod Int
n Int
x)
  where
    -- number of digits in input
    n :: Int
n = String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Int -> String
forall a. Show a => a -> String
show Int
x)
    -- recurse reducting digits of list
    polyMod :: Int -> Int -> [Int]
    polyMod :: Int -> Int -> [Int]
polyMod Int
m Int
a
      | Int
m Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1    = [Int
0]  -- as m is from length this is always positive
      | Bool
otherwise = Int
a Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
m Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: Int -> Int -> [Int]
polyMod (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int
a Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
10)

-- | @isPolyMod''@: Test number is modulo @n ... 1@.
isPolyMod'' :: Int -> Bool
isPolyMod'' :: Int -> Bool
isPolyMod'' Int
x = (Int -> Bool) -> [Int] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) [Int]
xs
  where
    -- number of digits in input
    n :: Int
n = String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (Int -> String
forall a. Show a => a -> String
show Int
x)
    -- list of x's reduced by factor of 10 for length of x as a string
    -- eg. 123 gives [(123 % 3), (12 % 2), (1 % 1)]
    xs :: [Int]
xs = (Int -> Int) -> [Int] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (\Int
p -> Int
x Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
10 Int -> Int -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
p Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
p) ) [Int
0..Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]