Ein Zug überquert eine beschriftete Brücke

9

Stellen Sie sich eine Brücke der Länge B vor, die aus Kacheln besteht, die mit den Ziffern der verketteten positiven ganzen Zahlen gekennzeichnet sind. Wenn B beispielsweise 41 wäre, würde es so aussehen:

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

Stellen Sie sich nun einen Zug der Länge T vor , der die Brücke überquert. Der am weitesten links liegende Punkt des Zuges beginnt an Position X (1-indexiert). Um das Problem besser zu verstehen, erstellen wir ein Schema des Ereignisses mit B = 41, T = 10, X = 10 . Der Zug wird mit Gleichheitszeichen ( =) und Linien gezeichnet :

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

Der Zug kann bei jedem Schritt um die Summe der einzigartigen Kacheln vorrücken, auf denen er sich befindet. Zum Beispiel sind die Kacheln, auf denen der Zug oben steht, : [1, 0, 1, 1, 1, 2, 1, 3, 1, 4], die eindeutigen (deduplizierten) Kacheln: [1, 0, 2, 3, 4]und ihre Summe ist 10. Daher kann der Zug durch 10Kacheln vorrücken . Wir sollten es erneut zeichnen und den Vorgang wiederholen, bis der am weitesten links stehende Punkt des Zuges die letzte Kachel passiert hat:

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

Summe der einzigartigen Kacheln: 1 + 5 + 6 + 7 + 8 + 9 = 36. Der Zug rückt um 36 Kacheln vor ...

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

Der Zug überquerte offensichtlich die Brücke vollständig, also sollten wir jetzt anhalten.

Da sich die Leute im Haus langweilen, zählen sie jedes Mal die Kacheln, die der Zug vorgerückt hat. In diesem speziellen Fall 10und 36. Zusammenfassend hat sich der Zug bewegt, 46bevor er die Brücke passiert hat.


Aufgabe

Bei drei positiven ganzen Zahlen, B (die Brückenlänge), T (die Zuglänge) und X (die Startposition, 1-indiziert ), müssen Sie bestimmen, wie viele Kacheln der Zug bewegt hat, bis er die Brücke gemäß den Regeln überquert hat über.

  • Sie können davon ausgehen, dass:
    • B ist höher als T .
    • X niedriger als B .
    • T ist mindestens 2 .
    • Der Zug überquert schließlich die Brücke.
  • Es gelten alle unsere Standardregeln.
  • Dies ist , also gewinnt der kürzeste Code in Bytes!

Testfälle

Eingang ([B, T, X]) -> Ausgang

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

Ein weiteres Beispiel für den letzten Testfall:

Die Brücke hat die Länge 50, der Zug 6 und die Startposition ist 11.

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

Einzigartige Kacheln: [0, 1, 2]. Summe: 3.

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

Einzigartige Kacheln: [1, 2, 3, 4]. Summe: 10.

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

Einzigartige Kacheln: [1, 7, 8, 9]. Summe: 25.

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

Einzigartige Kacheln: [9, 3]. Summe: 12.
                                                            ______
                                                            | ==== |
                                                            | ==== |
--------------------------------------------------
12345678910111213141516171819202122232425262728293

Zug existiert die Brücke. Gesamtsumme: 3 + 10 + 25 + 12 = 50.
Mr. Xcoder
quelle
6
Können wir den Zug übernehmen nicht über die Brücke schließlich? Für Eingänge mögen (200, 2, 169), wird der Zug auf dem stecken 00in …9899100101102….
Lynn
@Lynn Ein bisschen spät, ja, du kannst.
Mr. Xcoder

Antworten:

3

Schale , 20 Bytes

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

Probieren Sie es online aus!

Nimmt drei Argumente , um T , B , X .

Erläuterung

ṁ←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
Löwe
quelle
6

Python 2 , 110 105 104 103 100 97 96 Bytes

  • Dank Mr. Xcoder wurden fünf Bytes gespeichert . unnötige Zuordnung entfernt, Negation in verfügbares Leerzeichen verschoben.
  • Dank Mr. Xcoder ein Byte gespeichert ; golfed [~-x:x+~-t]zu [~-x:][:t].
  • Ein Byte gespeichert; golfed ...range(1,-~b)))[:b]zu ...range(b)))[1:-~b].
  • Drei Bytes gespeichert; golfed [1:-~b][~-x:]zu [:-~b][x:].
  • Drei Bytes gespeichert; golfed [:-~b][x:]zu [x:-~b].
  • Dank Lynn ein Byte gespeichert ; Golf die whileSchleife zu einer execAussage.
b,t,x=input();S=x;exec"x+=sum(set(map(int,''.join(map(str,range(b)))[x:-~b][:t])));"*b;print-S+x

Probieren Sie es online aus!

Jonathan Frech
quelle
Eine alternative 105 Byte lange Lösung.
Jonathan Frech
104 Bytes . [~-x:x+~-t]kann ersetzt werden durch[x-1:][:t]
Mr. Xcoder
exec"x+=sum(set(map(int,''.join(map(str,range(b)))[x:-~b][:t])));"*barbeitet für 96. (Der Zug wird nie mehr als bSchritte unternehmen, um die Brücke zu verlassen, und dieser gesamte Vorgang wird sich immer wieder belaufen, x+=0sobald er verlassen ist.)
Lynn
4

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)

Probieren Sie es online aus!

(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
Nimi
quelle
3

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}

Implementiert nur den beschriebenen Algorithmus.

R ist ziemlich schrecklich in Saiten.

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
}

Probieren Sie es online aus!

Giuseppe
quelle
2

Gelee ,  22  21 Bytes

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

Ein vollständiges Programm mit drei Argumenten - die Reihenfolge ist B , X , T -, das das Ergebnis druckt.

Probieren Sie es online aus!

Wie?

ḣ⁵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
Jonathan Allan
quelle
1

JavaScript (ES6), 117 Byte

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

Ein Paar rekursiver Funktionen:

  1. f() summiert die Bewegungen des Zuges.
  2. g() erstellt die Zeichenfolge.

Weniger Golf:

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

Rick Hitchcock
quelle
0

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;

Probieren Sie es online aus!

Um es mit niedrigeren Versionen von PHP kompatibel zu machen, ändern Sie [,$p,$q,$r]=zu 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
Jo.
quelle