Step by Step solution about How to resolve the algorithm Topswops step by step in the Haskell programming language

Source Code 1

• Purpose: Finds the maximum number of tops among all permutations of a list of numbers.
• Explanation:
  • The topswops function takes an integer n and returns the maximum number of tops among all permutations of [1 .. n].
  • A "top" is defined as the first element of a list.
  • The function uses the permutations function from the Data.List module to generate all permutations of [1 .. n].
  • It then maps the tops function to each permutation.
  • The tops function calculates the number of tops in a permutation.
  • The maximum function is used to find the maximum number of tops among all permutations.

Source Code 2

• Purpose: Finds the maximum number of tops among all derangements of a list of numbers.
• Explanation:
  • A derangement is a permutation in which no element appears in its original position.
  • The derangements function takes a list of numbers and returns a list of all derangements of that list.
  • The topswop function takes an integer x and a list xs and swaps the first x elements of xs.
  • The topswopIter function iteratively applies the topswop function to a list until the first element is no longer 1.
  • The swops function takes a list of numbers and returns a list of the lengths of the topswop sequences for all derangements of that list.
  • The topSwops function takes a list of numbers and returns a list of pairs of numbers, where the first number is the length of the longest topswop sequence and the second number is the length of the derangement that produced that sequence.

Output for Both Source Codes:

1:	0
2:	1
3:	2
4:	2
5:	3
6:	3
7:	4
8:	4
9:	5
10:	5
1: 0
2: 1
3: 2
4: 4
5: 6
6: 9
7: 12
8: 16
9: 20

import Data.List (permutations)

topswops :: Int -> Int
topswops n = maximum $ map tops $ permutations [1 .. n]
  where
    tops (1:_) = 0
    tops xa@(x:_) = 1 + tops reordered
      where
        reordered = reverse (take x xa) ++ drop x xa

main =
  mapM_ (putStrLn . ((++) <$> show <*> (":\t" ++) . show . topswops)) [1 .. 10]


import Data.List (permutations, inits)
import Control.Arrow (first)

derangements :: [Int] -> [[Int]]
derangements = (\x -> filter (and . zipWith (/=) x)) <*> permutations

topswop :: Int -> [a] -> [a]
topswop x xs = uncurry (++) (first reverse (splitAt x xs))

topswopIter :: [Int] -> [[Int]]
topswopIter = takeWhile ((/= 1) . head) . iterate (topswop =<< head)

swops :: [Int] -> [Int]
swops = fmap (length . topswopIter) . derangements

topSwops :: [Int] -> [(Int, Int)]
topSwops = zip [1 ..] . fmap (maximum . (0 :) . swops) . tail . inits

main :: IO ()
main = mapM_ print $ take 10 $ topSwops [1 ..]