Rosetta Code

Solve the no connection puzzle: Difference between revisions

Page Discussion

Solve the no connection puzzle (view source)

Revision as of 06:24, 14 February 2024

6,615 bytes added ,  4 months ago
Add C# implementation
m (syntax highlighting fixup automation)
(Add C# implementation)
(3 intermediate revisions by 3 users not shown)
Line 1,126:
2 8 1 7
4 3</pre>
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Linq;
 
public class NoConnection
{
// adopted from Go
static int[][] links = new int[][] {
new int[] {2, 3, 4}, // A to C,D,E
new int[] {3, 4, 5}, // B to D,E,F
new int[] {2, 4}, // D to C, E
new int[] {5}, // E to F
new int[] {2, 3, 4}, // G to C,D,E
new int[] {3, 4, 5}, // H to D,E,F
};
 
static int[] pegs = new int[8];
 
public static void Main(string[] args)
{
List<int> vals = Enumerable.Range(1, 8).ToList();
Random rng = new Random();
 
do
{
vals = vals.OrderBy(a => rng.Next()).ToList();
for (int i = 0; i < pegs.Length; i++)
pegs[i] = vals[i];
 
} while (!Solved());
 
PrintResult();
}
 
static bool Solved()
{
for (int i = 0; i < links.Length; i++)
foreach (int peg in links[i])
if (Math.Abs(pegs[i] - peg) == 1)
return false;
return true;
}
 
static void PrintResult()
{
Console.WriteLine($" {pegs[0]} {pegs[1]}");
Console.WriteLine($"{pegs[2]} {pegs[3]} {pegs[4]} {pegs[5]}");
Console.WriteLine($" {pegs[6]} {pegs[7]}");
}
}
</syntaxhighlight>
{{out}}
<pre>
6 1
4 3 8 7
2 5
 
</pre>
 
=={{header|C++}}==
Line 1,473 ⟶ 1,535:
5 6
Tested 12094 positions and did 20782 swaps.</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
 
{ This item would normally be in a separate library. It is presented here for clarity}
 
{Permutator object steps through all permutation of array items}
{Zero-Based = True = 0..Permutions-1 False = 1..Permutaions}
{Permutation set on "Create(Size)" or by "Permutations" property}
{Permutation are contained in the array "Indices"}
 
type TPermutator = class(TObject)
private
FZeroBased: boolean;
FBase: integer;
FPermutations: integer;
procedure SetZeroBased(const Value: boolean);
procedure SetPermutations(const Value: integer);
protected
FMax: integer;
public
Indices: TIntegerDynArray;
constructor Create(Size: integer);
procedure Reset;
function Next: boolean;
property ZeroBased: boolean read FZeroBased write SetZeroBased;
property Permutations: integer read FPermutations write SetPermutations;
end;
 
 
 
procedure TPermutator.Reset;
var I: integer;
begin
FMax:=High(Indices);
for I:= 0 to High(Indices) do Indices[I]:= I+FBase;
end;
 
 
 
procedure TPermutator.SetPermutations(const Value: integer);
begin
if FPermutations<>Value then
begin
FPermutations := Value;
SetLength(Indices,Value);
Reset;
end;
end;
 
 
 
constructor TPermutator.Create(Size: integer);
begin
ZeroBased:=True;
Permutations:=Size;
Reset;
end;
 
 
function TPermutator.Next: boolean;
{Returns true when sequence completed}
var I,T: integer;
begin
while true do
begin
T:= Indices[0];
for I:=0 to FMax-1 do Indices[I]:= Indices[I+1];
Indices[FMax]:= T;
if T<>(FMax+FBase) then
begin
FMax:=High(Indices);
break;
end
else FMax:= FMax-1;
if FMax<0 then break;
end;
Result:=FMax<1;
if Result then Reset;
end;
 
 
 
procedure TPermutator.SetZeroBased(const Value: boolean);
begin
if FZeroBased<>Value then
begin
FZeroBased := Value;
if Value then FBase:=0
else FBase:=1;
Reset;
end;
end;
 
{------------------------------------------------------------------------------}
 
{Network structures}
{Puzzle node}
 
type TPuzNode = record
Name: string;
Value: integer;
end;
type PPuzNode = ^TPuzNode;
 
{Edges connecting nodes}
 
type TPuzEdge = record
N1,N2: ^TPuzNode;
end;
 
{All edges in puzzle}
 
var Edges: array [0..14] of TPuzEdge;
 
{All nodes in puzzle}
 
var A: TPuzNode = (Name: 'A'; Value: 1);
var B: TPuzNode = (Name: 'B'; Value: 2);
var C: TPuzNode = (Name: 'C'; Value: 3);
var D: TPuzNode = (Name: 'D'; Value: 4);
var E: TPuzNode = (Name: 'E'; Value: 5);
var F: TPuzNode = (Name: 'F'; Value: 6);
var G: TPuzNode = (Name: 'G'; Value: 7);
var H: TPuzNode = (Name: 'H'; Value: 8);
 
{Array of pointers to puzzle nodes }
 
var PuzNodes: array [0..7] of Pointer;
 
procedure BuildNetwork;
{Build puzzle net work}
begin
{Put pointers to nodes in array}
PuzNodes[0]:=@A;
PuzNodes[1]:=@B;
PuzNodes[2]:=@C;
PuzNodes[3]:=@D;
PuzNodes[4]:=@E;
PuzNodes[5]:=@F;
PuzNodes[6]:=@G;
PuzNodes[7]:=@H;
{Set up all edges}
Edges[0].N1:=@A; Edges[0].N2:=@C;
Edges[1].N1:=@A; Edges[1].N2:=@D;
Edges[2].N1:=@A; Edges[2].N2:=@E;
Edges[3].N1:=@B; Edges[3].N2:=@D;
Edges[4].N1:=@B; Edges[4].N2:=@E;
Edges[5].N1:=@B; Edges[5].N2:=@F;
Edges[6].N1:=@G; Edges[6].N2:=@C;
Edges[7].N1:=@G; Edges[7].N2:=@D;
Edges[8].N1:=@G; Edges[8].N2:=@E;
Edges[9].N1:=@H; Edges[9].N2:=@D;
Edges[10].N1:=@H; Edges[10].N2:=@E;
Edges[11].N1:=@H; Edges[11].N2:=@F;
Edges[12].N1:=@C; Edges[12].N2:=@D;
Edges[13].N1:=@D; Edges[13].N2:=@E;
Edges[14].N1:=@E; Edges[14].N2:=@F;
end;
 
 
 
function ValidPattern: boolean;
{Test if pattern of node values is valid}
{i.e., edges values are greater than 1}
var I: integer;
begin
Result:=False;
for I:=0 to High(Edges) do
if abs(Edges[I].N2.Value-Edges[I].N1.Value)<2 then exit;
Result:=True;
end;
 
 
function Permutate: boolean;
{Use permutator object to iterate through all combinations}
var PM: TPermutator;
var I: integer;
begin
{Create with 8 items}
PM:=TPermutator.Create(8);
try
{Set to make it 1..8}
PM.ZeroBased:=False;
Result:=True;
{Iterate through all permutation}
while not PM.Next do
begin
{Copy permutation into network}
for I:=0 to High(PM.Indices) do
PPuzNode(PuzNodes[I])^.Value:=PM.Indices[I];
{If permutation is valid exit}
if ValidPattern then exit;
end;
{No valid permutation found}
Result:=False;
finally PM.Free; end;
end;
 
{String to display game board}
 
var GameBoard: string =
' A B'+CRLF+
' /|\ /|\'+CRLF+
' / | X | \'+CRLF+
' / |/ \| \'+CRLF+
' C - D - E - F'+CRLF+
' \ |\ /| /'+CRLF+
' \ | X | /'+CRLF+
' \|/ \|/'+CRLF+
' G H'+CRLF;
 
 
procedure ShowPuzzle(Memo: TMemo);
{Display game board with correct answer inserted}
var I,Inx: integer;
var S: string;
var PN: TPuzNode;
begin
S:=GameBoard;
{Search for Letters A..H}
for I:=1 to Length(S) do
if S[I] in ['A'..'H'] then
begin
{Convert A..H to index}
Inx:=byte(S[I]) - $41;
{Get node A..H}
PN:=PPuzNode(PuzNodes[Inx])^;
{Store value in corresponding node}
S[I]:=char(PN.Value+$30);
end;
{Display board}
Memo.Lines.Add(S);
end;
 
 
procedure ConnectionPuzzle(Memo: TMemo);
{Solve connection puzzle}
var S: string;
var I: integer;
var PN: TPuzNode;
begin
BuildNetwork;
Permutate;
{Display result}
S:='';
for I:=0 to High(PuzNodes) do
begin
PN:=PPuzNode(PuzNodes[I])^;
S:=S+PN.Name+'='+IntToStr(PN.Value)+' ';
end;
Memo.Lines.Add(S);
{Show puzzle with values inserted}
ShowPuzzle(Memo);
end;
 
 
 
</syntaxhighlight>
{{out}}
<pre>
A=5 B=6 C=7 D=1 E=8 F=2 G=3 H=4
5 6
/|\ /|\
/ | X | \
/ |/ \| \
7 - 1 - 8 - 2
\ |\ /| /
\ | X | /
\|/ \|/
3 4
 
Elapsed Time: 2.092 ms.
 
</pre>
 
 
=={{header|Elixir}}==
Line 2,284 ⟶ 2,626:
 
=={{header|jq}}==
{{works with|jq|1.46}}
'''Also works with gojq, the Go implementation of jq'''
 
We present a generate-and-test solver for a slightly more general version of the problem, in which there are N pegs and holes, and in which the connectedness of holes is defined by an array such that holes i and j are connected if and only if [i,j] is a member of the
array.
Line 2,294 ⟶ 2,638:
 
'''Part 1: Generic functions'''
<syntaxhighlight lang="jq"># Short-circuit determination of whether (a|condition)
# permutations of 0 .. (n-1) inclusive
# is true for all a in array:
def forall(array; condition):
def check:
. as $ix
| if $ix == (array|length) then true
elif (array[$ix] | condition) then ($ix + 1) | check
else false
end;
0 | check;
 
# permutations of 0 .. (n-1)
def permutations(n):
# Given a single array, generate a stream by inserting n at different positions:
Line 2,317 ⟶ 2,651:
 
# Count the number of items in a stream
def count(f): reduce f as $_ (0; .+1);</syntaxhighlight>
</syntaxhighlight>
 
'''Part 2: The no-connections puzzle for N pegs and holes'''
<syntaxhighlight lang="jq"># Generate a stream of solutions.
# Generate a stream of solutions.
# Input should be the connections array, i.e. an array of [i,j] pairs;
# N is the number of pegs and holds.
Line 2,329 ⟶ 2,664:
def ok(connections):
. as $p
| forallall( connections[];
(($p[.[0]] - $p[.[1]])|abs) != 1 );
 
. as $connections | permutations(N) | select(ok($connections));</syntaxhighlight>
</syntaxhighlight>
'''Part 3: The 8-peg no-connection puzzle'''
<syntaxhighlight lang="jq"># The connectedness matrix:
# The connectedness matrix
# In this table, 0 represents "A", etc, and an entry [i,j]
# signifies that the holes with indices i and j are connected.
Line 2,373 ⟶ 2,710:
# To count the number of solutions:
# count(solve)
# => 16
 
limit(1; solve) | pp
# jq 1.4 lacks facilities for harnessing generators,
# but the following will suffice here:
def one(f): reduce f as $s
(null; if . == null then $s else . end);
 
one(solve) | pp
</syntaxhighlight>
{{outoutput}}
<syntaxhighlight lang="sh">$Invocation: jq -n -r -f no_connection.jq
<pre>
 
5 6
/|\ /|\
Line 2,392 ⟶ 2,725:
\ | X | /
\|/ \|/
3 4</syntaxhighlight>
</pre>
 
=={{header|Julia}}==
Line 3,964 ⟶ 4,298:
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="ecmascriptwren">import "./dynamic" for Tuple
 
var Solution = Tuple.create("Solution", ["p", "tests", "swaps"])
Aspen138
338

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328418...352546"