Zeichen rekursiv verdoppeln und "zählen"

Ich glaube, diese Aufgabe ist mit einer kontextfreien Sprache nicht lösbar, oder anders: Diese Aufgabe ist ohne eine Typ-1 oder Typ-0 Sprache (nach der Chomsky-Hierarchie) nicht lösbar.

Beispiel

Ich kann (ohne Weiteres) einen Algorithmus für einen NPDA angeben, der

"abbbc", 'b' -> abbbbbbc111
"ccabc", 'c' -> ccccabcc111
"abc", ' ' -> abc

erzeugt (oder genügt), jedoch keinen, der zusätzlich die 1en ohne ein vorstehendes Trennzeichen zählt bzw. zusammenfasst.

Beiweis

Eine Typ-2 ist nicht abgeschlossen über dem Komplement.

Um 111... (eine Folge von 1 oder beliebig vielen 1en hintereinander) zu "extrahieren", muss ich aber das Komplement bilden. Das ist allerdings durch die Aufgabenstellung (1... darf in der Eingabe auch vorkommen) nicht erlaubt.

(Dieser Beweis ist hoffentlich richtig...)

Das sollte eigentlich auch mit dieser Antwort übereinstimmen: https://stackoverflow.com/a/14207715

In short, context-sensitive languages look a lot like context-free languages but the elements of a context-sensitive languages may be interpreted in different ways depending on the program state.

Das: Wie interpretiere ich die 1en, die überall vorkommen können, ohne dabei einen Kontext (program state) zu haben?, geht eben aus meiner Sicht nicht.

Edit:
... Und dann sind wir auch schnell bei https://en.wikipedia.org/wiki/State_(computer_science)#Program_state und https://en.wikipedia.org/wiki/Purely_functional_programming vs. Impure functional programming.

Vereinfacht: Mit reiner funktionalen Programmierung nicht lösbar.

Wahrscheinlich alles Quatsch, was ich gesagt habe...

Ich habe hier eine Variante, die bis zu n=1 000 funktioniert.

(in Java aber... bitte nicht steinigen):

public class Verdoppeln {
    public static String verdoppeln(final String s, final char c) {
        if (s.length() > 0) {
            if (c == s.charAt(0)) {
                int len1 = s.length();
                String s1 = "" + c + c + verdoppeln(s.substring(1), c);
                int len2 = s1.length();
                int lenDiff = len2 - len1;
                int log3 = (int) Math.ceil(Math.log10(lenDiff - Math.log(lenDiff + 1) + 1));
                if (log3 > 0) {
                    int n = Integer.parseInt(s1.substring(s1.length() - log3));
                    return s1.substring(0, s1.length() - log3) + (n + 1);
                }
                return s1;
            }
            return "" + s.charAt(0) + verdoppeln(s.substring(1), c);
        }
        return "0";
    }

    public static void main(final String[] args) {
        System.out.println(verdoppeln("abc", ' '));
        System.out.println(verdoppeln("abc", 'a'));
        System.out.println(verdoppeln("abc", 'b'));
        System.out.println(verdoppeln("abc", 'c'));
        System.out.println(verdoppeln("abaac", 'a'));
        System.out.println(verdoppeln("abbbc", 'b'));
        System.out.println(verdoppeln("ccabc", 'c'));
        System.out.println(verdoppeln("abaaaaaaaac", 'a'));
        System.out.println(verdoppeln("abaaaaaaaaac", 'a'));
        System.out.println(verdoppeln("abaaaaaaaaacabaaaaaaaaacabaaaaaaaaacabaaaaaaaaacaa", 'a'));
        String s = "";
        for (int i = 0; i < 99; i++) {
            s += "a";
        }
        System.out.println(verdoppeln(s, 'a'));
        System.out.println(verdoppeln(s + "a", 'a'));
        System.out.println(verdoppeln(s + "aa", 'a'));
        System.out.println(verdoppeln(s + "aaa", 'a'));
        s = "";
        for (int i = 0; i < 999; i++) {
            s += "a";
        }
        System.out.println(verdoppeln(s, 'a'));
        System.out.println(verdoppeln(s + "a", 'a'));
        System.out.println(verdoppeln(s + "aa", 'a')); // -> Wrong output
        s = "";
        for (int i = 0; i < 10_000; i++) {
            s += "a";
        }
        System.out.println(verdoppeln(s, 'a')); // -> StackOverflowError
    }
}

Für 1001 Verdopplungen kommt ein falscher Wert heraus, und für 10 000 ein Overflow.

Schlangenmensch

Ich habe keine Ahnung woher du solche Sachen hast (wenn du die Sachen dir nicht ausgedacht hast, wären Quellen nett).

Ist mit einer statischen Variable wahrscheinlich nicht ganz, wie gedacht und ich habe mir nicht viel Mühe gegeben alles zu testen, aber auf den ersten Blick scheint es zu funktionieren,.

std::string verdoppeln(const std::string& s, char c)
{
  static int count = 0;
  std::string res{};
  if(s.length() > 0)
  {
    if(s.length() == 1)
    {
      if (s[0] == c)
      {
        ++count;
        res = res + c + c + std::to_string(count);
      }
      else
      {
        res = res + s + std::to_string(count);
      }
      count = 0;
    }
    else if (s.front() != c)
    {
      res = res + s.front() + verdoppeln(s.substr(1, s.length()), c);
    }
    else
    {
      ++count;
      res = res + c + c + verdoppeln(s.substr(1, s.length()), c);
    }
  }
  return res;
}

P.S: Das man ab einer gewissen Rekursionstiefe in einen Overflow läuft, ist normal.

Danke für die Antwort.

In C(++) ist static erlaubt, in Java nicht...

In diesem Fall brauche ich aber einmal so viele rekursive Calls...

Ich habe herausgefunden, dass die Berechnung:

@NoIDE sagte in Zeichen rekursiv verdoppeln und "zählen":

(int) Math.ceil(Math.log10(lenDiff - Math.log(lenDiff + 1) + 1));

falsch ist.

Ich müsste floor(x*2+log_10(x)+1) für x lösen, was eine Herausforderung darstellt, siehe hier: https://www.wolframalpha.com/input?i=solve+floor(x*2%2Blog_10(x)%2B1)+for+x

Mein Mathe-Skills sind nicht so gut, um das umzusetzen. Hättest du eine Idee?

Vereinfacht gesagt, kann ich dann über die String-Längendifferenz bestimmen, wie oft verdoppelt wurde.

Schlangenmensch

Um ehrlich zu sein, verstehe ich nicht, was du wie berechnen willst, wie du auf den Term kommst und nach was du das auflösen möchtest.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Ich habe keine Ahnung woher du solche Sachen hast (wenn du die Sachen dir nicht ausgedacht hast, wären Quellen nett)

Die Frage wurde in dem anderen Forum von thomas_tom gestellt, aber ich habe sie leicht abgewandelt.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Um ehrlich zu sein, verstehe ich nicht, was du wie berechnen willst, wie du auf den Term kommst und nach was du das auflösen möchtest.

Verstehe ich im Moment auch nicht mehr, werde morgen nochmal schauen.

So, ich habe eine "allgemeine"/"generalisierte" Lösung gefunden.

import java.util.HashMap;

public class Doubly {
    public static String doubly(final String s, final char c) {
        if (s.length() > 0) {
            if (s.charAt(0) == c) {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(2, 1);
                for (int j = 1; j <= 4; j++) {
                    int n0 = (int) Math.pow(10, j - 1);
                    int n1 = (int) Math.pow(10, j);
                    int i = n0;
                    for (; i < n0 + j; i++) {
                        int x = ((int) (i * 2 + Math.log10(i)) + 3 - j) / 2;
                        if (!map.containsKey(x)) {
                            map.put(x, j - 1);
                        }
                    }
                    for (; i < n1; i++) {
                        int x = ((int) (i * 2 + Math.log10(i)) + 3 - j) / 2;
                        if (!map.containsKey(x)) {
                            map.put(x, j);
                        }
                    }
                }
                //System.out.println("map = " + map);

                int len1 = s.length();
                String s1 = "" + c + c + doubly(s.substring(1), c);
                int len2 = s1.length();
                int lenDiff = len2 - len1;
                if (lenDiff > 0) {
                    int x = map.get(lenDiff);
                    //System.out.println(lenDiff + " " + x);
                    int n = Integer.parseInt(s1.substring(s1.length() - x));
                    return s1.substring(0, s1.length() - x) + (n + 1);
                }
                return s1;
            }
            return "" + s.charAt(0) + doubly(s.substring(1), c);
        }
        return "0";
    }

    public static void main(final String[] args) {
        String s = "0cac1c";
        for (int i = 2; i <= 1010; i++) {
            s += "a";
            String s2 = doubly(s, 'a');
            System.out.println("Expected: " + i + ", actual: " + s2.substring(s2.length() - (int) Math.log10(i) - 1));
            if (!String.valueOf(i).equals(s2.substring(s2.length() - (int) Math.log10(i) - 1))) {
                System.out.println("ERROR");
                return;
            }
        }
    }
}

Meine Frage wäre ... Wie man, anstatt eine HashMap zu verwenden, Zeile 7 bis 26 in eine geschlossene Formel umwandeln könnte...

Aber erst mal kann ich beruhigt schlafen.

Schlangenmensch

@NoIDE sagte in Zeichen rekursiv verdoppeln und "zählen":

durch Rekursion, nicht durch Schleifen

und, wie passt deine Lösung zu deinen eigenen Anforderungen? Wenn du Schleifen zulässt kannst du gleich am Schluss die Anzahl an chars c zählen und durch 2 teilen.
Davon abgesehen, sieht das: for (int j = 1; j <= 4; j++) nicht nach einer "allgemeinen"/"generalisierten" Lösung aus.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

und, wie passt deine Lösung zu deinen eigenen Anforderungen?

Das "Verdoppeln" soll nicht durch Schleifen geschehen... Zudem ist die map quasi nur eine Hilfsvariable...

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Davon abgesehen, sieht das: for (int j = 1; j <= 4; j++) nicht nach einer "allgemeinen"/"generalisierten" Lösung aus.

Für mehr als i=10 000 Rekursionstiefe, macht das aber keinen Sinn mehr.

Theoretisch könnte man für die 4 einen beliebig hohen Wert wählen.

Btw... Zeile 14 und Zeile 20 kann noch etwas vereinfacht werden:

int x = ((int) Math.log10(i) + i * 2 + 3 - j) / 2;

das ist mir gestern nicht mehr aufgefallen...

und dann steht da ja quasi: x=floor((floor(log_10(i))+i2+3-j)/2).

https://www.wolframalpha.com/input?i=solve+x%3Dfloor((floor(log_10(i))%2Bi2%2B3-j)%2F2)+for+i da kommt eine Stufenebene raus (Treppe)

Schlangenmensch

@NoIDE sagte in Zeichen rekursiv verdoppeln und "zählen":

Das "Verdoppeln" soll nicht durch Schleifen geschehen

Damit wird's halt einfach. Dann weiß ich auch nicht, was dein "Versuch" mit dem Beweis sollte.

Und, auch wenn für deinen Anwendungsfall hier die 4 ausreicht, ist, egal welche Zahl da steht, das nicht "allgemeingültig". Sowas führt dann am Ende zum Year 2038 Problem

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Damit wird's halt einfach. Dann weiß ich auch nicht, was dein "Versuch" mit dem Beweis sollte.

a) ich weiß nicht genau, ob der Beweis "richtig" ist, und
b) ich weiß auch nicht mehr genau, was ich da beweisen wollte.

@Schlangenmensch sagte in Zeichen rekursiv verdoppeln und "zählen":

Und, auch wenn für deinen Anwendungsfall hier die 4 ausreicht, ist, egal welche Zahl da steht, das nicht "allgemeingültig".

Deshalb war ja eigentlich die Frage nach der Formel.

@admin und @Mod kann dieses Thema nicht gelöscht werden, bitte? Es stellt doch offenbar für viele ein Ärgernis dar.

Edit: Also, nicht nicht... Bitte löschen.