I was contacted by a friend that maintains an online judge, asking about the solution to a particular problem that has existed for how many days on an “easy” section.
Basically, the problem is this: given positive integers A, B, C, D, compute A/B + C/D and simplify it. You are guaranteed that if you represent A/B + C/D = E/F in lowest terms, then all of A,B,C,D,E,F fit in p-bit integers (in the problem, p = 64). Your task is to find this E and F.
Here we go again! To remind you, this is the original.
12345, a puzzle game where 2+2=3 and 5+5=0. Merge boxes and utilize special blocks to achieve a perfect cover.
Original Game • Easy Version • v1.0
This game is now released! Get through 30 mind-boggling levels with quirky mechanics! (But intuitive once you get it. Some levels are intended to be difficult due to discovering the mechanics first.)
Sequels are possible. You can also contribute, sending your ideas (levels/objects) to me, which might get included in official sequels. You can even create your own spin-off if you want!
So, this is what I did today.
Original version • Easy version • Version 1.0 • AoPS discussion thread
The original version has no instructions (and is intended), although its mechanics is identical to the easy version, which is intended to be easy and has instructions.
So, feedback! Comments, criticisms, suggestions are much appreciated. Also, open for levels and objects suggestions, as long as it can be implemented in the scripting language I use for this, PuzzleScript. (Just suggest anything; I’ll see if it can be implemented.)
(Oh, also, tip. If you get stuck at figuring out the main screen: Wait until it displays the title and with Start Game and so on, then click the applet (to get focus), then press space bar to select. (If you have a previous saved data, you can use arrow keys to choose the menu “Continue”.) The controls are the arrow keys, plus Z for undo and R for restart.)
An esoteric programming language, and by esoteric, I mean as esoteric as Fractran.
A program consists of several directed lines on the Euclidean plane. A line has four properties: the direction it is going to, whether it is bounded to the “back” (negative, opposite of the line’s direction) (and if so, the endpoint), whether it is bounded to the “front” (positive, along the line’s direction) (and if so, the endpoint), and an attribute. All lines are open (doesn’t include the endpoints).
The program must consist of the line y = 0 directed to the “right” (positive; “left” is negative) that is not bounded to the back; this is the “main line” equivalent to the main procedure in other languages.
The lines may intersect, but no intersection may be passed by more than two non-vertical lines; this results on a compile error. No two non-vertical lines may coincide at more than one point either; this also results a compile error.
The program begins with a “program counter” (PC) at 
Vertical lines (infinite/undefined slope) behave very differently though. A vertical line has no direction, and the PC never goes along a vertical line. There is a completely different set of attributes for vertical lines. Generally non-vertical lines and intersections are for various conditionals, and vertical lines are about programs.
The program ends successfully if the PC can be proven not to meet any other intersection. The program returns a runtime error if the PC reaches an endpoint of a line.
The program has an “input stack”. True to its name, when the program is executed, all input is moved to the input stack so that the first bit in input is the top bit in the stack. The program modifies this stack (as the sole movable data storage). The program also has a standard output.
Attributes for non-vertical lines:
– Is 1: Pops a bit from the input stack. If it’s 1, PC moves to the line met; if it’s 0, PC stays on the same line. If there is no bit to read, the program returns a runtime error.
– Is 1 Seen: Similar to “Is 1”, but pushes back the bit to the input stack afterwards.
– Is Empty: Checks whether the input stack is empty. If it is empty, PC moves to the line met. If it is not empty, PC stays on the same line.
The three attributes above also come with the negated variants: PC stays on the same line if the condition is met and moves to the line met otherwise.
– Move: PC is forced to move along this line. (Note that as only the attribute of the line met that is checked, PC can move out from this line on the next intersection.)
Vertical lines:
– Output: Prints a 1 if the PC has a positive ordinate (y-coordinate), 0 if the PC has a negative ordinate, and doesn’t print anything otherwise.
– Push: Pushes a 1 to the input stack if the PC has a positive ordinate, 0 if the PC has a negative ordinate, and doesn’t push anything otherwise.
So far that’s all attributes I can think of.
Progline can be specified in natural English, but since I want a more compact definition:
Every line I write is of this format:
(equation) (direction) (back-boundedness) (front-bounded-ness) (attribute)
Equation is always in the form y = slope * x + constant for non-vertical lines and x = constant for vertical lines.
Direction is Left or Right for non-vertical lines and Up for vertical lines. (The latter makes sure a back endpoint is lower than a front endpoint, which is usually natural to humans (smaller numbers to the left of larger numbers when written).)
Each boundedness is either None or a point that the line is guaranteed to pass.
Attribute is one of the above.
A line that is preceded by * is a comment. A blank line is also allowed to clarify procedures better.
Sample program:
Copy input bit
Outputs the first bit in input, or leave the output empty if there is no input.
* Main line
y = 0 Right None None Move
* Check whether input stack is empty. If it’s empty, go to the left. We’ll make sure no line afterwards interferes with this line, so this successfully exits the program.
y = x Left (1,1) None Is Empty
* Otherwise, read the first bit in the input (that is proven to exist). If it’s 1, go up with the first line; if it’s 0, go down after passing the first line unchanged. Note that as endpoints are open, these two lines don’t intersect.
y = x-10 Right (-10, 0) None Is 1
y = -x+12 Right (11, 1) None Move
* Now PC is above the x-axis if the input is 1 and below otherwise. Also, PC won’t meet any other line, so the program exits successfully.
x = 14 Vertical None None Output
Infinite loop
This utilizes the push vertical attribute to generate numbers endlessly, while keeping the input stack near empty.
* Begin by pushing a 0 to the stack. The first line is the obligatory main line, the second line moves PC down, the third line pushes 0, the fourth line moves PC up (passing the ended main line to above x-axis), and the fifth line keeps the PC on a horizontal line just for the sake of ease.
y = 0 Right None (-9, 0) Move
y = -x-10 Right None None Move
x = -9 Up None None Push
y = x+8 Right None None Move
y = 2 Right None None Move
* Begin the fun. The loop utilizes the triangle (-2, 2)—(2, 2)—(0, 4).
* First, the PC will pass an Is 1 line. This line will be skipped in the first iteration, but will be followed in later iterations; keep reading. This also has the side effect of consuming the 0, which helps keeping the stack empty (although it’s not necessary).
y = x+4 Left None None Is 1
* Now, the PC will pass a Push line. Because it has ordinate 2, it will push 1 to the stack.
x = 0 Up (0, 1) (0, 3) Push
* We move back to our Is 1 line.
y = -x+4 Left None None Move
* Now, it will meet our Is 1 line before, and will move along that line because our bit is 1. The PC then meets the y=2 line again with empty stack, repeating the state and hence proving an infinite loop.
Progline programming problems! (some are open)
– Can you find a Copy input bit program that has no endpoints of lines anywhere? (I found one.)
– Can you find an Infinite loop program that doesn’t push values into the stack, even if it means an infinite input is required? (I found one.)
– Can you find an Infinite loop program that doesn’t push values into the stack but has only a finite input? (I haven’t found one 😦 ) Or otherwise prove that this is impossible.
– Can you make the Hello, world! program? (Assume that every 8 bits output is bundled into one ASCII character, with earlier bit being more significant and printed characters are from left to right. So “123” can be output by 001100010011001000110011, as “00110001” is “1”, “00110010” is “2”, and “00110011” is “3”, concatenated together.) (I found one.)
– Can you make a program that generates the Thue-Morse sequence? (I haven’t found one 😦 )
In the famous Queens Problem, you need to put n chess queens on an n x n chessboard so no two queens attack each other. It has been proven that a solution exists for all n except n=2,3.
One of the methods (albeit an ineffective one) to solve it is by greedy algorithm, which does a depth-first search. In this case, a queen is placed on the first row, on the first column. The next queen is placed on the second row, starting from the first column. As it attacks a previous queen, it is moved to the second column, and again to the third column. Now as they don’t attack, a third queen is placed from the leftmost column rightward, and so on. When a queen cannot be placed, the previous queen is removed and placed to the next column. This guarantees a solution, as it checks every possible board as long as no conflict has been made.
For example, with n=4:
First queen tries a1.
Second queen tries a2. Conflict with a1.
Second queen tries b2. Conflict with a1.
Second queen tries c2.
Third queen tries a3,b3,c3,d3 in order but conflicts each time. Second queen is retracted.
Second queen tries d2.
Third queen tries a3, conflict with a1.
Third queen tries b3.
Fourth queen tries a4,b4,c4,d4, all conflict. Third queen is retracted.
Third queen tries c3,d3, all conflict. Third queen is retracted. Second queen is retracted (cannot go further).
First queen tries b1.
This algorithm is run until the solution b1,d2,a3,c4 is found (the first solution found). In total, there are 26 queen tries.
For n=5, it can be verified that it takes 15 queen tries to arrive at a1,c2,e3,b4,d5.
Can you compute the number of queen tries for a given n effectively? In other words, is this problem in P? (Naively executing the algorithm gives a possible n^n steps, so it’s not polynomial. You need a better way.)
Extra Problem
A revised version of the algorithm doesn’t put a queen when it makes a conflict. So, for the n=4 example above, we have:
First queen on a1.
Second queen can’t go on a2,b2. Second queen on c2.
Third queen can’t go anywhere, second queen is retracted and go on d2.
Third queen on b3.
Fourth queen can’t go anywhere. Third queen retracted. Second queen retracted. First queen on b1.
And so on.
It takes 8 queen tries now. For n=5, it takes 5 queen tries, or in other words the exact number required.
Can you compute this number effectively too?
Jahooma’s LogicBox is a fantastic game, if you have the proper skills to play it. As in programming interest and somewhat great problem solving skills.
Roughly, you are given a task to perform by placing “boxes” (which represent functions in programming) in a grid. Different levels allow you to use different boxes, and sometimes it becomes extremely challenging because of the nonexistence of some boxes. When the program is run, an object carrying a string appears from the Start box, following the directions and executing the boxes’ purposes, until the object leaves the grid. You must match the direction where you are told to exit from, and the string in your object must have been modified to match the requirements. You probably can understand better by playing it.
So, what’s the point of this post then? As you can probably expect, I love that game, at least until when it requires payment to play a fuller version (it’s still in “lite” version, and judging from the “premium” release name in 2013, it seems like it’s going to need money to play). Well, I’ll just make some puzzles to post here. Yay.
Puzzles!
In each puzzle, you are given an infinite grid to toy with unless otherwise stated; if your object won’t encounter any more box, you can say that it leaves the grid, in the same direction as the game (up = green, down = red, left = yellow, right = blue). You are also given the boxes available and their effects. Finally, you are also obviously given the task, but not the test cases! It’s up to you to determine. You can submit your solutions to me if you want me to check it, but I will analyze your program and give you either the verdict CORRECT or the verdict INCORRECT along with one test case where your program fails the task. Oh yay that looks like a programming contest or something. But then again it’s a programming game, so yeah. After everything that matters with the puzzle, you might be given a Variants section which will adapt your solution into several other similar boxes.
Reminding you again that square boxes cut the input up to just before the first asterisk, aka if you have “ab*cd”, a square box will only accept the argument “ab” and leaves “*cd” unchanged.
Also, Redirect is always an available box, and because I aim this to be more programmer-style, Redirect (and Start) isn’t counted as a box when counting the total number of boxes and not counted as a step when counting the total number of steps.
Puzzle 1.1: Is It A Star? (Easy)
Is Period: Given an input, determine whether the first character is a period or not. You should exit from the green direction if it is, and red direction if it isn’t. The input should stay unchanged when it is output.
Boxes:
– Circular Add period (adds a period in front of the string)
– Circular Copy (copies the first character of the string to the end of the string)
– Circular Delete (deletes the first character of the string)
– Circular Compare (compares the first character and the second character of the string; if they are equal, exit green, otherwise exit red; the input is unchanged)
Sample cases:
– “.a” -> “.a”, exit green
– “a.” -> “a.”, exit red
– “period” -> “period”, exit red
– “…” -> “…”, exit green
Variants:
Is Asterisk: Checks whether the first character is asterisk; if it is, exit green, otherwise exit red. Replaces all mentions of “period” in the previous implementation with “asterisk”.
Puzzle 1.2: Finding Star (Medium)
Find Period: Given an input containing at least one period, splice the string into two parts: before the first period and after the first period. Afterwards, change their position so the part after the period appears first. The period is “consumed” and disappears.
Boxes:
– Circular Add period (adds a period in front of the string)
– Circular Copy (copies the first character of the string to the end of the string)
– Circular Delete (deletes the first character of the string)
– Circular Compare (compares the first character and the second character of the string; if they are equal, exit green, otherwise exit red; the input is unchanged)
– Circular Rotate (moves the first character of the string to the end of the string)
– Circular Is period (implemented from your solution to Puzzle 1.1)
Sample cases:
– “abc.def” -> “defabc”
– “a.b.c” -> “b.ca”
– “…” -> “..”
– “.” -> “”
Variants:
Find Asterisk: Splices the argument into two parts, one before asterisk and one after asterisk. The two parts exchange place so the latter appears first while the former follows. is removed. If doesn’t exist, the program gets to an infinite loop. Replaces all mentions of “period” in the previous implementation with “asterisk”.
Puzzle 1.3: Getting A Clearer View (Hard)
Square Back Rotate: Given an input not containing any asterisk, move the last character of the string to the front of the string.
Boxes:
– Circular Add asterisk (adds an asterisk in front of the string)
– Circular Copy (copies the first character of the string to the end of the string)
– Circular Delete (deletes the first character of the string)
– Circular Compare (compares the first character and the second character of the string; if they are equal, exit green, otherwise exit red; the input is unchanged)
– Circular Rotate (moves the first character of the string to the end of the string)
– Circular Is asterisk (implemented from your solution to Puzzle 1.1, replacing period with asterisk)
– Circular Find asterisk (implemented from your solution to Puzzle 1.2, replacing period with asterisk)
Sample cases:
– “abcd” -> “dabc”
– “period.” -> “.period”
– “aaa” -> “aaa”
– “ayayay” -> “yayaya”
Puzzle 1.4: Counting Stars (Insane)
Square Increment Number: Given an input of a valid non-negative integer (starts with a digit other than zero except if it has only one character), increment its value by 1.
Boxes:
– Circular Add asterisk (adds an asterisk in front of the string)
– Circular Add period (adds an period in front of the string)
– Circular Add zero (adds a zero in front of the string)
– Circular Copy (copies the first character of the string to the end of the string)
– Circular Delete (deletes the first character of the string)
– Circular Compare (compares the first character and the second character of the string; if they are equal, exit green, otherwise exit red; the input is unchanged)
– Circular Rotate (moves the first character of the string to the end of the string)
– Circular Increment (increments the first character of the string (0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 0; * -> *; . -> .))
– Circular Is asterisk (implemented from your solution to Puzzle 1.1, replacing period with asterisk)
– Circular Find asterisk (implemented from your solution to Puzzle 1.2, replacing period with asterisk)
– Circular Is period (implemented from your solution to Puzzle 1.1)
– Circular Find period (implemented from your solution to Puzzle 1.2)
– Square Back rotate (implemented from your solution to Puzzle 1.3)
Sample cases:
– “123” -> “124”
– “999” -> “1000”
– “0” -> “1”
– “499499” -> “499500”
It’s weird that I’m a fan of Pokemon but I don’t have any entry about it in this blog. So here goes the first entry.
The following regex expression scores precisely one match in the set of all 649 names of Pokemon. (Hopefully; at least it scores precisely one match among all Pokemon names I remember.) What is it? (Case insensitive.)
(j|q|x|z).+\1
Chaos at the Sky 