Solve the no connection puzzle: Difference between revisions

{{trans|Python}}

 

(1, 3), (1, 4), (1, 5),

(6, 2), (6, 3), (6, 4),

 

V solutions = solve()

 

{{out}}

=={{header|Ada}}==

This solution is a bit longer than it actually needs to be; however, it uses tasks to find the solution and the used types and solution-generating functions are well-separated, making it more amenable to other solutions or altering it to display all solutions.

With

Ada.Text_IO,

begin

Ada.Text_IO.Put_Line( Connection_Types.Image(Result) );

 

Package Connection_Types with Pure is

Function Image ( Input : Partial_Board ) Return String;

 

Pragma Ada_2012;

 

 

Function Connection_Combinations return Partial_Board;

 

Package Body Connection_Types is

end Image;

 

 

begin

End return;

End Connection_Combinations;

{{out}}

<pre> 4 5

{{works with|Dyalog APL 17.0 Unicode}}

 

 

 

tries[''⍴solns;]

}

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

 

/* ARM assembly Raspberry PI */

iMagicNumber: .int 0xCCCCCCCD

 

<pre>

a=3 b=4 c=7 d=1

 

=={{header|AutoHotkey}}==

,[ "X", "X", "X", "X"]

,[ "", "X", "X"]]

list .= oGrid[row, col+1] ? row ":" col+1 "," : oGrid[row, col-1] ? row ":" col-1 "," : ""

return Trim(list, ",")

Outputs:<pre>

3 5

=={{header|C}}==

{{trans|Go}}

#include <stdio.h>

#include <math.h>

solution(0, 8 - 1);

return 0;

{{out}}

<pre>----- 0 -----

2 8 1 7

4 3</pre>

 

=={{header|C++}}==

{{trans|C}}

#include <iostream>

#include <vector>

solution(0, pegs.size() - 1);

return 0;

{{out}}

<pre>----- 0 -----

 

=={{header|Chapel}}==

param A : hole = 1;

param B : hole = A+1;

}

<pre>

4 5

 

=={{header|D}}==

import std.stdio, std.math, std.algorithm, std.traits, std.string;

 

return board.tr("ABCDEFGH", "%(%d%)".format(perm)).writeln;

while (perm[].nextPermutation);

{{out}}

<pre>

Using a simple backtracking.

{{trans|Go}}

 

// Holes A=0, B=1, ..., H=7

board.tr("ABCDEFGH", "%(%d%)".format(sol.p)).writeln;

writeln("Tested ", sol.tests, " positions and did ", sol.swaps, " swaps.");

{{out}}

<pre>

5 6

Tested 12094 positions and did 20782 swaps.</pre>

 

=={{header|Elixir}}==

{{trans|Ruby}}

This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]]

 

# require HLPsolver

|> Enum.zip(~w[A B C D E F G H])

|> Enum.reduce(layout, fn {n,c},acc -> String.replace(acc, c, to_string(n)) end)

 

{{out}}

 

=={{header|Factor}}==

math.ranges math.parser multiline pair-rocket sequences

sequences.generalizations ;

: main ( -- ) find-solution display-solution ;

 

{{out}}

<pre>

=={{header|Fortran}}==

{{works with|gfortran|11.2.1}}

! via the Unlicense.

! For more information, please refer to <http://unlicense.org/>

 

program no_connection_puzzle

 

! The names of the holes.

end subroutine print_solution

 

The first solution printed:

{{out}}

=={{header|Go}}==

A simple recursive brute force solution.

 

import (

}

return b - a

{{out}}

<pre>

=={{header|Groovy}}==

{{trans|Java}}

import java.util.stream.IntStream

 

println(" ${pegs[6]} ${pegs[7]}")

}

{{out}}

<pre> 6 7

 

=={{header|Haskell}}==

 

solution :: [Int]

rightShift s

| length s > 3 = s

{{Out}}

<pre style="font-size:80%">A = 3

Supporting code:

 

 

connections=:".;._2]0 :0

disp=:verb define

rplc&(,holes;&":&>y) box

 

Intermezzo:

 

3 4 7 1 8 2 5 6

3 5 7 1 8 2 4 6

6 3 2 8 1 7 5 4

6 4 2 8 1 7 5 3

 

Since there's more than one arrangement where the pegs satisfy the task constraints, and since the task calls for one solution, we will need to pick one of them. We can use the "first" function to satisfy this important constraint.

 

3 4

/|\ /|\

5 6

 

 

'''Video'''

If we follow the video and also connect A and B as well as G and H, we get only four solutions (which we can see are reflections / rotations of each other):

 

3 5 7 1 8 2 4 6

4 6 7 1 8 2 3 5

5 3 2 8 1 7 6 4

 

The first of these looks like this:

 

3 - 5

/|\ /|\

\|/ \|/

4 - 6

 

For this puzzle, we can also see that the solution can be described as: put the starting and ending numbers in the middle - everything else follows from there. It's perhaps interesting that we get this solution even if we do not explicitly put that logic into our code - it's built into the puzzle itself and is still the only solution no matter how we arrive there.

The backtracking is getting tiresome, we'll try a stochastic solution for a change.<br>

{{works with|Java|8}}

import java.util.*;

import static java.util.stream.Collectors.toList;

System.out.printf(" %s %s%n", pegs[6], pegs[7]);

}

(takes about 500 shuffles on average)

<pre> 4 5

===ES6===

{{Trans|Haskell}}

'use strict';

 

 

return main();

{{Out}}

<pre>A = 3

 

=={{header|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.

 

'''Part 1: Generic functions'''

def permutations(n):

# Given a single array, generate a stream by inserting n at different positions:

 

# Count the number of items in a stream

'''Part 2: The no-connections puzzle for N pegs and holes'''

# Input should be the connections array, i.e. an array of [i,j] pairs;

# N is the number of pegs and holds.

def ok(connections):

. as $p

 

'''Part 3: The 8-peg no-connection puzzle'''

# In this table, 0 represents "A", etc, and an entry [i,j]

# signifies that the holes with indices i and j are connected.

| $letters

| reduce range(0;length) as $i ($board; index($letters[$i]) as $ix | .[$ix] = $in[$i] + 48)

'''Examples''':

# solve | pp

 

# To count the number of solutions:

# count(solve)

 

5 6

/|\ /|\

\ | X | /

\|/ \|/

 

=={{header|Julia}}==

using Combinatorics

 

 

printsolutions()

Found 16 solutions.

3 4

=={{header|Kotlin}}==

{{trans|Go}}

 

import kotlin.math.abs

println(pegsAsString(p))

println("Tested $tests positions and did $swaps swaps.")

 

{{out}}

 

Press space bar to see solutions so far.

Module no_connection_puzzle {

\\ Holes

no_connection_puzzle

 

{{out}}

<pre>

4 6

</pre >

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

This one simply takes all permutations of the pegs and filters out invalid solutions.

Select[#,

Function[perm, Abs[perm[[#2[[1]]]] - perm[[#2[[2]]]]] > 1]] &,

" `` ``\n /|\\ /|\\\n / | X | \\\n / |/ \\| \\\n`` - `` \

- `` - ``\n \\ |\\ /| /\n \\ | X | /\n \\|/ \\|/\n `` ``",

{{out}}

<pre> 3 4

I choose to use one-based indexing for the array of pegs. It seems more logical here and Nim allows to choose any starting index for static arrays.

 

 

const Connections = [(1, 3), (1, 4), (1, 5), # A to C, D, E

 

var pegs = [Peg 1, 2, 3, 4, 5, 6, 7, 8]

 

{{out}}

 

=={{header|Perl}}==

 

use strict;

exit;

}

{{out}}

<pre>

Brute force solution. I ordered the links highest letter first, then grouped by start letter to eliminate things asap. Nothing

to eliminate when placing A and B, when placing C, check that CA>1, when placing D, check that DA,DB,DC are all >1, etc.

{{out}}

<pre>

 

=={{header|Picat}}==

 

no_connection_puzzle(X) =>

" %d %d \n",

A,B,C,D,E,F,G,H),

<pre>

Picat> no_connection_puzzle(_X)

 

We first compute a list of nodes, with sort this list, and we attribute a value at the nodes.

 

edge(a, c).

set_constraint(H, T1, V, VT).

 

Output :

<pre> ?- no_connection_puzzle(Vs).

=={{header|Python}}==

A brute force search solution.

from itertools import permutations

from enum import Enum

if __name__ == '__main__':

solutions = solve()

 

{{out}}

 

Add the following code after that above:

"""Prettyprint a solution"""

boardformat = r"""

for i, s in enumerate(solutions, 1):

print("\nSolution", i, end='')

 

;Extra output:

=={{header|Racket}}==

 

;; Solve the no connection puzzle. Tim Brown Oct. 2014

 

"~a") pzl))

 

 

{{out}}

 

The idiosyncratic adjacency diagram is dealt with by the simple expedient of bending the two vertical lines <tt>||</tt> into two bows <tt>)(</tt>, such that adjacency can be calculated simply as a distance of 2 or less.

take [$y,$x] if abs($x|$y) > 2;

} for flat -5 .. 5 X -5 .. 5;

say "$tries tries";

 

{{out}}

=={{header|Red}}==

===Basic version===

 

points: [a b c d e f g h]

; start with and empty list

check []

 

{{out}}

 

===With graphics===

 

points: [a b c d e f g h]

; start with and empty list

check []

 

{{out}}

=={{header|REXX}}==

===unannotated solutions===

parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */

if limit=='' | limit=="," then limit= 1 /* ║ A B ║ */

if nL==fn | nH==fn then return 1 /*if ≡ ±1, then the node can't be used.*/

end /*ch*/ /* [↑] looking for suitable number. */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

===annotated solutions===

Usage note: &nbsp; if the &nbsp; '''limit''' &nbsp; (the 1^st argument) &nbsp; is negative, a diagram (node graph) is shown.

@abc= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

parse arg limit . /*number of solutions wanted.*/ /* ╔═══════════════════════════╗ */

end /*box*/

say _ 'a='a _ "b="||b _ 'c='c _ "d="d _ ' e='e _ "f="f _ 'g='g _ "h="h

{{out|output|text=&nbsp; when using the default inputs of: &nbsp; &nbsp; <tt> -1 </tt>}}

<pre>

=={{header|Ruby}}==

Be it Golden Frogs jumping on trancendental lilly pads, or a Knight on a board, or square pegs into round holes this is essentially a Hidato Like Problem, so I use [http://rosettacode.org/wiki/Solve_a_Hidato_puzzle#With_Warnsdorff HLPSolver]:

# Solve No Connection Puzzle

#

g.board[H[0]][H[1]].adj = [A,B,C,G]

g.solve

{{out}}

<pre>

{{libheader|Scala sub-repositories}}

{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/Ub2LEup/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/ZXGSJLFEQe21Frh4Vwp0WA Scastie (remote JVM)].

 

private def links = Seq(

 

printResult(genRandom.dropWhile(!notSolved(links, _)).head)

 

=={{header|Tcl}}==

{{tcllib|struct::list}}

package require struct::list

 

break

}

{{out}}

<pre> 3 4

{{trans|Kotlin}}

{{libheader|Wren-dynamic}}

 

var Solution = Tuple.create("Solution", ["p", "tests", "swaps"])

var s = solve.call()

System.print(pegsAsString.call(s.p))

 

{{out}}

 

=={{header|XPL0}}==

 

int Hole, Max, I;

until Hole = 8;

Text(0, Str);

 

{{out}}

=={{header|zkl}}==

{{trans|D}}

connections:=T(

T(PegA, PegC), T(PegA, PegD), T(PegA, PegE),

board.translate("ABCDEFGH",p.apply('+(1)).concat()).println();

break; // comment out to see all 16 solutions

The filter1 method stops on the first True, so it acts like a conditional or.

{{out}}