-
Notifications
You must be signed in to change notification settings - Fork 0
/
99_problems_klong_solution.html
2332 lines (2283 loc) · 122 KB
/
99_problems_klong_solution.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<html><head><title>niplav</title>
<link href="./favicon.png" rel="shortcut icon" type="image/png"/>
<link href="main.css" rel="stylesheet" type="text/css"/>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type"/>
<!DOCTYPE HTML>
<style type="text/css">
code.has-jax {font: inherit; font-size: 100%; background: inherit; border: inherit;}
</style>
<script async="" src="./mathjax/latest.js?config=TeX-MML-AM_CHTML" type="text/javascript">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js"],
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
},
"HTML-CSS": { availableFonts: ["TeX"] }
});
</script>
<script>
document.addEventListener('DOMContentLoaded', function () {
// Change the title to the h1 header
var title = document.querySelector('h1')
if(title) {
var title_elem = document.querySelector('title')
title_elem.textContent=title.textContent + " – niplav"
}
});
</script>
</head><body><h2 id="home"><a href="./index.html">home</a></h2>
<p><em>author: niplav, created: 2019-02-10, modified: 2022-02-23, language: english, status: in progress, importance: 3, confidence: highly likely</em></p>
<blockquote>
<p><strong>Solutions to the <a href="./99_klong_problems.html" title="99 Klong
Problems">99 problems</a> in <a href="http://t3x.org/klong/index.html">Klong</a>, <a href="https://en.wikipedia.org/wiki/Literate_programming">literate
programming</a>
style. Attempts to produce the shortest complete solution to these
problems up to date.</strong></p>
</blockquote><div class="toc"><div class="toc-title">Contents</div><ul><li><a href="#Acknowledgements">Acknowledgements</a><ul></ul></li><li><a href="#Code">Code</a><ul></ul></li><li><a href="#Conventions">Conventions</a><ul></ul></li><li><a href="#Prerequisites">Prerequisites</a><ul></ul></li><li><a href="#Working_with_Lists">Working with Lists</a><ul><li><a href="#P01__Find_the_last_element_of_a_list">P01 (*) Find the last element of a list.</a><ul></ul></li><li><a href="#P02__Find_the_last_but_one_sublist_of_a_list">P02 (*) Find the last but one sublist of a list.</a><ul></ul></li><li><a href="#P03__Find_the_Kth_element_of_a_list">P03 (*) Find the K'th element of a list.</a><ul></ul></li><li><a href="#P04__Find_the_number_of_elements_of_a_list">P04 (*) Find the number of elements of a list.</a><ul></ul></li><li><a href="#P05__Reverse_a_list">P05 (*) Reverse a list.</a><ul></ul></li><li><a href="#P06__Find_out_whether_a_list_is_a_palindrome">P06 (*) Find out whether a list is a palindrome.</a><ul></ul></li><li><a href="#P07__Flatten_a_nested_list_structure">P07 (**) Flatten a nested list structure.</a><ul></ul></li><li><a href="#P08__Eliminate_consecutive_duplicates_of_list_elements">P08 (**) Eliminate consecutive duplicates of list elements.</a><ul></ul></li><li><a href="#P09__Pack_consecutive_duplicates_of_list_elements_into_sublists">P09 (**) Pack consecutive duplicates of list elements into sublists.</a><ul></ul></li><li><a href="#P10__Runlength_encoding_of_a_list">P10 (*) Run-length encoding of a list.</a><ul></ul></li><li><a href="#P11__Modified_runlength_encoding">P11 (*) Modified run-length encoding.</a><ul></ul></li><li><a href="#P12__Decode_a_runlength_encoded_list">P12 (**) Decode a run-length encoded list.</a><ul></ul></li><li><a href="#P13__Runlength_encoding_of_a_list_direct_solution">P13 (**) Run-length encoding of a list (direct solution).</a><ul></ul></li><li><a href="#P14__Duplicate_the_elements_of_a_list">P14 (*) Duplicate the elements of a list.</a><ul></ul></li><li><a href="#P15__Replicate_the_elements_of_a_list_a_given_number_of_times">P15 (**) Replicate the elements of a list a given number of times.</a><ul></ul></li><li><a href="#P16__Drop_every_Nth_element_from_a_list">P16 (**) Drop every N'th element from a list.</a><ul></ul></li><li><a href="#P17__Split_a_list_into_two_parts_the_length_of_the_first_part_is_given">P17: (*) Split a list into two parts, the length of the first part is given.</a><ul></ul></li><li><a href="#P18__Extract_a_slice_from_a_list">P18: (**) Extract a slice from a list.</a><ul></ul></li><li><a href="#P19__Rotate_a_list_N_places_to_the_left">P19: (**) Rotate a list N places to the left.</a><ul></ul></li><li><a href="#P20__Remove_the_Kth_element_from_a_list">P20: (*) Remove the K'th element from a list.</a><ul></ul></li><li><a href="#P21__Insert_an_element_at_a_given_position_into_a_list">P21: (*) Insert an element at a given position into a list.</a><ul></ul></li><li><a href="#P22__Create_a_list_containing_all_integers_within_a_given_range">P22: (*) Create a list containing all integers within a given range.</a><ul></ul></li><li><a href="#P23__Extract_a_given_number_of_randomly_selected_elements_from_a_list">P23 (**) Extract a given number of randomly selected elements from a list.</a><ul></ul></li><li><a href="#P24__Lotto_Draw_N_different_random_numbers_from_the_set_1M">P24 (*) Lotto: Draw N different random numbers from the set 1..M.</a><ul></ul></li><li><a href="#P25__Generate_a_random_permutation_of_the_elements_of_a_list">P25 (*) Generate a random permutation of the elements of a list.</a><ul></ul></li><li><a href="#P26__Generate_the_combinations_of_K_distinct_objects_chosen_from_the_N_elements_of_a_list">P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.</a><ul></ul></li><li><a href="#P27__Group_the_elements_of_a_set_into_disjoint_subsets">P27 (**) Group the elements of a set into disjoint subsets.</a><ul></ul></li><li><a href="#P28__Sorting_a_list_of_lists_according_to_length_of_sublists">P28 (**) Sorting a list of lists according to length of sublists</a><ul></ul></li></ul></li><li><a href="#Arithmetic">Arithmetic</a><ul><li><a href="#P31__Determine_whether_a_given_integer_number_is_prime">P31 (**) Determine whether a given integer number is prime.</a><ul></ul></li><li><a href="#P32__Determine_the_greatest_common_divisor_of_two_positive_integer_numbers">P32 (**) Determine the greatest common divisor of two positive integer numbers.</a><ul></ul></li><li><a href="#P33__Determine_whether_two_positive_integer_numbers_are_coprime">P33 (*) Determine whether two positive integer numbers are coprime.</a><ul></ul></li><li><a href="#P34__Calculate_Eulers_totient_function_phim">P34 (**) Calculate Euler's totient function phi(m).</a><ul></ul></li><li><a href="#P35__Determine_the_prime_factors_of_a_given_positive_integer">P35 (**) Determine the prime factors of a given positive integer.</a><ul></ul></li><li><a href="#P36__Determine_the_prime_factors_of_a_given_positive_integer_2">P36 (**) Determine the prime factors of a given positive integer (2).</a><ul></ul></li><li><a href="#P37__Calculate_Eulers_totient_function_phim_improved">P37 (**) Calculate Euler's totient function phi(m) (improved).</a><ul></ul></li><li><a href="#P38__Compare_the_two_methods_of_calculating_Eulers_totient_function">P38 (*) Compare the two methods of calculating Euler's totient function.</a><ul></ul></li><li><a href="#P39__A_list_of_prime_numbers">P39 (*) A list of prime numbers.</a><ul></ul></li><li><a href="#P40__Goldbachs_conjecture">P40 (**) Goldbach's conjecture.</a><ul></ul></li><li><a href="#P41__A_list_of_Goldbach_compositions">P41 (**) A list of Goldbach compositions.</a><ul></ul></li></ul></li><li><a href="#Logic_and_Codes">Logic and Codes</a><ul><li><a href="#P46__Truth_tables_for_logical_expressions">P46 (**) Truth tables for logical expressions.</a><ul></ul></li><li><a href="#P49__Gray_code">P49 (**) Gray code.</a><ul></ul></li><li><a href="#P50__Huffman_code">P50 (***) Huffman code.</a><ul></ul></li><li><a href="#A_More_Complete_Implementation">A More Complete Implementation</a><ul></ul></li></ul></li><li><a href="#Binary_Trees">Binary Trees</a><ul><li><a href="#P54A__Check_whether_a_given_term_represents_a_binary_tree">P54A (*) Check whether a given term represents a binary tree.</a><ul></ul></li><li><a href="#P55__Construct_completely_balanced_binary_trees">P55 (**) Construct completely balanced binary trees.</a><ul></ul></li><li><a href="#P56__Symmetric_binary_trees">P56 (**) Symmetric binary trees.</a><ul></ul></li><li><a href="#P57__Binary_search_trees_dictionaries">P57 (**) Binary search trees (dictionaries).</a><ul></ul></li><li><a href="#P58__Generateandtest_paradigm">P58 (**) Generate-and-test paradigm.</a><ul></ul></li><li><a href="#P59__Construct_heightbalanced_binary_trees">P59 (**) Construct height-balanced binary trees.</a><ul></ul></li><li><a href="#P60__Construct_heightbalanced_binary_trees_with_a_given_number_of_nodes">P60 (**) Construct height-balanced binary trees with a given number of nodes.</a><ul><li><a href="#A_Generative_Solution">A Generative Solution</a><ul><li><a href="#Determine_the_Maximally_Uneven_Weighting_of_Nodes">Determine the Maximally Uneven Weighting of Nodes</a><ul></ul></li><li><a href="#Generating_a_List_of_Possible_Weightings_for_Both_Sides">Generating a List of Possible Weightings for Both Sides</a><ul></ul></li><li><a href="#Generating_all_Trees_for_all_Given_Weightings">Generating all Trees for all Given Weightings</a><ul></ul></li><li><a href="#Filter_out_Duplicates_and_Trees_with_the_Wrong_Height_Difference">Filter out Duplicates and Trees with the Wrong Height Difference</a><ul></ul></li><li><a href="#Final_Result">Final Result</a><ul></ul></li></ul></li><li><a href="#Generating_AVL_Trees">Generating AVL Trees</a><ul></ul></li></ul></li><li><a href="#P61__Count_the_leaves_of_a_binary_tree">P61 (*) Count the leaves of a binary tree.</a><ul></ul></li><li><a href="#P61A__Collect_the_leaves_of_a_binary_tree_in_a_list">P61A (*) Collect the leaves of a binary tree in a list.</a><ul></ul></li><li><a href="#P62__Collect_the_internal_nodes_of_a_binary_tree_in_a_list">P62 (*) Collect the internal nodes of a binary tree in a list.</a><ul></ul></li><li><a href="#P62B__Collect_the_nodes_at_a_given_level_in_a_tree">P62B (*) Collect the nodes at a given level in a tree.</a><ul></ul></li><li><a href="#P63__Construct_a_complete_binary_tree">P63 (*) Construct a complete binary tree.</a><ul></ul></li><li><a href="#P64__Layout_a_binary_tree_1">P64 (**) Layout a binary tree (1).</a><ul></ul></li></ul></li></ul></div>
<h1 id="99_Problems_Klong_Solutions"><a class="hanchor" href="#99_Problems_Klong_Solutions">99 Problems Klong Solutions</a></h1>
<blockquote>
<p>Weil ein Vers dir gelingt in einer gebildeten Sprache,<br/>
Die für dich dichtet und denkt, glaubst du schon Dichter zu sein?</p>
</blockquote>
<p><em>— <a href="https://en.wikipedia.org/wiki/Friedrich_Schiller">Friedrich Schiller</a>, “Votivtafeln” (Die Kunstschätzer), 1804</em></p>
<h2 id="Acknowledgements"><a class="hanchor" href="#Acknowledgements">Acknowledgements</a></h2>
<p>s7 is inspired by a function by
<a href="http://t3x.org/nmh/index.html">nmh</a>, who wrote it <a href="http://t3x.org/klong/klong-ref.txt.html">in the Klong
documentation</a>.
<a href="https://old.reddit.com/user/John_Earnest">/u/John_Earnest</a>
provided a <a href="https://old.reddit.com/r/apljk/comments/59asq0/pack_duplicate_consecutive_elements_into_sublists/">more
elegant</a>
s9 on <a href="https://old.reddit.com/r/apljk/">/r/apljk</a>. Dave
Long provided a much more elegant s8, s26, c1, s49 and
s55 over email. s31 is from the <a href="https://en.wikipedia.org/wiki/K_(programming_language)#Examples">Wikipedia article about
K</a>.</p>
<h2 id="Code"><a class="hanchor" href="#Code">Code</a></h2>
<!--TODO: Make the tests also external-->
<p>The pure Klong code, without tests, explanations, comments or performance
tests is available <a href="./code/99_klong/sol.kg">here</a>. It currently implements
solutions for all problems up to P64 (excluding P47 and P48), in 2428
bytes.</p>
<h2 id="Conventions"><a class="hanchor" href="#Conventions">Conventions</a></h2>
<p>Since this collection of solutions attempts to maximize for terseness,
several concessions concerning completeness have to be made. There
is nearly no checking for correct arguments, except for empty lists.
Variables are declared locally. The solution for problem N is called
<code>sN</code>, helper functions are numbered <code>aN</code> for the Nth helper function in
<a href="./99_klong_problems.html#Working_with_lists"><strong>Working with lists</strong></a>,
<code>bN</code> in <a href="./99_klong_problems.html#Arithmetic"><strong>Arithmetic</strong></a>, <code>cN</code> in
<a href="./99_klong_problems.html#Logic_and_Codes"><strong>Logic and Codes</strong></a> and so on.</p>
<h2 id="Prerequisites"><a class="hanchor" href="#Prerequisites">Prerequisites</a></h2>
<p>The solutions use <code>flr</code> and <code>dp</code> from the util library and <code>sqr</code> and
<code>ln</code> from the math library in the standard library.</p>
<pre><code>.l("util")
.l("math")
</code></pre>
<p>These would be, of course, trivial to implement on your own:
<code>flr::{[f];f::x;y@(f'y)?1}</code>, <code>dp::{:[@x;0;1+|/.f'x]}</code> and
<code>sqr::{[a];a::x;:[0=x;0;{(x+a%x)%2}:~a]}</code> (taken directly from the
library).</p>
<h2 id="Working_with_Lists"><a class="hanchor" href="#Working_with_Lists">Working with Lists</a></h2>
<h3 id="P01__Find_the_last_element_of_a_list"><a class="hanchor" href="#P01__Find_the_last_element_of_a_list">P01 (*) Find the last element of a list.</a></h3>
<p>The function reverses the first argument and then returns the first element.</p>
<pre><code>s1::{*|x}
mylast::s1
</code></pre>
<p>Testing with the example obtains the correct result:</p>
<pre><code> mylast([:a :b :c :d])
:d
</code></pre>
<p>Another possible version would be <code>s1::{x@((#x)-1)}</code>. These can be
compared to each other in respect to their performance (the performance
test repeated 10 times each to avoid advantages from caching):</p>
<pre><code> .l("time")
s1::{*|x}
(+/1_10{x;time({s1(!3000000)})}\*[])%10
0.0842222
s1::{x@((#x)-1)}
(+/1_10{x;time({s1(!3000000)})}\*[])%10
0.1471947
</code></pre>
<p>One can see that the first version of <code>s1</code> is nearly twice as fast
as the second version.</p>
<p>Klong apparently has a very efficient reversing operation for lists.</p>
<h3 id="P02__Find_the_last_but_one_sublist_of_a_list"><a class="hanchor" href="#P02__Find_the_last_but_one_sublist_of_a_list">P02 (*) Find the last but one sublist of a list.</a></h3>
<p>This implementation uses a property of the Take verb that allows
indexing from the end of the list with negative numbers. A longer and
less elegant solution, re-using <code>s1</code>, would be <code>s2::{((|x)@2),s1(x)}</code>.
Alternatively, one could also use direct indexing while reversing the
list: <code>s2::{(|x)@[1 0]}</code>.</p>
<pre><code>s2::{(-2)#x}
mybutlast::s2
</code></pre>
<p>We again take the test from the problems list:</p>
<pre><code> mybutlast([:a :b :c :d])
[:c :d]
</code></pre>
<h3 id="P03__Find_the_Kth_element_of_a_list"><a class="hanchor" href="#P03__Find_the_Kth_element_of_a_list">P03 (*) Find the K'th element of a list.</a></h3>
<p>This one is very straightforward in Klong: indexing is zero-based,
so one subtracts one of the second element and then extracts the value.</p>
<pre><code>s3::{x@y-1}
elementat::s3
</code></pre>
<p>Testing:</p>
<pre><code> elementat([:a :b :c :d :e];3)
:c
</code></pre>
<h3 id="P04__Find_the_number_of_elements_of_a_list"><a class="hanchor" href="#P04__Find_the_number_of_elements_of_a_list">P04 (*) Find the number of elements of a list.</a></h3>
<p>Since <code>#</code> is a Klong primitive for the length of a list, this
problem is trivial.</p>
<pre><code>s4::{#x}
</code></pre>
<h3 id="P05__Reverse_a_list"><a class="hanchor" href="#P05__Reverse_a_list">P05 (*) Reverse a list.</a></h3>
<p>Similar to problem 5, there is a primitive for this.</p>
<pre><code>s5::{|x}
</code></pre>
<h3 id="P06__Find_out_whether_a_list_is_a_palindrome"><a class="hanchor" href="#P06__Find_out_whether_a_list_is_a_palindrome">P06 (*) Find out whether a list is a palindrome.</a></h3>
<p>Since <code>=</code> compares a list element-wise (and returns a list with boolean
values corresponding to the equality of the two lists), we have to use
the <code>~</code> primitive, which compares lists by structure and content. So we
compare <code>x</code> and its reversion that way.</p>
<pre><code>s6::{x~|x}
</code></pre>
<h3 id="P07__Flatten_a_nested_list_structure"><a class="hanchor" href="#P07__Flatten_a_nested_list_structure">P07 (**) Flatten a nested list structure.</a></h3>
<p>This solution is taken from the Klong
<a href="(http://t3x.org/klong/klong-ref.txt.html)">documentation</a>, while fixing
a little problem. The original solution was <code>s7::{,/:~x}</code>, which applied
the concatenation operator to the sublists of a list as long as the
list changes with each operation, and then returned the list. However,
that solution failed with nested lists that contain only one element:
"If “a” is a single-element list, return the single element." (from the
Klong documentation on Over). For flattening a list, that is not right:
<code>s7([1])</code> should be <code>[1]</code>, not <code>1</code>. So this code differentiates between
a list that only contains an atom, and returns that, or executes the original
code otherwise.</p>
<pre><code>s7::{{:[@,/x;x;,/x]}:~x}
myflatten::s7
</code></pre>
<p>Tests:</p>
<pre><code> myflatten([:a [:b [:c :d] :e]])
[:a :b :c :d :e]
myflatten([0])
[0]
</code></pre>
<p>This is also the result in the problems statement.</p>
<p>Testing it with nested empty lists doesn't work:</p>
<pre><code> myflatten([[] [[]] [[][]]])
[[] [] []]
</code></pre>
<!--TODO: Find a solution that doesn't do this.-->
<!--
Idea:
s7::{{:[@,/x;,,/x;,/x]}:~x}
Returns `[[]]` for s7([[] [[]] [[][]]]).
-->
<h3 id="P08__Eliminate_consecutive_duplicates_of_list_elements"><a class="hanchor" href="#P08__Eliminate_consecutive_duplicates_of_list_elements">P08 (**) Eliminate consecutive duplicates of list elements.</a></h3>
<p>This solution first creates a list of <code>1</code> and <code>0</code> that has <code>1</code> at at
positions where in <code>x</code> the element is followed by an value different
from itself. Because one has one element too much in the list (<code>[]</code> has
the positions <code>[1]</code>), we only take as many elements as we need off the
beginning of the resulting positions list (in these cases, it's <code>#x</code>,
the length of the argument list).
We then use Expand/Where to find the positions of 1 in the list of
positions, and extract them with At/Index.</p>
<pre><code>s8::{x@&(#x)#~0,~:'x}
compress::s8
</code></pre>
<p>Compressing the example list returns the desired result:</p>
<pre><code> compress([:a :a :a :a :b :c :c :a :a :d :e :e :e :e])
[:a :b :c :a :d :e]
</code></pre>
<p>And compressing the empty list (and a 1-element list) works as well:</p>
<pre><code> compress([])
[]
compress([1])
[1]
</code></pre>
<h3 id="P09__Pack_consecutive_duplicates_of_list_elements_into_sublists"><a class="hanchor" href="#P09__Pack_consecutive_duplicates_of_list_elements_into_sublists">P09 (**) Pack consecutive duplicates of list elements into sublists.</a></h3>
<p>Here, we first do the same matching between the elements as in P08,
but then we reverse the results and append 0 at the start. In that
way, we can use Expand/Where to obtain the positions of <code>1</code> in the list
(that's where the element in the list changes). We then can use Cut to
cut out sublists ending before the given positions. Because <code>~~:'[]</code>
returns not <code>[]</code>, but the number <code>1</code> (for whatever reason), we have
to build in a special case for the empty list at the beginning.</p>
<pre><code>s9::{:[x~[];[];(&0,~~:'x):_x]}
pack::s9
</code></pre>
<p>Since the problems don't specify how we should deal with empty
lists (whether one should return <code>[]</code> or <code>[[]]</code>), we could consider
<code>s9::{(&0,~'~:'x):_x}</code>, which returns the latter. But this clashes with
<code>s10</code>, where <code>s10([])</code> returns <code>[[0]]</code>, which doesn't seem to be correct
at all.</p>
<p>Testing it:</p>
<pre><code> pack([:a :a :a :a :b :c :c :a :a :d :e :e :e :e])
[[:a :a :a :a] [:b] [:c :c] [:a :a] [:d] [:e :e :e :e]]
</code></pre>
<h3 id="P10__Runlength_encoding_of_a_list"><a class="hanchor" href="#P10__Runlength_encoding_of_a_list">P10 (*) Run-length encoding of a list.</a></h3>
<p>As the problem statement suggests, this solution is pretty
straightforward. For every sublist of the result of <code>s9</code>, we append
its length to its first element.</p>
<pre><code>s10::{{(#x),*x}'s9(x)}
encode::s10
</code></pre>
<p>Tests:</p>
<pre><code> encode([:a :a :a :a :b :c :c :a :a :d :e :e :e :e])
[[4 :a] [1 :b] [2 :c] [2 :a] [1 :d] [4 :e]]
</code></pre>
<h3 id="P11__Modified_runlength_encoding"><a class="hanchor" href="#P11__Modified_runlength_encoding">P11 (*) Modified run-length encoding.</a></h3>
<p>Again, this is quite easy. For the result of <code>s10</code>, we test whether the
length of the sublist is 1, and if it is, then we return just the value,
otherwise we return the list.</p>
<pre><code>s11::{{:[1=*x;*|x;x]}'s10(x)}
encodemodified::s11
</code></pre>
<p>Testing:</p>
<pre><code> encodemodified([:a :a :a :a :b :c :c :a :a :d :e :e :e :e])
[[4 :a] :b [2 :c] [2 :a] :d [4 :e]]
</code></pre>
<p>This works fine. However, <code>encodemodified</code> shows weird behavior with lists with one element:</p>
<pre><code> encodemodified([0])
[0 [0]]
encodemodified([1])
[1]
</code></pre>
<!--TODO: Fix this.-->
<p>It works fine with <code>[]</code>, though:</p>
<pre><code> encodemodified([])
[]
</code></pre>
<h3 id="P12__Decode_a_runlength_encoded_list"><a class="hanchor" href="#P12__Decode_a_runlength_encoded_list">P12 (**) Decode a run-length encoded list.</a></h3>
<p>Here, we simply execute a function over the list: If the list element
is an atom (it is itself not a list), we simply return it, otherwise
we use Reshape to repeat the last element of <code>x</code> (<code>x</code> has the form
<code>[freq val]</code>) <code>freq</code> times. The result is then flattened by appending
the list elements to each other.</p>
<pre><code>s12::{,/{:[@x;x;(*x):^x@1]}'x}
</code></pre>
<h3 id="P13__Runlength_encoding_of_a_list_direct_solution"><a class="hanchor" href="#P13__Runlength_encoding_of_a_list_direct_solution">P13 (**) Run-length encoding of a list (direct solution).</a></h3>
<p>The difference between 'creating sublists' and 'indexing them' is
not very big in Klong, but a reasonable attempt is presented here.
We start like in P09: First, we check whether our function argument
is the empty list, in case of which we return immediately with the
empty list. Otherwise we store the outer function argument <code>x</code> in
the local variable <code>a</code>. Then we proceed by again executing Match
between the elements of the list, and append <code>1</code> at the beginning
to indicate that we want to include the first sublist. This results
in a list containing the starting positions of the sublists with different
elements. We pass this list pairwise to a function, where we first
check whether the difference is <code>1</code>. In this case, the sublist has
length <code>1</code> as well and can be returned as an atom, otherwise we
return the length of the sequence concatenated with its first element.</p>
<pre><code>s13::{[a];a::x;:[x~[];[];{:[1=y-x;a@x;(y-x),a@x]}:'&1,~~:'x]}
encodedirect::s13
</code></pre>
<p>Testing this function should return the same result as <code>s11</code>:</p>
<pre><code> encodedirect([:a :a :a :a :b :c :c :a :a :d :e :e :e :e])
[[4 :a] :b [2 :c] [2 :a] :d]
</code></pre>
<p>Which it does.</p>
<p>One can now compare the speed of the direct solution with the speed of
the indirect solution:</p>
<pre><code> .l("time")
s9::{:[x~[];[];(&0,~~:'x):_x]}
s10::{{(#x),*x}'s9(x)}
s11::{{:[1=*x;*|x;x]}'s10(x)}
time({s11(!10000)})
0.010219
s13::{[a];a::x;:[x~[];[];{:[1=y-x;a@x;(y-x),a@x]}:'&1,~~:'x]}
time({s13(!10000)})
1.884073
</code></pre>
<p>As one can see, the more complex solution <code>s13</code> is much slower than the
more idiomatic <code>s11</code>.</p>
<!--TODO: Explore further why `s13` is so much slower.-->
<h3 id="P14__Duplicate_the_elements_of_a_list"><a class="hanchor" href="#P14__Duplicate_the_elements_of_a_list">P14 (*) Duplicate the elements of a list.</a></h3>
<p>This solution is a specialization of the solution to P15. We take the function
<code>2:^x</code> (repeat x 2 times, abusing Reshape) and call Each-Left on the first
function argument with it. Because the result is a list of lists, we then have
to flatten the list using the well known <code>,/</code> pattern.</p>
<pre><code>s14::{,/2:^:\x}
dupli::s14
</code></pre>
<p>There are two alternative, but longer solutions: <code>s14::{,/{x,x}'x}</code>
is more naïve, and <code>s14::{x@_0.5*!2*#x}</code> is perhaps slightly more
amusing.</p>
<p>The test runs through, as expected:</p>
<pre><code> dupli([:a :b :c :c :d])
[:a :a :b :b :c :c :c :c :d :d]
</code></pre>
<p>We're now interested in the performance of these functions, so we time
calling the different versions with <code>10000</code> elements:</p>
<pre><code> .l("time")
s14::{,/2:^:\x}
time({s14(!10000)})
0.666863
s14::{,/{x,x}'x}
time({s14(!10000)})
0.64103
s14::{x@_0.5*!2*#x}
time({s14(!10000)})
0.022282
</code></pre>
<p>As one can see, the indexing-based solution is by far the fastest,
with little difference between the other two.</p>
<h3 id="P15__Replicate_the_elements_of_a_list_a_given_number_of_times"><a class="hanchor" href="#P15__Replicate_the_elements_of_a_list_a_given_number_of_times">P15 (**) Replicate the elements of a list a given number of times.</a></h3>
<p>Here we have the more general case of P14. We simply have to replace <code>2</code>
by the second argument <code>y</code> here: Repeat <code>x</code> <code>y</code> times for every <code>x</code> in
the first argument, then concatenate the result.</p>
<pre><code>s15::{,/y:^:\x}
repli::s15
</code></pre>
<p>Test:</p>
<pre><code> repli([:a :b :c];3)
[:a :a :a :b :b :b :c :c :c]
</code></pre>
<h3 id="P16__Drop_every_Nth_element_from_a_list"><a class="hanchor" href="#P16__Drop_every_Nth_element_from_a_list">P16 (**) Drop every N'th element from a list.</a></h3>
<p>The example given indicates that the indexing is 1-based. The Drop verb
doesn't work with two lists (although that would make a nice addition
to the language), so we have to find a simpler solution. <code>s16</code> works
by creating a list with all indices to <code>x</code> (<code>!#x</code>) and then executing
the modulo of <code>y</code> on it. The result is a list in the form of <code>[0 1 2 3 … (y-1) 0 1 2 3 …]</code>.
The elements we want to avoid are at the positions where the list
contains <code>y-1</code>, so we create a list where <code>1</code> is at the positions
where the original list had elements smaller than <code>y-1</code>. We then use
<code>&</code> to obtain the positions of the value <code>1</code> and then simply index <code>x</code>
by those positions.</p>
<pre><code>s16::{x@&(y-1)>(!#x)!y}
drop::s16
</code></pre>
<p>We test the implementation:</p>
<pre><code> drop([:a :b :c :d :e :f :g :h :i :k];3)
[:a :b :d :e :g :h :k]
drop([:a :b :c];1)
[]
drop([];1)
kg: error: rem: type error: [[] 1]
</code></pre>
<p>So our solution fails for empty lists. We could modify it to
include a simple conditional statement to return the empty list
if <code>x</code> is <code>[]</code>: <code>s16::{:[x~[];[];x@&(y-1)>(!#x)!y]}</code>.</p>
<!--TODO: Think about including this into the full text.-->
<h3 id="P17__Split_a_list_into_two_parts_the_length_of_the_first_part_is_given"><a class="hanchor" href="#P17__Split_a_list_into_two_parts_the_length_of_the_first_part_is_given">P17: (*) Split a list into two parts, the length of the first part is given.</a></h3>
<p>For this problem, Split is the fitting verb. It can receive a list of
lengths, and is quite lenient with lists that don't fit exactly. So we
concatenate <code>y</code> with the total length of <code>x</code> and then just split <code>x</code>
by that.</p>
<pre><code>s17::{(y,#x):#x}
split::s17
</code></pre>
<p>An alternative solution could be <code>s17::{(,y#x),,y_x}</code>, in which one
concatenates taking <code>y</code> elements of <code>x</code> with dropping <code>y</code> elements of <code>x</code>.</p>
<p>Executing the test returns the correct result:</p>
<pre><code> split([:a :b :c :d :e :f :g :h :i :k]; 3)
[[:a :b :c] [:d :e :f :g :h :i :k]]
</code></pre>
<p>The Split verb doesn't work with a range of <code>0</code>:</p>
<pre><code> split([1 2 3];0)
kg: error: split: range error: 0
</code></pre>
<h3 id="P18__Extract_a_slice_from_a_list"><a class="hanchor" href="#P18__Extract_a_slice_from_a_list">P18: (**) Extract a slice from a list.</a></h3>
<p>Here, we can simply take the first <code>z</code> elements from the start of
the list, and then drop <code>y-1</code> elements of that list (we have to subtract
<code>1</code> because indexing in lists is <code>0</code>-based).</p>
<pre><code>s18::{(y-1)_z#x}
slice::s18
</code></pre>
<p>The test runs through, as expected:</p>
<pre><code> slice([:a :b :c :d :e :f :g :h :i :k];3;7)
[:c :d :e :f :g]
</code></pre>
<p>However, passing arguments that are not long enough gives some
interesting results:</p>
<pre><code> slice([:a];3;7)
[:a :a :a :a :a]
</code></pre>
<p>This happens because if Take doesn't find enough elements, it simply
repeats the elements it finds.</p>
<p>An alternative solution, using Index over a range, is
<code>s18::{x@(y-1)+!1+z-y}</code>.</p>
<h3 id="P19__Rotate_a_list_N_places_to_the_left"><a class="hanchor" href="#P19__Rotate_a_list_N_places_to_the_left">P19: (**) Rotate a list N places to the left.</a></h3>
<p>Klong has a verb for that™. By default, <code>:+</code> rotates to the right with
positive, and to the left with negative integers, so we have to reverse
the sign of <code>y</code>.</p>
<pre><code>s19::{(-y):+x}
rotate::s19
</code></pre>
<p>Tests:</p>
<pre><code> rotate([:a :b :c :d :e :f :g :h];3)
[:d :e :f :g :h :a :b :c]
rotate([:a :b :c :d :e :f :g :h];-2)
[:g :h :a :b :c :d :e :f]
</code></pre>
<h3 id="P20__Remove_the_Kth_element_from_a_list"><a class="hanchor" href="#P20__Remove_the_Kth_element_from_a_list">P20: (*) Remove the K'th element from a list.</a></h3>
<p>It's quite possible that there is a short and elegant solution with 3
combined adverbs, but this solution does the obvious: it concatenates
the first <code>y-1</code> elements of <code>x</code> with the last elements of <code>x</code> that don't
contain the <code>y</code>th element.</p>
<pre><code>s20::{((y-1)#x),y_x}
removeat::s20
</code></pre>
<p>Tests:</p>
<pre><code> removeat([:a :b :c :d];2)
[:a :c :d]
removeat([];1)
[]
</code></pre>
<p>Alternative solutions could use Expand over a list of booleans
<code>s20::{x@&~(y-1)=!#x}</code> or double rotation <code>s20::{(-y-2):+1_(y-1):+x}</code></p>
<h3 id="P21__Insert_an_element_at_a_given_position_into_a_list"><a class="hanchor" href="#P21__Insert_an_element_at_a_given_position_into_a_list">P21: (*) Insert an element at a given position into a list.</a></h3>
<p>Here, one can use a naïve solution takes the first <code>z-1</code> elements from
the list, concatenates them with <code>x</code>, and then concatenates the result
with the rest of <code>y</code>.</p>
<pre><code>s21::{((z-1)#y),x,(z-1)_y}
insertat::s21
</code></pre>
<p>The given test passes successfully:</p>
<pre><code> s21(:alfa;[:a :b :c :d];2)
[:a :alfa :b :c :d]
</code></pre>
<p>Other solutions are possible, for example a hack using the Amend verb with
lists and then flattening the result <code>s21::{,/y:=(,x,y@z-1),z-1}</code> or re-using
solution 17 to obtain the sublists <code>s21::{[r];r::s17(y;z-1);(*r),x,r@1}</code>.</p>
<p>Timing the different solutions returns unsurprising results:</p>
<pre><code> s21::{((z-1)#y),x,(z-1)_y}
(+/1_100{x;time({s21(1;!100000;50000)})}\*[])%100
0.00247086
s21::{,/y:=(,x,y@z-1),z-1}
time({s21(1;!100000;50000)})
31.133766
s17::{(y,#x):#x}
s21::{[r];r::s17(y;z-1);(*r),x,r@1}
(+/1_100{x;time({s21(1;!100000;50000)})}\*[])%100
0.00285916
</code></pre>
<p>The Amend solution is much slower, mainly because of the flattening at
the end. The solution re-using <code>s17</code> is a bit slower, maybe because
of storing the result in a local variable or because Cut is a more
expensive operation.</p>
<h3 id="P22__Create_a_list_containing_all_integers_within_a_given_range"><a class="hanchor" href="#P22__Create_a_list_containing_all_integers_within_a_given_range">P22: (*) Create a list containing all integers within a given range.</a></h3>
<p>This one is quite simple, although a bit clunky. We simply create a
list of integers from 0 to <code>y-(x-1)</code> (in Klong, because of right-to-left
operator evaluation, simply <code>y-x-1</code>), and add x to that.</p>
<pre><code>s22::{x+!y-x-1}
range::s22
</code></pre>
<p>Tests run through like a breeze:</p>
<pre><code> range(4;9)
[4 5 6 7 8 9]
</code></pre>
<h3 id="P23__Extract_a_given_number_of_randomly_selected_elements_from_a_list"><a class="hanchor" href="#P23__Extract_a_given_number_of_randomly_selected_elements_from_a_list">P23 (**) Extract a given number of randomly selected elements from a list.</a></h3>
<p>We don't use solution 20 because we don't have to. Instead, we wrap the
function into an Iterate verb that gets executed <code>(#x)-y</code> times, and
each of these iterations we drop one element of the list that has been
rotated a random number of positions in the range <code>0</code>..<code>#x</code>. That way
we remove the right number of elements and return a list of the size <code>y</code>.</p>
<pre><code>s23::{((#x)-y){1_(_.rn()*#x):+x}:*x}
rndselect::s23
</code></pre>
<p>Tests are a bit different here, because we obtain a random result. But
we can check if it does the approximately right thing:</p>
<pre><code> rndselect([:a :b :c :d :e :f :g :h];3)
[:b :d :f]
rndselect([:a :b :c :d :e :f :g :h];1)
[:h]
rndselect([:a :b :c :d :e :f :g :h];0)
[]
</code></pre>
<h3 id="P24__Lotto_Draw_N_different_random_numbers_from_the_set_1M"><a class="hanchor" href="#P24__Lotto_Draw_N_different_random_numbers_from_the_set_1M">P24 (*) Lotto: Draw N different random numbers from the set 1..M.</a></h3>
<p>The solution to this is pretty simple. With <code>s23</code>, we already have a
function to draw N elements from a list, so we only have to create the
set 1..M, or, in Klong-speak, <code>1+!M</code> (where M is the second argument
<code>y</code> to the function).</p>
<pre><code>s24::{s23(1+!y;x)}
lottoselect::s24
</code></pre>
<p>Testing:</p>
<pre><code> lottoselect(6;49)
[6 11 12 13 35 37]
lottoselect(1;49)
[13]
lottoselect(0;49)
[]
lottoselect(10;10)
[1 2 3 4 5 6 7 8 9 10]
</code></pre>
<p>Using <code>s22</code> here would be wasteful, since that would use up more bytes
than simply typing <code>1+!y</code>: <code>s24::{s23(s22(1;1+y);x)}</code>. We don't need
the given hint.</p>
<h3 id="P25__Generate_a_random_permutation_of_the_elements_of_a_list"><a class="hanchor" href="#P25__Generate_a_random_permutation_of_the_elements_of_a_list">P25 (*) Generate a random permutation of the elements of a list.</a></h3>
<p>A quite nice solution is the following: First, one creates a list of
random numbers that has the same length as the first argument using the
Iterate adverb. Then, one uses Grade-Down (or Grade-Up, in this case
synonymous) to create a list of random indices, and uses Index/At to
pick the elements in this random order from <code>x</code>.</p>
<pre><code>s25::{x@<(#x){x,.rn()}:*[]}
rndpermu::s25
</code></pre>
<p>Tests:</p>
<pre><code> rndpermu([:a :b :c :d :e :f])
[:d :c :b :a :e :f]
rndpermu([])
[]
rndpermu([:a])
[:a]
</code></pre>
<p>It is probably slower than a more naïve
<a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Fischer-Yates shuffle</a>
like equivalent <code>s25::{(#x){p::_.rn()*#x;(x@p),s20(x;p+1)}:*x}</code>, since
Grade-Up <code><</code> sorts the list, which results in a <code>$\cal{O}(n \cdot log(n))$</code> time
complexity, while Fischer-Yates is just <code>$\cal{O}(n)$</code>.</p>
<p>One can then measure the runtimes of these two functions and generate
a graph of the runtimes using Klong's nplot and time libraries:</p>
<pre><code>.l("nplot")
.l("time")
s25.1::{x@<(#x){x,.rn()}:*[]}
s20::{((y-1)#x),y_x}
s25.2::{(#x){p::_.rn()*#x;(x@p),s20(x;p+1)}:*x}
rt1::{[a];a::x;time({s25.1(!a)})}'1000+500*!19
rt2::{[a];a::x;time({s25.2(!a)})}'1000+500*!19
:"frame with the maximum value"
frame([0 10000 1000]; [0],(1+_|/rt1,rt2),[0.5])
ytitle("runtime in seconds")
segplot(rt1)
text(250;60;"Grading Shuffle")
setrgb(0;0;1)
segplot(rt2)
text(200;250;"Fisher-Yates Shuffle")
draw()
</code></pre>
<p>The output of this is in <a href="https://en.wikipedia.org/wiki/Encapsulated_PostScript">Encapsulated
PostScript</a>
and now has to be converted into
<a href="https://en.wikipedia.org/wiki/Portable_Network_Graphics">PNG</a> using
<a href="https://imagemagick.org/index.php">ImageMagick</a>:</p>
<pre><code>kg -l ./p25plot.kg -e '[]' >runtimes25.eps
convert -size 750x750 runtimes25.eps runtimes25.png
</code></pre>
<p><img alt="Runtimes for the solutions to problem 3" src="./img/99_klong/runtimes25.png" title="Runtimes for the solutions to problem 3. Fisher-Yates shuffle is alot slower than the shorter Grading shuffle (Fisher-Yates takes 3 seconds for 9k elements, Grading shuffle only 0.6 seconds), and also grows quicker."/></p>
<p>The Fisher-Yates shuffle implementation seems to grow with <code>$\cal{O}(n^2)$</code>,
but the growth behavior of the Grading Shuffle is not entirely
clear. Nonetheless, it seems like the grading shuffle is clearly superior
to the Fisher-Yates Shuffle implementation in terms of performance.
There is probably a Klong verb that runs in <code>$\cal{O}(n^2)$</code> and was used in
<code>s20</code> or <code>s25.2</code>.</p>
<!--TODO: this shuffle might (very rarely) contain duplicates-->
<h3 id="P26__Generate_the_combinations_of_K_distinct_objects_chosen_from_the_N_elements_of_a_list"><a class="hanchor" href="#P26__Generate_the_combinations_of_K_distinct_objects_chosen_from_the_N_elements_of_a_list">P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.</a></h3>
<p>This solution is a <em>bit</em> more complicated than the previous ones. It
takes a recursive approach, with the base case being <code>1</code>, returning a
list that contains all elements in the original list as sublists: <code>,'y</code>.
Each recursive step first creates all suffixes of the list, then calls
<code>s26</code> with the tail of that suffix and appends the first element to each
of the results.</p>
<p>If the suffixes were not created, calling the function would result in
duplicates: <code>s26([:a :b];2)</code> would return <code>[[:a :b][:b :a]]</code>.</p>
<p>The suffixes are created with the expression <code>{x}{1_x}\</code><code>y</code>, using the
While adverb and exploiting the fact that <code>[]</code> is equivalent to <code>0</code>
(false) in Klong. This expression can be expressed as "While x is not
the empty list, drop one element of the front of list, and return all
intermediary results".</p>
<p>The appending uses the Append verb with the Each-Left adverb, appending
the first element of the list to all sublists.</p>
<p>In the end, the result needs to be flattened with <code>,/</code>, because the
elements are themselves put in sublists and empty lists are left in
the result.</p>
<pre><code>s26::{[k];k::x;:[1=k;,'y;,/{(1#x),:\s26(k-1;1_x)}'{x}{1_x}\~y]}
combination::s26
</code></pre>
<p>Testing:</p>
<pre><code> combination(3;[:a :b :c :d :e :f])
[[:a :b :c] [:a :b :d] [:a :b :e] ...]
combination(3;[])
[]
combination(0;[:a :b])
[]
combination(3;[:a :b])
[]
</code></pre>
<h3 id="P27__Group_the_elements_of_a_set_into_disjoint_subsets"><a class="hanchor" href="#P27__Group_the_elements_of_a_set_into_disjoint_subsets">P27 (**) Group the elements of a set into disjoint subsets.</a></h3>
<p>Fortunately, given <code>s26</code>, both <code>group3</code> and <code>s27</code> are quite easy to
implement. <code>group3</code> First generates all subsets of <code>x</code> containing 2
members, and then passes them on to another function. This function
creates the set difference <code>a1</code> of the argument and the set passed
(for example, when <code>x</code> is for the local function is <code>[:a :b]</code>, and <code>a</code>
is <code>[:a :b :c :d]</code>, then <code>a1(a;x)</code> is of course <code>[:c :d]</code>). Of this,
all subsets with length 3 are generated with <code>s26</code>, and the result is
concatenated with the sets from the first call of <code>s26</code>. The results
are then passed, and the same procedure is repeated for subsets of size 4.</p>
<p><code>a1</code> is not a very efficient implementation of set difference (it seems
to have a quadratic run-time of <code>$\cal{O}(n \cdot m)$</code>). But it is short and easy to
implement: it filters out all elements out of <code>x</code> that can be found in
<code>y</code>. The quadratic run-time can thus be explained easily: For each
element in x; that element has to be searched in <code>y</code>, resulting in
<a href="https://en.wikipedia.org/wiki/Big_O_notation#Product">a runtime</a> of
<code>$\cal{O}(n) \cdot \cal{O}(m)=\cal{O}(n \cdot m)$</code>, where <code>$n$</code> is the size of <code>x</code> and <code>$m$</code> is the
size of <code>y</code>.</p>
<p><code>s27</code> is basically a recursive version of <code>group3</code>, producing just the
result of <code>s26</code> for the base case and applying the same set-difference
call of <code>s26</code> as in <code>group3</code>.
It does not check whether the length of <code>x</code> corresponds to the size specified
by <code>+/y</code>, although that would be trivial to implement.</p>
<pre><code>a1::{[b];b::y;flr({[]~b?x};x)}
group3::{[a];a::x;*'{x,:\,'s26(4;a1(a;,/x))}',/{(,x),:\,'s26(3;a1(a;x))}'s26(2;x)}
s27::{[a b];a::x;b::y;:[1=#y;,'s26(*y;x);,/{x,:\,'s26(*b;a1(a;,/x))}'.f(x;1_y)]}
group::s27
</code></pre>
<p>The tests given in the specification have gigantic results, but small samples confirm
the correct behavior of <code>group3</code>:</p>
<pre><code> group3([:aldo :beat :carla :david :evi :flip :gary :hugo :ida])@[0 1 2 3]
[[[:aldo :beat] [:carla :david :evi] [:flip :gary :hugo :ida]]
[[:aldo :beat] [:carla :david :flip] [:evi :gary :hugo :ida]]
[[:aldo :beat] [:carla :david :gary] [:evi :flip :hugo :ida]]
[[:aldo :beat] [:carla :david :hugo] [:evi :flip :gary :ida]]]
</code></pre>
<p>Similarly, this also works for <code>s27</code>:</p>
<pre><code> s27([:aldo :beat :carla :david :evi :flip :gary :hugo :ida];[2 3 4])@[0 1 2 3]
[[[:aldo :beat :carla :david] [:evi :flip :gary] [:hugo :ida]]
[[:aldo :beat :carla :david] [:evi :flip :hugo] [:gary :ida]]
[[:aldo :beat :carla :david] [:evi :flip :ida] [:gary :hugo]]
[[:aldo :beat :carla :david] [:evi :gary :hugo] [:flip :ida]]]
s27([:a :b :c];[1 2])
[[[:a :b] [:c]] [[:a :c] [:b]] [[:b :c] [:a]]]
s27([:a :b :c :d];[2 2])
[[[:a :b] [:c :d]] [[:a :c] [:b :d]] [[:a :d] [:b :c]]
[[:b :c] [:a :d]] [[:b :d] [:a :c]] [[:c :d] [:a :b]]]
s27([:a];[1])
[[[:a]]]
</code></pre>
<p>Empty lists don't work</p>
<pre><code> s27([];[])
kg: error: interrupted
</code></pre>
<p>But set sizes that don't sum to the length of the original list still work:</p>
<pre><code> s27([:a :b :c :d];[1 2])
[[[:a :b] [:c]] [[:a :b] [:d]] [[:a :c] [:b]]
[[:a :c] [:d]] [[:a :d] [:b]] [[:a :d] [:c]]
[[:b :c] [:a]] [[:b :c] [:d]] [[:b :d] [:a]]
[[:b :d] [:c]] [[:c :d] [:a]] [[:c :d] [:b]]]
</code></pre>
<h3 id="P28__Sorting_a_list_of_lists_according_to_length_of_sublists"><a class="hanchor" href="#P28__Sorting_a_list_of_lists_according_to_length_of_sublists">P28 (**) Sorting a list of lists according to length of sublists</a></h3>
<p>a) Sorting a list after the length of its sublists is nearly trivial in
Klong. Create a list with the lengths of the sublists, then grade that
list and select the indexes from the original argument.</p>
<pre><code>s28a::{x@<#'x}
lsort::s28a
</code></pre>
<p>Tests:</p>
<pre><code> lsort([[:a :b :c] [:d :e] [:f :g :h] [:d :e] [:i :j :k :l] [:m :n] [:o]])
[[:o] [:d :e] [:m :n] [:d :e] [:a :b :c] [:f :g :h] [:i :j :k :l]
lsort([])
[]
lsort([:a])
kg: error: size: type error: [:a]
</code></pre>
<p>It is not stable, though:</p>
<pre><code> lsort([[:a][:b]])
[[:b] [:a]]
</code></pre>
<p>b) In this exercise, the solution is supposed to sort the sublists of a
list according to the frequency of length of the list. So if there are
5 lists with length 2, and one list with length 7, the five lists with
length 2 come first, and then the list with length 7.</p>
<p>I haven't found a very elegant and beautiful solution for this, but the
obvious answer is quite straightforward and direct: First, one obtains the
lengths of the sublists and groups (so that the indices of lists with the
same length are put into sublists. This is assigned to the variable <code>f</code>.
We then sort this list after the length of its sublists so that we simply
repeat the implementation of s28a (which takes more bytes to be called
than to be implemented in-line). Finally, <code>x</code> is indexed with the flattened
version of these indices.</p>
<pre><code>s28b::{[f];f::=#'x;x@,/f@<#'f}
lfsort::s28b
</code></pre>
<p>Tests:</p>
<pre><code> lfsort([[:a :b :c] [:d :e] [:f :g :h] [:d :e] [:i :j :k :l] [:m :n] [:o]])
[[:o] [:i :j :k :l] [:a :b :c] [:f :g :h] [:d :e] [:d :e] [:m :n]]
lfsort([])
[]
lfsort([[:a]])
[[:a]]
</code></pre>
<p>One can see that <code>lfsort</code> returns the correct result, but is not stable:
<code>[:o]</code> occurred after <code>[:i :j :k :l]</code> in the original list, but is before
it in the returned value.</p>
<h2 id="Arithmetic"><a class="hanchor" href="#Arithmetic">Arithmetic</a></h2>
<h3 id="P31__Determine_whether_a_given_integer_number_is_prime"><a class="hanchor" href="#P31__Determine_whether_a_given_integer_number_is_prime">P31 (**) Determine whether a given integer number is prime.</a></h3>
<p>In the implementation of a primality test, there generally is a great trade-off
between conciseness and performance. This seems only partially applicable in Klong.</p>
<p>Here, I compare four different primality tests written in Klong. The
first three were written by me, and the fourth is a slightly adapted
version from the Klong standard math library. The fifth one is <a href="https://en.wikipedia.org/wiki/K_(programming_language)#Examples">from
wikipedia</a>,
and the sixth is an adaption of the wikipedia version.</p>
<p><code>s31.1</code> is the simplest and therefore the shortest of these four
implementations: it simply checks whether a number is divisible by any
of the numbers smaller than itself, and if that is the case, it returns
0, otherwise 1. It needs a special case for the number 2, but otherwise,
it is quite boring.</p>
<pre><code>s31.1::{:[x<2;0:|x=2;1;[]~(x!2+!x-2)?0]}
</code></pre>
<p><code>s31.2</code> basically does the same thing, but tests less numbers: Only odd
numbers less than the square root of the argument (with special cases
for 2, 3 and 5). Because of this, it should run a lot faster (and as one
will see, it does!).</p>
<pre><code>s31.2::{:[x<2;0:|[2 3 5]?x;1;&/(x!2,3+2*!_sqr(x)%2)]}
</code></pre>
<p>One perhaps a naïve primality check is not optimal, and using a
sieve is a lot faster. These two function implement the <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">sieve of
Eratosthenes</a> :
checking whether the current number divides all smaller prime numbers
until the biggest known prime number is either bigger than the argument
or equal to it.</p>
<pre><code>s31.3::{[a v];a::x;v::1;x=*{a>*x}{v::v+2;:[[]~(v!x)?0;v,x;x]}:~[2]}
s31.4::{[n p];n::x;p::[2];{~x>n}{:[&/x!p;p::p,x;0];x+2}:~3;:[x<2;0;x=*|p]}
</code></pre>
<p><code>s31.5</code> is especially beautiful: It generate all numbers smaller than x (save 0 and 1);
and makes a division test using the Each-Right adverb (x Modulo Each-Right every number
smaller than x). The resulting list of booleans is then searched for a 1 using Min/And:</p>
<pre><code>s31.5::{:[x<2;0:|x=2;1;&/x!:\2_!x]}
</code></pre>
<p><code>s31.6</code> is basically the same principle, but the list of values generated to be checked
is shorter (through omission of even numbers and numbers greater than the square root
of x).</p>
<pre><code>s31.6::{:[x<2;0:|x>3;&/x!:\2,3+2*!_sqr(x)%2;1]}
</code></pre>
<p>Even quick performance tests reveal massive differences between these
four functions (the result always is the average runtime in seconds):</p>
<p>Testing <code>s31.1</code> with 100 random values >100k:</p>
<pre><code> .l("time")
s31.1::{:[[0 1]?x;0:|x=2;1;[]~(x!2+!x-2)?0]}
(+/1_100{x;time({s31.1(100000+_100*.rn())})}\*[])%100
0.08203387
</code></pre>
<p>Testing <code>s31.2</code> with 100 random values >1G:</p>
<pre><code> .l("time")
s31.2::{:[[0 1]?x;0:|[2 3 5]?x;1;&/(x!2,3+2*!_sqr(x)%2)]}
(+/1_100{x;time({s31.2(1000000000+_100*.rn())})}\*[])%100
0.05924128
</code></pre>
<p>Testing <code>s31.3</code> with 100 random values >10k:</p>
<pre><code> .l("time")
s31.3::{[a v];a::x;v::1;x=*{a>*x}{v::v+2;:[[]~(v!x)?0;v,x;x]}:~[2]}
(+/1_100{x;time({s31.3(10000+_100*.rn())})}\*[])%100
2.87354341
</code></pre>
<p>Testing <code>s31.4</code> with 100 random values >10k:</p>
<pre><code> .l("time")
s31.4::{[n p];n::x;p::[2];{~x>n}{:[&/x!p;p::p,x;0];x+2}:~3;:[x<2;0;x=*|p]}
(+/1_100{x;time({s31.4(10000+_100*.rn())})}\*[])%100
5.4216601
</code></pre>
<p>Testing <code>s31.5</code> with 100 random values >100k:</p>
<pre><code> .l("time")
s31.5::{:[x<2;0:|x=2;1;&/x!:\2_!x]}
(+/1_100{x;time({s31.5(100000+_100*.rn())})}\*[])%100
0.28281745
</code></pre>
<p>Testing <code>s31.6</code> with 100 values >1G:</p>
<pre><code> .l("time")
s31.6::{:[x<2;0:|x>3;&/x!:\2,3+2*!_sqr(x)%2;1]}
(+/1_100{x;time({s31.6(1000000000+_100*.rn())})}\*[])%100
0.07785973
</code></pre>
<p>One can already see that the primality checks implementing sieves are
orders of magnitude slower than the simple and boring divisor-checking
primality tests. One can also see that together with <code>s31.6</code>, <code>s31.2</code>
is by far the fastest of these three implementations (probably due to
the omission of even divisors).</p>
<p>One can now check the performance of the first two functions to find
out about their runtime behavior (notice that both have similar growth
behavior at 100k and 10b, respectively).</p>
<p>Measuring runtimes of <code>s31.1</code> and generating the graph:</p>
<pre><code>.l("nplot")
.l("time")
s31.1::{:[[0 1]?x;0:|x=2;1;[]~(x!2+!x-2)?0]}
rt::{[a];a::x;time({s31.1(a+_100*.rn())})}'100000+50000*!19
frame([0 1000000 100000]; [0],(1+_|/rt),[0.5])
ytitle("runtime in seconds")
segplot(rt)
text(300;300;"s31.1")
draw()
</code></pre>
<p><img alt="Runtimes of s31.1" src="./img/99_klong/runtimes31_1.png" title="Runtimes of s31.1. The runtime grows linearly, with spikes in the runtime around the values 300k, 500k and 700k."/></p>
<p>Measuring runtimes of <code>s31.2</code> and generating the graph:</p>
<pre><code>.l("nplot")
s31.2::{:[[0 1]?x;0:|[2 3 5]?x;1;&/(x!2,3+2*!_sqr(x)%2)]}
rt::{[a];a::x;time({s31.2(a+_100*.rn())})}'10000000000+5000000000*!19
frame([0 100000000000 10000000000]; [0],(1+_|/rt),[0.5])
ytitle("runtime in seconds")
segplot(rt)
text(300;300;"s31.2")
draw()
</code></pre>
<p><img alt="Runtimes of s31.2" src="./img/99_klong/runtimes31_2.png" title="Runtimes of s31.2. The runtime seems to grow linearly, with spikes around values of 9G, 30G and 90G. s31.2 takes around 1 second for a value of 10G."/></p>
<p>And, finally, I measure the runtimes of <code>s31.5</code> and generate the
corresponding graph:</p>
<pre><code>.l("nplot")
.l("time")
s31.5::{:[x<2;0:|x=2;1;&/x!:\2_!x]}
rt::{[a];a::x;time({s31.5(a+_100*.rn())})}'100000+50000*!19
frame([0 1000000 100000]; [0],(1+_|/rt),[0.5])
ytitle("runtime in seconds")
segplot(rt)
text(300;300;"s31.5")
draw()
</code></pre>
<p><img alt="Runtimes of s31.5" src="./img/99_klong/runtimes31_5.png" title="Runtimes of s31.5. It is not clear whether the function grows linearly or quadratically. But it also has spikes, this time around 100k, 200k, 400k and 650k. It takes around 3 seconds for a value of 600k."/></p>
<p>As one can see, both grow approximately linearly, and <code>s31.5</code> is around
twice as slow as <code>s31.1</code>, while having the same growth behavior. I am
not sure where the spikes in the graph come from, they could be from
cache layers, or the internal Klong garbage collector.</p>
<p>One can now give a good justification for choosing <code>s31.5</code> as the prime
checking implementation (though it hurts a bit to be alot slower than
<code>s31.2</code>, while shaving off a few bits).</p>
<pre><code>s31::{:[x<2;0:|x=2;1;&/x!:\2_!x]}
isprime::s31
</code></pre>
<p>Tests:</p>
<pre><code> isprime(7)
1
flr(isprime;!100)
[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]
isprime(-1)
0
isprime(0)
0
isprime(1)
0
</code></pre>
<h3 id="P32__Determine_the_greatest_common_divisor_of_two_positive_integer_numbers"><a class="hanchor" href="#P32__Determine_the_greatest_common_divisor_of_two_positive_integer_numbers">P32 (**) Determine the greatest common divisor of two positive integer numbers.</a></h3>
<p>Implementing <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm">Euclid's
algorithm</a> is not
very hard:</p>
<pre><code>s32::{:[0=y;x;.f(y;x!y)]}
gcd::s32
</code></pre>
<p>Testing it:</p>
<pre><code> gcd(36;63)
9
s32(1;10)
1
s32(0;10)
10
s32(-15;10)
-5
s32(123456;98765432)
8
</code></pre>
<p>Seems about right.</p>
<h3 id="P33__Determine_whether_two_positive_integer_numbers_are_coprime"><a class="hanchor" href="#P33__Determine_whether_two_positive_integer_numbers_are_coprime">P33 (*) Determine whether two positive integer numbers are coprime.</a></h3>
<blockquote>
<p>Two numbers are coprime if their greatest common divisor equals 1.</p>
</blockquote>
<p><em>— niplav, <a href="./99_klong_problems.html#P33__Determine_whether_two_positive_integer_numbers_are_coprime">“P33“ in 99 Klong Problems</a>, 2019</em></p>
<p>This is trivial:</p>
<pre><code>s33::{1=s32(x;y)}
coprime::s33
</code></pre>
<p>Testing:</p>
<pre><code> coprime(35;64)
1
coprime(35;63)
0
</code></pre>
<h3 id="P34__Calculate_Eulers_totient_function_phim"><a class="hanchor" href="#P34__Calculate_Eulers_totient_function_phim">P34 (**) Calculate Euler's totient function phi(m).</a></h3>
<blockquote>
<p>Euler's so-called totient function phi(m) is defined as the number of
positive integers r (1 <= r < m) that are coprime to m.</p>
</blockquote>
<p><em>— niplav, <a href="./99_klong_problems.html#P34__Calculate_Eulers_totient_function_phim">“P34“ in 99 Klong Problems</a>, 2019</em></p>
<p>Since a predicate for coprimality is already given with <code>s33</code>, it is
not hard to find the number of coprimes for a given integer: Iterating
the smaller integers just works fine. <code>s34</code> calculates <code>s33</code> for all smaller
integers, returning a list containing 0s and 1s for the respective coprimality.
Using the Where verb compresses the list of boolean values into indices of
1, so one can just return the length of that compressed list.</p>
<pre><code>s34::{[t];t::x;#&{s33(x;t)}'!x}
totientphi::s34
</code></pre>
<p>An alternative formulation filters the list after coprimality, and then returns
the length of that list: <code>s34::{[t];t::x;#flr({s33(x;t)};!x)}</code>, but that solution is
slightly longer.</p>
<p>Tests:</p>
<pre><code> totientphi(10)
4
totientphi(1)
1
totientphi(0)
0
totientphi'!20
[0 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18]
</code></pre>
<h3 id="P35__Determine_the_prime_factors_of_a_given_positive_integer"><a class="hanchor" href="#P35__Determine_the_prime_factors_of_a_given_positive_integer">P35 (**) Determine the prime factors of a given positive integer.</a></h3>
<p>In short, this solution generates all prime numbers ≤x, iterates to
determine how often x divides the given prime and repeats that prime
that many times.</p>
<p>To find the primes, it filters the numbers from 1 to x using <code>s31</code>. The
iteration is similarly easy: it divides <code>x</code> by the given prime until
<code>x!prime</code> (x modulo the prime) is 0. This produces a list of numbers,
starting with x, with x divided by the prime one or more times. The
length of this list is the number of times x can be divided by the
prime. In theory, one could then just use the Reshape verb to repeat the
prime this many times, but unfortunately Reshape, used as repetition,
has the weird behavior of producing the atom n with 0 as length: <code>0:^5</code>
is <code>5</code>, not the empty list <code>[]</code> or something similar. Because of this,
atoms have to be filtered out of the result list using <code>{~@x}</code> as a filter.
The result is then flattened and returned.</p>
<p>Also, this function accesses arguments of outer functions pretty
often. It would be nice to be able to have a shortcut for the arguments of
outer functions (or does this violate some deep structure in functional
programming languages?). If this were possible, it would probably shave
off a couple of bytes from the code.</p>
<pre><code>s35::{[a];a::x;,/flr({~@x};{[b];b::x;(#{~x!b}{x:%b}\~a):^x}'flr(s31;1+!x))}
primefactors::s35
</code></pre>
<p>Tests:</p>
<pre><code> primefactors(315)
[3 3 5 7]
s46'2+!10
[[2] [3] [2 2] [5] [2 3] [7] [2 2 2] [3 3] [2 5] [11] [2 2 3] [13] [2 7] [3 5] [2 2 2 2] [17] [2 3 3] [19] [2 2 5] [3 7]]
primefactors(1)
[]
primefactors(0)
kg: error: plus: type error: [1 []]
</code></pre>
<p>Unsurprisingly, this algorithm and its implementation is <em>abysmally</em> slow:</p>
<pre><code> .l("time")
time({primefactors'2+!100})
0.37971
time({primefactors(1023)})
1.095063
</code></pre>
<!--
TODO:
[Here](https://github.com/kevinlawler/kona/wiki/K-99%3A-Ninety-Nine-K-Problems#problem-30-202)
is a better solution for factoring (it is shorter etc.), but
1. I don't understand it.
2. It is written in K.
Solve these two problems, and adopt it!
-->
<h3 id="P36__Determine_the_prime_factors_of_a_given_positive_integer_2"><a class="hanchor" href="#P36__Determine_the_prime_factors_of_a_given_positive_integer_2">P36 (**) Determine the prime factors of a given positive integer (2).</a></h3>
<p>Given the implementations of <code>s10</code> and <code>s35</code>, this is very easy:</p>
<pre><code>s36::{|'s10(s35(x))}
primefactorsmult::s36
</code></pre>
<p>Tests:</p>
<pre><code> primefactorsmult(315)
[[3 2] [5 1] [7 1]]
</code></pre>
<h3 id="P37__Calculate_Eulers_totient_function_phim_improved"><a class="hanchor" href="#P37__Calculate_Eulers_totient_function_phim_improved">P37 (**) Calculate Euler's totient function phi(m) (improved).</a></h3>
<p>This problem is also simple to solve: One simply generates the prime
factors and their multiplicities, and then implements the function