The Cairo Games Vol. 2 – Solutions

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

Nu

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

# Program hash: 0x0603aa817aa054d58beb522a1e17286e92afbce15009893cbd81d22b7bdc3f56.

# Prove that the prime number 17 is in fact composite!

# Well, 17 is not really a composite number, so there must be a bug in the program.
# The bug turns out to be an integer overflow that occurs when x and y are multiplied.
# assert_nn() implies that both x and y are less than 2^128.
# On the other hand the product is computed modulo the field's size,
# which is P=2^251 + 17*2^192 + 1.
# Since this number is less than 2^128 * 2^128, we have a potential overflow.
# Therefore, if the product x*y is in fact 17 + P (rather than 17), the code will succeed.
#
# Computing the factorization of 17 + P (which *is* composite) gives:
#   2 * 11 * 137659 * 1991573 * 109785357751 * 576309240307649 *
#   9482118669354530065856070474433091563.
# Splitting it to:
#   x = 2 * 9482118669354530065856070474433091563,
#   y = 11 * 137659 * 1991573 * 109785357751 * 576309240307649,
# solves the puzzle.
#
# When you write real Cairo code, you should make sure computations do not overflow.
# In this example, a simple way to achieve it is to enforce a stricter bound on
# x and y. For example, that both of them are less than 2^64.

%builtins output range_check

from starkware.cairo.common.math import assert_nn

func main(output_ptr : felt*, range_check_ptr) -> (output_ptr : felt*, range_check_ptr):
    alloc_locals
    local x
    local y
    %{
        ids.x = 2 * 9482118669354530065856070474433091563
        ids.y = 11 * 137659 * 1991573 * 109785357751 * 576309240307649
        # Output the user's public key.
        memory[ids.output_ptr] = 0x1234
    %}
    assert_nn{range_check_ptr=range_check_ptr}(x - 2)
    assert_nn{range_check_ptr=range_check_ptr}(y - 2)
    assert x * y = 17
    return (output_ptr=output_ptr + 1, range_check_ptr=range_check_ptr)
end

Pakhet

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

# Program hash: 0x07b60b3745d3c816553bc8b7ac9410b2fc4441d5cd694e5f61226455092a98ce.

# In this puzzle you have to find a Hamiltonian cycle in a graph.
# The graph has 18 vertices and it is encoded using its (symmetric) adjacency matrix.
# In order to find the Hamiltonian cycle you can start by drawing the graph.
# For example, you can use networkx and matplotlib:
#
#   import networkx
#   import matplotlib.pyplot as plt
#
#   encoding = 904711815024524574246580775193158565348810842345109828206640 + \
#       (1662189419663012728075783146332749833 << 200)
#   graph = networkx.Graph()
#
#   for u in range(18):
#       for v in range(u):
#           if encoding & (1 << (18 * u + v)) != 0:
#               graph.add_edge(u, v)
#   networkx.draw_planar(graph, with_labels=True)
#   plt.show()
#
# Then, find vertices of the form x--y--z where y is connected *only* to x and z: the
# edges x--y and y--z must be in the Hamiltonian cycle.

%builtins output range_check

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

const N_VERTICES = 18

# 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
    %{ memory[ids.arr] = ids.x % 2 %}
    tempvar v = [arr]
    assert v = v * v
    preprocess((x - v) / 2, arr + 1, arr_size - 1)
    return ()
end

# Checks that 'path' (a list of n+1 vertices) is a valid path in the graph.
# For each i < n (note that the last one is excluded), writes aux[path[i]] = len(path) - i.
# This ensures that each vertex appears at most once.
func check{range_check_ptr}(path : felt*, aux : felt*, graph : felt*, n : felt):
    if n == 0:
        return ()
    end

    tempvar cur = [path]
    # Make sure the current vertex index is valid, and set aux[cur] = n to make sure each vertex
    # appears at most once.
    assert_nn_le(cur, N_VERTICES - 1)
    assert [aux + cur] = n

    tempvar next = [path + 1]
    assert [graph + cur * N_VERTICES + next] = 1

    return check(path=path + 1, aux=aux, graph=graph, n=n - 1)
end

func main{output_ptr, range_check_ptr}():
    alloc_locals
    # Unpack the graph's encoding.
    let (local graph : felt*) = alloc()
    preprocess(904711815024524574246580775193158565348810842345109828206640, graph, 200)
    preprocess(1662189419663012728075783146332749833, graph + 200, N_VERTICES * N_VERTICES - 200)

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

    %{
        segments.write_arg(
            ids.path, [12, 13, 5, 0, 4, 6, 7, 1, 11, 2, 15, 3, 8, 9, 10, 16, 14, 17, 12])
        memory[ids.output_ptr] = 0x1234
    %}
    # Make sure it's a cycle - the first and last vertices must be the same.
    assert [path] = [path + N_VERTICES]

    let (local aux : felt*) = alloc()
    # Check that path forms a Hamiltonian cycle.
    # Since [path] = [path + N_VERTICES] it is a cycle.
    # check() verifies that each vertex appears at most once.
    # Since the length of the path is the same as the number of vertices,
    # we obtain that each vertex appears *exactly* once.
    check(path, aux=aux, graph=graph, n=N_VERTICES)

    let output_ptr = output_ptr + 1
    return ()
end

Seth

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

# Program hash: 0x077bb8982750b5732e37570e20d02d60bc3bad6f9fc413d06a1f95f15dcd6ef0.

# This puzzle demonstrates a wrong use of the Fiat-Shamir heuristic.
# In this puzzle you should provide a sequence of 100 values, which, when sampled "randomly",
# should be 0 for 50 samples and hash(x, x) for the other 50 samples.
# If the samples were truly random, this would have been infeasible.
# In this implementation (which incorrectly uses the Fiat-Shamir heuristic),
# you can control the randomness between the samples and thus make the test pass.

%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 hash2
from starkware.cairo.common.hash_chain import hash_chain
from starkware.cairo.common.math import split_felt, unsigned_div_rem

const SIZE = 100
const COUNT = 100

func check{pedersen_ptr : HashBuiltin*, range_check_ptr}(items : felt*, seed, n, type):
    if n == 0:
        return ()
    end

    alloc_locals

    let (high, low) = split_felt(seed)
    let (_, r) = unsigned_div_rem(low, SIZE)

    local preimage
    %{
        if ids.type == 0:
            # preimage is not really used in this case, but it's taken into the seed hash.
            # Thus, you can pick a value that will make the next two samples pass.
            for preimage in range(100):
                # Predict the next two values.
                next_seed = pedersen_hash(pedersen_hash(ids.seed, preimage), 0)
                next_value = (next_seed % 2**128) % ids.SIZE
                # Make sure it's in the second half of the array. Otherwise, try a different value.
                if next_value < ids.SIZE // 2:
                    continue
                next_next_seed = pedersen_hash(pedersen_hash(next_seed, 0), H)
                next_next_value = (next_next_seed % 2**128) % ids.SIZE
                # Make sure it's in the first half of the array. Otherwise, try a different value.
                if next_next_value >= ids.SIZE // 2:
                    continue
                break
            else:
                raise Exception('Failed')
        else:
            preimage = 0
        ids.preimage = preimage
    %}
    let (image) = hash2{hash_ptr=pedersen_ptr}(preimage, preimage)

    tempvar item = [items + r]
    if type == 0:
        assert item = 0
    else:
        assert item = image
    end
    let (seed) = hash2{hash_ptr=pedersen_ptr}(seed, preimage)
    let (seed) = hash2{hash_ptr=pedersen_ptr}(seed, item)

    return check(items=items, seed=seed, n=n - 1, type=1 - type)
end

func main{output_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals
    let (local data : felt*) = alloc()
    assert [data] = SIZE
    %{
        # Create an array where the first half is zeros and the second is h(0, 0).
        from starkware.crypto.signature.signature import pedersen_hash
        H = pedersen_hash(0, 0)
        segments.write_arg(
            ids.data + 1, [0] * (ids.SIZE // 2) + [H] * (ids.SIZE // 2))
        memory[ids.output_ptr] = 0x1234
    %}

    # Compute the initial seed, by taking the hash of the array.
    let (seed) = hash_chain{hash_ptr=pedersen_ptr}(data)

    check(items=data + 1, seed=seed, n=COUNT, type=0)
    let output_ptr = output_ptr + 1
    return ()
end

Montu

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

# Program hash: 0x00a4ca077b0c3f81cc3c813af6ebf16fb83f2bbf96068c5cbe5b4f9e73febfa8.

# This puzzle is about Reed–Solomon codes and the FRI algorithm. FRI gets a sequence of N field
# elements a_i and checks whether there exists a polynomial f(x) of some bounded degree such that
#   a_i = f(g^i)  (where g is an N-th root of unity in the field).
#
# For those of you familiar with the FFT algorithm, FRI is very similar except that it uses
# randomness to reduce an instance of size N to *one* instance of size N/2 (rather than two such
# instances in FFT). This means the running time is O(N), rather than O(N * log N).
#
# The puzzle goes as follows: you're given an array of 8 numbers, and you should modify 3 of them
# so that the resulting sequence will be the evaluation of a polynomial of degree less than 4.
# You can use math programs, such as sage, to enumerate over the 56 options of which elements
# should be modified, until you find one where the 5 other values lie on the required polynomial.
# Then you evaluate it on the 3 wrong values. (This is in fact error correction in a
# Reed–Solomon code.)

%builtins output pedersen

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash_state import HashState, hash_finalize, hash_init, hash_update

func compute_next_layer(
        input : felt*, output : felt*, length : felt, alpha : felt, x : felt, g : felt):
    tempvar a = [input]
    tempvar b = [input + length]
    assert [output] = (a + b) / 2 + alpha * (a - b) / (2 * x)
    if x * g == -1:
        return ()
    end
    return compute_next_layer(
        input=input + 1, output=output + 1, length=length, alpha=alpha, x=x * g, g=g)
end

# Verifies that there exists a polynomial f(x) of degree less than length/2 where input[i] = f(g^i).
# Implemented using FRI.
func verify{hash_ptr : HashBuiltin*, hash_state_ptr : HashState*}(
        input : felt*, length : felt, g : felt):
    alloc_locals

    if length == 2:
        # If length is 2, the degree should be less than 1, which means f(x) is a constant
        # polynomial. Just check that the two values are indeed the same.
        assert [input] = [input + 1]
        return ()
    end

    # Compute alpha.
    let (hash_state_ptr) = hash_update(
        hash_state_ptr=hash_state_ptr, data_ptr=input, data_length=length)
    let (alpha) = hash_finalize(hash_state_ptr=hash_state_ptr)
    local hash_ptr : HashBuiltin* = hash_ptr
    local hash_state_ptr : HashState* = hash_state_ptr

    let (local next_layer : felt*) = alloc()
    compute_next_layer(input=input, output=next_layer, length=length / 2, alpha=alpha, x=1, g=g)

    return verify(input=next_layer, length=length / 2, g=g * g)
end

# Counts the number of differences between the input and the output arrays.
func compare(input : felt*, output : felt*, length : felt) -> (diff : felt):
    if length == 0:
        return (diff=0)
    end

    let (diff) = compare(input=input + 1, output=output + 1, length=length - 1)
    if [input] == [output]:
        return (diff=diff)
    else:
        return (diff=diff + 1)
    end
end

func main{output_ptr : felt*, pedersen_ptr : HashBuiltin*}():
    alloc_locals

    const LENGTH = 8
    const G = 2804690217475462062143361339624939640984649667966511418446363596075299761851

    let (input) = alloc()

    # The input sequence.
    assert [input] = (
        2760163267763136926307712447289333015931143661720962520709479367174330989984)
    assert [input + 1] = (
        620345510678501588305616341951109830750033614090225920347864657883483407165)
    assert [input + 2] = (
        3181959697776337130511545402257206919343979808211484609881516936335798865334)
    assert [input + 3] = (
        1830152343057623004121086982129442788610913917055044983876581372969127139593)
    assert [input + 4] = (
        3553572895696142252358926310847411672039878792883770142922873977486098926969)
    assert [input + 5] = (
        2462248735454554379268841047904517280521029943202779759148500485193601548624)
    assert [input + 6] = (
        792090413233267968557021563731724001464889355006703125688313681478453789157)
    assert [input + 7] = (
        1348005446214778757482455457529115254152067928062775094282398020688141612139)

    let (local modified_input) = alloc()

    %{
        values = [memory[ids.input + i] for i in range(8)]
        # Modify the three wrong values.
        values[0] = 2832196451828398372049458809620220651104433024139451345189664845961660092224
        values[1] = 2973895000156339190100688610451105694809999170219600703266872401149050581336
        values[6] = 2665075268248548789750464358384411881228826548637091142553388576352235017646
        segments.write_arg(ids.modified_input, values)

        memory[ids.output_ptr] = 0x1234
    %}

    # Checks that exactly 3 values were modified.
    let (diff) = compare(input=input, output=modified_input, length=LENGTH)
    assert diff = 3

    let (hash_state_ptr) = hash_init()

    verify{hash_ptr=pedersen_ptr, hash_state_ptr=hash_state_ptr}(
        input=modified_input, length=LENGTH, g=G)

    let output_ptr = output_ptr + 1
    return ()
end

Amun

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

# Program hash: 0x03a90efd79e07518a02ccdfc0ad37151143827d32ba4a90f284f37e6b040fbe0.

# This is a Rubik's 3x3x3 cube.
# To solve it you should find the initial state and identify the possible moves (which are
# U, R, F, L, B, D, representing the faces of the cube - Up, Right, Front, Left, Back and Down,
# respectively).

%builtins output pedersen range_check

from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.dict_access import DictAccess
from starkware.cairo.common.hash_chain import hash_chain
from starkware.cairo.common.math import assert_nn_le
from starkware.cairo.common.registers import get_fp_and_pc
from starkware.cairo.common.squash_dict import squash_dict

# Describes the six permutations U, R, F, L, B, D according to their action on the stickers.
# Each permutation is represented as 5 cycles of 4 stickers each (note that rotating a face
# by 90 degrees, changes 20 stickers, and the cycles are all of length 4).
# The stickers are ordered as follows: all the stickers on U, then on L, F, R, B, and D,
# where the 8 stickers of each face (center excluded) are ordered clockwise.
func get_data() -> (res : felt*):
    alloc_locals
    # Up.
    local a0 = 0
    local a = 2
    local a = 4
    local a = 6
    local a = 1
    local a = 3
    local a = 5
    local a = 7
    local a = 8
    local a = 32
    local a = 24
    local a = 16
    local a = 9
    local a = 33
    local a = 25
    local a = 17
    local a = 10
    local a = 34
    local a = 26
    local a = 18
    # Right.
    local a = 24
    local a = 26
    local a = 28
    local a = 30
    local a = 25
    local a = 27
    local a = 29
    local a = 31
    local a = 4
    local a = 32
    local a = 44
    local a = 20
    local a = 3
    local a = 39
    local a = 43
    local a = 19
    local a = 2
    local a = 38
    local a = 42
    local a = 18
    # Front.
    local a = 16
    local a = 18
    local a = 20
    local a = 22
    local a = 17
    local a = 19
    local a = 21
    local a = 23
    local a = 6
    local a = 24
    local a = 42
    local a = 12
    local a = 5
    local a = 31
    local a = 41
    local a = 11
    local a = 4
    local a = 30
    local a = 40
    local a = 10
    # Left.
    local a = 8
    local a = 10
    local a = 12
    local a = 14
    local a = 9
    local a = 11
    local a = 13
    local a = 15
    local a = 0
    local a = 16
    local a = 40
    local a = 36
    local a = 7
    local a = 23
    local a = 47
    local a = 35
    local a = 6
    local a = 22
    local a = 46
    local a = 34
    # Back.
    local a = 32
    local a = 34
    local a = 36
    local a = 38
    local a = 33
    local a = 35
    local a = 37
    local a = 39
    local a = 2
    local a = 8
    local a = 46
    local a = 28
    local a = 1
    local a = 15
    local a = 45
    local a = 27
    local a = 0
    local a = 14
    local a = 44
    local a = 26
    # Down.
    local a = 40
    local a = 42
    local a = 44
    local a = 46
    local a = 41
    local a = 43
    local a = 45
    local a = 47
    local a = 22
    local a = 30
    local a = 38
    local a = 14
    local a = 21
    local a = 29
    local a = 37
    local a = 13
    local a = 20
    local a = 28
    local a = 36
    local a = 12
    let (__fp__, _) = get_fp_and_pc()
    return (res=&a0)
end

# Gets a cycle of 4 stickers and applies it on the state dictionary.
func cycle{state : DictAccess*}(values : felt*):
    let state0 = state
    let state1 = state0 + DictAccess.SIZE
    let state2 = state1 + DictAccess.SIZE
    let state3 = state2 + DictAccess.SIZE
    assert state0.key = [values + 0]
    assert state1.key = [values + 1]
    assert state2.key = [values + 2]
    assert state3.key = [values + 3]
    %{
        ids.state0.prev_value = arr[ids.state0.key]
        ids.state1.prev_value = arr[ids.state1.key]
        ids.state2.prev_value = arr[ids.state2.key]
        ids.state3.prev_value = arr[ids.state3.key]
    %}
    assert state0.new_value = state3.prev_value
    assert state1.new_value = state0.prev_value
    assert state2.new_value = state1.prev_value
    assert state3.new_value = state2.prev_value
    let state = state + 4 * DictAccess.SIZE
    %{
        arr[ids.state0.key] = ids.state0.new_value
        arr[ids.state1.key] = ids.state1.new_value
        arr[ids.state2.key] = ids.state2.new_value
        arr[ids.state3.key] = ids.state3.new_value
    %}
    return ()
end

# Executes the solution on the state dictionary.
func run{range_check_ptr, state : DictAccess*}(data : felt*, sol : felt*, sol_size : felt):
    if sol_size == 0:
        return ()
    end
    tempvar x = [sol]
    assert_nn_le(x, 5)
    cycle(data + 20 * x)
    cycle(data + 20 * x + 4)
    cycle(data + 20 * x + 8)
    cycle(data + 20 * x + 12)
    cycle(data + 20 * x + 16)

    run(data=data, sol=sol + 1, sol_size=sol_size - 1)
    return ()
end

# Returns the initial state of the cube.
func get_initial_value{hash_ptr : HashBuiltin*}() -> (initial_value : felt*):
    alloc_locals
    let (local initial_value : felt*) = alloc()
    assert [initial_value] = 48
    %{ segments.write_arg(ids.initial_value + 1, initial_state) %}

    # This is the hash of the full state of the cube. It's the last thing to look at.
    let (res) = hash_chain(initial_value)
    assert res = 402684044838294963951952172461450293510735826065192598384325922359699836469

    # The state is encoded using various hash chains on slices of the state.
    # Each hash chain starts with its length (excluding the length item).
    # For example, [2, 2, 5] where 2 is the length of [2, 5].
    # Since we know that all the values should be in the range 0, 1, ..., 5 we can enumerate
    # over all options and compute the preimage of the hashes below.
    # For example hash_chain([2, 2, 5]) is pedersen_hash(2, pedersen_hash(2, 5)) =
    # 1501038259288321437961590173137394957125779122158200548115283728521438213428,
    # which appears below.
    #
    # Not all the values are revealed this way. We are left with 7 unknown numbers.
    # Since we know that each number in the range 0, 1, ..., 5 appears exactly 8 times,
    # we know that the missing numbers are 0, 1, 1, 2, 3, 3, 5.
    # We enumerate on all possible options until we get the final hash written above.
    let (res) = hash_chain(initial_value + 1)
    assert res = 1508108551069464286813785297355641266663485599320848393798932455588476865295

    let (res) = hash_chain(initial_value + 7)
    assert res = 2245701625176425331085101334837624242646502129018701371434984384296915870715

    let (res) = hash_chain(initial_value + 12)
    assert res = 3560520899812162122215526869789497390123010766571927682749531967294685134040

    let (res) = hash_chain(initial_value + 18)
    assert res = 196997208112053944281778155212956924860955084720008751336605214240056455402

    let (res) = hash_chain(initial_value + 24)
    assert res = 1035226353110224801512289478587695122129015832153304072590365512606504328818

    let (res) = hash_chain(initial_value + 30)
    assert res = 1501038259288321437961590173137394957125779122158200548115283728521438213428

    let (res) = hash_chain(initial_value + 34)
    assert res = 3537881782324467737440957567711773328493014027685577879465936840743865613662

    let (res) = hash_chain(initial_value + 39)
    assert res = 1039623306816876893268944011668782810398555904667703809415056949499773381189

    let (res) = hash_chain(initial_value + 42)
    assert res = 2508528289207660435870821551803296739495662639464901004905339054353214007301

    return (initial_value=initial_value + 1)
end

# Verifies that we obtained a solved cube.
func verify(squashed_dict : felt*, initial_value : felt*, n):
    if n == 6:
        return ()
    end

    assert [squashed_dict + 0] = n * 8
    assert [squashed_dict + 1] = [initial_value]
    assert [squashed_dict + 2] = n

    assert [squashed_dict + 3] = n * 8 + 1
    assert [squashed_dict + 4] = [initial_value + 1]
    assert [squashed_dict + 5] = n

    assert [squashed_dict + 6] = n * 8 + 2
    assert [squashed_dict + 7] = [initial_value + 2]
    assert [squashed_dict + 8] = n

    assert [squashed_dict + 9] = n * 8 + 3
    assert [squashed_dict + 10] = [initial_value + 3]
    assert [squashed_dict + 11] = n

    assert [squashed_dict + 12] = n * 8 + 4
    assert [squashed_dict + 13] = [initial_value + 4]
    assert [squashed_dict + 14] = n

    assert [squashed_dict + 15] = n * 8 + 5
    assert [squashed_dict + 16] = [initial_value + 5]
    assert [squashed_dict + 17] = n

    assert [squashed_dict + 18] = n * 8 + 6
    assert [squashed_dict + 19] = [initial_value + 6]
    assert [squashed_dict + 20] = n

    assert [squashed_dict + 21] = n * 8 + 7
    assert [squashed_dict + 22] = [initial_value + 7]
    assert [squashed_dict + 23] = n
    verify(squashed_dict=squashed_dict + 24, initial_value=initial_value + 8, n=n + 1)
    return ()
end

func main{output_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals
    let (local data : felt*) = get_data()
    let (local sol : felt*) = alloc()
    local sol_size
    %{
        memory[ids.output_ptr] = 0x1234
        # Prepare the initial state.
        arr = [
            5, 0, 0, 3, 3, 1, 4, 0,
            4, 1, 0, 4, 0, 5, 4, 2,
            3, 4, 0, 1, 5, 5, 1, 3,
            2, 2, 1, 0, 1, 2, 2, 5,
            2, 4, 1, 1, 3, 2, 2, 3,
            4, 4, 3, 0, 5, 5, 5, 3,
        ]
        initial_state = list(arr)
        rotations = {'U': 0, 'R': 1, 'F': 2, 'L': 3, 'B': 4, 'D': 5}
        solution = 'LULLLUUFFFDDDFFBBBUUULLLFFUUUDDDLLUBBUBBRRLL'
        ids.sol_size = len(solution)
        segments.write_arg(ids.sol, [rotations[x] for x in solution])
    %}

    let (state : DictAccess*) = alloc()
    local state_start : DictAccess* = state

    run{state=state}(data, sol, sol_size)

    let (local squashed_dict : DictAccess*) = alloc()
    let (squashed_dict_end) = squash_dict(
        dict_accesses=state_start, dict_accesses_end=state, squashed_dict=squashed_dict)
    assert squashed_dict_end = squashed_dict + DictAccess.SIZE * 48
    local range_check_ptr = range_check_ptr

    let (initial_value) = get_initial_value{hash_ptr=pedersen_ptr}()
    local pedersen_ptr : HashBuiltin* = pedersen_ptr
    verify(squashed_dict=squashed_dict, initial_value=initial_value, n=0)

    let output_ptr = output_ptr + 1
    return ()
end