Three standard traversals of binary trees are preorder, inorder and postorder. Assuming all the nodes of a binary tree contain unique values, an inorder traversal and a postorder traversal completely determine the shape and information in a tree. For example, an inorder traversal of ABCDEFG and a postorder traversal of ACBFGED correspond to the tree below.
D / \ B E / \ \ A C G / F
Write a program that has as input the inorder and postorder traversals of binary trees and produces the preorder traversals of the trees. Each node in the tree contains a single printable nonblank character. A traversal can therefore be represented as a character string (as in the first paragraph above).
Input for your program consists of a text file organised into pairs of lines. The first line of each pair contains the postorder traversal of a tree and the second line contains the inorder traversal of the same tree. You may assume that there are an even number of lines in the file and that each line contains no blank or nonprintable characters. You may also assume that the pairs of lines are consistent, that is, given the nth line, the n is odd, the n+1th line contains the inorder traversal of the tree whose postorder traversal in on the preceding line.
Output should consist of a copy of the input as well as the preorder traversal of each tree.
For example, the tree shown above would be represented in input as:
ACBFGED ABCDEFG CDAB CBAD
And for this data, your program should print:
Postorder traversal: ACBFGED Inorder traversal: ABCDEFG Preorder traversal: DBACEGF Postorder traversal: CDAB Inorder traversal: CBAD Preorder traversal: BCAD
A new sonar system has been developed which can detect the presence or absence of objects in water up to one metre deep. Unfortunately, it only has a resolution of one centimetre and can only scan a surface area of one square metre without distortion. The device generates data in this form:
000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000 D 000000000000000000000000000000000000000000000000000000 e 000000000000000000000000000000000000000000000000000000 p 000000000000000000000000000000000000000000000000000000 t 000000000000000000000000000000000000000000000000000000 h 000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000 I n 000000000000000000000000000000000000000000000000000000 c 000000000000000000000000000000000000000000000000000000 r 000000001111000000000000100000000000000000000011000000 e 000000000111000000000000100000000011111100000000000000 a 000100000000000000000000000000000000000000000000000000 s 000100000000000000000000000001110000000000000000000000 i 000100000000000000000000000000000010101010100000000000 n 000000000000000000000000000000000000000000000000000000 g 000000000000000000000000000000000000000000000000000000 | 000000000110000000000000100000000011111100000001100000 | 000000011111000000000000100000000011111100000011110000 V 000000001111000000000000110000000011111100000001100000 000100000011100000000000000000000000011000000000001100 000100000000000001111100000001110000000000000000000000 000100000000000000000000000000000000000000000001110000 000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000 000000000000000000000000110000000000111000000000000000 000000001110000000000000110000000001111100000011110000 000000001111000000000000110000000001111100000000000000 000100000011000000000000000000000000011000000000000000 000100000000000001111100000001110000000000000000000000 000100000000000000000000000000000001010101010000000000 000000000000000000000000000000000000000000000000000000
One wealthy customer wants to use the device to monitor his fish tank. When a fish dies, it floats to the top or sinks to the bottom, but in either case it is no longer detected by the device. You have been asked to take data such as the above, and count the number of objects of each different size. This way, when a fish dies it can be detected as missing.
Input data will consist of three numbers, the width, height and depth of the data followed by depth cross sections of the tank each with width characters and height lines. Only ones and zeros will appear in the sonar report.
For the above data the first few lines would be:
54 8 4 000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000 ...
There will be a blank line between each of the cross sections.
You must output the size and a count of the number of objects of that size for all sizes that occur in the data, for example (using the above data):
Size Count ============ 1 10 2 1 3 1 9 2 10 1 12 1 30 1 41 1
Note:
Given a line segment drawn from 5 to 7 along a reference line marked in units from an arbitrary origin, it is obvious that the line segment is 2 units long. In fact, however, we obtain this answer by taking the imaginary 7 unit long line and subtracting an imaginary 5 unit long line: 7-5 is 2. A planimeter is a mechanical device that employs the two-dimensional equivalent of this geometric trick to determine the area enclosed by merely tracing the perimeter.
For example, consider the following walk:
Move Command Right 3 r 3 Up 1 u 1 Left 1 l 1 Up 2 u 2 Left 3 l 3 Down 2 d 2 Right 1 r 1 Down 1 (closed) d 1 Down 1 d 1 Left 1 l 1 Up 1 u 1 Right 1 (closed) r 1
The enclosed areas are, as one would expect, 9 units and 1 unit.
You are to write a program that accepts a list of motion commands tracing a series of perimeters, computes and prints the area enclosed by each, and prints the total area enclosed by all perimeters.
Each motion command is on a line by itself in the form given above: a single character in the first column indicating the direction (u,d,l,r), followed by a space and then an integer which indicates a distance to move in that direction.
There is no command separating the moves tracing one perimeter from those tracing the next, but each perimeter is a closed walk -- each starting and ending at the same point. This fact should be used to distinguish one perimeter from the next. Print each enclosed area as an integer, right justified in four columns. At end of file, print the total area accumulated from all walks of perimeters.
For the example given above, your program should output:
9 1 ==== 10
Notes:
The decimal expansion of the fraction 1/33 is 0.(03), where the (03) is used to indicate that the cycle 03 repeats indefinitely with no intervening digits. In fact, the decimal expansion of every rational number (fraction) has a repeating cycle as opposed to decimal expansions of irrational numbers, which have no such repeating cycles. Examples of decimal expansions of rational numbers and their repeating cycles are shown below. Here, we use parentheses to enclose the repeating cycle rather than place a bar over the cycle.
Fraction Decimal Expansion Repeating Cycle Cycle Length 1/6 0.1(6) 6 1 5/7 0.(714285) 714285 6 1/250 0.004(0) 0 1 300/31 9.(677419354838709) 677419354838709 15 655/990 0.6(61) 61 2
Write a program that reads numerators and denominators of fractions and determines their repeating cycles. For the purposes of this problem, define a repeating cycle of a fraction to e the first minimal length string of digits to the right of the decimal that repeats indefinitely with no intervening digits. Thus for example, the repeating cycle of the fraction 1/250 is 0, which begins at position 4 (as opposed to 0 which begins at positions 1 or 2 and as opposed to 00 which begins at positions 1 or 4).
Each line of input consists of an integer numerator, which is non-negative, followed by an integer denominator which is positive. None of the input integers exceeds 3000. A sample input is as follows:
76 25 5 43 1 397
For each line of input, print the fraction, its decimal expansion through the first occurrence of the cycle to the right of the decimal, or 50 decimal places (whichever comes first), and the length of the entire repeating cycle. In writing the decimal expansion, enclose the repeating cycle in parentheses when possible. If the entire repeating cycle does not occur within the first 50 places, place a left parenthesis where the cycle begins -- it will begin within the first 50 places -- and place ``...)'' after the 50th digit. Output for the sample input file is shown here:
76/25 = 3.04(0) number of digits in repeating cycle = 1 5/43 = 0.(116279069767441860465) number of digits in repeating cycle = 21 1/397 = 0.(00251889168765743073047858942065491183879093198992...) number of digits in repeating cycle = 99
Othello is a board game played on a 8x8 board with 64 discs that are black on one side and white on the other. A legal move consists of placing a disc with the player's side facing up on an empty square such that opponent discs are bracketed by the newly placed disc and the player's colour already on the board. These bracketed discs are flipped and become the player's own colour. To bracket a disc in any direction (horizontal, vertical or diagonal), there must be an uninterrupted line of opponent discs starting at the newly placed disc and terminated by a disc of the player's colour.
Here is an example board, where black is to move next:
ABCDEFGH 1.*.....* 2..o..*o. 3....oo.. 4.*oo.... 5....o... 6....*... 7........ 8........
This shows a position where a move to E4 flips discs at C4, D4, F3, G2, and E5. The disc at C2 is not flipped because of the empty square D3, and the disc at E3 is not flipped because there is no black disc at E2. Note that there is no black disc at E2. Note that there is no chain reaction: flipping D4 does not cause E3 to be flipped. A player with no legal move has to pass (forfeit his turn). A player with legal moves is not allowed to pass.
In this question, your program must accept as input an Othello board in ASCII format, a single letter (``b'' or ``w'') for whose move it is next, and a set of moves. After applying all the moves, the resulting board is output. Each available legal move is numbered in order of all available moves starting at the top right and going right and then down. For example, a board with the legal moves numbered in this order would be as is shown in figure one. If the first move to be made were ``3'' by black, then the move would be C4, resulting board shown in figure two.
o....... o..1.... o....... .o.o.... .o2o.... .o.o.... oooo.... oooo.... oooo.... ...o*... ..3o*... ..***... ...**... ...**... ...**... ..*o.*.. ..*o4*.. ..*o.*.. ........ ..56.... ........ ........ ........ ........ Figure 1 Figure 2
Input data will contain from one to five moves (terminated by a newline). For example, given this input, with three moves to perform:
o....... .o.o.... oooo.... ...o*... ...**... ..*o.*.. ........ ........ b 3 2 5
Your program should output:
o....... .o.o.... oooo.... .****... .o.**... ..*o.*.. ........ ........
Notes:
Many Unix programmers like the editor called ``vi''. In this problem, you are challenged to write a simple non-interactive version of vi. The input will be a sample of text, terminated with a single period in column one and then followed by a string of vi commands. The output will be the resulting text. The commands that you must implement are as follows, with their effect.
Command Result i[text][esc] Insert [text] before the current character I[text][esc] Insert starting at the beginning of line a[text][esc] Insert after the current character A[text][esc] Insert at end of line s[text][esc] Substitute the character under the cursor for [text] S[text][esc] Substitute the whole line the cursor is on with [text] x Delete the current character X Delete the character to the left of the cursor h,j,k,l Move: left, down, up, and right 0 Go to the beginning of the current line $ Go to the end of the current line f[character] Find the next occurrence of [character] in the current line F[character] Find the previous occurrence of [character] on this line Prefix Result [number][command] Repeat [command] [number] of times (where [number]> 0)
After reading the text to be edited, your program should position the cursor at the first character of the text. You may assume that lines will be restricted to 80 characters only (even during editing) and there will be a maximum of 40 lines of text at any time. Remember the value \033 or 0x01b corresponds to the escape key ([esc]). There is only one line of commands to be interpreted.
Here is an example of the input to your program:
Now is the time for all good men to come to the aid of their country. It is also the time for all the women to go home and make lots of new soldiers. . fmfm3swomen[esc]24liour[esc]l5xj02fm2X
The corresponding output is as follows:
Now is the time for all good women to come to the aid of our country. It is also the time for all the men to go home and make lots of new soldiers.
Notes: