
\section{Introduction}\label{sec.intro}
\vspace{-2mm}
\looseness-1
Block-based visual programming environments are increasingly used nowadays to introduce computing concepts to novice programmers including children and $\textnormal{K-}12$ students. Led by the success of environments like Scratch~\cite{resnick2009scratch}, initiatives like \emph{Hour of Code} by \emph{Code.org}~\cite{hourofcode} (HOC) and online platforms like \emph{CodeHS.com}~\cite{codehscom},  block-based programming has become an integral part of introductory computer science education. Considering HOC alone, over one billion hours of block-based programming  activity has been performed so far by over 50 million unique students worldwide~\cite{hourofcode,wu2019zero}.

The societal need for enhancing $\textnormal{K-}12$ computing education has led to a surge of interest in developing AI-driven  systems for pedagogy of block-based programming~\cite{wang2017learning,price2017position,price2017isnap,weintrop2017comparing,maloney2008programming}. Existing works have studied various aspects of intelligent support, including providing real-time next-step hints when a student is stuck solving a task~\cite{piech15las,yi2017feasibility,paassen2018continuous,marwan2019impact,efremov2020zeroshot}, giving data-driven feedback about a student's misconceptions~\cite{singh2013automated,DBLP:conf/icml/PiechHNPSG15,price2017evaluation,rolim2017learning,wu2019zero}, and demonstrating a worked-out solution for a task when a student lacks the required programming concepts~\cite{zhi2019exploring}. An underlying assumption when providing such intelligent support is that afterwards the student can practice \emph{new similar tasks} to finally learn the missing concepts. However, this assumption is far from reality in existing systems---the programming tasks are typically hand-curated by experts/tutors, and the available set of tasks is limited. Consider HOC's \emph{Classic Maze} challenge~\cite{hourofcode_maze}, which provides a progression of $20$ tasks: Millions of students have attempted these tasks, yet when students fail to solve a task and receive assistance, they cannot practice similar tasks, hindering their ability to master the desired concepts. We seek to tackle this pedagogical challenge by developing techniques for synthesizing new programming tasks.

\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/intro/intro_hoc_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.58}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathLeft}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/mctsplots/hoc-G-mutation-6-22_run7/mctsplot_best_2M.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.58}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathRight}\textcode{)\{}\\
			\quad \quad \quad \textcode{turnRight}\\
			\quad \quad \textcode{\}}\\
			\quad \textcode{\}}\\
			\textcode{\}}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Illustration of our methodology for task \emph{Maze 16} from the \emph{Hour of Code: Classic Maze} challenge by \emph{Code.org}~\cite{hourofcode_maze}; the complete list of tasks with their specifications is in \figref{fig:dataset}.
	}
	\vspace{-3.5mm}
	\label{fig:intro.hoc}
\end{figure}

We formalize the problem of synthesizing visual programming tasks of the kind found in popular learning platforms like \emph{Code.org} (see \figref{fig:intro.hoc}) and \emph{CodeHS.com}  (see \figref{fig:intro.karel}). As input, we are given a reference task $\text{\textcode{T}}^{\textnormal{in}}$, specified as a visual puzzle, and its solution code $\text{\textcode{C}}^{\textnormal{in}}$. Our goal is to synthesize a set $\{(\text{\textcode{T}}^{\textnormal{out}}, \text{\textcode{C}}^{\textnormal{out}})\}$ of new tasks along with their solution codes that are \emph{conceptually similar} but \emph{visually dissimilar} to the input. This is motivated by the need for practice tasks that on one hand exercise the same concepts, while looking fresh in order to maintain student engagement.


When tackling the problem of synthesizing new tasks with the above desirable properties, three key challenges emerge. First, we are generating problems in a \emph{conceptual domain} with no \emph{well-defined procedure} that students follow to solve a task---consequently, existing work on educational problem generation in procedural domains does not apply in our setting~\cite{Andersen13,gulwani2014example}. Second, the mapping from the space of visual tasks to their solution codes is highly discontinuous; hence, template-based problem generation techniques~\cite{singh2012,polozov2015} that rely on directly mutating the input to generate new tasks is ineffective (see Section~\ref{sec.userstudy} where we use this approach as a baseline). Furthermore, such a direct task-mutation approach would require access to an automated solution synthesizer; however, state-of-the-art program synthesis techniques are not yet on par with experts and their minimal solutions~\cite{Bunel18,Devlin17,chen2018execution}. Third, the space of possible tasks and their solutions is potentially unbounded, and thus, any problem generation technique that relies on exhaustive enumeration is intractable~\cite{singh2012,Ahmed13,Alvin14}.

To overcome these challenges, we propose a novel methodology that operates by first mutating the solution code $\text{\textcode{C}}^{\textnormal{in}}$ to obtain a set of codes $\{\text{\textcode{C}}^{\textnormal{out}}\}$, and then performing symbolic execution over a code $\text{\textcode{C}}^{\textnormal{out}}$ to obtain a visual puzzle $\text{\textcode{T}}^{\textnormal{out}}$. Mutation is efficient by creating an abstract representation of $\text{\textcode{C}}^{\textnormal{in}}$ along with appropriate constraints and querying an SMT solver~\cite{BarrettTinelli2018}; any solution to this query is a mutated code $\text{\textcode{C}}^{\textnormal{out}}$. During symbolic execution, we use Monte Carlo Tree Search (MCTS) to guide the search over the (unbounded) symbolic execution tree. We demonstrate the effectiveness of our methodology by performing an extensive empirical evaluation and user study on a set of reference tasks from the \emph{Hour of code} challenge by \emph{Code.org} and the \emph{Intro to Programming with Karel} course by \emph{CodeHS.com}. In summary, our main contributions are:

\setlength{\leftmargini}{0.7em}
\begin{itemize}
\item We formalize the problem of synthesizing block-based visual programming tasks (Section~\ref{sec.problem}).
\item We present a novel approach for generating new visual tasks along with solution codes such that they are conceptually similar but visually dissimilar to a given reference task (Section~\ref{sec.approach}).
\item We demonstrate the effectiveness of our approach through an extensive empirical evaluation and user study on reference tasks from real-world programming platforms (Section~\ref{sec.simulations} and Section~\ref{sec.userstudy}).
\end{itemize}




















 












    





\section{Problem Formulation}\label{sec.problem}
\vspace{-2mm}
\textbf{The space of  tasks.} We define a task as a tuple $\text{\textcode{T}} := (\text{\textcode{T}}_\textnormal{vis}, \text{\textcode{T}}_\textnormal{store}, \text{\textcode{T}}_\textnormal{size})$, where $\text{\textcode{T}}_\textnormal{vis}$ denotes the visual puzzle,  $\text{\textcode{T}}_\textnormal{store}$ the available block types, and $\text{\textcode{T}}_\textnormal{size}$ the maximum number of blocks allowed in the solution code. For instance, considering the task $\text{\textcode{T}} := \text{\textcode{T}}^{\textnormal{in}}$ in \figref{fig:intro.hoc.t0}, $\text{\textcode{T}}_\textnormal{vis}$ is illustrated in \figref{fig:intro.hoc.t0}, $\text{\textcode{T}}_\textnormal{store} = \{\textnormal{\textsf{move}\xspace, \textsf{turnL}\xspace, \textcode{turnR}, \textsf{repeatUntilGoal}\xspace, \textsf{If}\xspace}\}$, and $\text{\textcode{T}}_\textnormal{size} = 4$.

\looseness-1\textbf{The space of codes.} The programming environment has a domain-specific language (DSL), which defines the set of valid codes $\ensuremath{\mathcal{C}}$ and is shown in \figref{fig:mutation.1}. A code $\text{\textcode{C}} \in \ensuremath{\mathcal{C}}$ is characterized by several properties, such as the set $\text{\textcode{C}}_{\textnormal{blocks}}$ of block types in $\text{\textcode{C}}$, the number of blocks $\text{\textcode{C}}_{\textnormal{size}}$, the depth $\text{\textcode{C}}_{\textnormal{depth}}$ of the corresponding Abstract Syntax Tree (AST), and the nesting structure $\text{\textcode{C}}_{\textnormal{struct}}$ representing programming concepts exercised by $\text{\textcode{C}}$. For instance, considering the code $\text{\textcode{C}} := \text{\textcode{C}}^{\textnormal{in}}$ in \figref{fig:intro.hoc.p0},  $\text{\textcode{C}}_{\textnormal{blocks}}=\{\textnormal{\textsf{move}\xspace, \textsf{turnL}\xspace, \textsf{repeatUntilGoal}\xspace, \textsf{If}\xspace}\}$, $\text{\textcode{C}}_{\textnormal{size}}=4$, $\text{\textcode{C}}_{\textnormal{depth}}=3$, and $\text{\textcode{C}}_{\textnormal{struct}} = \{\textcode{\textsc{Run}}\{\textsf{repeatUntilGoal}\xspace\{\textsf{If}\xspace\}\}\}$. 

Below, we introduce two useful definitions relating the task and code space.

\looseness-1\begin{definition}[Solution code] $\text{\textcode{C}}$ is a solution code for  $\text{\textcode{T}}$ if the following holds: $\text{\textcode{C}}$ successfully solves the visual puzzle $\text{\textcode{T}}_\textnormal{vis}$, $\text{\textcode{C}}_{\textnormal{blocks}}  \subseteq \text{\textcode{T}}_\textnormal{store}$, and $\text{\textcode{C}}_{\textnormal{size}} \leq \text{\textcode{T}}_\textnormal{size}$. $\ensuremath{\mathcal{C}}_{\text{\textcode{T}}}$ denotes the set of all solution codes for $\text{\textcode{T}}$.
\end{definition}

\begin{definition}[Minimality of a task] \label{def.minimality} Given  a solvable task $\text{\textcode{T}}$ with $|\ensuremath{\mathcal{C}}_\text{\textcode{T}}| \geq 1$ and a threshold $\delta \in \mathbb{N}$, the task is minimal if $\nexists \text{\textcode{C}} \in \ensuremath{\mathcal{C}}_\text{\textcode{T}}$ such that  $\text{\textcode{C}}_{\textnormal{size}} < \text{\textcode{T}}_\textnormal{size} - \delta$.
\end{definition}

\looseness-1Next, we introduce two definitions formalizing the notion of conceptual similarity. Definition~\ref{def.conceptualsimilarity} formalizes conceptual similarity of a task $\text{\textcode{T}}$ along with one solution code $\text{\textcode{C}}$.  
Since a task can have multiple solution codes, Definition~\ref{def.conceptualsimilarity.task} provides a stricter notion of conceptual similarity of a task $\text{\textcode{T}}$ for all its solution codes. These definitions are used in our objective of task synthesis in conditions (I) and (V) below.

\begin{definition}[Conceptual similarity of $(\text{\textcode{T}}, \text{\textcode{C}})$] \label{def.conceptualsimilarity}  Given a reference  $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$ and a threshold $\delta \in \mathbb{N}$, a task $\text{\textcode{T}}$ along with a solution code $\text{\textcode{C}}$ is conceptually similar to $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$ if the following holds: $\text{\textcode{T}}_\textnormal{store} = \text{\textcode{T}}^{\textnormal{in}}_\textnormal{store}$, $|\text{\textcode{T}}_\textnormal{size} - \text{\textcode{T}}^{\textnormal{in}}_\textnormal{size}| \leq \delta$, and $\text{\textcode{C}}_{\textnormal{struct}} = \text{\textcode{C}}^{\textnormal{in}}_{\textnormal{struct}}$.
\end{definition}

\begin{definition}[Conceptual similarity of $(\text{\textcode{T}}, \cdot)$] \label{def.conceptualsimilarity.task} Given a reference  $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$ and a threshold $\delta \in \mathbb{N}$, a task $\text{\textcode{T}}$ is conceptually similar to $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$ if the following holds: $\text{\textcode{T}}_\textnormal{store} = \text{\textcode{T}}^{\textnormal{in}}_\textnormal{store}$, $|\text{\textcode{T}}_\textnormal{size} - \text{\textcode{T}}^{\textnormal{in}}_\textnormal{size}| \leq \delta$, and $\forall \text{\textcode{C}} \in \ensuremath{\mathcal{C}}_\text{\textcode{T}}, \text{\textcode{C}}_{\textnormal{struct}} = \text{\textcode{C}}^{\textnormal{in}}_{\textnormal{struct}}$.
\end{definition}



\textbf{Environment domain knowledge.} We now formalize our domain knowledge about the block-based environment to measure \emph{visual dissimilarity} of two tasks, and capture some notion of \emph{interestingness and quality} of a task. Given tasks $\text{\textcode{T}}$ and $\text{\textcode{T}}'$, we measure their visual dissimilarity by an environment-specific function $\ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}_\textnormal{vis}, \text{\textcode{T}}'_\textnormal{vis}) \in [0, 1]$. Moreover, we measure generic quality of a task with function $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}_\textnormal{vis},\text{\textcode{C}}) \in [0, 1]$. We provide specific instantiations of $\ensuremath{\mathcal{F}_{\textnormal{diss}}}$  and $\ensuremath{\mathcal{F}_{\textnormal{qual}}}$ in our evaluation.

\textbf{Objective of task synthesis.} Given a reference task $\text{\textcode{T}}^{\textnormal{in}}$ and a solution code $\text{\textcode{C}}^{\textnormal{in}} \in \ensuremath{\mathcal{C}}_{\text{\textcode{T}}^{\textnormal{in}}}$ as input, we seek to generate a set $\{(\text{\textcode{T}}^{\textnormal{out}}, \text{\textcode{C}}^{\textnormal{out}})\}$ of new tasks along with solution codes that are \emph{conceptually similar} but \emph{visually dissimilar} to the input. 
Formally, given parameters $(\delta_{\textnormal{size}}, \delta_{\textnormal{diss}}, \delta_{\textnormal{qual}})$, our objective is to synthesize new tasks meeting the following conditions:
\vspace{-1.5mm}
\begin{enumerate}[(I)]
	\setlength{\itemsep}{2pt}
  	\setlength{\parskip}{0pt}
	\item $(\text{\textcode{T}}^{\textnormal{out}}, \text{\textcode{C}}^{\textnormal{out}})$ is conceptually similar to $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$ with threshold $\delta_{\textnormal{size}}$ in Definition~\ref{def.conceptualsimilarity}.
	\item $\text{\textcode{T}}^{\textnormal{out}}$ is visually dissimilar to $\text{\textcode{T}}^{\textnormal{in}}$ with margin $\delta_{\textnormal{diss}}$, i.e., $\ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}^{\textnormal{in}}_\textnormal{vis}, \text{\textcode{T}}^{\textnormal{out}}_\textnormal{vis}) \geq \delta_{\textnormal{diss}}$.
	\item $\text{\textcode{T}}^{\textnormal{out}}$ has a quality score above threshold $\delta_{\textnormal{qual}}$, i.e.,  $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^{\textnormal{out}}_\textnormal{vis},\text{\textcode{C}}^\textnormal{out}) \geq \delta_{\textnormal{qual}}$.


\end{enumerate}

In addition, depending on the use case, it is desirable that the new tasks satisfy the following criteria:
\vspace{-1.5mm}
\begin{enumerate}[(I)]
	\setcounter{enumi}{3}
	\setlength{\itemsep}{2pt}
  	\setlength{\parskip}{0pt}
	\item $\text{\textcode{C}}^{\textnormal{out}}$ is different from the input solution code, i.e., $\text{\textcode{C}}^{\textnormal{out}} \neq \text{\textcode{C}}^{\textnormal{in}}$.	
	\item $\text{\textcode{T}}^{\textnormal{out}}$ is conceptually similar to $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$ with threshold $\delta_{\textnormal{size}}$ in Definition~\ref{def.conceptualsimilarity.task}.
	\item $\text{\textcode{T}}^{\textnormal{out}}$ is minimal as per Definition~\ref{def.minimality} for a desired value of $\delta_{\textnormal{mini}}$ (e.g.,  $\delta_{\textnormal{mini}}=0$ or $\delta_{\textnormal{mini}}=1$).	



\end{enumerate}









































\section{Our Task Synthesis Algorithm}\label{sec.approach}
\vspace{-2mm}
\begin{wrapfigure}[6]{r}{0.50\textwidth}
  \centering
 
  \includegraphics[height=1.0cm]{fig/overview-pipeline/overview-pipeline.pdf}
 
  \caption{Stages in our task synthesis algorithm.}
  \label{fig:overviewofapproach}
\end{wrapfigure}
We now present the pipeline of our algorithm (see \figref{fig:overviewofapproach}), which takes as input a reference task $\text{\textcode{T}}^{\textnormal{in}}$ and its solution code $\text{\textcode{C}}^{\textnormal{in}}$, and generates a set $\{(\text{\textcode{T}}^{\textnormal{out}}, \text{\textcode{C}}^{\textnormal{out}})\}$ of new tasks with their solution codes. The goal is for this set to be conceptually similar to $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$, but for new tasks $\{\text{\textcode{T}}^{\textnormal{out}}\}$ to be visually dissimilar to $\text{\textcode{T}}^{\textnormal{in}}$. This is achieved by two main stages: (1)~mutation of $\text{\textcode{C}}^{\textnormal{in}}$ to obtain a set $\{\text{\textcode{C}}^{\textnormal{out}}\}$, and (2)~symbolic execution of each $\text{\textcode{C}}^{\textnormal{out}}$ to create a task $\text{\textcode{T}}^{\textnormal{out}}$. The first stage, presented in Section~\ref{sec.approach.mutation}, converts $\text{\textcode{C}}^{\textnormal{in}}$ into an abstract representation restricted by a set of constraints (\figref{fig:overviewofapproach}(a)), which must be satisfied by any generated $\text{\textcode{C}}^{\textnormal{out}}$ (\figref{fig:overviewofapproach}(b)). The second stage, described in Section~\ref{sec.approach.tasksynthesis}, applies symbolic execution on each code $\text{\textcode{C}}^{\textnormal{out}}$ to create a corresponding visual task $\text{\textcode{T}}^{\textnormal{out}}$ (\figref{fig:overviewofapproach}(c)) while using Monte Carlo Tree Search (MCTS) to guide the search in the symbolic execution tree.










\subsection{Code Mutation}\label{sec.approach.mutation}
\vspace{-1mm}
This stage in our pipeline mutates code $\text{\textcode{C}}^{\textnormal{in}}$ of task $\text{\textcode{T}}^{\textnormal{in}}$ such that its conceptual elements are preserved. Our mutation procedure consists of three main steps. First, we generate an abstract representation of $\text{\textcode{C}}^{\textnormal{in}}$, called \emph{sketch}. Second, we restrict the sketch with constraints that describe the space of its concrete instantiations. Although this formulation is inspired from work on generating algebra problems~\cite{singh2012}, we use it in the entirely different context of generating conceptually similar mutations of $\text{\textcode{C}}^{\textnormal{in}}$. This is achieved in the last step, where we use the sketch and its constraints to query an SMT solver~\cite{BarrettTinelli2018}; the query solutions are mutated codes $\{\text{\textcode{C}}^{\textnormal{out}}\}$ such that $\text{\textcode{C}}^{\textnormal{out}}_{\textnormal{struct}} = \text{\textcode{C}}^{\textnormal{in}}_{\textnormal{struct}}$ (see Definition~\ref{def.conceptualsimilarity}).

\textbf{Step 1: Sketch.} The sketch of code \text{\textcode{C}}, denoted by  \textcode{Q}, is an abstraction of $\text{\textcode{C}}$ capturing its skeleton and generalizing $\text{\textcode{C}}$ to the space of conceptually similar codes. \textcode{Q}, expressed in the language of \figref{fig:mutation.2}, is generated from $\text{\textcode{C}}$ with mapping $\ensuremath{\Omega}$. In particular, the map exploits the AST structure of the code: the AST is traversed in a depth-first manner, and all values are replaced with their corresponding sketch variables, i.e., \textnormal{action } \textcode{a}, \textnormal{bool } \textcode{b}, and \textnormal{iter } \textcode{x} are replaced with \textcode{A}, \textcode{B}, and \textcode{X}, respectively. In the following, we also use mapping $\ensuremath{\omega}(\cdot|~\text{\textcode{C}})$, which takes a sketch variable in \textcode{Q} and returns its value in \text{\textcode{C}}.

In addition to the above, we may extend a variable \textcode{A} to an \emph{action sequence} \textoverline{\textcode{A}}, since any \textcode{A} is allowed to be empty ($\phi$). We may also add an action sequence of length $\delta_{\textnormal{size}}$ at the beginning and end of the obtained sketch. As an example, consider the code in \figref{fig:mutation.4} and the resulting sketch in \figref{fig:mutation.5}. Notice that, while we add an action sequence at the beginning of the sketch (\textoverline{\textcode{A}}\textsubscript{1}), no action sequence is appended at the end because construct \textsf{repeatUntilGoal}\xspace renders any succeeding code unreachable.

\textbf{Step 2: Sketch constraints}. Sketch constraints restrict the possible concrete instantiations of a sketch by encoding the required semantics of the mutated codes. All constraint types are in \figref{fig:mutation.3}.

In particular, $\Delta_0$ restricts the size of the mutated code within $\delta_{\textnormal{size}}$. 
$\Delta_1$ specifies the allowed mutations to an action sequence based on its value in the code, given by $\ensuremath{\omega}(\textoverline{\textcode{A}}~|~\text{\textcode{C}})$. For instance, this constraint could result in converting all \textcode{turnLeft}~actions of a sequence to \textcode{turnRight}.
$\Delta_2$ restricts the possible values of the \textsf{repeat}\xspace~counter within threshold $\delta_{\textnormal{iter}}$.
$\Delta_3$ ensures that the \textsf{repeat}\xspace~counter is optimal, i.e., action subsequences before and after this construct are not nested in it.
$\Delta_4$ specifies the possible values of the \textsf{If}\xspace~condition based on its value in the code, given by $\ensuremath{\omega}(\textnormal{\textcode{B}}~|~\text{\textcode{C}})$.
$\Delta_5$ refers to constraints imposed on action sequences nested within conditionals. As an example, consider $\Delta_5$ in \figref{fig:mutation.6}, which states that if $\text{\textcode{B}}_{1}$ = \textcode{pathLeft}, then the nested action sequence must have at least one \textcode{turnLeft}~action, and the first occurrence of this action must not be preceded by a \textsf{move}\xspace~or \textcode{turnRight}, thus preventing invalid actions within the conditional.
$\Delta_6$ ensures minimality of an action sequence, i.e., optimality of the constituent actions to obtain the desired output. This constraint would, for instance, eliminate redundant sequences such as \textcode{turnLeft}, \textcode{turnRight}, which does not affect the output, or \textcode{turnLeft}, \textcode{turnLeft}, \textcode{turnLeft}, whose output could be achieved by a single \textcode{turnRight}. All employed elimination sequences can be found in the supplementary material.
The entire list of constraints applied on the solution code in \figref{fig:mutation.4} is shown in \figref{fig:mutation.6}.

\textbf{Step 3: SMT query.} For a sketch \textcode{Q} generated from code $\text{\textcode{C}}$ and its constraints, we pose the following query to an SMT solver: (sketch \textcode{Q}, \textcode{Q}-constraints). As a result, the solver generates a set of instantiations, which are conceptually similar to \text{\textcode{C}}. 
In our implementation, we used the Z3 solver~\cite{deMouraBjorner2008}. For the code in \figref{fig:mutation.4}, Z3 generated $66$ mutated codes in $0.8$s from an exhaustive space of $2,997$ possible codes with $\delta_{\textnormal{size}} = 2$. One such mutation is shown in \figref{fig:intro.hoc.p1}.

While this approach generates codes that are devoid of most semantic irregularities, it has its limitations. Certain irregularities continue to exist in some generated codes: An example of such a code included the action sequence \textsf{move}\xspace, \textcode{turnLeft}, \textsf{move}\xspace, \textcode{turnLeft},  \textsf{move}\xspace, \textcode{turnLeft},  \textsf{move}\xspace, \textcode{turnLeft}, which results in the agent circling back to its initial location in the task space. This kind of undesirable behaviour is eliminated in the symbolic execution stage of our pipeline.


\subsection{Symbolic Execution}\label{sec.approach.tasksynthesis}
\vspace{-1mm}
Symbolic execution~\cite{King1976} is an automated test-generation technique that symbolically explores execution paths in a program. During exploration of a path, it gathers symbolic constraints over program inputs from statements along the path. These constraints are then mutated (according to a search strategy), and an SMT solver is queried to generate new inputs that explore another path.

\looseness-1\textbf{Obtaining visual tasks with symbolic execution.}
This stage in our pipeline applies symbolic execution on each generated code $\text{\textcode{C}}^{\textnormal{out}}$ to obtain a suitable visual task $\text{\textcode{T}}^{\textnormal{out}}$. The program inputs of $\text{\textcode{C}}^{\textnormal{out}}$ are the agent's initial location/orientation and the status of the grid cells (\emph{unknown}, \emph{free}, \emph{blocked}, \emph{marker}, \emph{goal}), which is initially \emph{unknown}. Symbolic execution collects constraints over these from code statements. As in \figref{fig:symbolicexecution} for one path, symbolic execution generates a visual task for each path in $\text{\textcode{C}}^{\textnormal{out}}$.

However, not all of these tasks are suitable. For instance, if the goal is reached after the first \textsf{move}\xspace~in \figref{fig:intro.hoc.p1}, all other statements in $\text{\textcode{C}}^{\textnormal{out}}$ are not covered, rendering the task less suitable for this code. Na\"ively, symbolic execution could first enumerate all paths in $\text{\textcode{C}}^{\textnormal{out}}$ and their corresponding tasks, and then rank them in terms of suitability. However, solution codes may have an unbounded number of paths, which leads to \emph{path explosion}, that is, the inability to cover all paths with tractable resources.

\textbf{Guiding symbolic execution using Monte Carlo Tree Search (MCTS).}
To address this issue, we use MCTS~\cite{kocsis2006bandit} as a search strategy in symbolic execution with the goal of generating more suitable tasks with fewer resources---we define task suitability next. Symbolic execution has been previously combined with MCTS in order to direct the exploration towards costly paths~\cite{luckow2018monte}.
In the supplementary material, we provide an example demonstrating how MCTS could guide the symbolic execution in generating more suitable tasks.

\looseness-1
As previously observed~\cite{kartal2016data}, a critical component of effectively applying MCTS is to define an evaluation function that describes the desired properties of the output, i.e., the visual tasks. Tailoring the evaluation function to our unique setting is exactly what differentiates our approach from existing work. 
In particular, our evaluation function, \ensuremath{\mathcal{F}_{\textnormal{score}}}, distinguishes suitable tasks 
by assigning a score ($\in [0,1]$) to them, which guides the MCTS search. A higher \ensuremath{\mathcal{F}_{\textnormal{score}}}~indicates a more suitable task. Its constituent components are: (i) $\ensuremath{\mathcal{F}_{\textnormal{cov}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis},\text{\textcode{C}}^\textnormal{out}) \in \{0,1\}$, which evaluates to 1 in the event of complete coverage of code $\text{\textcode{C}}^{\textnormal{out}}$ by task $\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}$ and 0 otherwise; (ii) $\ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in [0,1]$, which evaluates the dissimilarity of $\text{\textcode{T}}^\textnormal{out}$ to $\text{\textcode{T}}^{\textnormal{in}}$ (see Section~\ref{sec.problem});
(iii) $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out},\text{\textcode{C}}^\textnormal{out}) \in [0,1]$, which evaluates the quality and validity of $\text{\textcode{T}}^\textnormal{out}$; (iv) $\ensuremath{\mathcal{F}_{\textnormal{nocrash}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}) \in \{0,1\}$, which evaluates to 0 in case the agent crashes into a wall and 1 otherwise; and (v) $\ensuremath{\mathcal{F}_{\textnormal{nocut}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}) \in \{0,1\}$, which evaluates to 0 if there is a \emph{shortcut sequence} of actions (\textcode{a} in Fig.~\ref{fig:mutation.1}) smaller than $\text{\textcode{C}}^\textnormal{out}_\textnormal{size}$
that solves \text{\textcode{T}}\textsuperscript{out} and 1 otherwise. \ensuremath{\mathcal{F}_{\textnormal{qual}}}~and~\ensuremath{\mathcal{F}_{\textnormal{nocut}}}~also resolve the limitations of our mutation stage by eliminating codes and tasks that lead to undesirable agent behavior. We instantiate \ensuremath{\mathcal{F}_{\textnormal{score}}}~in the next section.










\section{Experimental Evaluation}\label{sec.simulations}
\vspace{-2mm}
In this section, we evaluate our task synthesis algorithm on \textnormal{HOC}~and~\textnormal{Karel}~tasks. Our implementation is publicly available.\footnote{\href{https://github.com/adishs/neurips2020_synthesizing-tasks_code}{https://github.com/adishs/neurips2020\_synthesizing-tasks\_code}\label{footnote.githubrepo}} While we give an overview of key results here, a detailed description of our setup and additional experiments can be found in the supplementary material.

\vspace{-2mm}
\subsection{Reference Tasks and Specifications}
\vspace{-1mm}
\textbf{Reference tasks.} We use a set of ten reference tasks from \textnormal{HOC}~and~\textnormal{Karel}, shown in \figref{fig:dataset}. The \textnormal{HOC}~tasks were selected from the \textit{Hour of Code: Classic Maze} challenge by \textit{Code.org}~\cite{hourofcode_maze} and the Karel tasks from the \textit{Intro to Programming with Karel} course by \textit{CodeHS.com}~\cite{intro_to_karel_codehs}. The DSL of \figref{fig:mutation.1} is generic in that it includes both HOC and Karel codes, with the following differences: (i)~construct \textsf{while}\xspace, marker-related actions \textsf{put}\xspace, \textsf{pick}\xspace, and conditions \textcode{noPathA}, \textcode{noPathL}, \textcode{noPathR}, \textcode{marker}, \textcode{noMarker}~are specific to Karel only; (ii)~construct \textsf{repeatUntilGoal}\xspace and \textcode{goal} are specific to HOC only. Furthermore, the puzzles for HOC and Karel are of different styles (see \figref{fig:intro.hoc} and \figref{fig:intro.karel}). 
For all tasks, the grid size of the puzzles is fixed to $10\times10$ cells (grid-size parameter $n = 10$). 



\textbf{Specification of scoring functions.} $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out},\text{\textcode{C}}^\textnormal{out}) \in [0,1]$ was approximated as the sum of the normalized counts of `moves', `turns', `segments', and `long-segments' in the grid; segments and long-segments are sequences of $\geq 3$ and $\geq 5$ \textsf{move}\xspace actions respectively. 
More precisely, for \textnormal{HOC}~tasks, we used the following function where features are computed by executing $\text{\textcode{C}}^\textnormal{out}$ on $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{qual}}}^{\textnormal{HOC}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out},\text{\textcode{C}}^\textnormal{out}) & = \frac{1}{4}\Big{(} \frac{\ensuremath{\#}\text{moves}}{2n} +  \frac{\ensuremath{\#}\text{turns}}{n} +  \frac{\ensuremath{\#}\text{segments}}{n/2} +  
    \frac{\ensuremath{\#}\text{long-segments}}{n/3} \Big{)}.
\end{align*}
Furthermore, in our implementation, $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\cdot)$ value was set to $0$ when $\ensuremath{\mathcal{F}_{\textnormal{nocrash}}}(\cdot) = 0$. 
For \textnormal{Karel}~tasks, \ensuremath{\mathcal{F}_{\textnormal{qual}}}~additionally included the normalized counts of \textsf{put}\xspace and \textsf{pick}\xspace, and is provided in the supplementary material.
$\ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in [0,1]$ was computed based on the dissimilarity of the agent's initial location/orientation w.r.t. $\text{\textcode{T}}_\textnormal{vis}^\textnormal{in}$, and the grid-cell level dissimilarity based on the Hamming distance between $\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}$ and $\text{\textcode{T}}_\textnormal{vis}^\textnormal{in}$. More precisely, we used the following function:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) & = \frac{1}{3}\Big{(}
    \textnormal{diss}(\textnormal{loc}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) +  \textnormal{diss}(\textnormal{dir}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) + 
    \textnormal{diss}(\textnormal{grid-cells}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in})
    \Big{)}
\end{align*}
where $\textnormal{diss}(\textnormal{loc}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in \{0, 1\}$, $\textnormal{diss}(\textnormal{dir}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in \{0, 1\}$, and $\textnormal{diss}(\textnormal{grid-cells}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in [0, 1]$ (after the Hamming distance is normalized with a factor of $\frac{2}{n^2}$). 


Next, we define the evaluation function $\ensuremath{\mathcal{F}_{\textnormal{score}}}(\text{\textcode{T}}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}, \text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}}) \in [0,1]$ used by MCTS:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{score}}}(\text{\textcode{T}}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}, \text{\textcode{T}}^\textnormal{in}, \text{\textcode{C}}^\textnormal{in}) & = \underbrace{\mathbbm{1}{\big(\medmath{ \ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) \geq \delta_{\textnormal{qual}}, \ensuremath{\mathcal{F}_{\textnormal{nocrash}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) = 1, \ensuremath{\mathcal{F}_{\textnormal{nocut}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) = 1 }\big)}}_\text{(i)} \cdot \\
    & \ \ \ \ \underbrace{\big[ \alpha_{1}\ensuremath{\mathcal{F}_{\textnormal{cov}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) + \alpha_{2}\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) + \alpha_{3} \ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{T}}^\textnormal{in}_\textnormal{vis}) \big]}_\text{(ii)}
\end{align*}
where $\mathbbm{1}$ is an indicator function and each constant $\alpha = 1/3$. 
Component (ii) in the above function supplies the gradients for guiding the search in MCTS; Component (i) is applied at the end of the MCTS run to pick the output.  More precisely, the \textit{best} task (i.e, the one with the highest \ensuremath{\mathcal{F}_{\textnormal{score}}}~value) is picked only from the pool of generated tasks which have $\ensuremath{\mathcal{F}_{\textnormal{score}}}(\cdot) > 0$ and satisfy $\ensuremath{\mathcal{F}_{\textnormal{cov}}}(\cdot) = 1$.

\looseness-1\textbf{Specification of task synthesis and MCTS.}  As per Section~\ref{sec.problem}, we set the following thresholds for our algorithm: (i) $\delta_\textnormal{size} = 2$, (ii) $\delta_\textnormal{diss} = 0.33$, and (iii) $\delta_\textnormal{qual}=0.2$ for codes with \textsf{while}\xspace or \textsf{repeatUntilGoal}\xspace, and $0.05$ otherwise.  We run MCTS $10$ times per code, with each run generating one task.
We set the maximum iterations of a run to $2$ million (M) and the exploration constant to $2$~\cite{kocsis2006bandit}. Even when considering a tree depth of $2n~(= 20)$, there are millions of leaves for difficult tasks \textsf{H4}\xspace~and \textsf{H5}\xspace, reflecting the complexity of task generation.  For each code $\text{\textcode{C}}^{\textnormal{out}}$, we generated $10$ different visual tasks. To ensure sufficient diversity among the tasks generated for the same code, we introduced a measure \ensuremath{\mathcal{F}_{\textnormal{diversity}}}. This measure, not only ensures visual task dissimilarity, but also ensures sufficient diversity in entire symbolic paths during generation (for details, see supplementary material).

\vspace{-2mm}
\subsection{Results}
\looseness-1\textbf{Performance of task synthesis algorithm.}
\figref{fig:experiments.analysis} shows the results of our algorithm. The second column illustrates the enormity of the unconstrained space of mutated codes; we only impose size constraint $\Delta_0$ from \figref{fig:mutation.3}. We then additionally impose constraint $\Delta_1$ resulting in a partially constrained space of mutated codes (column 3), and finally apply all constraints from \figref{fig:mutation.3} to obtain the final set of generated codes (column 4). This reflects the systematic reduction in the space of mutated codes by our constraints. Column 5 shows the total running time for generating the final codes, which denotes the time taken by Z3 to compute solutions to our mutation query. As discussed in Section~\ref{sec.approach.mutation}, few codes with semantic irregularities still remain after the mutation stage. The symbolic execution stage eliminates these to obtain the reduced set of valid codes (column 6). Column 7 shows the final number of generated tasks and column 8 is the average time per output task (i.e., one MCTS run).


\begin{figure}[t!]
\centering

	\scalebox{0.85}{
	\setlength\tabcolsep{2pt}
	\renewcommand{\arraystretch}{1.1}
	\begin{tabular}{c||rrrr||rrr||rrr}
			\toprule
			Task & \multicolumn{4}{c||}{Code Mutation} & \multicolumn{3}{c||}{Symbolic Execution} & \multicolumn{3}{c}{Fraction of $\text{\textcode{T}}^{\textnormal{out}}$ with criteria} \\
			    \multicolumn{1}{c||}{$\text{\textcode{T}}^{\textnormal{in}}$} & \multicolumn{1}{r}{\textbf{2:}$\#\text{\textcode{C}}^{\textnormal{out}}_{\Delta=\textnormal{0}}$} & \multicolumn{1}{r}{\textbf{3:}$\#\text{\textcode{C}}^{\textnormal{out}}_{\Delta=\textnormal{0,1}}$} & \multicolumn{1}{r}{\textbf{4:}$\#\text{\textcode{C}}^{\textnormal{out}}_{\Delta=\textnormal{all}}$} & \multicolumn{1}{r||}{\textbf{5:}Time} & \multicolumn{1}{r}{\textbf{6:}$\#\text{\textcode{C}}^{\textnormal{out}}$} & \multicolumn{1}{r}{\textbf{7:}$\#\text{\textcode{T}}^{\textnormal{out}}$} & \multicolumn{1}{r||}{\textbf{8:}Time} & \multicolumn{1}{r}{\textbf{9:}(V)} & \multicolumn{1}{r}{\textbf{10:}$\textnormal{(VI)}_{\delta_{\textnormal{mini}}=1}$} & \multicolumn{1}{r}{\textbf{11:}$\textnormal{(VI)}_{\delta_{\textnormal{mini}}=0}$} \\
			   
			\toprule
			\textsf{H1}\xspace & $3,159$ & $112$ & $64$ & $0.6$s & $28$ & $272$ & $68$s & $1.00$ & $1.00$ & $1.00$\\
			\textsf{H2}\xspace & $8,991$ & $594$ & $138$ & $1.7$s & $48$ & $428$ & $61$s & $1.00$ & $1.00$ & $1.00$\\
			\textnormal{H3} & $798,255$ & $13,122$ & $720$ & $13.3$s & $196$ & $1,126$ & $60$s & $0.90$ & $0.98$ & $0.90$\\
			\textsf{H3}\xspace & $5,913$ & $152$ & $108$ & $1.0$s & $44$ & $404$ & $167$s & $1.00$ & $1.00$ & $0.50$\\
			\textsf{H4}\xspace & $2,997$ & $294$ & $66$ & $0.8$s & $46$ & $444$ & $348$s & $0.98$ & $0.59$ & $0.27$\\
			\textsf{H5}\xspace & $1,728$ & $294$ & $54$ & $0.6$s & $48$ & $480$ & $347$s & $0.80$ & $0.45$ & $0.07$\\
		
			\textsf{K7}\xspace & $96,875$ & $150$ & $122$ & $1.3$s & $122$ & $1,196$ & $61$s & $1.00$ & $1.00$ & $1.00$\\
			\textsf{K8}\xspace & $484,875$ & $4,506$ & $990$ & $11.6$s & $469$ & $4,506$ & $63$s & $1.00$ & $1.00$ & $1.00$\\
			\textsf{K9}\xspace & $8.595 \times 10^{6}$ & $60,768$ & $888$ & $11.3$s & $432$ & $4,258$ & $185$s & $0.92$ & $0.92$ & $0.88$\\
		
			\textsf{K10}\xspace & $132.625 \times 10^{6}$ & $19,328$ & $1,404$ & $17.1$s & $532$ & $5,032$ & $158$s & $1.00$ & $1.00$ & $1.00$\\
		
		
		
		
		
		
		\bottomrule
   \end{tabular}
   }
	\vspace{-1mm}   
	\caption{Results on \textnormal{HOC}~and~\textnormal{Karel}~tasks; details are provided in Section~\ref{sec.simulations}.}
	\label{fig:experiments.analysis}
	\vspace{-4mm}
\end{figure}

\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.39\textwidth}
	\centering
	{
		\includegraphics[width=1\textwidth]{fig/mctsplots/hoc-G-mutation-6-22_run7/mctsplot_vary_time.pdf}
		\caption{Trends in \ensuremath{\mathcal{F}_{\textnormal{score}}}~features}
	
		\label{fig:experiments.mcts.varytime}
    }
    \end{subfigure}
  	\begin{subfigure}[b]{.197\textwidth}
  	\centering
  	{
		\includegraphics[height=2.84cm]{fig/mctsplots/hoc-G-mutation-6-22_run7/mctsplot_best_200.pdf}
		\caption{Best at $200$}
		\label{fig:experiments.mcts.best1}
	}
	\end{subfigure}
	\begin{subfigure}[b]{.197\textwidth}
	\centering
	{
		\includegraphics[height=2.84cm]{fig/mctsplots/hoc-G-mutation-6-22_run7/mctsplot_best_20K.pdf}
		\caption{Best at $20$K}
	
		\label{fig:experiments.mcts.best2}
    }
    \end{subfigure}
  	\begin{subfigure}[b]{.197\textwidth}
  	\centering
  	{
		\includegraphics[height=2.84cm]{fig/mctsplots/hoc-G-mutation-6-22_run7/mctsplot_best_2M.pdf}
		\caption{Best at $2$M}
	
		\label{fig:experiments.mcts.best3}
	}
	\end{subfigure}	
	\vspace{-5mm}
	\caption{Illustration of a single MCTS run on $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.hoc.p1} obtained from solution code of task \textsf{H4}\xspace~by mutation. (a) shows the temporal trends of different feature values in \ensuremath{\mathcal{F}_{\textnormal{score}}}~averaged over a time window of $100$ steps. (b)--(d)~show the best, i.e., highest scoring, tasks generated up to times $2 \times 10^2$, $2 \times 10^4$, and $2 \times 10^6$ respectively. $\text{\textcode{T}}^{\textnormal{out}}_\textnormal{vis}$ shown in \figref{fig:intro.hoc.t1} is the puzzle produced in (d).
	}
	\vspace{-5mm}
	\label{fig:experiments}
\end{figure}







\textbf{Analyzing output tasks.}
We further analyze the generated tasks based on the objectives of Section~\ref{sec.problem}. All tasks satisfy properties (I)--(III) by design. Objective (IV) is easily achieved by excluding generated tasks for which $\text{\textcode{C}}^{\textnormal{out}} = \text{\textcode{C}}^{\textnormal{in}}$. For a random sample of $100$ of the generated tasks per reference task, we performed manual validation to determine whether objectives (V) and (VI) are met. The fraction of tasks that satisfy these objectives is listed in the last three columns of \figref{fig:experiments.analysis}.
We observe that the vast majority of tasks meet the objectives, even if not by design.
For \textsf{H5}\xspace, the fraction of tasks satisfying (VI) is low because the corresponding codes are generic enough to solve several puzzles.




\textbf{Deep dive into an MCTS run.}
To offer more insight into the task generation process, we take a closer look at an MCTS run for task \textsf{H4}\xspace, shown in \figref{fig:experiments}. \figref{fig:experiments.mcts.varytime} illustrates the improvement in various components of \ensuremath{\mathcal{F}_{\textnormal{score}}}~as the number of MCTS iterations increases. Best tasks at different iterations are shown in \figref{fig:experiments.mcts.best1}, \ref{fig:experiments.mcts.best2}, \ref{fig:experiments.mcts.best3}. As expected, the more the iterations, the better the tasks are.

\looseness-1\textbf{Remarks.} We also ran the mutation stage by enumerating the programs within size constraints and then post-checking other constraints without Z3. This implementation leads to a run-time increase by a factor of $10$ to $100$ for different tasks. So, Z3 seems to be very effective by jointly considering all the constraints. As a search method, although MCTS seems computationally expensive, the actual run-time and memory footprint of an MCTS run depend on the unique traces explored (i.e., unique symbolic executions done)---this number is typically much lower than the number of iterations, also see discussion in the supplementary material. Considering the MCTS output in Figs.~\ref{fig:experiments.mcts.best2}, \ref{fig:experiments.mcts.best3}, to obtain a comparable evaluation score through a random search, the corresponding number of unique symbolic executions required is at least $10$ times more than executed by MCTS. We note that while we considered one I/O pair for \textnormal{Karel}~tasks, our methodology can be easily extended to multiple I/O pairs by adapting techniques designed for generating diverse tasks. 















































		
		
		
		
		
		
			%
		
			%
		
		


\section{User Study and Comparison with Alternate Methods}\label{sec.userstudy}
\vspace{-2mm}
In this section, we evaluate our task synthesis algorithm with a user study focusing on tasks \textsf{H2}\xspace, \textsf{H3}\xspace, \textsf{H4}\xspace, and \textsf{H5}\xspace. We developed an online app\footnote{\href{https://www.teaching-blocks.cc/}{https://www.teaching-blocks.cc/}\label{footnote.userstudyapp}}, which uses the publicly available toolkit of Blockly Games~\cite{googleblockly} and provides an interface for a participant to practice block-based programming tasks for HOC. Each ``practice session'' of the study involves three steps: (i)~a reference task $\text{\textcode{T}}^{\textnormal{in}} \in \{\text{\textsf{H2}\xspace}, \text{\textsf{H3}\xspace}, \text{\textsf{H4}\xspace}, \text{\textsf{H5}\xspace}\}$ is shown to the participant along with its solution code $\text{\textcode{C}}^{\textnormal{in}}$, (ii)~a new task  $\text{\textcode{T}}^{\textnormal{out}}$ is generated for which the participant has to provide a solution code, and (iii)~a post-survey asks the participant to assess the visual dissimilarity of the two tasks on a $4$-point Likert scale as used in \cite{polozov2015}. Details on the app interface and questionnaire are provided in the supplementary material. Participants for the study were recruited through Amazon Mechanical Turk. We only selected four tasks due to the high cost involved in conducting the study (about $1.8$~USD per participant). The number of participants and their performance are documented in \figref{fig:userstudy}. 





\textbf{Baselines and methods evaluated.}
\looseness-1 We evaluated four different methods, including three baselines (\ensuremath{\textsc{Same}}, \ensuremath{\textsc{Tutor}}, \ensuremath{\textsc{MutTask}}) and our algorithm  (\ensuremath{\textsc{SynTask}}). \ensuremath{\textsc{Same}}~generates tasks such that $\text{\textcode{T}}^{\textnormal{in}} = \text{\textcode{T}}^{\textnormal{out}}$. \ensuremath{\textsc{Tutor}}~produces tasks that are similar to $\text{\textcode{T}}^{\textnormal{in}}$ and designed by an expert. We picked similar problems from the set of $20$ \emph{Classic Maze} challenge~\cite{hourofcode_maze} tasks exercising the same programming concepts: \emph{Maze 6, 9} for \textsf{H2}\xspace, \emph{Maze 11, 13} for \textsf{H3}\xspace, \emph{Maze 15, 17} for \textsf{H4}\xspace, and \emph{Maze 19} for \textsf{H5}\xspace.




\ensuremath{\textsc{MutTask}}~generated tasks by directly mutating the grid-world of the original task, i.e., by moving the agent or goal by up to two cells and potentially changing the agent's orientation. A total of $18$, $20$, $15$, and $17$ tasks were generated for \textsf{H2}\xspace, \textsf{H3}\xspace, \textsf{H4}\xspace, and \textsf{H5}\xspace, respectively. \figref{fig:userstudy.taskmutation} shows two output tasks for \textsf{H3}\xspace~and illustrates the challenge in directly mutating the input task, given the high discontinuity in mapping from the space of tasks to their codes. For \textsf{H3}\xspace, a total of $14$ out of $20$ new tasks were structurally very different from the input.




\ensuremath{\textsc{SynTask}}~uses our algorithm to generate tasks. We picked the generated tasks from three groups based on the size of the code mutations from which they were produced, differing from the reference solution code by $+\delta_{\textnormal{size}}$ for $\delta_{\textnormal{size}} \in \{0, 1, 2\}$. For \textsf{H2}\xspace~and \textsf{H3}\xspace, we randomly selected $5$ tasks from each group, for a total of $15$ new tasks per reference task.  For \textsf{H4}\xspace~and \textsf{H5}\xspace, we selected $10$ tasks from the first group ($\delta_{\textnormal{size}}=0$) only, due to their complexity stemming from nested constructs in their codes. We observed that \ensuremath{\textsc{Tutor}}~tasks for \textsf{H4}\xspace, \textsf{H5}\xspace~were also of $\delta_{\textnormal{size}}=0$, i.e., $\text{\textcode{C}}^{\textnormal{out}}_{\textnormal{size}} = \text{\textcode{C}}^{\textnormal{in}}_{\textnormal{size}}$. All the generated tasks picked for \ensuremath{\textsc{SynTask}}~adhere to properties (I)--(VI) in Section~\ref{sec.problem}.





\textbf{Results on task solving.}
In terms of successfully solving the generated tasks, \ensuremath{\textsc{Same}}~performed best (mean success = $0.94$) in comparison to \ensuremath{\textsc{Tutor}}~(mean = $0.90$), \ensuremath{\textsc{SynTask}}~(mean = $0.89$), and \ensuremath{\textsc{MutTask}}~(mean = $0.68$)---this is expected given the tasks generated by \ensuremath{\textsc{Same}}. In comparison to \ensuremath{\textsc{Tutor}}, the performance of \ensuremath{\textsc{SynTask}}~was not significantly different~($\chi^2=0.04, p=0.83$); in comparison to \ensuremath{\textsc{MutTask}},  \ensuremath{\textsc{SynTask}}~performed significantly better ($\chi^2=28.74,  p < e^{-8}$).
The complexity of the generated tasks is also reflected in the average time that participants spent on solving them. As shown in \figref{fig:userstudy}, they spent more time solving the tasks generated by \ensuremath{\textsc{MutTask}}.

\looseness-1
\textbf{Results on visual task dissimilarity.}
Visual dissimilarity was measured on a Likert scale ranging from 1--4, 1 being highly similar and 4 highly dissimilar.
Comparing the dissimilarity of the generated tasks w.r.t. the reference task, we found that the performance of \ensuremath{\textsc{Same}}~was worst (mean dissimilarity = $1.07$), while that of \ensuremath{\textsc{Tutor}}~was best (mean = $2.90$). \ensuremath{\textsc{SynTask}}~(mean = $2.63$) performed significantly better than \ensuremath{\textsc{MutTask}}~(mean = $2.17$), yet slightly worse than \ensuremath{\textsc{Tutor}}. This is because \ensuremath{\textsc{Tutor}}~generates tasks with additional distracting paths and noise, which can also be done by our algorithm (although not done for this study). Moreover, for \textsf{H2}\xspace, which had no conditionals, the resulting codes were somewhat similar, and so were the generated puzzles. When excluding \textsf{H2}\xspace~from the analysis, the difference between \ensuremath{\textsc{SynTask}}~(mean = $2.72$) 
and \ensuremath{\textsc{Tutor}}~(mean =$2.93$) was not statistically significant. A detailed distribution of the responses can be found in the supplementary material.

\looseness-1\textbf{Remarks.} \ensuremath{\textsc{Same}}'s performance in terms of tasks solved is below $1.00$, possibly because participants overlooked the solution of Step $1$, unaware they will be receiving the same task in Step $2$, and the app did not allow them to go back to Step $1$. 
This user study provides a proof-of-concept; more elaborate studies are needed to fully reach the motivational goal of teaching $\textnormal{K-}12$ students, and evaluate the long term impact on students' concept learning. 
As additional studies, it would be important to understand the sensitivity of user study results w.r.t. the Likert scale definition; another possibility is to use pairwise comparisons in eliciting user evaluations.
 






\begin{figure}[t!]
\centering

	\scalebox{0.85}{
	\setlength\tabcolsep{3pt}
	\renewcommand{\arraystretch}{1.1}
	\begin{tabular}{r|rrrrr|rrrrr|rrrrr|rrrrr}
			\toprule
		
			Method & \multicolumn{5}{c|}{Total participants} & \multicolumn{5}{c|}{Fraction of tasks solved} & \multicolumn{5}{c|}{Time spent in secs} & \multicolumn{5}{c}{Visual dissimilarity} \\
			 & \textbf{H-} & \textsf{H2}\xspace & \textsf{H3}\xspace & \textsf{H4}\xspace & \textsf{H5}\xspace 	& \textbf{H-} & \textsf{H2}\xspace & \textsf{H3}\xspace & \textsf{H4}\xspace & \textsf{H5}\xspace  & \textbf{H-} & \textsf{H2}\xspace & \textsf{H3}\xspace & \textsf{H4}\xspace & \textsf{H5}\xspace & \textbf{H-} & \textsf{H2}\xspace & \textsf{H3}\xspace & \textsf{H4}\xspace & \textsf{H5}\xspace \\ 		
			\toprule
			\ensuremath{\textsc{Same}} & $\textbf{96}$ & $24$ & $24$ & $24$ & $24$ & $\textbf{.94}$ & $.92$ & $1.00$ & $.96$ & $.88$ & $\textbf{89}$ & $60$ & $59$ & $93$ & $145$ & $\textbf{1.07}$ & $1.12$ & $1.04$ & $1.00$ & $1.12$ \\
			\ensuremath{\textsc{Tutor}} & $\textbf{170}$ & $48$ & $48$ & $49$ & $25$ & $\textbf{.90}$ & $.90$ & $.92$ & $.88$ & $.92$ & $\textbf{121}$ & $107$ & $113$ & $118$ & $169$ & $\textbf{2.90}$ & $2.81$ & $2.79$ & $2.96$ & $3.16$ \\
			\ensuremath{\textsc{MutTask}} & $\textbf{278}$ & $72$ & $79$ & $60$ & $67$ & $\textbf{.68}$ & $.76$ & $.71$ & $.65$ & $.60$ & $\textbf{219}$ & $135$ & $299$ & $219$ & $215$ & $\textbf{2.17}$ & $2.36$ & $2.33$ & $1.95$ & $1.99$  \\
		
			\ensuremath{\textsc{SynTask}} & $\textbf{197}$ & $59$ & $57$ & $40$ & $41$ & $\textbf{.89}$ & $.92$ & $.89$ & $.92$ & $.83$ & $\textbf{144}$ & $85$ & $183$ & $130$ & $189$ & $\textbf{2.63}$ & $2.41$ & $2.42$ & $2.68$ & $3.20$ \\
		
			\bottomrule
   \end{tabular}
   }
   \vspace{-1mm}
	\caption{User study results for \textnormal{HOC}~tasks (\textbf{H-} represents all tasks in the study); see Section~\ref{sec.userstudy}. }
   \vspace{-4mm}	
	\label{fig:userstudy}
\end{figure}

\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.1425\textwidth}
	\centering
	{
	
		\includegraphics[height=2.085cm]{fig/taskmutation_baseline/F_orig.pdf}
	
		\caption{$\text{\textcode{T}}^{\textnormal{in}}_\textnormal{vis}$ for \textsf{H3}\xspace}
		 \label{fig:userstudy.hoc.t0.orig}
	}
	\end{subfigure}


	\begin{subfigure}[b]{.1425\textwidth}
	\centering
	{
	
		\includegraphics[height=2.085cm]{fig/taskmutation_baseline/F19.pdf}
	
		\caption{1\textsuperscript{st} $\text{\textcode{T}}^{\textnormal{out}}_\textnormal{vis}$}
		 \label{fig:userstudy.hoc.t0.sim}
	}
	\end{subfigure}


	\begin{subfigure}[b]{.1425\textwidth}
	\centering
	{
	
		\includegraphics[height=2.085cm]{fig/taskmutation_baseline/F16-1.pdf}
	
		\caption{2\textsuperscript{nd} $\text{\textcode{T}}^{\textnormal{out}}_\textnormal{vis}$}
		 \label{fig:userstudy.hoc.t0.diff}
	}
	\end{subfigure}


	\begin{subfigure}[b]{.197\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.68cm}{0.7}{0.55}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnLeft}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnRight}\\				
				\quad \textcode{\}}\\
				\textcode{\}}
			
			
				\\	
				\\	
		\end{boxcode}
		\vspace{-1mm}
		\caption{$\text{\textcode{C}}^{\textnormal{in}}$ for \textsf{H3}\xspace}
		\label{fig:userstudy.hoc.p0.orig}
    }
    \end{subfigure}


	\begin{subfigure}[b]{.197\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.68cm}{0.7}{0.55}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{move}\xspace\\
				\quad \textsf{move}\xspace\\				
				\quad
				\textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textcode{turnLeft}\\				
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnRight}\\				
				\quad \quad \textsf{move}\xspace\\				
				\quad \textcode{\}}\\
				\textcode{\}}
			
			
		\end{boxcode}
		\vspace{-1mm}
		\caption{1\textsuperscript{st} $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:userstudy.hoc.p0.sim}
    }
    \end{subfigure}


	\begin{subfigure}[b]{.145\textwidth}
	\centering
	{
    
		\begin{boxcode}{2.72cm}{0.7}{0.55}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{move}\xspace\\
				\quad \textsf{move}\xspace\\
                \quad \textcode{turnLeft}\\
                \quad \textsf{move}\xspace\\
                \quad \textcode{turnRight}\\
                \quad \textsf{move}\xspace\\
                \quad \textcode{turnLeft} \\
               
               
                \quad \textcolor{blue}{$\mathbf{15}$ \textbf{more actions}}\\
				\textcode{\}}
		\end{boxcode}
		\vspace{-0.6mm}
		\caption{2\textsuperscript{nd} $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:userstudy.hoc.p0.diff}
    }
    \end{subfigure}
   
    \vspace{-5mm}
	\caption{\ensuremath{\textsc{MutTask}}~applied to \textsf{H3}\xspace. $\text{\textcode{T}}^{\textnormal{in}}_\textnormal{vis}$ and $\text{\textcode{C}}^{\textnormal{in}}$ are shown in (a) and (d). (b)--(c) illustrate two tasks $\text{\textcode{T}}^{\textnormal{out}}_\textnormal{vis}$ obtained via small mutations of $\text{\textcode{T}}^{\textnormal{in}}_\textnormal{vis}$. (e) is the smallest solution code for (b) and is structurally similar to $\text{\textcode{C}}^{\textnormal{in}}$. (f) is the smallest solution code for (c) and is drastically different from $\text{\textcode{C}}^{\textnormal{in}}$.
	}
	\vspace{-6mm}
	\label{fig:userstudy.taskmutation}
\end{figure}
















\section{Conclusions and Outlook}\label{sec.conclusions}
\vspace{-3mm}
\looseness-1We developed techniques for a critical aspect of pedagogy in block-based programming: Automatically generating new tasks that exercise specific programming concepts, while looking visually dissimilar to input. We demonstrated the effectiveness of our methodology through an extensive empirical evaluation and user study on reference tasks from popular programming platforms. We believe our techniques have the potential to drastically improve the success of pedagogy in block-based visual programming environments by providing tutors and students with a substantial pool of new tasks. Beyond the application domain of programming education, our methodology can be used for generating large-scale datasets consisting of tasks and solution codes with desirable characteristics---this can be potentially useful for training neural program synthesis methods.

There are several promising directions for future work, including but not limited to: Learning a policy to guide the MCTS procedure (instead of running vanilla MCTS); automatically learning the constraints and cost function from a human-generated pool of problems; and applying our methodology to other programming environments (e.g., Python problems).


















\section*{Broader Impact}\label{sec.impact}
This paper develops new techniques for improving pedagogy in block-based visual programming environments. Such programming environments are increasingly used nowadays to introduce computing concepts to novice programmers, and our work is motivated by the clear societal need of enhancing $\textnormal{K-}12$ computing education. In existing systems, the programming tasks are hand-curated by tutors, and the available set of tasks is typically very limited. This severely limits the utility of existing systems for long-term learning as students do not have access to practice tasks for mastering the programming concepts.

\looseness-1
We take a step towards tackling this challenge by developing a methodology to generate new practice tasks for a student that match a desired level of difficulty and exercise specific programming concepts. Our task synthesis algorithm is able to generate 1000's of new similar tasks for reference tasks taken from the \emph{Hour of Code: Classic Maze} challenge by \emph{Code.org} and the \emph{Intro to Programming with Karel} course by \emph{CodeHS.com}. Our extensive experiments and user study further validate the quality of the generated tasks.  Our task synthesis algorithm could be useful in many different ways in practical systems. For instance, tutors can assign new practice tasks as homework or quizzes to students to check their knowledge, students can automatically obtain new similar tasks after they failed to solve a given task and received assistance, and intelligent tutoring systems could automatically generate a personalized curriculum of problems for a student for long-term learning. 




\section{List of Appendices}\label{appendix.table-of-contents}
In this section, we provide a brief description of the content provided in the appendices of the paper.   
\begin{itemize}
\item Appendix~\ref{appendix.sec.introduction} shows all the $10$ reference tasks from \figref{fig:dataset}. For each task, we also illustrate our methodology as was done in \figref{fig:intro.hoc} and \figref{fig:intro.karel}.
\item Appendix~\ref{appendix.sec.userstudy} expands on the user study analysis. (Section~\ref{sec.userstudy})
\item Appendix~\ref{appendix.sec.mutation} provides additional details on the code mutation stage. (Section~\ref{sec.approach.mutation})
\item Appendix~\ref{appendix.sec.symbolicexecution} demonstrates how MCTS could guide the symbolic execution in generating more suitable tasks. (Section~\ref{sec.approach.tasksynthesis})
\item Appendix~\ref{appendix.sec.simulations} provides additional details and results about experiments. (Section~\ref{sec.simulations})
\end{itemize}





\section{Illustration of Our Methodology for the \textnormal{HOC}~and \textnormal{Karel}~Dataset}\label{appendix.sec.introduction}
In this section, we illustrate our methodology for all the $10$ reference tasks from \figref{fig:dataset}. For each reference task $(\text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}})$, we picked one output $(\text{\textcode{T}}^{\textnormal{out}}, \text{\textcode{C}}^{\textnormal{out}})$ from the entire set of generated outputs.

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H1_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:appendix.intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{turnRight}\\
			\quad \textsf{move}\xspace\\				
			\textcode{\}}
			\\
			\\
			\vspace{2.5mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H1_env1.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:appendix.intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\			
			\quad \textcode{turnRight}\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{move}\xspace\\
			\textcode{\}}
			\vspace{2.5mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Task \textsf{H1}\xspace~-- Illustration of our methodology.}    

	\vspace{-3.5mm}
	\label{fig:appendix.intro.hoc}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H2_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:appendix.intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textcode{turnRight}\\
			\quad \textsf{repeat}\xspace\textcode{(5}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \textcode{\}}\\
			\textcode{\}}
			\\
			\\
			\\
			\vspace{1.5mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H2_env1.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:appendix.intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{turnRight}\\
			\quad \textsf{repeat}\xspace\textcode{(6}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \textcode{\}}\\
			\textcode{\}}
			\\
			\vspace{2mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Task \textsf{H2}\xspace~-- Illustration of our methodology.}

	\vspace{-3.5mm}
	\label{fig:appendix.intro.hoc}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H3_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:appendix.intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{repeat}\xspace\textcode{(4}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \textcode{\}}\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{repeat}\xspace\textcode{(5}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \textcode{\}}\\
			\textcode{\}}
			\vspace{2.5mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H3_env1.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:appendix.intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.58}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{repeat}\xspace\textcode{(5}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \textcode{\}}\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{repeat}\xspace\textcode{(5}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \textcode{\}}\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{move}\xspace\\
			\textcode{\}}
		
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Task \textnormal{H3}~-- Illustration of our methodology.}

	\vspace{-3.5mm}
	\label{fig:appendix.intro.hoc}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H4_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:appendix.intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnRight}\\			
			\quad \textcode{\}}\\
		    \textcode{\}}
			\\
		    \vspace{1.8mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H4_env1.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:appendix.intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnRight}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\			
			\quad \textcode{\}}\\
		    \textcode{\}}
		    \vspace{1.5mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Task \textsf{H3}\xspace~-- Illustration of our methodology.}   

	\vspace{-3.5mm}
	\label{fig:appendix.intro.hoc}
\end{figure}


\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/intro/intro_hoc_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:appendix.intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathLeft}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\vspace{1mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/mctsplots/hoc-G-mutation-6-22_run7/mctsplot_best_2M.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:appendix.intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.58}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathRight}\textcode{)\{}\\
			\quad \quad \quad \textcode{turnRight}\\
			\quad \quad \textcode{\}}\\
			\quad \textcode{\}}\\
			\textcode{\}}
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Task \textsf{H4}\xspace~-- Illustration of our methodology (same as \figref{fig:intro.hoc} and shown for completeness).}   

	\vspace{-3.5mm}
	\label{fig:appendix.intro.hoc}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H6_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		 \label{fig:appendix.intro.hoc.t0}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
				\quad \quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{\}}\\
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
    			\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
			
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.hoc.p0}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
	
	
		\includegraphics[height=2.39cm]{fig/appendix_intro/appendix_intro_H6_env1.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		 \label{fig:appendix.intro.hoc.t1}
	}
	\end{subfigure}
	\

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
				\quad \quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{\}}\\
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
    			\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
			
		\end{boxcode}
		\vspace{-1mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.hoc.p1}
    }
    \end{subfigure}
   
    \vspace{-1.5mm}
	\caption{Task \textsf{H5}\xspace~-- Illustration of our methodology.}

	\vspace{-3.5mm}
	\label{fig:appendix.intro.hoc}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
	
		\includegraphics[height=1.95cm]{fig/appendix_intro/appendix_intro_K7_env0.pdf}		
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.t0}
    }
    \end{subfigure}
  	\
  	\begin{subfigure}[b]{.195\textwidth}
  	\centering
  	 {
  	 
  	 	\begin{boxcode}{3.5cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{pickMarker}\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\			
		
			\textcode{\}}
			\vspace{2.5mm}
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.p0}
	}
	\end{subfigure}
	\quad \  
	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
		\includegraphics[height=1.95cm]{fig/appendix_intro/appendix_intro_K7_env1.pdf}		
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.t1}
	}
	\end{subfigure}
	\
	\begin{subfigure}[b]{.195\textwidth}
	\centering
	{
	
  	 	\begin{boxcode}{3.5cm}{0.75}{0.58}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textcode{putMarker}\\
			\quad \textcode{turnLeft}\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\
			\quad \textcode{pickMarker}\\
			\quad \textsf{move}\xspace\\
			\quad \textsf{move}\xspace\\			
		
			\textcode{\}}
		\end{boxcode}
		\vspace{-1.3mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.p1}
	}
	\end{subfigure}  
	\vspace{-1.5mm}	
	\caption{Task \textsf{K7}\xspace~-- Illustration of our methodology.}   

	\vspace{-3.5mm}
	\label{fig:appendix.intro.karel1}
\end{figure}


\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
	
		\includegraphics[height=1.95cm]{fig/appendix_intro/appendix_intro_K8_env0.pdf}		
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.t0}
    }
    \end{subfigure}
  	\
  	\begin{subfigure}[b]{.195\textwidth}
  	\centering
  	 {
  	 
  	 	\begin{boxcode}{3.5cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{repeat}\xspace\textcode{(4}\textcode{)\{}\\
			\quad \quad \textcode{putMarker}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \textcode{\}}\\		
			\textcode{\}}
			\vspace{3mm}
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.p0}
	}
	\end{subfigure}
	\quad \  
	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
		\includegraphics[height=1.95cm]{fig/appendix_intro/appendix_intro_K8_env1.pdf}		
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.t1}
	}
	\end{subfigure}
	\
	\begin{subfigure}[b]{.195\textwidth}
	\centering
	{
	
  	 	\begin{boxcode}{3.5cm}{0.75}{0.7}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textsf{repeat}\xspace\textcode{(4}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{pickMarker}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \textcode{\}}\\		
			\textcode{\}}
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.p1}
	}
	\end{subfigure}  
	\vspace{-1.5mm}	
	\caption{Task \textsf{K8}\xspace~-- Illustration of our methodology.}   

	\vspace{-3.5mm}
	\label{fig:appendix.intro.karel2}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
		\includegraphics[height=1.95cm]{fig/appendix_intro/appendix_intro_K9_env0.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.t0}
    }
    \end{subfigure}
  	\
  	\begin{subfigure}[b]{.195\textwidth}
  	\centering
  	 {
  	 
  	 	\begin{boxcode}{3.5cm}{0.75}{0.58}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeat}\xspace\textcode{(8}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{noMarker}\textcode{)\{}\\
				\quad \quad \quad \textcode{putMarker}\\
				\quad \quad \textcode{\}}\\
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
    			\quad \quad \quad \textcode{pickMarker}\\
				\quad \quad \textcode{\}}\\
    			\quad \quad \textsf{move}\xspace\\				
				\quad \textcode{\}}\\
				\textcode{\}}
				\vspace{1.5mm}
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.p0}
	}
	\end{subfigure}
	\quad \  
	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
		\includegraphics[height=1.95cm]{fig/appendix_intro/appendix_intro_K9_env1.pdf}
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.t1}
	}
	\end{subfigure}
	\
	\begin{subfigure}[b]{.195\textwidth}
	\centering
	{
	
  	 	\begin{boxcode}{3.5cm}{0.75}{0.58}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
                \quad \textcode{turnRight}\\				
				\quad \textsf{repeat}\xspace\textcode{(7}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{noMarker}\textcode{)\{}\\
				\quad \quad \quad \textcode{putMarker}\\
				\quad \quad \textcode{\}}\\
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
    			\quad \quad \quad \textcode{pickMarker}\\
				\quad \quad \textcode{\}}\\
    			\quad \quad \textsf{move}\xspace\\				
				\quad \textcode{\}}\\
				\textcode{\}}
			
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.p1}
	}
	\end{subfigure}  
	\vspace{-1.5mm}	
	\caption{Task \textsf{K9}\xspace~-- Illustration of our methodology.}   

	\vspace{-3.5mm}
	\label{fig:appendix.intro.karel3}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
	
		\includegraphics[height=1.95cm]{fig/intro/intro_karel_env0.pdf}		
	
		\caption{Visual puzzle for $\text{\textcode{T}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.t0}
    }
    \end{subfigure}
  	\
  	\begin{subfigure}[b]{.195\textwidth}
  	\centering
  	 {
  	 
  	 	\begin{boxcode}{3.5cm}{0.75}{0.58}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textcode{putMarker}\\
			\quad \textsf{while}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnRight}\\
			\quad \quad \textcode{putMarker}\\	
			\quad \textcode{\}}\\
			\textcode{\}}
			\vspace{1.9mm}
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{in}}$}
		\label{fig:appendix.intro.karel.p0}
	}
	\end{subfigure}
	\quad \  
	\begin{subfigure}[b]{.27\textwidth}
	\centering
	{
	
		\includegraphics[height=1.95cm]{fig/intro/intro_karel_env1.pdf}		
	
		\caption{Visual puzzle for $\text{\textcode{T}}^\textnormal{out}$}   
		\label{fig:appendix.intro.karel.t1}
	}
	\end{subfigure}
	\
	\begin{subfigure}[b]{.195\textwidth}
	\centering
	{
	
  	 	\begin{boxcode}{3.5cm}{0.75}{0.58}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textcode{putMarker}\\
			\quad \textsf{while}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnRight}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \quad \textcode{putMarker}\\	
			\quad \textcode{\}}\\
			\textcode{\}}
		\end{boxcode}
		\vspace{-1.18mm}
		\caption{Solution code $\text{\textcode{C}}^{\textnormal{out}}$}
		\label{fig:appendix.intro.karel.p1}
	}
	\end{subfigure}  
	\vspace{-1.5mm}	
	\caption{Task \textsf{K10}\xspace~-- Illustration of our methodology (same as \figref{fig:intro.karel} and shown for completeness).}   

	\vspace{-3.5mm}
	\label{fig:appendix.intro.karel4}
\end{figure}


\section{Code Mutation: Additional Details}\label{appendix.sec.mutation}
This section describes the mutation stage of the task synthesis algorithm. In particular, we describe in detail the constraints applied on sketch \textcode{Q} = $\ensuremath{\Omega}(\text{\textcode{C}})$. Note that we denote an empty action as $\phi$.
Our implementation of the code mutation stage, using the Z3 solver~\cite{deMouraBjorner2008}, is publicly available (see Footnote~\ref{footnote.githubrepo})

\textbf{Constraint $(\Delta_1)$: \ensuremath{\textsc{ActionEdits}}.}
\ensuremath{\textsc{ActionEdits}}~returns the values that all action sequences can take, based on their values in the reference code, $\text{\textcode{C}}^\textnormal{in}$. Consider the action sequence $\textoverline{\textcode{A}}$ in sketch $\text{\textcode{Q}}$. The function $\ensuremath{\omega}(\textoverline{\textcode{A}}|~\text{\textcode{C}}^\textnormal{in})$ returns the value of \textoverline{\textcode{A}}~in $\text{\textcode{C}}^\textnormal{in}$. The types of constraints returned by \ensuremath{\textsc{ActionEdits}}~are:
\begin{enumerate}
    \item Local \textoverline{\textcode{A}}~constraints. These constraints describe the values that one \textoverline{\textcode{A}}~can take w.r.t.  $\ensuremath{\omega}(\textoverline{\textcode{A}}|~\text{\textcode{C}}^\textnormal{in})$. It has the following rules:
    \begin{itemize}
    \item \textsf{move}\xspace~action $\in \ensuremath{\omega}(\textoverline{\textcode{A}}|~\text{\textcode{C}}^\textnormal{in})$, would imply that the corresponding action in \textoverline{\textcode{A}}~must be \textsf{move}\xspace.
    
    \item Set of $\text{\textcode{turnLeft}}$, $\text{\textcode{turnRight}}$~actions $\in \ensuremath{\omega}(\textoverline{\textcode{A}}|~\text{\textcode{C}}^\textnormal{in})$, would imply that the corresponding actions in \textoverline{\textcode{A}}~will either have all the `turn' actions changed to $\text{\textcode{turnLeft}}$, or to $\text{\textcode{turnRight}}$, or remain the same, or be flipped, i.e. $\text{\textcode{turnLeft}} \rightarrow \text{\textcode{turnRight}}$~and $\text{\textcode{turnRight}} \rightarrow \text{\textcode{turnLeft}}$.
    
    \item Set of $\text{\textcode{pickMarker}}$, $\text{\textcode{putMarker}}$~actions $\in \ensuremath{\omega}(\textoverline{\textcode{A}}|~\text{\textcode{C}}^\textnormal{in})$, would imply that the corresponding actions in \textoverline{\textcode{A}}~will either have all the `marker' actions changed to $\text{\textcode{pickMarker}}$, or to $\text{\textcode{putMarker}}$, or remain the same, or be flipped i.e. $\text{\textcode{pickMarker}} \rightarrow \text{\textcode{putMarker}}$~and $\text{\textcode{putMarker}} \rightarrow \text{\textcode{pickMarker}}$.
    
    \item Additional actions (up to $\delta_{\textnormal{size}}$) to \textoverline{\textcode{A}}~can either be appended before the existing actions (in $\ensuremath{\omega}(\textoverline{\textcode{A}}|~\text{\textcode{C}}^\textnormal{in})$) or after, but not both. In our experiments we set $\delta_{\textnormal{size}} = 2$.
    \end{itemize}
    
    \looseness-1These constraints are listed under ``Local \textoverline{\textcode{A}}~constraints'' in \figref{fig:appendix.mutation.hoc.7} and \figref{fig:appendix.mutation.karel.7}.
   
    
    \item Global \textoverline{\textcode{A}}~constraints. These constraints apply on all the \textoverline{\textcode{A}}'s in sketch \textcode{Q}. They allow only one of all the \textoverline{\textcode{A}}'s to have additional actions added to them. These constraints are listed under ``Global \textoverline{\textcode{A}}~constraints'' in \figref{fig:appendix.mutation.hoc.7} and \figref{fig:appendix.mutation.karel.7}.
    

\end{enumerate}


\textbf{Constraint $(\Delta_{6})$: Action sequence is minimal.}
These constraints describe the sequences that invalidate minimality of code. The constraints ensure that certain sequences of actions do not occur in \textoverline{\textcode{A}}. The detailed list of sequences for the two example codes described, which invalidate \textoverline{\textcode{A}}~if they occur, are given in \figref{fig:appendix.mutation.hoc.8} and \figref{fig:appendix.mutation.karel.8}.

\vspace{-1.5mm}
\subsection{Details of Code Mutation for HOC}
\vspace{-1mm}
Here, we build on the generic DSL presented in \figref{fig:mutation} for \textnormal{HOC}~codes.
We describe the \textnormal{HOC}-DSL, Sketch DSL, and constraints for \textnormal{HOC}~codes (shown in \figref{fig:appendix.mutation.hoc.1}, \figref{fig:appendix.mutation.hoc.2}, and \figref{fig:appendix.mutation.hoc.3}, respectively). It is to be noted that the \textnormal{HOC}~DSL does not contain `marker' based actions/conditionals: (action) \textcode{pickMarker}, (action) \textcode{putMarker}, (conditional) \textcode{marker}, (conditional) \textcode{noMarker}. It does not allow few more conditionals: \textcode{noPathA}, \textcode{noPathL}~and \textcode{noPathR}.
It also does not contain the \textsf{while}\xspace~construct. We consider a concrete example (continued from the example presented in \figref{fig:mutation.4}), in \figref{fig:appendix.mutation.hoc.4}, illustrate its sketch in \figref{fig:appendix.mutation.hoc.5}, and its constraints in \figref{fig:appendix.mutation.hoc.6}. We elaborate its \textoverline{\textcode{A}}~minimality constraints and \ensuremath{\textsc{ActionEdits}}~in \figref{fig:appendix.mutation.hoc.8} and \figref{fig:appendix.mutation.hoc.7}, respectively.

\textbf{A brief description of elimination sequences to ensure \textoverline{\textcode{A}}-minimality.}
We identify four sequences in \textnormal{HOC}~codes, which must be removed to ensure code minimality. These are: \textcode{turnLeft}, \textcode{turnRight}~or \textcode{turnRight}, \textcode{turnLeft}, which do not lead to any change in the output; \textcode{turnLeft}, \textcode{turnLeft}, \textcode{turnLeft}, which can be replaced by a single \textcode{turnRight}; and finally \textcode{turnRight}, \textcode{turnRight}, \textcode{turnRight}, which can be replaced by a single \textcode{turnLeft}. It is to be noted that we also eliminate variants of the above sequences, that contain $\phi$, but effectively reduce to these four sequences only, given that $\phi$ denotes an empty action.

\vspace{-1.5mm}
\subsection{Details of Code Mutation for Karel}
\vspace{-1mm}
Here, we present a modified/detailed form of \figref{fig:mutation} for \textnormal{Karel}~codes in particular.
We describe the \textnormal{Karel}-DSL, Sketch DSL, and constraints for \textnormal{Karel}~codes (shown in \figref{fig:appendix.mutation.karel.1}, \figref{fig:appendix.mutation.karel.2}, and \figref{fig:appendix.mutation.karel.3}, respectively). It is to be noted that \textnormal{Karel}-DSL does not contain the \textsf{repeatUntilGoal}\xspace~construct. We consider a concrete example (same as the \textnormal{Karel}~solution code presented in \figref{fig:intro.karel.p0}), in \figref{fig:appendix.mutation.karel.4}, illustrate its sketch in \figref{fig:appendix.mutation.karel.5}, and its constraints in \figref{fig:appendix.mutation.karel.6}. We elaborate its \textoverline{\textcode{A}}~minimality constraints and \ensuremath{\textsc{ActionEdits}}~in \figref{fig:appendix.mutation.karel.8} and \figref{fig:appendix.mutation.karel.7}, respectively.

\textbf{A brief description of elimination sequences to ensure \textoverline{\textcode{A}}-minimality.} In addition to the four sequences considered in \textnormal{HOC}~codes, we identify sixteen more sequences in \textnormal{Karel}~codes, which must be removed to ensure code minimality. These are: \textcode{pickMarker}, \textcode{putMarker}~or \textcode{putMarker}, \textcode{pickMarker}~or \textcode{pickMarker}, \textcode{pickMarker}~or \textcode{putMarker}, \textcode{putMarker}, which do not lead to any change in the output or leads to a crash in the \textnormal{Karel}~grid (only one marker is allowed per grid-cell); \textcode{turnLeft}, \textcode{pickMarker}, \textcode{turnRight}~or  \textcode{turnRight}, \textcode{pickMarker}, \textcode{turnLeft}~or \textcode{turnLeft}, \textcode{putMarker}, \textcode{turnRight}~or  \textcode{turnRight}, \textcode{putMarker}, \textcode{turnLeft}, which bring about the same output without the `turn' actions; \textcode{pickMarker}, \textcode{turnLeft}, \textcode{putMarker}~or \textcode{putMarker}, \textcode{turnLeft}, \textcode{pickMarker}~or  \textcode{pickMarker}, \textcode{turnRight}, \textcode{putMarker}~or \textcode{putMarker}, \textcode{turnRight}, \textcode{pickMarker}, which bring about the same output without the `marker' actions; and finally \textcode{pickMarker}, \textcode{turnLeft}, \textcode{pickMarker}~or \textcode{pickMarker}, \textcode{turnRight}, \textcode{pickMarker}~or \textcode{putMarker}, \textcode{turnLeft}, \textcode{putMarker}~or \textcode{putMarker}, \textcode{turnRight}, \textcode{putMarker}, which leads to a crash in the \textnormal{Karel}~grid (only one marker is allowed per grid-cell).
It is to be noted that we also eliminate variants of the above sequences, that contain $\phi$, but effectively reduce to these basic sequences only, given that $\phi$ denotes an empty action.


    


\begin{figure}[h!]
	\centering

	\begin{minipage}{1\textwidth}
	\begin{minipage}{0.465\textwidth}
			\begin{subfigure}[b]{1.0\textwidth}
			\centering
			{
				\begin{boxcode2col}{1.2cm}{6.7cm}{0.75}{1.08}
						\textnormal{code } \text{\textcode{C}} &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} y \\
						\textnormal{rule } \textcode{y} &:= \textcode{s} | \textcode{g}  | \textcode{s}; \textcode{g} \\
					
						\textnormal{rule } \textcode{s} \hspace{1mm} &:= \textcode{a} | $\text{\textcode{s}};\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \textcode{\textsc{Else}} $\text{\textcode{s}}$\\
						& \quad | \textsf{repeat}\xspace(\textcode{x}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \\
						\textnormal{rule } \textcode{g} &:= \textsf{repeatUntilGoal}\xspace(\textcode{goal}) \textcode{\textsc{do}} $\text{\textcode{s}}$\\
					
						\textnormal{action } \textcode{a} &:= \textsf{move}\xspace| \textsf{turnL}\xspace | \textcode{turnR} \\
					
						\textnormal{bool } \textcode{b} &:= \textcode{pathA} | \textcode{pathL} | \textcode{pathR} \\
					
						\textnormal{iter } \textcode{x} &:= $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$\\
					
					\end{boxcode2col}
					\vspace{-3mm}
					\caption{Code DSL -- \textnormal{HOC}}
					\label{fig:appendix.mutation.hoc.1}
				}
			\end{subfigure}
		
		
			\begin{subfigure}[b]{1.0\textwidth}
			\centering
			{
				\begin{boxcode2col}{1.2cm}{6.7cm}{0.75}{1.08}
					\textnormal{sketch } \textcode{Q}  &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} $\text{\textcode{Y}}$ \\
				
					\textnormal{rule } \textcode{Y} & := \textcode{S} | \textcode{G} | \textcode{S}; \textcode{G} \\
				
					\textnormal{rule } \textcode{S} &:= \textcode{A} | \textcode{S}; \textcode{S} |
																	\textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$ | \textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \textcode{\textsc{Else}} $\text{\textcode{S}}$ \\
					& \quad | \textsf{repeat}\xspace(\textcode{X}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
				
					\textnormal{rule } \textcode{G} & := \textsf{repeatUntilGoal}\xspace(\textcode{goal}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
				
				    \textcolor{blue}{Comments} & \textcolor{blue}{:\ \textcode{A} may be $\phi$ or take values of action \textcode{a}}\\
				   
				    & \textcolor{blue}{\ \ \textoverline{\textcode{A}}~denotes a sequence $\text{\textcode{A}}_{1}, \ldots, \text{\textcode{A}}_{n}$}\\
				\end{boxcode2col}
				\vspace{-3mm}
				\caption{Sketch DSL -- \textnormal{HOC}}
			
				\label{fig:appendix.mutation.hoc.2}
			}
			\end{subfigure}    		
	\end{minipage}


	\begin{minipage}{0.55\textwidth}
		\begin{subfigure}[b]{1.0\textwidth}
		\centering
		{
			\begin{boxcode}{9.6cm}{0.75}{1.0}
				\textbf{Input}: code \text{\textcode{C}}, sketch \textcode{Q} $\leftarrow$ $\ensuremath{\Omega}(\text{\textcode{C}})$, map $\ensuremath{\omega}(\cdot|~\text{\textcode{C}})$, $\delta_\text{size}$, $\delta_\text{iter}$
				\begin{enumerate
					\item[(\ensuremath{\Delta_{0}})] Size of generated code may be at most $\text{\textcode{C}}_{\textnormal{size}} + \delta_\text{size}$ 
					%
					\item[(\ensuremath{\Delta_1})] Edit action sequences $\ensuremath{\textsc{ActionEdits}}(\{\textoverline{\textcode{A}} \in \text{\textcode{Q}}\},  \ensuremath{\omega}(\cdot|~\text{\textcode{C}}))$ 
					%
				
					%
					\item[(\ensuremath{\Delta_{2}})]  For each \textcode{X}~$ \in \text{\textcode{Q}}: |\text{\textcode{X}} - \ensuremath{\omega}(\text{\textcode{X}}|~\text{\textcode{C}})| \leq \delta_{\textnormal{iter}}$
					%
					\item[(\ensuremath{\Delta_{3}})] Constraints induced by structure \{\text{\textoverline{\textcode{A}}}\textsubscript{before};  \textsf{repeat}\xspace\{\textoverline{\textcode{A}}\};  \text{\textoverline{\textcode{A}}}\textsubscript{after}\}
					\begin{enumerate}[\leftmargin=0em]
						\item[i.] \textoverline{\textcode{A}}~is not a suffix of \textoverline{\textcode{A}}\textsubscript{before}
						\item[ii.] \textoverline{\textcode{A}}~is not a prefix of \textoverline{\textcode{A}}\textsubscript{after}
					\end{enumerate}
					%
					\item[(\ensuremath{\Delta_{4}})]  For each \textcode{B}~$\in \text{\textcode{Q}}:$
					\begin{enumerate}[\leftmargin=0em]
						\item[i.] \ensuremath{\omega}(\text{\textcode{B}}~|~\text{\textcode{C}}) $\in$ \{\textcode{pathA} \}
							
						\item[] \qquad $\Rightarrow$ \textcode{B} $\in$ \{\textcode{pathA} \}							
						
						\item[ii.] \ensuremath{\omega}(\text{\textcode{B}}~|~\text{\textcode{C}}) $\in$ \{\textcode{pathL},
							 \text{\textcode{pathR} } \} 
						\item[] 
							\quad \quad $\Rightarrow$ \textcode{B} $\in$ \{\textcode{pathL}, \textcode{pathR} \}
					\end{enumerate}
					%
					\item[(\ensuremath{\Delta_{5}})] Constraints induced on \textoverline{\textcode{A}}~nested inside conditional \textcode{B}
					%
					\item[(\ensuremath{\Delta_{6}})] For each $\text{\textoverline{\textcode{A}}} \in \text{\textcode{Q}}$, constraints ensuring minimality of \textoverline{\textcode{A}} 
					\vspace{-0.3em}
				\end{enumerate}
				\\
			\end{boxcode}
			\vspace{-3mm}
			\caption{Types of Sketch Constraints -- \textnormal{HOC}}
			\label{fig:appendix.mutation.hoc.3}
		}
		\end{subfigure}
	\end{minipage}
	\end{minipage}



    \centering
	
		\begin{subfigure}[b]{0.215\textwidth}
		\centering
		{
			\begin{boxcode}{3.68cm}{0.75}{1.0}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathLeft}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
				\\
				\vspace{2mm}
			
			\end{boxcode}
			\vspace{-3mm}
			\caption{Code \text{\textcode{C}}\textsuperscript{in}}
			\label{fig:appendix.mutation.hoc.4}
			}
		\end{subfigure}
	
		\begin{subfigure}[b]{.24\textwidth}
		\centering
		{
			\begin{boxcode}{4.05cm}{0.75}{1.0}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad $\text{\textcode{A}}^{1}_{1}$, $\text{\textcode{A}}^{2}_{1}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{1})}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad $\text{\textcode{A}}^{1}_{2}$, $\text{\textcode{A}}^{2}_{2}$, $\text{\textcode{A}}^{3}_{2}$, 
				$\text{\textcode{A}}^{4}_{2}$, 
				$\text{\textcode{A}}^{5}_{2}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{2})}\\
				\quad \quad \textsf{If}\xspace\textcode{(}$\text{\textcode{B}}_{1}$\textcode{)\{}\\
				\quad \quad \quad $\text{\textcode{A}}^{1}_{3}$, $\text{\textcode{A}}^{2}_{3}$, $\text{\textcode{A}}^{3}_{3}$, $\text{\textcode{A}}^{4}_{3}$, $\text{\textcode{A}}^{5}_{3}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{3})} \\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
				\vspace{1.75mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{Sketch $\text{\text{\textcode{Q}}}^\text{in}$}
			\label{fig:appendix.mutation.hoc.5}
			}
		\end{subfigure}
	
			\begin{subfigure}[b]{0.53\textwidth}
			\centering
			{
				\begin{boxcode}{9.6cm}{0.75}{1.0}
					\textbf{Input}: \text{\textcode{C}}\textsuperscript{in}, $\text{\text{\textcode{Q}}}^\text{in}$, \ensuremath{\omega}$(\cdot|~\text{\text{\textcode{C}}}^\text{in}$), $\delta_\text{size} = 2$
				
					\begin{enumerate}
						%
					    \item[(\ensuremath{\Delta_0})] Up to $2$ new actions may be added in total to $\text{\textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$
						\item[(\ensuremath{\Delta_1})] Edit action sequences $\ensuremath{\textsc{ActionEdits}}(\{\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}\},  \ensuremath{\omega}(\cdot|~\text{\textcode{C}}^\text{in}))$ 
						%
					    \item[(\ensuremath{\Delta_4})] $\text{\textcode{B}}_{1}$ = \textcode{pathL} $\lor$ $\text{\textcode{B}}_{1}$ = \textcode{pathR}	
					    %
					    \item[(\ensuremath{\Delta_5})] $(\text{\textcode{B}}_{1} = \text{\textcode{pathL}}) \Rightarrow$
					    \item[] \quad $\Big{(}\exists i \in [5]$ s.t $\big(\text{\textcode{A}}^{i}_{3} =  \text{\textsf{turnL}\xspace} \ \ \land$  $(\text{ } \forall j < i \text{, } \text{\textcode{A}}^{j}_{3} \notin \{\text{\textsf{move}\xspace}, \text{\textcode{turnR}} \})\big) \Big{)}$
					
						%
						\item[(\ensuremath{\Delta_5})] $(\text{\textcode{B}}_{1} = \text{\textcode{pathR}}) \Rightarrow$
						\item[] \quad $\Big{(} \exists i \in [5]$ s.t $\big(\text{\textcode{A}}^{i}_{3} =  \text{\textcode{turnR}} \ \ \land$  $(\text{ } \forall j<i \text{, }\text{\textcode{A}}^{j}_{3} \notin \{\text{\textsf{move}\xspace}, \text{\textsf{turnL}\xspace} \})\big) \Big{)}$
					
					
						%
					   
					
					
						%
						\item[(\ensuremath{\Delta_6})] $\text{\textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$ are minimal
						%
				\vspace{-3mm}
				\end{enumerate}
			\end{boxcode}
			\vspace{-3mm}
			\caption{$\text{\text{\textcode{Q}}}^\text{in}$-Constraints for \textnormal{HOC}}
		
			\label{fig:appendix.mutation.hoc.6}
		}
		\end{subfigure}		




   
   
    \begin{subfigure}[b]{1\textwidth}
    \centering
			{
				\begin{boxcode}{18.5cm}{0.75}{1.0}
				    Set of elimination sequences $\mathcal{E} := \{(\text{\textcode{L}},\text{\textcode{R}}), (\text{\textcode{R}},\text{\textcode{L}}), (\text{\textcode{L}}, \text{\textcode{L}}, \text{\textcode{L}}), (\text{\textcode{R}}, \text{\textcode{R}}, \text{\textcode{R}})\}$
				     \begin{enumerate}[(i)]
    				    \item Apply each elimination sequence from $\mathcal{E}$ to $\textoverline{\textcode{A}}_{1}$ as a set of constraints.
    				    \item Apply each elimination sequence from $\mathcal{E}$ to $\textoverline{\textcode{A}}_{2}$ as a set of constraints.
    				    \item Apply each elimination sequence from $\mathcal{E}$ to $\textoverline{\textcode{A}}_{3}$ as a set of constraints.			    
				    \end{enumerate}
			\vspace{-2mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{$\text{\text{\textcode{Q}}}^\text{in}$-Constraints: $(\Delta_{6})~\text{ \textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$ are minimal}
		
			\label{fig:appendix.mutation.hoc.8}
		}
    \end{subfigure}


    \begin{subfigure}[b]{1\textwidth}
    \centering
			{
				\begin{boxcode}{18.5cm}{0.75}{1.0}
    			
					\textcolor{blue}{Shorthand notation for actions: $\text{\textsf{move}\xspace} \rightarrow \text{\textcode{M}}$, $\text{\textsf{turnL}\xspace} \rightarrow \text{\textcode{L}}$, $\text{\textcode{turnR}} \rightarrow \text{\textcode{R}}$, $\phi \rightarrow \text{empty-action}$.}
				
				   \vspace{2mm}
				   \\
				    Local \textoverline{\textcode{A}}~constraints that define the values that each action sequence can take:
				   
                    \begin{enumerate}[(i)]
					\item $(\ha{1}{1} =\text{\textcode{M}} \vee \ha{1}{1} = \text{\textcode{L}}
					\vee \ha{1}{1} = \text{\textcode{R}} \vee \ha{1}{1} = \phi) \wedge $ $(\ha{1}{2} =\text{\textcode{M}} \vee \ha{1}{2} = \text{\textcode{L}} \vee \ha{1}{2} = \text{\textcode{R}} \vee \ha{1}{2} = \phi) $
		    	
		    		
					\item $(\ha{2}{1} =\text{\textcode{M}} \vee \ha{2}{1} = \text{\textcode{L}} \vee \ha{2}{1} = \text{\textcode{R}} \vee \ha{2}{1} = \phi) \wedge $ $(\ha{2}{2} =\text{\textcode{M}} \vee \ha{2}{2} = \text{\textcode{L}} \vee \ha{2}{2} = \text{\textcode{R}} \vee \ha{2}{2} = \phi) $
					$(\ha{2}{3} =\text{\textcode{M}}) \wedge $ $(\ha{2}{4} =\text{\textcode{M}} \vee \ha{2}{4} = \text{\textcode{L}} \vee \ha{2}{4} = \text{\textcode{R}} \vee \ha{2}{4} = \phi) \wedge $ $(\ha{2}{5} =\text{\textcode{M}} \vee \ha{2}{5} = \text{\textcode{L}} \vee \ha{2}{5} = \text{\textcode{R}} \vee \ha{2}{5} = \phi) $
					
					\item $(\ha{2}{1} \neq \phi \vee \ha{2}{2} \neq \phi) \Rightarrow (\ha{2}{4} = \phi \wedge \ha{2}{5} = \phi)$
					
					\item $(\ha{2}{4} \neq \phi \vee \ha{2}{5} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi)$
				
					
					\item $(\ha{3}{1} =\text{\textcode{M}} \vee \ha{3}{1} = \text{\textcode{L}} \vee \ha{3}{1} = \text{\textcode{R}} \vee \ha{3}{1} = \phi) \wedge $ $(\ha{3}{2} =\text{\textcode{M}} \vee \ha{3}{2} = \text{\textcode{L}} \vee \ha{3}{2} = \text{\textcode{R}} \vee \ha{3}{2} = \phi) \wedge $ $(\ha{3}{3} = \text{\textcode{L}} \vee \ha{3}{3} = \text{\textcode{R}}) \wedge $
				    \item[] $(\ha{3}{4} =\text{\textcode{M}} \vee \ha{3}{4} = \text{\textcode{L}} \vee \ha{3}{4} = \text{\textcode{R}} \vee \ha{3}{4} = \phi) \wedge $ 
				    $(\ha{3}{5} =\text{\textcode{M}} \vee \ha{3}{5} = \text{\textcode{L}} \vee \ha{3}{5} = \text{\textcode{R}} \vee \ha{3}{5} = \phi) $
				    
				    \item $(\ha{3}{1} \neq \phi \vee \ha{3}{2} \neq \phi) \Rightarrow (\ha{3}{4} = \phi \wedge \ha{3}{4} = \phi)$
				    
				    \item $(\ha{3}{4} \neq \phi \vee \ha{3}{5} \neq \phi) \Rightarrow (\ha{3}{1} = \phi \wedge \ha{3}{2} = \phi)$
				   
				    \end{enumerate}
				    \vspace{2mm}
				     Global \textoverline{\textcode{A}}~constraints that allow actions to be added to either of $\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}$:
				    
				   
				    \begin{enumerate}[(i)]
				    
				    
				    \item $(\ha{1}{1} \neq \phi \vee \ha{1}{2} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge \ha{2}{4} = \phi \wedge \ha{2}{5} = \phi \wedge$ $\ha{3}{1} = \phi \wedge \ha{3}{2} = \phi \wedge \ha{3}{4} = \phi \wedge \ha{3}{5} = \phi)$
				   
				    
				    \item $(\ha{2}{1} \neq \phi \vee \ha{2}{2} \neq \phi) \Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi \wedge$ $\ha{3}{1} = \phi \wedge \ha{3}{2} = \phi \wedge \ha{3}{4} = \phi \wedge \ha{3}{5} = \phi)$
				    \item[] $(\ha{2}{4} \neq \phi \vee \ha{2}{5} \neq \phi) \Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi \wedge$
			        $\ha{3}{1} = \phi \wedge \ha{3}{2} = \phi \wedge \ha{3}{4} = \phi \wedge \ha{3}{5} = \phi)$
				    
				    
				    \item $(\ha{3}{1} \neq \phi \vee \ha{3}{2} \neq \phi) \Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi \wedge \ha{2}{1} = \phi \wedge \ha{2}{1} = \phi \wedge$ $\ha{2}{4} = \phi \wedge \ha{2}{5} = \phi \wedge )$
				    \item[]$(\ha{3}{4} \neq \phi \vee \ha{3}{5} \neq \phi) \Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi \wedge \ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge$ $\ha{2}{4} = \phi \wedge \ha{2}{5} = \phi)$
				   
				    \end{enumerate}
				  
			\end{boxcode}
			\vspace{-3mm}
			\caption{$\text{\text{\textcode{Q}}}^\text{in}$-Constraints: ~$(\Delta_{1})~\ensuremath{\textsc{ActionEdits}}(\{\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}\},  \ensuremath{\omega}(\cdot|~\text{\textcode{C}}^\text{in}))$}
		
			\label{fig:appendix.mutation.hoc.7}
		}
    \end{subfigure}
    \caption{Illustration of Code Mutation for \textnormal{HOC}~on the solution code for task \emph{Maze 16} from the \emph{Hour of Code: Classic Maze} challenge by \emph{Code.org}~\cite{hourofcode_maze}; We build on \figref{fig:mutation} here.
	}

	\label{fig:appendix.mutation.hoc}
	\vspace{-5mm}	
\end{figure}

\begin{figure}[h!]
	\centering

	\begin{minipage}{1\textwidth}
	\begin{minipage}{0.465\textwidth}
			\begin{subfigure}[b]{1.0\textwidth}
			\centering
			{
				\begin{boxcode2col}{1.2cm}{6.7cm}{0.75}{1.15}
						\textnormal{code } \text{\textcode{C}} &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}}~\textcode{s} \\
					
						\textnormal{rule } \textcode{s} \hspace{1mm} &:= \textcode{a} | $\text{\textcode{s}};\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \textcode{\textsc{Else}} $\text{\textcode{s}}$\\
						& \quad | \textsf{while}\xspace (\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ | \textsf{repeat}\xspace(\textcode{x}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \\
					
						\textnormal{action } \textcode{a} &:= \textsf{move}\xspace| \textsf{turnL}\xspace | \textcode{turnR}|  \textsf{put}\xspace | \textsf{pick}\xspace \\
					
						\textnormal{bool } \textcode{b} &:= \textcode{pathA} | \textcode{noPathA} | \textcode{pathL} | \textcode{noPathL} \\
						& \quad | \textcode{pathR} | \textcode{noPathR}  | \textcode{marker}  | \textcode{noMarker} \\
					
						\textnormal{iter } \textcode{x} &:= $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$\\
					
					\end{boxcode2col}
					\vspace{-3mm}
					\caption{Code DSL -- Karel}
					\label{fig:appendix.mutation.karel.1}
				}
			\end{subfigure}
			\\
			\\
			\\
		
			\begin{subfigure}[b]{1.0\textwidth}
			\centering
			{
				\begin{boxcode2col}{1.2cm}{6.7cm}{0.75}{1.15}
					\textnormal{sketch } \textcode{Q}  &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} $\text{\textcode{Y}}$ \\
				
					\textnormal{rule } \textcode{Y} & := \textcode{S} \\
				
					\textnormal{rule } \textcode{S} &:= \textcode{A} | \textcode{S}; \textcode{S} |
					\textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$ | \textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \textcode{\textsc{Else}} $\text{\textcode{S}}$ \\
					& \quad | \textsf{while}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$  | \textsf{repeat}\xspace(\textcode{X}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
				
				    \textcolor{blue}{Comments} & \textcolor{blue}{:\ \textcode{A} may be $\phi$ or take values of action \textcode{a}}\\
				   
				    & \textcolor{blue}{\ \ \textoverline{\textcode{A}}~denotes a sequence $\text{\textcode{A}}_{1}, \ldots, \text{\textcode{A}}_{n}$}\\
				\end{boxcode2col}
				\vspace{-3mm}
				\caption{Sketch DSL -- Karel}
			
				\label{fig:appendix.mutation.karel.2}
			}
			\end{subfigure}    		
	\end{minipage}


	\begin{minipage}{0.55\textwidth}
		\begin{subfigure}[b]{1.0\textwidth}
		\centering
		{
			\begin{boxcode}{9.6cm}{0.75}{1.0}
				\textbf{Input}: code \text{\textcode{C}}, sketch \textcode{Q} $\leftarrow$ $\ensuremath{\Omega}(\text{\textcode{C}})$, map $\ensuremath{\omega}(\cdot|~\text{\textcode{C}})$, $\delta_\text{size}$, $\delta_\text{iter}$
				\begin{enumerate
					\item[(\ensuremath{\Delta_{0}})] Size of generated code may be at most $\text{\textcode{C}}_{\textnormal{size}} + \delta_\text{size}$ 
					%
					\item[(\ensuremath{\Delta_1})] Edit action sequences $\ensuremath{\textsc{ActionEdits}}(\{\textoverline{\textcode{A}} \in \text{\textcode{Q}}\},  \ensuremath{\omega}(\cdot|~\text{\textcode{C}}))$ 
					%
				
					%
					\item[(\ensuremath{\Delta_{2}})]  For each \textcode{X}~$ \in \text{\textcode{Q}}: |\text{\textcode{X}} - \ensuremath{\omega}(\text{\textcode{X}}|~\text{\textcode{C}})| \leq \delta_{\textnormal{iter}}$
					%
					\item[(\ensuremath{\Delta_{3}})] Constraints induced by structure \{\text{\textoverline{\textcode{A}}}\textsubscript{before};  \textsf{repeat}\xspace\{\textoverline{\textcode{A}}\};  \text{\textoverline{\textcode{A}}}\textsubscript{after}\}
					\begin{enumerate}[\leftmargin=0em]
						\item[i.] \textoverline{\textcode{A}}~is not a suffix of \textoverline{\textcode{A}}\textsubscript{before}
						\item[ii.] \textoverline{\textcode{A}}~is not a prefix of \textoverline{\textcode{A}}\textsubscript{after}
					\end{enumerate}
					%
					\item[(\ensuremath{\Delta_{4}})]  For each \textcode{B}~$\in \text{\textcode{Q}}:$
					\begin{enumerate}[\leftmargin=0em]
						\item[i.] \ \ \ensuremath{\omega}(\text{\textcode{B}}~|~\text{\textcode{C}}) $\in$ \{\textcode{pathA}, \textcode{noPathA}\}
							
						\item[] \qquad \ $\Rightarrow$ \textcode{B} $\in$ \{\textcode{pathA}, \textcode{noPathA}\}							
						
						\item[ii.] \ \ensuremath{\omega}(\text{\textcode{B}}~|~\text{\textcode{C}}) $\in$ \{\textcode{pathL}, \textcode{noPathL} 
							 \text{\textcode{pathR} }, \textcode{noPathR}\} 
						\item[] 
							\quad \quad \ $\Rightarrow$ \textcode{B} $\in$ \{\textcode{pathL}, \textcode{noPathL}, \textcode{pathR}, \textcode{noPathR}\}
						\item[iii.] \ensuremath{\omega}(\text{\textcode{B}}~|~\text{\textcode{C}}) $\in$ \{\textcode{marker}, \textcode{noMarker}\} 
						\item[] \quad \quad \hspace{0.1em} $\Rightarrow$ \textcode{B} $\in$ \{ \textcode{marker},\textcode{noMarker}\}
					\end{enumerate}
					%
					\item[(\ensuremath{\Delta_{5}})] Constraints induced on \textoverline{\textcode{A}}~nested inside conditional \textcode{B}
					%
					\item[(\ensuremath{\Delta_{6}})] For each $\text{\textoverline{\textcode{A}}} \in \text{\textcode{Q}}$, constraints ensuring minimality of \textoverline{\textcode{A}} 
					\vspace{-0.3em}
				\end{enumerate}
			\end{boxcode}
			\vspace{-3mm}
			\caption{Types of Sketch Constraints -- Karel}
			\label{fig:appendix.mutation.karel.3}
		}
		\end{subfigure}
	\end{minipage}
	\end{minipage}



    \centering
	
		\begin{subfigure}[b]{0.215\textwidth}
		\centering
		{
			\begin{boxcode}{3.68cm}{0.75}{1.0}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textcode{putMarker}\\
			\quad \textsf{while}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnRight}\\
			\quad \quad \textcode{putMarker}\\	
			\quad \textcode{\}}\\
			\textcode{\}}
			\\
			\\
			\vspace{2.5mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{Code \text{\textcode{C}}\textsuperscript{in}}
			\label{fig:appendix.mutation.karel.4}
			}
		\end{subfigure}
	
		\begin{subfigure}[b]{.24\textwidth}
		\centering
		{
			\begin{boxcode}{4.05cm}{0.75}{1.0}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad $\text{\textcode{A}}^{1}_{1}$, $\text{\textcode{A}}^{2}_{1}$, $\text{\textcode{A}}^{3}_{1}$, $\text{\textcode{A}}^{4}_{1}$,
				$\text{\textcode{A}}^{5}_{1}$,
				\textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{1})}\\
				\quad \textsf{while}\xspace\textcode{(}$\text{\textcode{B}}_{1}$\textcode{)\{}\\
				\quad \quad $\text{\textcode{A}}^{1}_{2}$, $\text{\textcode{A}}^{2}_{2}$,\\ \quad \quad $\text{\textcode{A}}^{3}_{2}$, 
				$\text{\textcode{A}}^{4}_{2}$, 
				$\text{\textcode{A}}^{5}_{2}$,\\ \quad \quad
				$\text{\textcode{A}}^{6}_{2}$, 
				$\text{\textcode{A}}^{7}_{2}$,
				$\text{\textcode{A}}^{8}_{2}$, \quad \quad \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{2})}
				\\ 
				\quad \quad
				$\text{\textcode{A}}^{9}_{2}$, 
				$\text{\textcode{A}}^{10}_{2}$, 
				$\text{\textcode{A}}^{11}_{2}$,\\ \quad \quad
				$\text{\textcode{A}}^{12}_{2}$, 
				$\text{\textcode{A}}^{13}_{2}$ \\
				\quad \textcode{\}}\\
				\quad $\text{\textcode{A}}^{1}_{3}$, $\text{\textcode{A}}^{2}_{3}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{3})}\\
				\textcode{\}}
				\\
				\vspace{1.5mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{Sketch $\text{\text{\textcode{Q}}}^\text{in}$}
			\label{fig:appendix.mutation.karel.5}
			}
		\end{subfigure}
	
			\begin{subfigure}[b]{0.53\textwidth}
			\centering
			{
				\begin{boxcode}{9.9cm}{0.75}{1.0}
					\textbf{Input}: \text{\textcode{C}}\textsuperscript{in}, $\text{\text{\textcode{Q}}}^\text{in}$, \ensuremath{\omega}$(\cdot|~\text{\text{\textcode{C}}}^\text{in}$), $\delta_\text{size} = 2$
				
					\begin{enumerate}
						%
					    \item[(\ensuremath{\Delta_0})] Up to $2$ new actions may be added in total to $\text{\textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$
						\item[(\ensuremath{\Delta_1})] Edit action sequences $\ensuremath{\textsc{ActionEdits}}(\{\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}\},  \ensuremath{\omega}(\cdot|~\text{\textcode{C}}^\text{in}))$ 
						%
					    \item[(\ensuremath{\Delta_4})] $\text{\textcode{B}}_{1}$ = \textcode{pathA} $\lor$ $\text{\textcode{B}}_{1}$ = \textcode{noPathA}
					    %
					    \item[(\ensuremath{\Delta_5})] $(\text{\textcode{B}}_{1} = \text{\textcode{pathA}} ) \Rightarrow$ 
					    \item[] \quad $\Big{(} \exists i \in [13]$ s.t $\big(\text{\textcode{A}}^{i}_{2} =  \text{\textsf{move}\xspace} \ \ \land$  $(\text{ } \forall j < i \text{, } \text{\textcode{A}}^{j}_{2} \notin \{\text{\textsf{turnL}\xspace}, \text{\textcode{turnR}} \})\big) \Big{)}$
					
						%
						\item[(\ensuremath{\Delta_5})] $(\text{\textcode{B}}_{1} = \text{\textcode{noPathA}}) \Rightarrow $ 
						\item[] \quad $\Big{(} \exists i \in [13]$ s.t $\big{(}\text{\textcode{A}}^{i}_{2} =  \text{\textsf{move}\xspace}$ $\Rightarrow$  $(\text{ } \exists j<i \text{, }\text{\textcode{A}}^{j}_{2} \in \{\text{\textsf{turnL}\xspace}, \text{\textcode{turnR}} \}) \big{)} \Big{)}$
					
					
						%
					   
					
					
						%
						\item[(\ensuremath{\Delta_6})] $\text{\textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$ are minimal
				\vspace{-2.5mm}
				\end{enumerate}
			
			\end{boxcode}
			\vspace{-3mm}
			\caption{$\text{\text{\textcode{Q}}}^\text{in}$-Constraints for \textnormal{Karel}}
		
			\label{fig:appendix.mutation.karel.6}
		}
		\end{subfigure}		






    \begin{subfigure}[b]{1\textwidth}
    \centering
			{
				\begin{boxcode}{18.5cm}{0.75}{1.0}
				    Set of elimination sequences $\mathcal{E} := \{(\text{\textcode{L}},\text{\textcode{R}}), (\text{\textcode{R}},\text{\textcode{L}}), (\text{\textcode{L}}, \text{\textcode{L}}, \text{\textcode{L}}), (\text{\textcode{R}}, \text{\textcode{R}}, \text{\textcode{R}}), (\text{\textcode{piM}}, \text{\textcode{puM}}), (\text{\textcode{puM}}, \text{\textcode{piM}}), (\text{\textcode{piM}}, \text{\textcode{piM}}), (\text{\textcode{puM}}, \text{\textcode{puM}}), (\text{\textcode{L}}, \text{\textcode{piM}}, \text{\textcode{R}}),$ \\
				    \qquad \qquad \qquad \qquad \qquad \qquad \qquad $(\text{\textcode{R}}, \text{\textcode{piM}}, \text{\textcode{L}}), (\text{\textcode{L}}, \text{\textcode{puM}}, \text{\textcode{R}}), (\text{\textcode{R}},\text{\textcode{puM}}, \text{\textcode{L}}), (\text{\textcode{piM}}, \text{\textcode{L}}, \text{\textcode{puM}}), (\text{\textcode{puM}}, \text{\textcode{L}}, \text{\textcode{piM}}), (\text{\textcode{piM}}, \text{\textcode{R}}, \text{\textcode{puM}}), (\text{\textcode{puM}}, \text{\textcode{R}}, \text{\textcode{piM}}),$\\
				    \qquad \qquad \qquad \qquad \qquad \qquad \qquad
				    $(\text{\textcode{piM}}, \text{\textcode{L}}, \text{\textcode{piM}}), (\text{\textcode{piM}}, \text{\textcode{R}}, \text{\textcode{piM}}), (\text{\textcode{puM}}, \text{\textcode{L}}, \text{\textcode{puM}}), (\text{\textcode{puM}}, \text{\textcode{R}}, \text{\textcode{puM}})\}$
				     \begin{enumerate}[(i)]
    				    \item Apply each elimination sequence from $\mathcal{E}$ to $\textoverline{\textcode{A}}_{1}$ as a set of constraints.
    				    \item Apply each elimination sequence from $\mathcal{E}$ to $\textoverline{\textcode{A}}_{2}$ as a set of constraints.
    				    \item Apply each elimination sequence from $\mathcal{E}$ to $\textoverline{\textcode{A}}_{3}$ as a set of constraints.			    
				    \end{enumerate}
			\vspace{-2mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{$\text{\text{\textcode{Q}}}^\text{in}$-Constraints:~$(\Delta_{6})\text{ \textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$ are minimal}
		
			\label{fig:appendix.mutation.karel.8}
		}
    \end{subfigure}




	\caption{\textbf{(a)--(g)}: Illustration of Code Mutation for \textnormal{Karel}~task \emph{Diagonal} from the \emph{Intro to Programming with Karel} course by \emph{CodeHS.com}~\cite{intro_to_karel_codehs}; We present the \textnormal{Karel}~variant of \figref{fig:mutation} here.
	}

	\label{fig:appendix.mutation.karel}
	\vspace{-5mm}	
\end{figure}
\begin{figure}[h!]
\ContinuedFloat
\begin{subfigure}[b]{1\textwidth}
    \centering
			{
				\begin{boxcode}{18.5cm}{0.75}{1.0}
				       
						\textcolor{blue}{Shorthand notation for actions: $\text{\textsf{move}\xspace} \rightarrow \text{\textcode{M}}$, $\text{\textsf{turnL}\xspace} \rightarrow \text{\textcode{L}}$, $\text{\textcode{turnR}} \rightarrow \text{\textcode{R}}$,
						$\text{\textsf{pick}\xspace} \rightarrow \text{\textcode{piM}}$,
						$\text{\textsf{put}\xspace} \rightarrow \text{\textcode{puM}}$,
						$\phi \rightarrow \text{empty-action}$.}
					
			
				    \\
				    \\
				   
				    Local \textoverline{\textcode{A}}~constraints that define the values that each action sequence can take:
				    \vspace{-0.5mm}
                    \begin{enumerate}[(i)]
					\item \hspace{0.25em} $(\ha{1}{1} =\text{\textcode{M}} \vee \ha{1}{1} = \text{\textcode{L}}
					\vee \ha{1}{1} = \text{\textcode{R}} \vee \ha{1}{1} = \text{\textcode{piM}} \vee \ha{1}{1} = \text{\textcode{puM}} \vee \ha{1}{1} = \phi)$ 
					\item[] $\wedge (\ha{1}{2} =\text{\textcode{M}} \vee \ha{1}{2} = \text{\textcode{L}}
					\vee \ha{1}{2} = \text{\textcode{R}} \vee \ha{1}{2} = \text{\textcode{piM}} \vee \ha{1}{2} = \text{\textcode{puM}} \vee \ha{1}{2} = \phi) $ 
					\item[] $\wedge ( \ha{1}{3} =\text{\textcode{piM}} \vee \ha{1}{3} = \text{\textcode{puM}} )$ 
					\item[] $\wedge(\ha{1}{4} =\text{\textcode{M}} \vee \ha{1}{4} = \text{\textcode{L}}
					\vee \ha{1}{4} = \text{\textcode{R}} \vee \ha{1}{4} = \text{\textcode{piM}} \vee \ha{1}{4} = \text{\textcode{puM}} \vee \ha{1}{4} = \phi)$ 
					\item[] $\wedge (\ha{1}{5} =\text{\textcode{M}} \vee \ha{1}{5} = \text{\textcode{L}}
					\vee \ha{1}{5} = \text{\textcode{R}} \vee \ha{1}{5} = \text{\textcode{piM}} \vee \ha{1}{5} = \text{\textcode{puM}} \vee \ha{1}{5} = \phi)$ 
					
					\item $\wedge (\ha{1}{1} \neq \phi \vee \ha{1}{2} \neq \phi) \Rightarrow (\ha{1}{4} = \phi \wedge \ha{1}{5} = \phi) \wedge$
					
					\item[] $\wedge (\ha{1}{4} \neq \phi \vee \ha{1}{5} \neq \phi) \Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi)$
				
					
					
					\item \hspace{0.25em} $(\ha{2}{1} =\text{\textcode{M}} \vee \ha{2}{1} = \text{\textcode{L}}
					\vee \ha{2}{1} = \text{\textcode{R}} \vee \ha{2}{1} = \text{\textcode{piM}} \vee \ha{2}{1} = \text{\textcode{puM}} \vee \ha{2}{1} = \phi) $ 
					
					\item[] $\wedge(\ha{2}{2} =\text{\textcode{M}} \vee \ha{2}{2} = \text{\textcode{L}}
					\vee \ha{2}{2} = \text{\textcode{R}} \vee \ha{2}{2} = \text{\textcode{piM}} \vee \ha{2}{2} = \text{\textcode{puM}} \vee \ha{2}{2} = \phi)$ 
					
					\item[] $\wedge (\ha{2}{3} = \text{\textcode{M}} )$ 
					
					\item[] $\wedge (\ha{2}{4} =\text{\textcode{M}} \vee \ha{2}{4} = \text{\textcode{L}}
					\vee \ha{2}{4} = \text{\textcode{R}} \vee \ha{2}{4} = \text{\textcode{piM}} \vee \ha{2}{4} = \text{\textcode{puM}} \vee \ha{2}{4} = \phi)$ 
					
					\item[] $\wedge \big{(}(\ha{2}{5} = \text{\textcode{L}} \wedge \ha{2}{9} = \text{\textcode{L}}) \vee (\ha{2}{5} = \text{\textcode{R}} \wedge \ha{2}{9} = \text{\textcode{R}}) \vee (\ha{2}{5} = \text{\textcode{L}} \wedge \ha{2}{9} = \text{\textcode{R}}) \vee (\ha{2}{5} = \text{\textcode{R}} \wedge \ha{2}{9} = \text{\textcode{L}}) \big{)}$ 
					
					\item[] $\wedge (\ha{2}{6} =\text{\textcode{M}} \vee \ha{2}{6} = \text{\textcode{L}}
					\vee \ha{2}{6} = \text{\textcode{R}} \vee \ha{2}{6} = \text{\textcode{piM}} \vee \ha{2}{6} = \text{\textcode{puM}} \vee \ha{2}{6} = \phi)$ 
					
					\item[] $\wedge (\ha{2}{7} = \text{\textcode{M}})$
					
					\item[] $ \wedge (\ha{2}{8} =\text{\textcode{M}} \vee \ha{2}{8} = \text{\textcode{L}}
					\vee \ha{2}{8} = \text{\textcode{R}} \vee \ha{2}{8} = \text{\textcode{piM}} \vee \ha{2}{8} = \text{\textcode{puM}} \vee \ha{2}{8} = \phi)$ 
					
					\item[] $\wedge (\ha{2}{10} =\text{\textcode{M}} \vee \ha{2}{10} = \text{\textcode{L}}
					\vee \ha{2}{10} = \text{\textcode{R}} \vee \ha{2}{10} = \text{\textcode{piM}} \vee \ha{2}{10} = \text{\textcode{puM}} \vee \ha{2}{10} = \phi)$ 
					
					\item[] $\wedge (\ha{2}{11} = \text{\textcode{piM}} \vee \ha{2}{11} = \text{\textcode{puM}})$ 
					
					\item[] $\wedge (\ha{2}{12} =\text{\textcode{M}} \vee \ha{2}{12} = \text{\textcode{L}}
					\vee \ha{2}{12} = \text{\textcode{R}} \vee \ha{2}{12} = \text{\textcode{piM}} \vee \ha{2}{12} = \text{\textcode{puM}} \vee \ha{2}{12} = \phi)$ 
					
					\item[] $\wedge (\ha{2}{13} =\text{\textcode{M}} \vee \ha{2}{13} = \text{\textcode{L}}
					\vee \ha{2}{13} = \text{\textcode{R}} \vee \ha{2}{13} = \text{\textcode{piM}} \vee \ha{2}{13} = \text{\textcode{puM}} \vee \ha{2}{13} = \phi) $ 
					
					\item \hspace{0.25em} $ \big{(}(\ha{2}{1} \neq \phi \vee \ha{2}{2} \neq \phi) \Rightarrow (\ha{2}{4} = \phi \wedge \ha{2}{6} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{10} = \phi \wedge \ha{2}{12} = \phi \wedge \ha{2}{13} = \phi)\big{)}$
				    
				    \item[] $ \wedge \big{(}(\ha{2}{4} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge  \ha{2}{6} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{10} = \phi \wedge \ha{2}{12} = \phi \wedge \ha{2}{13} = \phi) \big{)}$
				    
				    \item[] $ \wedge \big{(}(\ha{2}{6} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge  \ha{2}{4} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{10} = \phi \wedge \ha{2}{12} = \phi \wedge \ha{2}{13} = \phi) \big{)}$
				     
				    \item[] $ \wedge \big{(}(\ha{2}{8} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge  \ha{2}{4} = \phi \wedge \ha{2}{6} = \phi \wedge \ha{2}{10} = \phi \wedge \ha{2}{12} = \phi \wedge \ha{2}{13} = \phi) \big{)}$
				    
				    \item[] $ \wedge \big{(}(\ha{2}{10} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge  \ha{2}{4} = \phi \wedge \ha{2}{6} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{12} = \phi \wedge \ha{2}{13} = \phi) \big{)}$
				    
				    \item[] $ \wedge \big{(}(\ha{2}{12} \neq \phi \vee \ha{2}{13} \neq \phi) \Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge \ha{2}{4} = \phi \wedge \ha{2}{6} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{10} = \phi) \big{)}$
				
					
					\item \hspace{0.25em} $(\ha{3}{1} =\text{\textcode{M}} \vee \ha{3}{1} = \text{\textcode{L}} \vee \ha{3}{1} = \text{\textcode{R}} \vee \ha{3}{1} = \text{\textcode{piM}} \vee \ha{3}{1} = \text{\textcode{puM}} \vee \ha{3}{1} = \phi)$ 
					\item[] $\wedge  (\ha{3}{2} =\text{\textcode{M}} \vee \ha{3}{2} = \text{\textcode{L}} \vee \ha{3}{2} = \text{\textcode{R}} \vee \ha{3}{2} = \text{\textcode{piM}} \vee \ha{3}{2} = \text{\textcode{puM}} \vee \ha{3}{2} = \phi)$ 
				   
				    \end{enumerate}
			
				\\
				 Global \textoverline{\textcode{A}}~constraints that allow actions to be added to either of $\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}$:
				    
				    \vspace{-0.5mm}
				    \begin{enumerate}[(i)]
				    \item $(\ha{1}{1} \neq \phi \vee \ha{1}{2} \neq \phi \vee \ha{1}{3} \neq \phi \vee \ha{1}{4} \neq \phi)$ 
				    \item[] \qquad $\Rightarrow (\ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge \ha{2}{4} = \phi \wedge \ha{2}{6} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{10} = \phi \wedge \ha{2}{12} = \phi \wedge \ha{2}{13} = \phi$ $\wedge$ $\ha{3}{1} = \phi \wedge \ha{3}{2} = \phi)$
				    
				   
				    
				   
				    
				     \item $(\ha{2}{1} \neq \phi \vee \ha{2}{2} \neq \phi \vee \ha{2}{4} \neq \phi \wedge \ha{2}{6} \neq \phi \wedge \ha{2}{8} \neq \phi \wedge \ha{2}{10} \neq \phi \wedge \ha{2}{12} \neq \phi \wedge \ha{2}{13} \neq \phi )$ 
				     \item[] \qquad $\Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi \wedge \ha{1}{4} = \phi \wedge \ha{1}{5} = \phi$ $\wedge$ $\ha{3}{1} = \phi \wedge \ha{3}{2} = \phi)$
				   
				   
				    
				     \item $(\ha{3}{1} \neq \phi \vee \ha{3}{2} \neq \phi)$
				     \item[] \qquad $\Rightarrow (\ha{1}{1} = \phi \wedge \ha{1}{2} = \phi \wedge \ha{1}{4} = \phi \wedge \ha{1}{5} = \phi \wedge \ha{2}{1} = \phi \wedge \ha{2}{2} = \phi \wedge \ha{2}{4} = \phi \wedge \ha{2}{6} = \phi \wedge \ha{2}{8} = \phi \wedge \ha{2}{10} = \phi \wedge$ $\ha{2}{12} = \phi \wedge \ha{2}{13} = \phi)$
				    
				     
				   
				    \end{enumerate}
				  
			\end{boxcode}
			\vspace{-3mm}
			\caption{$\text{\text{\textcode{Q}}}^\text{in}$-Constraints:~$(\Delta_{1})~\ensuremath{\textsc{ActionEdits}}(\{\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}\},  \ensuremath{\omega}(\cdot|~\text{\textcode{C}}^\text{in}))$}
		
			\label{fig:appendix.mutation.karel.7}
		}
\end{subfigure}
\caption{\textbf{(h)}: Illustration of Code Mutation for \textnormal{Karel}~task \emph{Diagonal} from the \emph{Intro to Programming with Karel} course by \emph{CodeHS.com}~\cite{intro_to_karel_codehs}; We present the \textnormal{Karel}~variant of \figref{fig:mutation} here.}
\end{figure}





					
					
			    
				
				
				
			
				

					
					
			    
			    
			
					
				
				
					
				
	
			
			
					
				
		    
			
			
					
				
		    
			
					
			    
					
					
				
			
			
					
			    
					
					
				
			





					
					
					
					
					
		
					


					
					
					
					
					
                
                
				
				












				
					
			    
					
					
				
			
			
						
					
			    
					
					
				
			
			



\section{Symbolic Execution: Additional Details}\label{appendix.sec.symbolicexecution}
In this section, we provide an example demonstrating how MCTS could guide the symbolic
execution in generating more suitable tasks, see Fig.~\ref{fig:appendix.mcts.symbolicexecution}.



\begin{figure}[h!]
\centering
	\begin{subfigure}[b]{.17\textwidth}
	\centering
	{
		\includegraphics[height=2.3cm]{fig/appendix_mcts_symbolicexecution/mcts_symbolicexecution_a.pdf}
		\caption{Initialization}
	
		\label{fig:appendix.mcts.symbolicexecution.init}
    }
    \end{subfigure}

  	\begin{subfigure}[b]{.27\textwidth}
  	\centering
  	{
		\includegraphics[height=4.7cm]{fig/appendix_mcts_symbolicexecution/mcts_symbolicexecution_tree.pdf}
		\caption{Search tree}
	
		\label{fig:appendix.mcts.symbolicexecution.tree}
	}
	\end{subfigure}	    

  	\begin{subfigure}[b]{.17\textwidth}
  	\centering
  	{
		\includegraphics[height=2.3cm]{fig/appendix_mcts_symbolicexecution/mcts_symbolicexecution_b.pdf}
		\caption{(1, 0, 1)}
		\label{fig:appendix.mcts.symbolicexecution.path1}
	}
	\end{subfigure}
	\begin{subfigure}[b]{.17\textwidth}
	\centering
	{
		\includegraphics[height=2.3cm]{fig/appendix_mcts_symbolicexecution/mcts_symbolicexecution_c.pdf}
		\caption{(1, 1, 0)}
	
		\label{fig:appendix.mcts.symbolicexecution.path2}
    }
    \end{subfigure}
  	\begin{subfigure}[b]{.17\textwidth}
  	\centering
  	{
		\includegraphics[height=2.3cm]{fig/appendix_mcts_symbolicexecution/mcts_symbolicexecution_d.pdf}
		\caption{(1, 1, 1, 0, 0)}
	
		\label{fig:appendix.mcts.symbolicexecution.path3}
	}
	\end{subfigure}

	\caption{Search strategy for guiding the symbolic execution; see the text below for details.
	}

	\label{fig:appendix.mcts.symbolicexecution}
\end{figure}

In Fig.~\ref{fig:appendix.mcts.symbolicexecution.tree}, we consider the MCTS search tree for the code $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.hoc.p1} obtained from the solution code of task \textsf{H4}\xspace~by mutation.  At the top of the tree, we have a ``Root'' node where the initial location/direction of the agent is picked from among the available choices. Node ``RU'' corresponds to the block \textsf{repeatUntilGoal}\xspace; the child ``1'' from a node ``RU'' corresponds to unrolling of the loop (i.e., \textcode{goal} is false).  Node ``If'' corresponds to the block \textsf{If}\xspace; the child ``1'' from a node ``If'' corresponds to executing the code inside (i.e., \textcode{pathR} is true). For the purpose of this demonstration, we limited the unrolling of the loops to a maximum of $3$; for our experiments, this depth is $2n (=20)$ as discussed in Appendix~\ref{appendix.sec.simulations}. Furthermore, in this demonstration, the initial location/direction for the agent are fixed as shown in  Fig.~\ref{fig:appendix.mcts.symbolicexecution.init}; for our experiments, we consider $5\times4 (=20)$ initial configurations which are picked by MCTS resulting in a large branching factor at the root of the tree.

Figs.~\ref{fig:appendix.mcts.symbolicexecution.path1},~\ref{fig:appendix.mcts.symbolicexecution.path2},~and~\ref{fig:appendix.mcts.symbolicexecution.path3} illustrate the symbolic execution output for three different paths in the search tree as discussed below:
\begin{itemize}
\item Fig.~\ref{fig:appendix.mcts.symbolicexecution.path1} corresponds to the path (``RU'':1, ``If'':0, ``RU'': 1). This path results in agent crashing the wall. As discussed in Section~\ref{sec.simulations}, $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\cdot)$ score is set to $0$ when $\ensuremath{\mathcal{F}_{\textnormal{nocrash}}}(\cdot) = 0$ and hence this tree path evaluates to low $\ensuremath{\mathcal{F}_{\textnormal{score}}}(\cdot)$ score. 
\item \looseness-1Fig.~\ref{fig:appendix.mcts.symbolicexecution.path2} corresponds to the path (``RU'':1, ``If'':1, ``RU'': 0). This path results in two moves and two turns.
\item Fig.~\ref{fig:appendix.mcts.symbolicexecution.path3} corresponds to the path (``RU'':1, ``If'':1, ``RU'': 1, ``If'':0, ``RU'': 0). This path results in three moves and two turns, and is the higher scoring path compared to other two paths.
\end{itemize}

MCTS is extremely effective as a search strategy and quickly learns to pick paths with high scores. For the same code $\text{\textcode{C}}^{\textnormal{out}}$ used in Fig.~\ref{fig:appendix.mcts.symbolicexecution} above, Fig.~\ref{fig:experiments.mcts.varytime} shows the temporal trends of different feature values in \ensuremath{\mathcal{F}_{\textnormal{score}}}~averaged over a time window of $100$ steps in our experiments. For further details, we refer the reader to \cite{kocsis2006bandit} for an overview of the MCTS procedure, and to \cite{luckow2018monte} where MCTS is used with symbolic execution to direct the exploration towards costly paths.

\section{Experimental Evaluation: Additional Details and Results}\label{appendix.sec.simulations}
This section elaborates the experimental setup and results described in Section~\ref{sec.simulations}. We begin by providing details on the MCTS procedure in the symbolic execution stage of our task synthesis algorithm. Furthermore, we provide insights on generating multiple tasks for a single code. We also illustrate some example output tasks which violate criteria (V) and (VI), and mutated codes which got pruned in the symbolic execution stage (see Figure~\ref{fig:experiments.analysis}).
Our implementation of the symbolic execution stage with MCTS procedure  is publicly available (see Footnote~\ref{footnote.githubrepo}).



\subsection{Specification of MCTS for Single Run and Additional Results}
In this section, we elaborate on the specification of MCTS, briefly discussed in Section~\ref{sec.simulations}. We begin by discussing choices that effect the scalability and run-time of MCTS procedure.


\textbf{Choice of initial location and direction.} When doing symbolic execution using MCTS, the procedure begins by picking an initial location and direction for the agent (see \figref{fig:symbolicexecution}(b)). Given a grid-size $n$, and four initial directions (\emph{north}, \emph{east}, \emph{south}, \emph{west}) of the agent to choose from, we get a total of $4n^2$ choices for our initial configuration of the grid-puzzle. In the implementation used for generating the results, we restricted the set of initial choices to $20$ (by choosing only $5$ initial locations of the grid including four corners and centre, and $4$ directions)---this aids in exploration by limiting the branching factor at the root of the MCTS's tree.

\textbf{Tree depth for symbolic execution.} The depth of the  symbolic tree depends on the nature of the corresponding solution code.  For codes without the \textsf{repeatUntilGoal}\xspace~or \textsf{while}\xspace~constructs (\textsf{H1}\xspace, \textsf{H2}\xspace, \textnormal{H3},  \textsf{K7}\xspace, \textsf{K8}\xspace~and \textsf{K9}\xspace), the tree-depth is bounded. But, for more complex codes (\textsf{H3}\xspace, \textsf{H4}\xspace, \textsf{H5}\xspace, and \textsf{K10}\xspace), the tree depth is unbounded. In our implementation,  we limited the unrolling of the loops to a maximum of $2n (=20)$. To get an insight into the complexity of the problem, we note that with $20$ initial choices and a depth of $2n$, there are over $40$ million leaves in the symbolic tree for codes \textsf{H4}\xspace~and \textsf{H5}\xspace~which contain conditionals nested inside \textsf{repeatUntilGoal}\xspace~or \textsf{while}\xspace~constructs.\footnote{The actual memory footprint of the MCTS procedure is small given that the symbolic tree is dynamically constructed during a run and the actual number of leaves explored is much lesser. In fact, the average runtime per output task (i.e., one MCTS run) as reported in Column $8$ of \figref{fig:experiments.analysis} is achieved on a laptop machine with $2.8$ GHz Quad-Core Intel Core i$7$ processor and $16$ GB RAM.} Next, we describe the details of our evaluation function for MCTS.








\textbf{Details on the evaluation function \ensuremath{\mathcal{F}_{\textnormal{score}}}.}
Our evaluation function $\ensuremath{\mathcal{F}_{\textnormal{score}}}(\text{\textcode{T}}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}, \text{\textcode{T}}^{\textnormal{in}}, \text{\textcode{C}}^{\textnormal{in}}) \in [0,1]$ measures the suitability of a generated task. A higher \ensuremath{\mathcal{F}_{\textnormal{score}}}~indicates a more suitable task. We describe the elements of our evaluation function in greater detail here. We defined it in Section~\ref{sec.simulations} and present it here again for completeness:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{score}}}(\text{\textcode{T}}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}, \text{\textcode{T}}^\textnormal{in}, \text{\textcode{C}}^\textnormal{in}) & = \underbrace{\mathbbm{1}{\big(\medmath{ \ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) \geq \delta_{\textnormal{qual}}, \ensuremath{\mathcal{F}_{\textnormal{nocrash}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) = 1, \ensuremath{\mathcal{F}_{\textnormal{nocut}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) = 1 }\big)}}_\text{2a} \cdot \\
    & \ \ \ \ \underbrace{\big[ \alpha_{1}\ensuremath{\mathcal{F}_{\textnormal{cov}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) + \alpha_{2}\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) + \alpha_{3} \ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{T}}^\textnormal{in}_\textnormal{vis}) \big]}_\text{2b} \label{evalfunc2} \tag{2}
\end{align*}
where $\mathbbm{1}$ is an indicator function and each constant $\alpha = 1/3$.
It is to be noted that component $2\textnormal{b}$ in Eq.\ref{evalfunc2} supplies the gradients for guiding the search in MCTS. At the end of the MCTS run (containing $2$ million iterations), the \textit{best} task (i.e, the one with the highest \ensuremath{\mathcal{F}_{\textnormal{score}}}~value) is picked only from the pool of generated tasks which satisfy $\ensuremath{\mathcal{F}_{\textnormal{cov}}}(\cdot) = 1, \ensuremath{\mathcal{F}_{\textnormal{score}}}(\cdot) > 0$. We discuss each constituent function of \ensuremath{\mathcal{F}_{\textnormal{score}}}~next.

\textbf{Task quality component of evaluation function.} $\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out},\text{\textcode{C}}^\textnormal{out}) \in [0,1]$ evaluates the quality and validity of $\text{\textcode{T}}^\textnormal{out}$. Its is defined as a linear combination of the normalized counts of certain features of $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ when $\text{\textcode{C}}^\textnormal{out}$ is executed. As certain elements differ in the two task types, \textnormal{HOC}~and \textnormal{Karel}, we define the features differently for each. More precisely, for \textnormal{HOC}~tasks, we have:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{qual}}}^{\textnormal{HOC}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out},\text{\textcode{C}}^\textnormal{out}) & = \frac{1}{4}\Big{(} \frac{\ensuremath{\#}\text{moves}}{2n} +  \frac{\ensuremath{\#}\text{turns}}{n} +  \frac{\ensuremath{\#}\text{segments}}{n/2} +  
    \frac{\ensuremath{\#}\text{long-segments}}{n/3} \Big{)}
\end{align*}
where the individual features are defined as 
\vspace{4mm}
\begin{itemize}
    \item \ensuremath{\#} moves: This refers to the count of `moves'.
   
    \item \ensuremath{\#} turns: This refers to the count of `turns'.
   
    \item \ensuremath{\#} segments: This refers to the number of consecutive sequence ($\geq 3$) of `moves'
    \item \ensuremath{\#} long-segments:  This refers to the number of longer consecutive sequence ($\geq 5$) of `moves'.
\end{itemize}
For \textnormal{Karel}~tasks, we additionally have two marker based features to define the quality of the task i.e,
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{qual}}}^{\textnormal{Karel}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out},\text{\textcode{C}}^\textnormal{out}) & = \frac{3}{4} \cdot \frac{1}{4}\Big{(} \frac{\ensuremath{\#}\text{moves}}{2n} +  \frac{\ensuremath{\#}\text{turns}}{n} +  \frac{\ensuremath{\#}\text{segments}}{n/2} +  
    \frac{\ensuremath{\#}\text{long-segments}}{n/3} \Big{)}
    \\ & + \frac{1}{4} \cdot \frac{1}{2} \Big{(}\frac{\ensuremath{\#}\text{pick-markers}}{n} + \frac{\ensuremath{\#}\text{put-markers}}{n}\Big{)}
\end{align*}
where the additional features are defined as 
\begin{itemize}
    \item \ensuremath{\#} pick-markers: This refers to the count of `pick-marker' activity
    \item \ensuremath{\#} put-markers: This refers to the count of `put-marker' activity
\end{itemize}
\looseness-1 While we have used high-level features of  $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ to define the quality of a task, one could also embed more specific domain knowledge in defining these features to obtain more interesting/complex tasks.

\textbf{Task dissimilarity component of the evaluation function.}
$\ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in [0,1]$ evaluates the visual dissimilarity of $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ w.r.t. $\text{\textcode{T}}^{\textnormal{in}}_\textnormal{vis}$. We define it as a linear combination of the dissimilarity features as follows:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) & = \frac{1}{3}\Big{(}
   
    \textnormal{diss}(\textnormal{loc}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) +  \textnormal{diss}(\textnormal{dir}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) + 
    \textnormal{diss}(\textnormal{grid-cells}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in})
    \Big{)}
\end{align*}
where the individual features are defined as
\begin{itemize}
    \item $\textnormal{diss}(\textnormal{loc}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in \{0, 1\}$ measures the dissimilarity in the agent's initial location in the task-puzzles $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{in}_\textnormal{vis}$.
    
    
    \item $\textnormal{diss}(\textnormal{dir}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in \{0, 1\}$ measures the dissimilarity in the agent's initial direction in the task-puzzles $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{in}_\textnormal{vis}$.
  
    
    \item $\textnormal{diss}(\textnormal{grid-cells}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis}^\textnormal{in}) \in [0, 1]$ measures the grid-cell level dissimilarity in the task-puzzles $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{in}_\textnormal{vis}$. This is computed as the normalized Hamming distance w.r.t. the two grid-worlds (i.e., number of cells which are different, multiplied with a normalization factor of $\frac{2}{n^2}$).
\end{itemize}







\textbf{Deep dive into an MCTS run for Karel.} Analogous to the example provided in Section~\ref{sec.simulations}, we take a closer look at an MCTS run for the \textnormal{Karel}~task~\textsf{K10}\xspace, shown in \figref{fig:appendix.experiments.mcts}. \figref{fig:appendix.experiments.mcts.varytime.1} and \figref{fig:appendix.experiments.mcts.varytime.2} illustrate the improvement in various components of \ensuremath{\mathcal{F}_{\textnormal{score}}}~as the number of MCTS iterations increases. Best tasks at different iterations are shown in \figref{fig:appendix.experiments.mcts.best1} and   \figref{fig:appendix.experiments.mcts.best3}. As expected, the more the iterations, the better the tasks which are generated.
\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.45\textwidth}
	\centering
	{
		\includegraphics[width=1\textwidth]{fig/appendix_mctsplots_karel/20200610/karel-F_mutation-8-252_run5/mctsplot_vary_time_with_karel-features.pdf}
		\caption{Trends in \ensuremath{\mathcal{F}_{\textnormal{score}}}~features}
	
		\label{fig:appendix.experiments.mcts.varytime.1}
    }
    \end{subfigure}
    \quad

	\begin{subfigure}[b]{.45\textwidth}
	\centering
	{
		\includegraphics[width=1\textwidth]{fig/appendix_mctsplots_karel/20200610/karel-F_mutation-8-252_run5/mctsplot_vary_time_diss-features.pdf}
		\caption{Trends in \ensuremath{\mathcal{F}_{\textnormal{score}}}~features capturing dissimilarity}
	
		\label{fig:appendix.experiments.mcts.varytime.2}
    }
    \end{subfigure}
    \\
    \vspace{2mm}

  	\begin{subfigure}[b]{.45\textwidth}
  	\centering
  	{
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4/mctsplot_best_20.pdf}
		\caption{Best at $20$}
		\label{fig:appendix.experiments.mcts.best1}
	}
	\end{subfigure}
	\quad
  	\begin{subfigure}[b]{.45\textwidth}
  	\centering
  	{
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4/mctsplot_best_2000.pdf}
		\caption{Best at $2$M}
	
	
		\label{fig:appendix.experiments.mcts.best3}
	}
	\end{subfigure}	

	\caption{Illustration of a single MCTS run on $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.karel.p1} obtained from solution code of task \textsf{K10}\xspace~by mutation. (a, b) show the temporal trends of different feature values in \ensuremath{\mathcal{F}_{\textnormal{score}}}~averaged over a time window of $100$ steps. (c, d)~show the best, i.e., highest scoring, tasks generated up to times $2 \times 10^1$ and $2 \times 10^6$ respectively.
	}
	\vspace{-10mm}
	\label{fig:appendix.experiments.mcts}
\end{figure}


\subsection{Specification of MCTS for Multiple Runs with Diversity and Additional Results}
Our task synthesis algorithm can also generate multiple tasks for a \emph{single} code, with sufficient diversity. To achieve this, we modify the evaluation function \ensuremath{\mathcal{F}_{\textnormal{score}}}~guiding the MCTS search. We introduce a diversity measure \ensuremath{\mathcal{F}_{\textnormal{diversity}}}~which measures the diversity between the generated tasks. More concretely, when generating a new $(k+1)^{\textsuperscript{th}}$ task, we capture the diversity score w.r.t the tasks generated in the previous k-runs of MCTS $\{ \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}, \ldots, \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},k} \}$.


\textbf{Modified evaluation function \ensuremath{\mathcal{F}_{\textnormal{score}}}.}
Our evaluation function with the new diversity component is given below with each $\alpha = 1/4$. We have $\ensuremath{\mathcal{F}_{\textnormal{score}}}(\text{\textcode{T}}^\textnormal{out}, \text{\textcode{C}}^\textnormal{out}, \text{\textcode{T}}^\textnormal{in}, \text{\textcode{C}}^\textnormal{in}, \{ \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}, \ldots, \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},k} \}):=$
\begin{align*}
    &\quad \underbrace{\mathbbm{1}{\big(\medmath{ \ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) \geq \delta_{\textnormal{qual}}, \ensuremath{\mathcal{F}_{\textnormal{nocrash}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) = 1, \ensuremath{\mathcal{F}_{\textnormal{nocut}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) = 1 }\big)}}_\text{3a} \cdot 
    \\
     &\quad  \underbrace{\big[ \alpha_{1}\ensuremath{\mathcal{F}_{\textnormal{cov}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) + \alpha_{2}\ensuremath{\mathcal{F}_{\textnormal{qual}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}) + \alpha_{3} \ensuremath{\mathcal{F}_{\textnormal{diss}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{T}}^\textnormal{in}_\textnormal{vis}) +
    \alpha_{4} \ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~\{ \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1} \ldots \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},k} \})
    \big]}_\text{3b} 
\label{evalfunc3} 
\tag{3}
\end{align*}



\textbf{Diversity score of tasks \ensuremath{\mathcal{F}_{\textnormal{diversity}}}.} Here, we describe the diversity component of the evaluation function. $\ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~\{ \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1},\ldots, \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},k} \}) \in [0,1]$ operates on a pool of generated tasks, and computes a diversity score for the new task w.r.t the tasks in the pool. Initially, the pool of tasks generated is empty. In this case, we have $\ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~\{\}) = 1$.


After one run of MCTS, we have one task in the task pool $\{\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$\}. We define the diversity score for a subsequent task $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ as follows. First, if $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis} = \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$ then we set $\ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~ \{\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1} \}) = 0$. Otherwise, the diversity score is given by 
\begin{align*}
\ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~ \{\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1} \}) & = \frac{1}{4} \Big{(}
   
    \textnormal{diss}(\textnormal{loc}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis,1}^\textnormal{out}) 
    +  \textnormal{diss}(\textnormal{dir}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis,1}^\textnormal{out}) \\
   & + \textnormal{diss}(\textnormal{grid-cells}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis,1}^\textnormal{out})
    +  \textnormal{diss}(\textnormal{symbolic-paths}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis,1}^\textnormal{out})
    \Big{)}
\end{align*}
where the individual features are defined as 
\begin{itemize}
    \item $\textnormal{diss}(\textnormal{loc}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis,1}^\textnormal{out}) \in \{0,1\}$ measures the dissimilarity in the agent's initial location in the task-puzzles $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$.
    \item $\textnormal{diss}(\textnormal{dir}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_\textnormal{vis,1}^\textnormal{out}) \in \{0,1\}$ measures the dissimilarity in the agent's initial direction in the task-puzzles $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$.
    \item $\textnormal{diss}(\textnormal{grid-cells}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_{\textnormal{vis},1}^\textnormal{out}) \in [0,1]$ measures the grid-cell level dissimilarity in the task-puzzles $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$.  This is computed as the normalized Hamming distance w.r.t. the two grid-worlds (i.e., number of cells which are different, multiplied with a normalization factor of $\frac{2}{n^2}$).
     \item \looseness-1 $\textnormal{diss}(\textnormal{symbolic-paths}~|~\text{\textcode{T}}_\textnormal{vis}^\textnormal{out}, \text{\textcode{T}}_{\textnormal{vis},1}^\textnormal{out}) \in [0,1]$ measures the dissimilarity in the symbolic-paths used in the generation of  $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$ and $\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$. This is computed as the normalized ``edit distance" between these paths.
    
\end{itemize}

After we have run $k$ MCTS runs, the pool of tasks generated is populated ($\{\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1} \ldots \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},k}\} $)
and the diversity score of the subsequent task is computed as follows:
\begin{align*}
    \ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~\{\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}, \ldots, \text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},k}\} ) & = \min_{i \in [k]} \ensuremath{\mathcal{F}_{\textnormal{diversity}}}(\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}~|~\{\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},i}\} )
\end{align*}

As the pool of tasks grow, it becomes more constrained to generate a task that is diverse from all the tasks in the pool. In general, there is a limit to the number of tasks per code that can be generated---eventually, the new task will have \ensuremath{\mathcal{F}_{\textnormal{diversity}}}~to be $0$ or \ensuremath{\mathcal{F}_{\textnormal{score}}}~to be $0$. As stated in Section~\ref{sec.simulations}, for each code $\text{\textcode{C}}^{\textnormal{out}}$, we generated up to $10$ different visual tasks using this process.

 
\textbf{Illustration of output tasks using diversity.} We illustrate our diverse task generation process on both \textnormal{HOC}~and \textnormal{Karel}~tasks. \figref{fig:appendix.experiments.mcts.hoc.diversity} shows the $10$ diverse tasks generated for code shown in \figref{fig:intro.hoc.p1}, while \figref{fig:appendix.experiments.mcts.karel.diversity} shows the $6$ diverse tasks generated for the code shown in \figref{fig:intro.karel.p1}.

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_1.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},1}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.1}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_2.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},2}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.2}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_3.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},3}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.3}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_4.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis},4}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.4}
	}
	\end{subfigure}	

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_5.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 5}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.5}
	}
	\end{subfigure}		

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_6.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 6}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.6}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_7.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 7}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.7}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_8.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 8}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.8}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_9.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 9}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.9}
	}
	\end{subfigure}	

	\begin{subfigure}[b]{.18\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_hoc/hoc-G_mutation-6-22_run2_diversity/mcts_diversity_10.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 10}$}
		 \label{fig:appendix.experiments.mcts.hoc.diversity.10}
	}
	\end{subfigure}		



	\caption{Illustration of task diversity on $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.hoc.p1} which was obtained from solution code of task \textsf{H4}\xspace~by mutation. All the $10$ diverse tasks generated are shown here.

	}
	\vspace{-4mm}
	\label{fig:appendix.experiments.mcts.hoc.diversity}
\end{figure}

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.32\textwidth}
	\centering
	{
	
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4_diversity/mcts_diversity_1.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 1}$}
		 \label{fig:appendix.experiments.mcts.karel.diversity.1}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.32\textwidth}
	\centering
	{
	
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4_diversity/mcts_diversity_2.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 2}$}
		 \label{fig:appendix.experiments.mcts.karel.diversity.2}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.32\textwidth}
	\centering
	{
	
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4_diversity/mcts_diversity_3.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 3}$}
		 \label{fig:appendix.experiments.mcts.karel.diversity.3}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.32\textwidth}
	\centering
	{
	
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4_diversity/mcts_diversity_4.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 4}$}
		 \label{fig:appendix.experiments.mcts.karel.diversity.6}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.32\textwidth}
	\centering
	{
	
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4_diversity/mcts_diversity_5.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 5}$}
		 \label{fig:appendix.experiments.mcts.karel.diversity.7}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.32\textwidth}
	\centering
	{
	
		\includegraphics[height=2.00cm]{fig/appendix_mctsplots_karel/20200607/karel-F_mutation-8-252_run4_diversity/mcts_diversity_6.pdf}
	
		\caption{$\text{\textcode{T}}^\textnormal{out}_{\textnormal{vis}, 6}$}
		 \label{fig:appendix.experiments.mcts.karel.diversity.8}
	}
	\end{subfigure}	


	\caption{Illustration of task diversity on $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.karel.p1} which was obtained from solution code of task \textsf{K10}\xspace~by mutation. First $6$ diverse tasks are shown here.
	}
	\vspace{-4mm}
	\label{fig:appendix.experiments.mcts.karel.diversity}
\end{figure}



\subsection{Insights into Results of \figref{fig:experiments.analysis}}
In this section, we provide further insights into the final results presented \figref{fig:experiments.analysis}. In particular, we illustrate few limitations of the codes and tasks we generate (w.r.t task-synthesis objectives defined in Section~\ref{sec.problem}):


\begin{itemize}
\item \textbf{Limitations of mutated codes generated}: Column $4$ of \figref{fig:experiments.analysis} lists the number of codes generated by our mutation stage. However this set ($\#\text{\textcode{C}}^\textnormal{out}_{\Delta=\textnormal{all}}$) continues to have few semantic irregularities (as discussed in Section \ref{sec.approach.mutation}). Some of these irregularities are illustrated in \figref{fig:appendix.experiments.problematic.pruned}. These codes are pruned by the symbolic execution stage of our algorithm, and the revised set of codes($\#\text{\textcode{C}}^\textnormal{out}$) is listed in Column $6$ of \figref{fig:experiments.analysis}.

\item \textbf{Tasks which violate  task-synthesis objective $\textnormal{(V)}$}: Out of the final set of tasks generated (shown in Column $7$ of \figref{fig:experiments.analysis}), some of them violate objective (V). The fraction of the tasks which satisfy this particular objective are listed in Column $9$ of \figref{fig:experiments.analysis}. In \figref{fig:appendix.experiments.problematic.structure} we illustrate two examples which violate the objective, in output tasks for \textsf{H4}\xspace~and \textsf{H5}\xspace.
\item \textbf{Tasks which violate task-synthesis objective $\textnormal{(VI)}_{\delta_\textnormal{mini} = 1}$}: Column $10$ of \figref{fig:experiments.analysis} lists the fraction of the tasks generated that satisfy this particular objective, on task-minimality. In \figref{fig:appendix.experiments.problematic.minimality}, we illustrate two examples of tasks which violate this minimality constraint with $\delta_\textnormal{mini} = 1$.
\end{itemize}


\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{move}\xspace\\
				\quad \textcode{turnRight}\\
				\quad \textsf{move}\xspace\\
				\quad \textcode{turnRight}\\
				\quad \textsf{move}\xspace\\
				\textcode{\}}
				\\
				\\
				\\
				\vspace{4.3mm}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{H1}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.1}
    }
    \end{subfigure}
  	\quad  	

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textcode{turnLeft}\\				
				\quad \textsf{repeat}\xspace\textcode{(5}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnRight}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
				\\
				\\
				\vspace{0.5mm}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{H2}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.2}
    }
    \end{subfigure}
  	\quad  	

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeat}\xspace\textcode{(4}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \textcode{\}}\\
				\quad \textcode{turnLeft}\\
				\quad \textsf{move}\xspace\\
				\quad \textcode{turnLeft}\\
				\quad \textsf{repeat}\xspace\textcode{(6}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \textcode{\}}\\
				\textcode{\}}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textnormal{H3}: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.3}
    }
    \end{subfigure}
  	\quad  	
 
	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnLeft}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnLeft}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
				\\
				\vspace{1.7mm}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{H3}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.4}
    }
    \end{subfigure}
  	\\
 
	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{turnRight}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathRight}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\vspace{1mm}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{H4}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.5}
    }
    \end{subfigure}
  	\quad  	
 
	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
				\quad \quad \quad \textsf{move}\xspace\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
			
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\				
				\quad \textcode{\}}\\
				\textcode{\}}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{H5}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.6}
    }
    \end{subfigure}
  	\quad  	
 
	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.70}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeat}\xspace\textcode{(5}\textcode{)\{}\\
				\quad \quad \textcode{pickMarker}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{putMarker}\\				
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
				\\				
				\vspace{1.8mm}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{K8}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.7}
    }
    \end{subfigure}
  	\quad  	
 
	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{3.8cm}{0.75}{0.70}
			\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
			\quad \textcode{putMarker}\\
			\quad \textsf{while}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \quad \textsf{move}\xspace\\
			\quad \quad \textcode{turnLeft}\\
			\quad \quad \textcode{putMarker}\\	
			\quad \textcode{\}}\\
			\textcode{\}}
			\\
			\vspace{2mm}
		\end{boxcode}
		\vspace{-2mm}
		\caption{\textsf{K10}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.pruned.8}
    }
    \end{subfigure}
  	\quad  	  	  	

	\vspace{-3.5mm}
    \caption{Illustration of codes with semantic irregularities in Column $\text{\textcode{C}}^\textnormal{out}_{\Delta=\textnormal{all}}$ of \figref{fig:experiments.analysis}. (a)--(f) show the semantic irregularities in mutated codes generated for \textnormal{HOC}~tasks. All of these codes lead to circular paths in output task, and are pruned out in the symbolic execution stage, by the \ensuremath{\mathcal{F}_{\textnormal{nocut}}}~component of the \ensuremath{\mathcal{F}_{\textnormal{score}}}~measure. In particular, consider the semantic irregularity presented in (g). This code corresponding to the reference task \textsf{K8}\xspace, has redundant marker activity. With each iteration of \textsf{repeat}\xspace, the \textcode{pickMarker}~and \textcode{putMarker}~actions occur consecutively, leading to no change in marker activity in the output. (h) illustrates a mutated code for reference task \textsf{K10}\xspace~where if the \textsf{while}\xspace~is executed more than once, \textcode{putMarker}~activity occurs in the same location consecutively leading to a crash (as only one marker is allowed per grid-cell); if \textsf{while}\xspace~is executed only once, the corresponding task generated has a short-cut to the goal.
	}

	\vspace{-2.5mm}
	\label{fig:appendix.experiments.problematic.pruned}
\end{figure}


\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_problematic-examples/criteria_structure_hoc-G_in-hoc-G_mutation-5-19_div3.pdf}
	
		\caption{\textsf{H4}\xspace: $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$}
		 \label{fig:appendix.experiments.problematic.structure.1}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{4.0cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathRight}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
				\\
				\vspace{1mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{\textsf{H4}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.problematic.structure.2}
    }
    \end{subfigure}
  	\quad \quad 

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_problematic-examples/criteria_structure_hoc-H_in-hoc-H_mutation-6-36_div1.pdf}
	
		\caption{\textsf{H5}\xspace: $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$}
		 \label{fig:appendix.experiments.problematic.structure.3}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{4.0cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
				\quad \quad \quad \textsf{move}\xspace\\
				\quad \quad \quad \textsf{move}\xspace\\				
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\				
				\quad \textcode{\}}\\
				\textcode{\}}
			
		\end{boxcode}
		\vspace{-1mm}
		\caption{\textsf{H5}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.problematic.structure.4}
    }
    \end{subfigure}
  	\quad  	

	\vspace{-1.5mm}
\caption{Illustration of violation of task-synthesis objective (V) by generated output tasks for reference tasks \textsf{H4}\xspace~and \textsf{H5}\xspace. (a, b) show the irregularity in generated task ($\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}$) for \textsf{H4}\xspace~which leads to only a straight path in the visual-puzzle. The corresponding code renders the \textsf{If}\xspace~construct redundant. (c, d) illustrate a similar irregularity in the generated task ($\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}$) for \textsf{H5}\xspace. Here, \textsf{IfElse}\xspace~construct is not needed for the optimal solution.
	}

	\vspace{-2.5mm}
	\label{fig:appendix.experiments.problematic.structure}
\end{figure}


\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_problematic-examples/criteria_minimality_hoc-G_in-hoc-G_mutation-6-12_div6}
	
		\caption{\textsf{H4}\xspace: $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$}
		 \label{fig:appendix.experiments.problematic.minimality.1}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{4.0cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{move}\xspace\\
				\quad \textcode{turnRight}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathRight}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\vspace{3mm}
		\end{boxcode}
		\vspace{-1mm}
		\caption{\textsf{H4}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.problematic.minimality.2}
    }
    \end{subfigure}
  	\quad \quad

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_problematic-examples/criteria_minimality_hoc-H_in-hoc-H_mutation-6-27_div1.pdf}
	
		\caption{\textsf{H5}\xspace: $\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}$}
		 \label{fig:appendix.experiments.problematic.minimality.3}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
    
		\begin{boxcode}{4.0cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textcode{turnRight}\\
				\quad \textsf{move}\xspace\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathAhead}\textcode{)\{}\\
				\quad \quad \quad \textsf{move}\xspace\\
				\quad \quad \textcode{\}}\\
				\quad \quad \textcode{\textsc{Else}}\textcode{\{}\\
				\quad \quad \quad \textcode{turnRight}\\
				\quad \quad \textcode{\}}\\				
				\quad \textcode{\}}\\
				\textcode{\}}
			
		\end{boxcode}
		\vspace{-1mm}
		\caption{\textsf{H5}\xspace: $\text{\textcode{C}}^\textnormal{out}$}
		\label{fig:appendix.experiments.problematic.minimality.4}
    }
    \end{subfigure}
  	\quad  	

	\vspace{-1.5mm}
	\caption{\looseness-1 Illustration of violation of task-synthesis objective (V1), with $\delta_\textnormal{mini} = 1$ by generated output tasks for reference tasks \textsf{H4}\xspace~and \textsf{H5}\xspace. (a, b) show the violation of task minimality, for the task ($\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}$) generated for \textsf{H4}\xspace. In particular, the first two actions in the code shown in (b) are unnecessary. Similarly, (c, d) show the violation of task minimality, for the task ($\text{\textcode{T}}^\textnormal{out}_\textnormal{vis}, \text{\textcode{C}}^\textnormal{out}$) generated for \textsf{H5}\xspace.
	}
	\vspace{-2.5mm}
	\label{fig:appendix.experiments.problematic.minimality}
\end{figure}



\subsection{Additional Results and Discussions}
\subsection{Adding More Variability to Output Tasks}\label{appendix.sec.simulations.more_variability}
Here, we propose a few simple extensions to our task generation algorithm allowing us to add more variability in the visual puzzles. We show that high variability can be achieved through suitable post-processing and pre-processing of the generated tasks (happening after and before the symbolic execution process, respectively). We describe each of these strategies next.

\textbf{Different grid-sizes.}
A simple strategy to enhance task variability is by altering the grid-size parameter $n$. \figref{fig:appendix.gridsz} illustrates the tasks generated with different values of the grid-size parameter $n$. For instance, this strategy is employed in generating multiple input-output pairs for Karel tasks in \textit{Intro to Programming with Karel} course by \textit{CodeHS.com}~\cite{intro_to_karel_codehs}.

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_vary-gridsz/mcts_variants_vary-gridsz_12.pdf}
	
		\caption{$\text{\textcode{T}}^{\textnormal{out}}_{\textnormal{vis}}$; $n = 10$}
		 \label{fig:appendix.samegridsz}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_vary-gridsz/mcts_variants_vary-gridsz_10.pdf}
	
		\caption{$\text{\textcode{T}}^{\textnormal{out}}_{\textnormal{vis}}$; $n = 8$}
		 \label{fig:appendix.gridsz8}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.22\textwidth}
	\centering
	{
	
		\includegraphics[height=2.39cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_vary-gridsz/mcts_variants_vary-gridsz_8.pdf}
	
		\caption{$\text{\textcode{T}}^{\textnormal{out}}_{\textnormal{vis}}$; $n = 6$}
		 \label{fig:appendix.gridsz6}
	}
	\end{subfigure}


	\caption{
	Tasks generated for $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.hoc.p1}  when varying grid-size ($n$).

	}

	\label{fig:appendix.gridsz}
\end{figure}

\textbf{Post-processing: Using distractor paths.}
One of the ways to add variability to the tasks is by adding \emph{distractor-paths}, to the generated tasks. These paths are added after the symbolic execution stage is complete, and a basic task has been generated. \figref{fig:appendix.nopostprocess} shows the task generated  without any post-processing of the output of symbolic execution, carried out on $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.hoc.p1}. \figref{fig:appendix.postprocess1}, and \figref{fig:appendix.postprocess2} illustrate two different post-processing patterns that yield tasks with greater variability, for the same code.

\textbf{Pre-processing: Using different initializations of grid cells.}
We could also add task variability by initializing the grid-cells differently, before they are subjected to symbolic execution for task synthesis. We have a set of fixed grid-patterns, which when chosen as initializations of the grid-world yield very different looking output tasks. \figref{fig:appendix.nopreprocessing} shows the task generated for $\text{\textcode{C}}^{\textnormal{out}}$ from \figref{fig:intro.hoc.p1}~without any pre-processing on the grid-cells. \figref{fig:appendix.preprocessing1} and \figref{fig:appendix.preprocessing2} show two different tasks obtained using different grid-initializations, for the same code. 



\clearpage 



\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.465\textwidth}
	\centering
	{
	
		\includegraphics[trim={0 0.55cm 0 0},clip,height=2.45cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_post-distractor/mcts_variants_post-distractor_1.pdf}
		\vspace{-4mm}
		\caption{No post processing}
		 \label{fig:appendix.nopostprocess}
	}
	\end{subfigure}
	\\

	\begin{subfigure}[b]{.465\textwidth}
	\centering
	{
	
		\includegraphics[trim={0 0.55cm 0 0},clip,height=2.45cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_post-distractor/mcts_variants_post-distractor_2.pdf}
		\vspace{-4mm}
		\caption{Post-processing 1}
		 \label{fig:appendix.postprocess1}
	}
	\end{subfigure}
	\quad \ \ 

	\begin{subfigure}[b]{.465\textwidth}
	\centering
	{
	
		\includegraphics[trim={0 0.55cm 0 0},clip,height=2.45cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_post-distractor/mcts_variants_post-distractor_3.pdf}
		\vspace{-4mm}
		\caption{Post-processing 2}
		 \label{fig:appendix.postprocess2}
	}
	\end{subfigure}


	\caption{Illustration of the (post-processing) distractor path strategy to increase task variability on tasks generated from $\text{\textcode{C}}^{\textnormal{out}}$ in \figref{fig:intro.hoc.p1} which was obtained from solution code of task \textsf{H4}\xspace~by mutation. (a) illustrates the basic task obtained after symbolic execution. (b, c) show two different distractor paths added after the symbolic execution stage, yielding visually very different tasks.
	}

	\label{fig:appendix.postprocess}
\end{figure}


\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.465\textwidth}
	\centering
	{
	
		\includegraphics[trim={0 0.55cm 0 0},clip,height=2.45cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_pre-constraints/mcts_variants_pre-constraints_cons-none.pdf}
		\vspace{-4mm}
		\caption{No grid-cell initialization}
		 \label{fig:appendix.nopreprocessing}
	}
	\end{subfigure}
	\\

	\begin{subfigure}[b]{.465\textwidth}
	\centering
	{
	
		\includegraphics[trim={0 0.55cm 0 0},clip,height=2.45cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_pre-constraints/mcts_variants_pre-constraints_cons1.pdf}
		\vspace{-4mm}
		\caption{Grid-cell initialization 1}
		 \label{fig:appendix.preprocessing1}
	}
	\end{subfigure}
	\quad \ \ 

	\begin{subfigure}[b]{.465\textwidth}
	\centering
	{
	
		\includegraphics[trim={0 0.55cm 0 0},clip,height=2.45cm]{fig/appendix_mctsplots_variants/hoc-G_mutation-6-22_variants_pre-constraints/mcts_variants_pre-constraints_cons2.pdf}
		\vspace{-4mm}
		\caption{Grid-cell initialization 2}
		 \label{fig:appendix.preprocessing2}
	}
	\end{subfigure}


	\caption{Illustration of the (pre-processing) grid-cell initialization strategy to increase task variability on tasks generated from $\text{\textcode{C}}^{\textnormal{out}}$ in  \figref{fig:intro.hoc.p1} which was obtained from solution code of task \textsf{H4}\xspace~by mutation. (a) illustrates the basic task obtained after symbolic execution. (b, c) show two different grid-cell initializations, yielding visually very different tasks.
	}

	\label{fig:appendix.preprocessing}
\end{figure}


\section{User Study: Additional Details and Results}\label{appendix.sec.userstudy}
\vspace{-2mm}
In this section, we discuss additional details of our user study and expand on the key results provided in Section \ref{sec.userstudy}. For our user study, we used $4$ reference tasks (\textsf{H2}\xspace, \textsf{H3}\xspace, \textsf{H4}\xspace, and \textsf{H5}\xspace). We developed an web app where participants, recruited through Amazon Mechanical Turk, were asked to solve tasks generated by four algorithms, $\ensuremath{\textsc{Same}}, \ensuremath{\textsc{Tutor}}, \ensuremath{\textsc{MutTask}}, \text{ or } \ensuremath{\textsc{SynTask}}$ (described in Section~\ref{sec.userstudy}). Next, we describe the interface of our app and details of the questionnaire. The web app is publicly available (see Footnote~\ref{footnote.userstudyapp}).

\begin{figure}[h!]
\centering

	\begin{subfigure}[b]{0.48\textwidth}
	\centering
	{
    	\begin{adjustbox}{varwidth=1\textwidth,fbox,center}
	    
		    \includegraphics[trim={0.4cm 0 0.4cm 0},clip,width=1\textwidth]{fig/appendix_userstudy/interface_v1/step0.png}
	       
		\end{adjustbox}
		\caption{Login and welcome page}
		 \label{fig:appendix.userstudy.login}
	}
	\end{subfigure}
	\ \ 

	\begin{subfigure}[b]{.48\textwidth}
	\centering
	{
    	\begin{adjustbox}{varwidth=1\textwidth,fbox,center}
	    
		    \includegraphics[trim={0.4cm 0 0.4cm 0},clip,width=1\textwidth]{fig/appendix_userstudy/interface_v1/step1.png}
    	
		\end{adjustbox}    		
		\caption{Step $1$: Coding task with solution}
		 \label{fig:appendix.userstudy.step1}
	}
	\end{subfigure}
	\\
	\vspace{2mm}

	\begin{subfigure}[b]{.48\textwidth}
	\centering
	{
	    \begin{adjustbox}{varwidth=1\textwidth,fbox,center}
		   
		    \includegraphics[trim={0.4cm 0 0.4cm 0},clip,width=1\textwidth]{fig/appendix_userstudy/interface_v1/step2.png}
		   
		\end{adjustbox} 		    
		\caption{Step $2$: Solve new coding task}
		 \label{fig:appendix.userstudy.step2}
	}
	\end{subfigure}
	\ \ 

	\begin{subfigure}[b]{.48\textwidth}
	\centering
	{
    	\begin{adjustbox}{varwidth=1\textwidth,fbox,center}
	    
		    \includegraphics[trim={0.4cm 0 0.4cm 0},clip,width=1\textwidth]{fig/appendix_userstudy/interface_v1/step3.png}
		   
		\end{adjustbox}
		\caption{Step $3$: Survey}
		 \label{fig:appendix.userstudy.step3}
	}
	\end{subfigure}		

	\vspace{-1.5mm}
	\caption{Interface of the app.}


	\label{fig:appendix.userstudy.app}
\end{figure}

\vspace{-4mm}
\subsection{App Interface and Questionnaire}
Our online app was developed using the publicly available toolkit of Blockly Games~\cite{googleblockly} and provides an interface for a participant to practice Block-based programming tasks for \textnormal{HOC}. Participants were familiarized with the tasks by a small tutorial given before they logged-in to the app. Each participant was randomly assigned a reference task, an algorithm (out of the four chosen for evaluation), and a particular task generated based on the chosen algorithm. These elements constituted a ``practice session" for a participant. Each session consisted of three steps. In Step $1$, the reference task along with its solution code was shown to the participant (\figref{fig:appendix.userstudy.step1}). In Step $2$, the participant was asked to solve a new task (\figref{fig:appendix.userstudy.step2}). The new task was generated by one of the four algorithms: $\ensuremath{\textsc{Same}}, \ensuremath{\textsc{Tutor}}, \ensuremath{\textsc{MutTask}}, \text{ or } \ensuremath{\textsc{SynTask}}$. To solve this new task, the participant was given $10$ tries. If they successfully solved the task or ran out of tries, they were directed to Step $3$ of the practice session, the survey~(\figref{fig:appendix.userstudy.step3}). Here, they were presented with a question on the visual dissimilarity of the tasks from Step 1 and Step 2, which was to be answered on a $4$-point Likert scale as used in \cite{polozov2015}:
\begin{itemize}
\item Score $1$: indicates that the tasks are visually exactly same
\item Score $2$: indicates that the tasks are visually similar
\item Score $3$: indicates that the tasks are visually slightly different
\item Score $4$: indicates that the tasks are visually very different
\end{itemize}





\subsection{Results on Visual Task Dissimilarity}

\begin{figure}[t!]
\centering

	\begin{subfigure}[b]{.194\textwidth}
	\centering
	{
	
		\includegraphics[width=1\textwidth]{fig/appendix_userstudy/histograms/histogram_H-all.pdf}
	
	
		\caption{\textnormal{H-}}
		 \label{fig:appendix.userstudy.q2.all}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.194\textwidth}
	\centering
	{
	
		\includegraphics[width=1\textwidth]{fig/appendix_userstudy/histograms/histogram_H2.pdf}
	
		\caption{\textsf{H2}\xspace}
		 \label{fig:appendix.userstudy.q2.h2}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.194\textwidth}
	\centering
	{
	
		\includegraphics[width=1\textwidth]{fig/appendix_userstudy/histograms/histogram_H4.pdf}
	
		\caption{\textsf{H3}\xspace}
		 \label{fig:appendix.userstudy.q2.h4}
	}
	\end{subfigure}

	\begin{subfigure}[b]{.194\textwidth}
	\centering
	{
	
		\includegraphics[width=1\textwidth]{fig/appendix_userstudy/histograms/histogram_H5.pdf}
	
		\caption{\textsf{H4}\xspace}
		 \label{fig:appendix.userstudy.q2.h5}
	}
	\end{subfigure}		

	\begin{subfigure}[b]{.194\textwidth}
	\centering
	{
	
		\includegraphics[width=1\textwidth]{fig/appendix_userstudy/histograms/histogram_H6.pdf}
	
		\caption{\textsf{H5}\xspace}
		 \label{fig:appendix.userstudy.q2.h6}
	}
	\end{subfigure}


	\caption{Distribution of participant responses on visual dissimilarity of tasks, rated on a 4-point Likert scale (1: exactly same, 2: almost same, 3: slightly different, 4: very different)


	}

	\label{fig:appendix.userstudy.q2}
\end{figure}




The distribution of participant responses (on a 4-point scale) on the visual dissimilarity of the presented tasks is shown in \figref{fig:appendix.userstudy.q2}; the aggregate statistics are provided in \figref{fig:userstudy}.

Comparing the dissimilarity of the generated tasks w.r.t. all the reference tasks \textnormal{H-}, we found that the performance of \ensuremath{\textsc{Same}}~was worst (mean dissimilarity = $1.07$) in comparison to \ensuremath{\textsc{MutTask}}~(mean = $2.17$), \ensuremath{\textsc{SynTask}}~(mean = $2.63$), and \ensuremath{\textsc{Tutor}}~(mean = $2.90$). The poor performance of \ensuremath{\textsc{Same}},~with the majority of scores being $1$, is expected. Furthermore, we also see in \figref{fig:appendix.userstudy.q2.all} that \ensuremath{\textsc{MutTask}}~has a greater percentage of lower scores of $1$ and $2$, and this is because the baseline directly mutates the task puzzle.
Comparing the performance of \ensuremath{\textsc{SynTask}}~to the baselines, we find that \ensuremath{\textsc{SynTask}}~performed significantly better than \ensuremath{\textsc{MutTask}}~($\chi^2 = 38.81, p < e^{-7}$). However, its performance was worse than that of \ensuremath{\textsc{Tutor}}~and this difference was significant~($\chi^2 = 12.20, p = 0.0053$).


When analyzing the differences in the performance of \ensuremath{\textsc{SynTask}}~w.r.t. \ensuremath{\textsc{Tutor}}, we find that \ensuremath{\textsc{Tutor}}~performs better primarily because of the following two reasons: (i) some of the tasks generated by \ensuremath{\textsc{Tutor}}~have additional distracting paths / noise, and (ii) for simpler tasks without conditionals like \textsf{H2}\xspace, more powerful code mutations were used. Next, we performed additional analysis by limiting to two complex tasks with nested conditionals, \textsf{H4}\xspace~and \textsf{H5}\xspace. On these two tasks, the mean scores of the methods \ensuremath{\textsc{MutTask}}, \ensuremath{\textsc{SynTask}}, and \ensuremath{\textsc{Tutor}}~were $1.97$,  $2.94$, and $3.03$ respectively. Furthermore, we find that \ensuremath{\textsc{SynTask}}'s performance continued to be significantly better than \ensuremath{\textsc{MutTask}}~($\chi^2 = 64.33, p < e^{-13}$). But, the difference in the performance of  \ensuremath{\textsc{SynTask}}~and~\ensuremath{\textsc{Tutor}}~was not statistically significant ($\chi^2 = 2.68, p = 0.44$). 

In general, the performance of our task synthesis algorithm can be further improved by allowing for more powerful code mutations in tasks without conditionals (such as \textsf{H2}\xspace) and by adding more variability in the output tasks by incorporating techniques discussed in Appendix ~\ref{appendix.sec.simulations.more_variability}.




















\section{Related Work}\label{appendix.relatedwork}
\paragraph{Related work. }
FIRST PARAGRAPH:
\begin{itemize}
\item Problem generation
\item Conceptual vs. procedural
\item Existing works on problem generation (other than coding) and differences
\end{itemize}

SECOND PARAGRAPH: Existing works on problem generation for coding and differences

THIRD PARAGRAPH: Existing works on visual content generation

FOURTH PARAGRAPH:
\begin{itemize}
\item Solution synthesizer, ITS hints, feedback
\item curriculum, teaching sequential tasks \cite{haug_teaching_2018}
\end{itemize}


\section{Misc}\label{appendix.misc}


\begin{figure}[t!]
	\centering

	\begin{minipage}{0.50\textwidth}
			\begin{subfigure}[b]{1.0\textwidth}
				\centering
				{
					\begin{boxcode2col}{1.2cm}{6.2cm}{0.75}{1.0}
						\textnormal{code } \text{\textcode{C}} &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} y \\
						\textnormal{rule } \textcode{y} &:= \textcode{s} | \textcode{g}  | \textcode{s};\textcode{g} \\
					
						\textnormal{rule } \textcode{s} \hspace{1mm} &:= \textcode{a} \text{ } | $\text{\textcode{s}};\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \textcode{\textsc{Else}} $\text{\textcode{s}}$\\
						& \quad | \textsf{while}\xspace(\textcode{b}) \textcode{\textsc{do}}  $\text{\textcode{s}}$  | \textsf{repeat}\xspace(\textcode{x}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \\
						\textnormal{rule } \textcode{g} &:= \textsf{repeatUntilGoal}\xspace(\textcode{goal}) \textcode{\textsc{do}} $\text{\textcode{s}}$\\
					
						\textnormal{action } \textcode{a} &:= \textsf{move}\xspace| \textsf{turnL}\xspace | \textcode{turnR}|  \textsf{put}\xspace | \textsf{pick}\xspace \\
					
						\textnormal{bool } \textcode{b} &:= \textcode{pathA} | \textcode{noPathA} | \textcode{pathL} | \textcode{noPathL} \\
						& \quad | \textcode{pathR} | \textcode{noPathR}  | \textcode{marker}  | \textcode{noMarker} \\
					
						\textnormal{iter } \textcode{x} &:= $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$\\
					
					\end{boxcode2col}
					\vspace{-3mm}
					\caption{Code DSL}
					\vspace{0.5mm}
					\label{fig:mutation.1}
				}
			\end{subfigure}
		\\
	
			\begin{subfigure}[b]{1.0\textwidth}
			\centering
			{
				\begin{boxcode}{9.0cm}{0.75}{1.0}
					\textbf{Input}: code \text{\textcode{C}}, sketch \textcode{Q} $\leftarrow$ $\ensuremath{\Omega}(\text{\textcode{C}})$, parameters $\ensuremath{\omega}(.| \text{\textcode{C}})$, $\delta_\text{thresh}$, $\delta_{r}$
					\\
					Note: \textoverline{\textcode{A}}~is a sequence of actions: $\text{\textcode{A}}_{1}$, \ldots $\text{\textcode{A}}_{N}$
					\begin{enumerate
						\item[(\ensuremath{\Delta_{0}})] Constraint on generated code size based on $\text{\textcode{C}}_{\textnormal{size}} \pm \delta_\text{thresh}$ 
						
						\item[(\ensuremath{\Delta_{1}})] For each $\text{\textoverline{\textcode{A}}} \in \text{\textcode{Q}}$, constraints ensuring minimality of \textoverline{\textcode{A}} 
						
						\item[(\ensuremath{\Delta_{2}})] Constraints induced on \textoverline{\textcode{A}}~nested inside conditional \textcode{B}
						
						\item[(\ensuremath{\Delta_{3}})] Constraints induced by repeat: \{\text{\textoverline{\textcode{A}}}\textsubscript{before};  \textsf{repeat}\xspace\{\textoverline{\textcode{A}}\} \text{\textoverline{\textcode{A}}}\textsubscript{after}\}
						\begin{enumerate}[\leftmargin=0em]
							\item[i.] \textoverline{\textcode{A}}~is not a suffix of \textoverline{\textcode{A}}\textsubscript{before}
							\item[ii.] \textoverline{\textcode{A}}~is not a prefix of \textoverline{\textcode{A}}\textsubscript{after}
						\end{enumerate}
						
						\item[(\ensuremath{\Delta_{4}})]  For each \textcode{X}~$ \in \text{\textcode{Q}}: |\text{\textcode{X}} - \ensuremath{\omega}(\text{\textcode{X}}| \text{\textcode{C}})| \leq \delta_{r}$
						
						\item[(\ensuremath{\Delta_{5}})]  For each \textcode{B}~$\in \text{\textcode{Q}}:$
						
						\begin{enumerate}[\leftmargin=0em]
							\item[i.] \ensuremath{\omega}(\text{\textcode{B}}| \text{\textcode{C}})
							$\in$ \{ \textcode{pathA}, \textcode{noPathA} \}
							$\Rightarrow$ \textcode{B} $\in$ \{ \textcode{pathA},\textcode{noPathA} \}
							
							\item[ii.] \ensuremath{\omega}(\text{\textcode{B}}| \text{\textcode{C}}) $\in$ \{ \textcode{pathL}, \textcode{noPathL} 
							\text{\textcode{pathR} }, \textcode{noPathR} \} 
							\item[] 
							$\Rightarrow$ \textcode{B} $\in$ \{ \textcode{pathL}, \textcode{noPathL}, \textcode{pathR}, \textcode{noPathR} \}
							
							\item[iii.] \ensuremath{\omega}(\text{\textcode{B}}| \text{\textcode{C}}) $\in$ \{\textcode{marker}, \textcode{noMarker}\} 
							\item[] $\Rightarrow$ \textcode{B} $\in$ \{ \textcode{marker},\textcode{noMarker}\}
							
						\end{enumerate}
						
						\item[(\ensuremath{\Delta_{6}})] $\text{For each }\text{\textoverline{\textcode{A}}} \in \text{\textcode{Q}}$, \ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}, $\ensuremath{\omega}(\textoverline{\textcode{A}}| \text{\textcode{C}})$). 
						\item[] \quad Only one block has actions added to them at a time.
						
						\vspace{-0.8em}
					\end{enumerate}
				\end{boxcode}
				\vspace{5mm}
				\caption{Sketch Constraint Types}
				\label{fig:mutation.3}
			}
		\end{subfigure}

	\end{minipage}
	\hspace{0.5em}

	\begin{minipage}{0.40\textwidth}
	\begin{subfigure}[b]{1.0\textwidth}
					\centering
					{
						\begin{boxcode2col}{1.2cm}{6.2cm}{0.75}{1.0}
							\textnormal{sketch } \textcode{Q}  &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} $\text{\textcode{Y}}$ \\
						
						\textnormal{rule } \textcode{Y} & := \textcode{S} | \textcode{G} | \textcode{S}; \textcode{G} \\
						
							\textnormal{rule } \textcode{S} &:= \ensuremath{\Lambda} | \textcode{S};\textcode{S} |
							\textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$
							\\
							& \quad | \textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \textcode{\textsc{Else}}
							$\text{\textcode{S}}$ \\
						& \quad | \textsf{while}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$  | \textsf{repeat}\xspace(\textcode{X}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
					
							\textnormal{rule } \textcode{G} & := \textsf{repeatUntilGoal}\xspace(\textcode{goal}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
					
							\textnormal{rule }\ensuremath{\Lambda} &:= $\phi$ |   \textcode{A} | \textcode{A}; \ensuremath{\Lambda}\\
						
						\end{boxcode2col}
						\vspace{-3mm}
						\caption{Sketch DSL}
					
						\label{fig:mutation.2}
					}
		\end{subfigure}    	

	\\
	\begin{subfigure}[b]{0.52\textwidth}
		\centering
		{
		
			\begin{boxcode}{3.8cm}{0.60}{0.65}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathLeft}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
			\vspace{-1.5mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{Solution code \text{\textcode{C}}\textsuperscript{in}}
			\label{fig:mutation.4}
		}
	\end{subfigure}
	\begin{subfigure}[b]{.40\textwidth}
		\centering
		{
			
			\begin{boxcode}{3.8cm}{0.65}{0.45}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				{\small
				\quad
				$\text{\textcode{A}}^{1}_{1}$, $\text{\textcode{A}}^{2}_{1}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{1})}
				}
				\\
				\quad
				\textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				{\small
				\quad \quad  
				$\text{\textcode{A}}^{1}_{2}$, $\text{\textcode{A}}^{2}_{2}$, $\text{\textcode{A}}^{3}_{2}$, 
				$\text{\textcode{A}}^{4}_{2}$, 
				$\text{\textcode{A}}^{5}_{2}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{2})}
				}
				\\
				
				\quad \quad \textsf{If}\xspace\textcode{(}$\text{\textcode{B}}_{1}$\textcode{)\{}\\
				{\small
					\quad \quad  \quad
					$\text{\textcode{A}}^{1}_{3}$, $\text{\textcode{A}}^{2}_{3}$, $\text{\textcode{A}}^{3}_{3}$, 
					$\text{\textcode{A}}^{4}_{3}$, 
					$\text{\textcode{A}}^{5}_{3}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{2})}
				}
				\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\vspace{-1.5mm}
			\end{boxcode}
			\vspace{-3mm}
			\caption{Sketch \textcode{Q}\textsuperscript{in}}
			\label{fig:mutation.5}
		}
	\end{subfigure}
	\\
	\begin{subfigure}[b]{1.0\textwidth}
		\centering
		{
			\begin{boxcode}{8.2cm}{0.75}{1.0}
				\textbf{Input}: \text{\textcode{C}}\textsuperscript{in}, $\text{\textcode{Q}}^\text{in}$, \ensuremath{\omega}($.| \text{\text{\textcode{C}}}^\text{in}$) = ($\phi$ , $\text{\textsf{move}\xspace}$,  $\text{\textsf{turnL}\xspace}$, \textcode{pathL}), \\
				\qquad \quad $\delta_\text{thresh} = 2$
				\begin{enumerate}
					\item[(\ensuremath{\Delta_1})] $\text{\textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$ is minimal
					
					\item[(\ensuremath{\Delta_2})] $\text{\textoverline{\textcode{A}}}_{3}$ in \textnormal{bool } $\text{\textcode{B}}_{1} = \text{\textcode{pathL}}$
					\begin{itemize}
						\item[] $\exists \text{\textcode{A}}_{3i} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{35}\}$ s.t ($\text{\textcode{A}}_{3i} = $ \textsf{turnL}\xspace
						
						\item[] $\land \text{ } \forall \text{\textcode{A}}_{3j} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{3i} \}$ $\text{\textcode{A}}_{3j}$ $\notin$ \{\textsf{move}\xspace, \textcode{turnR} \})
					\end{itemize}
					
					\item[(\ensuremath{\Delta_2})] $\text{\textoverline{\textcode{A}}}_{3}$ in \textnormal{bool } $\text{\textcode{B}}_{1} = \text{\textcode{pathR}}$
					
					\begin{itemize}
						\item[]$\exists \text{\textcode{A}}_{3i} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{35}\}$ s.t ($\text{\textcode{A}}_{3i} = $ \textcode{turnR}
						\item[] $\land \text{ } \forall \text{\textcode{A}}_{3j} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{3i} \}$ $\text{\textcode{A}}_{3j} \notin $ \{\textsf{move}\xspace, \textsf{turnL}\xspace \})
					\end{itemize}
					
					\item[(\ensuremath{\Delta_5})] $\text{\textcode{B}}_{1}$ = \textcode{pathL} $\lor$ $\text{\textcode{B}}_{1}$ = \textcode{pathR}
					
					\item[(\ensuremath{\Delta_6})] $\ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}_{1}, \ensuremath{\omega}(\textoverline{\textcode{A}}_{1}| \text{\textcode{C}}^\text{in}))$, 
					$\ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}_{2}, 
					\ensuremath{\omega}(\textoverline{\textcode{A}}_{2}| \text{\textcode{C}}^\text{in}))$, 
					\item []  \qquad $\ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}_{3}, \ensuremath{\omega}(\textoverline{\textcode{A}}_{3}| \text{\textcode{C}}^\text{in}))$
					\item[]
					\quad \quad Only one of $\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}$ have actions added to them.
					
					\vspace{-2mm}
				\end{enumerate}
				
			\end{boxcode}
			\vspace{-3mm}
			\caption{Sketch \textcode{Q}-Constraints}
			\label{fig:mutation.6}
		}
	\end{subfigure}	
	\end{minipage}

	\caption{Illustration of Program Mutation}
	\label{fig:mutation}
\end{figure}


\clearpage



\begin{figure}[t!]
\centering

\begin{minipage}{0.48\textwidth}
    \begin{minipage}{1.0\textwidth}
    \hspace{-4em}
	\begin{subfigure}[b]{1.0\textwidth}
	\centering
	{
	    \begin{boxcode2col}{1.2cm}{6.2cm}{0.75}{1.0}
		      \textnormal{code } \text{\textcode{C}} &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} y \\
		      \textnormal{rule } \textcode{y} &:= \textcode{s} | \textcode{g}  | \textcode{s};\textcode{g} \\
		     
		      \textnormal{rule } \textcode{s} \hspace{1mm} &:= \textcode{a} \text{ } | $\text{\textcode{s}};\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ | \textsf{If}\xspace(\textcode{b}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \textcode{\textsc{Else}} $\text{\textcode{s}}$\\
		      & \quad | \textsf{while}\xspace(\textcode{b}) \textcode{\textsc{do}}  $\text{\textcode{s}}$  | \textsf{repeat}\xspace(\textcode{x}) \textcode{\textsc{do}} $\text{\textcode{s}}$ \\
		      \textnormal{rule } \textcode{g} &:= \textsf{repeatUntilGoal}\xspace(\textcode{goal}) \textcode{\textsc{do}} $\text{\textcode{s}}$\\
		     
		      \textnormal{action } \textcode{a} &:= \textsf{move}\xspace| \textsf{turnL}\xspace | \textcode{turnR}|  \textsf{put}\xspace | \textsf{pick}\xspace \\
		     
		      \textnormal{bool } \textcode{b} &:= \textcode{pathA} | \textcode{noPathA} | \textcode{pathL} | \textcode{noPathL} \\
		      & \quad | \textcode{pathR} | \textcode{noPathR}  | \textcode{marker}  | \textcode{noMarker} \\
            
		      \textnormal{iter } \textcode{x} &:= $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$\\
		     
		\end{boxcode2col}
		\vspace{-3mm}
		\caption{Code DSL}
		\vspace{0.5mm}
		\label{fig:mutation.1}
    }
    \end{subfigure}
    \end{minipage}
    \\

	\begin{minipage}{1.0\textwidth}
	\hspace{-4em}
	\begin{subfigure}[b]{1.0\textwidth}
	\centering
	{
	    \begin{boxcode2col}{1.2cm}{6.2cm}{0.75}{1.0}
		      \textnormal{sketch } \textcode{Q}  &:= \textcode{def }\textcode{\textsc{Run}}() \textcode{\textsc{do}} $\text{\textcode{Y}}$ \\
		     
		      \textnormal{rule } \textcode{Y} & := \textcode{S} | \textcode{G} | \textcode{S}; \textcode{G} \\
		     
		      \textnormal{rule } \textcode{S} &:= \ensuremath{\Lambda} | \textcode{S};\textcode{S} |
		     \textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$
		     \\
		     & \quad | \textsf{If}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \textcode{\textsc{Else}}
		       $\text{\textcode{S}}$ \\
		       & \quad | \textsf{while}\xspace(\textcode{B}) \textcode{\textsc{do}} $\text{\textcode{S}}$  | \textsf{repeat}\xspace(\textcode{X}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
		      
		    \textnormal{rule } \textcode{G} & := \textsf{repeatUntilGoal}\xspace(\textcode{goal}) \textcode{\textsc{do}} $\text{\textcode{S}}$ \\
		   
		     \textnormal{rule }\ensuremath{\Lambda} &:= $\phi$ |   \textcode{A} | \textcode{A}; \ensuremath{\Lambda}\\
		     
		\end{boxcode2col}
		\vspace{-3mm}
		\caption{Sketch DSL}
		\vspace{0.5mm}
		\label{fig:mutation.2}
    }
    \end{subfigure}    
    \end{minipage}
\end{minipage}

	\hspace{-5em}
	\begin{minipage}{0.48\textwidth}
	\begin{subfigure}[b]{1.0\textwidth}
	\centering
	{
		 \begin{boxcode}{9.0cm}{0.75}{1.0}
		 \textbf{Input}: code \text{\textcode{C}}, sketch \textcode{Q} $\leftarrow$ $\ensuremath{\Omega}(\text{\textcode{C}})$, parameters $\ensuremath{\omega}(.| \text{\textcode{C}})$, $\delta_\text{thresh}$, $\delta_{r}$
		 \\
		 Note: \textoverline{\textcode{A}}~is a sequence of actions: $\text{\textcode{A}}_{1}$, \ldots $\text{\textcode{A}}_{N}$
    		 \begin{enumerate
    		     \item[(\ensuremath{\Delta_{0}})] Constraint on generated code size based on $\text{\textcode{C}}_{\textnormal{size}} \pm \delta_\text{thresh}$ 
    		     
    		     \item[(\ensuremath{\Delta_{1}})] For each $\text{\textoverline{\textcode{A}}} \in \text{\textcode{Q}}$, constraints ensuring minimality of \textoverline{\textcode{A}} 
    		     
    		     \item[(\ensuremath{\Delta_{2}})] Constraints induced on \textoverline{\textcode{A}}~nested inside conditional \textcode{B}
    		     
    		     \item[(\ensuremath{\Delta_{3}})] Constraints induced by repeat: \{\text{\textoverline{\textcode{A}}}\textsubscript{before};  \textsf{repeat}\xspace\{\textoverline{\textcode{A}}\} \text{\textoverline{\textcode{A}}}\textsubscript{after}\}
    		        \begin{enumerate}[\leftmargin=0em]
    		            \item[i.] \textoverline{\textcode{A}}~is not a suffix of \textoverline{\textcode{A}}\textsubscript{before}
    		            \item[ii.] \textoverline{\textcode{A}}~is not a prefix of \textoverline{\textcode{A}}\textsubscript{after}
    		        \end{enumerate}
    		        
    		 \item[(\ensuremath{\Delta_{4}})]  For each \textcode{X}~$ \in \text{\textcode{Q}}: |\text{\textcode{X}} - \ensuremath{\omega}(\text{\textcode{X}}| \text{\textcode{C}})| \leq \delta_{r}$
    		
    		 \item[(\ensuremath{\Delta_{5}})]  For each \textcode{B}~$\in \text{\textcode{Q}}:$
    		 
    		 \begin{enumerate}[\leftmargin=0em]
    		     \item[i.] \ensuremath{\omega}(\text{\textcode{B}}| \text{\textcode{C}})
		         $\in$ \{ \textcode{pathA}, \textcode{noPathA} \}
		         $\Rightarrow$ \textcode{B} $\in$ \{ \textcode{pathA},\textcode{noPathA} \}
		        
		         \item[ii.] \ensuremath{\omega}(\text{\textcode{B}}| \text{\textcode{C}}) $\in$ \{ \textcode{pathL}, \textcode{noPathL} 
		 \text{\textcode{pathR} }, \textcode{noPathR} \} 
		\item[] 
		 $\Rightarrow$ \textcode{B} $\in$ \{ \textcode{pathL}, \textcode{noPathL}, \textcode{pathR}, \textcode{noPathR} \}
		 
		  \item[iii.] \ensuremath{\omega}(\text{\textcode{B}}| \text{\textcode{C}}) $\in$ \{\textcode{marker}, \textcode{noMarker}\} 
		  \item[] $\Rightarrow$ \textcode{B} $\in$ \{ \textcode{marker},\textcode{noMarker}\}
		 
		 \end{enumerate}
		 
		 \item[(\ensuremath{\Delta_{6}})] $\text{For each }\text{\textoverline{\textcode{A}}} \in \text{\textcode{Q}}$, \ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}, $\ensuremath{\omega}(\textoverline{\textcode{A}}| \text{\textcode{C}})$). 
		 \item[] \quad Only one block has actions added to them at a time.

		  \vspace{-0.8em}
    \end{enumerate}
		\end{boxcode}
		\vspace{-3mm}
		\caption{Sketch Constraint Types}
		\label{fig:mutation.3}
	}
    \end{subfigure}
    \end{minipage}

		\begin{subfigure}[b]{.22\textwidth}
		\centering
		{
		
			\begin{boxcode}{3.8cm}{0.75}{0.7}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				\quad \textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				\quad \quad \textsf{move}\xspace\\
				\quad \quad \textsf{If}\xspace\textcode{(}\textcode{pathLeft}\textcode{)\{}\\
				\quad \quad \quad \textcode{turnLeft}\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
				\\
			\end{boxcode}
			\vspace{-2mm}
			\caption{Solution code \text{\textcode{C}}\textsuperscript{in}}
			\label{fig:mutation.4}
		}
	\end{subfigure}
\begin{subfigure}[b]{.22\textwidth}
		\centering
		{
			
			\begin{boxcode}{3.8cm}{0.72}{0.65}
				\textcode{def }\textcode{\textsc{Run}}\textcode{()\{}\\
				{\small
					\quad
					$\text{\textcode{A}}^{1}_{1}$, $\text{\textcode{A}}^{2}_{1}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{1})}
				}
				\\
				\quad
				\textsf{repeatUntilGoal}\xspace\textcode{(}\textcode{goal}\textcode{)\{}\\
				{\small
					\quad \quad  
					$\text{\textcode{A}}^{1}_{2}$, $\text{\textcode{A}}^{2}_{2}$, $\text{\textcode{A}}^{3}_{2}$, 
					$\text{\textcode{A}}^{4}_{2}$, 
					$\text{\textcode{A}}^{5}_{2}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{2})}
				}
				\\
				
				\quad \quad \textsf{If}\xspace\textcode{(}$\text{\textcode{B}}_{1}$\textcode{)\{}\\
				{\small
					\quad \quad  \quad
					$\text{\textcode{A}}^{1}_{3}$, $\text{\textcode{A}}^{2}_{3}$, $\text{\textcode{A}}^{3}_{3}$, 
					$\text{\textcode{A}}^{4}_{3}$, 
					$\text{\textcode{A}}^{5}_{3}$ \textcolor{blue}{(\textcolor{blue}{\textoverline{\textcode{A}}}\textsubscript{2})}
				}
				\\
				\quad \quad \textcode{\}}\\
				\quad \textcode{\}}\\
				\textcode{\}}
				\\
			\end{boxcode}
			\vspace{-2mm}
			\caption{Sketch \textcode{Q}\textsuperscript{in}}
			\label{fig:mutation.5}
		}
	\end{subfigure}
   
   
   
 
	\begin{subfigure}[b]{0.50\textwidth}
	\centering
    {
    \begin{boxcode}{8.8cm}{0.75}{1.0}
    \textbf{Input}: \text{\textcode{C}}\textsuperscript{in}, $\text{\textcode{Q}}^\text{in}$, \ensuremath{\omega}($.| \text{\text{\textcode{C}}}^\text{in}$) = ($\phi$ , $\text{\textsf{move}\xspace}$,  $\text{\textsf{turnL}\xspace}$, \textcode{pathL}), \\
    \qquad \quad $\delta_\text{thresh} = 2$
        \begin{enumerate}
            \item[(\ensuremath{\Delta_1})] $\text{\textoverline{\textcode{A}}}_{1}$, $\textoverline{\textcode{A}}_{2}$, $\textoverline{\textcode{A}}_{3}$ is minimal
            
            \item[(\ensuremath{\Delta_2})] $\text{\textoverline{\textcode{A}}}_{3}$ in \textnormal{bool } $\text{\textcode{B}}_{1} = \text{\textcode{pathL}}$
            \begin{itemize}
             \item[] $\exists \text{\textcode{A}}_{3i} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{35}\}$ s.t ($\text{\textcode{A}}_{3i} = $ \textsf{turnL}\xspace
             
             \item[] $\land \text{ } \forall \text{\textcode{A}}_{3j} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{3i} \}$ $\text{\textcode{A}}_{3j}$ $\notin$ \{\textsf{move}\xspace, \textcode{turnR} \})
            \end{itemize}
            
            \item[(\ensuremath{\Delta_2})] $\text{\textoverline{\textcode{A}}}_{3}$ in \textnormal{bool } $\text{\textcode{B}}_{1} = \text{\textcode{pathR}}$
            
            \begin{itemize}
                \item[]$\exists \text{\textcode{A}}_{3i} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{35}\}$ s.t ($\text{\textcode{A}}_{3i} = $ \textcode{turnR}
                \item[] $\land \text{ } \forall \text{\textcode{A}}_{3j} \in \{ \text{\textcode{A}}_{31}, \ldots , \text{\textcode{A}}_{3i} \}$ $\text{\textcode{A}}_{3j} \notin $ \{\textsf{move}\xspace, \textsf{turnL}\xspace \})
            \end{itemize}
        
        \item[(\ensuremath{\Delta_5})] $\text{\textcode{B}}_{1}$ = \textcode{pathL} $\lor$ $\text{\textcode{B}}_{1}$ = \textcode{pathR}
        
        \item[(\ensuremath{\Delta_6})] $\ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}_{1}, \ensuremath{\omega}(\textoverline{\textcode{A}}_{1}| \text{\textcode{C}}^\text{in}))$, 
        $\ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}_{2}, 
        \ensuremath{\omega}(\textoverline{\textcode{A}}_{2}| \text{\textcode{C}}^\text{in}))$, 
        \item []  \qquad $\ensuremath{\textsc{ActionEdits}}(\textoverline{\textcode{A}}_{3}, \ensuremath{\omega}(\textoverline{\textcode{A}}_{3}| \text{\textcode{C}}^\text{in}))$
        \item[]
        \quad \quad Only one of $\textoverline{\textcode{A}}_{1}, \textoverline{\textcode{A}}_{2}, \textoverline{\textcode{A}}_{3}$ have actions added to them.
        
         \vspace{-2mm}
        \end{enumerate}
   
	\end{boxcode}
		\vspace{-3mm}
		\caption{Sketch \textcode{Q}-Constraints}
		\label{fig:mutation.6}
	}
	\end{subfigure}
   
	    
        
	    
	   
	   
	
    

	\caption{Illustration of Program Mutation}
	\label{fig:mutation}
\end{figure}

\section{Related Work}\label{sec.relatedwork}
\paragraph{Related work. }
FIRST PARAGRAPH:
\begin{itemize}
\item Problem generation
\item Conceptual vs. procedural
\item Existing works on problem generation (other than coding) and differences
\end{itemize}

SECOND PARAGRAPH: Existing works on problem generation for coding and differences

THIRD PARAGRAPH: Existing works on visual content generation

FOURTH PARAGRAPH:
\begin{itemize}
\item Solution synthesizer, ITS hints, feedback
\item curriculum, teaching sequential tasks \cite{haug_teaching_2018}
\end{itemize}

\todo{Finish on page 2}


