greedy_algorithm.tex

\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{geometry}
\geometry{margin=1in}

\title{Greedy Algorithm for Bridge Puzzle Solving}
\author{%
Visruth Thayyil Vijind - CB.SC.U4CSE24557\\
Lohit G - CB.SC.U4CSE24522\\
Srishanth P A- CB.SC.U4CSE24550\\
Sanjith S J - CB.SC.U4CSE24544
}
\date{\today}

\begin{document}

\maketitle

\section{Algorithm Design}

\subsection{Algorithm Overview}

The main solving algorithm operates in two distinct phases based on graph connectivity:

\begin{algorithm}
\caption{Greedy Bridge Solver Main Algorithm}
\begin{algorithmic}[1]
\Procedure{doNextMove}{}
    \State $prevMove \gets$ \Call{getPrevMove}{edgeSystem}
    \If{$prevMove \neq -1$ AND edge component exists}
        \State Add both endpoints (nodeA, nodeB) to priority queue
    \EndIf
    \State $visited \gets \emptyset$
    \State $islandIds \gets$ all islands
    \State $adjList \gets$ \Call{genAdjacencyList}{islandIds}
    \State $visitedCount \gets$ \Call{dfs}{adjList, islandIds[0], visited}
    \If{$visitedCount < |islandIds|$}
        \State \Call{doConMove}{adjList, visited} \Comment{Connection Phase}
    \Else
        \State \Call{solveAllConnections}{} \Comment{Satisfaction Phase}
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Connection Phase}

\begin{algorithm}
\caption{Connection Phase Algorithm}
\begin{algorithmic}[1]
\Procedure{doConMove}{adjList, visited}
    \State $currentBridgeCount \gets$ \Call{getBridgeCounts}{all islands}
    \While{priority queue is not empty}
        \State $(maxCapacity, currentId) \gets$ \Call{poll}{pq}
        \State Remove $currentId$ from queued set
        \State $currentConnections \gets$ size of adjList[$currentId$] or 0
        \State $availableNeighbors \gets$ size of neighborList[$currentId$]
        \If{$(availableNeighbors - currentConnections) < 1$}
            \State \textbf{continue} \Comment{Skip islands with no available connections}
        \EndIf
        \State \textbf{Priority 1}: Connect to isolated neighbors
        \For{each neighbor $n$ of $currentId$}
            \If{current bridge count of $n = 0$}
                \If{\Call{createEdge}{$currentId$, $n$} succeeds}
                    \State \Call{addToPQ}{$n$}
                    \State \Call{addToPQ}{$currentId$}
                    \State \Return \textbf{true}
                \EndIf
            \EndIf
        \EndFor
        \State \textbf{Priority 2}: Connect to connected neighbors
        \For{each neighbor $n$ of $currentId$}
            \If{neighbor's bridges $<$ required AND not in adjList[$currentId$]}
                \If{\Call{createEdge}{$currentId$, $n$} succeeds}
                    \State \Call{addToPQ}{$currentId$}
                    \State \Call{addToPQ}{$n$}
                    \State \Return \textbf{true}
                \EndIf
            \EndIf
        \EndFor
    \EndWhile
    \Return \textbf{false} \Comment{No moves found}
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Satisfaction Phase}

\begin{algorithm}
\caption{Satisfaction Phase Algorithm}
\begin{algorithmic}[1]
\Procedure{solveAllConnections}{}
    \If{islandIds is empty}
        \State \Return
    \EndIf
    \State $bridgeCount \gets$ \Call{getBridgeCounts}{islandIds}
    \State $pairCounts \gets$ \Call{currentEdgeCounts}{}
    \State $remaining \gets$ empty map
    \For{each island $i$}
        \State $current \gets$ bridgeCount[$i$] or 0
        \State $remaining[i] \gets$ max(0, required[$i$] $-$ $current$)
    \EndFor
    \State Sort islands by bridge capacity (descending)
    \For{each island $i$ in sorted order}
        \State $need \gets$ $remaining[i]$
        \If{$need \leq 0$}
            \State \textbf{continue}
        \EndIf
        \State Get neighbors of $i$
        \State Sort neighbors by remaining need (descending), then by ID (descending)
        \For{each neighbor $n$ in sorted order}
            \State $neighborNeed \gets$ $remaining[n]$
            \If{$neighborNeed \leq 0$}
                \State \textbf{continue}
            \EndIf
            \State $key \gets$ \Call{edgeKey}{$i$, $n$}
            \State $pairCount \gets$ $pairCounts[key]$ or 0
            \If{$pairCount \geq 2$}
                \State \textbf{continue} \Comment{Maximum bridges between pair reached}
            \EndIf
            \If{\Call{createEdge}{$i$, $n$} succeeds}
                \State $pairCounts[key] \gets$ $pairCount + 1$
                \State $remaining[i] \gets$ $need - 1$
                \State $remaining[n] \gets$ $neighborNeed - 1$
                \State \Return \Comment{Single move per call}
            \EndIf
        \EndFor
    \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Priority Queue Management}

\begin{algorithm}
\caption{Add Island to Priority Queue}
\begin{algorithmic}[1]
\Procedure{addToPQ}{islandId}
    \If{islandId not in queued set}
        \State $bridgeNo \gets$ island's required bridge count
        \State Insert $[bridgeNo, islandId]$ into priority queue
        \State Add islandId to queued set
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

\section{Complexity Analysis}

\subsection{Time Complexity}

\begin{itemize}
    \item \textbf{Island Neighbor Detection:} $O(N^2)$ for $N \times N$ grid
    \item \textbf{Edge Creation:} $O(E)$ where $E$ is number of existing edges (cross-detection)
    \item \textbf{DFS Connectivity Check:} $O(V + E)$ where $V$ is vertices, $E$ is edges
    \item \textbf{Connection Phase:} $O(V \log V + E)$ due to priority queue operations
    \item \textbf{Satisfaction Phase:} $O(V^2 \log V)$ in worst case (sorting and priority queue)
    \item \textbf{Path Obstruction Check:} $O(V)$ per edge creation
\end{itemize}


\end{document}