9
\$\begingroup\$

Consider a bridge of length B formed by tiles labeled with the digits of the positive integers concatenated. For example, if B was 41, then it would look like this:

-----------------------------------------
12345678910111213141516171819202122232425

Now imagine a train of length T crossing the bridge. The leftmost point of the train starts at position X (1-indexed). To get a better understanding of the problem, let's make a scheme of the event, with B = 41, T = 10, X = 10. The train is drawn using equal signs (=) and lines:

         __________
         |========|
         |========|
-----------------------------------------
12345678910111213141516171819202122232425

The train can advance, at each step, by sum of the unique tiles it is located on. For example, the tiles the train stands on above are: [1, 0, 1, 1, 1, 2, 1, 3, 1, 4], the unique (deduplicated) tiles are: [1, 0, 2, 3, 4], and their sum is 10. Hence, the train can advance by 10 tiles. We should draw it again and repeat the process until the leftmost point of the train has passed the last tile:

                   __________
                   |========|
                   |========|
-----------------------------------------
12345678910111213141516171819202122232425

Sum of unique tiles: 1 + 5 + 6 + 7 + 8 + 9 = 36. The train advances by 36 tiles...

                                                       __________
                                                       |========|
                                                       |========|
-----------------------------------------
12345678910111213141516171819202122232425

The train obviously crossed the bridge completely, so we should stop now.

Since the people inside are bored, they count the tiles the train has advanced each time. In this specific case, 10 and 36. Summing everything up, the train has moved 46 before it passed the bridge.


Task

Given three positive integers, B (the bridge length), T (the train length) and X (the starting position, 1-indexed), your task is to determine how many tiles the train has moved until it crossed the bridge following the rules above.

  • You can assume that:
    • B is higher than T.
    • X is lower than B.
    • T is at least 2.
    • The train eventually crosses the bridge.
  • All our standard rules apply.
  • This is , so the shortest code in bytes wins!

Test cases

Input ([B, T, X]) -> Output

[41, 10, 10] -> 46
[40, 10, 10] -> 46
[30, 4, 16] -> 24
[50, 6, 11] -> 50

Another worked example for the last test case:

The bridge is of length 50, the train 6, and the starting position is 11.

          ______
          |====|
          |====|
--------------------------------------------------
12345678910111213141516171819202122232425262728293

Unique tiles: [0, 1, 2]. Sum: 3.

             ______
             |====|
             |====|
--------------------------------------------------
12345678910111213141516171819202122232425262728293

Unique tiles: [1, 2, 3, 4]. Sum: 10.

                       ______
                       |====|
                       |====|
--------------------------------------------------
12345678910111213141516171819202122232425262728293

Unique tiles: [1, 7, 8, 9]. Sum: 25.

                                                ______
                                                |====|
                                                |====|
--------------------------------------------------
12345678910111213141516171819202122232425262728293

Unique tiles: [9, 3]. Sum: 12.
                                                            ______
                                                            |====|
                                                            |====|
--------------------------------------------------
12345678910111213141516171819202122232425262728293

Train exists the bridge. Total sum: 3 + 10 + 25 + 12 = 50.
\$\endgroup\$
  • 6
    \$\begingroup\$ Can we assume the train does cross the bridge eventually? For inputs like (200, 2, 169), the train gets stuck on the 00 in …9899100101102…. \$\endgroup\$ – Lynn Oct 9 '17 at 22:47
  • \$\begingroup\$ @Lynn A little late, yes, you can. \$\endgroup\$ – Mr. Xcoder Oct 10 '17 at 4:16
3
\$\begingroup\$

Husk, 20 bytes

ṁ←U¡S↓←moΣuX_⁰↓Θ↑ṁdN

Try it online!

Takes three arguments in order T, B, X.

Explanation

ṁ←U¡S↓←moΣuX_⁰↓Θ↑ṁdN
                 ṁdN    Build the list of digits of natural numbers
              ↓Θ↑       Take the first B digits, add a 0 in front
                        then drop the first X digits
           X_⁰          Get all sublists of length T
       moΣu             Map the sum of unique values of each sublist

   ¡S↓←                 Repeatedly drop as many elements from the start of the list as the
                        first element of the list says;
                        keep all partial results in an infinite list.

  U                     Take elements until the first repeated one
                        (drops tail of infinite empty lists)

ṁ←                      Sum the first elements of each remaining sublist
\$\endgroup\$
6
\$\begingroup\$

Python 2, 110 105 104 103 100 97 96 bytes

  • Saved five bytes thanks to Mr. Xcoder; removed unnecessary assignment, moved negation into available whitespace.
  • Saved a byte thanks to Mr. Xcoder; golfed [~-x:x+~-t] to [~-x:][:t].
  • Saved a byte; golfed ...range(1,-~b)))[:b] to ...range(b)))[1:-~b].
  • Saved three bytes; golfed [1:-~b][~-x:] to [:-~b][x:].
  • Saved three bytes; golfed [:-~b][x:] to [x:-~b].
  • Saved a byte thanks to Lynn; golfing the while loop to an exec statement.
b,t,x=input();S=x;exec"x+=sum(set(map(int,''.join(map(str,range(b)))[x:-~b][:t])));"*b;print-S+x

Try it online!

\$\endgroup\$
  • \$\begingroup\$ An alternative 105 bytes long solution. \$\endgroup\$ – Jonathan Frech Oct 9 '17 at 20:15
  • \$\begingroup\$ 104 bytes. [~-x:x+~-t] can be replaced by [x-1:][:t] \$\endgroup\$ – Mr. Xcoder Oct 9 '17 at 20:16
  • \$\begingroup\$ exec"x+=sum(set(map(int,''.join(map(str,range(b)))[x:-~b][:t])));"*b works for 96. (The train will never take more than b steps to leave the bridge, and that whole operation will amount to x+=0 over and over once it’s left.) \$\endgroup\$ – Lynn Oct 9 '17 at 22:35
4
\$\begingroup\$

Haskell, 106 102 bytes

import Data.List
(b#t)x|x>b=0|y<-sum[read[c]|c<-nub$take t$drop(x-1)$take b$show=<<[1..]]=y+(b#t)(x+y)

Try it online!

(b#t)x
   |x>b=0                 -- if the train has left the bridge, return 0
   |y<-sum[   ]           -- else let y be the sum of
      read[c]|c<-         -- the digits c where c comes from
        nub               -- the uniquified list of
            show=<<[1..]] -- starting with the digits of all integers concatenated
          take b          -- taking b digits (length of bridge)
         drop(x-1)        -- dropping the part before the train
        take t            -- take the digits under the train
     =y+(b#t)(x+y)        -- return y plus a recursive call with the train advanced
\$\endgroup\$
3
\$\begingroup\$

R, 123 bytes

function(B,T,X){s=substring
while(X<B){F=F+(S=sum(unique(strtoi(s(s(paste(1:B,collapse=''),1,B),K<-X+1:T-1,K)))))
X=X+S}
F}

Just implements the described algorithm.

R is quite terrible at strings.

function(B,T,X){
 s <- substring                         # alias
 b <- s(paste(1:B,collapse=''),1,B)     # bridge characters
 while(X<B){                            # until we crossed the bridge
  K <- X+1:T-1                          # indices of the characters
  S <- s(b,K,K)                         # the characters from b
  S <- sum(unique(strtoi(S)))           # sum
  F <- F + S                            # F defaults to 0 at the beginning
  X <- X + S                            # advance the train
 }
 F                                      # number of steps, returned
}

Try it online!

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

Jelly,  22  21 bytes

ḣ⁵QS
RDẎḣ⁸ṫṫÇ‘$$ÐĿÇ€S

A full program taking three arguments - the order is B, X, T - which prints the result.

Try it online!

How?

ḣ⁵QS - Link 1, calculate next jump: list of digits, bridge under and beyond train's left
 ⁵   - program's fifth command line argument (3rd input) = T (train length)
ḣ    - head to index (get the digits of the tiles under the train)
  Q  - de-duplicate
   S - sum

RDẎḣ⁸ṫṫÇ‘$$ÐĿÇ€S - Main link: number, B (bridge length); number, X (starting position)
R                - range(B) = [1,2,3,...,B-1,B]
 D               - to decimal list (vectorises) = [[1],[2],[3],...,[digits of B-1],[digits of B]]
  Ẏ              - tighten (flatten by one) = [1,2,3,...,digits of B-1,digits of B]
    ⁸            - chain's left argument, B
   ḣ             - head to index (truncate to only the bridge's digits)
     ṫ           - tail from index (implicit X) (truncate from the train's left)
           ÐĿ    - loop, collecting results, until no more change occurs:
          $      -   last two links as a monad:
         $       -     last two links as a monad:
       Ç         -       call last link (1) as a monad (get next jump)
        ‘        -       increment
      ṫ          -     tail from that index (remove the track to the left after train jumps)
             Ç€  - call last link (1) as a monad for €ach (gets the jump sizes taken again)
               S - sum
                 - implicit print
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 117 bytes

f=(B,T,X,g=b=>b?g(b-1)+b:'',o=0)=>X<B?[...g(B).substr(X-1,T)].map((e,i,a)=>o+=i+X>B|a[-e]?0:a[-e]=+e)&&o+f(B,T,X+o):0

A pair of recursive functions:

  1. f() sums the train's moves.
  2. g() creates the string of numbers.

Less golfed:

f=
(B,T,X,
 g=b=>b?g(b-1)+b:'',                       //creates the string of numbers
 o=0                                       //sum of tiles the train sits on
)=>
  X<B?                                     //if we're not past the bridge:
      [...g(B).substr(X - 1,T)].map(       //  grab the tiles we're sitting on
        (e,i,a)=>o += i + X > B |          //  if we've passed the bridge,
                      a[-e] ? 0 :          //  ... or we've seen this tile before, add 0 to o
                              a[-e] = +e   //  else store this tile and add its value to o
      ) &&
      o + f(B,T,X+o) :                     //recurse
  0

f=(B,T,X,g=b=>b?g(b-1)+b:'',o=0)=>X<B?[...g(B).substr(X-1,T)].map((e,i,a)=>o+=i+X>B|a[-e]?0:a[-e]=+e)&&o+f(B,T,X+o):0

console.log(f(41, 10, 10));  //46
console.log(f(40, 10, 10));  //46
console.log(f(30, 4, 16));   //24
console.log(f(50, 6, 11));   //50

\$\endgroup\$
0
\$\begingroup\$

PHP >= 7.1, 153 bytes

<?$s=substr;[,$p,$q,$r]=$argv;while($i<$p)$a.=++$i;$a=$s($a,0,$p);;while($r<$p){$x+=$n=array_sum(array_unique(str_split($s($a,$r-1,$q))));$r+=$n;}echo$x;

Try it online!

To make it compatible with lower versions of PHP, change [,$p,$q,$r]= to list(,$p,$q,$r)= (+4 bytes).

<?
[,$bridgelen,$trainlen,$position] = $argv;                  // grab input
while($i<$bridgelen)                                        // until the bridge is long enough...
  $bridgestr .= ++$i;                                       // add to the bridge
$bridgestr = substr($bridgestr,0,$bridgelen);               // cut the bridge down to size (if it splits mid-number)
while($position<$bridgelen){                                // while we are still on the bridge...
  $currtiles =                                              // set current tiles crossed to the...
    array_sum(                                              // sum of tiles...
      array_unique(                                         // uniquely...
        str_split(substr($bridgestr,$position-1,$trainlen)) // under the train
      )
    )
  ;
  $totaltiles += $currtiles;                                // increment total tiles crossed
  $position += $currtiles;                                  // set new position
}
echo $totaltiles;                                           // echo total tiles crossed
\$\endgroup\$

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.