Axel Reichert

2020-05-13 20:10:29 UTC

Hello,

my programming language background is mostly an imperative one, even if

for more than a decade now augmented by Python. Maybe two years back I

came across functional programming and was immediately hooked by the

concepts. As an old .emacs tinkerer I gave the "real" Lisp a try.

Yesterday I heard about a nice math question for talented kids and

thought this to be a nice exercise to try my Common Lisp skills (I know

how to tackle the problem from a pure mathematical point of view, so

this is not the point here). The question is about so-called "bellied"

numbers, defined as 4-digit integers for which the sum of the two

"middle" digits is smaller than the sum of the two outer digits. So 1265

is bellied, while 4247 is not.

This checking part is easy:

(defun bellied-number-p (n)

(> (+ (mod (truncate n 10) 10) (mod (truncate n 100) 10))

(+ (mod n 10) (truncate n 1000))))

Now the task is to find the longest, uninterrupted sequence of bellied

numbers within all 4-digit number, hence from 1000 to 9999. And this is

where I terribly screwed up:

While the following code does the job,

(let ((max-length 0)

(current-length 0)

(last-bellied-number 0))

(dotimes (m 9000)

(let ((n (+ 1000 m)))

(if (bellied-number-p n)

(incf current-length)

(progn

(when (> current-length max-length)

(setf max-length current-length)

(setf last-bellied-number (1- n)))

(setf current-length 0)))))

(print (format t "~&Longest sequence of ~a bellied numbers ends at ~a."

max-length last-bellied-number)))

when I looked at this monster, I thought "Fortran in every language

syndrome". So I had to try harder to get something without loops, without

side effects except for the final print, without global state, hopefully

something nice with mapcar et. al. and tail-recursion. (-:

I found it terribly difficult to wrap my head around these concepts, as

brilliant as I think them to be from a theoretical point of view. Deeply

ingrained habits are no so easy to get rid of, it seemed ...

It got worse, my next try applied some higher order function in

composition, but got the wrong result and was a real "Frankencode":

(ql:quickload :alexandria)

(ql:quickload "cl-ppcre")

(defun bellied-number-p (n)

(if

(> (+ (mod (truncate n 10) 10) (mod (truncate n 100) 10))

(+ (mod n 10) (truncate n 1000)))

1 0))

(let ((candidates (alexandria:iota 1000 :start 1000)))

(apply #'max

(mapcar #'length

(ppcre:all-matches-as-strings

"1+"

(substitute #\linefeed #\0

(remove #\SPACE

(format nil "~a"

(mapcar #'bellied-number-p

candidates))))))))

This one is "Shell scripting in every language syndrome", compare with:

seq 1000 9999 | sed 's/\(.\)/\1 /g' | \

awk '{if ($2 + $3 > $1 + $4) {print 1} else {print "0"}}' | \

tr -d '\n' | tr -s "0" "\n" | sort | tail -n 1 | tr -d '\n' | wc -c

This is a neat and simple one-liner which took me 5 minutes to cobble

together instead of 5 hours ...

Of course it is a misuse to convert a list into a string that is then

tortured to extract the (originally numerical) information hidden in it,

etc. etc.

Two questions, though, may be allowed on this:

1. I am quite sure that the wrong result is due to the pretty printing

of the Lisp output, such that line wrapping occurs and the regex fails

to count the subsequent 1s correctly. How could I (in general, not for

this problem) increase the line width for "formatted" output by the Lisp

printer?

2. Calling one list-manipulating function after the other seems to be an

elegant concept (probably because it reminds me on pipes in shell

programming). However, I have no idea how one could avoid the above

indentation nightmare. How to deal with and un-clutter this excessive

chaining?

Finally, after another one or two hours of frustration, I got

enlightened (or so it seemed to me by comparison) and came up with this:

(defun bellied-checker (start end)

(labels ((bellied-checker-helper (n n-max this-length max-length)

(if (<= n n-max)

(if (> (+ (mod (truncate n 10) 10)

(mod (truncate n 100) 10))

(+ (mod n 10) (truncate n 1000)))

(bellied-checker-helper (1+ n) n-max

(1+ this-length) max-length)

(bellied-checker-helper (1+ n) n-max 0

(max this-length max-length)))

(print max-length)))))

(bellied-checker-helper start end 0 0))

No global state, nested function definitions, no loops, recursion (is it

tail-recursive? I think so).

From an experienced Lisper's point of view: How can this be improved

(indentation, modularization, ...)?

If you have read this far, am I already thankful and would be even more

so for each and every criticism!

Best regards

Axel (who fortunately for himself and the rest of world is not a professional

programmer)

my programming language background is mostly an imperative one, even if

for more than a decade now augmented by Python. Maybe two years back I

came across functional programming and was immediately hooked by the

concepts. As an old .emacs tinkerer I gave the "real" Lisp a try.

Yesterday I heard about a nice math question for talented kids and

thought this to be a nice exercise to try my Common Lisp skills (I know

how to tackle the problem from a pure mathematical point of view, so

this is not the point here). The question is about so-called "bellied"

numbers, defined as 4-digit integers for which the sum of the two

"middle" digits is smaller than the sum of the two outer digits. So 1265

is bellied, while 4247 is not.

This checking part is easy:

(defun bellied-number-p (n)

(> (+ (mod (truncate n 10) 10) (mod (truncate n 100) 10))

(+ (mod n 10) (truncate n 1000))))

Now the task is to find the longest, uninterrupted sequence of bellied

numbers within all 4-digit number, hence from 1000 to 9999. And this is

where I terribly screwed up:

While the following code does the job,

(let ((max-length 0)

(current-length 0)

(last-bellied-number 0))

(dotimes (m 9000)

(let ((n (+ 1000 m)))

(if (bellied-number-p n)

(incf current-length)

(progn

(when (> current-length max-length)

(setf max-length current-length)

(setf last-bellied-number (1- n)))

(setf current-length 0)))))

(print (format t "~&Longest sequence of ~a bellied numbers ends at ~a."

max-length last-bellied-number)))

when I looked at this monster, I thought "Fortran in every language

syndrome". So I had to try harder to get something without loops, without

side effects except for the final print, without global state, hopefully

something nice with mapcar et. al. and tail-recursion. (-:

I found it terribly difficult to wrap my head around these concepts, as

brilliant as I think them to be from a theoretical point of view. Deeply

ingrained habits are no so easy to get rid of, it seemed ...

It got worse, my next try applied some higher order function in

composition, but got the wrong result and was a real "Frankencode":

(ql:quickload :alexandria)

(ql:quickload "cl-ppcre")

(defun bellied-number-p (n)

(if

(> (+ (mod (truncate n 10) 10) (mod (truncate n 100) 10))

(+ (mod n 10) (truncate n 1000)))

1 0))

(let ((candidates (alexandria:iota 1000 :start 1000)))

(apply #'max

(mapcar #'length

(ppcre:all-matches-as-strings

"1+"

(substitute #\linefeed #\0

(remove #\SPACE

(format nil "~a"

(mapcar #'bellied-number-p

candidates))))))))

This one is "Shell scripting in every language syndrome", compare with:

seq 1000 9999 | sed 's/\(.\)/\1 /g' | \

awk '{if ($2 + $3 > $1 + $4) {print 1} else {print "0"}}' | \

tr -d '\n' | tr -s "0" "\n" | sort | tail -n 1 | tr -d '\n' | wc -c

This is a neat and simple one-liner which took me 5 minutes to cobble

together instead of 5 hours ...

Of course it is a misuse to convert a list into a string that is then

tortured to extract the (originally numerical) information hidden in it,

etc. etc.

Two questions, though, may be allowed on this:

1. I am quite sure that the wrong result is due to the pretty printing

of the Lisp output, such that line wrapping occurs and the regex fails

to count the subsequent 1s correctly. How could I (in general, not for

this problem) increase the line width for "formatted" output by the Lisp

printer?

2. Calling one list-manipulating function after the other seems to be an

elegant concept (probably because it reminds me on pipes in shell

programming). However, I have no idea how one could avoid the above

indentation nightmare. How to deal with and un-clutter this excessive

chaining?

Finally, after another one or two hours of frustration, I got

enlightened (or so it seemed to me by comparison) and came up with this:

(defun bellied-checker (start end)

(labels ((bellied-checker-helper (n n-max this-length max-length)

(if (<= n n-max)

(if (> (+ (mod (truncate n 10) 10)

(mod (truncate n 100) 10))

(+ (mod n 10) (truncate n 1000)))

(bellied-checker-helper (1+ n) n-max

(1+ this-length) max-length)

(bellied-checker-helper (1+ n) n-max 0

(max this-length max-length)))

(print max-length)))))

(bellied-checker-helper start end 0 0))

No global state, nested function definitions, no loops, recursion (is it

tail-recursive? I think so).

From an experienced Lisper's point of view: How can this be improved

(indentation, modularization, ...)?

If you have read this far, am I already thankful and would be even more

so for each and every criticism!

Best regards

Axel (who fortunately for himself and the rest of world is not a professional

programmer)

--

-X- | in memoriam John Conway

--X | 1937-2020

XXX | A glider from his "Game of Life"

-X- | in memoriam John Conway

--X | 1937-2020

XXX | A glider from his "Game of Life"