9
\$\begingroup\$

Brief description of the game

In the game Otteretto Classic (which you can test directly in your browser; try it!) the player has to form palindromic sequences using adjacent cells on a square grid. Each cell has one of five possible colours, which we will denote by the letters \$\mathrm A, \ldots, \mathrm E\$.

The user creates a sequence by sliding the mouse or finger, joining cells one by one, and then releasing the mouse button or lifting the finger to end the sequence. Each time a cell is added, the game updates the score of the sequence that has been built so far. This is actually a partial score, because new cells may be added later. Also, those future cells must make the final sequence palindromic, but that condition cannot be evaluated at this point, so it is ignored when computing the current partial score of the sequence.

Interestingly, the tutorial of the game does not fully specify the scoring method. All it says (slightly rephrased here) is that

  • longer sequences are worth more points than shorter ones;
  • more complicated sequences are worth more points than simpler ones.

In addition, since future cells are unknown, we may add

  • the (partial) score can only depend on the previous and current cells.

The tutorial gives the following examples. For each sequence, all partial scores are indicated:

ABA    ->  1 4 9
AABAA  ->  1 2 6 12 15
CABAC  ->  1 4 9 16 25

The following images represent the sequence \$\mathrm A \mathrm B \mathrm A\$ being built in the actual game (with \$\mathrm A\$ corresponding to yellow and \$\mathrm B\$ to purple). The score is the number shown in the lower part of each image.

The scoring method

Based on the above examples and a few others, it appears that the game computes the score according to the rules described next. Note that these rules have only been inferred by me from observing the game, and therefore might not be correct; but in any case they are the applicable rules for the purpose of this challenge.

Let \$x\$ be a sequence of length \$n\$, formed by \$x[1], \ldots, x[n]\$, where each \$x[k]\$ takes one of the five possible values \$\mathrm A, \ldots, \mathrm E\$. For each \$k = 1,\ldots,n\$, let \$r[k]\$ be the number of times that a cell differs from the preceding one in the (prefix) subsequence \$x[1], \ldots, x[k]\$, considering the first cell as differing from the (non-existing) "preceding" one. For example, given the sequence \$\mathrm A \mathrm B \mathrm A \mathrm A \mathrm B \mathrm B \mathrm C \mathrm C\$,

x[k] =   A B A A A B B C C
  k  =   1 2 3 4 5 6 7 8 9
r[k] =   1 2 3 3 3 4 4 5 5

Equivalently, \$r[k]\$ can be seen as an integer label for each run of equal values.

With this definition, for any \$k = 1, \ldots, n\$ the \$k\$-th partial score \$S[k]\$ is obtained as:

  1. \$S[1] = 1\$.

  2. For \$k \geq 2\$: \$S[k] = S[k-1] + u[k]\$, where:

    a. \$u[k]\ = r[k]\$ if the current cell has the same value as the preceding one (\$x[k]=x[k-1]\$).

    b. \$u[k]\ = r[k] + k - 1\$ if the current cell has a different value from the preceding one (\$x[k] \neq x[k-1]\$).

Equivalently, each cell's contribution to the score is the label of the run it belongs to (\$r[k]\$), plus the \$0\$-based cell index (\$k-1\$) if the cell starts a new run.

Observe that this computation satisfies the stated features that the score increases if the sequence is "longer" or "more complicated", where "complicated" is defined by comparing each cell with the preceding one.

The challenge

Given a sequence \$x\$ of length \$n \geq 1\$, output its \$n\$ partial scores \$S[1], \ldots, S[k]\$.

Additional rules

  • The letters \$\mathrm A, \ldots, \mathrm E\$ can be replaced by other characters of your choice. The input can be a string, a list or array of characters or numbers, or any similar structure. There have to be \$5\$ distinct elements available to represent the original colours of the game.

  • As usual, programs or functions are allowed. Input and output means are flexible.

  • Code golf. Shortest answer in bytes wins.

Test cases

A             ->  1
ABA           ->  1 4 9
DDDD          ->  1 2 3 4
AABAA         ->  1 2 6 12 15
CABAC         ->  1 4 9 16 25
EBBBE         ->  1 4 6 8 15
DEBBBE        ->  1 4 9 12 15 24
CCAABBA       ->  1 2 6 8 15 18 28
AABCDEEA      ->  1 2 6 12 20 30 35 48
CCAAAAABB     ->  1 2 6 8 10 12 14 24 27
DCCAAAAABB    ->  1 4 6 12 15 18 21 24 36 40
EDEADDCEEBB   ->  1 4 9 16 25 30 42 56 63 80 88
BBCAADDAACBB  ->  1 2 6 12 15 24 28 40 45 60 77 84
BBAACDDCAABB  ->  1 2 6 8 15 24 28 40 54 60 77 84
\$\endgroup\$
3
  • \$\begingroup\$ It turns out that there is a simpler formula which I failed to notice; see Luis Felipe's answer \$\endgroup\$
    – Luis Mendo
    Commented Aug 23, 2023 at 10:12
  • \$\begingroup\$ Looks like the score can also be computed by (length)*(number of distinct runs of elements) \$\endgroup\$
    – Carmeister
    Commented Aug 23, 2023 at 16:27
  • \$\begingroup\$ @Carmeister Yes, that's what i was referring to in my previous comment (see the linked answer) \$\endgroup\$
    – Luis Mendo
    Commented Aug 23, 2023 at 16:36

11 Answers 11

7
\$\begingroup\$

JavaScript (ES6), 37 bytes

The method was first found by Luis felipe De jesus Munoz so make sure to upvote this answer as well!

Expects an array of characters.

a=>a.map(v=>(s+=a!==(a=v))*++i,i=s=0)

Try it online!

Commented

a =>              // a[] = input array, re-used to store the previous
                  //       character
a.map(v =>        // for each character v in a[]:
  ( s +=          //   increment s if ... 
    a !== (a = v) //   ... v is not equal to the previous character
  )               //   we have to use !== to make sure that the test always
                  //   gives true on the first iteration, even for the edge
                  //   case where a[] is a singleton
  * ++i,          //   increment i and multiply s by i
  i = s = 0       //   start with i = 0 and s = 0
)                 // end of map()
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Sometimes I think you invented JS.... amazing solution! \$\endgroup\$ Commented Aug 22, 2023 at 20:41
  • 1
    \$\begingroup\$ @LuisfelipeDejesusMunoz As far as I remember, the few languages I've designed are all statically typed. :-) \$\endgroup\$
    – Arnauld
    Commented Aug 22, 2023 at 21:06
5
\$\begingroup\$

JavaScript (Node.js), 47 bytes

Expects the input to be an array of characters


Basically, r[k]*k where k is the current length of array and r[k] the number of times that a cell differs from the preceding one.

(x,t=1)=>x.map((a,i)=>(t+=i&&a!=x[i-1])&&-~i*t)

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Very good insight! The formula was much simpler than what I found \$\endgroup\$
    – Luis Mendo
    Commented Aug 22, 2023 at 20:20
3
\$\begingroup\$

Nekomata, 7 bytes

pNᵉ#ĉ#*

Attempt This Online!

pNᵉ#ĉ#*
pN        For each nonempty prefix:
  ᵉ#        Length
      *     Times
    ĉ#      Number of runs of consecutive equal elements
\$\endgroup\$
2
  • \$\begingroup\$ Pardon; I can believe ĉ, but what encoding represents ᵉ as single-byte? \$\endgroup\$ Commented Aug 24, 2023 at 4:43
  • \$\begingroup\$ @KarlKnechtel Nekomata's custom encoding. \$\endgroup\$
    – alephalpha
    Commented Aug 24, 2023 at 5:34
3
\$\begingroup\$

J, 31 16 bytes

(#*1+1#.2~:/\])\

Try it online!

-15 by porting alephalpha's excellent idea!!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 18 bytes

IEθ×⊕κ⊕LΦ…θκ⁻λ§θ⊕μ

Try it online! Link is to verbose version of code. Explanation: Port of my Retina answer.

  θ                 Input string
 E                  Map over characters
     κ              Current index
    ⊕               Incremented
   ×                Multiplied by
          θ         Input string
         …          Truncated to
           κ        Current index
        Φ           Filtered where
             λ      Current character
            ⁻       Does not equal
               θ    Input string
              §     Indexed by
                 μ  Inner index
                ⊕   Incremented  
       L            Take the length
      ⊕             Incremented
I                   Cast to string
                    Implicitly print
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 7 bytes

ηεÔgyg*

Port of @alephalpha's Nekomata's answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Ô could alternatively be γ and yg could alternatively be N> or for the same byte-counts.

Explanation:

η        # Get the prefixes of the (implicit) input-string
 ε       # Map each prefix to:
  Ô      #  Connected uniquify the characters in the string
   g     #  Pop and push the length of this string
    yg   #  Also push the length of the prefix itself
      *  #  Multiply the two together
         # (after which this list of integers is output implicitly as result)

  γ      #  Split the string into equal adjacent groups of characters

    N>   #  Push the 0-based map-index, and increase it by 1

    }    # Close the map
     ā   # Push a list in the range [1,length] (without popping the list itself)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 43 bytes

->l{a=b=0;l.map{|x|(b+=(l!=l=x)?1:0)*a+=1}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Retina, 30 bytes

.(?<=(\2*(.))+)
$.($#1*$>:&*) 

Try it online! Link includes test cases. Explanation: Uses @Arnauld's @LuisfelipeDejesusMunoz's observation that the partial score is the product of the letter's index and the number of runs so far.

.(?<=(\2*(.))+)

For each letter, count the number of runs so far.

$.($#1*$>:&*) 

Replace it with the product of that with the letter's 1-based index.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I believe Luis' answer is based on the same observation and it predates mine. \$\endgroup\$
    – Arnauld
    Commented Aug 22, 2023 at 19:12
  • \$\begingroup\$ @Arnauld Fair enough, but I hadn't seen his edit yet. \$\endgroup\$
    – Neil
    Commented Aug 22, 2023 at 19:13
1
\$\begingroup\$

Jelly, 10 bytes

Ż⁻ƝµJ’×+ÄÄ

A monadic Link that accepts a list of characters*, and yields a list of the partial scores.

* or, indeed, non-zero numbers, or even lists.

Try it online! Or see the test-suite.

How?

Ż⁻ƝµJ’×+ÄÄ - Link: list of characters L  e.g. A  A  A  B  B  C  A  A
Ż          - prefix a zero                 0  A  A  A  B  B  C  A  A
  Ɲ        - for neighbouring pairs:
 ⁻         -   not equal?                     1  0  0  1  0  1  1  0
   µ       - start a new monadic chain - f(S=that)
    J      -   range of length                1  2  3  4  5  6  7  8
     ’     -   decrement                      0  1  2  3  4  5  6  7
      ×    -   multiply by {S}                0  0  0  3  0  5  6  0
        Ä  -   cumulative sums {S}            1  1  1  2  2  3  4  4
       +   -   add                            1  1  1  5  2  8 10  4
         Ä -   cumulative sums                1  2  3  8 10 18 28 32
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 162 bytes

lambda x,t=[7]:(lambda m:[*map(lambda i,a:(lambda m:t)(t.__setitem__(0,t[0]+(i and a!=(x[i-1]if i else 0))))and-~i*t[0],*zip(*enumerate(x)))])(t.__setitem__(0,1))

"Port" of Luis felipe De jesus Munoz's answer. Try its test cases. t=[7] can be replaced with any other one-digit number for no extra cost. Explanation / readable version in TIO header and my painful debugging helper below

_queue = [];function print(...args) {_queue.push([args[0], args.slice(1)])}function release(l) {args_ = [];isStart = true;for (let i of _queue) {args_.push((isStart?l:'')+(i[0][0]=='.'?i[0].slice(1):'\n'+i[0]));for (let j of i[1]) {args_.push(j)}isStart=false}console.log(...args_)}

f=(x,t=1)=>x.map((a,i)=>{
        print('inner',t,a,i)
        p = [ t+=(i&&a!=x[i-1]) , -~i*t ]
        ret = p[0] && p[1];
        print('.returning',t,a,i,p[0],p[1],ret)
return ret});(l=>{f(Array.from(l));release(l)})('DDDD')

Python 3.8 (pre-release), 131 bytes, non-reusable

lambda x,t=[1]:[*map(lambda i,a:(lambda m:t)(t.__setitem__(0,t[0]+(i and a!=(x[i-1]if i else 0))))and-~i*t[0],*zip(*enumerate(x)))]

Omits t.__setitem__(0,1). Test cases

\$\endgroup\$
1
  • \$\begingroup\$ Absolute pain to do, 0/10. Next time I'd rather check if it is "a legal atomic chess move?" (hint hint) || tbh I still don't get how Luis felipe De jesus Munoz's answer works \$\endgroup\$
    – W D
    Commented Aug 23, 2023 at 11:25
1
\$\begingroup\$

Python, 61 bytes

lambda l:len(list(__import__('itertools').groupby(l)))*len(l)

The standard library itertools.groupby, with one argument, produces a lazy iterator over consecutive runs in the input (which are encoded as a pair of the value and another lazy iterator over the run - it's much more useful with the second argument in general, but...). Converting to list explicitly is required to measure the length (i.e. how many such runs there are).

\$\endgroup\$

Your Answer

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

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