Beginner Programming Challenge #10
Welcome to the 10th programming challenge, sponsored by The Ubuntu Beginners Team Development Focus Group. I have been tasked with coming up with this challenge by virtue of 'winning' programming challenge #9.
background:
-----
I have a connection with Lychrel numbers so I wanted to make this challenge something in relation to those.
lychrel numbers:
-----
A Lychrel number is a natural number which cannot form a palindrome through the iterative process of repeatedly reversing its digits and adding the resulting numbers. The name "Lychrel" was coined by Wade VanLandingham; a rough anagram of his girlfriend's name Cheryl.
example: The reverse and add process produces the sum of a number and the number formed by reversing the order of its digits.eg. 56 + 65 = 121, 125 + 521 = 646, 9999 + 9999 = 19998
task:
-----
Find all the Lychrel candidate numbers below 10,000
:KS bonus points:
-----
Find all the Lychrel seed numbers below 10,000
:confused: Disqualified Entries:
-----
Any overly obfuscated code will be immediately disqualified without account for programmers skill. Please remember that these challenges are for beginners and therefore the code should be easily readable and well commented.
Any non-beginner entries will not be judged. Please use common sense when posting code examples. Please do not give beginners a copy paste solution before they have had a chance to try this for themselves.
:KS Assistance:
-----
If you require any help with this challenge please do not hesitate to come and chat to the development focus group. We have a channel on irc.freenode.net #ubuntu-beginners-dev
----------
OK -- time for you all to be :guitar: rockstars!
Re: Beginner Programming Challenge #10
Looks great! Let's see some entries, people!
Re: Beginner Programming Challenge #10
I'm not sure I'd call this a "beginner" challenge...
Re: Beginner Programming Challenge #10
Quote:
Originally Posted by
schauerlich
I'm not sure I'd call this a "beginner" challenge...
+1
Is 196 a Lychrel number? Nobody knows, it hasn't been proven yet. So 196 would be a Lychrel candidate number? But how many iterations should be made before calling a number a Lychrel candidate? And what is a Lychrel seed number?
Re: Beginner Programming Challenge #10
I think its a good challenge.
I am going to do it in a language I am still a bit green with: Python :D
-Silver Fox
Re: Beginner Programming Challenge #10
Quote:
Originally Posted by
conehead77
What is a Lychrel seed number?
From Wikipedia:
Quote:
Seed numbers are a subset of Lychrel numbers, that is the smallest number of each non palindrome producing thread. A seed number may be a palindrome itself.
-Silver Fox
Re: Beginner Programming Challenge #10
Quote:
Originally Posted by
conehead77
+1
Is 196 a Lychrel number? Nobody knows, it hasn't been proven yet. So 196 would be a Lychrel candidate number? But how many iterations should be made before calling a number a Lychrel candidate? And what is a Lychrel seed number?
Wikipedia says that the largest number of iterations for a number under 10,000 to resolve to a palindrome is 24. So I'd say go for 30 iterations before calling it a lychrel candidate.
Re: Beginner Programming Challenge #10
Obligatory Haskell. ;)
PHP Code:
readInt :: String -> Int
reverseInt :: Int -> Int
isPalindrome :: Int -> Bool
isCandidate :: (Int, Int) -> Bool
readInt = read
reverseInt n = if n < 10
then n
else readInt (reverse (show n))
isPalindrome n = if n < 10
then True
else ns == reverse ns
where ns = show n
isCandidate (30, _) = True
isCandidate (n, p) = if isPalindrome p
then False
else isCandidate (n + 1, p + reverseInt p)
main = print [n | n <- [1..9999], isCandidate (0, n)]
I'll do the seed-hunting later. I don't think it really needs commenting, but someone correct me if I'm wrong. :p
Re: Beginner Programming Challenge #10
Quote:
Originally Posted by
schauerlich
Wikipedia says that the largest number of iterations for a number under 10,000 to resolve to a palindrome is 24. So I'd say go for 30 iterations before calling it a lychrel candidate.
Yup. I went up to 10,000 iterations, and it gave me the same results as 30.
Re: Beginner Programming Challenge #10
here's my first scheme implementation.
Code:
(use-modules (ice-9 format))
(define num->chain
(lambda (num)
(if (< num 10)
(list num)
(cons (remainder num 10) (num->chain (quotient num 10))))))
(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 empty-chain? null?)
(define chain->num
(lambda (chain)
(if (empty-chain? 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-numbers
(lambda (limit max-tries)
(define iterate
(lambda (chain)
(num->chain (+ (chain->num chain) (chain->num (reverse-chain chain))))))
(define is-lychrel-number?
(lambda (chain try)
(cond ((> try max-tries)
#f)
((is-palindrome? chain)
(chain->num chain))
(else
(is-lychrel-number? (iterate chain) (+ try 1))))))
(define loop
(lambda (number)
(if (< number limit)
(let ((result (is-lychrel-number? (num->chain number) 0)))
(if (not result)
(format #t "~d is a candidate\n" number))
(loop (+ 1 number))))))
(loop 1)))
(find-lychrel-numbers 10000 40)
it works by storing the numbers in chains of digits and then reversing these chains and adding them. this saves the overhead of using int->string and string->int conversion.
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