<commit_before>selections [] = [[]]
selections (x:xs) = selections xs ++ map (x:) (selections xs)

withSumOf target = filter (\xs -> sum xs == target)

powersOf n x = takeWhile (<=x) $ map (^n) [1..]

sumOfPowers x n = withSumOf x $ selections $ powersOf n x

main = do
 x <- readLn :: IO Int
 n <- readLn :: IO Int
 print $ length $ sumOfPowers x n<commit_msg>minor optimization for sum-of-powers problem<commit_after>selections _ [] = [[]]
selections target (x:xs) =
  sel ++ map (x:) sel
  where sel = selections target xs

sumsTo = sumsTo' 0
  where
    sumsTo' _ _ [] = False
    sumsTo' s target (x:xs)
      | null xs && s' == target = True
      | s' > target = False
      | otherwise = sumsTo' s' target xs
      where s' = s + x

powersOf n x = takeWhile (<=x) $ map (^n) [1..]
sumOfPowers x n = filter (sumsTo x) $ selections x $ powersOf n x

main = do
 x <- readLn :: IO Int
 n <- readLn :: IO Int
 print $ length $ sumOfPowers x n

{'fraction_non_alphanumeric': 0.1427061310782241, 'fraction_numerical': 0.003171247357293869, 'mean_word_length': 2.8811475409836067, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1647586', 'n_tokens_mistral': 368, 'n_tokens_neox': 340, 'n_words': 125}