Mais desafios em Common Lisp

[Daniel Cerqueira]

A Patrícia lançou um desafio em Common Lisp, que já consegui solucionar.
Não publiquei a solução completa aqui, por isso, caso queiram vê-la, é
só pedir.

Passei momentos de grande diversão, e aprendi muito, a tentar solucionar
estes problemas.

Há mais desafios de programação que queiram publicar? Estou com vontade
de solucionar mais.

[Patricia Ferreira]

Daniel Cerqueira <dan....@brilhante.top> writes:

> A Patrícia lançou um desafio em Common Lisp, que já consegui solucionar.
> Não publiquei a solução completa aqui, por isso, caso queiram vê-la, é
> só pedir.

É simples? Não investiguei suas soluções postadas até agora porque elas
tomam bastante energia. Tudo que é simples é interessante.

> Passei momentos de grande diversão, e aprendi muito, a tentar solucionar
> estes problemas.
>
> Há mais desafios de programação que queiram publicar? Estou com vontade
> de solucionar mais.

Estou trabalhando num neste exato momento.

O que faz este procedimento?

(defun split-sequence (delim ls acc &key limit (so-far 1))
(let* ((len (length ls))
(delim delim)
(pos (search delim ls))
(n-take (or pos len))
(n-drop (if pos
(+ n-take (length delim))
n-take)))
(cond ((zerop len) acc)
((and limit (= so-far limit)) (list ls))
(t (split-sequence
delim (drop n-drop ls)
(cons (take n-take ls) acc)
:limit limit
:so-far (1+ so-far))))))

(defun take (n seq) (subseq seq 0 n))
(defun drop (n seq) (subseq seq n))

Pergunta principal. Por que ele é tão lento? :-)

* (time (length (split-sequence (list 13 10) x nil)))
Evaluation took:
65.710 seconds of real time
65.671875 seconds of total run time (47.093750 user, 18.578125 system)
[ Run times consist of 23.968 seconds GC time, and 41.704 seconds non-GC time. ]
99.94% CPU
170,322,749,168 processor cycles
79,439,358,864 bytes consed

11585
*

Quem é x? X é um artigo NNTP com um arquivo PDF de 610 KiB anexado. As
linhas são todas curtas.

--8<---------------cut here---------------start------------->8---
Message-Id: <tnkqcqnuujaljsvmzvuc@loop>
Content-Type: multipart/mixed; boundary="------------PeB0GiqcER01ZhCmBvnP2yr6"
Date: Wed, 7 Feb 2024 22:22:57 -0300
Mime-Version: 1.0
User-Agent: Mozilla Thunderbird
Newsgroups: local.test
Content-Language: en-US
From: Sabrina Wadsworth <s...@rina.org>
Subject: juris hartmanis

This is a multi-part message in MIME format.
--------------PeB0GiqcER01ZhCmBvnP2yr6
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

--------------PeB0GiqcER01ZhCmBvnP2yr6
Content-Type: application/pdf;
name="juris-hartmanis-godel-von-neumann-1956-89-994.pdf"
Content-Disposition: attachment;
filename="juris-hartmanis-godel-von-neumann-1956-89-994.pdf"
Content-Transfer-Encoding: base64

JVBERi0xLjIKekdf1fnfSqQYt7AjczYfpmRSIEyEcx8KMSAwIG9iago8PAovVHlwZSAvQ2F0
YWxvZwovUGFnZXMgMyAwIFIKL091dGxpbmVzIDIgMCBSCj4+CmVuZG9iagoyIDAgb2JqCjw8
[...]
IDAwMDAwIG4gCjAwMDA2MjI5NTQgMDAwMDAgbiAKdHJhaWxlcgo8PAovU2l6ZSA0NgovUm9v
dCAxIDAgUgovSW5mbyA0NSAwIFIKPj4Kc3RhcnR4cmVmCjYyMzI4NgolJUVPRgo=

--------------PeB0GiqcER01ZhCmBvnP2yr6--
--8<---------------cut here---------------end--------------->8---

Eis os primeiros 1000 bytes de x.

* (take 1000 x)
(77 101 115 115 97 103 101 45 73 100 58 32 60 116 110 107 113 99 113 110 117
117 106 97 108 106 115 118 109 122 118 117 99 64 108 111 111 112 62 13 10 67
111 110 116 101 110 116 45 84 121 112 101 58 32 109 117 108 116 105 112 97 114
116 47 109 105 120 101 100 59 32 98 111 117 110 100 97 114 121 61 34 45 45 45
45 45 45 45 45 45 45 45 45 80 101 66 48 71 105 113 99 69 82 48 49 90 104 67
109 66 118 110 80 50 121 114 54 34 13 10 68 97 116 101 58 32 87 101 100 44 32
55 32 70 101 98 32 50 48 50 52 32 50 50 58 50 50 58 53 55 32 45 48 51 48 48 13
10 77 105 109 101 45 86 101 114 115 105 111 110 58 32 49 46 48 13 10 85 115
101 114 45 65 103 101 110 116 58 32 77 111 122 105 108 108 97 32 84 104 117
110 100 101 114 98 105 114 100 13 10 78 101 119 115 103 114 111 117 112 115 58
32 108 111 99 97 108 46 116 101 115 116 13 10 67 111 110 116 101 110 116 45 76
97 110 103 117 97 103 101 58 32 101 110 45 85 83 13 10 70 114 111 109 58 32 83
97 98 114 105 110 97 32 87 97 100 115 119 111 114 116 104 32 60 115 97 98 64
114 105 110 97 46 111 114 103 62 13 10 83 117 98 106 101 99 116 58 32 106 117
114 105 115 32 104 97 114 116 109 97 110 105 115 13 10 13 10 84 104 105 115 32
105 115 32 97 32 109 117 108 116 105 45 112 97 114 116 32 109 101 115 115 97
103 101 32 105 110 32 77 73 77 69 32 102 111 114 109 97 116 46 13 10 45 45 45
45 45 45 45 45 45 45 45 45 45 45 80 101 66 48 71 105 113 99 69 82 48 49 90 104
67 109 66 118 110 80 50 121 114 54 13 10 67 111 110 116 101 110 116 45 84 121
112 101 58 32 116 101 120 116 47 112 108 97 105 110 59 32 99 104 97 114 115
101 116 61 85 84 70 45 56 13 10 67 111 110 116 101 110 116 45 84 114 97 110
115 102 101 114 45 69 110 99 111 100 105 110 103 58 32 55 98 105 116 13 10 13
10 45 45 45 45 45 45 45 45 45 45 45 45 45 45 80 101 66 48 71 105 113 99 69 82
48 49 90 104 67 109 66 118 110 80 50 121 114 54 13 10 67 111 110 116 101 110
116 45 84 121 112 101 58 32 97 112 112 108 105 99 97 116 105 111 110 47 112
100 102 59 13 10 32 110 97 109 101 61 34 106 117 114 105 115 45 104 97 114 116
109 97 110 105 115 45 103 111 100 101 108 45 118 111 110 45 110 101 117 109 97
110 110 45 49 57 53 54 45 56 57 45 57 57 52 46 112 100 102 34 13 10 67 111 110
116 101 110 116 45 68 105 115 112 111 115 105 116 105 111 110 58 32 97 116 116
97 99 104 109 101 110 116 59 13 10 32 102 105 108 101 110 97 109 101 61 34 106
117 114 105 115 45 104 97 114 116 109 97 110 105 115 45 103 111 100 101 108 45
118 111 110 45 110 101 117 109 97 110 110 45 49 57 53 54 45 56 57 45 57 57 52
46 112 100 102 34 13 10 67 111 110 116 101 110 116 45 84 114 97 110 115 102
101 114 45 69 110 99 111 100 105 110 103 58 32 98 97 115 101 54 52 13 10 13 10
74 86 66 69 82 105 48 120 76 106 73 75 101 107 100 102 49 102 110 102 83 113
81 89 116 55 65 106 99 122 89 102 112 109 82 83 73 69 121 69 99 120 56 75 77
83 65 119 73 71 57 105 97 103 111 56 80 65 111 118 86 72 108 119 90 83 65 118
81 50 70 48 13 10 89 87 120 118 90 119 111 118 85 71 70 110 90 88 77 103 77
121 65 119 73 70 73 75 76 48 57 49 100 71 120 112 98 109 86 122 73 68 73 103
77 67 66 83 67 106 52 43 67 109 86 117 90 71 57 105 97 103 111 121 73 68 65
103 98 50 74 113 67 106 119 56 13 10 67 105 57 85 101 88 66 108 73 67 57 80
100 88 82 115 97 87 53 108 99 119 111 118 81 50 57 49 98 110 81 103 77 84 65
75 76 48 90 112 99 110 78 48 73 68 77 49 73 68 65 103 85 103 111 118 84 71 70
122 100 67 65 48 78 67 65 119 73 70 73 75 13 10 80 106 52 75 90 87 53 107 98
50 74 113 67 106 77 103 77 67 66 118 89 109 111)

Consegue resolver esse mistério? Te agradeço bastante!

[Nuno Silva]

Se alguém conhecer algum conjunto de desafios interessantes que estejam
também disponíveis em formato para leitura offline e impressão (PDF, por
exemplo), digam, por favor.

Conheço o Project Euler e já ouvi falar do Advent of Code, mas este
último penso que tenta mesmo proibir a reprodução do texto dos
problemas. O Project Euler ainda não vi se tem os problemas disponíveis
para download.

Seria útil poder imprimir para ir pensando e programando em contextos
offline e sem computador em condições, por exemplo, num comboio.

--
Nuno Silva

[Patricia Ferreira]

Quantos desafios você resolve em um dia?

Tenho a impressão de que um livro seja interessante. Você lê ele
offline sem computador. Se estiver fácil demais, leia o próximo
capítulo.

Você tá querendo exercícios especificamente? Num nível fácil, ``ANSI
Common Lisp'' de Paul Graham está repleto de exercícios com o intuito de
apresentar a linguagem.

Pra quem já tem algum conforto, acho que ``Let Over Lambda'' de Doug
Hoyte é bem legal. Estou lendo ele sem ter lido ``On Lisp'' de Paul
Graham e ele assume que o leitor já leu ``On Lisp''.

[Nuno Silva]

On 2024-02-09, Patricia Ferreira wrote:

> Nuno Silva <nunoj...@invalid.invalid> writes:
>
>> On 2024-02-08, Daniel Cerqueira wrote:
>>
>>> A Patrícia lançou um desafio em Common Lisp, que já consegui solucionar.
>>> Não publiquei a solução completa aqui, por isso, caso queiram vê-la, é
>>> só pedir.
>>>
>>> Passei momentos de grande diversão, e aprendi muito, a tentar solucionar
>>> estes problemas.
>>>
>>> Há mais desafios de programação que queiram publicar? Estou com vontade
>>> de solucionar mais.
>>
>> Se alguém conhecer algum conjunto de desafios interessantes que estejam
>> também disponíveis em formato para leitura offline e impressão (PDF, por
>> exemplo), digam, por favor.
>>
>> Conheço o Project Euler e já ouvi falar do Advent of Code, mas este
>> último penso que tenta mesmo proibir a reprodução do texto dos
>> problemas. O Project Euler ainda não vi se tem os problemas disponíveis
>> para download.
>>
>> Seria útil poder imprimir para ir pensando e programando em contextos
>> offline e sem computador em condições, por exemplo, num comboio.
>
> Quantos desafios você resolve em um dia?

Dependerá do género de desafio. Já encontrei um PDF com os problemas do
Project Euler, e ver isso relembrou-me que talvez não seja o melhor, há
problemas que penso exigirem conhecimentos matemáticos mais
aprofundados, quando neste momento pretendo algo mais de, por exemplo,
algoritmos (que não deixam de ser também matemática, claro).

Mas penso que tens toda a razão que um livro provavelmente será a melhor
fonte para isto. Estava a tentar separar o "resolver problemas" da
leitura de um livro, mas talvez ir à procura destes desafios em livros
seja o melhor, mesmo.

> Tenho a impressão de que um livro seja interessante. Você lê ele
> offline sem computador. Se estiver fácil demais, leia o próximo
> capítulo.
>
> Você tá querendo exercícios especificamente? Num nível fácil, ``ANSI
> Common Lisp'' de Paul Graham está repleto de exercícios com o intuito de
> apresentar a linguagem.
>
> Pra quem já tem algum conforto, acho que ``Let Over Lambda'' de Doug
> Hoyte é bem legal. Estou lendo ele sem ter lido ``On Lisp'' de Paul
> Graham e ele assume que o leitor já leu ``On Lisp''.

--
Nuno Silva

[Patricia Ferreira]

Nuno Silva <nunoj...@invalid.invalid> writes:

[...]

>>> Se alguém conhecer algum conjunto de desafios interessantes que estejam
>>> também disponíveis em formato para leitura offline e impressão (PDF, por
>>> exemplo), digam, por favor.
>>>
>>> Conheço o Project Euler e já ouvi falar do Advent of Code, mas este
>>> último penso que tenta mesmo proibir a reprodução do texto dos
>>> problemas. O Project Euler ainda não vi se tem os problemas disponíveis
>>> para download.
>>>
>>> Seria útil poder imprimir para ir pensando e programando em contextos
>>> offline e sem computador em condições, por exemplo, num comboio.
>>
>> Quantos desafios você resolve em um dia?
>
> Dependerá do género de desafio. Já encontrei um PDF com os problemas do
> Project Euler, e ver isso relembrou-me que talvez não seja o melhor, há
> problemas que penso exigirem conhecimentos matemáticos mais
> aprofundados, quando neste momento pretendo algo mais de, por exemplo,
> algoritmos (que não deixam de ser também matemática, claro).
>
> Mas penso que tens toda a razão que um livro provavelmente será a melhor
> fonte para isto. Estava a tentar separar o "resolver problemas" da
> leitura de um livro, mas talvez ir à procura destes desafios em livros
> seja o melhor, mesmo.

Por que não o SICP? (Já leu o HtDP?)

>> Tenho a impressão de que um livro seja interessante. Você lê ele
>> offline sem computador. Se estiver fácil demais, leia o próximo
>> capítulo.
>>
>> Você tá querendo exercícios especificamente? Num nível fácil, ``ANSI
>> Common Lisp'' de Paul Graham está repleto de exercícios com o intuito de
>> apresentar a linguagem.
>>
>> Pra quem já tem algum conforto, acho que ``Let Over Lambda'' de Doug
>> Hoyte é bem legal. Estou lendo ele sem ter lido ``On Lisp'' de Paul
>> Graham e ele assume que o leitor já leu ``On Lisp''.

Li /Let Over Lambda/ até o capítulo 5 com conforto. Chegando ao
capítulo 6, resolvi voltar pro /On Lisp/.

[Nuno Silva]

On 2024-02-19, Patricia Ferreira wrote:

> Nuno Silva <nunoj...@invalid.invalid> writes:
>
> [...]
>
>>>> Se alguém conhecer algum conjunto de desafios interessantes que estejam
>>>> também disponíveis em formato para leitura offline e impressão (PDF, por
>>>> exemplo), digam, por favor.
>>>>
>>>> Conheço o Project Euler e já ouvi falar do Advent of Code, mas este
>>>> último penso que tenta mesmo proibir a reprodução do texto dos
>>>> problemas. O Project Euler ainda não vi se tem os problemas disponíveis
>>>> para download.
>>>>
>>>> Seria útil poder imprimir para ir pensando e programando em contextos
>>>> offline e sem computador em condições, por exemplo, num comboio.
>>>
>>> Quantos desafios você resolve em um dia?
>>
>> Dependerá do género de desafio. Já encontrei um PDF com os problemas do
>> Project Euler, e ver isso relembrou-me que talvez não seja o melhor, há
>> problemas que penso exigirem conhecimentos matemáticos mais
>> aprofundados, quando neste momento pretendo algo mais de, por exemplo,
>> algoritmos (que não deixam de ser também matemática, claro).
>>
>> Mas penso que tens toda a razão que um livro provavelmente será a melhor
>> fonte para isto. Estava a tentar separar o "resolver problemas" da
>> leitura de um livro, mas talvez ir à procura destes desafios em livros
>> seja o melhor, mesmo.
>
> Por que não o SICP? (Já leu o HtDP?)

Talvez até venha a ser, ainda não explorei muito o assunto. Estava
simplesmente a pensar mais em "lista de desafios", mas verei então
o que arranjo a partir de livros.

Só que um dia destes também tenho de arranjar tempo para reler o "The
Art of Prolog"!

--
Nuno Silva

[Patricia Ferreira]

O SICP aborda programação lógica no livro. É uma das coisas que eles
mostram como forma de ilustrar o calculador meta-circular.