Codegolf - Lisp Edition

I occasionally like a round of code-golf (e.g. recently) and I try to solve these with R, but this one gave me some hope that I could make use of a really cool feature I knew about in common lisp.

lisp is timeless. https://xkcd.com/297

I have occasionally tinkered with lisp - initially because I learned emacs, but later because it’s really interesting and does teach a lot about quoting. Practical Common Lisp is a book I’m still (slowly) making my way through, but it’s a great read so far.

There’s a lot you can do with lisp - you can even connect it up to R (sort of).

Anyway, back to the code-golf. The problem as stated:

It’s 2050, and people have decided to write numbers in a new way. They want less to memorize, and number to be able to be written quicker. For every place value(ones, tens, hundreds, etc.) the number is written with the number in that place, a hyphen, and the place value name. “zero” and it’s place value does not need to be written. The number 0 and negative numbers do not need to be handled, so don’t worry about those.

Input: The input will be a positive integer up to 3 digits.

Output: The output should be a string that looks like something below.

Test cases:

56 => five-ten six
11 => ten one
72 => seven-ten two
478 => four-hundred seven-ten eight
754 => seven-hundred five-ten four
750 => seven-hundred five-ten
507 => five-hundred seven

On it’s own, this seems like it’s going to need some sort of mapping from digits to words. R does have one of those in the {english} package (I know this because I used it the last example in this post) but code-golf doesn’t really allow you to use external packages (mostly).

What gave me hope is something I really wish R had natively, and that the "~R" option of lisp’s format method

(format nil "~R" 14000605) 
"fourteen million six hundred five"

This works really nicely, and seemed like an efficient route to a code-golf solution.

What was missing from this? For starters, we explicity need the tens digits to be of the form ‘n-ten’, which isn’t the case here

(format nil "~R" 478) 
"four hundred seventy-eight"

I considered trying to do a text replacement of “ty” to “-ten” but, alas,

(format nil "~R" 56) 
"fifty-six"

is going to break that pattern.

The alternative, I suppose, is to split out the digits and add the “-hundred” and “-ten” parts. This took me down a rabbit hole, but eventually I managed to pull together enough stack overflow answers to achieve

(map 'list #'digit-char-p (prin1-to-string 458))
(4 5 8)

There’s (hopefully) a faster way to do that, but it works.

Converting each of these digits to words means applying the format in a map. That… also took a while to figure out, and this is probably overkill

(mapcar (lambda (it) (format nil "~R" it)) (map 'list #'digit-char-p (prin1-to-string 458)))
("four" "five" "eight")

Pasting together this result with a list of suffixes requires the concatenate operator, again in a map, but with a lambda function to do this pairwise, otherwise it just appends the lists

(mapcar (lambda(j k) (concatenate 'string j k)) (mapcar (lambda (it) (format nil "~R" it)) (map 'list #'digit-char-p (prin1-to-string 458))) '("-hundred" "-ten" ""))
("four-hundred" "five-ten" "eight")

Nearly there! Or so I thought. How does this suffixing work when there isn’t a hundred digit, e.g. 21?

(print (mapcar (lambda(j k) (concatenate 'string j k)) (mapcar (lambda (it) (format nil "~R" it)) (map 'list #'digit-char-p (prin1-to-string 21))) '("-hundred" "-ten" "")))
("two-hundred" "one-ten") 

Well, that’s not right. But lisp seems okay with having the unequal sized lists. How about starting from the ones digit (i.e. reversed)? That means reversing the split digits list and reversing the suffixes list, doing the operations, then reversing the result

(print (reverse (mapcar (lambda(j k) (concatenate 'string j k)) (mapcar (lambda (it) (format nil "~R" it)) (reverse (map 'list #'digit-char-p (prin1-to-string 21)))) (reverse '("-hundred" "-ten" "")))))
("two-ten" "one") 

Fantastic! And the larger digits?

(print (reverse (mapcar (lambda(j k) (concatenate 'string j k)) (mapcar (lambda (it) (format nil "~R" it)) (reverse (map 'list #'digit-char-p (prin1-to-string 458)))) (reverse '("-hundred" "-ten" "")))))
("four-hundred" "five-ten" "eight")

Woohoo!

The last step is to manually reverse the suffix list, make it a function, and try out the test cases, which you can try out for yourself here

(defun f(n) (reverse (mapcar (lambda(j k) (concatenate 'string j k)) (mapcar (lambda (it) (format nil "~R" it)) (reverse (map 'list #'digit-char-p (prin1-to-string n)))) '("" "-ten" "-hundred"))))

(print (f 56))
(print (f 11))
(print (f 72))
(print (f 478))
(print (f 754))
(print (f 750))
(print (f 507))
("five-ten" "six") 
("one-ten" "one") 
("seven-ten" "two") 
("four-hundred" "seven-ten" "eight") 
("seven-hundred" "five-ten" "four") 
("seven-hundred" "five-ten" "zero") 
("five-hundred" "zero-ten" "seven")

That’s soemwhat close to what the challenge wants, and the ‘Attempt This Online’ tool linked about claims 198 bytes for this solution, but it’s not quite there yet:

  • these should be a single string per test, which I presume involves collapsing the list into a 'string
  • I still have the "zero-ten" and "zero" entries which break the tests
  • "one" should only appear in the ones entry, so 11 should produce "ten one".

At this point, it was 1am, and I figured I’d learned enough for the day. If anyone would like to improve on this solution, please be my guest.

What’s also great to see is that there’s a Julia solution now!

!n=n<10 ? split(" one two three four five six seven eight nine"," ")[n+1] :
n<20 ? "ten "*!(n-10) :
n<(H=100) ? !(n÷10)*"-"*!(10+n%10) :
n<2H ? "hundred "*!(n-H) :
!(n÷H)*"-"*!(H+n%H)
## ! (generic function with 1 method)
tests = [1; 11; 56; 72; 478; 754; 750; 507];
for t in tests
    println(t => !t)
end
## 1 => "one"
## 11 => "ten one"
## 56 => "five-ten six"
## 72 => "seven-ten two"
## 478 => "four-hundred seven-ten eight"
## 754 => "seven-hundred five-ten four"
## 750 => "seven-hundred five-ten "
## 507 => "five-hundred seven"

I’ll be trying to make sense of this for sure. You can try it out yourself here

As usual, the journey was the important part of this - I got to play with and learn some more lisp. There’s no prize for the challenge aside from arbitrary internet points, so I’m entirely happy with how this turned out.


devtools::session_info()
## ─ Session info ───────────────────────────────────────────────────────────────
##  setting  value                       
##  version  R version 4.1.2 (2021-11-01)
##  os       Pop!_OS 21.04               
##  system   x86_64, linux-gnu           
##  ui       X11                         
##  language en_AU:en                    
##  collate  en_AU.UTF-8                 
##  ctype    en_AU.UTF-8                 
##  tz       Australia/Adelaide          
##  date     2022-04-02                  
## 
## ─ Packages ───────────────────────────────────────────────────────────────────
##  package     * version date       lib source        
##  assertthat    0.2.1   2019-03-21 [3] CRAN (R 4.0.1)
##  blogdown      1.8     2022-02-16 [1] CRAN (R 4.1.2)
##  bookdown      0.24    2021-09-02 [1] CRAN (R 4.1.2)
##  brio          1.1.1   2021-01-20 [3] CRAN (R 4.0.3)
##  bslib         0.3.1   2021-10-06 [1] CRAN (R 4.1.2)
##  cachem        1.0.3   2021-02-04 [3] CRAN (R 4.0.3)
##  callr         3.7.0   2021-04-20 [1] CRAN (R 4.1.2)
##  cli           3.2.0   2022-02-14 [1] CRAN (R 4.1.2)
##  crayon        1.5.0   2022-02-14 [1] CRAN (R 4.1.2)
##  DBI           1.1.1   2021-01-15 [3] CRAN (R 4.0.3)
##  desc          1.4.1   2022-03-06 [1] CRAN (R 4.1.2)
##  devtools      2.4.3   2021-11-30 [1] CRAN (R 4.1.2)
##  digest        0.6.27  2020-10-24 [3] CRAN (R 4.0.3)
##  dplyr       * 1.0.8   2022-02-08 [1] CRAN (R 4.1.2)
##  ellipsis      0.3.2   2021-04-29 [1] CRAN (R 4.1.2)
##  evaluate      0.14    2019-05-28 [3] CRAN (R 4.0.1)
##  fansi         0.4.2   2021-01-15 [3] CRAN (R 4.0.3)
##  fastmap       1.1.0   2021-01-25 [3] CRAN (R 4.0.3)
##  fs            1.5.0   2020-07-31 [3] CRAN (R 4.0.2)
##  generics      0.1.0   2020-10-31 [3] CRAN (R 4.0.3)
##  glue          1.6.1   2022-01-22 [1] CRAN (R 4.1.2)
##  htmltools     0.5.2   2021-08-25 [1] CRAN (R 4.1.2)
##  jquerylib     0.1.4   2021-04-26 [1] CRAN (R 4.1.2)
##  jsonlite      1.7.2   2020-12-09 [3] CRAN (R 4.0.3)
##  JuliaCall     0.17.4  2021-05-16 [1] CRAN (R 4.1.2)
##  knitr         1.37    2021-12-16 [1] CRAN (R 4.1.2)
##  lifecycle     1.0.1   2021-09-24 [1] CRAN (R 4.1.2)
##  magrittr      2.0.1   2020-11-17 [3] CRAN (R 4.0.3)
##  memoise       2.0.0   2021-01-26 [3] CRAN (R 4.0.3)
##  pillar        1.7.0   2022-02-01 [1] CRAN (R 4.1.2)
##  pkgbuild      1.2.0   2020-12-15 [3] CRAN (R 4.0.3)
##  pkgconfig     2.0.3   2019-09-22 [3] CRAN (R 4.0.1)
##  pkgload       1.2.4   2021-11-30 [1] CRAN (R 4.1.2)
##  prettyunits   1.1.1   2020-01-24 [3] CRAN (R 4.0.1)
##  processx      3.5.2   2021-04-30 [1] CRAN (R 4.1.2)
##  ps            1.5.0   2020-12-05 [3] CRAN (R 4.0.3)
##  purrr         0.3.4   2020-04-17 [3] CRAN (R 4.0.1)
##  R6            2.5.0   2020-10-28 [3] CRAN (R 4.0.2)
##  Rcpp          1.0.6   2021-01-15 [3] CRAN (R 4.0.3)
##  remotes       2.4.2   2021-11-30 [1] CRAN (R 4.1.2)
##  rlang         1.0.1   2022-02-03 [1] CRAN (R 4.1.2)
##  rmarkdown     2.13    2022-03-10 [1] CRAN (R 4.1.2)
##  rprojroot     2.0.2   2020-11-15 [3] CRAN (R 4.0.3)
##  rstudioapi    0.13    2020-11-12 [3] CRAN (R 4.0.3)
##  sass          0.4.0   2021-05-12 [1] CRAN (R 4.1.2)
##  sessioninfo   1.1.1   2018-11-05 [3] CRAN (R 4.0.1)
##  stringi       1.5.3   2020-09-09 [3] CRAN (R 4.0.2)
##  stringr       1.4.0   2019-02-10 [3] CRAN (R 4.0.1)
##  testthat      3.1.2   2022-01-20 [1] CRAN (R 4.1.2)
##  tibble        3.1.6   2021-11-07 [1] CRAN (R 4.1.2)
##  tidyselect    1.1.2   2022-02-21 [1] CRAN (R 4.1.2)
##  usethis       2.1.5   2021-12-09 [1] CRAN (R 4.1.2)
##  utf8          1.1.4   2018-05-24 [3] CRAN (R 4.0.2)
##  vctrs         0.3.8   2021-04-29 [1] CRAN (R 4.1.2)
##  withr         2.5.0   2022-03-03 [1] CRAN (R 4.1.2)
##  xfun          0.30    2022-03-02 [1] CRAN (R 4.1.2)
##  yaml          2.2.1   2020-02-01 [3] CRAN (R 4.0.1)
## 
## [1] /home/jono/R/x86_64-pc-linux-gnu-library/4.1
## [2] /usr/local/lib/R/site-library
## [3] /usr/lib/R/site-library
## [4] /usr/lib/R/library