text:
#!/usr/bin/env sh

##############################################################################
##
##  Gradle start up script for UN*X
##
##############################################################################

# Attempt to set APP_HOME
# Resolve links: $0 may be a link
PRG="$0"
# Need this for relative symlinks.
while [ -h "$PRG" ] ; do
    ls=`ls -ld "$PRG"`
    link=`expr "$ls" : '.*-> \(.*\)$'`
    if expr "$link" : '/.*' > /dev/null; then
        PRG="$link"
    else
        PRG=`dirname "$PRG"`"/$link"
    fi
done
SAVED="`pwd`"
cd "`dirname \"$PRG\"`/" >/dev/null
APP_HOME="`pwd -P`"
cd "$SAVED" >/dev/null

APP_NAME="Gradle"
APP_BASE_NAME=`basename "$0"`

# Add default JVM options here. You can also use JAVA_OPTS and GRADLE_OPTS to pass JVM options to this script.
DEFAULT_JVM_OPTS=""

# Use the maximum available, or set MAX_FD != -1 to use that value.
MAX_FD="maximum"

warn () {
    echo "$*"
}

die () {
    echo
    echo "$*"
    echo
    exit 1
}

# OS specific support (must be 'true' or 'false').
cygwin=false
msys=false
darwin=false
nonstop=false
case "`uname`" in
  CYGWIN* )
    cygwin=true
    ;;
  Darwin* )
    darwin=true
    ;;
  MINGW* )
    msys=true
    ;;
  NONSTOP* )
    nonstop=true
    ;;
esac

CLASSPATH=$APP_HOME/gradle/wrapper/gradle-wrapper.jar

# Determine the Java command to use to start the JVM.
if [ -n "$JAVA_HOME" ] ; then
    if [ -x "$JAVA_HOME/jre/sh/java" ] ; then
        # IBM's JDK on AIX uses strange locations for the executables
        JAVACMD="$JAVA_HOME/jre/sh/java"
    else
        JAVACMD="$JAVA_HOME/bin/java"
    fi
    if [ ! -x "$JAVACMD" ] ; then
        die "ERROR: JAVA_HOME is set to an invalid directory: $JAVA_HOME

Please set the JAVA_HOME variable in your environment to match the
location of your Java installation."
    fi
else
    JAVACMD="java"
    which java >/dev/null 2>&1 || die "ERROR: JAVA_HOME is not set and no 'java' command could be found in your PATH.

Please set the JAVA_HOME variable in your environment to match the
location of your Java installation."
fi

# Increase the maximum file descriptors if we can.
if [ "$cygwin" = "false" -a "$darwin" = "false" -a "$nonstop" = "false" ] ; then
    MAX_FD_LIMIT=`ulimit -H -n`
    if [ $? -eq 0 ] ; then
        if [ "$MAX_FD" = "maximum" -o "$MAX_FD" = "max" ] ; then
            MAX_FD="$MAX_FD_LIMIT"
        fi
        ulimit -n $MAX_FD
        if [ $? -ne 0 ] ; then
            warn "Could not set maximum file descriptor limit: $MAX_FD"
        fi
    else
        warn "Could not query maximum file descriptor limit: $MAX_FD_LIMIT"
    fi
fi

# For Darwin, add options to specify how the application appears in the dock
if $darwin; then
    GRADLE_OPTS="$GRADLE_OPTS \"-Xdock:name=$APP_NAME\" \"-Xdock:icon=$APP_HOME/media/gradle.icns\""
fi

# For Cygwin, switch paths to Windows format before running java
if $cygwin ; then
    APP_HOME=`cygpath --path --mixed "$APP_HOME"`
    CLASSPATH=`cygpath --path --mixed "$CLASSPATH"`
    JAVACMD=`cygpath --unix "$JAVACMD"`

    # We build the pattern for arguments to be converted via cygpath
    ROOTDIRSRAW=`find -L / -maxdepth 1 -mindepth 1 -type d 2>/dev/null`
    SEP=""
    for dir in $ROOTDIRSRAW ; do
        ROOTDIRS="$ROOTDIRS$SEP$dir"
        SEP="|"
    done
    OURCYGPATTERN="(^($ROOTDIRS))"
    # Add a user-defined pattern to the cygpath arguments
    if [ "$GRADLE_CYGPATTERN" != "" ] ; then
        OURCYGPATTERN="$OURCYGPATTERN|($GRADLE_CYGPATTERN)"
    fi
    # Now convert the arguments - kludge to limit ourselves to /bin/sh
    i=0
    for arg in "$@" ; do
        CHECK=`echo "$arg"|egrep -c "$OURCYGPATTERN" -`
        CHECK2=`echo "$arg"|egrep -c "^-"`                                 ### Determine if an option

        if [ $CHECK -ne 0 ] && [ $CHECK2 -eq 0 ] ; then                    ### Added a condition
            eval `echo args$i`=`cygpath --path --ignore --mixed "$arg"`
        else
            eval `echo args$i`="\"$arg\""
        fi
        i=$((i+1))
    done
    case $i in
        (0) set -- ;;
        (1) set -- "$args0" ;;
        (2) set -- "$args0" "$args1" ;;
        (3) set -- "$args0" "$args1" "$args2" ;;
        (4) set -- "$args0" "$args1" "$args2" "$args3" ;;
        (5) set -- "$args0" "$args1" "$args2" "$args3" "$args4" ;;
        (6) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" ;;
        (7) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" "$args6" ;;
        (8) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" "$args6" "$args7" ;;
        (9) set -- "$args0" "$args1" "$args2" "$args3" "$args4" "$args5" "$args6" "$args7" "$args8" ;;
    esac
fi

# Escape application args
save () {
    for i do printf %s\\n "$i" | sed "s/'/'\\\\''/g;1s/^/'/;\$s/\$/' \\\\/" ; done
    echo " "
}
APP_ARGS=$(save "$@")

# Collect all arguments for the java command, following the shell quoting and substitution rules
eval set -- $DEFAULT_JVM_OPTS $JAVA_OPTS $GRADLE_OPTS "\"-Dorg.gradle.appname=$APP_BASE_NAME\"" -classpath "\"$CLASSPATH\"" org.gradle.wrapper.GradleWrapperMain "$APP_ARGS"

# by default we should be in the correct project dir, but when run from Finder on Mac, the cwd is wrong
if [ "$(uname)" = "Darwin" ] && [ "$HOME" = "$PWD" ]; then
  cd "$(dirname "$0")"
fi

exec "$JAVACMD" "$@"


text:
## Stickers Import Sample for Telegram

This is a sample project for importing stickers to Telegram via the Android app.

Please read the full documentation here: https://core.telegram.org/import-stickers

>**WARNING:** Each time a user imports stickers, a **new sticker pack** is created on Telegram. **Do not use** the importing feature to share stickers *you* made with *other* users. If you want to share your stickers, simply upload them using [@stickers](https://t.me/stickers), then share the **link** of your pack. For example, here's a link to install some [Duck Stickers](https://t.me/addstickers/UtyaDuck).

### Supported file formats

1. **PNG** or **WEBP** for static sticker packs with a transparent layer which must fit into a 512x512 square (one of the sides must be 512px and the other 512px or less).
2. [**TGS**](https://core.telegram.org/animated_stickers) for animated stickers packs.

### How to use

Simply send an Android [Intent](https://developer.android.com/guide/components/intents-filters) with the action `org.telegram.messenger.CREATE_STICKER_PACK` and two extras:

1. `Intent.EXTRA_STREAM` containing URIs to the stickers.
2. `STICKER_EMOJIS` with relevant emojis for every sticker you importing.

Additionaly you can provide an `IMPORTER` extra for statistic purposes.

```
private static final String CREATE_STICKER_PACK_ACTION = "org.telegram.messenger.CREATE_STICKER_PACK";
private static final String CREATE_STICKER_PACK_EMOJIS_EXTRA = "STICKER_EMOJIS";
private static final String CREATE_STICKER_PACK_IMPORTER_EXTRA = "IMPORTER";

private void doImport(ArrayList<Uri> stickers, ArrayList<String> emojis) {
    Intent intent = new Intent(CREATE_STICKER_PACK_ACTION);
    intent.putExtra(Intent.EXTRA_STREAM, stickers);
    intent.putExtra(CREATE_STICKER_PACK_IMPORTER_EXTRA, getPackageName());
    intent.putExtra(CREATE_STICKER_PACK_EMOJIS_EXTRA, emojis);
    intent.setType("image/*");

    // Try to invoke the intent.
    try {
        startActivity(sendIntent);
    } catch (ActivityNotFoundException e) {
        // Define what your app should do if no activity can handle the intent.
    }
}
```

repo_name: DrKLO/TelegramStickersImport

repo_language: Java

mime_type: text/plain


text:
# Add project specific ProGuard rules here.
# You can control the set of applied configuration files using the
# proguardFiles setting in build.gradle.
#
# For more details, see
#   http://developer.android.com/guide/developing/tools/proguard.html

# If your project uses WebView with JS, uncomment the following
# and specify the fully qualified class name to the JavaScript interface
# class:
#-keepclassmembers class fqcn.of.javascript.interface.for.webview {
#   public *;
#}

# Uncomment this to preserve the line number information for
# debugging stack traces.
#-keepattributes SourceFile,LineNumberTable

# If you keep the line number information, uncomment this to
# hide the original source file name.
#-renamesourcefileattribute SourceFile


text:
<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="org.telegram.stickersimportexample">

    <application
        android:allowBackup="true"
        android:icon="@mipmap/ic_launcher"
        android:label="@string/app_name"
        android:roundIcon="@mipmap/ic_launcher_round"
        android:supportsRtl="true"
        android:theme="@style/Theme.StickersImportExample">
        <activity android:name=".MainActivity">
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />

                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>

</manifest>


text:
<?xml version="1.0" encoding="utf-8"?>
<resources>
    <color name="purple_200">#FFBB86FC</color>
    <color name="purple_500">#FF6200EE</color>
    <color name="purple_700">#FF3700B3</color>
    <color name="teal_200">#FF03DAC5</color>
    <color name="teal_700">#FF018786</color>
    <color name="black">#FF000000</color>
    <color name="white">#FFFFFFFF</color>
</resources>


text:
<resources xmlns:tools="http://schemas.android.com/tools">
    <!-- Base application theme. -->
    <style name="Theme.StickersImportExample" parent="Theme.MaterialComponents.DayNight.DarkActionBar">
        <!-- Primary brand color. -->
        <item name="colorPrimary">@color/purple_500</item>
        <item name="colorPrimaryVariant">@color/purple_700</item>
        <item name="colorOnPrimary">@color/white</item>
        <!-- Secondary brand color. -->
        <item name="colorSecondary">@color/teal_200</item>
        <item name="colorSecondaryVariant">@color/teal_700</item>
        <item name="colorOnSecondary">@color/black</item>
        <!-- Status bar color. -->
        <item name="android:statusBarColor" tools:targetApi="l">?attr/colorPrimaryVariant</item>
        <!-- Customize your theme here. -->
    </style>
</resources>


text:
<resources>
    <string name="app_name">StickersImportExample</string>
</resources>


text:
<resources xmlns:tools="http://schemas.android.com/tools">
    <!-- Base application theme. -->
    <style name="Theme.StickersImportExample" parent="Theme.MaterialComponents.DayNight.DarkActionBar">
        <!-- Primary brand color. -->
        <item name="colorPrimary">@color/purple_200</item>
        <item name="colorPrimaryVariant">@color/purple_700</item>
        <item name="colorOnPrimary">@color/black</item>
        <!-- Secondary brand color. -->
        <item name="colorSecondary">@color/teal_200</item>
        <item name="colorSecondaryVariant">@color/teal_200</item>
        <item name="colorOnSecondary">@color/black</item>
        <!-- Status bar color. -->
        <item name="android:statusBarColor" tools:targetApi="l">?attr/colorPrimaryVariant</item>
        <!-- Customize your theme here. -->
    </style>
</resources>


text:
<?xml version="1.0" encoding="utf-8"?>
<adaptive-icon xmlns:android="http://schemas.android.com/apk/res/android">
    <background android:drawable="@drawable/ic_launcher_background" />
    <foreground android:drawable="@drawable/ic_launcher_foreground" />
</adaptive-icon>


text:
<?xml version="1.0" encoding="utf-8"?>
<FrameLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    tools:context=".MainActivity">

    <Button
        android:id="@+id/button2"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_gravity="center"
        android:layout_marginTop="50dp"
        android:text="Import Animated"
        tools:layout_editor_absoluteX="116dp"
        tools:layout_editor_absoluteY="380dp" />

    <Button
        android:id="@+id/button"
        android:layout_width="wrap_content"
        android:layout_height="48dp"
        android:layout_gravity="center"
        android:layout_marginBottom="50dp"
        android:text="Import"
        tools:layout_editor_absoluteX="160dp"
        tools:layout_editor_absoluteY="240dp" />
</FrameLayout>


text:
<?xml version="1.0" encoding="utf-8"?>
<vector xmlns:android="http://schemas.android.com/apk/res/android"
    android:width="108dp"
    android:height="108dp"
    android:viewportWidth="108"
    android:viewportHeight="108">
    <path
        android:fillColor="#3DDC84"
        android:pathData="M0,0h108v108h-108z" />
    <path
        android:fillColor="#00000000"
        android:pathData="M9,0L9,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,0L19,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M29,0L29,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M39,0L39,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M49,0L49,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M59,0L59,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M69,0L69,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M79,0L79,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M89,0L89,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M99,0L99,108"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,9L108,9"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,19L108,19"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,29L108,29"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,39L108,39"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,49L108,49"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,59L108,59"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,69L108,69"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,79L108,79"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,89L108,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M0,99L108,99"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,29L89,29"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,39L89,39"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,49L89,49"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,59L89,59"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,69L89,69"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M19,79L89,79"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M29,19L29,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M39,19L39,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M49,19L49,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M59,19L59,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M69,19L69,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
    <path
        android:fillColor="#00000000"
        android:pathData="M79,19L79,89"
        android:strokeWidth="0.8"
        android:strokeColor="#33FFFFFF" />
</vector>


text:
<vector xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:aapt="http://schemas.android.com/aapt"
    android:width="108dp"
    android:height="108dp"
    android:viewportWidth="108"
    android:viewportHeight="108">
    <path android:pathData="M31,63.928c0,0 6.4,-11 12.1,-13.1c7.2,-2.6 26,-1.4 26,-1.4l38.1,38.1L107,108.928l-32,-1L31,63.928z">
        <aapt:attr name="android:fillColor">
            <gradient
                android:endX="85.84757"
                android:endY="92.4963"
                android:startX="42.9492"
                android:startY="49.59793"
                android:type="linear">
                <item
                    android:color="#44000000"
                    android:offset="0.0" />
                <item
                    android:color="#00000000"
                    android:offset="1.0" />
            </gradient>
        </aapt:attr>
    </path>
    <path
        android:fillColor="#FFFFFF"
        android:fillType="nonZero"
        android:pathData="M65.3,45.828l3.8,-6.6c0.2,-0.4 0.1,-0.9 -0.3,-1.1c-0.4,-0.2 -0.9,-0.1 -1.1,0.3l-3.9,6.7c-6.3,-2.8 -13.4,-2.8 -19.7,0l-3.9,-6.7c-0.2,-0.4 -0.7,-0.5 -1.1,-0.3C38.8,38.328 38.7,38.828 38.9,39.228l3.8,6.6C36.2,49.428 31.7,56.028 31,63.928h46C76.3,56.028 71.8,49.428 65.3,45.828zM43.4,57.328c-0.8,0 -1.5,-0.5 -1.8,-1.2c-0.3,-0.7 -0.1,-1.5 0.4,-2.1c0.5,-0.5 1.4,-0.7 2.1,-0.4c0.7,0.3 1.2,1 1.2,1.8C45.3,56.528 44.5,57.328 43.4,57.328L43.4,57.328zM64.6,57.328c-0.8,0 -1.5,-0.5 -1.8,-1.2s-0.1,-1.5 0.4,-2.1c0.5,-0.5 1.4,-0.7 2.1,-0.4c0.7,0.3 1.2,1 1.2,1.8C66.5,56.528 65.6,57.328 64.6,57.328L64.6,57.328z"
        android:strokeWidth="1"
        android:strokeColor="#00000000" />
</vector>


text:
package org.telegram.stickersimportexample;

import androidx.appcompat.app.AppCompatActivity;

import android.content.ContentResolver;
import android.content.Intent;
import android.net.Uri;
import android.os.Bundle;
import android.widget.Button;

import java.util.ArrayList;

public class MainActivity extends AppCompatActivity {

    private static final String CREATE_STICKER_PACK_ACTION = "org.telegram.messenger.CREATE_STICKER_PACK";
    private static final String CREATE_STICKER_PACK_EMOJIS_EXTRA = "STICKER_EMOJIS";
    private static final String CREATE_STICKER_PACK_IMPORTER_EXTRA = "IMPORTER";

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        Button button = findViewById(R.id.button);
        if (button != null) {
            button.setOnClickListener(v -> {
                ArrayList<Uri> uris = new ArrayList<>();
                uris.add(getRawUri("sticker1"));
                uris.add(getRawUri("sticker2"));
                uris.add(getRawUri("sticker3"));
                uris.add(getRawUri("sticker4"));
                uris.add(getRawUri("sticker5"));
                uris.add(getRawUri("sticker6"));
                uris.add(getRawUri("sticker7"));
                uris.add(getRawUri("sticker8"));
                uris.add(getRawUri("sticker9"));

                ArrayList<String> emojis = new ArrayList<>();
                emojis.add("☺");
                emojis.add("\uD83D\uDE22");
                emojis.add("\uD83E\uDD73");
                emojis.add("\uD83E\uDD2A");
                emojis.add("\uD83D\uDE18");
                emojis.add("\uD83D\uDE18");
                emojis.add("\uD83E\uDD2A");
                emojis.add("\uD83E\uDD73");
                emojis.add("☺");

                doImport(uris, emojis);
            });
        }

        button = findViewById(R.id.button2);
        if (button != null) {
            button.setOnClickListener(v -> {
                ArrayList<Uri> uris = new ArrayList<>();
                uris.add(getRawUri("a_sticker1"));
                uris.add(getRawUri("a_sticker2"));
                uris.add(getRawUri("a_sticker3"));
                uris.add(getRawUri("a_sticker4"));
                uris.add(getRawUri("a_sticker5"));
                uris.add(getRawUri("a_sticker6"));
                uris.add(getRawUri("a_sticker7"));
                uris.add(getRawUri("a_sticker8"));
                uris.add(getRawUri("a_sticker9"));

                ArrayList<String> emojis = new ArrayList<>();
                emojis.add("☺");
                emojis.add("\uD83D\uDE22");
                emojis.add("\uD83E\uDD73");
                emojis.add("\uD83E\uDD2A");
                emojis.add("\uD83D\uDE18");
                emojis.add("\uD83D\uDE18");
                emojis.add("\uD83E\uDD2A");
                emojis.add("\uD83E\uDD73");
                emojis.add("☺");

                doImport(uris, emojis);
            });
        }
    }

    private void doImport(ArrayList<Uri> stickers, ArrayList<String> emojis) {
        Intent intent = new Intent(CREATE_STICKER_PACK_ACTION);
        intent.putExtra(Intent.EXTRA_STREAM, stickers);
        intent.putExtra(CREATE_STICKER_PACK_IMPORTER_EXTRA, getPackageName());
        intent.putExtra(CREATE_STICKER_PACK_EMOJIS_EXTRA, emojis);
        intent.setType("image/*");
        try {
            startActivity(intent);
        } catch (Exception e) {
            e.printStackTrace();
            //no activity to handle intent
        }
    }

    private Uri getRawUri(String filename) {
        return Uri.parse(ContentResolver.SCHEME_ANDROID_RESOURCE + "://" + getPackageName() + "/raw/" + filename);
    }
}


text:
#Fri Jun 18 03:00:41 MSK 2021
distributionBase=GRADLE_USER_HOME
distributionUrl=https\://services.gradle.org/distributions/gradle-6.7.1-bin.zip
distributionPath=wrapper/dists
zipStorePath=wrapper/dists
zipStoreBase=GRADLE_USER_HOME


text:
# Changelog
All notable changes to this project will be documented in this file.

The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).

## [0.3.2] - 2023-08-09
### Changed
- Make `decode/2` and `decode!/2` accept iodata instead of just Strings

## [0.3.1] - 2023-06-16
### Changed
- Bump `rustler` to 0.28 to support OTP 26

### Fixed
- Attempting to handle some specific errors no longer raises a new error

## [0.3.0] - 2023-03-15
### Added
- Support for compression via the `compress` encode option (#15, thanks @mmmries)

### Changed
- Errors returned from `encode/2` are now descriptive strings instead of a generic atom. Instead of `{:error, :encode_error}`, you may now see something like `{:error, "Expected to deserialize a UTF-8 stringable term"}`. This is technically a breaking change.

## [0.2.1] - 2022-11-06
### Added
- Precompiled binary support for `aarch64-unknown-linux-musl`

### Fixed
- Bump `rustler_precompiled` to 0.5.4 to avoid https://github.com/philss/rustler_precompiled/issues/38

## [0.2.0] - 2022-08-14
### Added
- Precompiled binaries via [rustler_precompiled](https://github.com/philss/rustler_precompiled) (#10, thanks @lytedev)

## [0.1.6] - 2021-03-11
### Fixed
- Prevent `:ok` and `:error` atoms from being encoded as capitalized strings, inconsistent with other atom encoding

## [0.1.5] - 2021-02-06
### Fixed
- Honor custom encodings in nested structs

## [0.1.4] - 2020-04-02
### Fixed
- Correct typespec in NIF stub that caused issues with Dialyzer

## [0.1.3] - 2019-12-02
### Changed
- Limit nesting depth to 128 again when decoding strings

## [0.1.2] - 2019-12-02
### Changed
- Make `decode` and `decode!` accept a second (unused) options argument for compatibility (#1, thanks @joedevivo)

## [0.1.1] - 2019-11-08
### Changed
- Support decoding strings with a nesting depth over 128

## 0.1.0 - 2019-11-03
### Added
- Initial release

[Unreleased]: https://github.com/benhaney/Jsonrs/compare/v0.3.2...HEAD
[0.3.2]: https://github.com/benhaney/Jsonrs/compare/v0.3.1...v0.3.2
[0.3.1]: https://github.com/benhaney/Jsonrs/compare/v0.3.0...v0.3.1
[0.3.0]: https://github.com/benhaney/Jsonrs/compare/v0.2.1...v0.3.0
[0.2.1]: https://github.com/benhaney/Jsonrs/compare/v0.2.0...v0.2.1
[0.2.0]: https://github.com/benhaney/Jsonrs/compare/v0.1.6...v0.2.0
[0.1.6]: https://github.com/benhaney/Jsonrs/compare/v0.1.5...v0.1.6
[0.1.5]: https://github.com/benhaney/Jsonrs/compare/v0.1.4...v0.1.5
[0.1.4]: https://github.com/benhaney/Jsonrs/compare/v0.1.3...v0.1.4
[0.1.3]: https://github.com/benhaney/Jsonrs/compare/v0.1.2...v0.1.3
[0.1.2]: https://github.com/benhaney/Jsonrs/compare/v0.1.1...v0.1.2
[0.1.1]: https://github.com/benhaney/Jsonrs/compare/v0.1.0...v0.1.1

repo_name: benhaney/Jsonrs

repo_language: Elixir


text:
defmodule Jsonrs.MixProject do
  use Mix.Project

  @version "0.3.2"

  def project do
    [
      app: :jsonrs,
      version: @version,
      elixir: "~> 1.9",
      start_permanent: Mix.env() == :prod,
      rustler_crates: rustler_crates(),
      deps: deps(),
      description: description(),
      package: package(),
      docs: docs(),
      source_url: "https://github.com/benhaney/jsonrs"
    ]
  end

  # Run "mix help compile.app" to learn about applications.
  def application do
    [
      extra_applications: [:logger]
    ]
  end

  # Run "mix help deps" to learn about dependencies.
  defp deps do
    [
      {:rustler_precompiled, "~> 0.6.1"},
      {:rustler, "~> 0.28.0", optional: true},
      {:ex_doc, "~> 0.27", only: :dev, runtime: false},
    ]
  end

  defp rustler_crates do
    [
      jsonrs: [path: "native/jsonrs"]
    ]
  end

  defp description() do
    """
    A fully-featured and performant JSON library powered by Rust
    """
  end

  defp package() do
    [
      maintainers: ["Ben Haney"],
      licenses: ["Unlicense"],
      links: %{"GitHub" => "https://github.com/benhaney/jsonrs"},
      files: ["lib", "mix.exs", "README*", "native/jsonrs/src", "native/jsonrs/.cargo", "native/jsonrs/README*", "native/jsonrs/Cargo*", "checksum-*.exs"]
    ]
  end

  defp docs() do
    [
      main: "readme",
      name: "Jsonrs",
      source_ref: "v#{@version}",
      canonical: "http://hexdocs.pm/jsonrs",
      source_url: "https://github.com/benhaney/jsonrs",
      extras: [
        "README.md"
      ]
    ]
  end
end


text:
# Publishing Jsonrs

From: https://hexdocs.pm/rustler_precompiled/precompilation_guide.html#recommended-flow

- Bump dep version in `mix.exs`
- `git tag v${mix_version}` the git tag must be `v` prepended to the Mix project version
- `git push --tags`
- Wait for the associated GitHub actions to finish
- Run `mix rustler_precompiled.download Jsonrs --all`
- Release the package to hex.pm `mix hex.publish` (making sure to include the correct files (**untested!**)


text:
# Jsonrs

A safe NIF-based JSON library for Elixir powered by Rust's Serde. [API Documentation](https://hexdocs.pm/jsonrs/Jsonrs.html).

## Installation

Add Jsonrs as a dependency in your `mix.exs` file.

```elixir
def deps do
  [{:jsonrs, "~> 0.3"}]
end
```

To avoid requiring an entire Rust toolchain for projects that use Jsonrs, pre-built binaries are provided via [Rustler Precompiled](https://github.com/philss/rustler_precompiled), which will download a platform-specific binary from the appropriate Github release during compilation. If you would like to avoid using the pre-built binaries, set the environment variable `FORCE_JSONRS_BUILD=true` when building.

## Summary

Jsonrs is much faster than other JSON libraries for Elixir, including other NIFs like jiffy.

It uses much less memory than other JSON libraries when operating in a mode with comparable features.

It has an API typical of Elixir JSON libraries. `decode/1` `encode/2` and `encode_to_iodata/2` are available along with their raising `!` counterparts, and structs can implement the `Jsonrs.Encoder` protocol to specify custom encoding.

Multiple operating modes allow you to turn off features you don't need for extra performance. In the default 2-pass mode, Jsonrs works like Jason and Poison and honors custom encoding of structs. In the opt-in 1-pass (_lean_) mode, Jsonrs will ignore custom encoding impls and operate more like jiffy.

## Encoder Design

Jsonrs is a 2-pass encoder by default.

The first pass involves mapping the input object according to any custom encodings implemented for types in the input. This is done in Elixir.

The second pass performs the actual encoding of the input to a JSON string. This is done in the Rust NIF.

If custom encoding definitions are not required, the first pass can be disabled entirely by passing `lean: true` in the encode opts. When operating in this mode, structs will always be encoded as if they were maps regardless of custom encoder implementations.

## Performance

Jsonrs has different performance characteristics in different modes.
In the default 2-pass mode, Jsonrs is comparable feature-wise to Jason or Poison and should always be much faster (~5-10x) and consume less memory (~3-30x) than either of them when working with any non-trivial JSON.
In lean mode, Jsonrs is comparable feature-wise to jiffy and should always be faster (~3x) and use less memory (~100x+) than it.

For example, here is a benchmark of Jsonrs's speed and memory consumption compared to other popular JSON libraries when encoding the 8MB [issue-90.json](https://github.com/devinus/poison/blob/a4208a6252f4e58fbcc8d9fd2f4f64c99e974cc8/bench/data/issue-90.json) from the Poison benchmark data.

![Speed comparison of JSON libraries](https://raw.githubusercontent.com/benhaney/Jsonrs/bd8a008bcee93a0418646e4a8b32b8e26492fe97/bench-speed.png)

![Memory comparison of JSON libraries](https://raw.githubusercontent.com/benhaney/Jsonrs/bd8a008bcee93a0418646e4a8b32b8e26492fe97/bench-memory.png)

It is easy to see that Jsonrs dramatically outperforms Poison and Jason, while Jsonrs-lean similarly outperforms jiffy.

## Quick Start

`Jsonrs.decode/1` takes a JSON string and turns it into an Elixir term.

`Jsonrs.encode/2` takes an Elixir term and a keyword list of options and turns the input term into a JSON string with behavior defined by the options. Valid options are:
* `lean`: disables the first encoder pass (default `false`)
* `pretty`: turns on pretty printing when `true` or a non-negative-integer specifying indentation size (default `false`)
* `compress`: turns on streaming compression when passed in.
  * Currently you can pass `:gzip` to get default level gzip compression
  * You can also pass `{:gzip, 0..9}` to get a specific level of gzip compression
  * Other compression forms may be accepted in the future

## Examples

### Basic usage
```elixir
iex> Jsonrs.encode!(%{"x" => [1, 2], "y" => 0.5})
"{\"x\":[1,2],\"y\":0.5}"

iex> Jsonrs.decode!("{\"x\":[1,2],\"y\":0.5}")
%{"x" => [1, 2], "y" => 0.5}

iex> Jsonrs.encode!(%{"x" => false, "y" => []}, pretty: true) |> IO.puts()
{
  "x": false,
  "y": []
}
```

### Defining a custom encoder

Implement `Jsonrs.Encoder` for your struct, with an `encode/1` function that returns any other type encodable by Jsonrs (it does not need to return a string).

For example:

```elixir
defimpl Jsonrs.Encoder, for: [MapSet, Range, Stream] do
  def encode(struct), do: Enum.to_list(struct)
end
```

## Limitations

Inherited from `serde_json`, decoding is limited to a nesting depth of 128. As per RFC 7159, section 9:
> An implementation may set limits on the maximum depth of nesting.

## Credits

Jsonrs is built on the backs of giants. It is connecting the Rust libraries [Serde_rustler](https://github.com/sunny-g/serde_rustler) and [Serde_json](https://github.com/serde-rs/json), exposing them to Elixir through [Rustler](https://github.com/rusterlium/rustler), and wrapping the NIF in an interface inspired by [Jason](https://github.com/michalmuskala/jason). Without these projects, Jsonrs probably wouldn't exist.


text:
name: Build precompiled NIFs

env:
  NIF_DIRECTORY: "native/jsonrs"
  SKIP_JSONRS_BUILD: "true"

on:
  push:
    tags:
      - '*'

defaults:
  run:
    working-directory: "./native/jsonrs"

jobs:
  build_release:
    name: NIF ${{ matrix.nif }} - ${{ matrix.job.target }} (${{ matrix.job.os }})
    runs-on: ${{ matrix.job.os }}
    strategy:
      fail-fast: false
      matrix:
        nif: ["2.16", "2.15", "2.14"]
        job:
          - { target: aarch64-unknown-linux-gnu   , os: ubuntu-20.04 , use-cross: true }
          - { target: aarch64-unknown-linux-musl  , os: ubuntu-20.04 , use-cross: true }
          - { target: aarch64-apple-darwin        , os: macos-11 }
          - { target: arm-unknown-linux-gnueabihf , os: ubuntu-20.04 , use-cross: true }
          - { target: riscv64gc-unknown-linux-gnu , os: ubuntu-20.04 , use-cross: true }
          - { target: x86_64-apple-darwin         , os: macos-11 }
          - { target: x86_64-unknown-linux-gnu    , os: ubuntu-20.04 }
          - { target: x86_64-unknown-linux-musl   , os: ubuntu-20.04 , use-cross: true }
          - { target: x86_64-pc-windows-gnu       , os: windows-2019 }
          - { target: x86_64-pc-windows-msvc      , os: windows-2019 }

    env:
      RUSTLER_NIF_VERSION: ${{ matrix.nif }}

    steps:
    - name: Checkout source code
      uses: actions/checkout@v2

    - name: Install prerequisites
      shell: bash
      run: |
        case ${{ matrix.job.target }} in
          arm-unknown-linux-*) sudo apt-get -y update ; sudo apt-get -y install gcc-arm-linux-gnueabihf ;;
          aarch64-unknown-linux-gnu) sudo apt-get -y update ; sudo apt-get -y install gcc-aarch64-linux-gnu ;;
        esac
    - name: Extract crate information
      shell: bash
      run: |
        echo "PROJECT_NAME=$(sed -n 's/^name = "\(.*\)"/\1/p' Cargo.toml | head -n1)" >> $GITHUB_ENV
        # Get the project version from mix.exs
        echo "PROJECT_VERSION=$(sed -n 's/^  @version "\(.*\)"/\1/p' ../../mix.exs | head -n1)" >> $GITHUB_ENV

    - name: Install Rust
      uses: actions-rs/toolchain@v1
      with:
        toolchain: stable
        target: ${{ matrix.job.target }}
        override: true
        profile: minimal

    - name: Show version
      shell: bash
      run: |
        gcc --version || true
        rustup -V
        rustup toolchain list
        rustup default
        cargo -V
        rustc -V
        rustc --print=cfg

    - name: Download cross
      uses: giantswarm/install-binary-action@v1.0.0
      if: ${{ matrix.job.use-cross }}
      with:
        binary: "cross"
        version: "v0.2.4"
        download_url: "https://github.com/cross-rs/cross/releases/download/${version}/cross-x86_64-unknown-linux-gnu.tar.gz"
        tarball_binary_path: "${binary}"
        smoke_test: "${binary} --version"

    - name: Build lib
      shell: bash
      run: |
        if [ "${{ matrix.job.use-cross }}" == "true" ]; then
          cross build --release --target=${{ matrix.job.target }}
        else
          cargo build --release --target=${{ matrix.job.target }}
        fi

    - name: Rename lib
      id: rename
      shell: bash
      run: |
        LIB_PREFIX="lib"
        case ${{ matrix.job.target }} in
          *-pc-windows-*) LIB_PREFIX="" ;;
        esac;
        # Figure out suffix of lib
        # See: https://doc.rust-lang.org/reference/linkage.html
        LIB_SUFFIX=".so"
        case ${{ matrix.job.target }} in
          *-apple-darwin) LIB_SUFFIX=".dylib" ;;
          *-pc-windows-*) LIB_SUFFIX=".dll" ;;
        esac;
        CICD_INTERMEDIATES_DIR=$(mktemp -d)
        # Setup paths
        LIB_DIR="${CICD_INTERMEDIATES_DIR}/released-lib"
        mkdir -p "${LIB_DIR}"
        LIB_NAME="${LIB_PREFIX}${{ env.PROJECT_NAME }}${LIB_SUFFIX}"
        LIB_PATH="${LIB_DIR}/${LIB_NAME}"
        # Copy the release build lib to the result location
        cp "target/${{ matrix.job.target }}/release/${LIB_NAME}" "${LIB_DIR}"
        # Final paths
        # In the end we use ".so" for MacOS in the final build
        # See: https://www.erlang.org/doc/man/erlang.html#load_nif-2
        LIB_FINAL_SUFFIX="${LIB_SUFFIX}"
        case ${{ matrix.job.target }} in
          *-apple-darwin) LIB_FINAL_SUFFIX=".so" ;;
        esac;
        LIB_FINAL_NAME="${LIB_PREFIX}${PROJECT_NAME}-v${PROJECT_VERSION}-nif-${RUSTLER_NIF_VERSION}-${{ matrix.job.target }}${LIB_FINAL_SUFFIX}"
        # Copy lib to final name on this directory
        cp "${LIB_PATH}" "${LIB_FINAL_NAME}"
        tar -cvzf "${LIB_FINAL_NAME}.tar.gz" "${LIB_FINAL_NAME}"
        # Passes the path relative to the root of the project.
        LIB_FINAL_PATH="${NIF_DIRECTORY}/${LIB_FINAL_NAME}.tar.gz"
        # Let subsequent steps know where to find the lib
        echo ::set-output name=LIB_FINAL_PATH::${LIB_FINAL_PATH}
        echo ::set-output name=LIB_FINAL_NAME::${LIB_FINAL_NAME}.tar.gz

    - name: "Upload artifact"
      uses: actions/upload-artifact@v2
      with:
        name: ${{ steps.rename.outputs.LIB_FINAL_NAME }}
        path: ${{ steps.rename.outputs.LIB_FINAL_PATH }}

    - name: Publish archives and packages
      uses: softprops/action-gh-release@v1
      with:
        files: |
          ${{ steps.rename.outputs.LIB_FINAL_PATH }}
      if: startsWith(github.ref, 'refs/tags/')


text:
name: CI

on:
  pull_request:
  push:
    branches: [ "master" ]

env:
  CARGO_TERM_COLOR: always
  FORCE_JSONRS_BUILD: true
  CARGO_INCREMENTAL: 0

permissions:
  contents: read

jobs:
  build:

    name: Build and test
    runs-on: ubuntu-latest

    steps:
    - uses: actions/checkout@v3
    - name: Set up Elixir
      uses: erlef/setup-beam@v1
      with:
        elixir-version: '1.14.3'
        otp-version: '25.x'
    - name: Restore Elixir dependencies cache
      uses: actions/cache@v3
      with:
        path: deps
        key: ${{ runner.os }}-mix-${{ hashFiles('**/mix.lock') }}
        restore-keys: ${{ runner.os }}-mix-
    - name: Restore Cargo cache
      uses: actions/cache@v3
      with:
        path: |
          ~/.cargo/registry/index/
          ~/.cargo/registry/cache/
          ~/.cargo/git/db/
        key: ${{ runner.os }}-cargo-${{ hashFiles('**/Cargo.lock') }}
    - name: Install dependencies
      run: mix deps.get
    - name: Run tests
      run: mix test


text:
[build.env]
passthrough = [
  "RUSTLER_NIF_VERSION"
]


text:
[package]
name = "jsonrs"
version = "0.3.2"
authors = []
edition = "2018"

[lib]
name = "jsonrs"
path = "src/lib.rs"
crate-type = ["dylib"]

[dependencies]
flate2 = "1.0"
rustler = "0.28.0"
serde = { version = "1.0", features = ["derive"] }
serde_json = "1.0"
serde_rustler = { git = "https://github.com/benhaney/serde_rustler", tag = "v0.0.7" }
serde-transcode = "1.1"
lazy_static = "1.0"


text:
# NIF for Elixir.Jsonrs

Implements `encode` and `decode` and exposes them as `Elixir.Jsonrs.encode!` and `Elixir.Jsonrs.decode!` respectively for use in an Elixir module.

Uses `serde_rustler` and `serde_json` (de)serializers to implement transcoding


text:
use rustler::NifUnitEnum;
use flate2::Compression;
use flate2::write::GzEncoder;
use std::io::{BufWriter, Write, Error};

#[derive(NifUnitEnum)]
pub enum Algs {
  None,
  Gzip,
}

pub trait BufWrapper: Write {
  fn get_buf(&mut self) -> Result<Vec<u8>, Error>;
}

impl BufWrapper for Vec<u8> {
  fn get_buf(&mut self) -> Result<Vec<u8>, Error> { Ok(self.to_vec()) }
}

impl BufWrapper for BufWriter<GzEncoder<Vec<u8>>> {
  fn get_buf(&mut self) -> Result<Vec<u8>, Error> {
    self.flush()?;
    self.get_mut().try_finish()?;
    Ok(self.get_ref().get_ref().to_vec())
  }
}

pub fn get_writer(opts: Option<(Algs, Option<u32>)>) -> Box<dyn BufWrapper> {
  match opts {
    Some((Algs::Gzip, None)) => Box::new(BufWriter::with_capacity(10_240, GzEncoder::new(Vec::new(), Compression::default()))),
    Some((Algs::Gzip, Some(lv))) => Box::new(BufWriter::with_capacity(10_240, GzEncoder::new(Vec::new(), Compression::new(lv)))),
    _ => Box::new(Vec::<u8>::new()),
  }
}


text:
use rustler::{Env, Error, Term};
mod compression;

rustler::init!("Elixir.Jsonrs", [encode, decode]);

#[rustler::nif(name = "nif_encode", schedule = "DirtyCpu")]
fn encode(term: Term, indent_size: Option<u32>, comp_opts: Option<(compression::Algs, Option<u32>)>) -> Result<String, Error> {
  let mut buf = compression::get_writer(comp_opts);
  let des = serde_rustler::Deserializer::from(term);
  match indent_size {
    None => serde_transcode::transcode(des, &mut serde_json::Serializer::new(&mut buf)),
    Some(inds) => {
      let indent = std::iter::repeat(" ").take(inds as usize).collect::<String>();
      let formatter = serde_json::ser::PrettyFormatter::with_indent(indent.as_bytes());
      serde_transcode::transcode(des, &mut serde_json::Serializer::with_formatter(&mut buf, formatter))
    }
  }.map_err(|e| Error::RaiseTerm(Box::new(format!("{}", e))))?;

  let output = buf.get_buf().map_err(|e| Error::RaiseTerm(Box::new(format!("{}", e))))?;

  unsafe { Ok(String::from_utf8_unchecked(output)) }
}

#[rustler::nif(name = "nif_decode", schedule = "DirtyCpu")]
fn decode<'a>(env: Env<'a>, string: String) -> Result<Term<'a>, Error> {
  serde_transcode::transcode(
    &mut serde_json::Deserializer::from_slice(string.as_bytes()),
    serde_rustler::Serializer::from(env)
  ).map_err(|e| e.into())
}


text:
[target.'cfg(target_os = "macos")']
rustflags = [
  "-C", "link-arg=-undefined",
  "-C", "link-arg=dynamic_lookup",
]

# See https://github.com/rust-lang/rust/issues/59302
[target.x86_64-unknown-linux-musl]
rustflags = [
  "-C", "target-feature=-crt-static"
]

[target.aarch64-unknown-linux-musl]
rustflags = [
  "-C", "target-feature=-crt-static"
]

[profile.release]
lto = true


text:
defmodule Jsonrs do
  @moduledoc """
  A JSON library powered by Rust's Serde through a NIF
  """

  source_url = Mix.Project.config()[:source_url]
  version = Mix.Project.config()[:version]

  use RustlerPrecompiled, otp_app: :jsonrs,
    base_url: "#{source_url}/releases/download/v#{version}",
    force_build: System.get_env("FORCE_JSONRS_BUILD") in ["1", "true"],
    targets: RustlerPrecompiled.Config.default_targets(),
    nif_versions: ["2.16", "2.15", "2.14"],
    version: version

  @type compression_algorithm :: :gzip | :none
  @type compression_level :: non_neg_integer()
  @type compression_options :: {compression_algorithm(), compression_level()}

  @spec nif_encode(term, non_neg_integer | nil, compression_options()) :: String.t()
  defp nif_encode(_input, _indent, _compression), do: :erlang.nif_error(:nif_not_loaded)

  @spec nif_decode(String.t()) :: term
  defp nif_decode(_input), do: :erlang.nif_error(:nif_not_loaded)

  @doc """
  Generates JSON corresponding to `input`.

  ## Examples

      iex> Jsonrs.encode(%{"x" => [1,2]})
      {:ok, "{\\"x\\":[1,2]}"}

      iex> Jsonrs.encode("\\xFF")
      {:error, \"Expected to deserialize a UTF-8 stringable term\"}
  """
  @spec encode(term, keyword) :: {:ok, String.t()} | {:error, String.t()}
  def encode(input, opts \\ []) do
    {:ok, encode!(input, opts)}
  rescue
    e -> {:error, error_string(e)}
  end

  @doc """
  Parses a JSON value from `input` string.

  ## Examples

      iex> Jsonrs.decode("{\\"x\\":[1,2]}")
      {:ok, %{"x" => [1, 2]}}

      iex> Jsonrs.decode("invalid")
      {:error, "expected value at line 1 column 1"}
  """
  @spec decode(iodata, Keyword.t()) :: {:ok, term} | {:error, String.t()}
  def decode(input, opts \\ []) do
    {:ok, decode!(input, opts)}
  rescue
    e -> {:error, error_string(e)}
  end

  @doc """
  Generates JSON corresponding to `input`.

  Similar to `encode/1` except it will raise in case of errors.

  ## Examples

      iex> Jsonrs.encode!(%{"x" => [1,2]})
      "{\\"x\\":[1,2]}"

      iex> Jsonrs.encode!("\\xFF")
      ** (ErlangError) Erlang error: \"Expected to deserialize a UTF-8 stringable term\"
  """
  @spec encode!(term, keyword) :: String.t()
  def encode!(input, opts \\ []) do
    {lean, opts} = Keyword.pop(opts, :lean, false)
    {indent, opts} = Keyword.pop(opts, :pretty, nil)
    {compression, _opts} = Keyword.pop(opts, :compress, :none)
    compression = validate_compression(compression)
    indent = if true == indent, do: 2, else: indent
    case lean do
      true -> input
      false -> Jsonrs.Encoder.encode(input)
    end
    |> nif_encode(indent, compression)
  end

  @doc """
  Parses a JSON value from `input` string.

  Similar to `decode/2` except it will raise in case of errors.

  ## Examples

      iex> Jsonrs.decode!("{\\"x\\":[1,2]}")
      %{"x" => [1, 2]}

      iex> Jsonrs.decode!("invalid")
      ** (ErlangError) Erlang error: "expected value at line 1 column 1"
  """
  @spec decode!(iodata, Keyword.t()) :: term
  def decode!(input, _opts \\ []), do: input |> IO.iodata_to_binary() |> nif_decode()

  @doc """
  Identical to `encode/1`. Exists to implement Phoenix interface and encodes to a single normal string.
  """
  @spec encode_to_iodata(term, keyword) :: {:ok, String.t()} | {:error, :encode_error}
  def encode_to_iodata(input, opts \\ []), do: encode(input, opts)

  @doc """
  Identical to `encode!/1`. Exists to implement Phoenix interface and encodes to a single normal string.
  """
  @spec encode_to_iodata!(term, keyword) :: String.t()
  def encode_to_iodata!(input, opts \\ []), do: encode!(input, opts)

  defp validate_compression(nil), do: {:none, nil}
  defp validate_compression(false), do: {:none, nil}
  defp validate_compression(atom) when is_atom(atom), do: {atom, nil}
  defp validate_compression(other), do: other

  defp error_string(%ErlangError{original: err}), do: error_string(err)
  defp error_string(err) when is_exception(err), do: Exception.message(err)
  defp error_string(err), do: err
end


text:
defprotocol Jsonrs.Encoder do
  @moduledoc """
  Protocol controlling how a value is encoded to JSON.

  By default, structs are encoded as maps without the `:__struct__` key. If this
  is sufficient for you use, you don't need to implement this protocol.

  When implementing an encoding function, the goal is to turn your value into
  something already capable of being encoded.

  ## Example

  An implementation of this protocol for `Decimal` might look something like

      defimpl Jsonrs.Encoder, for: Decimal do
        def encode(value) do
          Decimal.to_string(value)
        end
      end

  Which will cause the Decimal to be encoded as its string representation

  """

  @fallback_to_any true

  @doc """
  Converts `value` to a JSON-encodable type.
  """
  def encode(value)
end

defimpl Jsonrs.Encoder, for: Map do
  def encode(map), do: :maps.map(fn _, v -> Jsonrs.Encoder.encode(v) end, map)
end

defimpl Jsonrs.Encoder, for: List do
  def encode(list), do: Enum.map(list, &Jsonrs.Encoder.encode/1)
end

defimpl Jsonrs.Encoder, for: Tuple do
  def encode(tuple) do
    tuple |> Tuple.to_list() |> Jsonrs.Encoder.encode()
  end
end

defimpl Jsonrs.Encoder, for: [Date, Time, NaiveDateTime, DateTime] do
  def encode(d), do: d |> @for.to_iso8601()
end

defimpl Jsonrs.Encoder, for: URI do
  def encode(uri), do: URI.to_string(uri)
end

defimpl Jsonrs.Encoder, for: Any do
  def encode(s) when is_struct(s), do: s |> Map.from_struct() |> Jsonrs.Encoder.encode()
  def encode(any), do: any
end


text:
defmodule JsonrsTest do
  use ExUnit.Case
  doctest Jsonrs

  defmodule Container do
    defstruct [:payload]
  end

  describe "encodes" do
    test "simple map" do
      assert Jsonrs.encode!(%{"foo" => 5}) == ~s({"foo":5})
      assert Jsonrs.encode!({:ok, :error}) == ~s(["ok","error"])
    end

    test "struct using fallback protocol" do
      assert Jsonrs.encode!(%Container{payload: ~T[12:00:00]}) == ~s({"payload":"12:00:00"})
    end

    test "nested types" do
      assert Jsonrs.encode!(%{a: [3, {URI.parse("http://foo.bar"), ~T[12:00:00]}]}) == ~s({"a":[3,["http://foo.bar","12:00:00"]]})
    end

    test "prettily" do
      assert Jsonrs.encode!([1], pretty: 2) == "[\n  1\n]"
    end

    test "without custom protocols when lean" do
      assert "12:00:00" == Jsonrs.encode!(~T[12:00:00]) |> Jsonrs.decode!()
      assert %{"hour" => _, "minute" => _, "second" => _} = Jsonrs.encode!(~T[12:00:00], lean: true) |> Jsonrs.decode!()
    end

    test "with compress: :gzip" do
      assert zipped = Jsonrs.encode!(%{"foo" => 5}, compress: :gzip)
      assert :zlib.gunzip(zipped) == ~s({"foo":5})
    end

    test "with compress: {:gzip, level}" do
      for level <- 0..9 do
        assert zipped = Jsonrs.encode!(%{"Leslie" => "Pawnee"}, compress: {:gzip, level})
        assert :zlib.gunzip(zipped) == ~s({"Leslie":"Pawnee"})
      end
    end

    test "with compress and pretty" do
      assert zipped = Jsonrs.encode!([1], compress: :gzip, pretty: 2)
      assert :zlib.gunzip(zipped) == "[\n  1\n]"
    end

    test "with compress: false/nil" do
      assert Jsonrs.encode!(%{ron: "swanson"}, compress: false) == ~S({"ron":"swanson"})
      assert Jsonrs.encode!(%{ron: "swanson"}, compress: nil) == ~S({"ron":"swanson"})
    end

    test "with invalid compress options" do
      assert_raise ArgumentError, "argument error", fn ->
        Jsonrs.encode!(%{foo: "bar"}, compress: :zlib)
      end

      assert_raise ArgumentError, "argument error", fn ->
        Jsonrs.encode!(%{foo: "bar"}, compress: "Wat?!?!")
      end

      assert_raise ArgumentError, "argument error", fn ->
        Jsonrs.encode!(%{foo: "bar"}, compress: {:gzip, "foo"})
      end
    end
  end

  describe "decodes" do
    test "simple map" do
      assert Jsonrs.decode!(~s({"foo":5})) == %{"foo" => 5}
    end

    test "charlist" do
      assert Jsonrs.decode!('{"foo":5}') == %{"foo" => 5}
    end
  end
end


text: ExUnit.start()


text:
# DS_Jupyter

A course for B.Sc. students, Computer Engineering Department, Sharif University of Technology.

The course is instructed in Persian (Farsi) language.

All course materials (Slides, Jupyter Notebooks, Theory and Practical Assignments, Projects, etc.) are freely available under Creative Commons BY license.

# Copyright Notice

All materials are provided under Creative-Commons BY license. This course is crowd-sourced by a group of volunteer university students. If you noticed any copyright violation in texts, figures, etc., please report it by sending an email to sharifi@sharif.edu.

repo_language: Jupyter Notebook


text:
import os
import re

def tester(problem_name, f):
	input_path = "src/tests/" + problem_name + "/input/"
	output_path = "src/tests/" + problem_name + "/output/"
	regex = re.compile(r'input(\d+).txt')
	co = 1;
	num_tests = 0
	num_wrong = 0
	for file_name in os.listdir(input_path):
		m = regex.match(file_name)
		if not m:
			continue
		n = m.groups()[0]
		input_file_path = os.path.join(input_path, file_name)
		output_file_path = os.path.join(output_path, "output" + n + ".txt")
		if not os.path.isfile(output_file_path):
			print("output for input file " + input_file_path + "does not exist!")
			continue
		num_tests += 1
		with open(input_file_path) as input_file:
			with open(output_file_path) as output_file:
				input_params = []
				output = eval(output_file.readlines()[0])
				for line in input_file.readlines():
					input_params.append(eval(line))
				if not f(*input_params.copy()) == output:
					num_wrong += 1
	if num_wrong != 0:
		print("Your code get wrong answer in " + str(num_wrong) + " test(s) from " + str(num_tests) + " test(s).")
	else:
		print("Your code passes all " + str(num_tests) + " test(s).")


text:
# ---------------------------------------------------------------
#                            تعریف متغیر
# ---------------------------------------------------------------

# مقداردهی
# -------
x_int = 2
x_float = 2.3
x_bool = False
x_str1 = "i am a string"
x_str2 = 'i am a string too'
x_str3 = """i am a
alsdkfjaskldjfal
;alsdfjlasd;jdflsajkf
very long string"""

# نوع متغیر
# -------
type(x_int)
type(x_str1)
type(x_float)
type(x_bool)
isinstance(x_str3, str)

# عملیات
# -------
x_int + x_float
x_int + x_str1  # error
x_str1 + x_str2

# ---------------------------------------------------------------
#                            متغیرهای عددی
# ---------------------------------------------------------------
x, y, z, = 4, 1, 6
x / y  # تقسیم اعشاری
type(x / y)
x // y  # تقسیم صحیح
type(x // y)
x, y = y, x

# ---------------------------------------------------------------
#                            ورودی گرفتن
# ---------------------------------------------------------------
n = input()
type(n)
n_number = int(n)

# ---------------------------------------------------------------
#                            رشته‌ها
# ---------------------------------------------------------------

# تعریف
# -------
s1 = "workshop"
s2 = 'python workshop'
s3 = """hello """
s3 = """ hello
this is a python workshop
welcome everyone
"""

# عملیات
# -------
s1 + s2
s1 * 3
s1 + x  # error
s1 + str(x)
int('1234')
bool(1)
float("1234.8")

# دسترسی به اندیس‌ها
# -------
s = 'this is a python workshop'
s[0]
s[-1]
s[100]  # error
s[1:4]
s[1:6:2]
s[5:1928347]
s[9:5]
s[9:5:-1]
s[0] = 'H'  # error

# ************************************************
# تمرین
# برنامه‌ای بنویسید که یک رشته و دو عدد i و j بگیرد.
# سپس معکوس زیر رشته از اندیس کوچکتر تا عدد بزرگتر را چاپ کند.
# بدون استفاده از if
# ************************************************

# ************************************************
# جواب:

s = input()
i, j = int(input()), int(input())
higher = (i > j) * i + (j > i) * j
lower = (i > j) * j + (j > i) * i
s[higher:lower:-1]
# ************************************************

# رشته‌های فرمت‌دار
student_id = '96543210'
class_id = 40124
time = '13:30 - 15'
day = 'Saturday - Monday'

"hello %s" % student_id
"hello %s, welcome to %d" % (student_id, class_id)
"hello {}, welcome to {}, class is at {}, on {}".format(student_id, class_id, time, day)
"hello {student}, welcome to {class_no}, class is at {time}, on {day}".format(
    student=student_id, class_no=class_id, time=time, day=day
)

# توابع ویژه در رشته‌ها
# -------
s = 'this is a workshop. have FUNNNNNN!'
s.lower()
s.upper()
s.split(' ')
s.index('work')
s.find('work')
s.count('a')

# ************************************************
# تمرین
# برنامه‌ای بنویسید که
# در خط اول رشته‌ی S را ورودی بگیرد.
# و در خط دوم دو کلمه‌ی S1 و S2 که با فاصله از هم جدا شده اند را از ورودی بگیرد.
# سپس زیررشته‌ای از S، که از S1 شروع شود و به S2 ختم شود را چاپ کند.
# مثال:
# S = 'salam aleikom, hale shoma chetore? che khabara?'
# S1 = 'aleikom' S2 = 'shoma'
# output = 'aleikom, hale shoma'
# ************************************************

# ************************************************
# جواب:
S = input()
S1, S2 = input().split(" ")
start, end = S.find(S1), S.find(S2) + S2.__len__()
# or
start, end = S.find(S1), S.find(S2) + len(S2)
S[start:end]
# ************************************************

# ---------------------------------------------------------------
#                     ساختارهای شرطی و حلقه
# ---------------------------------------------------------------

# شرط
# --------
s = 'salam aleikom, aleikomossalam'
if len(s) < 20:
    pass
elif len(s) < 30:
    print("s is kinda short")
else:
    print("s isn't short")

# حلقه
# --------

# 1: while
i = 1
while i < 10:
    print(i)
    i += 1

# 2: for
# ۱: روی آرایه
s = 'python workshop'
for char in s:
    print(char, end=":")

# ۲: روی iterable
for i in range(0, 10):
    print(i, end="/")

for i in range(10):
    if i % 2 == 0:
        continue
    print(i)

for i in range(9, -1, -1):
    print(i)

# ************************************************
# تمرین
# برنامه‌ای بنویسید که دو رشته با طول برابر دریافت کند
# به عنوان خروجی رشته‌ای شامل حروف بزرگتر هر جایگاه را چاپ کند
# ************************************************

# ************************************************
# جواب:
x, y = input(), input()
output = ""

## 1
for i in range(len(x)):
    output += x[i] if x[i] > y[i] else y[i]

## 2
for (xi, yi) in zip(x, y):
    output += xi if xi > yi else yi
# ************************************************

# ************************************************
# تمرین
# با استفاده از while برنامه‌ای بنویسید که مقدار count را ورودی بگیرد.
# سپس از count تا 1 به پایین بدین صورت بشمارد:
# count > 1: [count] days left
# count == 1: [count] day left
# ************************************************

# ************************************************
# جواب:
count = int(input())
while count > 0:
    print("countdown, {number} day{plural} left".format(
        number=count, plural=(count > 1) * 's'
    ))
    count -= 1
# ************************************************

# ---------------------------------------------------------------
#                            لیست‌ها
# ---------------------------------------------------------------

# تعریف
# -------
l = [1, 6, -4, 4.2, 19 + 2j, 'workshop']

# اندیس‌ها عینا مانند رشته با تنها یک تفاوت:
# --------------------------------
l[1] = 123  # no error

# چند تابع کاربردی
# ------------

# ۱: اضافه کردن به لیست
l.append(100)
l.insert(5, 201)
l += [1, 7, 2, 2, 2]

# ۲: حذف کردن از لیست
l.remove(19 + 2j)
l.pop(5)

# ۳: سایر توابع
l.reverse()
l.sort()
l.count(2)

# مسائل عجیب در لیست‌ها!
# -------------------

# ۱: کپی کردن
l1 = l
l1[0] = 12309
l1
l  # !!!!

l1 = l.copy()
l1[0] = 394
l1
l  # ^_^

# ۲: مقداردهی اولیه

a = [0] * 10
a[2] = a[4] = a[5] = 123
print(a)  # منطقی

a = [0, 1, 2] * 5
a[0] = 123
print(a)  # بازم منطقی

a = [[0, 1, 2]] * 5
print(a)
a[0][0] = 123
print(a)  # !!!!

a = [[0, 1, 2] for i in range(5)]
print(a)
a[0][0] = 123
print(a)  # ^_^

# ************************************************
# تمرین
# برنامه‌ای بنویسید که در خط اول عدد n را ورودی بگیرد.
# سپس در n خط بعدی اعضای آرایه را ورودی بگیرد.
# در انتها آرایه را استفاده از روش حبابی مرتب کنید و تعداد حباب‌ها را بشمارید.
# ************************************************

# ************************************************
# جواب:

n = int(input())

a = [int(input()) for _ in range(n)]
# or
a = []
for i in range(n):
    a.append(int(input()))

count = 0
for i in range(n):
    for j in range(n - i - 1):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            count += 1
print(a)
print(count)
# ************************************************

# ************************************************
# تمرین
# برنامه‌ای بنویسید که در دو خط، دو آرایه‌ی n بعدی از ورودی بگیرد.
# در خروجی یک آرایه‌ی دوبعدی n در 2 از آن بسازد
# ************************************************

# ************************************************
# جواب:
a = list(map(int, input().split(" ")))
b = list(map(int, input().split(" ")))

# 1
output = []
for (ai, bi) in zip(a, b):
    output += [[ai, bi]]

# 2
output = []
for (ai, bi) in zip(a, b):
    output.append([ai, bi])

# 3
output = [[a[i], b[i]] for i in range(len(a))]
# ************************************************

# ************************************************
# تمرین
# برنامه‌ای بنویسید  اعضای int یک آرایه را در قالب یک آرایه‌ی جدید نمایش دهد
# ************************************************

# ************************************************
# جواب:
a = [2, 3, 'salam', None, 4, [1, 2, 3], 3.4, 1, 99]
print([x for x in a if isinstance(x, int)])
# ************************************************

# ---------------------------------------------------------------
#                   چند‌تایی‌های مرتب، مجموعه‌ها و دیکشنری
# ---------------------------------------------------------------

# چندتایی‌های مرتب: لیست غیرقابل تغییر
# ----------------------------
z = (10, 9, 8)  # کاربردش را بعدا خواهیم دید

z[0]
z[-1]
z[2] = 100  # error

# مجموعه‌ها: لیست با اعضاء متمایز
# ------------------------
s = {1, 2, 3, 3, 3, 3, (1, 2), "helloooooo"}
print(s)
print(4 in s)
print(3 in s)

# ۱: اضافه کردن به مجموعه
s.add(54)
print(s)

# ۲. حذف کردن از مجموعه
s.remove(3)
print(s)

# دیکشنری
# ------
a = {'salam': 'hello',
     40124: 'madaar',
     (1, 2, 3): [2, 4, 6],
     1: 10,
     'salam': 'hi'}  # مقادیر متمایز. آخرین مقدار قرار میگیره.

for key, value in a.items():
    print(key, ":", value)

# اضافه کردن به دیکشنری
a['khodafez'] = 'bye'
print(a)

# ************************************************
# تمرین
# برنامه‌ای بنویسید که معکوس یک دیکشنری را بدست بیاورد
# سپس از روی طول آن بفهمد که تابع نگاشت یک به یک بوده یا نه
# ************************************************

# ************************************************
# جواب:
a = {3: 9, -3: 9, 4: 16, 5: 25, 2: 4, -2: 4}

# 1
b = {}
for key, value in a.items():
    b[value] = key

# 2
b = {value: key for key, value in a.items()}

print(len(a) == len(b))
# ************************************************

# ************************************************
# تمرین
# برنامه‌ای بنویسید که تعدادی اسم و فامیل از ورودی بخواند
# سپس تشخیص بدهد در هر فامیل چند نفر متمایز هستند.
# ************************************************

# ************************************************
# جواب:
names = [['shabnam', 'sheikhha'], ['sheida', 'sheikhha'], ['abbas', 'sheikhha'], ['maria', 'faghihi']]
count = {}
for name, family in names:
    if family in count:
        count[family] += 1
    else:
        count[family] = 1
print(count)

# ************************************************

# ---------------------------------------------------------------
#                         توابع و کلاس‌ها
# ---------------------------------------------------------------

# توابع
# ------

# تعریف
def function_name(arg1, arg2, arg3="default_value"):
    # code
    return -1  # return value

def is_prime(num):
    for i in range(2, num // 2):
        if num % i == 0:
            return False
    return True

# کلاس‌ها
# ------
class student:
    def __init__(self, id):
        self.id = id
        self.classes = {}

    def add_class(self, class_no):
        self.classes[class_no] = -1

    def give_mark(self, class_no, mark):
        if class_no in self.classes.keys():
            self.classes[class_no] = mark
        else:
            print("student " + str(self.id) + " does not have this course.")

s = student(96106543)
s.add_class(40124)
s.add_class(40425)
s.give_mark(40124, 16)
s.give_mark(20123, 20)


text:
\relax
\providecommand\hyper@newdestlabel[2]{}
\providecommand\zref@newlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand*\HyPL@Entry[1]{}
\HyPL@Entry{0<</S/D>>}
\zref@newlabel{footdir@1}{\abspage{3}}
\zref@newlabel{footdir@3}{\abspage{3}}
\zref@newlabel{footdir@2}{\abspage{3}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces سر مار در خانه $[1,1]$ قرار دارد و دم آن از خانه $[1,3]$ خارج شده است.}}{4}{figure.1}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces جوابی که دکتر می‌گیرد 4 است.}}{4}{figure.2}}


text:
\documentclass[12pt,a4paper]{article}
\usepackage{tikz}
\usetikzlibrary{trees}
\usepackage{amsmath}
\usepackage{forest}
\usepackage{commons/course}

%\hidesolutions

\شروع{نوشتار}
\سربرگ{}{آزمون پایان‌ترم}{25 خرداد ۱۳۹8}{}

\vspace*{-2in}
\begin{center}
	به نام او
\end{center}
\vspace*{1.5in}
- امتحان از 120 نمره می‌باشد و نمره کامل این امتحان، 90 می‌باشد.\\
- هر سوال را در یک صفحه جدا پاسخ دهید و مشخصات خود را در هر صفحه بنویسید.\\
- طراح سوالات: دکتر شریفی، علیرضا اکبری، شبنم شیخها، پدرام خورسندی، آراد محمدی، آریا کوثری، امیر مجتبی صبور و متین خواجوی\\
\vspace*{-0.5in}
\section*{سوالات کوتاه‌پاسخ (30 نمره)}
\شروع{ابجد}

\فقره درستی یا نادرستی عبارت زیر را مشخص کنید. جواب خود را توجیه کنید.(10نمره)
\شروع{فقرات}
\فقره یک آرایه‌ی $n$تایی از اعداد داریم که با ۱۰۰ عملِ جابجایی مرتب می‌شود. می‌توان الگوریتمی از $O(n)$ ارائه داد که این آرایه را مرتب کند.
\فقره یک آرایه‌ی $n$تایی از اعداد طبیعی بین ۰ و
$n ^ 2 - 1$
داریم. می‌توان الگوریتمی از $O(n)$ ارائه داد که این آرایه را مرتب کند.
\فقره اگر رأسی در د.د.ج دو فرزند داشته باشد، آن‌گاه عنصر بعدی آن فرزند راست، و عنصر قبلی آن فرزند چپ  ندارد.
\فقره برای
$n \geq 3$
عبارت "د.د.ج با $n$ گره که از طریق درج $n$ عدد با چینش تصادفی ساخته شده باشد" با عبارت "د.د.ج با $n$ گره که به تصادف و با احتمال مساوی از میان د.د.ج‌های با $n$ گره انتخاب شده باشد" از نظر مفهومی فرقی ندارد.
\پایان{فقرات}
\فقره یک گراف جهت‌دار به عنوان ورودی به ما داده شده است اما از بدون دور بودن آن اطلاعی نداریم. الگوریتم مرتب‌سازی توپولوژیک را به گونه‌ای اصلاح کنید که در صورتی که گراف بدون دور است، ترتیب توپولوژیک آن را بیابد و در غیر این صورت اعلام کند که گراف دور دارد. زمان اجرای این الگوریتم باید بر اساس اندازه‌ی ورودی خطی باشد

توجه کنید که تنها با اصلاح الگوریتم می‌بایست این کار را انجام دهید و نمی‌توانید از الگوریتم بخصوص یافتن دور در گراف استفاده کنید. همچنین اگر چند الگوریتم برای مرتب‌سازی توپولوژیک می‌شناسید، الگوریتم مناسب را تشخیص داده و آنرا اصلاح کنید.(10 نمره)

\فقره پیچیدگی زمانی هر یک از توابع زیر را بنویسید.(10 نمره)

\begin{flushleft}
	\includegraphics[]{figs/f1}
	\includegraphics[]{figs/f2}
\end{flushleft}

\پایان{ابجد}

\newpage
\مسئله{مَمَّد در فینال لیگ قهرمانان اروپا(20 نمره)}
ممّد از سری دانشجوهایی است که به لباس هایش بسیار اهمیت می‌دهد و حوصله متین را همیشه با لباس‌ها و وسواس انتخاب لباس، سر می‌برد. وسواسش به حدی است که او تمام لباس های خود را بر اساس میزان علاقه‌اش به این لباس‌ها در کمدش و به صورت یک جدول $m*n$ مرتب کرده است. خاصیت این جدول این است که هر سطر از چپ به راست و هر ستون از بالا به پایین به صورت صعودی مرتب شده است. بعضی از نقاط این جدول می‌تواند $\infty$ باشد که به معنی عدم وجود لباسی در آن‌خانه است. (توجه کنید که مقدار $\infty$ از اعداد موجود در جدول بزرگتر است.) در زیر یک مثال از یک کمد $4*4$ آمده است:
\begin{center}
	\includegraphics[width=1.3in, height=1.2in]{figs/table}
\end{center}
به تازگی به دلیل زیاد بودن لباس‌ها ممد به مشکل خورده است و می‌خواهد تا برای کمدش سیستمی تعریف کند تا:

-	بی ارزش ترین لباس کمد را از کمد خارج کند. (تضمین می‌شود جدول خالی نیست.)(10 نمره)\\
-	یک لباس جدید را در کمد درج کند. (تضمین می‌شود جدول پر نیست.)(5 نمره)\\
-	فقط با استفاده از حافظه‌ی اضافی $O(1)$، فهرست مرتب‌شده‌ی لباس‌های قرار گرفته در یک جدول $n \times n$ را چاپ کند. توجه کنید وضعیت جدول بعد از اجرای الگوریتم به انتخاب شماست.(5 نمره)

ممد برای حل این مشکل در هفته قبل از فینال لیگ قهرمانان اروپا به متین مراجعه می‌کند و متین تنها به شرطی که ممد قول دهد با یکی از لباس‌های زیبایش به وسط مسابقه فینال برود قبول می‌کند تا مشکل او را حل کند.

متین 3 سوال را حل کرد و حال از شما نیز می‌خواهد حل کنید.\\
پیچیدگی زمانی دو بخش اول باید $O(m+n)$ باشد و خاصیت مرتب بودن جدول بعد از انجام هر عملیات حفظ شود. پیچیدگی زمانی بخش سوم $O(n^3)$ است. در هر بخش ثابت کنید پیچیدگی زمانی الگوریتم شما همان پیچیدگی زمانی خواسته شده است.\\
\\

\مسئله{واسه همه پیگیری‌هات مرسی(15 نمره)}
اکبر سلطانِ چندین ویلا در کُردان می‌باشد. وی که برای طراحی امتحان پایان‌ترم می‌بایست به متین کمک می‌کرد، پیگیری‌های زیادی از او بابت امتحان انجام داد و متین از آنجایی که یک جنتلمن واقعی است، برای تشکر از پیگیری‌های اکبر، می‌خواهد به او در یکی از مشکلاتش کمک کند.

نقشه‌ی کَردان یک گراف بدون جهت هم‌بند هست که راس‌های آن ویلاهای اکبر هستند و هر یال آن یک کوچه است که دو ویلا را به هم متصل می‌کند.(فرض نکنید گراف مسطح است، یعنی کوچه‌ها می‌توانند با پل یا تونل از هم عبور کنند) حال او با شروع از یک ویلای دلخواه  $v$ الگوریتم جستجوی سطح اول\lr{(BFS)} اجرا کرده است و درخت پوشایی که در نتیجه اجرای این الگوریتم به دست می‌آید را
$T_1$
نامیده است.همچنین بار دیگر با شروع از ویلای
$v$
الگوریتم جستجوی عمق اول\lr{(DFS)} را اجرا کرده است و درخت پوشایی که این بار بدست می‌آید را
$T_2$
نامیده است.

به اکبر کمک کنید ثابت کند که
$T_1$
و
$T_2$
با هم برابر هستند(یعنی مجموعه‌ی یال‌های برابری دارند) اگر و تنها اگر نقشه کُردان خود یک درخت باشد.
\\

\newpage
\مسئله {مسیریابی(15 نمره)}
در یک شهر $n$ تقاطع (میدان، چهارراه یا هر نوع تقاطع دیگر) که با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند، و $m$ خیابان که با شماره‌های ۱ تا $m$ شماره‌گذاری شده‌اند وجود دارد.
خیابان $i$ ام، تقاطع‌های با شماره‌ی $A_i$ و $B_i$ را به صورت دوطرفه به یک‌دیگر متصل می‌کند. هر تقاطع ممکن است به یک یا تعداد دل‌خواهی خیابان متصل باشد. در این شهر، می‌توان با عبور از خیابان‌ها بین هر دو تقاطع دلخواهی سفر کرد.

شما یک اپ مسیریابی توسعه داده‌اید. در این اپ، یک راننده دو تقاطع مبدا و مقصد را مشخص می‌کند و شما می‌بایست سریع‌ترین مسیر برای رسیدن به مقصد را مشخص کنید. برای سادگی کار، فرض کنید ترافیک خیابان‌ها و تقاطع‌ها در طول پیمودن مسیر ثابت است.
بر اساس اطلاعات دریافتی از همه‌ی رانندگان،  زمان پیمودن هر خیابان و تقاطع را تخمین زده‌اید. به طور دقیق‌تر، پیمودن خیابان $i$ ام از یک انتها به انتهای دیگر آن به اندازه‌ی $S_i$ ثانیه طول می‌کشد و تفاوتی ندارد که خیابان را در کدام جهت طی کنید.
هم‌چنین وقتی در مسیر  به یک تقاطع $j$ می‌رسیم، باید مدت زمان $T_j$ ثانیه در آن تقاطع صبر کنیم (مثلا متوسط زمان انتظار پشت چراغ قرمز). این موضوع برای تقاطع‌های مبدا و مقصد صادق نیست. تمام مقادیر $S_i$ و $T_j$ نامنفی است.

برای هر یک از دو حالت زیر، الگوریتم کارآمدی پیشنهاد دهید که با گرفتن اطلاعات شهر و یک مبدا و مقصد مشخص، کوتاه‌ترین مسیر بین مبدا و مقصد و زمان پیمودن مسیر را مشخص کند. اگر پاسخ شما برای حالت دوم درست باشد، نیازی به حل حالت اول نیست.
\شروع {ابجد}
\فقره اگر همه‌ی $S_i$ برابر ۱ و همه‌ی مقادیر $T_i$ برابر صفر باشد.(5 نمره)
\فقره در حالت کلی.(10 نمره)
\پایان {ابجد}

\مسئله{پیش از تابستان\footnote{به تقلید از سه‌گانه "پیش از" اثر ریچارد لینکلیتر}(20 نمره)}

سال پیش متین در هواپیمای مشهد به تهران بود که دکتر شریفی را دید و ناگهان تصمیم گرفت تا دستیار آموزشی شود. او خود را به دکتر معرفی کرد و به ایشان گفت که در تابستان به سفری طولانی خواهد رفت اما تا آن زمان می‌خواهد به ایشان در تیم تدریس دروس ارائه‌شده توسط ایشان کمک کند. دکتر با موافقت یکساله، درخواست او را مبنی بر دستیار آموزشی شدن قبول کرد و همکاری او با دکتر شروع شد.

حال زمان یکساله رو به پایان است و در این مدت متین متوجه شده است که دوست دارد برای زمان بیشتری دستیار ایشان باشد و علاقه زیادی به این کار پیدا کرده است، اما به دلیل نزدیکی تابستان و سفر پیش رو چاره‌ای جز خداحافظی نمی‌بیند.

دکتر شریفی رشته‌ای به طول $n$ را به او به عنوان یادگاری می‌دهد. این رشته شامل یک معما می‌باشد که با حل آن متین می‌تواند دوباره دستیار آموزشی شود. این معما به این صورت است که در این رشته، باید بزرگترین زیر رشته‌ای را بیابد که هم پیشوند، هم میانوند و هم پسوند باشد.

به متین کمک کنید تا در زمان $O(n)$ معما را حل کند. (میان‌وندِ یک رشته، یک زیررشته از آن است که شامل حرف اول و آخر رشته‌ی اصلی نباشد.)

\newpage
\مسئله{سَم(20 نمره)}
در طی مسیر دانشگاه تا خانه دکتر شریفی یک تالاب وجود دارد که ایشان را وادار میکند برای رفتن به دانشگاه، از این تالاب عبور کند. این تالاب با یک مربع به ضلع
$n$
توصیف میشود.
\\
درون این دریاچه ماری سمی زندگی میکند. این مار به شکل مسیری که هر راس از آن دقیقا یک خانه از جدول
$n \times n$
تالاب را پر میکند توصیف شده است. دم مار خارج از دریاچه قرار دارد و در صورت برخورد دکتر شریفی با سر مار، مار دکتر شریفی را نیش میزند. در زیر یک مثال از تالابی با $n=3$ آمده است.
\begin{figure}[h!]
	\centering
	\includegraphics[width=1.7in, height=1.7in]{figs/mar}
	\caption{سر مار در خانه $[1,1]$ قرار دارد و دم آن از خانه $[1,3]$ خارج شده است.}
\end{figure}
\\
برای یافتن سر مار، دستگاهی در اختیار دکتر شریفی قرار دارد. این دستگاه با دریافت یک مستطیل از تالاب تعداد دفعاتی که مار با مرز‌های مستطیل برخورد داشته را نشان می‌دهد. در شکل زیر یک مثال از زیر مستطیل مشخص شده توسط دکتر را مشاهده می‌کنید. دستگاه در پاسخ عدد ۴ را نشان می‌دهد که در شکل با ستاره مشخص شده است.
\\
\begin{figure}[h!]
	\centering
	\includegraphics[width=1.7in, height=1.7in]{figs/mar1}
	\caption{جوابی که دکتر می‌گیرد 4 است.}
\end{figure}
\\
الگوریتمی ارائه دهید که با
$O(lg~n)$
بار استفاده از دستگاه سر مار را بیابد.

\پایان{نوشتار}


text:
\documentclass[12pt,a4paper]{article}
\usepackage{tikz}
\usetikzlibrary{trees}
\usepackage{amsmath}
\usepackage{forest}
\usepackage{commons/course}

%\hidesolutions

\شروع{نوشتار}
\سربرگ{}{آزمون پایان‌ترم}{25 خرداد ۱۳۹8}{}

\vspace*{-2in}
\begin{center}
	به نام او
\end{center}
\vspace*{1.5in}
- امتحان از 120 نمره می‌باشد و نمره کامل این امتحان، 90 می‌باشد.\\
- هر سوال را در یک صفحه جدا پاسخ دهید و مشخصات خود را در هر صفحه بنویسید.\\
- طراح سوالات: دکتر شریفی، علیرضا اکبری، شبنم شیخها، پدرام خورسندی، آراد محمدی، آریا کوثری، امیر مجتبی صبور و متین خواجوی\\
\vspace*{-0.5in}
\section*{سوالات کوتاه‌پاسخ (30 نمره)}
\شروع{ابجد}

\فقره درستی یا نادرستی عبارت زیر را مشخص کنید. جواب خود را توجیه کنید.(10نمره)
\شروع{فقرات}
\فقره صحیح. \\
در چنین آرایه‌ای تعداد نابجایی‌ها حداکثر
$200n$
تاست، زیرا عناصری که جابجا نمی‌شوند با هم‌دیگر نابجایی ندارند. در ۱۰۰ عمل جابجایی، ۲۰۰ عنصر با هم جابجا می‌شوند که این ۲۰۰ عنصر هر کدام حداکثر با $n$ عنصر دیگر نابجایی دارند. می‌دانیم که الگوریتم
\lr{sort insertion}
به تعداد نابجایی‌ها عملیات انجام می‌دهد، پس با این الگوریتم می‌توان آرایه را در زمان $O(n)$ مرتب کرد.

\فقره صحیح. \\
اگر اعداد را به مبنای $n$ ببریم هر عدد به یک عدد دورقمی تبدیل می‌شود. حال می‌توان این اعداد را با
\lr{sort radix}
در $O(n)$ مرتب کرد.

\فقره غلط. \\
عنصر بعدی در زیردرخت فرزند راست قرار دارد. تمامی عناصر زیردرخت فرزند راست این رأسِ، از آن بزرگ‌ترند. کوچک‌ترین این عناصر، یعنی چپ‌ترین عنصر با شروع از ریشه، عنصر بعدی این رأس است. پس عنصر بعدی،
\textit{فرزند چپ}
نباید داشته باشد و فرزند راست داشتنِ آن مشکلی ایجاد نمی‌کند. به همین ترتیب می‌توان برای عنصر قبلی استدلال کرد.

\فقره غلط. \\
دو د.د.ج زیر را در نظر بگیرید. تعداد راه‌های ساختن سمت راست ۴ و سمت چپ ۱ است. برای همین احتمال ساختن د.د.ج سمت راست ۴ برابر ساختن د.د.ج سمت چپ است. در حالی که اگر همه‌ی درختان با ۵ گره را در نظر بگیریم و از بین آن‌ها یکی را انتخاب کنیم، احتمال انتخاب د.د.ج سمت راست با د.د.ج سمت چپ برابر است.
\begin{figure}[h!]
	\centering
	\includegraphics[width=0.4\linewidth]{figs/tree}
\end{figure}

\newpage
\پایان{فقرات}
\فقره از الگوریتمی استفاده می‌کنیم که در هر مرحله، راس با درجه ورودی صفر را پیدا می‌کند و آن راس و یالهای خروجی آنرا از گراف حذف می‌کند و این عملیات را به‌صورت \lr{iterative} انجام می‌دهد.\\
لم: در یک \lr{DAG} همواره حداقل یک راس با درجه ورودی صفر وجود دارد. \\
با توجه به لم، در هر مرحله الگوریتم، اگر راس با درجه ورودی صفر دیگر موجود نبود، یعنی گراف دور دارد. در غیر اینصورت ترتیب توپولوژیکال بدست می‌آید.

\فقره پیچیدگی زمانی به ترتیب: $O(n log n)$ و $O(n^3)$
\پایان{ابجد}

\مسئله{مَمَّد در فینال لیگ قهرمانان اروپا(20 نمره)}
- کوچکترین عضو در خانه [1,1] قرار دارد. حال این مقدار را خارج می‌کنیم و به جای آن $\infty$ می‌گذاریم. در ادامه برای بر قراری خاصیت جدول، $\infty$ را با کمینه دو خانه [1,2] یا [2,1] جایگزین می‌کنیم. حال مسئله ما به یک جدول $(m-1) \times n$ و یا $m \times (n-1)$ تبدیل می‌شود. پیچیدگی زمانی نیز از $O(m+n)$ می‌باشد زیرا حداکثر $3(m+n)$ عمل انجام می‌دهیم.

- در خانه \lr{[m,n]} بیشترین مقدار قرار دارد. در آن جا درج کرده و با عملیاتی مانند بخش قبل، عضو جدید را در جای درستش قرار می‌دهیم.
\\
- از آنجایی که در جدول قرار دارند، کافیست $n^2$ بار تابع بخش قبل را صدا بزنیم.

\مسئله{واسه همه پیگیری‌هات مرسی(15 نمره)}
اگر $G$ یک درخت باشد، با توجه به این که $T_1$ و $T_2$ هر دو درخت هستند باید دارای تمامی یال‌های $G$ باشند پس با هم برابر هستند.

برای ثابت کردن این که $G$ یک درخت است اگر $T_1$ و $T_2$ برابر باشند، از برهان خلف استفاده می‌کنیم و فرض خلف می‌کنیم که $G$ درخت نباشد. در این صورت $G$ حداقل حاوی یک دور به نام $C$ است که راس‌های آن  را به ترتیب دور $u_1$ تا $u_k$ می‌نامیم.

در $T_2$ هر $u_i$ و $u_{i+1}$ ای که در نظر بگیریم (و همچنین $u_k$ و $u_1$) یکی از آنها باید جد آن یکی باشد. زیرا در غیر این صورت (اگر آن که زودتر پیمایش شده $u_i$ باشد)، باید قبل از این که الگوریتم از $u_i$ خارج شود، $u_{i+1}$  پیمایش شود وگرنه با یال مستقیم $u_i$ به $u_{i+1}$ الگوریتم جستجوی عمق اول وارد آن می‌شد (پس به هر حال$u_{i+1}$ در زیردرخت $u_i$ است). پس تمامی رئوس $C$ در یک مسیر از ریشه به برگ در $T_2$ قرار دارند.

اما در اولین جایی که الگوریتم جستجوی سطح اول به راسی از $C$ به نام $u_j$ می‌رسد، اگر $u_{j-1}$ و $u_{j+1}$ قبلا علامت‌گذاری نشده‌باشند، همانجا دو شاخه برای رئوس $C$  در $T_1$ تولید می‌شود و اگر حداقل یکی از آنها از قبل علامت‌گذاری شده باشد، از قبل دو شاخه تولید شده‌اند (که یکی به $u_j$ رسیده و دیگری به یکی از همسایه‌هایش). پس تمامی رئوس $C$ در یک مسیر از ریشه به برگ در $T_1$ قرار نخواهند داشت. پس $T_1$ با $T_2$ متقاوت خواهد بود و فرض خلف باطل و حکم ثابت می‌شود.

\newpage
\مسئله {مسیریابی(15 نمره)}
شرایط قسمت الف یک گراف بدون وزن است بنابراین می‌توان به سادگی با الگوریتم \lr{BFS} این مسیر را پیدا کرد

در قسمت ب نیز با تغییر اندکی در الگوریتم \lr{Dijkstra} می‌توانیم به جواب برسیم. فرض کنیم مقدار کوتاه‌ترین فاصله‌ی هر راس را تا مبدا در آرایه‌ی $d$ ذخیره کرده‌ایم (همان آرایه‌ای که در طول الگوریتم تغییر می‌کند و در هر مرحله راس با کمترین مقدار $d$ را به مجموعه $S$ اضافه می‌کنیم). اگر بتوانیم در زمان $t$ به راس $x$ برسیم، در هنگام به روز رسانی آرایه ی برای همسایگان $x$ (مثلا راس $y$ با وزن یال $w$) دیگر زمان رسیدن به $y$ از طریق راس $x$ برابر با $d_x + w$  نخواهد بود؛ بلکه برابر با $d_x + T_x + w$ است و باید این مقدار را با مقدار کنونی $d_y$ مقایسه کنیم. البته برای راس شروع این قضیه برقرار نیست و این موضوع را باید «دستی» چک کنیم! هزینه زمانی این الگوریتم هم عیناً مانند الگوریتم دایکسترا است.

\مسئله{پیش از تابستان\footnote{به تقلید از سه‌گانه "پیش از" اثر ریچارد لینکلیتر}(20 نمره)}

رشته مورد نظر را هش می کنیم.ابتدا بلند ترین رشته ای را میبایم که هم پیشوند $A$ باشد و هم پسوند $A$ باشد.(این کار را به این صورت انجام می دهیم که به ازای هر طول رشته مانند $t$ با مقایسه هش ها ، می توانیم در $O(1)$ بفهمیم که رشته ی به طول $t$ به صورت پیشوند و پس وند ظاهر شده است یا نه).بعد از اینکه بلند ترین رشته را به دست آوردیم که هم پیشوند باشد هم پسوند، میتوانیم با الگوریتمی از $O(n)$ بفهمیم که این رشته به صورت میانوند ظاهر شده است یا خیر(با طی کردن کل رشته و مقایسه هش آن) اگر این رشته پیدا شده، به صورت میانوند نیز ظاهر شده بود، جواب ما پیدا شده است در غیر این صورت ، دومین بلند ترین زیر رشته که هم به صورت پیشوند آمده و هم به صورت پسوند، قطعا جواب مسئله است به صورت زیر:
\\
\includegraphics[width = \linewidth]{figs/1.jpg}\\

\newpage
\مسئله{سَم(20 نمره)}
ایده این سوال استفاده از \lr{binary search} می‌باشد. نکته دیگر این است اگر سر مار در مستطیل ما باشد جوابی که می‌گیریم فرد می‌باشد.
\\
حال کافیست هر بار نصف بخشی از تالاب را که جستجو نکرده‌ایم، بررسی کنیم و اگر جواب فرد بود همان بخش را ادامه می‌دهیم و در غیر این صورت، نصفه دیگر را. این کار را ادامه می‌دهیم تا در نهایت سر مار پیدا شود.

\پایان{نوشتار}


text:
% Course Assignment Style (v0.35)
% By: Hamid Zarrabi-Zadeh
% Licensed Under GPL

\usepackage{graphicx,comment,framed}
\usepackage{amsthm,amssymb,amsmath}
\usepackage[usenames,dvipsnames]{pstricks}
\usepackage{enumitem,xifthen,xparse}
\usepackage[margin=1in]{geometry}
\usepackage{hyperref}
\usepackage[localise=on]{xepersian}
\usepackage[noend]{algpseudocode}

%--------------------- Font settings ----------------------
\settextfont[Scale=1.0,ExternalLocation=fonts/,BoldFont=Y Nazanin 007 Bold.ttf]{Y Nazanin 007 regular.ttf}
\setdigitfont[Scale=1.0,ExternalLocation=fonts/,BoldFont=Y Nazanin 007 Bold.ttf]{Y Nazanin 007 regular.ttf}
%\setdigitfont[Scale=1.0]{XB Niloofar}
%\settextfont[Scale=1.2, ]{compset.ttf}
\defpersianfont\sayeh[Scale=1.0,ExternalLocation=fonts/]{XBKayhanPook.ttf}

%--------------------- page settings ----------------------

\parindent=0em
\setlength{\parskip}{.5em}

\renewcommand{\labelitemi}{$\small\bullet$}
\renewcommand{\arraystretch}{1.3}
\renewcommand{\thefootnote}{\scriptsize\arabic{footnote}}  % footnote number size

\g@addto@macro\normalsize{%
  \setlength\abovedisplayskip{.8em}
  \setlength\abovedisplayshortskip{.55em}
%  \setlength\belowdisplayskip{.8em}
%  \setlength\belowdisplayshortskip{.69em}
}

%-------------------------- Notations ------------------------------------

\newcommand{\IN}{\ensuremath{\mathbb{N}}}
\newcommand{\IZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\IQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\IR}{\ensuremath{\mathbb{R}}}
\newcommand{\IC}{\ensuremath{\mathbb{C}}}

\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\seq}[1]{\left< #1 \right>}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\card}[1]{\left|{#1}\right|}
\newcommand{\setcomp}[1]{\overline{#1}}
\newcommand{\provided}{\,:\,}
\newcommand{\divs}{\mid}
\newcommand{\ndivs}{\nmid}
\newcommand{\iequiv}[1]{\,\overset{#1}{\equiv}\,}
\newcommand{\imod}[1]{\allowbreak\mkern5mu(#1\,\,\text{به پیمانه‌ی})}

\newcommand{\poly}{\mathop{\mathrm{poly}}}
\newcommand{\polylog}{\mathop{\mathrm{\scriptsize polylog}}}
\newcommand{\lcm}{\mathop{\mathrm{lcm}}}

\newcommand{\lee}{\leqslant}
\newcommand{\gee}{\geqslant}
\renewcommand{\leq}{\lee}
\renewcommand{\le}{\lee}
\renewcommand{\geq}{\gee}
\renewcommand{\ge}{\gee}

%-------------------------- Commands ---------------------------

\def\farsi{\end{latin}}
\def\english{\begin{latin}}

\newcommand{\مهم}[1]{\textbf{#1}}
\renewcommand{\برچسب}{\label}

\newcommand{\REM}[1]{}
\renewcommand{\حذف}{\REM}
\newcommand{\لر}{\lr}
\newcommand{\کد}[1]{\lr{\tt #1}}
\newcommand{\پاورقی}[1]{\footnote{\lr{#1}}}

%------------------------ Environments ------------------------------------

\newtheorem{لم}{لم}
\newtheorem{قضیه}{قضیه‌ی}
\newtheorem{مشاهده}{مشاهده‌ی}
\newtheorem{تعریف}{تعریف}

\newcounter{probcnt}
\NewDocumentCommand{\مسئله}{m o}
	{\stepcounter{probcnt}\bigskip\medskip{
 	\large \bf مسئله‌ی \arabic{probcnt}. \ #1} \ \IfValueTF{#2}{[#2]}{}
 	\nopagebreak\par\medskip}

\newcommand{\fqed}[1]{\leavevmode\unskip\nobreak\quad\hspace*{\fill}{\ensuremath{#1}}}

\newenvironment{اثبات}
	{\begin{trivlist}\item[\hskip\labelsep{\em اثبات.}]}
	{\fqed{\square}\end{trivlist}}

\newcommand{\حل}[1]
	{\medskip\noindent{\bf حل.}\ #1 \fqed{\rhd}}

\newcommand{\hidesolutions}{\renewcommand{\حل}[1]{}}

%------------------------- Header -----------------------------

\newcommand{\heading}[4]{
\parindent=0em

\rightline{
\makebox[6em][c]{
\includegraphics[height=1.6cm]{commons/sharif.png}
}}
\vspace{-.5em}
{\scriptsize\bf دانشکده‌ی مهندسی کامپیوتر}
\hfill {\small
#4
}\\[-5.8em]
\leftline{\hfill\Large\bf
ساختمان داده‌ها و الگوریتم‌ها
}\\[.8em]
\leftline{\hfill\bf
نیم‌سال دوم 97-98
}\\[.8em]
\leftline{\hfill\bf
وقت امتحان: 3 ساعت
}\\
\hrule height .12em
\normalsize
\vspace{-.2em}
\makebox[5cm][r]{#1}
\hfill
\makebox[5cm][c]{\sayeh\large #2}
\hfill
\makebox[5cm][l]{\small #3}
\vspace{1mm}
\hrule height .1em
}

\newcommand{\سربرگ}[4]{\heading{#1}{#2}{#3}{#4}}

%---------------------------- General Style ------------------------------------

\renewcommand{\labelitemi}{$\small\bullet$}
\renewcommand{\usefont}[4]{}  % fix Persian font in pstricks

% --------------------------- Persian Enumerations --------------------------

\def\harfi#1{\expandafter\@harfi\csname c@#1\endcsname}  			% alef, b, p, t, c, j, ...
\def\abjad#1{\expandafter\@abjad\csname c@#1\endcsname}		% alef, b, j, d, h, ...
\def\adadi#1{\expandafter\@adadi\csname c@#1\endcsname}			%	yek, dow, se, chahar, ...

\def\@harfi#1{\beginR\@@harfi#1\endR}
\def\@@harfi#1{%
\ifcase#1\or الف\or ب\or پ\or ت\or ث\or ج\or چ\or ح\or خ\or د\or ذ\or ر\or ز\or ژ\else\@ctrerr\fi}

\def\@abjad#1{\beginR\@@abjad#1\endR}
\def\@@abjad#1{%
\ifcase#1\or الف\or ب\or ج\or د\or ه\or و\or ز\or ح\or ط\or ی\or ک\or ل\or م\or ن\else\@ctrerr\fi}

\def\@adadi#1{\beginR\@@adadi#1\endR}
\def\@@adadi#1{%
   \ifcase#1 یک\or دو\or سه\or چهاد\or پنج\or شش\or هفت\or هشت\or نه\or ده\else\@ctrerr\fi}

\newcounter{alef}
\newenvironment{ابجد}{
	\setcounter{alef}{0}
	\begin{list} {\abjad{alef})}
	{\usecounter{alef}}}
	{\end{list}}

\newenvironment{الفبا}{
	\setcounter{alef}{0}
	\begin{list} {\harfi{alef})}
	{\usecounter{alef}}}
	{\end{list}}

%--------------------- Headings ----------------------

\newcommand{\mytitle}[1]
{\bigskip{\bf\large{#1}}\nopagebreak\par\medskip}

\renewcommand{\ورودی}{\mytitle{ورودی}}
\newcommand{\خروجی}{\mytitle{خروجی}}
\newcommand{\محدودیت}{\mytitle{محدودیت‌ها}}
\newcommand{\نمونه}{\mytitle{ورودی و خروجی نمونه}}

% ------------------------------ Sample Input/Output --------------------------

% Bases on: https://github.com/admp/LIO-LaTeX/tree/master/other/neerc-acm

\def\s@tm@cr@s{%
\def\widthin##1{\exmpwidinf=##1\relax}\def\widthout##1{\exmpwidouf=##1\relax}%
\def\stretchin##1{\advance\exmpwidinf by ##1\relax}%
\def\stretchout##1{\advance\exmpwidouf by ##1\relax}%
}%

\newenvironment{example*}[3][]{%
\s@tm@cr@s\ttfamily\obeylines\obeyspaces\frenchspacing%\testst@r#1%
\newcommand{\exmp}[2]{%
\begin{minipage}[t]{#2}\rightskip=0pt plus 1fill\relax##1\medskip\end{minipage}&%
\begin{minipage}[t]{#3}\rightskip=0pt plus 1fill\relax##2\medskip\end{minipage}\\%
\hline}%
\begin{tabular}{|l|l|}
\hline
\multicolumn{1}{|c|}{\bf\rl{ورودی نمونه}}&%
\multicolumn{1}{|c|}{\bf\rl{خروجی نمونه}}\\%
\hline
}
{\end{tabular}}

\newenvironment{example}
	{\begin{example*}{.47\textwidth}{.475\textwidth}}
	{\end{example*}}


text:
Creators of each lesson:
- Comparison of Sorting Algorithms -> Arad Mohammadi
- Basic Data Structures -> Arya Kowsary
- Tree Storage and Traversal -> Alireza Akbari
- BST -> Mohammadreza Ahmadkhaniha
- Trie -> Rouzbeh Meshkin
- Heap -> Pedram Khorsandi, Matin Khajavi
- Binary Search -> Sadegh Mahdavi
- K Select -> Erfan Farhadi
- Hashing -> Alireza Mousavi
- DSU -> Amir Mojtaba Sabour
- Balanced BSTs -> Kiarash Banihashem
- Segment Tree -> Amir Hossein Maleki
- DFS and BFS -> Matin Khajavi
- Topological Sort -> Alireza Akbari, Erfan Farhadi


text:
import sys

def get_file_text(path):
    """ Returns file text by path"""
    file_io = open(path, "r")
    text = file_io.read()
    file_io.close()
    return text

def get_file_output(encoding="utf-8", path=sys.argv[-1], arg_string=""):
    """
    Returns answer file output
    :param encoding: to decode output in python3
    :param path: path of file to execute
    :return: list of strings
    """
    import subprocess

    proc = subprocess.Popen([sys.executable, path], stdin=subprocess.PIPE, stdout=subprocess.PIPE,
                            stderr=subprocess.STDOUT)
    if arg_string:
        for arg in arg_string.split("\n"):
            proc.stdin.write(bytearray(str(arg) + "\n", encoding))
            proc.stdin.flush()

    return list(map(lambda x: str(x.decode(encoding)), proc.communicate()[0].splitlines()))

def test_file_importable():
    """ Tests there is no obvious syntax errors"""
    path = sys.argv[-1]
    if not path.endswith(".py"):
        import os

        parent = os.path.abspath(os.path.join(path, os.pardir))
        python_files = [f for f in os.listdir(parent) if os.path.isfile(os.path.join(parent, f)) and f.endswith(".py")]
        for python_file in python_files:
            if python_file == "tests.py":
                continue
            check_importable_path(os.path.join(parent, python_file))
        return
    check_importable_path(path)

def check_importable_path(path):
    """ Checks that file is importable.
        Reports failure otherwise.
    """
    saved_input = patch_input()
    try:
        import_file(path)
    except:
        failed("The file contains syntax errors", test_file_importable.__name__)
        return
    finally:
        revert_input(saved_input)

    passed(test_file_importable.__name__)

def patch_input():
    def mock_fun(_m=""):
        return "mock"

    if sys.version_info[0] == 3:
        import builtins
        save_input = builtins.input
        builtins.input = mock_fun
        return save_input
    elif sys.version_info[0] == 2:
        import __builtin__
        save_input = __builtin__.raw_input
        __builtin__.raw_input = mock_fun
        __builtin__.input = mock_fun
        return save_input

def revert_input(saved_input):
    if sys.version_info[0] == 3:
        import builtins
        builtins.input = saved_input
    elif sys.version_info[0] == 2:
        import __builtin__
        __builtin__.raw_input = saved_input
        __builtin__.input = saved_input

def import_file(path):
    """ Returns imported file """
    if sys.version_info[0] == 2 or sys.version_info[1] < 3:
        import imp

        return imp.load_source("tmp", path)
    elif sys.version_info[0] == 3:
        import importlib.machinery

        return importlib.machinery.SourceFileLoader("tmp", path).load_module("tmp")

def import_task_file():
    """ Returns imported file.
        Imports file from which check action was run
    """
    path = sys.argv[-1]
    return import_file(path)

def test_is_not_empty():
    """
        Checks that file is not empty
    """
    path = sys.argv[-1]
    file_text = get_file_text(path)

    if len(file_text) > 0:
        passed()
    else:
        failed("The file is empty. Please, reload the task and try again.")

def test_text_equals(text, error_text):
    """
        Checks that answer equals text.
    """
    path = sys.argv[-1]
    file_text = get_file_text(path)

    if file_text.strip() == text:
        passed()
    else:
        failed(error_text)

def test_answer_placeholders_text_deleted(error_text="Don't just delete task text"):
    """
        Checks that all answer placeholders are not empty
    """
    windows = get_answer_placeholders()

    for window in windows:
        if len(window) == 0:
            failed(error_text)
            return
    passed()

def set_congratulation_message(message):
    """ Overrides default 'Congratulations!' message """
    print("#educational_plugin CONGRATS_MESSAGE " + message)

def failed(message="Please, reload the task and try again.", name=None):
    """ Reports failure """
    if not name:
        name = sys._getframe().f_back.f_code.co_name
    print("#educational_plugin " + name + " FAILED + " + message)

def passed(name=None):
    """ Reports success """
    if not name:
        name = sys._getframe().f_back.f_code.co_name
    print("#educational_plugin " + name + " test OK")

def get_answer_placeholders():
    """
        Returns all answer placeholders text
    """
    prefix = "#educational_plugin_window = "
    path = sys.argv[-1]
    import os

    file_name_without_extension = os.path.splitext(path)[0]
    windows_path = file_name_without_extension + "_windows"
    windows = []
    f = open(windows_path, "r")
    window_text = ""
    first = True
    for line in f.readlines():
        if line.startswith(prefix):
            if not first:
                windows.append(window_text.strip())
            else:
                first = False
            window_text = line[len(prefix):]
        else:
            window_text += line

    if window_text:
        windows.append(window_text.strip())

    f.close()
    return windows

def check_samples(samples=()):
    """
      Check script output for all samples. Sample is a two element list, where the first is input and
      the second is output.
    """
    for sample in samples:
        if len(sample) == 2:
            output = get_file_output(arg_string=str(sample[0]))
            if "\n".join(output) != sample[1]:
                failed(
                    "Test from samples failed: \n \n"
                    "Input:\n{}"
                    "\n \n"
                    "Expected:\n{}"
                    "\n \n"
                    "Your result:\n{}".format(str.strip(sample[0]), str.strip(sample[1]), "\n".join(output)))
                return
        set_congratulation_message("All test from samples passed. Now we are checking your solution on Stepik server.")

    passed()

def test_function(answer, func, *f_args):
    output = func(*f_args)
    if output != answer:
        failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format(f_args, output, answer))

def test_function2(answer, func, *f_args):
    output = func(*f_args)
    for i in answer:
        if i not in output:
            failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format(f_args, output, answer))

def run_common_tests(error_text="Please, reload file and try again"):
    test_is_not_empty()
    test_answer_placeholders_text_deleted()
    test_file_importable()


text:
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="ChangeListManager">
    <list default="true" id="c50db940-b2b0-4e6f-97f2-5e3555e8b69e" name="Default Changelist" comment="" />
    <option name="EXCLUDED_CONVERTED_TO_IGNORED" value="true" />
    <option name="SHOW_DIALOG" value="false" />
    <option name="HIGHLIGHT_CONFLICTS" value="true" />
    <option name="HIGHLIGHT_NON_ACTIVE_CHANGELIST" value="false" />
    <option name="LAST_RESOLUTION" value="IGNORE" />
  </component>
  <component name="FileEditorManager">
    <leaf>
      <file pinned="false" current-in-tab="true">
        <entry file="file://$PROJECT_DIR$/Comparison of Sorting Algorithms/Q1/task.py">
          <provider selected="true" editor-type-id="StudyEditor">
            <state>
              <EduEditorState>
                <MainEditorState relative-caret-position="17">
                  <caret line="1" column="4" selection-start-line="1" selection-start-column="4" selection-end-line="1" selection-end-column="36" />
                </MainEditorState>
              </EduEditorState>
            </state>
          </provider>
        </entry>
      </file>
    </leaf>
  </component>
  <component name="ProjectFrameBounds" extendedState="7">
    <option name="x" value="100" />
    <option name="y" value="40" />
    <option name="width" value="2800" />
    <option name="height" value="1840" />
  </component>
  <component name="ProjectView">
    <navigator currentView="Course" proportions="" version="1">
      <foldersAlwaysOnTop value="true" />
    </navigator>
    <panes>
      <pane id="ProjectPane" />
      <pane id="Course">
        <subPane>
          <expand>
            <path>
              <item name="course_preview2" type="a264ea2a:RootNode" />
              <item name="course_preview2" type="ed842865:CourseNode" />
            </path>
            <path>
              <item name="course_preview2" type="a264ea2a:RootNode" />
              <item name="course_preview2" type="ed842865:CourseNode" />
              <item name="Comparison of Sorting Algorithms" type="d53b8fed:LessonNode" />
            </path>
            <path>
              <item name="course_preview2" type="a264ea2a:RootNode" />
              <item name="course_preview2" type="ed842865:CourseNode" />
              <item name="Comparison of Sorting Algorithms" type="d53b8fed:LessonNode" />
              <item name="Q1" type="4928525d:TaskNode" />
            </path>
            <path>
              <item name="course_preview2" type="a264ea2a:RootNode" />
              <item name="course_preview2" type="ed842865:CourseNode" />
              <item name="Basic Data Structures" type="d53b8fed:LessonNode" />
            </path>
            <path>
              <item name="course_preview2" type="a264ea2a:RootNode" />
              <item name="course_preview2" type="ed842865:CourseNode" />
              <item name="Basic Data Structures" type="d53b8fed:LessonNode" />
              <item name="Q1" type="4928525d:TaskNode" />
            </path>
          </expand>
          <select />
        </subPane>
      </pane>
    </panes>
  </component>
  <component name="PropertiesComponent">
    <property name="last_opened_file_path" value="$PROJECT_DIR$" />
  </component>
  <component name="RunDashboard">
    <option name="ruleStates">
      <list>
        <RuleState>
          <option name="name" value="ConfigurationTypeDashboardGroupingRule" />
        </RuleState>
        <RuleState>
          <option name="name" value="StatusDashboardGroupingRule" />
        </RuleState>
      </list>
    </option>
  </component>
  <component name="SvnConfiguration">
    <configuration />
  </component>
  <component name="ToolWindowManager">
    <frame x="-6" y="-6" width="1513" height="973" extended-state="6" />
    <layout>
      <window_info active="true" content_ui="combo" id="Project" order="0" visible="true" weight="0.24948454" />
      <window_info id="Structure" order="1" weight="0.25" />
      <window_info anchor="bottom" id="Educational.CheckDetails" />
      <window_info anchor="bottom" id="Version Control" />
      <window_info anchor="bottom" id="Terminal" />
      <window_info anchor="bottom" id="Python Console" />
      <window_info anchor="bottom" id="Message" order="0" />
      <window_info anchor="bottom" id="Find" order="1" />
      <window_info anchor="bottom" id="Run" order="2" />
      <window_info anchor="bottom" id="Debug" order="3" weight="0.4" />
      <window_info anchor="bottom" id="Cvs" order="4" weight="0.25" />
      <window_info anchor="bottom" id="Inspection" order="5" weight="0.4" />
      <window_info anchor="bottom" id="TODO" order="6" />
      <window_info anchor="right" id="Task" visible="true" weight="0.3298969" />
      <window_info anchor="right" id="Commander" internal_type="SLIDING" order="0" type="SLIDING" weight="0.4" />
      <window_info anchor="right" id="Ant Build" order="1" weight="0.25" />
      <window_info anchor="right" content_ui="combo" id="Hierarchy" order="2" weight="0.25" />
    </layout>
  </component>
  <component name="editorHistoryManager">
    <entry file="file://$PROJECT_DIR$/Comparison of Sorting Algorithms/Q1/task.py">
      <provider selected="true" editor-type-id="StudyEditor">
        <state>
          <EduEditorState>
            <MainEditorState relative-caret-position="17">
              <caret line="1" column="4" selection-start-line="1" selection-start-column="4" selection-end-line="1" selection-end-column="36" />
            </MainEditorState>
          </EduEditorState>
        </state>
      </provider>
    </entry>
  </component>
</project>


text:
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="ProjectModuleManager">
    <modules>
      <module fileurl="file://$PROJECT_DIR$/.idea/course_preview2.iml" filepath="$PROJECT_DIR$/.idea/course_preview2.iml" />
    </modules>
  </component>
</project>