== Expressing integers using four nines
What non-negative integers can you write as expressions containing exactly four occurrences the number 9, and any of the binary operators *, /, %, +, -, prefix negations, and any number of matching pairs of parentheses you care to use?
The program should accept an upper limit N as a command-line argument. It should then print all integers 0..N in increasing order, along with an expression with four nines, if any such was found.
More precisely, let's say your program didn't find a four-nines expression for the number 18. Then it should simply print
18
on that particular line. If it did find a number, it should include the expression it found, like this:
18 = 9 + 9 * (9 / 9)
== Sum of cubes
Some natural numbers can be as the sum of two positive cubes of natural numbers. For example, 1729 is 12 cubed plus 1 cubed. Some natural numbers can even be expressed as more than one such sum. For example, 1729 can also be expressed as 10 cubed plus 9 cubed.
Just for clarity's sake, the sum with the two terms reversed is the same sum, not a new one. Thus, 91 is 3 cubed plus 4 cubed, but finding "4 cubed plus 3 cubed" does not count as a distinct sum.
Write a program that accepts an integer N on the command line, and prints out the first N of these numbers in increasing order. For each number found, print it out, as well as the sums of cubes that yield that number.
For example:
1729 = 12 ** 3 + 1 ** 3 = 10 ** 3 + 9 ** 3
== Addition chains
For a positive integer N, an addition chain for N is a sequence starting with 1, each subsequent element being the sum of two earlier elements (possibly the sum of the same element twice), and ending with N.
For example for N = 9, this is a possible addition chain:
(1, 2, 4, 5, 8, 9)
because 2 = 1 + 1, 4 = 2 + 2, 5 = 1 + 4, etc.
But a minimal solution would be:
(1, 2, 3, 6, 9)
Write a program that reads numbers N from standard input, one per line, and outputs a minimal addition chain like the one above.
Sometimes there will be several possible solutions of minimal length. That's fine; just pick one of them.
== Hex puzzle
This problem makes use of a board of hexagonal cells that looks like this:
i1 i2 i3 i4 i5
j1 j2 j3 j4 j5 j6
k1 k2 k3 k4 k5
l1 l2 l3 l4 l5 l6
m1 m2 m3 m4 m5
n1 n2 n3 n4 n5 n6
o1 o2 o3 o4 o5
Each cell has up to six neighbors. l3 has neighbors (clockwise) k3, l4, m3, m2, l2, and k2.
The board is populated with some number of straight pieces of length 2 and 3. Pieces never overlap, but they can move in the direction of their length, which we will refer to as a "groove". So for example, a piece that starts out on locations l1 and l2 can "slide" over to rest on locations l5 and l6. No valid move can make a piece leave the groove in which it was first found.
We write "groove" because "row" doesn't quite capture how the pieces can be situated. Besides the above seven rows of the table, a groove (and thus the pieces in it) can also run along a diagonal direction, like this:
e1 d1 c1 b1 a1
f1 e2 d2 c2 b2 a2
f2 e3 d3 c3 b3
g1 f3 e4 d4 c4 b4
g2 f4 e5 d5 c5
h1 g3 f5 e6 d6 c6
h2 g4 f6 e7 d7
Or a groove and its pieces could run along the other diagonal direction:
p2 q4 r6 s7 t7
p1 q3 r5 s6 t6 u6
q2 r4 s5 t5 u5
q1 r3 s4 t4 u4 v4
r2 s3 t3 u3 v3
r1 s2 t2 u2 v2 w2
s1 t1 u1 v1 w1
There are a total of 23 grooves on the board, 7 horizontal, and 8 for each diagonal. Grooves vary in length from 2 (out in the corners) to 7 (around the main diagonals).
A valid playing move on this board consists of sliding a piece along its groove, either forwards or backwards. There are a few things which are not allowed:
-
Two pieces may never overlap and occupy the same location. (Note that the above three representations of the board actually denote the same board; the three sets of grooves intersect each other.)
-
A piece may not "push" another piece as it slides; it is simply locked in by that other piece.
-
A piece may not "jump" over another piece as it slides; it is restricted in its movement by the current positions of the other pieces.
-
A piece may not rotate, move sideways, or otherwise leave its groove.
It's perfectly valid for a groove to contain more than one piece (as long as they don't overlap).
For this problem, we will restrict ourselves to initial board configurations with a piece at l1 and l2 (written as "l12"). We call this piece the "bullet". The goal is to slide the bullet to l56, through a valid sequence of moves. Thus, other pieces may have to be moved in order to get the bullet to l56.
.. .. .. .. ..
.. .. .. .. .. ..
.. .. .. .. ..
start --> l1 l2 .. .. l5 l6 <-- goal
.. .. .. .. ..
.. .. .. .. .. ..
.. .. .. .. ..
Some initial configurations won't have a solution at all. (For example, the bullet will never get through if there are other pieces in its groove.)
Write a program that accepts an initial board configuration on standard input. The format looks as follows:
d67
i12
l12
u345
v34
The program should reject any initial board configuration that has illegal piece specifications, contains overlapping pieces, or lacks the bullet at l12.
If there is possible solution, the program should output
No solution.
Otherwise it should output one solution as a sequence of valid moves on this format:
u[345 -> 456]
d[67 -> 23]
u[456 -> 123]
v[34 -> 23]
l[12 -> 56]
A solution doesn't have to be minimal in the number of moves, but it may count in your favor if it is. Even more so if it's minimal in the total distance the pieces were moved. Arriving at a solution quickly is an even more important success metric than minimal solutions.
== Enumerating trees
We're used to thinking about rooted trees in computer science, but now for a while we'll be talking about unrooted trees.
An unrooted tree is simply a graph with N nodes and N-1 edges, without cycles. Each node is reachable from any other node through exactly one simple path.
Here's an example tree with three nodes.
1--2--3 a tree with a line shape
In order to talk about different trees, we employ a traversal representation that looks like this:
1-2-3-2 traversal representation
This can be thought of as the sequence of nodes encountered when tracing around the tree (say) clockwise. In the above case, we start at node 1, continue to node 2, turn at node 3, find node 2 again, and then we're back at node 1 (which we don't include at the end).
The traversal representation is simply a way to identify each graph by its structure.
For simplicity's sake, let the traversal representation be "canonical", in the sense that it always introduces previously unseen nodes with the numbers 1..*, in order. This reflects the fact that we're really dealing with unlabeled trees, and don't consider nodes to be distinct.
Note that starting from a different node, or mirroring the tree in the plane that embeds it, may yield a different canonical traversal representation. (So it's not quite canonical.) You're free to pick any one of these if there are several.
There's only one tree each with 1, 2, or 3 nodes. 4 is the first interesting case, and has two unique trees
1--2--3--4 another line 1-2-3-4-3-2
1--2--3
| a T-shape 1-2-3-2-4-2
4
Similarly, there are three unique trees with 5 nodes.
Write a program that accepts a positive integer N on the command line, and outputs all unique unrooted unlabeled trees with N nodes, using canonical traversal representation.
For example, for N = 4, the program should output the above two trees:
1-2-3-4-3-2
1-2-3-2-4-2