The Cairo Games Vol.1 – Solutions

Below you will find the solutions to the puzzles presented in the first volume of the Cairo Games. If you are still working on solving the puzzles – major spoilers ahead!

Bastet

#########################################################################
#                             SPOILER ALERT                             #
#                                                                       #
# This is the solution to the puzzle.                                   #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################

# Program hash: 0x01ccacb5473cbcc8032bf8804eca3fc6a68a6320afc7113ba2355862895e95e2.

# This puzzle is a simple maze where you have to go from one point to another.
# In order to solve it you should first understand the encoding and draw it. Then, you should
# find the path solving it.

%builtins output

from starkware.cairo.common.alloc import alloc

# Unpacks an integer x to its bit representation, least significant bit first.
# Note that arr_size must be less than the log of field size to guarantee a unique unpacking.
func preprocess(x, arr : felt*, arr_size):
    if arr_size == 0:
        assert x = 0
        return ()
    end
    %{
        # Compute the least significant bit.
        memory[ids.arr] = ids.x % 2
    %}
    tempvar v = [arr]
    assert v = v * v
    preprocess((x - v) / 2, arr + 1, arr_size - 1)
    return ()
end

# Verifies that sol constitutes a valid path in the 10x25 pixels maze given by arr, starting from i,
# and ending at 223.
func run(sol : felt*, sol_size, arr : felt*, i):
    if sol_size == 0:
        assert i = 223
        return ()
    end

    alloc_locals
    # Verifies that i is not located on a wall of the maze.
    assert [arr + i] = 0

    local j
    tempvar value = [sol]
    if value == 0:
        # Move up.
        assert j = i - 25
    else:
        if value == 1:
            # Move right.
            assert j = i + 1
        else:
            if value == 2:
                # Move down.
                assert j = i + 25
            else:
                # Move left.
                assert j = i - 1
            end
        end
    end
    run(sol=sol + 1, sol_size=sol_size - 1, arr=arr, i=j)
    return ()
end

func main(output_ptr : felt*) -> (output_ptr : felt*):
    alloc_locals

    # The integer below is a 250-bit integers that represents the 10x25 maze.
    const VALUE = 1809251367787892036301135595905628874434260928980393026255783426015239340031
    let (local arr : felt*) = alloc()
    const ARR_SIZE = 250
    preprocess(x=VALUE, arr=arr, arr_size=ARR_SIZE)

    let (local sol : felt*) = alloc()
    local sol_size
    %{
        UP, RIGHT, DOWN, LEFT = range(4)
        START = 26
        END = 223
        lst = [RIGHT] * 11 + [DOWN] * 4 + [RIGHT] * 3 + [UP, UP, RIGHT, RIGHT, DOWN] + \
            [RIGHT] * 4 + [DOWN, DOWN, LEFT, DOWN, DOWN, RIGHT, RIGHT, RIGHT]
        ids.sol_size = len(lst)
        segments.write_arg(ids.sol, lst)

        # For readability, draw the maze.
        values = list(bin(ids.VALUE)[2:][::-1])
        values[START] = 's'
        values[END] = 'e'
        cur = START
        for x in lst[:-1]:
            cur += {UP: -25, RIGHT: 1, DOWN: 25, LEFT: -1}[x]
            values[cur] = '.'
        for i in range(10):
            print(''.join(values[i*25:(i+1) * 25]).replace('0', ' ').replace('1', u'\u2588'))
        memory[ids.output_ptr] = 0x1234
    %}
    run(sol=sol, sol_size=sol_size, arr=arr, i=26)
    return (output_ptr=output_ptr + 1)
end

Khepri

#########################################################################
#                             SPOILER ALERT                             #
#                                                                       #
# This is the solution to the puzzle.                                   #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################

# Program hash: 0x02bb25e03624218e0211798da4064586ea37958590167006bff1be82e0d99858.

# This puzzle requires you to sign on a message with the given public key.
# In theory it's not possible to find the private key given the public key, and this private
# key is required to sign the message.
# This means that the private key was not chosen in a secure way.
# The following python code enumerates over small private keys:
#
#   from starkware.crypto.signature.signature import private_to_stark_key
#
#   PUBLIC_KEY = 124221662027375191599785306371100866827147974414679244246692561282978781776
#   for priv_key in range(1, 100000):
#       if private_to_stark_key(priv_key) == PUBLIC_KEY:
#           print(priv_key)
#           break
#
# Running it reveals (within a few seconds) that the private key is indeed a very small
# number: 4711.

%builtins output pedersen ecdsa

from starkware.cairo.common.cairo_builtins import HashBuiltin, SignatureBuiltin
from starkware.cairo.common.hash import pedersen_hash
from starkware.cairo.common.signature import verify_ecdsa_signature

func main(output_ptr : felt*, pedersen_ptr : HashBuiltin*, ecdsa_ptr : SignatureBuiltin*) -> (
        output_ptr : felt*, pedersen_ptr : HashBuiltin*, ecdsa_ptr : SignatureBuiltin*):
    alloc_locals

    local your_eth_addr
    local signature_r
    local signature_s

    %{ ids.your_eth_addr = 0x1234 %}
    let (pedersen_ptr, x) = pedersen_hash(pedersen_ptr, your_eth_addr, your_eth_addr)
    %{
        PRIVATE_KEY = 4711
        from starkware.crypto.signature.signature import sign
        # Compute the signature.
        ids.signature_r, ids.signature_s = sign(ids.x, PRIVATE_KEY)
    %}
    let (ecdsa_ptr) = verify_ecdsa_signature(
        ecdsa_ptr,
        x,
        124221662027375191599785306371100866827147974414679244246692561282978781776,
        signature_r,
        signature_s)

    assert [output_ptr] = your_eth_addr

    return (output_ptr=output_ptr + 1, pedersen_ptr=pedersen_ptr, ecdsa_ptr=ecdsa_ptr)
end

Anubis

#########################################################################
#                             SPOILER ALERT                             #
#                                                                       #
# This is the solution to the puzzle.                                   #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################

# Program hash: 0x0005b19f277f97b73b8ac170fe57159274c2bbbfb65a213ecf55cd61508df973.

# This is an optimization puzzle. The puzzle defines characters as having five attributes, each of
# which can take values from 0 to 5. The puzzle starts with two characters whose attributes are
# (0, 0, 0, 0, 0), and the goal is to repeatedly select two characters to "merge" into a stronger
# character, until the goal of a (5, 5, 5, 5, 5) character is reached, within 30 steps.
#
# A solution can be found using a recursive search as follows:
#
# 1. Start with two (0, 0, 0, 0, 0) characters.
# 2. Define the "value" of a character to be the sum of its attributes.
# 3. On each step, iterate over pairs of characters and:
#   i.   Compute the new seed using the Pedersen hash.
#   ii.  Extract the values of `r` (in `merge`) from the seed.
#   iii. Compute the expected attributes of the merged character and its value.
#   iv.  Proceed with the pair that produces the most value on merge.
# 4. Backtrack as needed to back out of "dead ends" where improvement is impossible.
#
# Note that this is a theoretically infeasible computation at around 2^190 hashes naively,
# but it can be heuristically optimized by considering the latest characters (who are expected
# to be the most valuable), quickly pruning branches that turn out to produce low value, and
# other similar methods.

%builtins output pedersen range_check

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import pedersen_hash
from starkware.cairo.common.math import assert_nn_le, signed_div_rem, split_felt, unsigned_div_rem

const MAX = 1024
const BOUND = 5

struct Character:
    member strength : felt = 0
    member wisdom : felt = 1
    member beauty : felt = 2
    member courage : felt = 3
    member resolve : felt = 4
    const SIZE = 5
end

# Merges a single attribute of two characters given a seed, as follows:
# First, it extracts a number `r` between -1 and 1 from the seed.
# The merged attribute is set to be the average of the two attributes, rounded down, plus `r`.
func merge_value(range_check_ptr, a, b, seed) -> (range_check_ptr, seed, res):
    alloc_locals
    let (range_check_ptr, local seed, r) = unsigned_div_rem(range_check_ptr, seed, 3)
    let (local range_check_ptr, res, _) = signed_div_rem(
        range_check_ptr, a + b + 2 * r - 2, 2, 2 * BOUND)
    local final_res
    if res == BOUND + 1:
        assert final_res = BOUND
    else:
        if res == -1:
            assert final_res = 0
        else:
            assert final_res = res
        end
    end
    return (range_check_ptr=range_check_ptr, seed=seed, res=final_res)
end

# Merges two characters by merging each one of their attributes, extracting the
# various values of `r` from the given seed.
func merge(range_check_ptr, a : Character*, b : Character*, seed) -> (
        range_check_ptr, merged : Character*):
    alloc_locals
    let (local merged : Character*) = alloc()

    let (range_check_ptr, seed, strength) = merge_value(
        range_check_ptr, a.strength, b.strength, seed)
    assert merged.strength = strength

    let (range_check_ptr, seed, wisdom) = merge_value(range_check_ptr, a.wisdom, b.wisdom, seed)
    assert merged.wisdom = wisdom

    let (range_check_ptr, seed, beauty) = merge_value(range_check_ptr, a.beauty, b.beauty, seed)
    assert merged.beauty = beauty

    let (range_check_ptr, seed, courage) = merge_value(range_check_ptr, a.courage, b.courage, seed)
    assert merged.courage = courage

    let (range_check_ptr, seed, resolve) = merge_value(range_check_ptr, a.resolve, b.resolve, seed)
    assert merged.resolve = resolve

    return (range_check_ptr=range_check_ptr, merged=merged)
end

# Adds the new characters, expecting a hint on each one of its iterations indicating
# which two characters to merge.
# The seed given to the `merge` function is a Pedersen hash based on the previous seed and the
# indices of the characters picked.
func add_new_characters(
        pedersen_ptr : HashBuiltin*, range_check_ptr, seed, characters : Character**, n_characters,
        n_new_characters) -> (pedersen_ptr : HashBuiltin*, range_check_ptr):
    if n_new_characters == 0:
        return (pedersen_ptr=pedersen_ptr, range_check_ptr=range_check_ptr)
    end

    alloc_locals
    local i
    local j
    %{
        # Choose which characters to merge, based on the precomputed indices given below.
        ids.i, ids.j = indices.pop(0)
    %}
    let (range_check_ptr) = assert_nn_le(range_check_ptr, i, n_characters - 1)
    let (range_check_ptr) = assert_nn_le(range_check_ptr, j, n_characters - 1)
    let (range_check_ptr) = assert_nn_le(range_check_ptr, i, j - 1)

    # Compute the next seed.
    let (local pedersen_ptr : HashBuiltin*, local seed) = pedersen_hash(
        pedersen_ptr, seed, MAX * i + j)
    let (local range_check_ptr, high, low) = split_felt(range_check_ptr, seed)

    let (range_check_ptr, merged) = merge(
        range_check_ptr=range_check_ptr, a=[characters + i], b=[characters + j], seed=low)
    assert [characters + n_characters] = merged

    %{
        print(
            f'#{ids.n_characters}: {ids.merged.strength}, {ids.merged.wisdom}, '
            f'{ids.merged.beauty}, {ids.merged.courage}, {ids.merged.resolve} '
            f'(based on {ids.i, ids.j}).')
    %}
    add_new_characters(
        pedersen_ptr=pedersen_ptr,
        range_check_ptr=range_check_ptr,
        seed=seed,
        characters=characters,
        n_characters=n_characters + 1,
        n_new_characters=n_new_characters - 1)
    return (...)
end

func main(output_ptr, pedersen_ptr : HashBuiltin*, range_check_ptr) -> (
        output_ptr, pedersen_ptr : HashBuiltin*, range_check_ptr):
    alloc_locals

    let (local first : Character*) = alloc()
    assert first.strength = 0
    assert first.wisdom = 0
    assert first.beauty = 0
    assert first.courage = 0
    assert first.resolve = 0

    # Create the character array and set the first two characters' attributes to (0, 0, 0, 0, 0).
    let (local characters : Character**) = alloc()
    assert [characters] = first
    assert [characters + 1] = first

    local n_new_characters
    %{
        # A set of chosen indices that solves that puzzle, obtained as described above.
        indices = [
            (0, 1), (0, 1), (0, 1), (2, 4), (2, 4), (3, 5), (3, 7), (7, 8), (7, 9),
            (9, 10), (9, 10), (11, 12), (12, 13), (11, 13), (9, 13), (15, 16), (13, 17),
            (16, 17), (15, 19), (19, 20), (19, 20), (19, 22), (19, 23), (21, 23), (23, 24)]
        ids.n_new_characters = len(indices)
        memory[ids.output_ptr] = 0x1234
    %}

    # Limit the number of new characters to 30.
    let (range_check_ptr) = assert_nn_le(range_check_ptr, n_new_characters, 30)
    let (pedersen_ptr, range_check_ptr) = add_new_characters(
        pedersen_ptr=pedersen_ptr,
        range_check_ptr=range_check_ptr,
        seed=0,
        characters=characters,
        n_characters=2,
        n_new_characters=n_new_characters)

    # Assert that the last character's attributes are (5, 5, 5, 5, 5).
    let last_character = [characters + 1 + n_new_characters]
    assert last_character.strength = 5
    assert last_character.wisdom = 5
    assert last_character.beauty = 5
    assert last_character.courage = 5
    assert last_character.resolve = 5

    return (output_ptr=output_ptr + 1, pedersen_ptr=pedersen_ptr, range_check_ptr=range_check_ptr)
end

Ptah

#########################################################################
#                             SPOILER ALERT                             #
#                                                                       #
# This is the solution to the puzzle.                                   #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################

# Program hash: 0x0441921830d40b5be99e7a9108d43d9f50bfa3750dec33a23f70950f3c953166.

# This is a Sudoku puzzle.
# It works as follows:
# 1. Take an array of size 3 * 81.
# 2. Apply a permutation on the first 81 values and put the result in the next 81 values.
# 3. Apply the same permutation again and put the result in the last 81 values of the array.
# 4. Check that each block of 9 consecutive cells in the array is a permutation of the values
#    1, 2, ..., 9 (where each value appears exactly once).
#    In this manner, the first batch of 81 values checks the rows of the Sudoku table, the next
#    checks the 3x3 squares and the last checks the columns.
#
# In order to solve the puzzle you should first translate the known entries, which are given
# as indices of the long array, to their actual positions in the 9x9 Sudoku.

%builtins output range_check

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.math import assert_nn_le

# Tests that [vals + 0], ..., [vals + 8] are a permutation of 1, 2, ..., 9.
func work(range_check_ptr, vals : felt*, i : felt) -> (range_check_ptr):
    if i == 0:
        return (range_check_ptr=range_check_ptr)
    end

    alloc_locals
    local j
    %{
        for j in range(9):
            if memory[ids.vals + j] == ids.i:
                ids.j = j
    %}
    let (range_check_ptr) = assert_nn_le(range_check_ptr, j, 8)
    assert [vals + j] = i

    work(range_check_ptr, vals, i - 1)
    return (...)
end

# Tests that each of the first i blocks of 9 consecutive cells is a permutation of 1, 2, ..., 9.
func work2(range_check_ptr, vals : felt*, i : felt) -> (range_check_ptr):
    if i == 0:
        return (range_check_ptr=range_check_ptr)
    end

    let (range_check_ptr) = work(range_check_ptr, vals, 9)
    work2(range_check_ptr, vals + 9, i - 1)
    return (...)
end

# Applies a permutation on the input. Let abcd be the ternary representation (a, b, c, d < 3)
# of an index in the range [0, 81), then output[abcd] = input[dabc].
func copy(input : felt*, output : felt*, x):
    if x == 0:
        return ()
    end

    assert [output] = [input]
    assert [output + 1] = [input + 27]
    assert [output + 2] = [input + 54]

    copy(input + 1, output + 3, x - 1)
    return ()
end

func main(output_ptr : felt*, range_check_ptr) -> (output_ptr : felt*, range_check_ptr):
    alloc_locals

    let (local vals : felt*) = alloc()

    %{
        v = [
            [4,1,5, 2,3,9, 8,6,7],
            [7,8,2, 6,1,4, 5,9,3],
            [3,9,6, 5,7,8, 2,4,1],

            [2,4,9, 3,6,5, 7,1,8],
            [1,6,3, 8,9,7, 4,2,5],
            [5,7,8, 4,2,1, 9,3,6],

            [8,5,1, 9,4,3, 6,7,2],
            [9,2,7, 1,5,6, 3,8,4],
            [6,3,4, 7,8,2, 1,5,9],
        ]
        # Reorder the rows to prepare the first batch of 81 values.
        v = [*v[0], *v[3], *v[6], *v[1], *v[4], *v[7], *v[2], *v[5], *v[8]]
        segments.write_arg(ids.vals, v)
        memory[ids.output_ptr] = 0x1234
    %}
    assert [vals + 0] = 4
    assert [vals + 20] = 1
    assert [vals + 27] = 7
    assert [vals + 34] = 9
    assert [vals + 35] = 3
    assert [vals + 37] = 6
    assert [vals + 45] = 9
    assert [vals + 56] = 6
    assert [vals + 75] = 7
    assert [vals + 85] = 8
    assert [vals + 101] = 2
    assert [vals + 105] = 7
    assert [vals + 107] = 1
    assert [vals + 123] = 5
    assert [vals + 130] = 2
    assert [vals + 137] = 6
    assert [vals + 139] = 2
    assert [vals + 153] = 6
    assert [vals + 161] = 9
    assert [vals + 164] = 8
    assert [vals + 190] = 3
    assert [vals + 196] = 4
    assert [vals + 207] = 9
    assert [vals + 214] = 1
    assert [vals + 230] = 8
    assert [vals + 239] = 4

    copy(vals, vals + 81, 27)
    copy(vals + 81, vals + 162, 27)

    let (range_check_ptr) = work2(range_check_ptr, vals, 27)

    return (output_ptr=output_ptr + 1, range_check_ptr=range_check_ptr)
end

Anuket

#########################################################################
#                             SPOILER ALERT                             #
#                                                                       #
# This is the solution to the puzzle.                                   #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################

# Program hash: 0x001626f02c7ea1a6974ae3ab485216f148fe0255dd3132f862ef068b8c12a2bd.

# This puzzle simulates a Turing Machine.
# The objective is: find a Turing Machine with no more than 3 states and an alphabet of size 7
# (0, 1, ..., 6) that given the initial tape ...0001000... (where the head points to the 1)
# outputs the string 1212212222122222222122222222222222221... such that the number of 2s between two
# consecutive 1s is doubled every time (1, 2, 4, 8, ...).
# In fact, the code below only tests that after a certain amount of steps the tape reaches:
#   121221222212222222212222222222222222.

%builtins output range_check

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.math import assert_nn_le
from starkware.cairo.common.registers import get_fp_and_pc

# The maximal size of the alphabet.
const VALUE_BOUND = 7
# The number of states.
const AMOUNT = 3

# A linked list representing one side of the tape.
struct List:
    member head : felt = 0
    member tail : List* = 1
    const SIZE = 2
end

# A possible action of the machine where:
#   typ - 0 for moving left, 1 for moving right.
#   value - the value to write at the location of the head.
#   next - the next state (a list of 7 possible actions, one for each alphabet symbol).
struct Action:
    member typ : felt = 0
    member value : felt = 1
    member next : Action* = 2
    const SIZE = 3
end

# The entire state of the machine.
struct Context:
    # The value at the position of the head.
    member value : felt = 0
    # The tape to the left of the head.
    member list1 : List* = 1
    # The tape to the right of the head.
    member list2 : List* = 2
    # The current state (a list of 7 possible actions, one for each alphabet symbol).
    member state : Action* = 3
    const SIZE = 4
end

# Apply a "Move left" action (write action.value at the position of the head, and moves left).
func action0(context : Context*, action : Action*) -> (context : Context*):
    alloc_locals
    local new_list2 : List
    local new_context : Context
    let (__fp__, _) = get_fp_and_pc()

    assert new_list2.tail = context.list2
    assert new_list2.head = action.value
    assert new_context.list2 = &new_list2
    tempvar list1 = context.list1
    assert new_context.value = list1.head
    assert new_context.list1 = list1.tail
    assert new_context.state = action.next
    return (context=&new_context)
end

# Same as action0, except that it moves right.
func action1(context : Context*, action : Action*) -> (context : Context*):
    alloc_locals
    local new_list1 : List
    local new_context : Context
    let (__fp__, _) = get_fp_and_pc()

    assert new_list1.tail = context.list1
    assert new_list1.head = action.value
    assert new_context.list1 = &new_list1
    tempvar list2 = context.list2
    assert new_context.value = list2.head
    assert new_context.list2 = list2.tail
    assert new_context.state = action.next
    return (context=&new_context)
end

# Runs 'length' steps of the machine.
func run(context : Context*, length : felt) -> (context : Context*):
    if length == 0:
        return (context=context)
    end

    %{
        # Change to True to show the intermediate states of the tape.
        if False:
            # Print the tape.
            res = str(ids.context.value)
            x = ids.context.list1
            for i in range(10):
                res = str(memory[x]) + res
                x = memory[x + 1]
            x = ids.context.list2
            for i in range(10):
                res += str(memory[x])
                x = memory[x + 1]
            print(res)
            # Print the head position with the state.
            print(' ' * 10 + str(ids.context.state.offset // (ids.VALUE_BOUND * ids.Action.SIZE)))
    %}
    tempvar action = context.state + Action.SIZE * context.value
    if action.typ == 0:
        let (context) = action0(context=context, action=action)
    else:
        let (context) = action1(context=context, action=action)
    end

    run(context=context, length=length - 1)
    return (...)
end

# Validates that the first 'length' values in 'list' have values encoded by 'expected'.
# The encoding is defined by taking the binary representation of 'expected' and adding one to each
# binary digit (moving 0 to 1 and 1 to 2).
func validate(list : List*, expected : felt, length : felt):
    if length == 0:
        assert expected = 0
        return ()
    end

    alloc_locals
    tempvar z = list.head - 1
    assert z = z * z
    validate(list=list.tail, expected=(expected - z) / 2, length=length - 1)
    return ()
end

# Validates that the machine definition is valid.
func check_actions(range_check_ptr, all_actions : Action*, n_actions : felt, i : felt) -> (
        range_check_ptr):
    if i == 0:
        return (range_check_ptr=range_check_ptr)
    end

    let i = i - 1

    tempvar action = all_actions + i * Action.SIZE
    let (range_check_ptr) = assert_nn_le(range_check_ptr, action.value, VALUE_BOUND - 1)
    let (range_check_ptr) = assert_nn_le(
        range_check_ptr, (action.next - all_actions) / (VALUE_BOUND * Action.SIZE), AMOUNT - 1)

    check_actions(
        range_check_ptr=range_check_ptr, all_actions=all_actions, n_actions=n_actions, i=i)
    return (...)
end

func main(output_ptr, range_check_ptr) -> (output_ptr, range_check_ptr):
    alloc_locals
    local all_actions : Action*
    %{
        MOVE_LEFT, MOVE_RIGHT = range(2)
        ids.all_actions = segments.add()
        # Give names to the three states.
        NEXT_ITERATION, WRITE4, SEARCH_NEXT = [
            ids.all_actions.address_ + i * ids.Action.SIZE * ids.VALUE_BOUND for i in range(3)]
        DONT_CARE = 0, 0, NEXT_ITERATION
        # The transition table. Each state is represented by 7 actions, one for each alphabet
        # symbol. Each action is represented by a triple (direction, value, next_state).
        segments.write_arg(ids.all_actions.address_, [
            # State: NEXT_ITERATION (replaces "3" with "1" and "4" with "2" for the next iteration).
            MOVE_LEFT, 3, SEARCH_NEXT,
            MOVE_RIGHT, 1, SEARCH_NEXT,  # Initialization.
            *DONT_CARE,
            MOVE_RIGHT, 1, NEXT_ITERATION,  # Replace "3" with "1".
            MOVE_RIGHT, 2, NEXT_ITERATION,  # Replace "4" with "2".
            *DONT_CARE,
            *DONT_CARE,

            # State: WRITE4 (writes "4" at the next empty slot).
            MOVE_RIGHT, 4, SEARCH_NEXT,  # Write "4" and move to SEARCH_NEXT.
            *DONT_CARE,
            *DONT_CARE,
            MOVE_RIGHT, 3, WRITE4,  # Ignore.
            MOVE_RIGHT, 4, WRITE4,  # Ignore.
            *DONT_CARE,
            *DONT_CARE,

            # State: SEARCH_NEXT (searches for "2" and replaces it with "4").
            MOVE_LEFT, 4, SEARCH_NEXT,  # Write the second 4 and then start the search.
            MOVE_RIGHT, 1, NEXT_ITERATION,  # No more ones, move to NEXT_ITERATION.
            MOVE_RIGHT, 4, WRITE4,  # Found "2", move to WRITE4.
            MOVE_LEFT, 3, SEARCH_NEXT,  # Ignore.
            MOVE_LEFT, 4, SEARCH_NEXT,  # Ignore.
            *DONT_CARE,
            *DONT_CARE,
        ])
    %}

    let n_actions = VALUE_BOUND * AMOUNT
    let (range_check_ptr) = check_actions(
        range_check_ptr=range_check_ptr, all_actions=all_actions, n_actions=n_actions, i=n_actions)

    # An infinite list of zeros.
    let (local list : List*) = alloc()
    assert list.tail = list
    assert list.head = 0

    # The initial tape is:
    # ...00010000...
    #       ^
    # and the initial state is the first state.
    let (local context : Context*) = alloc()
    assert context.list1 = list
    assert context.list2 = list
    assert context.value = 1
    assert context.state = all_actions

    local length
    %{ ids.length = 376 %}
    let (local range_check_ptr) = assert_nn_le(range_check_ptr, length, 600)
    let (context) = run(context, length)
    %{
        res = ''
        x = ids.context.list1
        for i in range(36):
            res += str(memory[x])
            x = memory[x + 1]
        print(f'Result: {res[::-1]}')

        memory[ids.output_ptr] = 0x1234
    %}
    # Check that the final result is 121221222212222222212222222222222222 (the binary representation
    # of 24662441983 is 0b010110111101111111101111111111111111).
    validate(context.list1, 24662441983, 36)

    return (output_ptr=output_ptr + 1, range_check_ptr=range_check_ptr)
end