# Tag Info

## Hot answers tagged puzzle-solver

33

BBC BASIC, 570 514 490 bytes ASCII Download interpreter at http://www.bbcbasic.co.uk/bbcwin/download.html 435 bytes tokenised Full program displays an input from L.bmp on the screen, then modifies it to find a solution. *DISPLAY L t=PI/8q=FNa(1) DEFFNa(n)IFn=7END LOCALz,j,p,i,c,s,x,y,m,u,v F.z=0TO99u=z MOD10*100v=z DIV10*100ORIGINu,v F.j=0TO12S.4p=0F.i=j+...

21

Ruby, 85 bytes f=->l,n,s=n-l.sum-l.size+1{*a,b=l;b&&s>0?(a[0]?1+f[a,n-b-2,s-1]:(n.to_f/b).ceil-1):0} Try it online! Explanation The first step is to establish a recursive divide and conquer strategy to solve subproblems. I will use the variables $l=[l_1,l_2,...,l_x]$ for the list of clues, $x$ for the number of clues and $n$ for the ...

17

The shortest game of halma is 49 moves 49 move solution Proof there is no 48-move solution Code used for this solution The code now supports pass Notice that the 47 move solution in the paper is for the army transfer problem, not for the shortest game of halma I'll hopefully get to doing a proper writeup this weekend

16

05AB1E, 23 11 8 bytes ΔÍN-;иg= Try it online! Uses 0-based indexing. Explanation: # start from the implicit input Δ # loop forever Í # subtract 2 N- # subtract the current iteration number ; # divide by 2 и # create a list of length x g # get the length of the list = ...

15

C# - 2,098,382 steps I try many things, most of them fail and just didn't work at all, until recently. I got something interesting enough to post an answer. There is certainly ways to improve this further more. I think going under the 2M steps might be possible. It took approx 7 hours to generate results. Here is a txt file with all solutions, in case ...

14

C++ - 0.201s official score Using Tdoku (code; design; benchmarks) gives these results: ~/tdoku$lscpu | grep Model.name Model name: Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz ~/tdoku$ # build: ~/tdoku$CC=clang-8 CXX=clang++-8 ./BUILD.sh ~/tdoku$ clang -o solve example/solve.c build/libtdoku.a ~/tdoku$# adjust input format: ~/tdoku$ sed -e "s/...

13

Octave, 334 313 bytes Since the challenge may seem a bit daunting, I present my own solution. I did not formally prove that this method works (I guess that will come down to proving that the algorithm will never get stuck in a loop), but so far it works perfectly, doing 100x100 testcases within 15 seconds. Note that I chose to use a function with side ...

11

Python - 48 characters exec("".join(map(chr,map(len,' ...

11

Python 2.7: 544 bytes -50% = 272 bytes** import sys;o=''.join;r=range;a=sys.argv[1];a=o([(' ',x)[x in a[12]+a[19]+a[22]] for x in a]);v={a:''};w={' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:''} m=lambda a,k:o([a[([0x55a5498531bb9ac58d10a98a4788e0,0xbdab49ca307b9ac2916a4a0e608c02,0xbd9109ca233beac5a92233a842b420][k]>>5*i)%32] for i in r(24)]) def z(d,h): ...

10

Python – 10,800,000 steps As a last-place reference solution, consider this sequence: print "123456" * 18 Cycling through all the colours n times means that every square n steps away will be guaranteed to be of the same colour as the center square. Every square is at most 18 steps away from the center, so 18 cycles will guarantee all the squares ...

10

Python 2, 115 bytes n=input() for F in range(4): t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n) if x<1:print t[:-1];break This is the golfed version of the program I wrote while discussing the problem with Martin. Input is a list via STDIN. Output is a list representing the last solution found if there is a solution, or zero if ...

10

Python - 1669 Still pretty long, but fast enough to run the last example in under a second on my computer. It's probably possible to make shorter at the cost of speed, but for now it is pretty much equivalent to the ungolfed code. Example output for last test case: 0 11 1 11 2 11 3 11 4 11 4 10 3 10 2 10 1 10 1 9 2 9 3 9 4 9 4 8 3 8 3 7 4 7 5 7 5 6 5 5 6 5 6 ...

10

JavaScript (ES6), 41 bytes Returns false for valid or true for invalid. a=>a.some(p=(x,i)=>--p>0?x:a[i+x-1]^=p=x) Try it online! Commented a => // a[] = input a.some(p = // start with p NaN'ish (x, i) => // for each value x at position i in a[]: --p > 0 ? // decrement p; if it's positive: x // ...

9

Pyth, 66 ?"Yes".Am>2sm^-.uk2Cm.Dx"qwertyuiopasdfghjkl*zxcvbnm"b9.5dC,ztz"No Try it here. I was surprised to learn Pyth doesn't have a hypotenuse function, so this will likely be beat by a different language. I'll propose a hypotenuse function to Pyth, so this atrocity won't happen in the future. Explanation I transform the ...

9

MATL, 68 59 58 bytes '?'7XJQtX"'s'jh5e"@2#1)t35>)-1l8t_4$h9M)b'nsew'=8M*sJ+XJ+( Try it online! Explanation The map is kept in the bottom of the stack and gradually filled. The current position of the explorer is stored in clipboard J. The map uses matrix coordinates, so (1,1) is upper left. In addition, column-major linear indexing is used. ... 9 Haskell, 242 230 201 199 177 163 160 149 131 bytes import Data.Lists m=map a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b] g=m$list[0]id.m sum.wordsBy(<1) Finally under 200 bytes, credit to @Bergi. Huge thanks to @nimi for helping almost halving the size. Wow. Almost at half size now, partly because of me but ... 9 Python 2, 75 bytes f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)] Try it online! Explanation: Builds a sequence of 'binary' chunks, with a base number matching the number of cuts. Eg: 63 can be done in 3 cuts, which means a partition in base-4 (as we have 3 single rings): Cuts: 5, 14, 31, which gives chains of 4 1 8 1 ... 8 PyPy, 195 moves, ~12 seconds computation Computes optimal solutions using IDA* with a 'walking distance' heuristic augmented with linear conflicts. Here are the optimal solutions: 5 1 7 3 9 2 11 4 13 6 15 8 0 10 14 12 Down, Down, Down, Left, Up, Up, Up, Left, Down, Down, Down, Left, Up, Up, Up 2 5 13 12 1 0 3 15 9 7 14 6 10 11 8 4 Left,... 8 Java - 2,480,714 steps I made a little mistake before (I put one crucial sentence before a loop instead of in the loop: import java.io.*; public class HerjanPaintAI { BufferedReader r; String[] map = new String[19]; char[][] colors = new char[19][19]; boolean[][] reached = new boolean[19][19], checked = new boolean[19][19]; int[] ... 8 C#, M = 2535 This implements* the system which I described mathematically on the thread which provoked this contest. I claim the 300 rep bonus. The program self-tests if you run it either without command-line arguments or with --test as a command-line argument; for spy 1, run with --spy1, and for spy 2 with --spy2. In each case it takes the number which I ... 8 Python 2, 305 This is the golfed version. It is practically unusable for n > 3, as the time (and space) complexity is like 3n2... actually that may be way too low for the time. Anyway, the function accepts a list of strings. def f(i): Z=range;r=map(__import__('fractions').Fraction,i);R=r[1:];n=len(R);L=[[[1]*n,[0]]];g=0 for m,p in L: for d in([v/3**i%... 8 C, 590 640 760 880 963 1018 Brute force is quite fast for this. The 12x12 test runs under 10ms. Knowing that could opt for some language more appropriate for golfing. I don't assume the board is square as the larger puzzles tend not to be square. The W define sets the limit on the board dimensions. The actual limit is smaller W - 2 as I use extra rows for ... 8 Python 2 & PuLP — 2,644,688 squares (optimally minimized); 10,753,553 squares (optimally maximized) Minimally golfed to 1152 bytes from pulp import* x=0 f=open("c","r") g=open("s","w") for k,m in enumerate(f): if k%2: b=map(int,m.split()) p=LpProblem("Nn",LpMinimize) q=map(str,range(18)) ir=q[1:18] e=LpVariable.dicts("c",(q,q),0,1,... 8 JavaScript (ES6), 25 bytes x=>y=>((x<3?x:3)+x)*y/2+1 x=>y=>(x<3?x+x:x+3)*y/2+1 x=>y=>(x<3?x:(x+3)/2)*y+1 x=>y=>(x<3?x:x/2+1.5)*y+1 All of these compute the same value; I can't seem to come up with a shorter formulation. When x is less than 3, you take as much water as you can and walk as far as you can, which is simply ... 8 R, 77 69 bytes -8 bytes thanks to Aaron Hayman pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n] Try it online! Let $k$ be the number of cuts needed; $k$ is the smallest integer such that $(k+1)\cdot2^k\geq n$. Indeed, a possible solution is then to have subchains of lengths $1,1,\ldots,1$ ($k$ times) and \$(k+1), 2(k+...

8

Node.js, 8.231s 6.735s official score Takes the file name as argument. The input file may already contain the solutions in the format described in the challenge, in which case the program will compare them with its own solutions. The results are saved in 'sudoku.log'. Code 'use strict'; const fs = require('fs'); const BLOCK = []; const BLOCK_NDX = [...

7

SWI Prolog, 183 characters m(A,A). m([i],[i,u]). m([i,i,i|T],B):-m([u|T],B). m([u,u|T],B):-m(T,B). n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)). n(A,B):-m(A,B). s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y). How about some Prolog, (since nobody has answered in 6 months). To run, just use "s(mi,mu)." The code breaks up atoms into chars, then searches for ...

7

C, 366 - 50% optimal bonus = 183 char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};r=20;f(int m,int n){int e,i,j;for(i=4;i--;){for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;for(e=0,j=68;j<76;j++) e+= (c[j]!=c[j+8]) + (c[j]!=c[j^1]);i&&e&...

7

Lua, 594 575 559 Bytes Warning There's still lots of work before I'm done with this golfing! I should be able to take that under 500 Bytes, at the very least. For the moment, it's the first solution that worked, and I'm still working on it. I will provide a full explanation once I'm done. function f(t)s=#t a=","for i=1,s do p=t[i]for i=1,s do p.Q=...

7

JavaScript (ES6), 297 286 279 267 bytes Takes input in currying syntax (s)(k), where s is an array of digit characters and k is the number of moves (integer). s=>k=>(B=(n,b=0)=>n?B(n^n&-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=>c.charCodeAt()+2),r=[],g=(n,d='')=>n?n>0&&b.map((v,i)=>g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=>s+...

Only top voted, non community-wiki answers of a minimum length are eligible