Cairo: pattern of bits challenge
Tags: cairolang, web3, starknet
Published: 2022-11-06 07:44:27

## Introduction
In Encode's Cairo Bootcamp, there is an interesting bit manipulation challenge. It took me some time to figure it out. In this article, I will discuss the challenge and the solution.

## The challenge
`ex7.cairo`
```rust
%lang starknet
from starkware.cairo.common.bitwise import bitwise_and, bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.math import unsigned_div_rem

// Using binary operations return:
// - 1 when pattern of bits is 01010101 from LSB up to MSB 1, but accounts for trailing zeros
// - 0 otherwise

// 000000101010101 PASS
// 010101010101011 FAIL

func pattern{bitwise_ptr: BitwiseBuiltin*, range_check_ptr}(
    n: felt, idx: felt, exp: felt, broken_chain: felt
) -> (true: felt) {
    return (0,);
}
```
`test_ex7.cairo`
```rust
%lang starknet
from starkware.cairo.common.uint256 import Uint256
from starkware.cairo.common.bitwise import bitwise_and, bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin, HashBuiltin

from exercises.programs.ex7 import pattern

@external
func test_patternt{syscall_ptr: felt*, range_check_ptr, bitwise_ptr: BitwiseBuiltin*}() {
    alloc_locals;

    // test nice numbers
    //###############################################################################################
    let (nice_pattern) = pattern(n=170, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    let (nice_pattern) = pattern(n=10, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    let (nice_pattern) = pattern(n=43690, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    let (nice_pattern) = pattern(n=1398101, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 1;

    // test not-nice numbers
    //###############################################################################################
    let (nice_pattern) = pattern(n=17, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 0;

    let (nice_pattern) = pattern(n=11, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 0;

    let (nice_pattern) = pattern(n=43390, idx=0, exp=0, broken_chain=0);
    assert nice_pattern = 0;

    %{
        if ids.nice_pattern == 1:
            print(f"has nice pattern") 
        else:
            print(f"doesn't have a nice pattern")
    %}

    return ();
}
```
## Understanding the problem

If the bit pattern is 01010101, it is valid. Looking at the test cases, we can see that 01010 (decimal 10) is valid too. This means that the problem is about alternative bits between 1 and 0.  If the alternative pattern is not broken until the LSB, we return 1, otherwise, return 0. For instance, we will get 1 for 01010 (decimal 10), and 0 for 01011 (decimal 11).

Since the challenge gives us the test cases, we can get some cues about the arguments from them. There are 4 arguments in the pattern function: 
- `n: felt` is the decimal number that we want to check its bit pattern. This tells us that we need to convert the decimal number to binary.
- `idx: felt` is the index of a bit in the pattern.
- `exp: felt` is the value of a bit. We need this because we want to compare adjacent bits to see if the chain is valid.
- `broken_chain: felt` The name says it all. It is like a "boolean" variable that determines whether the pattern is broken. 

## Solution
```rust
func check_broken_chain{range_check_ptr}(remainder: felt, exp: felt) -> felt {
    if (remainder == exp) {
        return 1;
    }
    return 0;
}

func pattern{bitwise_ptr: BitwiseBuiltin*, range_check_ptr}(
    n: felt, idx: felt, exp: felt, broken_chain: felt
) -> (true: felt) {
    if (n == 0) {
        let valid_chain = 1 - broken_chain;
        return (valid_chain,);
    }

    if (broken_chain == 1) {
        let valid_chain = 1 - broken_chain;

        return (valid_chain,);
    }

    if (idx == 0) {
        let (quotient, remainder) = unsigned_div_rem(n, 2);
        let new_idx = idx + 1;
        return pattern(quotient, new_idx, remainder, 0);
    }

    let (quotient, remainder) = unsigned_div_rem(n, 2);
    let _broken_chain = check_broken_chain(remainder, exp);

    let new_idx = idx + 1;
    return pattern(quotient, new_idx, remainder, _broken_chain);
}
```
## Explain the solution

The solution can be broken down into 3 simple steps :
1. Convert the decimal `n` to binary
2. Check if the pattern is valid
3. Handle edge case and base case

### Convert the decimal n to binary

One way to convert decimal to binary is to use modulo. Cairo does not have a built-in modulo operator, but we can use [unsigned_div_rem](https://perama-v.github.io/cairo/cairo-common-library/#unsigned_div_rem) from Starkware math library. 

```rust
from starkware.cairo.common.math import unsigned_div_rem

let (quotient, remainder) = unsigned_div_rem(n, 2);
```

### Check if the pattern is valid
Simply put, It comes down to whether the current bit `remainder` is different than the previous bit `exp`. If they are the same, the pattern is broken. 

When I first tried to handle the _broken_chain value, I did this:
```rust
let (quotient, remainder) = unsigned_div_rem(n, 2);
tempvar _broken_chain = 0;
   if (remainder == exp) {
        _broken_chain = 1;
    }
let new_idx = idx + 1;

return pattern(quotient, new_idx, remainder, _broken_chain);
```
and got an error
```
An ASSERT_EQ instruction failed: 0 != 1.
        _broken_chain = 1;
        ^***************^
```
The reason is that Cairo's memory cell is read-only. Read more about it [here](https://www.cairo-lang.org/docs/how_cairo_works/cairo_intro.html#memory-model). 

A workaround is to make a standalone function:
```rust
func check_broken_chain{range_check_ptr}(remainder: felt, exp: felt) -> felt {
    if (remainder == exp) {
        return 1;
    }
    return 0;
}
...
let (quotient, remainder) = unsigned_div_rem(n, 2);
let _broken_chain = check_broken_chain(remainder, exp);
let new_idx = idx + 1;

return pattern(quotient, new_idx, remainder, _broken_chain);
```
Since the challenge has a `bitwise_xor` import in the first place, we can also use it to get the `_broken_chain` use like so: 
```rust
 let (remainder_xor_prev_remainder) = bitwise_xor(remainder, exp);
 let _broken_chain = 1 - remainder_xor_prev_remainder;
```

During the recursion, if broken_chain is 1, we just return the result. 
```rust
 if (broken_chain == 1) {
        let valid_chain = 1 - broken_chain;

        return (valid_chain,);
    }
```
### Handle the edge case and base case
The first bit does not have a previous bit to compare with, so we can just calculate its remainder and move to the next bit. 
```rust
  if (idx == 0) {
        let (quotient, remainder) = unsigned_div_rem(n, 2);
        let new_idx = idx + 1;
        return pattern(quotient, new_idx, remainder, 0);
    }
```

Because we keep dividing n by 2, it will become 0 eventually. When it does, we return the result. 
```rust
if (n == 0) {
        let valid_chain = 1 - broken_chain;
        return (valid_chain,);
   }
```

## Wrapping Up

Alright, that is all I am covering for today. If you have any questions, please feel free to reach out to me. I hope this is helpful to somebody learning Cairo. 

You can find the code in this article on [Github](https://github.com/peterblockman/CairoBootcamp/blob/main/exercises/programs/ex7.cairo)