A non-decreasing sequence is a sequence of n integers A[1] .. A[n] with, for all j > i, A[i] less than or equal to A[j]. In other words, it is a sequence possibly containing duplicates sorted into increasing order.
Given a sequence S, an upsequence of S is a non-decreasing sequence produced by deleting elements of S.
Write a program that, given a sequence, returns its longest upsequence. You may return any of the longest upsequences if there is more than one of them.
For example:
upsequence [1,4,5,6,6,8] [1,4,5,6,6,8] upsequence [1,4,6,5,6,6,8] [1,4,5,6,6,8] upsequence [2,1,3,2,3,7,8,6,7,8,15,11,12] [1,2,3,6,7,8,11,12]
The input to the program will be a 10x10 grid of cells. A cell is either a dot '.' or a hash '#'. Adjacent cells are called neighbours. Non-edge cells have 8 neighbours. Edge-cells have have 5 neighbours, or 3 if they are on a corner.
The initial configuration is called the 0th generation. From the 0th generation we can calculate the 1st generation, from the 1st generation we can calcululate the 2nd generation, and so on. The rules for calculating the next generation each time are:
Write a program which, given an initial configuration, and a integer n representing the number of generations to simulate, calculates and displays the nth-generation.
E.g. if the input denominations were 1¢, 3¢, 5¢,
10¢, 20¢ what is the smallest number of coins to
produce a total of 46¢ ?
A: 4 coins: 3¢, 3¢, 20¢, 20¢.
Write a program which, given a list of denominations and an integer repesent the desired total, returns the shortest list of coins of the denominations which add to the total.
You may assume that the denominations will include 1¢. The coins in the output list can be in any order you wish. If there is more than one shortest list combination you may return whichever of them you wish.
Take a strip of paper hold one end in each hand. Call the end in your left hand the start, and the end in your right hand the finish. Fold the strip by holding your left hand still and bringing the finish over the start. Unfold it enough so that the fold is a right angle. This is step 1.
*** * *
Step 2 is the same as step 1, except you make another fold before unfolding. (Again bring the right hand over the left to make the fold.)
*** * *** * *
Step n is one more fold than step n-1.
To display the results of your folding - unfold enough to make all folds right angles, and show the start segment as a horizontal line moving left to right. Just as in the pictures above.
Write a function fractal which, given the number of steps, produces the picture of the folded strip in the above format.
For example:
fractal 1
***
*
*
fractal 2
***
*
***
*
*
fractal 3
***
*
*** ***
* * *
* ***
You may leave trailing spaces on or take them off as you wish. Make sure you orient the displayed picture correctly.
For example: ..G.. MOON. ..L.. ..D..
Restrictions: All strings in the output must be connected by intersection (ie no unconnected strings). No pair of horizontal strings can be vertical neighbours, no pair of vertical strings can be horizontal neighbours. A pair of strings are vertical neighbours if they have any characters in the same column on adjacent rows. A pair of strings are horizontal neighbours if they have any characters on the same row in adjacent columns.
Example invalid configurations: 1. unconnected strings GOLD .... MOON .... 2. vertical neighbours ..G.. MOON. .FLY. ..D..
Write a program which, given a list of strings and a pair of integers representing width and height, arranges the strings to form a crossword no larger than the specified height/width rectangle. Your program should display the crossword in a format similar to the examples above.
You can assume there *is* a legal configuration. The strings supplied need not be English words - there is no dictionary involved in this question (unlike a real game of crosswords).
Half marks for a program which works for up to 3 strings. The remaining half of the marks are for the full program which should work for any number of input strings. You can collect the partial marks before writing the full program if you wish.
You may assume the height and width will each not exceed 12.
You have some computers you wish to connect with nextwork cable. You don't need to run cable from each computer to every other computer to connect them all, it is sufficent if there is a cable path (ie a sequence of links) between each pair of computers. You have a list of how much it will cost to lay cable linking various pairs of computers and you wish to work out the cheapest way of connecting them all together.
You cannot join cables midway - each cable must start at one computer and finish at another with no breaks or junctions. The computers are named 1,2,..n.
Write a program which, given n (the number of computers) and a list of possible cable links and their costs, determines which cables you should lay to connect all computers with minimum cost.
The list of cable links will be given in the format:
N N COST N N COST ...etcwhere N N are integers denoting the two computers connected by the link, and COST is an integer denoting the cost of the link. Your output is to be a subset of this list, displayed in a similar format.
You can assume that there *is* at least one combination of cable links which connects all the computers. There is no limit to the number of cables you can have connected to a computer.