20
\$\begingroup\$

(This is part 1 in a two-part challenge.)

Your task is to solve a Hexasweep puzzle.

A Hexasweep puzzle is set out on a grid of diamonds arranged in hexagonal shapes, of which the board looks like a hexagon, like so:

         _____
        /\    \
  _____/ X\____\_____
 /\    \  / XX /\    \
/X \____\/____/X \____\
\ X/ XX /\    \ X/    /
 \/____/  \____\/____/
 /\    \  / X  /\    \
/  \____\/____/  \____\
\  / XX /\    \  / XX /
 \/____/  \____\/____/
       \ X/    /
        \/____/

The above image is composed of 7 hexagons (21 diamonds), and is thus a Hexasweep puzzle of size 2.

  • If you want to expand it, cover the current Hexasweep puzzle with more hexagons (so that there are 19 hexagons - that will make a Hexasweep puzzle of size 3).

  • The same goes for the other direction - to make a Hexasweep puzzle of size 1, remove the outermost layer of hexagons (so that there's 1 hexagon).

Each diamond can contain 0, 1 or 2 "bombs", with bombs depicted as X above. With bombs filled out, this is the final solution.

Numbers are marked on "intersection points", to show how many bombs are on the diamonds which are touching those intersection points - the intersection points of this grid are shown below using O.

         _____
        /\    \
  _____/  OO___\_____
 /\    \  OO   /\    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
 \/___OO  OO___OO____/
 /\   OO  OO   OO    \
/  OO___OO___OO  OO___\
\  OO   OO   OO  OO   /
 \/____/  OO___\/____/
       \  OO   /
        \/____/

As you can see, there are two "types" of intersection points - those with 3 diamonds touching it, and those with 6 (the one that are touching the edge of the board aren't counted):

  _____
 /\  XX\
/X OO___\
\ XOO   /
 \/____/

       /\
 _____/X \_____
 \ XX \ X/    /
  \____OO____/
  / XX OO  X \
 /____/  \____\
      \ X/
       \/

The two intersections would be marked with 4 and 8 respectively.

In the original Hexasweep puzzle above, the intersection numbers would be:

   3
4 5 4 2
 2 1 3
2 4 1 2
   1

Which would be condensed to:

3,4,5,4,2,2,1,3,2,4,1,2,1

Given an input in this "condensed form", you must output the original puzzle, in "condensed form" (see above).

The solved image (the first one, with the crosses) - which would be formed from the puzzle - would be read from top to bottom, starting from the left:

2,0,0,2,0,2,1,0,1,0,2,0,1,0,0,2,0,0,0,0,2

That is now the "condensed form" of the puzzle.

If there is more than 1 answer (as in the condensed form above), the output must be N.

Examples:

0,0,4,3,1,3,4,7,1,4,3,6,1 -> 0,0,0,0,1,0,0,2,0,0,0,2,0,1,0,1,2,0,0,2,2 (size 2 Hexasweep)
6 -> 2,2,2 (size 1 Hexasweep)
0,1,5,3,1,4,4,7,2,5,3,6,1 -> N (multiple solutions)

Specs:

  • Any delimiter for the "condensed form" as input are allowed (it doesn't have to be , separating the numbers).
  • You may output a list, or a string with any delimiter.
  • Your program must be generalised: it must be able to solve Hexasweep puzzles of any size (at least from size 1 to size 4).

This is , so lowest amount of bytes wins!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ shouldn't these be two separate challenges? \$\endgroup\$ Nov 27, 2016 at 6:01
  • \$\begingroup\$ @DestructibleWatermelon I've decided to clump them together into one challenge, so that the score could be combined easily. \$\endgroup\$
    – clismique
    Nov 27, 2016 at 6:02
  • \$\begingroup\$ but why should they be combined? \$\endgroup\$ Nov 27, 2016 at 6:03
  • \$\begingroup\$ I agree with @DestructibleWatermelon that this should be two challenges. The two parts are not really dependent on each other except when calculating the score. A notable example of this is cops-and-robbers challenges \$\endgroup\$ Nov 27, 2016 at 6:20
  • 1
    \$\begingroup\$ Also the board is not a hexagon. \$\endgroup\$ Nov 27, 2016 at 22:45

1 Answer 1

15
+200
\$\begingroup\$

Javascript (V8), 1509 bytes

V=>{S=Math.sqrt(V[L="length"])/3+1|0;C=(Y=Array)(3**(W=12*(S-1)||2))[F="fill"]``.map(c=>Y(G=3*S*(S-1)+1)[F]``.map(h=>[N=-1,N,N]))
O=[];R=Y(4*S-3)[F]``.map(r=>[]);for(r=0,c=1,m=S,i=0;i<G;++r>=m&&(r=0,m+=++c>S?N:1))R[r*2+(X=Math.abs)(S-c)][P="push"](i++,N)
R=R.map(r=>(r.pop(t=Y(((T=2*S-1)-r[L]+1)/2)[F](N)),t.concat(r,t)));I=R.flat()[K="filter"](Q=r=>r+1);J=[[m=1,0]]
if(S>1){for(i=0;i<S-1;i++)J[P]([m+=3,0]);for(i=0;i<S-1;i++)J[P]([m-1,2],[m,0]);for(i=0;i<S-1;i++)J[P]([m-=3,0])}M=[]
J[K](j=>(t=j[1],Y(j[0])[F]``[K](_=>M[P](t++%3))))
z=0;g=p=>{for(j=0;j<R[L];j++)if(p<(t=R[j][K](Q))[L]){a=R[b=j].indexOf(t[p]);break}else p-=t[L]}
M=M.map((v,i)=>v?(v<2?(g(z-1),[[I[z-1],1],[I[z-1],2],[R[b-1][++a],0],[R[b-1][a],2],[R[b+1][a],0],[R[b+1][a],1]]):(g(z),[[I[z],0],[R[b-1][a-1],2],[R[b+1][a-1],1]])):(x=[0,1,2].map(d=>[I[z],d]),z++,x))
C.map((c,i)=>{r=-2;s=_=>[...i.toString(3).padStart(W,0).substr(r+=2,2).split``.map(n=>+n),N];for(j=0;j<S;c[j++]=s())
t=S-1;for(j=1;j<S;j++)c[++t]=s(),c[t+=j+S-1]=s();for(j=S-2;j>0;j--)c[++t]=s(),c[t+=j+S-1]=s();if(S>1)for(j=0;j<S;j++)c[++t]=s()})
C.map(c=>{q=1;l:while(c.find(h=>h[0]<0|h[1]<0|h[2]<0))for(j=0;j<M[L];j++){t=M[j];if(t[K](Z=v=>!(c[v[0]][v[1]]+1))[L]==1){if((s=V[j]-t.reduce(U=(a,v)=>a+(c[v[0]][v[1]]+1||1)-1,0))<0||s>2){q=0;break l};r=t.find(Z);c[r[0]][r[1]]=s}};
M.map((t,j)=>{if(t.reduce(U,0)!=V[j])q=0})
q&&O[P](c)});if(O[L]>1)return"N";O=O[p=0];E=[];for(i=0;i<T;i++){a=T-X(S-i-1);for(j=0;j<a;j++)E[P](O[p+j][0]);for(j=0;j<a;j++)E[P](O[p][1],O[p++][2])}return E}

Wow. This was not as fun as I expected it would be.

This is by far not an optimal solution. It's hard to golf something this big. I think you could save a hundred bytes or so by brute forcing the answer instead. However, my goal wasn't to be super competitive (yet!), but instead to provide a baseline for other answers to work off of.

Seeing as this challenge hasn't been answered in the four years since it was asked, it obviously took a few days. The strategy I ended up using was to generate a list of all possible values for the outer ring of hexagons, and repeatedly fill in any diamonds whose values can be inferred from the vertexes near them. If any contradictions are found, that starting value is ignored and the next one is analyzed.

This likely costs a few bytes compared to brute forcing, but it means it can finish running before the inevitable heat death of the universe. It takes less than a second for size one, about half a minute for size two, and based on the time complexity somewhere in the span of a few weeks to a few months for size three (haven't tested yet). My computer doesn't actually have enough memory for attempting higher than size two (gives me invalid array length), but with enough time and memory it's theoretically possible to use this approach for puzzles with millions of hexagons.

If anyone wants to use this to develop a shorter or faster solution, here's the pre-golfed version of my code (it's not very pretty, but it works):

var hexasweep = function(vertexes) {
    var size = Math.sqrt(vertexes.length) / 3 + 1 | 0;
    
    var configs = new Array(3 ** (2 * (6 * (size - 1) || 1))).fill(0).map(c => new Array(3 * size * (size - 1) + 1).fill(0).map(h => [-1, -1, -1]));
    
    var solutions = [];
    
    var reference_array = new Array(4 * size - 3).fill(0).map(r => []);
    
    for (let r = 0, c = 0, m = size, i = 0; i < 3 * size * (size - 1) + 1; i++) {
        reference_array[r * 2 + Math.abs(size - c - 1)].push(i, -1);
        
        if (++r >= m) {
            m += (++c >= size ? -1 : 1);
            r = 0;
        }
    }
    
    for (let t, r, i = 0; i < reference_array.length; i++) {
        r = reference_array[i];
        
        r.pop();
        
        t = new Array(((2 * size - 1) - r.length) / 2).fill(-1);
        
        reference_array[i] = t.concat(r, t);
    }
    
    var reference = reference_array.flat().filter(r => r + 1);
    
    var m = 1, length_map = [];
    
    length_map.push([m = 1, 0]);
    
    if (size > 1) {
        for (let i = 0; i < size - 1; i++) {
            length_map.push([m += 3, 0]);
        }

        for (let i = 0; i < size - 1; i++) {
            length_map.push([m - 1, 2], [m, 0]);
        }

        for (let i = 0; i < size - 1; i++) {
            length_map.push([m -= 3, 0]);
        }
    }
    
    var vertex_map = [];
    
    for (let t, i = 0; i < length_map.length; i++) {
        t = length_map[i][1];
        
        for (let j = 0; j < length_map[i][0]; j++) {
            vertex_map.push(t++ % 3);
        }
    }
    
    for (let v, z = 0, b, a, g, i = 0; i < vertex_map.length; i++) {
        v = vertex_map[i];
        
        g = p => {
            for (let t, j = 0; j < reference_array.length; j++) {
                if (p < (t = reference_array[j].filter(r => r + 1)).length) {
                    b = j;
                    a = reference_array[j].indexOf(t[p]);

                    break;
                } else {
                    p -= t.length;
                }
            }
        }
        
        if (v == 0) {
            vertex_map[i] = [0, 1, 2].map(d => [reference[z], d]);
            z++;
        } else if (v == 2) {
            g(z);
            
            vertex_map[i] = [[reference[z], 0], [reference_array[b - 1][a - 1], 2], [reference_array[b + 1][a - 1], 1]];
        } else {
            g(z - 1);
            
            vertex_map[i] = [
                [reference[z - 1], 1],
                [reference[z - 1], 2],
                [reference_array[b - 1][a + 1], 0],
                [reference_array[b - 1][a + 1], 2],
                [reference_array[b + 1][a + 1], 0],
                [reference_array[b + 1][a + 1], 1]
            ];
        }
    }
    
    for (let r, s, t, c, i = 0; i < configs.length; i++) {
        c = configs[i];
        
        r = -2;
        s = _ => (i.toString(3).padStart(2 * (6 * (size - 1) || 1), 0).substr(r += 2, 2)).split("").map(n => +n).concat(-1);
        
        for (let j = 0; j < size; j++) {
            c[j] = s();
        }
        
        t = size - 1;
        
        for (let j = 1; j < size; j++) {
            c[++t] = s();
            c[t += j + size - 1] = s();
        }
        
        for (let j = size - 2; j >= 1; j--) {
            c[++t] = s();
            c[t += j + size - 1] = s();
        }
        
        if (size > 1) {
            for (let j = 0; j < size; j++) {
                c[++t] = s();
            }
        }
    }
    
    // Validate each
    
    for (let c, i = 0; i < configs.length; i++) {
        c = configs[i];
        
        (_ => {
            while (c.find(h => h[0] == -1 || h[1] == -1 || h[2] == -1)) {
                for (let t, r, s, j = 0; j < vertexes.length; j++) {
                    t = vertex_map[j];
                    
                    if (t.filter(v => !(c[v[0]][v[1]] + 1)).length == 1) {
                        if ((s = vertexes[j] - t.reduce((a, v) => a + (c[v[0]][v[1]] + 1 || 1) - 1, 0)) < 0 || s > 2) {
                            return;
                        }
                        
                        r = t.find(v => !(c[v[0]][v[1]] + 1));
                        
                        c[r[0]][r[1]] = s;
                    }
                }
            }
            
            for (let j = 0; j < vertexes.length; j++) {
                if (vertex_map[j].reduce((a, v) => a + (c[v[0]][v[1]] + 1 || 1) - 1, 0) != vertexes[j])
                    return;
            }
            
            solutions.push(c);
        })();
    }

    if (solutions.length > 1)
        return "N";
    
    // Convert to output list format
    
    var solution = solutions[0];
    
    var result = [];
    
    for (let p = 0, a, i = 0; i < 2 * size - 1; i++) {
        a = 2 * size - 1 - Math.abs(size - i - 1);
        
        for (let j = 0; j < a; j++) {
            result.push(solution[p + j][0]);
        }
        
        for (let j = 0; j < a; j++) {
            result.push(solution[p][1], solution[p++][2]);
        }
    }
    
    return result;
};

This challenge would actually be really fun as : I think there are a lot of byte-expensive shortcuts that could really speed this up that I didn't have time to explore.

Thank you for a fun challenge.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Hey, thanks for answering the question! I haven't been on this site in forever, so seeing a bunch of notifs on other SE sites was a surprise! In hindsight, having this task as a code-golf wasn't ideal, and it would definitely be more fun to make this fastest-code, I'll try and think of something (maybe make my own solution) when I have the time. However, feel free to post any optimised versions of your code if you want! \$\endgroup\$
    – clismique
    Sep 26, 2020 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.