Hamiltonian
Hamiltonian is an esolang based on Hamiltonian cycles. Finding the result of a Hamiltonian computation is an NP-complete problem.
Syntax
Any given program will consist of any number of tokens, which are either digits and * symbols. An example program is below:
12*8**
Any character that is not a token is ignored.
12 This is the same program. *8aa**
To execute a program, the compiler counts the number of tokens and adds *'s until the number of tokens is a triangle number.
12*8 Again, the same program.
If the new number of tokens is the nth triangle number, there are considered to be (n+1) nodes in the graph. The first n tokens are the weights on the arcs from the starting node, with the first token corresponding to the arc to node 1, the second to node 2 and so on. The next (n-1) tokens are on the arcs from node 1 to node 2, from node 1 to node 3 and so on. (I've called the starting node 0, in case you were confused.)
A weight of * means there is no connection between the two nodes.
Solving
The compiler takes the resultant graph and finds the lengths of all possible Hamiltonian cycles. It then orders the cycles from shortest to longest and executes an instruction based on the length of each.
To execute an instruction, the length mod 8 is calculated, and the compiler selects an instruction from the following:
0 - Swap the top two elements of the stack. (Underload's "~") 1 - Duplicate the top element of the stack. (Underload's ":") 2 - Discard the top element of the stack. (Underload's "!") 3 - Concatenate the top element of the stack to the end of the second element of the stack. (Underload's "*") 4 - Pop the stack and append that string to the program. (Underload's "^") 5 - Push the string "0" onto the stack. 6 - If the string on the stack is a single digit, increment it by 1, mod 8 7 - Print the stack, see below (Underload's "S")
To print, take characters in groups of 3, padding with 0 if needed. Take the values as bits, and print each group of 9 bits as a char, ignoring the first bit.