Solve a Hopido puzzle: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 32: | Line 32: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">V neighbours = [[2, 2], [-2, 2], [2, -2], [-2, -2], [3, 0], [0, 3], [-3, 0], [0, -3]] |
||
V cnt = 0 |
V cnt = 0 |
||
V pWid = 0 |
V pWid = 0 |
||
Line 86: | Line 86: | ||
print() |
print() |
||
E |
E |
||
print(‘No solution!’, end' ‘’)</ |
print(‘No solution!’, end' ‘’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 99: | Line 99: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">SolveHopido(Grid, Locked, Max, row, col, num:=1, R:="", C:=""){ |
||
if (R&&C) ; if neighbors (not first iteration) |
if (R&&C) ; if neighbors (not first iteration) |
||
{ |
{ |
||
Line 168: | Line 168: | ||
} |
} |
||
return StrReplace(map, ">") |
return StrReplace(map, ">") |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">;-------------------------------- |
||
Grid := [["",0 ,0 ,"",0 ,0 ,""] |
Grid := [["",0 ,0 ,"",0 ,0 ,""] |
||
,[0 ,0 ,0 ,0 ,0 ,0 ,0] |
,[0 ,0 ,0 ,0 ,0 ,0 ,0] |
||
Line 197: | Line 197: | ||
;-------------------------------- |
;-------------------------------- |
||
MsgBox, 262144, ,% SolveHopido(Grid, Locked, Max, row, col) |
MsgBox, 262144, ,% SolveHopido(Grid, Locked, Max, row, col) |
||
return</ |
return</syntaxhighlight> |
||
Outputs:<pre> 17 24 16 25 |
Outputs:<pre> 17 24 16 25 |
||
22 8 11 21 7 10 20 |
22 8 11 21 7 10 20 |
||
Line 210: | Line 210: | ||
Any non-numeric value indicates a no-go.<br/> |
Any non-numeric value indicates a no-go.<br/> |
||
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.<br/> |
If there are cells that require more characters, then a 2-dimensional array of ints must be used. Any number < 0 indicates a no-go.<br/> |
||
< |
<syntaxhighlight lang="csharp">using System.Collections; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using static System.Console; |
using static System.Console; |
||
Line 335: | Line 335: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="height:30ex;overflow:scroll"> |
<pre style="height:30ex;overflow:scroll"> |
||
Line 347: | Line 347: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <vector> |
#include <vector> |
||
#include <sstream> |
#include <sstream> |
||
Line 481: | Line 481: | ||
return system( "pause" ); |
return system( "pause" ); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 495: | Line 495: | ||
{{trans|C++}} |
{{trans|C++}} |
||
From the refactored C++ version with more precise typing. This tries all possible start positions. The HopidoPuzzle struct is created at compile-time, so its pre-conditions can catch most malformed puzzles at compile-time. |
From the refactored C++ version with more precise typing. This tries all possible start positions. The HopidoPuzzle struct is created at compile-time, so its pre-conditions can catch most malformed puzzles at compile-time. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.conv, std.string, std.range, std.algorithm, std.typecons; |
||
Line 608: | Line 608: | ||
else |
else |
||
writefln("One solution:\n%(%-(%2s %)\n%)", solution); |
writefln("One solution:\n%(%-(%2s %)\n%)", solution); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>One solution: |
<pre>One solution: |
||
Line 621: | Line 621: | ||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]] |
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#Elixir | here]] |
||
< |
<syntaxhighlight lang="elixir"># require HLPsolver |
||
adjacent = [{-3, 0}, {0, -3}, {0, 3}, {3, 0}, {-2, -2}, {-2, 2}, {2, -2}, {2, 2}] |
adjacent = [{-3, 0}, {0, -3}, {0, 3}, {3, 0}, {-2, -2}, {-2, 2}, {2, -2}, {2, 2}] |
||
Line 633: | Line 633: | ||
. . . 1 . . . |
. . . 1 . . . |
||
""" |
""" |
||
HLPsolver.solve(board, adjacent)</ |
HLPsolver.solve(board, adjacent)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 656: | Line 656: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 778: | Line 778: | ||
} |
} |
||
printResult() |
printResult() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 794: | Line 794: | ||
Minor variant of [[Solve_a_Holy_Knight's_tour]]. Works in Unicon only. |
Minor variant of [[Solve_a_Holy_Knight's_tour]]. Works in Unicon only. |
||
< |
<syntaxhighlight lang="unicon">global nCells, cMap, best |
||
record Pos(r,c) |
record Pos(r,c) |
||
Line 891: | Line 891: | ||
QMouse(puzzle, visit(loc.r, loc.c+3), self, val) |
QMouse(puzzle, visit(loc.r, loc.c+3), self, val) |
||
QMouse(puzzle, visit(loc.r-2,loc.c+2), self, val) |
QMouse(puzzle, visit(loc.r-2,loc.c+2), self, val) |
||
end</ |
end</syntaxhighlight> |
||
Sample run: |
Sample run: |
||
Line 923: | Line 923: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|8}} |
{{works with|Java|8}} |
||
< |
<syntaxhighlight lang="java">import java.util.*; |
||
public class Hopido { |
public class Hopido { |
||
Line 1,031: | Line 1,031: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre> |
<pre> |
||
Line 1,043: | Line 1,043: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task. |
Uses the Hidato puzzle solver module, which has its source code listed [[Solve_a_Hidato_puzzle#Julia | here]] in the Hadato task. |
||
< |
<syntaxhighlight lang="julia">using .Hidato # Note that the . here means to look locally for the module rather than in the libraries |
||
const hopid = """ |
const hopid = """ |
||
Line 1,059: | Line 1,059: | ||
hidatosolve(board, maxmoves, hopidomoves, fixed, starts[1][1], starts[1][2], 1) |
hidatosolve(board, maxmoves, hopidomoves, fixed, starts[1][1], starts[1][2], 1) |
||
printboard(board) |
printboard(board) |
||
</ |
</syntaxhighlight>{{output}}<pre> |
||
0 0 0 0 |
0 0 0 0 |
||
0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 |
||
Line 1,077: | Line 1,077: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">// version 1.2.0 |
||
val board = listOf( |
val board = listOf( |
||
Line 1,172: | Line 1,172: | ||
printResult() |
printResult() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,186: | Line 1,186: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
Uses shortest tours on graphs to solve it: |
Uses shortest tours on graphs to solve it: |
||
< |
<syntaxhighlight lang="mathematica">puzz = ".00.00.\n0000000\n0000000\n.00000.\n..000..\n...0..."; |
||
puzz //= StringSplit[#, "\n"] & /* Map[Characters]; |
puzz //= StringSplit[#, "\n"] & /* Map[Characters]; |
||
puzz //= Transpose /* Map[Reverse]; |
puzz //= Transpose /* Map[Reverse]; |
||
Line 1,193: | Line 1,193: | ||
g = Graph[UndirectedEdge @@@ moves]; |
g = Graph[UndirectedEdge @@@ moves]; |
||
ord = Most[FindShortestTour[g][[2]]]; |
ord = Most[FindShortestTour[g][[2]]]; |
||
Graphics[MapThread[Text, {Range[Length[ord]], VertexList[g][[ord]]}]]</ |
Graphics[MapThread[Text, {Range[Length[ord]], VertexList[g][[ord]]}]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Shows a graphical solution. |
Shows a graphical solution. |
||
Line 1,200: | Line 1,200: | ||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="nim">import algorithm, sequtils, strformat |
||
const Moves = [(-3, 0), (0, 3), ( 3, 0), ( 0, -3), |
const Moves = [(-3, 0), (0, 3), ( 3, 0), ( 0, -3), |
||
Line 1,294: | Line 1,294: | ||
var hopido = initHopido(Board) |
var hopido = initHopido(Board) |
||
hopido.findSolution() |
hopido.findSolution() |
||
hopido.print()</ |
hopido.print()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,310: | Line 1,310: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # http://www.rosettacode.org/wiki/Solve_a_Hopido_puzzle |
use strict; # http://www.rosettacode.org/wiki/Solve_a_Hopido_puzzle |
||
Line 1,347: | Line 1,347: | ||
. 0 0 0 0 0 . |
. 0 0 0 0 0 . |
||
. . 0 0 0 . . |
. . 0 0 0 . . |
||
. . . 0 . . .</ |
. . . 0 . . .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,362: | Line 1,362: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Simple brute force approach. |
Simple brute force approach. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">board</span> |
||
Line 1,425: | Line 1,425: | ||
. . . 0 . . ."""</span> |
. . . 0 . . ."""</span> |
||
<span style="color: #000000;">Hopido</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">Hopido</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
The best and worse cases observed were: |
The best and worse cases observed were: |
||
<pre> |
<pre> |
||
Line 1,444: | Line 1,444: | ||
</pre> |
</pre> |
||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
<syntaxhighlight lang="picat"> |
|||
<lang Picat> |
|||
import sat. |
import sat. |
||
main => |
main => |
||
Line 1,473: | Line 1,473: | ||
if C = NC then nl end |
if C = NC then nl end |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> 24 15 23 26 |
<pre> 24 15 23 26 |
||
Line 1,486: | Line 1,486: | ||
This is a pure prolog implementation (no cuts,etc..), the only libary predicate used is select/3 witch is pure. |
This is a pure prolog implementation (no cuts,etc..), the only libary predicate used is select/3 witch is pure. |
||
< |
<syntaxhighlight lang="prolog">hopido(Grid,[C|Solved],Xs,Ys) :- |
||
select(C,Grid,RGrid), |
select(C,Grid,RGrid), |
||
solve(RGrid,C,Solved,Xs,Ys). |
solve(RGrid,C,Solved,Xs,Ys). |
||
Line 1,509: | Line 1,509: | ||
j3(O,N,[O,_,_,N|_]). |
j3(O,N,[O,_,_,N|_]). |
||
j3(O,N,[_|T]) :- j3(O,N,T).</ |
j3(O,N,[_|T]) :- j3(O,N,T).</syntaxhighlight> |
||
To test send in a list of p/2 terms that represent points that can be hopped to (order is not important). |
To test send in a list of p/2 terms that represent points that can be hopped to (order is not important). |
||
The grid coords can be anything so need to specify the valid coordinates as a list (in this case numbers between 0 and 6). |
The grid coords can be anything so need to specify the valid coordinates as a list (in this case numbers between 0 and 6). |
||
< |
<syntaxhighlight lang="prolog">puzzle([ |
||
p(1,0),p(2,0) ,p(4,0),p(5,0), |
p(1,0),p(2,0) ,p(4,0),p(5,0), |
||
p(0,1),p(1,1),p(2,1),p(3,1),p(4,1),p(5,1),p(6,1), |
p(0,1),p(1,1),p(2,1),p(3,1),p(4,1),p(5,1),p(6,1), |
||
Line 1,526: | Line 1,526: | ||
XYs = [0,1,2,3,4,5,6], |
XYs = [0,1,2,3,4,5,6], |
||
hopido(P,S,XYs,XYs), |
hopido(P,S,XYs,XYs), |
||
maplist(writeln,S).</ |
maplist(writeln,S).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,562: | Line 1,562: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python"> |
||
from sys import stdout |
from sys import stdout |
||
Line 1,626: | Line 1,626: | ||
else: |
else: |
||
stdout.write("No solution!") |
stdout.write("No solution!") |
||
</ |
</syntaxhighlight> {{out}}<pre> |
||
01 25 17 03 |
01 25 17 03 |
||
27 13 10 07 14 11 08 |
27 13 10 07 14 11 08 |
||
Line 1,641: | Line 1,641: | ||
essentially the neighbourhood function. |
essentially the neighbourhood function. |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require "hidato-family-solver.rkt") |
(require "hidato-family-solver.rkt") |
||
Line 1,658: | Line 1,658: | ||
#(_ _ 0 0 0 _ _) |
#(_ _ 0 0 0 _ _) |
||
#(_ _ _ 0 _ _ _))))) |
#(_ _ _ 0 _ _ _))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,679: | Line 1,679: | ||
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]] |
* [[Solve the no connection puzzle#Raku|Solve the no connection puzzle]] |
||
<lang |
<syntaxhighlight lang="raku" line>my @adjacent = [3, 0], |
||
[2, -2], [2, 2], |
[2, -2], [2, 2], |
||
[0, -3], [0, 3], |
[0, -3], [0, 3], |
||
Line 1,776: | Line 1,776: | ||
say "$tries tries"; |
say "$tries tries"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,791: | Line 1,791: | ||
No particular effort was made to reduce the elapsed time in solving the puzzle. |
No particular effort was made to reduce the elapsed time in solving the puzzle. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program solves a Hopido puzzle, it also displays the puzzle and the solution. */ |
||
call time 'Reset' /*reset the REXX elapsed timer to zero.*/ |
call time 'Reset' /*reset the REXX elapsed timer to zero.*/ |
||
maxR=0; maxC=0; maxX=0; minR=9e9; minC=9e9; minX=9e9; cells=0; @.= |
maxR=0; maxC=0; maxX=0; minR=9e9; minC=9e9; minX=9e9; cells=0; @.= |
||
Line 1,846: | Line 1,846: | ||
say _ |
say _ |
||
end /*r*/ |
end /*r*/ |
||
say; return</ |
say; return</syntaxhighlight> |
||
'''output''' when the input is: <br> |
'''output''' when the input is: <br> |
||
<tt> 1 4 1 \2 3 . . . \3 2 . . . . . \4 1 . . . . . . . \5 1 . . . . . . . \6 2 . . \6 5 . . </tt> |
<tt> 1 4 1 \2 3 . . . \3 2 . . . . . \4 1 . . . . . . . \5 1 . . . . . . . \6 2 . . \6 5 . . </tt> |
||
Line 1,871: | Line 1,871: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]] |
This solution uses HLPsolver from [[Solve_a_Hidato_puzzle#With_Warnsdorff | here]] |
||
< |
<syntaxhighlight lang="ruby">require 'HLPsolver' |
||
ADJACENT = [[-3, 0], [0, -3], [0, 3], [3, 0], [-2, -2], [-2, 2], [2, -2], [2, 2]] |
ADJACENT = [[-3, 0], [0, -3], [0, 3], [3, 0], [-2, -2], [-2, 2], [2, -2], [2, 2]] |
||
Line 1,885: | Line 1,885: | ||
t0 = Time.now |
t0 = Time.now |
||
HLPsolver.new(board1).solve |
HLPsolver.new(board1).solve |
||
puts " #{Time.now - t0} sec"</ |
puts " #{Time.now - t0} sec"</syntaxhighlight> |
||
Which produces: |
Which produces: |
||
<pre> |
<pre> |
||
Line 1,909: | Line 1,909: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6 |
||
oo::class create HopidoSolver { |
oo::class create HopidoSolver { |
||
Line 2,004: | Line 2,004: | ||
HopidoSolver create hop $puzzle |
HopidoSolver create hop $puzzle |
||
hop solve |
hop solve |
||
showPuzzle [hop solution] "Output"</ |
showPuzzle [hop solution] "Output"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,027: | Line 2,027: | ||
{{libheader|Wren-sort}} |
{{libheader|Wren-sort}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/sort" for Sort |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 2,125: | Line 2,125: | ||
if (pos >= nRows * nCols) break |
if (pos >= nRows * nCols) break |
||
} |
} |
||
printResult.call()</ |
printResult.call()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,139: | Line 2,139: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
This solution uses the code from [[Solve_a_Numbrix_puzzle#zkl]] |
This solution uses the code from [[Solve_a_Numbrix_puzzle#zkl]] |
||
< |
<syntaxhighlight lang="zkl">hi:= // 0==empty cell, X==not a cell |
||
#<<< |
#<<< |
||
" X 0 0 X 0 0 X |
" X 0 0 X 0 0 X |
||
Line 2,159: | Line 2,159: | ||
println(); |
println(); |
||
puzzle.print_board(); |
puzzle.print_board(); |
||
println();</ |
println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |