24
\$\begingroup\$

Bowling

Bowling is a game where, essentially, each player gets 10 turns to:

Take 2 attempts at knocking down 10 pins arranged in a triangle.

  • between turns the pins are reset
  • from the 1st to the 2nd attempt the pins are left as-is

The arrangement of the pins resembles the following scheme, with the pins numbered 0-9:

6 7 8 9
 3 4 5
  1 2
   0

(Some rules and scoring mechanics omitted.)

Split spare

In bowling, a spare is when the player manages to knock down the pins that were left standing after a first attempt. A spare is said to be a split spare1 if the pins that were left standing are not adjacent.

E.g. if the pins are laid out as such:

. . 8 9
 . . .
  . 2
   .

Then a player who manages to knock down all these 3 pins would score a split spare, given that the pin 2 is not adjacent to the 8, 9 group.

(1 for the purposes of this challenge, a split spare is defined taking into account only the adjacency of the pins left standing, even though Wikipedia's link states that for a split spare to take place, the pin 0 must have been knocked down already)

Your task

Given the numbers of the pins left standing, output a Truthy value if such an arrangement would give a split spare and Falsy otherwise.

Input

The list of all pins left standing (at least 2), in any reasonable format. Pin numbering may be 0- or 1-indexed provided it follows the numbering direction shown above. Sensible input formats include:

  • a list of integers, like [2, 8, 9]
  • a string of integers, like "289"
  • separate arguments to a function
  • an integer whose bits correspond to the pints left standing and whose least significant bit corresponds to pin 0, e.g. 0b1100000100 for pins 2, 8 and 9.

You may assume input is sorted, if that helps you in any way.

Output

A single consistent value for Falsy test cases and anything else for Truthy test cases.

Test cases

Truthy

[0, 9]
[2, 8, 9]
[1, 5, 8]
[3, 5]
[3, 8]
[3, 9]
[6, 8]
[6, 9]
[3, 5, 8, 9]
[5, 6]
[0, 1, 5, 6, 7, 9]
[1, 2, 8, 9]

Falsy

[1, 2]
[7, 8, 9]
[1, 2, 5]
[2, 4]
[0, 1, 3, 6]
[2, 5, 9]
[6, 7]
[4, 7]
[4, 8]
[1, 4, 5, 7]

Bonus imaginary internet points

Bonus imaginary internet points if your algorithm works for any triangle number of pins, instead of just 10.

So far, only Grimmy's 05AB1E answer qualifies for the bonus internet points!


Standard loopholes are forbidden by default.

This is so shortest solution wins! If you enjoy the challenge, consider upvoting it... And happy golfing!

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Can we assume at least 2 pins? \$\endgroup\$
    – G B
    Feb 11 '20 at 10:10
  • 1
    \$\begingroup\$ May we take the input as a single 10-bit integer? \$\endgroup\$
    – Arnauld
    Feb 11 '20 at 12:06
  • 1
    \$\begingroup\$ @Noodle9 yes, the pin 2 was misplaced. Yes, [1, 2, 8, 9] is a split spare and for the challenge, for a spare to be a split spare we only care about adjacency. We don't care about the headpin. \$\endgroup\$
    – RGS
    Feb 11 '20 at 14:08
  • 1
    \$\begingroup\$ @RGS My initial version was outputting either false (Boolean value) or 0 (integer) for the falsy output. I had to fix it to always output false. \$\endgroup\$
    – Arnauld
    Feb 11 '20 at 14:18
  • 5
    \$\begingroup\$ A shame we couldn't make it a code-bowling contest somehow! \$\endgroup\$
    – JDL
    Feb 11 '20 at 16:51
9
\$\begingroup\$

05AB1E, 27 25 24 23 bytes

ÅTαε.āθDƪ}©æε®yKδαOß}à

Try it online!

Outputs 2 for falsy and a larger integer for truthy. Works for any triangle number of pins, thus qualifying for the bonus internet points.

A set of pins is split if and only if there is a partition of the set of pins in two subsets A and B such that no pin in A is adjacent to a pin in B.

Adjacency is determined using 3-element hexagonal coordinates.

First, we convert the input pins to their hex coordinate triplets:

   ε      }     # for each pin in the input:
ÅT              #  list of triangle numbers <= pin
  α             #  absolute difference of each one with pin
    .ā          #  enumerate: [a, b, c] => [[a, 1], [b, 2], [c, 3]]
      θ         #  get the last pair
       D        #  duplicate
        Æ       #  reduce the copy by subtraction
         ª      #  append that to the pair

Then, we iterate over partitions of this set of triplets in two subsets:

©               # save the set in the register
 æ              # powerset (list of subsets)
  ε       }     # for each subset y:
   ®            #  push the set from the register
    y           #  push y
     K          #  set difference (=> y's complement)

Then, we compute the 2D list of distances between each pin in the first subset and each pin in the second subset. Thanks to the elegance of 3-element hexagonal coordinates, this is surprisingly easy:

      δα        #  double vectorized absolute difference
        O       #  sum each triplet

Finally, we answer the question:

         ß      #  minimum distance for the current partition
          }     #  end the loop
           à    # maximum of the list of minimums
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Good job on winning the bonus internet points! Can you explain how you did it? \$\endgroup\$
    – RGS
    Feb 11 '20 at 14:49
  • 2
    \$\begingroup\$ @RGS explanation added, also i golfed 3 more bytes. \$\endgroup\$
    – Grimmy
    Feb 11 '20 at 15:52
7
\$\begingroup\$

Ruby, 72... 74 bytes

->l{*r=l[0];l.map{r.map{|w|r|=l&"zê-ǓᔂYMŰɃc"[w].ord.digits}};l&r!=l}

Try it online!

What is that?

Starting from the first pin in the list, check if all pins can be reached within a finite number of steps.

The binary string "zê-ǓᔂYMŰɃc" is the UTF-8 encoding of the adjacency list [122,234,45,467,5378,89,77,368,579,99]. Some digits are repeated to make the numbers fit into the ASCII range and spare some bytes, some edges are omitted if the node can be reached through different paths.

Thanks Value Ink for smoothing out rough edges (-3 bytes).

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I have very high expectations for your corrected version :) \$\endgroup\$
    – RGS
    Feb 11 '20 at 17:12
  • \$\begingroup\$ The main optimization that comes to mind is *r=l[0]. Also, it seems you only need to take "steps" up to the number of pins remaining, so l.map{r.map{ works too (at least for the existing test cases) \$\endgroup\$
    – Value Ink
    Feb 11 '20 at 23:37
6
\$\begingroup\$

JavaScript (ES6),  87  83 bytes

Saved 4 bytes thanks to @Grimmy

Takes input as a 10-bit integer (LSB = pin \$0\$, MSB = pin \$9\$). Returns a non-zero integer for a split spare, or \$0\$ otherwise.

n=>(g=m=>[6,29,51,210,430,788,136,344,688].map((v,i)=>m|=m>>i&1&&n&v)|m)(g(n&-n))^n

Try it online!

How?

Starting with the lowest bit set in the input, we progressively expand a bitmask with the pin neighbors. We eventually compare the result with the input.

Because we expand from pin \$0\$ to pin \$9\$ (let's call them \$P_0\$ to \$P_9\$), a single pass would occasionally miss a connection. Fortunately, processing two passes is always enough for all possible paths, which is what this code is doing.

For instance, let's consider the following configuration:

6 - - -
 3 4 -
  - 2
   -

First pass

We start with \$P_2\$, which expands to \$P_4\$. Then, \$P_4\$ expands to \$P_3\$. The connection between \$P_3\$ and \$P_6\$ is missed because \$P_3\$ is not included in the bitmask at the time it's processed.

Second pass

Again, we start with \$P_2\$, which expands to \$P_4\$ (no change). Then, \$P_3\$ expands to \$P_4\$ (no change) and \$P_6\$, which completes the bitmask.

Improvement

As pointed out by @Grimmy, we never need to expand from \$P_9\$: when we reach it, its neighbors (\$P_5\$ and \$P_8\$) have necessarily been found already. Therefore, we can safely discard its neighbor bitmask and iterate only from \$P_0\$ to \$P_8\$.

Commented

n => (                // n = input bitmask
  g = m =>            // g is a recursive function taking a mask m
    [                 //   lookup table:
             6,       //     neighbors of pin 0
           29,51,     //     neighbors of pins 1, 2
        210,430,788,  //     neighbors of pins 3, 4, 5
      136,344,688     //     neighbors of pins 6, 7, 8
    ]                 //   
    .map((v, i) =>    //   for each value v at position i in the above array:
      m |=            //     update m:
        m >> i & 1 && //       if the i-th bit is set in m:
        n & v         //         m = m OR (n AND v)
    ) | m             //   end of map(); return the new value of m
)(                    // invoke g twice to support the longer paths,
  g(n & -n)           // starting with the lowest bit set in n
) ^ n                 // compare the result with n
\$\endgroup\$
3
  • \$\begingroup\$ +1 for the solution using bitwise operations \$\endgroup\$
    – RGS
    Feb 11 '20 at 14:24
  • \$\begingroup\$ You can drop ,288 from the array: if we start with bit 9, that means it's the only bit set, so it's neighbors are irrelevant; otherwise, we can only reach 9 through 5 or 8, and they are adjacent to each other, so we don't need 9 to make the connection. \$\endgroup\$
    – Grimmy
    Feb 12 '20 at 14:15
  • \$\begingroup\$ @Grimmy Very nice catch. :) (PS: the input is guaranteed to include at least 2 pins, so we don't even have to worry about the 'pin 9 alone' case.) \$\endgroup\$
    – Arnauld
    Feb 12 '20 at 14:39
2
\$\begingroup\$

Python 3.8 (pre-release), 106 121 bytes

Defines a function P.__contains__ that takes a set of pins and returns False for a split spare or True otherwise.

e.g. P.__contains__({"0", "9"}) returns False while P.__contains__({"0", "1"}) returns True

d="6310214374254859876"
P={*map(frozenset,zip(d,d[1:]))}
while P<(P:={a|b for a in P for b in P if a&b}):0
P.__contains__

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ +1 for a nice python solution :) \$\endgroup\$
    – RGS
    Feb 11 '20 at 20:13
  • \$\begingroup\$ Wouldn't P.__contains__ have to actually count towards you byte count? \$\endgroup\$
    – mypetlion
    Feb 12 '20 at 23:34
  • \$\begingroup\$ @mypetlion looked around meta a bit and the general consensus seems to be that it does count towards your byte count. Updated. \$\endgroup\$
    – Kyle G
    Feb 13 '20 at 14:41
2
\$\begingroup\$

C++ (gcc), 381 \$\cdots\$ 267 248 bytes

#import<set>
using S=std::set<long>;int f(S s){std::set<S>c;for(long b=0x5792628a5a065664;b>9;b/=10)c.insert({b%10,b/10%10});for(S i:c)for(S j:c){S q(i);q.insert(begin(j),end(j));if(q.size()<i.size()+j.size())c.insert(q);}return c.find(s)==end(c);}

Try it online!

Ungolfed

#include<set>
#include<algorithm>
using namespace std;
using S=set<int>;
bool f(S s) {
    // Change array a for any number or shape of pins,
    //  instead of just a triangle of 10.
    // It lists all the pins next to all their adjacent pins.
    int a[]{6,3,1,0,2,1,4,3,7,4,2,5,4,8,5,9,8,7,6};                                                                                                              
    set<S> c;
    for(int i=0;i<sizeof(a)/sizeof(int)-1;++i) 
        c.insert({a[i], a[i+1]});
    set<S> t;
    // Keep on adding connected sets of pins until there are no more new ones.
    while (t!=c) {
        for (auto i:c)
            for (auto j:c)
                if (any_of(begin(i),end(i),
                   [&](auto e){return j.find(e)!=end(j);}))
                {
                    S q(i);
                    q.insert(begin(j),end(j));
                    t.insert(q);
                }
        swap(t,c);
    }
    return c.find(s)==end(c);
}

Builds a set of all connected pin sets as per Kyle Gullion's idea and then simply tests for membership.

\$\endgroup\$
6
  • \$\begingroup\$ I'm having trouble with the TIO link, is it from my phone? \$\endgroup\$
    – RGS
    Feb 12 '20 at 9:23
  • \$\begingroup\$ Ah I see! +1 for your submission, even though you are currently losing :'( \$\endgroup\$
    – RGS
    Feb 12 '20 at 13:18
  • 1
    \$\begingroup\$ @RGS I'm still golfing it, you just wait and see! T_T \$\endgroup\$
    – Noodle9
    Feb 12 '20 at 13:40
  • 1
    \$\begingroup\$ @RGS Check it out now, runs fine on TIO with optimisation cranked! :-) \$\endgroup\$
    – Noodle9
    Feb 12 '20 at 17:01
  • \$\begingroup\$ Really cool! Thanks for the effort :D \$\endgroup\$
    – RGS
    Feb 12 '20 at 17:15
1
\$\begingroup\$

Charcoal, 47 bytes

UO⁸#Fθ«≔⌊⊘⊖₂⊕×⁸ιηJ⁺³⁻⊗ι×η⁺²η⊗ηUO²ψ»¤#≔›⁶⁴LKAη⎚η

Try it online! Link is to verbose version of code. Takes input as an array of integers and outputs a Charcoal boolean, - for a split spare, empty output otherwise. Explanation:

UO⁸#

Draw an 8-by-8 rectangle of #s.

Fθ«

Loop over the input pins.

≔⌊⊘⊖₂⊕×⁸ιη

Calculate the row of the pin.

J⁺³⁻⊗ι×η⁺²η⊗η

Jump to the position of the pin.

UO²ψ

Erase a 2-by-2 rectangle representing the pin.

»¤#

Fill with #s starting at the last pin.

≔›⁶⁴LKAη

See whether the fill restored all 64 #s.

⎚η

Clear the canvas and output the result.

Although I calculate the position of the pin directly (I tried a look-up table but it was the same byte count) this method won't handle arbitrary numbers of pins since it needs to be able to draw a large enough initial rectangle. However it can be adjusted to handle a specific maximum number of pins: the initial 8 needs to be increased by 2 for each additional row of pins, the 3 needs to be one less than the new number of rows of pins, and the 64 needs to be the square of the number that replaces 8.

\$\endgroup\$
3
  • \$\begingroup\$ Nice submission! You don't qualify for the bonus imaginary internet points, unfortunately :( \$\endgroup\$
    – RGS
    Feb 12 '20 at 6:59
  • 1
    \$\begingroup\$ @RGS Right, the bonus points aren't worth the extra byte count. \$\endgroup\$
    – Neil
    Feb 12 '20 at 10:03
  • \$\begingroup\$ No problem, the bonus points are just imaginary \$\endgroup\$
    – RGS
    Feb 12 '20 at 13:16
1
\$\begingroup\$

Excel (Ver. 1911), 142 Bytes

A1     'Input
B1:B10 3ÒƮ̔ŘʰĠ 'one character per row
       ^^^ (Non-printing characters)
C1     =ROW(B1:B10)-1
D1     =BITAND(INT(A1/2^C1#),1)*UNICODE(B1:B10)
E1     =SUM(MMULT(N(BITAND(2^C1#,TRANSPOSE(D1#))*D1#>0),N(C1#>=0)))+2<2*SUM(N(D1#>0)) 'Output

Here un-golfed using named ranges and extra columns

Input         'Input
Bit_List      3ÒƮ̔ŘʰĠ 'as a column of chars
Pin_Num       =SEQUENCE(ROWS(Bit_List))-1
Unicode       =UNICODE(Bit_List)
Pins_Left     =BITAND(INT(Input/2^Pin_Num),1)*Unicode
Pins_Adjacent =MMULT(SIGN(BITAND(2^Pin_Num,TRANSPOSE(Pins_Left))*Pins_Left),SIGN(Pin_Num+1))
Split         =SUM(Pins_Adjacent)<2*(SUM(SIGN(Pins_Left))-1)

Try it offline! (link to the workbook in a google drive)

You'll need to download and open in the latest version of excel for the formulas to work.

Single Test+Comments screenshot

Test+Comments

\$\endgroup\$
1
  • \$\begingroup\$ +1 incredible work on this! \$\endgroup\$
    – RGS
    Feb 14 '20 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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