Meine "Keybore" langweilt mich! Helfen Sie mir, minimale Tastenanschläge zu finden

13

Dank an @ Agawa001 für die Beantwortung dieser Frage.

Erläuterung

Mein neuer "Keybore" hat nur 2 Buttons, nämlich +und -.

Die Nummer im Speicher beginnt bei 0.

Jedes aufeinanderfolgende Drücken von +oder -erhöht / erniedrigt den Speicher genau so oft, wie er nacheinander gedrückt wurde.

Wenn Sie also +viermal drücken , wird beim ersten Mal 1 hinzugefügt, beim zweiten Mal 2, beim dritten Mal 3 und beim vierten Mal 4, sodass Sie 10(zehn) erhalten.

Wenn Sie nun -dreimal drücken , wird beim ersten Mal 1, beim zweiten Mal 2 und beim dritten Mal 3 abgezogen, und Sie haben 4(vier).

TL; DR

Teilen Sie die Zeichenfolge bei jedem Zeichenwechsel durch + und -. Dann +addiert jede resultierende Folge von m Symbolen die m-te Dreieckszahl und jede Folge von n- Symbolen subtrahiert die n-te Dreieckszahl.

Begehbar

Nun, wenn Sie immer noch nicht verstehen, werde ich Ihnen zeigen, wie es +++--+--schafft 1.

Program   | Counter | Memory
----------------------------
          |  0      | 0
+         | +1      | 1
++        | +2      | 3
+++       | +3      | 6
+++-      | -1      | 5
+++--     | -2      | 3
+++--+    | +1      | 4
+++--+-   | -1      | 3
+++--+--  | -2      | 1

Aufgabe

  • Sie nehmen eine positive Ganzzahl als Eingabe, entweder als Funktionsargument oder von STDIN.
  • Anschließend geben Sie die Mindestanzahl von Tastenanschlägen aus, die zum Erstellen dieser Anzahl mit der oben beschriebenen Methode erforderlich sind.

Testfälle

Da das Umordnen der +oder --Läufe die gleiche Nummer ergibt, wird für jede solche Gruppe nur die lexikographisch früheste Sequenz aufgelistet.

Input | Output | Possible corresponding sequences
-------------------------------------------------
    4 |      5 | -+++-
    6 |      3 | +++
    9 |      5 | ++++-
   11 |      7 | +++-+++
   12 |      7 | +++++--, ++++-++
   19 |      8 | -++++++-
   39 |     12 | +++++++++---
   40 |     13 | +++++++++---+, ++++++++-+++-
   45 |      9 | +++++++++
   97 |     20 | ++++++++++++++--+---, +++++++++++++-++++--, ++++++++++++-++++++-
  361 |     34 | ++++++++++++++++++++++++++-+++-+++

Zusätzliche Ressourcen

Wertung

Das ist . Kürzeste Lösung in Bytes gewinnt.

Undichte Nonne
quelle
9
Heißt das ... du bist gelangweilt?
busukxuan
Ich denke, Sie sind jetzt mit 10 Testfällen (einschließlich meiner) in Ordnung.
Erik der Outgolfer
@ ΈρικΚωνσταντόπουλος Der 12-Testfall wurde mit einer geringfügigen Änderung hinzugefügt (da +++++--ist auch eine Alternative, aber ich habe entfernt, ++-++++da das äquivalent ist zu ++++-++). Ich habe noch einen weiteren Fall, den ich später hinzufügen möchte, falls jemand eine effiziente Lösung findet, wenn ich es schaffe, sie zu generieren.
Sp3000
@ Sp3000 wollte ich nicht ++-++++entfernen. Auch das war MEINE Bearbeitung, nicht DEINE.
Erik der Outgolfer
@ ΈρικΚωνσταντόπουλος Es wird nur 1 Lösung aus jedem Satz äquivalenter Lösungen aufgelistet. Ich dachte, dass die Testfälle unnötig lang wären, wenn alle minimalen Lösungen aufgelistet würden (es gibt 6 Lösungen für 40 und 17 Lösungen für 97). Ich entschuldige mich, wenn diese Absicht nicht klar war. Außerdem haben Sie +++++--(oder gleichwertig --+++++) gefehlt , weshalb ich das Bedürfnis verspürte, es überhaupt zu bearbeiten.
Sp3000

Antworten:

2

Python 2, 119 Bytes

def g(n,i=0,s=''):
 c=x=t=0
 for d in s:C=int(d)*2-1;t=(c==C)*t+1;c=C;x+=c*t
 return(x==n)*len(s)or g(n,i+1,bin(i)[3:])

Sehr langsamer Brute-Force-Ansatz. Die dritte Zeile berechnet die Punktzahl eines Strings x. Die anderen Zeilen durchlaufen alle möglichen binären Zeichenfolgen, bis eine gefunden wird, deren Punktzahl dem Argument entspricht.

@Leaky sparte drei Bytes!

Lynn
quelle
s/x==n and len/(x==n)*len/
Undichte Nonne
Es könnte einige Bytes einsparen, um es loszuwerden, sund einfach die wiederholte Division verwenden, wie def f(n): \n while n>0:print n%2;n/=2
folgt
2

Pyth, 25 Bytes

ffqyQ.as-Mc*RhdY2{s.pM./T

Probieren Sie es online aus.

Dies ist äußerst ineffizient, und der Arbeitsspeicher für wird knapp f(n) ≥ 11 nicht mehr genügendf(22) Auf meinem Laptop wird in etwa 10 Sekunden = 10 berechnet .

Erläuterung

  • Ab 1 durchlaufen Sie die Zahlen T. ( f)
    • Generiere alle Partitionen von T. ( ./T)
    • Generieren Sie alle Permutationen von diesen. ( .pM)
    • Reduzieren Sie die Liste. ( s)
    • Vereinheitlichen Sie die Liste. ( {) Dieser Schritt könnte entfernt werden, macht den Code jedoch viel schneller.
    • Filtern Sie die resultierenden Permutationen von Partitionen: ( f)
      • Multiplizieren Sie jede Nummer dder Partition ( *R) mit sich selbst plus eins ( hd). Dies ergibt die doppelte Zahl, die zum Ergebnis addiert / subtrahiert werden muss.
      • Hacken Sie die Liste auf Teile der Länge 2. ( c2)
      • Subtrahieren Sie eine beliebige zweite Zahl in diesen Teilen von der zweiten Zahl. ( -M)
      • Summiere die Ergebnisse. Dies ergibt die doppelte resultierende Anzahl, wenn die Partitionspermutation als Anzahl von Additionen, dann Subtraktionen usw. interpretiert wurde.
      • Nimm den absoluten Wert. ( .a) Wenn das Ergebnis negativ war, wird durch Vertauschen der Additionen und Subtraktionen das positive Ergebnis erzielt.
      • Überprüfen Sie, ob das Ergebnis der doppelten Eingabe entspricht. ( qyQ) In diesem Fall ist die Partitionspermutation korrekt, geben Sie sie zurück.
    • Wenn der Filter ein Ergebnis liefert, liegt eine Längenlösung vor T. Zurück und ausdrucken T.
PurkkaKoodari
quelle
2

MATL , 43 29 Bytes

E:"@TFEqZ^!"@Y'tQ**s]vGE=a?@.

Dies ist speicher- und zeitineffizient. Der Online-Compiler kann 45nur Eingaben verarbeiten .

Probieren Sie es online!

Hier ist eine modifizierte Version mit allen Testfällen bis zu40 (es dauert fast eine Minute im Online-Compiler).

Erläuterung

Dadurch werden alle möglichen Tastendrucksequenzen jeder Länge in aufsteigender Reihenfolge geprüft, bis eine gültige Sequenz gefunden wird.

E:       % Range [1 2 ... 2*N] where N is implicit input. The required sequence length is
         % less than 2*N, so this is enough
"        % For each
  @      %   Push current value: length of sequence
  TFEq   %   Push array [1 -1]
  Z^     %   Cartesian power. Gives all possible sequences of 1, -1 of that length
  !      %   Transpose. Each sequence is now a row
  "      %   For each sequence
    @    %     Push current sequence
    Y'   %     Run-length decoding: Pushes an array of values 1 and -1, and then an
         %     array of run-lengths
    tQ*  %     Duplicate, add 1, multiply. Gives twice the triangular number for each run
    *    %     Multiply element-wise by 1 or -1 to produce correct sign
    s    %     Sum of array. This is the number produced by the current sequence
  ]      %   End for
  v      %   Concatenate all numbers into an array
  GE=a   %   True if any of those numbers equals twice the input
  ?      %   If so
    @    %     Push current sequence length. This is the final result
    .    %     Break loop
         %   End if
         % End for
         % Implicit display
Luis Mendo
quelle
@ Sp3000 Ich habe auch einen hinzugefügt, daher werden als Referenz 4, 6, 9 und 19 die Testfälle in der angegebenen Reihenfolge aufgeführt.
Erik der Outgolfer
1

Python, 105 100 Bytes

Verwendet eine ineffiziente Breitensuche.

def k(n):
 m=t=l=0;h=[]
 while m-n:o=1-2*(t>0);(m,t,l),*h=h+[(m+t-o,t-o,l+1),(m+o,o,l+1)]
 return l
  • h ist eine Liste, die als Warteschlange verwendet wird
  • m ist der Wert der Sequenz am Anfang der Liste
  • t ist die letzte hinzugefügte Nummer m
  • l ist die Länge der Sequenz, die generiert wurde m
  • o ist +/- 1, das Vorzeichen ist entgegengesetzt zum Vorzeichen von t

Edit: Undichte Nonne rasiert fünf Bytes.

RootTwo
quelle
s/m,t,l,h=0,0,0,[]/m=t=l=0,h=[]/
Undichte Nonne
s/while m!=n/while m-n/
Undichte Nonne