## 5.261. min_width_valley

Origin
Constraint

$\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}\left(\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Synonym

$\mathrm{𝚖𝚒𝚗}_\mathrm{𝚋𝚊𝚜𝚎}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$.

Arguments
 $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}\ge 0$ $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-2$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

Given a sequence $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ constraint $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}$ to be fixed to the width of the smallest valley, or to 0 if no valley exists.

Example
 $\left(5,〈3,3,5,5,4,2,2,3,4,6,6,5,5,5,5,5,5,6〉\right)$ $\left(0,〈3,8,8,5,0,0〉\right)$ $\left(4,〈9,8,8,0,0,2〉\right)$

The first $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint holds since the sequence $335542234665555556$ contains two valleys of respective width 5 and 6 (see Figure 5.261.1) and since its argument $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}$ is fixed to the smallest value 5.

##### Figure 5.261.1. Illustration of the first example of the Example slot: a sequence of eighteen variables ${V}_{1}$, ${V}_{2}$, ${V}_{3}$, ${V}_{4}$, ${V}_{5}$, ${V}_{6}$, ${V}_{7}$, ${V}_{8}$, ${V}_{9}$, ${V}_{10}$, ${V}_{11}$, ${V}_{12}$, ${V}_{13}$, ${V}_{14}$, ${V}_{15}$, ${V}_{16}$, ${V}_{17}$, ${V}_{18}$ respectively fixed to values 3, 3, 5, 5, 4, 2, 2, 3, 4, 6, 6, 5, 5, 5, 5, 5, 5, 6 and its two valleys of width 5 and 6. Typical
 $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}>1$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>2$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

• One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Arg. properties

Functional dependency: $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$: domains $0..n$  Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

095029517921108869498439791
1-14230320556637117439826327058
2--1002100284204249289363060
3---679170242687223413256
4----44801304522345982
5-----29154968946
6------188628

Solution count for $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$: domains $0..n$  Keywords
Automaton

Figure 5.261.2 depicts the automaton associated with the $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint. To each pair of consecutive variables $\left({\mathrm{𝚅𝙰𝚁}}_{i},{\mathrm{𝚅𝙰𝚁}}_{i+1}\right)$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a signature variable ${S}_{i}$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_{i}$, ${\mathrm{𝚅𝙰𝚁}}_{i+1}$ and ${S}_{i}$: $\left({\mathrm{𝚅𝙰𝚁}}_{i}<{\mathrm{𝚅𝙰𝚁}}_{i+1}⇔{S}_{i}=0\right)\wedge \left({\mathrm{𝚅𝙰𝚁}}_{i}={\mathrm{𝚅𝙰𝚁}}_{i+1}⇔{S}_{i}=1\right)\wedge \left({\mathrm{𝚅𝙰𝚁}}_{i}>{\mathrm{𝚅𝙰𝚁}}_{i+1}⇔{S}_{i}=2\right)$.

##### Figure 5.261.2. Automaton of the $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint: the start of the first potential valley is discovered while triggering the transition from $s$ to $j$, the bottom of a valley is discovered while triggering the transition from $j$ to $k$, the end of a valley and the start of the next potential valley are discovered while triggering the transition from $k$ to $j$; the counters $W$, $C$ and $F$ respectively stand for min_width, current and first. ##### Figure 5.261.3. Glue matrix associated with the automaton of the $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint, where $n$ stands for $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$
 $s$ $\left({\left\{<|=\right\}}^{*}\right)$ $j$ $\left(>{\left\{>|=\right\}}^{*}\right)$ $k$ $\left(<{\left\{<|=\right\}}^{*}\right)$ $s$ $\left({\left\{<|=\right\}}^{*}\right)$ 0 $\stackrel{←}{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}$ $\stackrel{←}{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}$ $j$ $\left(>{\left\{>|=\right\}}^{*}\right)$ $\stackrel{\to }{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}$ $min\left(\begin{array}{c}\stackrel{\to }{W},\\ n-\stackrel{\to }{F}-\stackrel{←}{F},\\ \stackrel{←}{W}\end{array}\right)$ $min\left(\begin{array}{c}\stackrel{\to }{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}},\\ n-\stackrel{\to }{F}-\stackrel{←}{F},\\ \stackrel{←}{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}\end{array}\right)$ $k$ $\left(<{\left\{<|=\right\}}^{*}\right)$ $\stackrel{\to }{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}$ $min\left(\begin{array}{c}\stackrel{\to }{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}},\\ n-\stackrel{\to }{F}-\stackrel{←}{F},\\ \stackrel{←}{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}\end{array}\right)$ $min\left(\begin{array}{c}\stackrel{\to }{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}},\\ \stackrel{←}{\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}}\end{array}\right)$ ##### Figure 5.261.4. Illustrating the use of the state pair $\left(j,j\right)$ of the glue matrix for linking $\mathrm{𝙼𝙸𝙽}_\mathrm{𝚆𝙸𝙳𝚃𝙷}$ with the counters variables obtained after reading the prefix $6,4,3,1$ and corresponding suffix $1,2,5,6$ of the sequence $6,4,3,1,2,5,6$; note that the suffix $1,2,5,6$ (in pink) is proceed in reverse order; the left (resp. right) table shows the initialisation (for $i=0$) and the evolution (for $i>0$) of the state of the automaton and its counters $W$, $C$ and $F$ upon reading the prefix $6,4,3,1$ (resp. the reverse suffix $6,5,2,1$). ##### Figure 5.261.5. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚠𝚒𝚍𝚝𝚑}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint 