Planet Scheme

August 23, 2016

Programming Praxis

Nearly Square Divisors, Revisited

In a recent exercise, we discussed the problem of computing the nearly square divisors of a composite number n = a · b, with a ≥ b, such that the difference ab is as small as possible. We gave two solutions: The first solution enumerated the divisors one-by-one, by trial division counting from 1, until reaching the square root, which is fast if n is small but slow in general. The second solution factored n, computed the divisors, the picked the two divisors in the middle of the list, which is fast in general but slow if n is highly composite and thus has a large number of divisors.

In a comment on that exercise, Matthew Arcus, who is a regular reader and commentor at Programming Praxis, gave a splendid answer to the problem; it relies on factoring n, but is fast even if n has a large number of divisors. His algorithm reduces the multiplication of the factors to addition of their logarithms, which means that the knapsack algorithm can be used to find the greatest sum less than the logarithm of the square root.

Your task is to implement Matthew’s algorithm to find the nearly-square divisors of a number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 23, 2016 09:00 AM

August 21, 2016

Grant Rettke

August 19, 2016

Programming Praxis

Diminishing Gap Sort

Today’s exercise comes from my friend Dan:

I don’t have time to think about this now (very busy these days), so I’m just throwing the idea at you. I’m sure there’s some sort of mathematical theorem that relates, but I’m sure you’ll probably know off the top of your head.

I was fascinated not too long ago by the consulting firm we’ve hired to re-vamp our website. I think they were given a tip-off that the color selection for the website theme could be a sticky wicket. So their plan was to pull the colors dynamically from the main picture selected on the home page (and/or departmental pages), which could be changed easily or automatically. They were going to develop something that would pick out the most prominent 6 to 10 colors — even if there wasn’t much contrast (and even black & white photos would supposedly work) — which would be then used for the menus and general color scheme.

Anyway, all this got me thinking about sorting a list of numbers (if these were color codes, there could be lots) such that the greatest gaps would float to the top. I’m sure you get the idea, but I’ll give an example anyway — which I figured out in Excel (below):

Given a number set of 5, 12, 14, 15, 80, 121, 134, 144, 256 the descending-by-highest-difference sort would yield: 256, 80, 121, 134, 144, 12, 14, 15, 5. So in this case, the top 3 biggest gaps would be between 80, 121, and 256.

     Num  Diff              Num  Diff
    ----  ----             ----  ----
     256   112              256   112
     144    10               80    65
     134    13              121    41
     121    41              134    13
      80    65              144    10
      15     1               12     7
      14     2                5     5
      12     7               14     2
       5     5               15     1

I have no idea if this makes sense for the colors thing — it just seemed like the type of problem you frequently do on Programming Praxis.

Hope all is well with you and your family!

-Dan-

Your task is to write a program that sorts a set of points in order by the diminishing gaps between them. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 19, 2016 09:00 AM

August 16, 2016

Programming Praxis

Highly Composite Numbers, Revisited

In a recent exercise, we used a priority queue to calculate highly composite numbers. That worked, but it was too slow and required too much memory to compute very large highly composite numbers. In today’s exercise we will use the same algorithm but a new data structure that permits us to compute very large highly composite numbers.

We make two changes. First, we record both highly composite numbers and candidates that are being considered as new highly composite numbers in a data structure called number-divisors-exponents, or ndxs for short, which has a number n in its car, the number of divisors d of n in its cadr, and the exponents of the prime factors of n in its cddr; carrying those numbers around rather than recomputing them as needed saves a little bit of time. The second change is more important; we use the distinct priority queue of a previous exercise to eliminate duplicate candidates, which greatly reduced the amount of computation needed to find highly composite numbers (since each candidate is considered only once) and the amount of memory require to store the candidates (because duplicates are not stored).

Your task is to write a program to compute highly composite numbers, as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 16, 2016 09:00 AM

August 12, 2016

Programming Praxis

Min-Min-Max

My statistics always decline in the summer, but they are starting to pick up, so I guess school must be starting in some places. Here’s a simple homework problem for beginning programmers:

Given an unsorted array of integers, find the smallest number in the array, the largest number in the array, and the smallest number between the two array bounds that is not in the array. For instance, given the array [-1, 4, 5, -23, 24], the smallest number is -23, the largest number is 24, and the smallest number between the array bounds is -22. You may assume the input is well-formed.

Your task is to provide two solutions to the problem, the first a straight forward solution that a beginning programmer might write, and a second solution that is rather more “creative;” feel free to define creative however you wish. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 12, 2016 09:00 AM

August 09, 2016

Programming Praxis

Priority Queues With Distinct Elements

I recently needed a priority queue that contains no duplicate elements; if an attempt is made to add an element to the priority queue that is already present in the priority queue, the priority queue remains unchanged. As far as I know, none of the standard priority queue algorithms provide such a feature; they can’t, because they are all based on trees, and any element of the priority queue can be in either branch at any level of the tree.

Your task is to write a program that provides the data structure of priority queues with distinct elements. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 09, 2016 09:00 AM

August 05, 2016

Programming Praxis

Nearly-Square Divisors

We have today a fun little problem from number theory:

Given positive integers n, a and b such that n = a · b with ab, find a and b such that the difference ab is as small as possible.

For n square, the solution is just the square root of n; for instance, with n = 36, a = b = 6. Otherwise, a and b will be the two divisors nearest the square root; for instance, with n = 60, a = 10 and b = 6.

Your task is to write a program to find a and b as described above; use your program to find the nearly square divisors of n = 224403121196654400. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 05, 2016 09:00 AM

August 03, 2016

GNU Guix

GNU Guix and GuixSD 0.11.0 released

It is a pleasure to announce the new beta release of GNU Guix and GuixSD, version 0.11.0!

The release comes with USB installation images to install the standalone GuixSD, and with tarballs to install the package manager on top of your GNU/Linux distro, either from source or from binaries.

It’s been 4 months since the previous release, during which 70 people contributed code and packages. The highlights include:

See https://lists.gnu.org/archive/html/guix-devel/2016-08/msg00219.html for details.

About GNU Guix

GNU Guix is a transactional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user's freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and armv7.

by Ludovic Courtès at August 03, 2016 02:23 PM

August 02, 2016

Programming Praxis

Keypad Errors

[ Programming Praxis passed 2 million lifetime hits over the weekend. Gracious thanks to all my readers who have taken it so far. I can still remember being ecstatic when I got to a thousand hits. Thank you all. — Phil ]

Sometimes one key on a keyboard gets stuck, so some keys that are struck do not register. For instance, you may be trying to type 18684 on a numeric keypad, but if the 8 key is stuck, the keyboard registers you typing 164 instead. Assume the only input allowed is the digits 0 through 9.

Your task is to write a program that takes a target number, say a PIN, and a keyboard input, and determines if the keyboard input matches the target number assuming a single key is stuck. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at August 02, 2016 09:00 AM

July 29, 2016

Programming Praxis

Gnome Sort

A garden gnome sorts flower pots by the following method:

The gnome looks at the flower pot next to him and the flower pot just behind him. If they are correctly ordered, so the flower pot just behind him is smaller than the flower pot next to him, he steps one pot forward; otherwise, he swaps the two flower pots and steps one pot backward. If there is no flower pot just behind him (thus, he is at the start of the line of flower pots), he steps forward to the next pot. If there is not flower pot next to him (thus, he is at the end of the line of flower pots), he is done.

Your task is to implement a program that sorts by the gnome method. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at July 29, 2016 09:00 AM

July 26, 2016

Programming Praxis

Changing Gender

The culture wars have my head spinning so fast that I need a computer to help me out. One day I might say “He is my brother.” and the very next day, speaking about the same person, say “She is my sister.”

Your task is to write a program that changes the gender of the words in a string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at July 26, 2016 09:00 AM

July 22, 2016

The Racket Blog

Racket v6.6

Racket version 6.6 is now available from http://racket-lang.org/

  • The new Macro Profiler command-line tool (`raco macro-profiler`) shows how macros contribute to the final expanded code size of a program.
  • Typed Racket supports intersection types. This allows the type system to track more information, and for programmers to express more precise types.
  • Typed Racket produces up to 4x smaller compiled files compared with Racket 6.5, reducing the size of the Racket distribution by 50M.
  • Typed Racket issues warnings in cases where the contract generated for Any was not strict enough in the past. These warnings will become errors in a future release. Warnings are enabled via View -> Show Log in DrRacket, and shown by default on command-line Racket.
  • Typed Racket enforces uses of cast more correctly, by checking both the "casted-to" and "casted-from" types. Previously, only the former were checked. In some cases, this will produce contract errors in programs that did not have errors before.
  • syntax-parse raises an error when an ellipsis pattern has an empty match rather than diverging, and it logs a warning when it statically detects a nullable pattern, such as ((~seq) ...). In the next version of Racket, it will reject the pattern instead, and it will remove special handling that currently makes some uses of such patterns terminate.
  • htdp/dir: The create-dir function delivers data information for files in a new field. The domain of its functions are backwards compatible.

The following people contributed to this release:
Alex Knauth, Alexander Shopov, Alexis King, Andrew Kent, Asumu Takikawa,
Ben Greenman, Bernardo Sulzbach, Brian Lachance, Chris Jester-Young, Dan
Feltey, Eric Dobson, Georges Dupéron, Gustavo Massaccesi, James Bornholt,
Jay McCarthy, John Clements, Leandro Facchinetti, Leif Andersen, Maksim
Kochkin, Matthew Flatt, Matthias Felleisen, Mike Sperber, Paul Stansifer,
Pedro Caldeira, Philip McGrath, Robby Findler, Ryan Culpepper, Sam
Tobin-Hochstadt, Spencer Florence, Stephen Chang, Stephen De Gabrielle,
Tim Brown, Tony Garnock-Jones, Vincent St-Amour, WarGrey Gyoudmon Ju,
William J. Bowman, and Zeina Migeed.

Feedback Welcome

by Vincent St-Amour (noreply@blogger.com) at July 22, 2016 11:50 PM

Programming Praxis

Array Manipulation

Our task today comes from Geeks for Geeks:

Given an array of positive integers, replace every element with the least greater element to its right. If there is no greater element to its right, replace it with -1. For instance, given the array [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28], the desired output is [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1].

Your task is to write the program that manipulates an array as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at July 22, 2016 09:00 AM

July 19, 2016

Programming Praxis

Highly Composite Numbers, A Sieving Approach

We’ve seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of Eratosthenes.

If you have to find a the divisors of a number, or count them, you can employ the brute-force method of testing each possible divisor from 1 to n, as in the first solution to this problem, or you can factor n and compute the divisors, as we have done in a previous exercise. But if you have to find the divisors of a bunch of numbers, in sequence, you can sieve for them; we also did that in a previous exercise. Once you know the divisor-count for each number from 1 to n, a simple sequential scan looking for successive records will create the list of highly composite numbers.

Your task is to write a program to calculate highly composite numbers less than a limit n using a sieving algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at July 19, 2016 09:00 AM

July 15, 2016

Programming Praxis

Highly Composite Numbers, Using Priority Queues

A different solution to the previous exercise exploits the form of highly composite numbers, which always consists of small primes to large exponents, so we can specify the highly composite number using only the exponents; for instance, 64221111 represents the number 26 · 34 · 52 · 72 · 111 · 131 · 171 · 191 = 293318625600. Since the exponents must be non-increasing, there are five possibilities for a larger highly composite numbers, represented using the power-notation as 74221111, 65221111, 64321111, 64222111, and 642211111. Thus, we find composite numbers by starting with the null power-list, which equates to the number 20 = 1, then add all possible successors to a priority queue, pop the successors in order, check each for a new record number of divisors, and push the successors of that number back on to the priority queue.

Your task is to generate the sequence of highly composite numbers using a priority queue. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at July 15, 2016 09:00 AM