NEWTON

NEWTON

# How to create Structs in Cairo Lang for StarkNet?

3 months ago

77

views

0

Hello! This is day 12 of the 17 days of the Cairo Challenge. And I have no idea how to solve the playground exercise “Structs. Perhaps you can help me?

``````// In this challenge you're going to implement a stack using a linked list.
//
// Add the missing code so that main() runs successfully.

from starkware.cairo.common.registers import get_fp_and_pc

struct Node {
// A pointer to the next node in the stack.
next: Node*,

// The value of the node.
value: felt,

// The number of elements in the stack.
size: felt,
}

// Returns an empty stack.
func empty_stack() -> (stack: Node*) {
alloc_locals;
local new_node: Node;
assert new_node.next = cast(0, Node*);
assert new_node.value = 0;
assert new_node.size = 0;

// The usage of get_fp_and_pc() here is necessary in order
// to access the address of a local variable (&new_node).
let (local __fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}

// Adds a node to the top of the stack.
// Returns the updated stack (since Cairo is immutable, you can still use the
// old copy of the stack).
func push(stack: Node*, value: felt) -> (stack: Node*) {
alloc_locals;
local new_node: Node;
// Fix and uncomment below.
// assert new_node.next = ...
// assert new_node.value = ...
// assert new_node.size = ...

let (__fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}

// Removes the top element of the stack.
// Returns the updated stack and the element that was removed.
func pop(stack: Node*) -> (stack: Node*, value: felt) {
return (stack=stack.next, value=stack.value);
}

// Returns the value of the n-th element from the top of the stack.
func stack_at(stack: Node*, n: felt) -> (value: felt) {
if (n == 0) {
}

}

func main() -> () {
alloc_locals;
let (stack) = empty_stack();
// Push 1, 10, 100.
let (stack) = push(stack, 1);
let (stack) = push(stack, 10);
let (local stack) = push(stack, 100);

// Check the size of the stack.
assert stack.size = 3;

// Query the stack at indices 0, 1 and 2.
let (value) = stack_at(stack, 0);
assert value = 100;
let (value) = stack_at(stack, 1);
assert value = 10;
let (value) = stack_at(stack, 2);
assert value = 1;

// Pop the top 2 values (100 and 10) and push 1000.
let (stack, value) = pop(stack);
assert value = 100;
let (stack, value) = pop(stack);
assert value = 10;
let (local stack) = push(stack, 1000);

// Query the stack at indices 0 and 1.
let (value) = stack_at(stack, 0);
assert value = 1000;
let (value) = stack_at(stack, 1);
assert value = 1;

return ();
}
``````

Answers to this question are a part of the ✨ 17 days of Cairo Lang with Playground & Newton. ✨

Vote for your favorite answer - the best answer will win a \$10 award. A new day – a new reward! During the next 17 days, our goal is to attract more developers to the Cairo language and to systematize the knowledge of Cairo lang. Read rules

#17daysOfCairocairo-beginnerscairoplayground

Newton

3 months ago

0

# 1. Requirement

• Define the `push` function: Adds a node to the top of the stack
• Define the `stack_at` function: Returns the value of the n-th element from the top of the stack.

# 2. Solution

• The push function: Create a new `Node`, `Node.next` is old linked list, increase size by 1. New linked list starts with newly created node.
• The `stack_at` function: if `n = 0,` return value of the first element in list. If `n > 0`, use recursion with `n-1` and pointer to next element.

# 3. Souce code

``````func push(stack: Node*, value: felt) -> (stack: Node*) {
alloc_locals;
local new_node: Node;
// Fix and uncomment below.
assert new_node.next = stack;
assert new_node.value = value;
assert new_node.size = stack.size + 1;

let (__fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}
``````
``````func stack_at(stack: Node*, n: felt) -> (value: felt) {
if (n == 0) {
return (value = stack.value);
}

return stack_at(stack.next, n - 1);
}
``````

3 months ago

0

``````//
// Add the missing code so that main() runs successfully.

from starkware.cairo.common.registers import get_fp_and_pc

struct Node {
// A pointer to the next node in the stack.
next: Node*,

// The value of the node.
value: felt,

// The number of elements in the stack.
size: felt,
}

// Returns an empty stack.
func empty_stack() -> (stack: Node*) {
alloc_locals;
local new_node: Node;
assert new_node.next = cast(0, Node*);
assert new_node.value = 0;
assert new_node.size = 0;

// The usage of get_fp_and_pc() here is necessary in order
// to access the address of a local variable (&new_node).
let (local __fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}

// Adds a node to the top of the stack.
// Returns the updated stack (since Cairo is immutable, you can still use the
// old copy of the stack).
func push(stack: Node*, value: felt) -> (stack: Node*) {
alloc_locals;
local new_node: Node;
// Fix and uncomment below.
assert new_node.next = stack;
assert new_node.value = value;
assert new_node.size = stack.size +1;

let (__fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}

// Removes the top element of the stack.
// Returns the updated stack and the element that was removed.
func pop(stack: Node*) -> (stack: Node*, value: felt) {
return (stack=stack.next, value=stack.value);
}

// Returns the value of the n-th element from the top of the stack.
func stack_at(stack: Node*, n: felt) -> (value: felt) {
alloc_locals;
if (n == 0) {
return (value = stack.value);
}

let (local val) = stack_at(stack=stack.next, n=n - 1);
return (value=val);

}

func main() -> () {
alloc_locals;
let (stack) = empty_stack();
// Push 1, 10, 100.
let (stack) = push(stack, 1);
let (stack) = push(stack, 10);
let (local stack) = push(stack, 100);

// Check the size of the stack.
assert stack.size = 3;

// Query the stack at indices 0, 1 and 2.
let (value) = stack_at(stack, 0);
assert value = 100;
let (value) = stack_at(stack, 1);
assert value = 10;
let (value) = stack_at(stack, 2);
assert value = 1;

// Pop the top 2 values (100 and 10) and push 1000.
let (stack, value) = pop(stack);
assert value = 100;
let (stack, value) = pop(stack);
assert value = 10;
let (local stack) = push(stack, 1000);

// Query the stack at indices 0 and 1.
let (value) = stack_at(stack, 0);
assert value = 1000;
let (value) = stack_at(stack, 1);
assert value = 1;

return ();
}
``````

3 months ago

0

# Solution

``````// In this challenge you're going to implement a stack using a linked list.
//
// Add the missing code so that main() runs successfully.

from starkware.cairo.common.registers import get_fp_and_pc

struct Node {
// A pointer to the next node in the stack.
next: Node*,

// The value of the node.
value: felt,

// The number of elements in the stack.
size: felt,
}

// Returns an empty stack.
func empty_stack() -> (stack: Node*) {
alloc_locals;
local new_node: Node;
assert new_node.next = cast(0, Node*);
assert new_node.value = 0;
assert new_node.size = 0;

// The usage of get_fp_and_pc() here is necessary in order
// to access the address of a local variable (&new_node).
let (local __fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}

// Adds a node to the top of the stack.
// Returns the updated stack (since Cairo is immutable, you can still use the
// old copy of the stack).
func push(stack: Node*, value: felt) -> (stack: Node*) {
alloc_locals;
local new_node: Node;
assert new_node.next = stack;
assert new_node.value = value;
assert new_node.size = stack.size+1;

let (__fp__, _) = get_fp_and_pc();
return (stack=&new_node);
}

// Removes the top element of the stack.
// Returns the updated stack and the element that was removed.
func pop(stack: Node*) -> (stack: Node*, value: felt) {
return (stack=stack.next, value=stack.value);
}

// Returns the value of the n-th element from the top of the stack.
func stack_at(stack: Node*, n: felt) -> (value: felt) {
alloc_locals;
if (n == 0) {
return (value=stack.value);
}
let (local val) = stack_at(stack=stack.next, n=n - 1);
return (value=val);
}

func main() -> () {
alloc_locals;
let (stack) = empty_stack();
// Push 1, 10, 100.
let (stack) = push(stack, 1);
let (stack) = push(stack, 10);
let (local stack) = push(stack, 100);

// Check the size of the stack.
assert stack.size = 3;

// Query the stack at indices 0, 1 and 2.
let (value) = stack_at(stack, 0);
assert value = 100;
let (value) = stack_at(stack, 1);
assert value = 10;
let (value) = stack_at(stack, 2);
assert value = 1;

// Pop the top 2 values (100 and 10) and push 1000.
let (stack, value) = pop(stack);
assert value = 100;
let (stack, value) = pop(stack);
assert value = 10;
let (local stack) = push(stack, 1000);

// Query the stack at indices 0 and 1.
let (value) = stack_at(stack, 0);
assert value = 1000;
let (value) = stack_at(stack, 1);
assert value = 1;

return ();
}

``````

Ishita Rastogi

3 months ago