Comment on Find Cow

Treczoks@lemmy.world ⁨1⁩ ⁨day⁩ ago

• Snazz@lemmy.world ⁨1⁩ ⁨day⁩ ago

  What I would have done is started filling in letters randomly and every time a C or W ends up next to an O, choose the same letter or an O to put on the opposite side of the O.

  Its hard to prove, but I’m pretty sure there isn’t a situation where a space can’t be filled in with this algorithm.

  source

  • MatSeFi@lemmy.liebeleu.de ⁨1⁩ ⁨day⁩ ago

    Yes, this would work — but it comes with a subtle statistical bias: the character ‘W’ ends up underrepresented. With a naïve “avoid COW” approach, only about 25% of the grid will typically be ‘W’.

    A more elegant solution would be:

    • fill the grid completely at random
      • search for every “COW” cluster
        • whenever one is found, copy a random character from one cell in the cluster into another cell of the same cluster
      • Iterate until no “COW” remains

    That keeps the distribution much closer to uniform while still guaranteeing a valid puzzle. Then just insert the single “COW” manually wherever you want the hidden solution to be.

    Julia code example

    julia s= (320,180) #size m=rand([‘C’,‘O’,‘W’],s) #random init c=1 while c>0 #iterate till solved c=0 for i in 1:first(s) for j in 1:last(s) #check for ‘COW’ in each cluster of 3 and copy a character #from a rendom cell to an other random cell of the cluster if found if i>2 && m[i-2:i,j] ==[‘C’,‘O’,‘W’] #vertical c +=1 r =shuffle([1,2]) m[i-r[1],j] = m[i-r[2],j] end if j>2 && m[i,j-2:j] ==[‘C’,‘O’,‘W’] #horizontal c +=1 r =shuffle([0,1,2]) m[i,j-r[1]] = m[i,j-r[2]] end end end end

    The neat part is that this preserves an almost perfectly balanced character frequency.

    For comparison, the puzzle in the example image seems to contain roughly:

    C: ~260 (~25%) O: ~520 (~50%) W: ~244 (~25%)

    So the original author clearly used a different generation strategy.

    Possibly on purpose: visually, ‘C’ and ‘O’ are much easier to confuse than ‘W’. Reducing the number of 'W’s therefore increases the search difficulty. In that sense, the approach suggested by @Snazz@lemmy.world is probably preferable: keep the distribution mostly balanced, but intentionally bias it just enough to make the puzzle psychologically annoying.

    I wonder if there is a non iterative way to generate this puzzle with a ‘uniform’ character distribution 🤔

    source
• zorblitz@programming.dev ⁨1⁩ ⁨day⁩ ago

  Top of the page says find 1 cow, so yes

  source