Practicing problem solving with puzzles

Puzzles came into vogue in the mid-19th century, appearing in many newspapers and magazines. Puzzles help with the development of problem solving skills. Part of the problem of designing programs is that novice programmers will try to solve the problem during the process of coding, or coding-on-the-fly. Puzzles help develop abstract thinking skills, enhance creativity and problem solving skills. Computer science uses a number of classical puzzles to illustrate concepts. Probably the most widely used puzzle is the Towers of Hanoi, introduced by French mathematician Édouard Lucas in 1883, and used exclusively for illustrating recursion. Other classical examples include the n-queens problem (backtracking), and Bridges of Könisberg (graphs). There are a number of examples of books which provide numerous puzzles including “The Canterbury Puzzles”, published in 1907 by Henry Dudeney, and Sam Loyd’s mathematical puzzles.

Brute force

This method of solving problems works on the principle of exhaustive search, i.e. finding all possible candidates for a solution and seeing which satisfies the problem domain. Brute force will always find a solution, if one exists. An example of brute force is the “Goats from cabbage” puzzle [1]:

“Separate all the goats from the cabbage in the picture by drawing 3 straight lines”

The easiest way of solving this problem is to try and draw lines on the picture using trial and error, and iterate through all possibilities until a solution is found.

Divide and Conquer

This means of problem solving is based on partitioning a problem into smaller subproblems, solving them independently and combining their solutions to arrive at a solution to the original problem. One example of a divide-and-conquer puzzle is “How much does the bottle weigh” [1].

The bottle and glass on the left scale balance the jug on the right scale (a). The bottle alone balances and glass and a plate (b), and 3 of the plates balance 2 jugs (c). How many glasses will balance the bottle? 

Solving this puzzle requires breaking the problem down into sub-problems: deciding how substitutions could be performed to solve a problem. Let’s denote the jug, glass, plate, and bottle by J, G, P, and B respectively. In the first subproblem, using (a) we can substitute two bottles (B) and two glasses (G) for the two jugs in (c):

(c)  BBGG–PPP

In the second subproblem, we can double the quantities in (b):

(d)  BB–GGPP

We can now substitute the two bottles in (c) with GGPP from (d):

(c) GGPPGG–PPP

Now taking two plates off either side will not disturb the balance:

(c) GGGG–P

Thereby leaving one plate balancing 4 glasses. Now in (b), instead of 1 plate put 4 glasses, thereby having 5 glasses balance the bottle.

Another divide-and-conquer problem is the “Bottle’s Volume” [1] .

“If a bottle, partly filled with liquid, has a round, square or rectangular bottom which is flat, can you find its volume using only a ruler? You may not add or pour out liquid.”

It may seem like a challenging problem, because of the shape of the bottle, however the area of a circle, square or rectangle can easily be calculated after measuring sides or diameter with a ruler. Call the area s. With the bottle upright, measure the height h1 of the liquid. The full part of the bottle has the volume sh1.

Turn the bottle upside down and measure the height h2 of the air space. The empty part of the bottle has the volume sh2. The whole bottle has the volume s(h1+ h2).

[1] Kordemsky, B.A., The Moscow Puzzles, 1972.
[2] Dudeney, H.E., Amusements in Mathematics, 1917.

 

Coding Cobol: Calling C (ii) – arrays

The hardest part of any type of program interoperability is likely data transfer, and the hardest component of this is arrays. It is often quite easy to transfer single pieces of data, but arrays are infinitely harder, especially when C is involved, because of the existence of pointers.

The interoperability of data types is sometimes compiler dependent. For example GNU Cobol offers a type binary-c-long which equates to a (signed) long in C. The sample programs below will provide an idea as to how to go about passing arrays between a calling Cobol program, and the associated C procedure it calls.

identification division.
program-id. arrays.
environment division.
data division.
working-storage section.
01 data-table.
   05 table-entry usage binary-c-long occurs 10 times.
01 tec          pic 99.
01 table-index  pic 99.

procedure division.
  move 10 to tec.
  call "arr" using by reference data-table
                   by value tec.
  perform varying table-index from 1 by 1
      until table-index > tec
      display table-entry(table-index)
  end-perform.
  stop run.

First let’s tackle the creation of an array in Cobol, which is called a table. It has two names data-table representing the “complete package”, and table-entry representing the elements of the array. In this case it is a table containing 10 elements of type binary-c-long. The external C function arr just populates the array with values. The variables tec and table-index represents the number of values in the array to populate, and the index variable respectively.

The function arr is then invoked using the call statement, passing data-table as a reference argument, and tec as a pass-by-value argument. The rest of the Cobol code merely prints out the table after it is returned from the C function. Now let’s look at the C function arr().

#include <stdio.h>
typedef long tarr[10];
void arr(tarr base, int L)
{
   int i;
   for (i=0; i<L; i=i+1)
      base[i] = i;
}

It specifies a typdef tarr, which is used to specify the parameter for the table in arr(). The rest of the code merely assigns a value to each of the L elements in the array base. This C function is then compiled using gcc -c arr.c to produce an object file.

The Cobol program is then compiled in the following manner:

cobc -free -x -Wall arrays.cob arr.o

Now when the program is run, the output has the form:

+00000000000000000000
+00000000000000000001
+00000000000000000002
+00000000000000000003
+00000000000000000004
+00000000000000000005
+00000000000000000006
+00000000000000000007
+00000000000000000008
+00000000000000000009

Not ideal from an aesthetic viewpoint, but it gives you a sense of the size of binary-c-long looks like in Cobol. When doing this sort of inter-language function call, I strongly suggest looking at the compilers documentation with respect to associated datatypes between C and Cobol.

 

Coding Ada: Timing code and passing functions to functions

If you have to time a function in a language like Ada, one option is to create a timer function that takes the function to be timed as a parameter. Here is an Ada program that times the Ackermann function. There is nothing special about the ackermann() function, except that it is recursive. The interesting part of the code involves creating a type, functype, to hold the function “pointer”, or access point. The type uses the phrase “access function” followed by the parameter list for the function in question, and the type of the return value. This denotes an Access type, which is the equivalent of a pointer in other languages. Rather than using the term “points to”, Ada prefers to refer to this type of entity as “granting access” to an object. An access to subprogram allows the caller to call a subprogram without knowing its name nor its declaration location.

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Calendar; use Ada.Calendar;

procedure passingfunc is

   type functype is access function (x,y: integer) return integer;

   function ackermann(m,n: in integer) return integer is
   begin
      if m = 0 then
         return n+1;
      elsif n = 0 then
         return ackermann(m-1,1);
      else
         return ackermann(m-1,ackermann(m,n-1));
      end if;
   end ackermann;

   procedure timeit(Func : functype; m,n : in integer) is 
      result : integer;
      startTime, endTime : time;
      milliS : Duration;
   begin
      startTime := Clock;
      result := Func(m,n);
      endTime := Clock;
      milliS := (endTime - startTime) * 1000;
      put_line("Result: " & Integer'Image(result));
      put_line("Runtime = " & Duration'Image(milliS) & " milliseconds.");
   end timeit;

begin
   timeit(ackermann'Access, 4, 1);
end passingfunc;

The function timeit() can then be implemented. It declares Func as one of the parameters, implying that a function (pointer) can be passed to it. The remaining two parameters are the two parameters to be passed onto ackermann(). Note that the call to Func() is quite normal as well – no magic needed. The guts of the timing algorithm are described in another post, so the interested reader is referred there. When the function timeit() is called in the main program, the ackermann() function is passed using ackermann’Access.

Here’s the program running… with some trivial output:

Result: 65533
Runtime = 17441.122000000 milliseconds.

Those of you who have ever implemented a non-recursive version of Ackermann will note the runtime of 17-odd seconds, which is much faster than the 60-80 seconds of the version using a stack.

Coding Cobol: Calling C (i)

Language interoperability is not a new thing. There are many instances in contemporary programming where it is optimal to call a function written in one language from another. Even doing crazy things like calling C from Cobol. This is important because there are instances when functionality in a legacy language could be provided by something else. Here is an example of calling a C function from Cobol. First let’s deal with the C portion.

#include <stdio.h>

int subc(char *arg1, char *arg2, long long *arg3)
{
   printf("Starting subc\n");
   printf("arg1=%s\n", arg1);
   printf("arg2=%s\n", arg2);
   printf("arg3=%Ld\n", *arg3);
   arg1[0]='X';
   arg2[0]='Y';
   *arg3=987654321;
   return 2;
}

The file subc.c contains only one function, subc(), which has three parameters, arg1, arg2, and arg3. The first two are strings, the last a large integer. The function prints out the values of the three parameters sent when it is called from the Cobol program, and modifies all three parameters. In the case of the two strings, the first element of each string is modified. In the case of the integer, a new value is assigned. The function ends by returning the integer value 2. Here is the accompanying Cobol program, maincob().

identification division.
program-id. maincob.
data division.
working-storage section.
01 arg1  pic x(7).
01 arg2  pic x(7).
01 arg3  usage binary-long.

procedure division.
   display 'starting Cobol Main'.
   move 123456789 to arg3.
   move "vader" to arg1.
   move "luke" to arg2.
   call 'subc' using by content arg1,
      by reference arg2,
      by reference arg3.
   display 'Back'
   display 'Arg1= ' arg1.
   display 'Arg2= ' arg2.
   display 'Arg3= ' arg3.
   display 'Returned value= ' return-code.
stop run.

This program doesn’t do much except illustrate how information can be passed between the Cobol program and the C function. The first part of the program assigns values to the three variables arg1 (vader), arg2 (luke), and arg3 (123456789). Then it calls the C function subc with the three variables being passed. It passes arg1 by content, which means that it essentially passes it by value, i.e. its value cannot be changed by subc. Both arg2 and arg3 are passed by reference (which means it can be modified). The special register return-code contains the value returned by subc.

These programs are compiled by first turning the subc.c file into an object file (gcc -c subc.c). The Cobol program is then compiled in the following manner:

cobc -free -x -Wall maincob.cob subc.o

The output is below showing the code from the subc and maincob programs:

starting Cobol Main
Starting subc
arg1=vader
arg2=luke
arg3=123456789
Back
Arg1= vader
Arg2= Yuke
Arg3= +0987654321
Returned value= +000000002

I leave it to the reader to trace through the program.

 

Human intuition

There is one thing that machines lack completely, and that is human intuition. When you run a piece of machinery, say a furnace, or a motor of some sort, you become attuned to its sounds, usually in a subconscious way because we don’t often sit there intently listening to a furnace run. In some engines there is more than one noise, say an engine running at different speeds, or different gears. When a machine makes a different noise, one that is not within the bounds of its normal operation, that’s intuition steps in and suggests that there may be something wrong. Some will no doubt argue that intuition is possible in AI – I doubt that, because intuition is likely not something capable of being expressed algorithmically.

Coding Cobol: Paragraphs, loops, and if statements

The next example explores a very simplistic interpretation of a Roman numeral generator. For example, it calculates viiii rather than ix for the number 9. This program contains a number of Cobol features, and control structures. The working-storage section contains four variables: maxR (the user input value for the upper bound of Roman numerals to calculate), x and y (working variables), and num (output variable for y).  The procedure division defines where the actual work is done, and also the “main” part of the program. Here the user defined upper bound (maxR)  is read in, y is set to its initial value (1), and the first loop is encountered.

identification division.
program-id. romannumerals.

data division.
working-storage section.
77 maxR  pic 9(4).
77 x     pic 9(8).
77 y     pic 9(8).
77 num   pic Z(7)9.

procedure division.

   display "How many Roman numbers? ".
   accept maxR.
   move 1 to y.
   perform convR
      varying y from 1 by 1
   until y is greater than maxR.
   stop run.

convR.
   move y to x.
   move y to num.
   display num " " with no advancing.
   perform thousandP until x < 1000.
   if x >= 500 then
      display "d" with no advancing
      compute x = x - 500
   end-if.
   perform hundredP until x < 100
   if x >= 50 then
      display "l" with no advancing
      compute x = x - 50
   end-if.
   perform tenP until x < 10
   if x >= 5 then
      display "v" with no advancing
      compute x = x - 5
   end-if.
   perform oneP until x < 1.
   display " ".

thousandP.
   display "m" with no advancing.
   compute x = x - 1000.

hundredP.
   display "c" with no advancing.
   compute x = x - 100.

tenP.
   display "x" with no advancing.
   compute x = x - 10.

oneP.
   display "i" with no advancing.
   compute x = x - 1.

The loop is very different from those found in other languages. It uses the perform keyword to activate the paragraph convR (sort of like a subroutine), using the value y, and varying its value in increments of 1, until it is greater than maxR. For if maxR is 12, it will perform the loop 12 times.

perform convR  
   varying y from 1 by 1  
until y is greater than maxR.

The main part of the program is followed by five different paragraphs, which act as quasi-subroutines, with no parameter passing. The first two lines of convR basically assign values. The second one (move y to num), edits y from a value which can be modified, to an output value. Basically y is an 8-digit integer: 99999999. If it contains the number 124, then it would be printed out as 00000124, which isn’t really that aesthetically pleasing. Better if those 0’s were blanks. This is achieved using the pic Z(7)9, which effectively prints a blank when no digit exists in the output.

Within convR there are a number of further loops, each of which activates a separate paragraph. Here is an example:

perform thousandP until x < 1000.

This basically activates the paragraph thousandP until the condition x<1000 becomes true (it is often known as a “procedural perform”). The paragraph thousandP performs an output and a calculation, then passes control back to the loop. In reality it is possible to incorporate the code from thousandP directly into the loop, but this often lead to much more complicated code.  Lastly there is the if statement (which is little different from that found in other languages).

if x >= 500 then 
   display "d" with no advancing compute 
   x = x - 500 
end-if.

Here is the program running:

How many Roman numbers?
10
       1 i
       2 ii
       3 iii
       4 iiii
       5 v
       6 vi
       7 vii
       8 viii
       9 viiii
      10 x

 

Coding Cobol: A basic program

To start programming in Cobol, let’s consider a small Cobol program which modifies an account balance, and returns the new balance. Notice the first thing that is different is that the Cobol program has a series of “divisions”. Here the first division, “identification“, relates to information about the program, in this case only the program-id. The next section,  “data“, deals with defining external objects such as files, and variables the latter of which are most commonly found in the “working-storage” section. Each variable in the working-storage section has an identifier, and an associated “data-type”, linked using the term pic. In this case the variable amount has a pic of s9999v99 (the term comp-3 is used to specify precision.). This allows a number to be entered which has 4 digits before the decimal place ,and two afterwards, in addition to a sign. The s = sign, v = implicit decimal, and 9 = numeric.

identification division.
program-id. balance.
data division.
working-storage section.
77 old-balance      pic s9999v99 usage is comp-3.
77 amount           pic s9999v99 usage is comp-3.
77 new-balance      pic s9999v99 usage is comp-3.
77 new-balanceO     pic +ZZZ9.99.
procedure division.
   display "Enter old balance: " with no advancing
   accept old-balance
   display "Enter amount: " with no advancing
   accept amount
   add amount to old-balance giving new-balance
   move new-balance to new-balanceO
   display "New balance: " new-balanceO
   stop run.

The s9999v99 implies that if a user enters 51067.1, then Cobol will truncate it to 1067.1 because there just is no room to store anything else.

The main program is associated with the procedure division. There are no “subroutines” in Cobol (unless they are in external files), just groupings of statements into paragraphs. The term display is used to output to the standard output, with the clause “with no advancing“, retaining the cursor at the end of the output of display. The term accept, reads input from the standard input. The calculation of the new balance typifies some of Cobol’s verbose syntax.

add amount to old-balance giving new-balance

which could also be written as:

compute new-balance = amount + old-balance

The result of the programming running is shown below:

Enter old balance: 1000.99
Enter amount: 1000.99
New balance: +2001.98

For an interesting article on Cobol and math, check out this blog post: Is COBOL holding you hostage with math?

 

The realm of real innovation

People think that real innovation comes from highly educated people, but I don’t think that is really the case. Watch an episode of “The Mind of Chefs”, and you will realize that some of the most innovative thinking comes from those that design and create things on a daily basis, be it with food, wood, stone, or yarn. Some of this is down to the whole idea of experiential thought… i.e. thought driven by the experience of actually doing something. If a chef uses a “new” indigenous ingredient in a dish this can have many differing outcomes. For the diner it can lead to the exploration of new flavours. To the wider community it could lead to more sustainable, nutrient rich edibles, and new techniques for preparing said ingredient. For the people cultivating, or foraging for the ingredient it can lead to a sustainable lifestyle. All these things are intertwined, and if done properly can have incredibly positive influences on society.

Academia just isn’t like that. As I have mentioned before, there is very little in the way of experiential learning. Imagine a course on Icelandic history where you are immersed in the real-life history of Iceland by being there and exploring it – you obviously can’t go back in time, but you can visit the places where historical events took place. A two-week immersive course like this would far outweigh a whole semester in a classroom. Or maybe an environmental engineering course where you are solving a real world problem, perhaps in a farming context. Or in a computer science context where you are actually building software to solve a problem, real-time. People sometimes talk negatively about going to college versus university, because “colleges are applied”… but here’s the thing, they probably do more experientially driven teaching than anyone else.

Even more shocking are people who have no formal training. Chefs who are self taught and own Michelin star restaurants. Woodworkers who are self taught and design incredibly intricate pieces of furniture. It’s not really about what you learn, and how many classes you take, it’s about what is within you, and how you can make it shine.

Ada and goto

Every language has its hidden “features”, and Ada, like most other languages has a goto statement. Any statement could be labelled by an identifier enclosed in double angle brackets, << >>. For example:

<<gohere>> g = 12.3; ...
goto gohere;

However, the goto in Ada is somewhat better behaved. It cannot transfer control outside the current subprogram or package body; it cannot transfer control inside a structure (e.g. from else to then in an if statement); and it cannot transfer control from the outside of a structured statement into the body of a structured statement. Consider the following code:

with ada.Text_IO; use Ada.Text_IO;
with ada.Integer_Text_IO; use ada.Integer_Text_IO;

procedure gotoada is
   x,y,z : integer;
 
begin
         put_line("Enter a number: ");
         get(x);
<<lbl1>> if x = 1 then
            y := 1;
            z := 1;
<<lbl2>> else
            y := 2;
            z := 2;
         end if;

         case y is
            when 1 =>
               put_line("jump to top");
               goto lbl1;
            when others =>
               put_line("jump to middle");
               goto lbl2;
         end case;

end gotoada;

The goto associated with lbl1 is allowed. However the goto associated with lbl2, which jumps into the middle of the if statement above it,  is not allowed. Try to compile this, and you’ll get the following compiler message:

gotoada.adb:24:21: target of goto statement is not reachable

Languages like Pascal would easily allow this sort of code, but Ada was designed to prevent issues with uber unstructured code.