Code patternsDataCompare two strings
Compare two strings
Reads two lines and prints Y if they are the same and N if not.
Watch it run
The form “Two lines from the input” works on 17 cells; the named ones are “zero”, “letter”, “flag” and “scratch”. Press Play, drag the step slider forwards and back, or edit first line and second line:
The figure needs JavaScript. The program below is the result for the example values.
The first line is stored with two empty cells after every letter. Then the second line is read one letter at a time, and each letter is taken off the stored one: a flat loop.
If anything is left, the letters differed. A flag is set to 1, and the flag is carried along from letter to letter, as the running total is in the form A running total that travels along of walk an array of records.
A line that is longer than the other leaves letters with nothing to cancel them, so different lengths are caught by the same test.
The code
This is the program the figure ran. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
>>>,----------[++++++++++>>>,----------]<<<[<<<]>>>>>,----------[++++++++++[-<<->>]<<[[-]>[-]+<]>[->>>+<<<]>>>>,----------]<<[[-]>[-]+[->>>+<<<]>>]>>+<[[-]>->>++++++[-<+++++++++++++>]<.[-]<]>[>>+++++++++++[-<++++++++>]<+.[-]<->]<<
What it needs
- Both lines end with a newline. Wrapping cells.
- A zero cell at the start; three cells per letter of the longer line, plus four.
- The tape ends empty. The pointer ends past the strings: where exactly depends on their length.
Common mistakes
- Storing the two strings one after the other. Then every comparison of two letters is a walk between them. Next to each other, it is one step.
- Counting the differences instead of setting a flag: 256 differences would wrap to "equal" on 8-bit cells.
What it costs
A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:
The figure needs JavaScript. The table below has the measured steps.
Cost as a formula, and measured
| Form | Plain steps | Optimised steps |
|---|---|---|
| Two lines from the input | grows with the letter codes | 19 + 12 per letter when the lines are equal |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Two lines from the input | first line = "tea"; second line = "tea" | 8 | 230 | 2,761 | 55 |
| Two lines from the input | first line = "tea"; second line = "ten" | 8 | 230 | 3,298 | 59 |
| Two lines from the input | first line = "tea"; second line = "teapot" | 8 | 230 | 6,082 | 88 |
Where it is used
- The idea of laying two things side by side so that one flat loop can combine them is how the chat program adds up its sums.
- The challenges: recognise a command word.
Sources
- Source: Esolang wiki: Brainfuck algorithms: the equality test and the newline loop are the wiki's; the side-by-side layout and the carried flag are our own.
Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.