Non-linear Recursions

Write a program that lets your enter a number from 1 to 7 and that returns the name of the day of the week. Your program should continue asking for week numbers until you enter an invalid integer, at which time it stops. Use an array which you initialize with the days of the week

// The "Ass1s3p1" class.
import java.awt.*;
import hsa.Console;

public class Ass1s3p1
{
    static Console cs = new Console ();

    public static void main (String [] args)
    {
     cs.println("Enter a day-of-the-week number (type an invalid number to stop): ");
     int day=cs.readInt();
     while (day>-1 && day<7)
     {
       cs.println("day "+day+" = "+dayOfWeek(day));
       cs.println("\nEnter a day-of-the-week number (type an invalid number to stop): ");
       day=cs.readInt();
     }
     cs.println("goodbye");
    } // main method

    public static String dayOfWeek (int d)
    {
     String day [] = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
     if (d < 0 || d > 6)
         return "";
     return day [d];
    } // end dayOfWeek
} // Ass1s3p1 class

See: the text file below, and use it to create a text file with 6 columns. Space the data in such a way, that provinces start at position 0, the 1998, 1999, 2000, 2001 and 2002 data respectively at positions 30, 40, 50, 60 and 70. Remove the commas from the numbers.
Write a program that will read the data into 2 arrays: String province[13] and double year[13][5]. Then print the data on the screen.

// The "Ass1s3p4" class.
import java.awt.*;
import java.io.*;
import hsa.Console;

public class Ass1s3p4
{
    static Console cs = new Console ();
    static String province [] = new String [11];
    static double year [] [] = new double [11] [5];

    public static void main (String [] args) throws IOException
    {
     readText ("PopulationByProvinces.txt");
     for (int i = 0 ; i < 11 ; i++)
     {
         cs.print (province [i], 25);
         for (int y = 0 ; y < 5 ; y++)
         {
          cs.print (year [i] [y], 10, 2);
         } //end y-loop
         cs.println ();
     } //end i-loop
    } // end main method

    public static void readText (String fileName) throws IOException
    {
     String line;
     FileReader f = new FileReader (fileName);
     BufferedReader input = new BufferedReader (f);
     for (int i = 0 ; i < 11 ; i++)
     {
         line = input.readLine ();
         province [i] = line.substring (0, 30);
         year [i] [0] = Double.valueOf (line.substring (30, 40)).doubleValue ();
         year [i] [1] = Double.valueOf (line.substring (40, 50)).doubleValue ();
         year [i] [2] = Double.valueOf (line.substring (50, 60)).doubleValue ();
         year [i] [3] = Double.valueOf (line.substring (60, 70)).doubleValue ();
         year [i] [4] = Double.valueOf (line.substring (70)).doubleValue ();
     } // end i-loop
     input.close ();
    } // end readText
} // Ass1s3p4 class

Use this text file for the program above

Newfoundland and Labrador     545.3     540.9     537.9     533.8     531.6
Prince Edward Island          136.9     137.8     138.3     138.9     139.9
Nova Scotia                   936.1     941.2     942.3     942.9     944.8
New Brunswick                 753.3     755.5     755.6     756       756.7
Quebec                        7323.6    7351.2    7381.8    7417.7    7455.2
Ontario                       11387.4   11527.9   11697.6   11894.9   12068.3
Manitoba                      1137.9    1142.5    1146.4    1149.1    1150.8
Saskatchewan                  1024.9    1025.6    1022      1017.1    1011.8
Alberta                       2906.8    2959.6    3009.9    3059.1    3113.6
British Columbia              3997.1    4028.3    4060.1    4101.6    4141.3
Yukon                         31.5      31.1      30.6      30.2      29.9
Northwest Territories         41.1      41        40.8      41.2      41.4 
Nunavut                       26.4      26.9      27.5      28.1      28.7

Searching in two dimensions: Find the best route:

    4
    5
    12 10 33 21
    15 20 14 24
    18 15 52  5
    22 21 30 41
    12 14 20 33

Imagine you are at the bottom left corner, and want to go to the top right of this array. You may only move east or north, and therefore must make 7 moves altogether. At each point you must pay a toll: the indicated amount of dollars. Write a program that will find the minimum amount of money you must spend.

// The "Ass1s4p1" class.
// Find the cheapest path through a rectangular grid:
import java.awt.*;
import hsa.TextConsole;
import java.io.*;
import java.util.*;

public class Ass1s4p1
{
    static TextConsole cs = new TextConsole ();
    static int grid [] [];
    static int gridX = 0;
    static int gridY = 0;
    static int cheapest;
    static String path;

    public static void main (String [] args) throws IOException
    {
     cs.println ("The file that contains the rectangular maze must contain:");
     cs.println ("on the first line:   the width of the grid (gridX)");
     cs.println ("on the second line:  the height of the grid (gridY)");
     readGrid ("cheap1.txt");
     cheapest = 100 * gridX + 100 * gridY;
     bestPath (0, 0, grid[0][0], ""+grid[0][0]);
     cs.println ("\nThe cheapest path is: $" + cheapest + ".- through " + path);
    } // main method

    static void readGrid (String dirName) throws IOException
    {
     FileReader f = new FileReader (dirName);
     BufferedReader input = new BufferedReader (f);
     gridX = Integer.parseInt (input.readLine ().trim ());
     gridY = Integer.parseInt (input.readLine ().trim ());
     grid = new int [gridX] [gridY];
     for (int j = 0 ; j < gridY ; j++)
     {
         String line = input.readLine ();
         cs.println (line);
         StringTokenizer list = new StringTokenizer (line);
         for (int i = 0 ; i < gridX ; i++)
          grid [i] [gridY - j - 1] = Integer.parseInt (list.nextToken ().trim ());
     }
     input.close ();
    } //end readGrid

    static void bestPath (int x, int y, int cost, String p)
    {
     if (x < gridX - 1)
         bestPath (x + 1, y, cost + grid [x + 1] [y], p + " " + grid [x + 1] [y]);
     if (y < gridY - 1)
         bestPath (x, y + 1, cost + grid [x] [y + 1], p + " " + grid [x] [y + 1]);
     if (x + y == gridX + gridY - 2 && cost < cheapest)
     {
         cheapest = cost;
         path = p;
     }
    } //end bestPath
} // Ass1s4p1 class

Create a text file containing a field of x's and an path of 0's starting in the top row. Let the field be a 20 rows x 30 columns. Looking something like the array of x¼s and o¼s below. Find the length of the path, knowing that the path starts in the upper left hand corner, and that it will always either go right or down.

     20 
     30
     0000000xxxxxxxxxxxxxxxxxxxxxxx
     xxxxxx000xxxxxxxxxxxxxxxxxxxxx
     xxxxxxxx0xxxxxxxxxxxxxxxxxxxxx
     xxxxxxxx0000xxxxxxxxxxxxxxxxxx
     xxxxxxxxxxx0xxxxxxxxxxxxxxxxxx
     xxxxxxxxxxx0xxxxxxxxxxxxxxxxxx
     xxxxxxxxxxx0xxxxxxxxxxxxxxxxxx
     xxxxxxxxxxx000xxxxxxxxxxxxxxxx
     xxxxxxxxxxxxx0xxxxxxxxxxxxxxxx
     xxxxxxxxxxxxx0xxxxxxxxxxxxxxxx
     xxxxxxxxxxxxx0xxxxxxxxxxxxxxxx
     xxxxxxxxxxxxx00000000xxxxxxxxx
     xxxxxxxxxxxxxxxxxxxx0xxxxxxxxx
     xxxxxxxxxxxxxxxxxxxx00xxxxxxxx
     xxxxxxxxxxxxxxxxxxxxx0xxxxxxxx
     xxxxxxxxxxxxxxxxxxxxx0xxxxxxxx
     xxxxxxxxxxxxxxxxxxxxx0xxxxxxxx
     xxxxxxxxxxxxxxxxxxxxx0xxxxxxxx
     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

// The "Ass1s4p3" class.
// Find the length of a path that can go right and down only
import java.awt.*;
import hsa.TextConsole;
import java.io.*;

public class Ass1s4p3
{
    static TextConsole cs = new TextConsole ();
    static String maze [];
    static int mazeW = 1, mazeH = 1;
    static int steps = 0;

    public static void main (String [] args) throws IOException
    {
     cs.println ("The file that contains the rectangular maze must contain:");
     cs.println ("on the first line:   the width of each line of the maze");
     cs.println ("on the second line:  the height of the maze (the number of lines)");
     readMaze ("maze1.txt");
     pathFinder (0, 0, 1);
     cs.println ("\nThe length of the path is: " + steps + " steps");
    } // main method

    static void readMaze (String DirName) throws IOException
    {
     FileReader f = new FileReader (DirName);
     BufferedReader input = new BufferedReader (f);
     mazeW = Integer.parseInt (input.readLine ().trim ());
     mazeH = Integer.parseInt (input.readLine ().trim ());
     maze = new String [mazeH];
     for (int i = 0 ; i < mazeH ; i++)
     {
         maze [i] = input.readLine ();
         cs.println (maze [i]);
     }
     input.close ();
    } //end readMaze

    static void pathFinder (int x, int y, int pathSofar)
    {
     if (maze [y].charAt (x) == '0')
     {
         steps = pathSofar;
         if (x + 1 < mazeW)
          pathFinder (x + 1, y, pathSofar + 1);
         if (y + 1 < mazeH)
          pathFinder (x, y + 1, pathSofar + 1);
     } // end if
    } //end pathFinder
} // Ass1s4p3 class

Prepare a text file for simulating flood filling a given closed shape.
Then write a program that uses recursion to fill the inside of such a shape, with 'T', given any interior point. Print the file before and after the fill.

40 
15
.....TTTTTTT............................
....T.......TTTTTTTTTTTT................
...T....................TTTT............
....T......................T............
..TT.....................TT.............
.T.......................T..............
..T.......................TTT...........
...TT........................T..........
.....T........................T.........
.....T.....TT.................T.........
.....T...TT..TT..............T..........
....T....T.....T..........TTT...........
...T......T....TTT....TTTT..............
....T......T.....TTTTT..................
.....TTTTTT.............................

// The "Ass1s4p6" class.
import java.awt.*;
import hsa.TextConsole;
import java.io.*;

public class Ass1s4p6
{
    static TextConsole cs = new TextConsole ();
    static String field [];
    static int fieldW = 1, fieldH = 1, min = 200;

    public static void main (String [] args) throws IOException
    {
     cs.println ("The file that contains the rectangular field must contain:");
     cs.println ("on the first line:   the width of each line of the field");
     cs.println ("on the second line:  the height of the field (the number of lines)");
     readMaze ("fillfield1.txt");
     floodFill (10, 10);
     cs.println("output...");
     for (int i = 0 ; i < fieldH ; i++)
         cs.println (field [i]);
    } // main method

    static void readMaze (String DirName) throws IOException
    {
     FileReader f = new FileReader (DirName);
     BufferedReader input = new BufferedReader (f);
     fieldW = Integer.parseInt (input.readLine ().trim ());
     fieldH = Integer.parseInt (input.readLine ().trim ());
     field = new String [fieldH];
     for (int i = 0 ; i < fieldH ; i++)
     {
         field [i] = input.readLine ();
         cs.println (field [i]);
     }
     input.close ();
    } //end readMaze


    static void floodFill (int x, int y)
    {
     if (x > -1 && x < fieldW && y > -1 && y < fieldH)
     {
         if (field [y].charAt (x) == '.')
         {
          field [y] = field [y].substring (0, x) + 'T' + field [y].substring (x + 1, fieldW);
          floodFill (x + 1, y);
          floodFill (x - 1, y);
          floodFill (x, y + 1);
          floodFill (x, y - 1);
         } 
     }
    } //end pathFinder
} // Ass1s4p6 class

Santa's magic sack, for carrying gifts for chidren down the chimney, can hold up to 8 000 000 cubic centimetres. The sack can wrap around any number of gifts of any shape or size as long as it does not exceed the 8 000 000 cm³ limit. The number of gifts, N that he can choose from does not exceed 15.
No gift is larger than 8 000 000 cm³.
The volume of each gift is expressed as an integer.
The input text file contains the number N followed by N integers, representing the gifts.
Write a program that will pick from among the N gifts the subset that will maximize the volume of the magic sack. Then print out the volume used.
(from the STA Online Computer Programming contest, DWITE, Dec 2002)

6 1550001 2655002 4355004 125008 654316 3555032

// The "Ass1s4p8" class.
import java.awt.*;
import hsa.TextConsole;
import java.util.*;
import java.io.*;

public class Ass1s4p8
{
    static TextConsole cs = new TextConsole ();
    static int box [];
    static int number = 0;
    static int fullest = 0;

    public static void main (String [] args) throws IOException
    {
     readArray ("santasack1.txt");
     stuffBag (0, 0);
     cs.println ("Santa's bag contains " + fullest + " cubic cm worth of presents");
    } // main method

    static void readArray (String dirName) throws IOException
    {
     FileReader f = new FileReader (dirName);
     BufferedReader input = new BufferedReader (f);
     String line = input.readLine ();
     cs.println ("input is: " + line);

     StringTokenizer list = new StringTokenizer (line);
     number = Integer.parseInt (list.nextToken ().trim ());
     box = new int [number];
     for (int i = 0 ; i < number ; i++)
         box [i] = Integer.parseInt (list.nextToken ().trim ());
     input.close ();
    } //end readArray

    static void stuffBag (int partFull, int thisBox)
    {
     // don't put this Box in the bag (one possibility)
     if (thisBox < number)
         stuffBag (partFull, thisBox + 1);
     // if there is room, put this Box in the bag (other possibility)
     if (thisBox < number && box [thisBox] + partFull <= 8000000)
         stuffBag (box [thisBox] + partFull, thisBox + 1);
     if (partFull > fullest)
         fullest = partFull;
    } //end stuffBag
} // Ass1s4p8 class