Use Python Hidden Features, Heaps & Functools to Explore 2D Infinite Array

Hello, checkiomates🐱‍👤!

Did you know, that at every mission page, under the editor window, there is a terminal window. If you want to discover all CheckiO features, visit our tutorial. It's a longread, but it's worth it!

🏁 MISSIONS:

You need to split strings of digits into the longest lists of encreasing numbers and find an element in the ♾ infinite 2D matrix! Sounds interesting? 🐍

Exploring Wythoff Array by freeman_lex - Wythoff array is an infinite two-dimensional grid of integers that is seeded with 1 and 2 to start off the first row. In each row, each element equals the sum of the previous two elements, so the first row contains precisely the Fibonacci numbers.

The first element of each row after the first is the smallest integer c that does not appear anywhere in the previous rows. Since every row is strictly ascending and grows exponentially fast, you can find this out by looking at relatively short finite prefixes of these rows. To determine the second element of that row, let a and b be the first two elements of the previous row. If the difference c-a equals 2, the second element of that row equals b+3, and otherwise that element equals b+5.

This function should return the position of n in the Wythoff array as tuple (row, col), rows and columns both starting from zero.

wythoff_array(21) == (0, 6)
wythoff_array(47) == (1, 5)
wythoff_array(1042) == (8, 8)

Beat The Previous by freeman_lex - Given a string of digits guaranteed to only contain ordinary integer digit characters 0 to 9, create and return the list of increasing integers acquired from reading these digits in order from left to right. The first integer in the result list is made up from the first digit of the string. After that, each element is an integer that consists of as many following consecutive digits as are needed to make that integer strictly larger than the previous integer. The leftover digits at the end of the digit string that do not form a sufficiently large integer are ignored.

beat_previous("600005") == [6]
beat_previous("6000050") == [6, 50]
beat_previous("045349") == [0, 4, 5, 34]

Staircase by freeman_lex - The easier problem "Beat the previous" asked you to greedily extract a strictly ascending sequence of integers from the given series of digits. For example, for digits equal to "31415926", the list of integers returned should be [3, 14, 15, 92], with the last original digit left unused.

Going somewhat against intuition, the ability to tactically skip some of the digits at will may allow the resulting list of integers to contain more elements than the list constructed in the previous greedy fashion. With this additional freedom, the example digit string "31415926" would allow the result [3, 4, 5, 9, 26] with one more element than the greedily constructed solution.

Your function should return the length of the longest list of ascending integers that can be extracted from digits. Note that you are allowed to skip one or more digits not just between two integers being extracted, but during the construction of each such integer.

staircase("100123") == 4
staircase("503715") == 4
staircase("0425494220946") == 6

💡ARTICLES:

Today's articles are focused on a few intermediate themes: using heaps, high-level functions of functools module and some hidden features in Python you may not know! Let's dive into this together!

Hidden Features of Python - Python is a powerful programming language that's easy to learn and fun to play with. But beyond the basics, there are plenty of hidden features and tricks that can help you write more efficient and more effective Python code. In this article, we'll uncover some of these hidden features and show you how to use them to improve your Python programming skills. Maybe, you'll find something new for you!

Introduction To Python's Functools Module - The functools module is part of Python's standard library and was implemented for higher-order functions. A higher-order function is a function that acts on or returns another function or multiple functions. In general, any callable object can be treated as a function for the purposes of this module.

Heap in Python: Min & Max Heap Implementation - While they are not as commonly used, they can be incredibly useful in certain scenarios. In this article, we will learn what a heap is in Python. We will also understand how to implement max heap and min heap concepts and the difference between them.

Don't forget to comment your code!😈

🙌 Thanks for your attention! Hope to meet you at CheckiO. We are really interested in your thoughts! Please, leave a comment below! ⤵