Task 1: Ackermann Function
Create a script to demonstrate the Ackermann function. The Ackermann function is defined as:
- $A(m, n) = n + 1$ if $m = 0$
- $A(m, n) = A(m - 1, 1)$ if $m > 0$ and $n = 0$
- $A(m, n) = A(m - 1, A(m, n - 1))$ if $m > 0$ and $n > 0$
Example Output
A(1, 2) = 4
A(2, 1) = 5
Logic
The Ackermann function is a classic example of a system that is recursive but not primitive recursive. It grows extremely fast even for small values of $m$ and $n$. A simple direct recursion translates the definition directly into code, though memoization is often required to calculate larger inputs due to call stack limits.
Perl Solution
ch-1.pl
sub get_ack {
my ( $m, $n ) = @_;
return $n + 1 if $m == 0;
return get_ack( $m - 1, 1 ) if ( $m > 0 ) and ( $n == 0 );
return get_ack( $m - 1, get_ack( $m, $n - 1 ) );
}
Python Solution
ch-1.py
def get_ack(m: int, n: int) -> int:
if m == 0:
return n + 1
if m > 0 and n == 0:
return get_ack(m - 1, 1)
return get_ack(m - 1, get_ack(m, n - 1))
Task 2: URL Parser
Create a script to parse a URL and print its components according to the syntax: scheme:[//[userinfo@]host[:port]]path[?query][#fragment].
Example
Input: jdbc://user:password@localhost:3306/pwc?profile=true#h1
Output:
Scheme: jdbc
Userinfo: user:password
Host: localhost
Port: 3306
Path: /pwc
Query: profile=true
Fragment: h1
Logic
We parse the URL string to extract its component parts using regular expressions or high-level URL libraries (like Mojo::URL in Perl or urllib.parse in Python) to reliably handle all edge cases.
Perl Solution
ch-2.pl
use Mojo::URL;
sub decompose_url {
my $what = shift;
return Mojo::URL->new($what);
}
Python Solution
ch-2.py
from urllib.parse import urlparse
def decompose_url(url_str: str) -> dict[str, str]:
parsed = urlparse(url_str)
return {
"scheme": parsed.scheme,
"userinfo": f"{parsed.username}:{parsed.password}" if parsed.username else "",
"host": parsed.hostname or "",
"port": str(parsed.port) if parsed.port else "",
"path": parsed.path,
"query": parsed.query,
"fragment": parsed.fragment,
}