Cairo: pattern of bits challenge

Cairo: pattern of bits challenge

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

%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

%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

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 from Starkware math library.

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:

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.

A workaround is to make a standalone function:

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:

 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.

 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.

  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.

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