10
\$\begingroup\$

Given a string s consisting of characters a-z lowercase, generate 5 arrays a1, a2, a3, a4, and a5 of size n (length of s) where the i-th element of each array represents the index of the next occurrence of the i-th character in s, with the following conditions:

  • If no such occurrence exists, set the value to n (0-based indexing) or n+1 (1-based indexing) depending on the indexing convention you use.
  • a1 represents the 1st next occurrence of the character, a2 represents the 2nd next occurrence, a3 represents the 4th next occurrence, a4 represents the 8th next occurrence, and a5 represents the 16th next occurrence.

This is a code golf challenge, so the shortest code in bytes wins.

Here are some test cases. They all use 0-based indexing.

Input: aakakakakka
Output:

1 3 4 5 6 7 8 10 9 11 11
3 5 6 7 8 10 9 11 11 11 11
7 10 9 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11

Input: sydgdtsfixuvhdgisifdyovjcgs
Output:

6 20 4 14 13 27 16 18 15 27 27 22 27 19 25 17 26 27 27 27 27 27 27 27 27 27 27
16 27 13 25 19 27 26 27 17 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27
27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27

Input: qmorzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
Output:

59 59 59 59 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
59 59 59 59 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59
59 59 59 59 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59
59 59 59 59 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59 59 59 59 59
59 59 59 59 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Can we output the list transposed, so N lists of length 5 instead of 5 lists of length N? \$\endgroup\$
    – mousetail
    Commented Mar 21, 2023 at 8:24

10 Answers 10

4
\$\begingroup\$

BQN, 18 bytesSBCS

-∘≠↑¨<⊒¨⍷⊸∾⍟(2⋆↕5)

Run online!

The Progressive Index of does the heavy lifting here.

...⍟(2⋆↕5) 1, 2, 4, 8 and 16 times:
⍷⊸∾ prepend the unique characters to the string.

<⊒¨ For each of the resulting strings find the progressive indices of the characters in the input string. progressive means that each index can only be used once. The length of the input is used as a not found value.
-∘≠↑ From each resulting integer list, take as many values from the back as there are characters in the input.

\$\endgroup\$
3
\$\begingroup\$

Excel, 111 109 bytes

With thanks to JvdV for the 2-byte save.

=LET(
    b,LEN(A1),
    c,SEQUENCE(b),
    d,MID(A1,c,1),
    IFERROR(FIND(0,SUBSTITUTE(MID(A1,c+1,b),d,0,{1,2,4,8,16}))+c-1,b)
)

0-based. Input in cell A1. Generates an n-row-by-5-column array, where n is the length of the input string.

\$\endgroup\$
2
  • \$\begingroup\$ Good thinking! I get 109, not 108, though. \$\endgroup\$ Commented Mar 22, 2023 at 9:13
  • \$\begingroup\$ Yeah my bad. Typo =) \$\endgroup\$
    – JvdV
    Commented Mar 22, 2023 at 9:17
2
\$\begingroup\$

J, 35 bytes

(2^i.5){0|:i.@#+(#,~^:16[:I.{.=])\.

Try it online!

  • (…)\.: Apply the verb inside to each suffix of the string, in order of start point.
    • {. = ]: Check for equality (=) between the first element ({.) and the whole suffix (], identity function). This produces a list of Booleans.
    • ([: to use monadically.) I. produces a list of indices of the 1s.
    • #, ~ ^: 16: Take the length of the suffix (#) and append (, with ~ to reverse operands) it to the list, repeating 16 times (^: 16).
  • i. @ #+: Add (+) [0,1,2,3,…] (# gives the length of the string, and i. produces that many numbers). This adjusts the numbers from indices in the suffixes to indices in the whole string.
  • 0 |:: Transpose.
  • (2^i.5){: Take the rows at indices 1, 2, 4, 8, 16.
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 93 bytes

Expects an array of characters. Returns an array of 5 arrays of integers, using 0-based indexing.

f=(s,k=5)=>k--?[...f(s,k),s.map(g=(c,i,q)=>!s[i]|q>>k?i:g(c,[...s,c].indexOf(c,i+1),-~q))]:[]

Try it online!

Commented

f = (               // f is a recursive function taking:
  s,                //   s[] = input string, as an array of characters
  k = 5             //   k = counter, initialized to 5
) =>                //
k-- ?               // decrement k; if it was not 0: 
  [ ...f(s, k),     //   append the result of a recursive call
    s.map(          //   for each entry in s[],
    g = (           //   using a recursive callback function g taking:
      c,            //     c = current character
      i,            //     i = current position
      q             //     q = iteration counter, initially zero'ish
    ) =>            //
      !s[i] |       //     if s[i] is undefined
      q >> k ?      //     or we've done 2 ** k iterations:
        i           //       stop and return i
      :             //     else:
        g(          //       do a recursive call:
          c,        //         pass c unchanged
          [...s, c] //         append c to a copy of s[]
          .indexOf( //         and look in there for the position of
            c,      //         the next occurrence of c
            i + 1   //         starting the search at i + 1
          ),        //
          -~q       //         increment q
        )           //       end of recursive call
    )               //   end of map()
  ]                 //
:                   // else:
  []                //   stop
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 23 bytes

IE⁵Eθ§⁺Φ⌕Aθλ›νμEφLθ⊖X²ι

Try it online! Link is to verbose version of code. 0-indexed. Outputs each index on its own line with each set of indices double-spaced from each other. Explanation:

  ⁵                     Literal integer `5`
 E                      Map over implicit range
    θ                   Input string
   E                    Map over characters
        ⌕A              Find all occurrences of
           λ            Current character in
          θ             Input string
       Φ                Filtered where
             ν          Occurrence index
            ›           Is greater than
              μ         Current index
      ⁺                 Concatenated with
                φ       Predefined variable `1000`
               E        Map over implicit range
                  θ     Input string
                 L      Length
     §                  Indexed by
                     ²  Literal integer `2`
                    X   Raised to power
                      ι Outer value
                   ⊖    Decremented
I                       Cast to string
                        Implicitly print
\$\endgroup\$
2
  • \$\begingroup\$ I'm sorry but you misread the problem statement \$\endgroup\$ Commented Mar 21, 2023 at 10:30
  • 1
    \$\begingroup\$ @HuỳnhTrầnKhanh Sorry I'm always doing that. Should be fixed now. \$\endgroup\$
    – Neil
    Commented Mar 21, 2023 at 11:27
1
\$\begingroup\$

Python NumPy, 92 bytes

lambda*s:clip(N:=len(s),0,x:=a(17*s,0,"s"))[2**c_[:5]+a(x)[:N]]
from numpy import*
a=argsort

Attempt This Online!

Expects the splatted input string and returns a 2D array of integers.

How?

Repeat the input to make sure at least 16 excess copies of every letter are available. Do an indirect sort, i.e. a sort we can take back by applying the inverse permutation. Apply the sort, shift by 1,2,4,8 or 16 and unsort. Clip to range.

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

Pyth, 24 bytes

[email protected]+fgTkxbcz1mlzGz^2d5

Try it online!

Explanation

                            # implicitly assign z = input()
   .e              z        # enumerated map b, k over z, indices
          xbcz1             #   get all indices of b in z
      f                     #   filter this on lambda T
       gTk                  #     T >= k
     +         mlzG         #   pad with 26 copies of len(z)
  C                         # transpose
m                      5    # map d over [0-4]
 @                          #   the element at the index
                    ^2d     #   2 ^ d
\$\endgroup\$
1
\$\begingroup\$

Haskell, 90 bytes

f s=[[([n|(n,x)<-z,x==c,i<=n]++l)!!(2^j)|(i,c)<-z]|let l=length s:l;z=zip[0..]s,j<-[0..4]]

It's got a perfectly natural typing, and uses 0-indexing as is normal for Haskell.

f :: String -> [[Int]]

try it online, with tests

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

Octave/MATLAB, 174 bytes

Modified from @loopy walt's answer

Golfed version, try it online!

function x=f(varargin),s=double(cell2mat(varargin));N=numel(s);[~,x]=sort(repmat(s,1,17));[~,i]=sort(x);f_i=bsxfun(@plus,i(1:N)-1,(2.^(0:4)).');x=min(max(x-1,0),N)(f_i+1);end

Ungolfed version:

function x = f(varargin)
    s = cell2mat(varargin);
    s = double(s);
    N = length(s);
    s17 = repmat(s,1,17);
    [~, x] = sort(s17);
    x=x-1;
    index_part1 = power(2, 0:4).';
    [~, index_part2 ]= sort(x);
    index_part2 = index_part2(1:N)-1;
    clipped = min(max(x, 0), N);
    sum_matrix = bsxfun(@plus, index_part2, index_part1);
    final_index = sum_matrix;
    x = clipped(final_index+1);
end

disp(f("aakakakakka"))
disp(f("sydgdtsfixuvhdgisifdyovjcgs"))
disp(f("qmorzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"))
\$\endgroup\$
0
\$\begingroup\$

Arturo, 92 bytes

$[s][map 0..4'x[i:0map s'c['i+1(char? select.with:'j.n:2^x drop s i'm->c=m)?->j+i->size s]]]

Try it

\$\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.