# Thread: Beginner Programming Challenge #10

1. ## Re: Beginner Programming Challenge #10

in case anybody's interested, it takes this much time:
Code:
```howlingmadhowie% time guile lychrel.scm 1>/dev/null
guile lychrel.scm > /dev/null  2,02s user 0,01s system 98% cpu 2,065 total```
Beat you

Code:
```firas@momiji ~ % time ./lychrel > /dev/null
./lychrel > /dev/null  0.23s user 0.00s system 94% cpu 0.242 total```

2. ## Re: Beginner Programming Challenge #10

Originally Posted by Bachstelze
Beat you

Code:
```firas@momiji ~ % time ./lychrel > /dev/null
./lychrel > /dev/null  0.23s user 0.00s system 94% cpu 0.242 total```
interesting. haskell must have some pretty good number/string conversion functions. i imagine my code is slow because of the huge amounts of quotient and remainder functions in it, but i can get around that by writing a function to add two chains. maybe i'll do that and see if it's faster ...

3. ## Re: Beginner Programming Challenge #10

interesting. haskell must have some pretty good number/string conversion functions. i imagine my code is slow because of the huge amounts of quotient and remainder functions in it, but i can get around that by writing a function to add two chains. maybe i'll do that and see if it's faster ...
Python seems to be similar. This code:

PHP Code:
``` int(str(n)[::-1])  ```
will outperform this code:

PHP Code:
``` def reverse_digits(n):     r = 0     while n:         n, t = divmod(n, 10)         r = r * 10 + t     return r  ```
Though this isn't entirely surprising, as generally the more time Python code spends in C, the faster it runs.

4. ## Re: Beginner Programming Challenge #10

A fairly simple C implementation. It uses recursion, which may be a little tricky for beginners, but hopefully my comments explain it well enough. It's certainly not the most efficient method (converting to a string, reversing the string and atol()'ing it), but it gets the job done.

I decided to do recursion because I'm not very good at it.

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LYCHREL 10000
#define DEPTH 30

void reverse(char *str, char *rev_str) {
// reverses str and stores it in rev_str

long len = strlen(str); // get the length of the string
long i;

if (!len) // if the string is empty
return;

for (i = 0; i < len; i++) { // for each char in the string
// put the i-th char from the back of str into the i-th position
// of rev_str. For instance, put the second to last character of str
// into the second position in rev_str.
rev_str[i] = str[len - i - 1];
} // for i

// C ends all of its strings in '\0' characters, so we need to add one
// to the end so that string functions know where the string is
// supposed to end
rev_str[len] = '\0';

} // reverse()

int islychrel(long n, long d) {
// recursively decides if a number is a lychrel candidate after depth d

// allocate strings for n and its reverse, and a long int for n's reverse
char nStr[100], nRevStr[100];
long nRev;

// convert n to a string
sprintf(nStr, "%ld", n);

// reverse n and put it in a string
reverse(nStr, nRevStr);

// convert that string to a long int
nRev = atol(nRevStr);

// if we've reached the maximum recursion depth, we're done, so
// return true (ie, n is a lychrel candidate)
if (d <= 0)
return 1;

// if the number is a palindrome, we're done and should return false
// (n is NOT a lychrel candidate)
if (d != DEPTH && n == nRev)
return 0;

// now we go around again, this time checking if the number plus its reverse is
// a palindrome. We decrement the depth so that once it gets to zero, we give up
// and the recursion "unwinds"
return islychrel(n + nRev, d - 1);

} // islychrel()

int main(int argc, char *argv[]) {
long i;

// iterate through 0 - MAX_LYCHREL (for this challenge, 10000)
// and print it out if it's a lychrel candidate
for (i = 0; i <= MAX_LYCHREL; i++)
if (islychrel(i, DEPTH))
printf("%ld\n", i);

return 0;

} // main()
```
Code:
```real	0m0.039s
user	0m0.023s
sys	0m0.004s```
Last edited by schauerlich; March 8th, 2010 at 09:59 PM.

5. ## Re: Beginner Programming Challenge #10

I decided to try it in python, a language I never really got into... wrote this in about 5 minutes. It's pretty much the same as my C entry, but python lists and easy casting between strings and ints made it much faster to write.

Code:
```#!/usr/bin/env python

DEPTH = 30
MAX_LYCHREL = 10000

def islychrel(n, d):
# recursively decides if a number is a lychrel candidate,
# giving up after d tries.

# convert n to a string
nStr = str(n)

# reverse it. This uses a funky way of slicing nStr
nRevStr = nStr[::-1]

# make an int out of the reversed string
nRev = int(nRevStr)

# d will equal zero when we've hit our maximum recursion
# depth - that is, when we've gone through a bunch of times
# without finding a palindrome. This means the number IS a
# lychrel candidate and we should return True
if d <= 0:
return True

# if the number and its reverse are equal, then the
# number is a palindrome. This means the number
# is NOT a lychrel candidate and we should return False
if d != DEPTH and n == nRev:
return False

# if neither of our base cases are met, then we should try
# the same thing again, this time adding the number and its
# reverse, and decrementing the depth.
return islychrel(n + nRev, d - 1)

def main():
# for every number between 0 and 10000,
# if the number is a lychrel candidate,
# print it
for i in range(0, MAX_LYCHREL):
if islychrel(i, DEPTH):
print i

if __name__ == "__main__":
main()```
Code:
```real	0m0.188s
user	0m0.164s
sys	0m0.016s```
Last edited by schauerlich; March 8th, 2010 at 09:59 PM.

6. ## Re: Beginner Programming Challenge #10

okay. this one finds the seeds as well:

Code:
```(use-modules (ice-9 format))

(define reverse-chain
(lambda (c)
(define reverse-helper
(lambda (l-in l-out)
(if (null? l-in)
l-out
(reverse-helper (cdr l-in) (cons (car l-in) l-out)))))
(reverse-helper c '())))

(define num->chain
(lambda (num)
(if (< num 10)
(list num)
(cons (remainder num 10) (num->chain (quotient num 10))))))

(define empty-chain? null?)

(lambda (c1 c2)

(lambda (l1 l2 carry)
(let ((num (+ l1 l2 carry)))
(if (> num 9)
(cons 1 (- num 10))
(cons 0 num)))))

(define loop
(lambda (c1 c2 carry)
(cond ((and (null? c1) (null? c2))
(if (> carry 0)
(list carry)
'()))
((null? c1)
((null? c2)
(else

(loop c1 c2 0)))

(define chain->num
(lambda (chain)
(if (null? chain)
0
(+ (car chain) (* 10 (chain->num (cdr chain)))))))

(define is-palindrome?
(lambda (n)

(define same-chain?
(lambda (c1 c2)
(cond ((empty-chain? c1)
(if (empty-chain? c2)
#t
#f))
((empty-chain? c2)
(if (empty-chain? c1)
#t
#f))
((= (car c1) (car c2))
(same-chain? (cdr c1) (cdr c2)))
(else #f))))

(same-chain? n (reverse-chain n))))

(define find-lychrel-seeds
(lambda (limit max-tries)

(define iterate
(lambda (chain)

(define is-lychrel-number?
(lambda (chain try l return)
(cond ((> try max-tries)
l)
((is-palindrome? chain)
(return (chain->num chain)))
(else
(is-lychrel-number? (iterate chain) (+ try 1) (cons (chain->num chain) l) return)))))

(define loop
(lambda (number results)
(if (< number limit)
(let ((result (call/cc (lambda (k) (is-lychrel-number? (num->chain number) 0 '() k)))))
(if (list? result)
(loop (+ 1 number) (cons result results))
(loop (+ 1 number) results)))
(reverse results))))

(define get-last-elements
(lambda (l)
(if (null? l)
'()
(cons (car (reverse (car l))) (get-last-elements (cdr l))))))

(let ((lychrel-numbers (loop 1 '())))

(define my-list-test?
(lambda (in1 in2 pred?)
(let loop ((obj1 in1)
(obj2 in2))
(cond ((null? obj1) #f)
((pred? (car obj1) obj2) #t)
(else (loop (cdr obj1) obj2))))))

(define in-list?
(lambda (l elem)
(my-list-test? l elem =)))

(lambda (list-of-lists l2)
(my-list-test? list-of-lists l2 same-seed?)))

(define same-seed?
(lambda (l1 l2)
(cond ((null? l1) #f)
((in-list? l2 (car l1)) #t)
(else
(same-seed? (cdr l1) l2)))))

(define inner-loop
(lambda (seed-list lychrel-list)
(cond ((null? lychrel-list) seed-list)
(inner-loop seed-list (cdr lychrel-list)))
(else (inner-loop (cons (car lychrel-list) seed-list) (cdr lychrel-list))))))

(let ((lychrel-seed-lists (inner-loop '() lychrel-numbers)))

(cons (get-last-elements lychrel-numbers) (list (reverse (get-last-elements lychrel-seed-lists))))))))

(display (find-lychrel-seeds 10000 40))
(newline)```
it's quite ugly code atm. i'll clean it up a bit later.

it outputs two lists. the first one is the list of lychrel numbers, the second is the list of seeds:

Code:
```howlingmadhowie% time guile lychrel.scm
((196 295 394 493 592 689 691 788 790 879 887 978 986 1495 1497 1585 1587 1675 1677 1765 1767 1855 1857 1945 1947 1997 2494 2496 2584 2586 2674 2676 2764 2766 2854 2856 2944 2946 2996 3493 3495 3583 3585 3673 3675 3763 3765 3853 3855 3943 3945 3995 4079 4169 4259 4349 4439 4492 4494 4529 4582 4584 4619 4672 4674 4709 4762 4764 4799 4852 4854 4889 4942 4944 4979 5078 5168 5258 5348 5438 5491 5493 5528 5581 5583 5618 5671 5673 5708 5761 5763 5798 5851 5853 5888 5941 5943 5978 5993 6077 6167 6257 6347 6437 6490 6492 6527 6580 6582 6617 6670 6672 6707 6760 6762 6797 6850 6852 6887 6940 6942 6977 6992 7059 7076 7149 7166 7239 7256 7329 7346 7419 7436 7491 7509 7526 7581 7599 7616 7671 7689 7706 7761 7779 7796 7851 7869 7886 7941 7959 7976 7991 8058 8075 8079 8089 8148 8165 8169 8179 8238 8255 8259 8269 8328 8345 8349 8359 8418 8435 8439 8449 8490 8508 8525 8529 8539 8580 8598 8615 8619 8629 8670 8688 8705 8709 8719 8760 8795 8799 8809 8850 8868 8885 8889 8899 8940 8958 8975 8979 8989 8990 9057 9074 9078 9088 9147 9164 9168 9178 9237 9254 9258 9268 9327 9344 9348 9358 9417 9434 9438 9448 9507 9524 9528 9538 9597 9614 9618 9628 9687 9704 9708 9718 9777 9794 9798 9808 9867 9884 9888 9898 9957 9974 9978 9988) (196 879 1997 7059))
guile lychrel.scm  3,90s user 0,03s system 98% cpu 3,992 total```
maybe i'll tidy up the code a bit tomorrow

7. ## Re: Beginner Programming Challenge #10

New version that tries to extract the seeds but still gives a few false positives... I also added a few comments to make things clearer.

PHP Code:
``` readInt             :: String -> IntegerreverseInt          :: Integer -> IntegernextIt              :: Integer -> IntegerisPalindrome        :: Integer -> BooldigitsSum           :: Integer -> IntegerequalDigitsSum      :: Integer -> Integer -> BoolgroupByDigitsSum    :: [Integer] -> [[Integer]]inSameThread        :: Integer -> Integer -> BoolisCandidate         :: (Integer, Integer) -> BoolextractSeeds        :: [Integer] -> [Integer]-- readInt is just an instance of read.-- Takes a string of digits as input, returns the corresponding IntegerreadInt             = read-- reverseInt takes an Integer as input and returns it with its digits-- in reverse order.reverseInt n        = readInt (reverse (show n))-- Self explanatory ;)nextIt n            = n + (reverseInt n)-- Returns True iff the Integer passed as input is a palindrome.isPalindrome n      = ns == reverse ns                        where ns = show n-- Takes a 2-uple (n, p) as input.-- n: number we want to test-- p: number of iterations so far (=0 for an initial call)-- Returns True iff n is a Lychrel candidate, i.e. no palindrome has been-- found after 30-p iterations.isCandidate (_, 30) = TrueisCandidate (n, 0)  = isCandidate (nextIt n, 1)isCandidate (n, p)  = if isPalindrome n                        then False                        else isCandidate (nextIt n, p+1)                        -- Takes an Integer as input and returns the sum of its digits.digitsSum n | n < 10    = n            | otherwise = (mod n 10) + digitsSum (quot n 10)-- Self explanatory ;)equalDigitsSum n p  = digitsSum n == digitsSum p-- Takes a list of Integers and returns a list of lists of Integers-- where the digits of all Integers in the same "sublist" have the same sum.-- We do this because in each "sublist", there will be at most one seed,-- and if there is one, it will be the first element of the list.groupByDigitsSum []     = []groupByDigitsSum (n:ns) = eqn:(groupByDigitsSum noteqn)                            where   eqn = n:[p | p <- ns, equalDigitsSum n p]                                    noteqn = [p | p <- ns, p `notElem` eqn]-- Returns True iff a and b are in the same thread, i.e. they "meet" after-- a sufficient number of iterations.inSameThread a b        -- We need this so we don't try indefinitely to make a and b "meet".        | a > 100000000 = False        | a > b         = inSameThread b a        | a == b        = True        | nextIt a == b = True        | otherwise     = inSameThread (nextIt a) (nextIt b)-- Extract the seeds from a list of candidatesextractSeeds []         = []extractSeeds (n:ns)     = n:(extractSeeds [p | p <- ns, not (inSameThread n p)])main = do        -- List of all candidates < 10,000        let candidates = [n | n <- [1..9999], isCandidate(n, 0)]        putStrLn "Lychrel candidates < 10,000:"        print candidates        putStrLn ""        putStrLn "Possible seeds < 10,000:"        -- List of all possible seeds, i.e. the first element of each group of        -- candidates whose digits have the same sum.        let possibleSeeds = [head l | l <- groupByDigitsSum candidates]        print possibleSeeds        -- Bad news: we still have some non-seeds.        -- Good news: inSameThread is going to help us!        --        -- if a is in possibleSeeds but it not actually a seed, it will be in        -- the thread grown from a seed.        putStrLn ""        print (extractSeeds possibleSeeds)  ```
Code:
```firas@momiji ~ % ./lychrel
Lychrel candidates < 10,000:
[196,295,394,493,592,689,691,788,790,879,887,978,986,1495,1497,1585,1587,1675,1677,1765,1767,1855,1857,1945,1947,1997,2494,2496,2584,2586,2674,2676,2764,2766,2854,2856,2944,2946,2996,3493,3495,3583,3585,3673,3675,3763,3765,3853,3855,3943,3945,3995,4079,4169,4259,4349,4439,4492,4494,4529,4582,4584,4619,4672,4674,4709,4762,4764,4799,4852,4854,4889,4942,4944,4979,4994,5078,5168,5258,5348,5438,5491,5493,5528,5581,5583,5618,5671,5673,5708,5761,5763,5798,5851,5853,5888,5941,5943,5978,5993,6077,6167,6257,6347,6437,6490,6492,6527,6580,6582,6617,6670,6672,6707,6760,6762,6797,6850,6852,6887,6940,6942,6977,6992,7059,7076,7149,7166,7239,7256,7329,7346,7419,7436,7491,7509,7526,7581,7599,7616,7671,7689,7706,7761,7779,7796,7851,7869,7886,7941,7959,7976,7991,8058,8075,8079,8089,8148,8165,8169,8179,8238,8255,8259,8269,8328,8345,8349,8359,8418,8435,8439,8449,8490,8508,8525,8529,8539,8580,8598,8615,8619,8629,8670,8688,8705,8709,8719,8760,8778,8795,8799,8809,8850,8868,8885,8889,8899,8940,8958,8975,8979,8989,8990,9057,9074,9078,9088,9147,9164,9168,9178,9237,9254,9258,9268,9327,9344,9348,9358,9417,9434,9438,9448,9507,9524,9528,9538,9597,9614,9618,9628,9687,9704,9708,9718,9777,9794,9798,9808,9867,9884,9888,9898,9957,9974,9978,9988,9999]

Possible seeds < 10,000:
[196,689,879,1495,1497,1997,4079,4799,7599,8089,8799,8899,9999]

[196,879,1495,1997,7599,8799,9999]```
Last edited by Bachstelze; March 8th, 2010 at 05:05 AM.

8. ## Re: Beginner Programming Challenge #10

Most of the entries have a basic flaw in their design. Review what a Lychrel number is and check your code.

9. ## Re: Beginner Programming Challenge #10

Originally Posted by cprofitt
Most of the entries have a basic flaw in their design. Review what a Lychrel number is and check your code.
err, what's wrong? the entries i've looked at print a list of the candidate lychrel numbers under 10000. isn't that what you wanted?

10. Iced Almond Soy Ubuntu, No Foam
Join Date
Nov 2009
Beans
1,081

## Re: Beginner Programming Challenge #10

The entries already posted tend to reject numbers that are palindromes.