#include

#include

#include

#include

#include

#include "farm.hpp$"$

$//***$ For you to implement

std::vector getNeighbours$($Inventory p$)\{$

std::vector neighbours;

$//1.$ Do nothing

Inventory neighbour $=\{$p$.$hay $+1,$ p$.$eggs $+$ p$.$chickens, p$.$chickens$\}$;

if $($neighbour$.$hay $>=0$ && neighbour.eggs $>=0)\{$

neighbours.push$\_$back$($neighbour$)$;

$\}$

$//2.$ Trade $2$ bales of hay for $1$ chicken.

if $($p$.$hay $>=2)\{$

neighbour $=\{$p$.$hay $-2,$ p$.$eggs, p$.$chickens $+1\}$;

if $($neighbour$.$hay $>=0$ && neighbour.eggs $>=0)\{$

neighbours.push$\_$back$($neighbour$)$;

$\}$

$\}$

$//3.$ Trade $1$ bale of hay for $2$ eggs.

if $($p$.$hay $>=1)\{$

neighbour $=\{$p$.$hay $-1,$ p$.$eggs $+2,$ p$.$chickens$\}$;

if $($neighbour$.$hay $>=0$ && neighbour.eggs $>=0)\{$

neighbours.push$\_$back$($neighbour$)$;

$\}$

$\}$

$//4.$ Trade $3$ eggs for $1$ chicken

if $($p$.$eggs $>=3)\{$

neighbour $=\{$p$.$hay, p$.$eggs $-3,$ p$.$chickens $+1\}$;

if $($neighbour$.$hay $>=0$ && neighbour.eggs $>=0)\{$

neighbours.push$\_$back$($neighbour$)$;

$\}$

$\}$

$//$ Return either neighbour or neighbours based on what is better

return neighbours.size$()>0?$ neighbours : std::vector$\{$neighbour$\}$;

$\}$

int daysForEggs$($const Inventory& origin, int numberOfEggs$)\{$

std::queue $>$ inventoryQueue $\{\}$;

inventoryQueue.push$(\{$origin$,0\})$;

std::map prev $\{\}$;

std::set visited $\{$origin$\}$;

while $(!$inventoryQueue.empty$())\{$

auto $[$current$,$ dist$]=$ inventoryQueue.front$()$;

inventoryQueue.pop$()$;

if $($current$.$eggs $>=$ numberOfEggs$)\{$

return dist;

$\}$

std::vector neighbours $=$ getNeighbours$($current$)$;

for $($Inventory neighbour : neighbours$)\{$

if $(!$visited.contains$($neighbour$))\{$

prev$[$neighbour$]=$ current;

visited.insert$($neighbour$)$;

inventoryQueue.push$(\{$neighbour$,$ dist $+1\})$;

$\}$

$\}$

$\}$

return $-1$;

$\}$