Dopo i primi 2 episodi arriviamo al momento più importante di questa serie con l’episodio dedicato al linguaggio di programmazione C♯.
Per questo episodio abbiamo deciso di aggiornare la nostra macchina con Windows 7 a Windows 8.1 e l’IDE è stato aggiornato da Visual Studio™ 2015 a Visual Studio™ 2017 Professional. Con questo update guadagniamo il lusso di poter vedere i numeri di linea. Purtroppo Windows Update si lamenta del fatto che la CPU della macchina non è progettata per Windows 8.1, e quindi non possiamo fare alcuni importanti aggiornamenti di sicurezza. Per favore non pwnate la macchina.
Il problema di oggi è il seguente: H - Two SAT, facilmente riconducibile a Two SAT. E chi l’avrebbe mai detto.
Elenchiamo qui i vantaggi della programmazione in C♯:
- Essendo C♯ (Do Diesis Maggiore) la tonalità di Never Gonna Give You Up, l’ilarità è garantita.
- Sintassi concisa come in Java: ve ne accorgerete leggendo il codice.
- Complesso ecosistema di classi come
System.Actionper le lambda senza valori di ritorno eSystem.Funcper le lambda con valori di ritorno;System.Collections.Generic.QueueeSystem.Collections.Generic.Stackper collezioni FIFO e LIFO e le loro sintassi sono completamente differenti così non ci si può confondere:PushePopper la Stack eEnqueueeDequeueper la Queue - Il linguaggio di programmazione è relativamente veloce rispetto ai suoi fratelli F♯ e VB .Net, infatti non abbiamo dovuto impiegare ottimizzazioni pesanti, come invece è stato necessario in F♯ e VB .Net.
- Indentazione Allman imposta dall’IDE, che non ti lascia neanche mettere meno spazi di quelli che dice lui, fixando il tuo codice non conforme alle linee guida ogni qualvolta cambi riga.
- Ogni variabile di tipo classe (Quindi tutto) può essere null. Altri linguaggi optano per creare tipi come
OptionaloMaybe, non C♯, che con questo trick ne fa a meno. -
System.Collections.Generic.Listè unstd::vector. Per avere unstd::listusareSystem.Collections.Generic.LinkedList. - UpperCamelCase
public static void Main (System.String[] Args)
E a voi il tanto atteso codice:
namespace NeverGonnaGive2Sat
{
class NeverGonnaLetYouDown
{
static System.Int32 N, D;
static System.Int32[] X, Y;
static System.Collections.Generic.List<System.Int32>[] InAdj;
static System.Collections.Generic.List<System.Int32>[] OutAdj;
static System.Collections.Generic.List<System.Tuple<System.Int32, System.Int32>> Clauses = new System.Collections.Generic.List<System.Tuple<System.Int32, System.Int32>>();
static System.Int32[] Components;
private static void ReadInput()
{
System.String[] nd = System.Console.ReadLine().Split(' ');
N = System.Int32.Parse(nd[0]);
D = System.Int32.Parse(nd[1]);
X = new System.Int32[N];
Y = new System.Int32[N];
for (System.Int32 i = 0; i < N; i++)
{
System.String[] xy = System.Console.ReadLine().Split(' ');
X[i] = System.Int32.Parse(xy[0]);
Y[i] = System.Int32.Parse(xy[1]);
}
}
private static void CreateClauses()
{
for (System.Int32 i = 0; i < N; i++)
{
for (System.Int32 j = i + 1; j < N; j++)
{
if (System.Math.Abs(X[i] - X[j]) < D)
{
Clauses.Add(new System.Tuple<System.Int32, System.Int32>(2 * i + 1, 2 * j + 1));
}
if (System.Math.Abs(X[i] - Y[j]) < D)
{
Clauses.Add(new System.Tuple<System.Int32, System.Int32>(2 * i + 1, 2 * j));
}
if (System.Math.Abs(Y[i] - X[j]) < D)
{
Clauses.Add(new System.Tuple<System.Int32, System.Int32>(2 * i, 2 * j + 1));
}
if (System.Math.Abs(Y[i] - Y[j]) < D)
{
Clauses.Add(new System.Tuple<System.Int32, System.Int32>(2 * i, 2 * j));
}
}
}
}
private static void CreateGraph()
{
InAdj = new System.Collections.Generic.List<System.Int32>[2 * N];
OutAdj = new System.Collections.Generic.List<System.Int32>[2 * N];
for (System.Int32 i = 0; i < 2 * N; i++)
{
InAdj[i] = new System.Collections.Generic.List<System.Int32>();
OutAdj[i] = new System.Collections.Generic.List<System.Int32>();
}
foreach (System.Tuple<System.Int32, System.Int32> el in Clauses)
{
InAdj[el.Item1 ^ 1].Add(el.Item2);
InAdj[el.Item2 ^ 1].Add(el.Item1);
OutAdj[el.Item2].Add(el.Item1 ^ 1);
OutAdj[el.Item1].Add(el.Item2 ^ 1);
}
}
private static System.Collections.BitArray BuildSolution () {
for (System.Int32 i = 0; i < N; i++)
{
if (Components[2 * i] == Components[2 * i + 1])
{
return null;
}
}
System.Collections.BitArray Solution = new System.Collections.BitArray(N);
System.Collections.BitArray Used = new System.Collections.BitArray(N);
System.Collections.Generic.List<System.Int32>[] ComponentAdj = new System.Collections.Generic.List<System.Int32>[2 * N];
System.Collections.Generic.List<System.Int32>[] ComponentNodes = new System.Collections.Generic.List<System.Int32>[2 * N];
System.Int32[] Taken = new System.Int32[2 * N];
for (System.Int32 i = 0; i < 2 * N; i++)
{
ComponentAdj[i] = new System.Collections.Generic.List<System.Int32>();
ComponentNodes[i] = new System.Collections.Generic.List<System.Int32>();
}
for (System.Int32 i = 0; i < 2 * N; i++)
{
ComponentNodes[Components[i] - 1].Add(i);
}
for (System.Int32 i = 0; i < 2 * N; i++)
{
foreach (System.Int32 OtherNode in InAdj[i])
{
if (Components[i] != Components[OtherNode])
{
ComponentAdj[Components[i] - 1].Add(Components[OtherNode] - 1);
Taken[Components[OtherNode] - 1]++;
}
}
}
System.Collections.Generic.Queue<System.Int32> Q = new System.Collections.Generic.Queue<System.Int32>();
for (System.Int32 i = 0; i < 2 * N; i++)
{
if (Taken[i] == 0)
{
Q.Enqueue(i);
}
}
while (Q.Count != 0)
{
System.Int32 El = Q.Dequeue();
foreach (System.Int32 Node in ComponentNodes[El])
{
if (!Used[Node / 2])
{
Used[Node / 2] = true;
Solution[Node / 2] = Node % 2 == 0;
}
}
foreach (System.Int32 Neighbor in ComponentAdj[El])
{
if (--Taken[Neighbor] == 0)
{
Q.Enqueue(Neighbor);
}
}
}
return Solution;
}
private static void Kosaraju()
{
System.Collections.Generic.Stack<System.Int32> Stck = new System.Collections.Generic.Stack<System.Int32>();
System.Collections.BitArray bitset = new System.Collections.BitArray(2 * N);
Components = new System.Int32[2 * N];
System.Action<System.Int32> Visit = null;
Visit = (System.Int32 node) =>
{
if (bitset.Get(node))
{
return;
}
bitset.Set(node, true);
foreach (System.Int32 OtherNode in OutAdj[node])
{
Visit(OtherNode);
}
Stck.Push(node);
};
System.Action<System.Int32, System.Int32> Assign = null;
Assign = (System.Int32 node, System.Int32 root) =>
{
if (Components[node] != 0)
{
return;
}
Components[node] = root;
foreach (System.Int32 OtherNode in InAdj[node])
{
Assign(OtherNode, root);
}
};
for (System.Int32 i = 0; i < 2 * N; i++)
{
Visit(i);
}
while (Stck.Count != 0)
{
System.Int32 Element = Stck.Pop();
Assign(Element, Element + 1);
}
}
private static void PrintOutput(System.Collections.BitArray solution)
{
if (solution == null)
{
System.Console.WriteLine("No");
return;
}
System.Console.WriteLine("Yes");
for (System.Int32 i = 0; i < N; i++)
{
if (!solution[i])
{
System.Console.WriteLine(X[i]);
}
else
{
System.Console.WriteLine(Y[i]);
}
}
}
public static void Main(System.String[] Args)
{
ReadInput();
CreateClauses();
CreateGraph();
Kosaraju();
System.Collections.BitArray solution = BuildSolution();
PrintOutput(solution);
}
}
}