puzzle with string permutations [photo]

puzzle with string permutations [photo]

[Emanuel Berg]

[-- Attachment #1: Type: text/plain, Size: 1924 bytes --]

Try to solve this - not easy!

  https://dataswamp.org/~incal/pimgs/survivor-puzzle.png

It is from US/CBC Survivor S42E13 around 9 minutes in.

It says

  eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte

Easy LOL :) The first word should be "the"!

But even the second one, "kudce", that has

  (length (string-perms "kudce")) ; 120

permutations [source last]

And (length (string-perms "pigelsen")) ; 40 320 !

Even a word with just four letters, e.g. what should come out
of "seot", has 24 perms already!

  (length (string-perms "seot")) ; 24

Because of the vowels, word order, and generally just how the
brain works, which we don't know exactly even by far BTW, it
doesn't translate lineary to more difficult because of more
permutations ...

But let's just say I was unable to solve it with a full
stomach and rising from a cozy bed, actually that should be
the other way around now that we are mentioning the brain
and all.

What should it be?
"eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte" ?

;;; -*- lexical-binding: t -*-
;;
;; this file:
;;   https://dataswamp.org/~incal/emacs-init/perm.el

(require 'cl-lib)

;; Christoph Conrad @ https://www.emacswiki.org/emacs/StringPermutations
(defun perms (l)
  (if l (cl-mapcan (lambda (a)
                     (cl-mapcan (lambda (p)
                                  (list (cons a p)))
                                (perms (cl-remove a l :count 1)) )) l)
    '(()) ))

(defun string-perms (s)
  (let*((chars      (string-to-list s))
        (char-perms (perms chars)) )
    (mapcar (lambda (a)
              (concat a) )
            char-perms) ))

;; (string-perms "abc") ; abc acb bac bca cab cba
;; (string-perms "neo") ; neo noe eno eon one oen

;; eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte
;; (length (string-perms "kudce"))    ; 120
;; (length (string-perms "seot"))     ; 24
;; (length (string-perms "pigelsen")) ; 40 320


[-- Attachment #2: survivor-puzzle.png --]
[-- Type: image/png, Size: 357181 bytes --]

[-- Attachment #3: Type: text/plain, Size: 61 bytes --]


-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Marcin Borkowski]

On 2022-06-07, at 08:39, Emanuel Berg <incal@dataswamp.org> wrote:

> Try to solve this - not easy!
>
>   https://dataswamp.org/~incal/pimgs/survivor-puzzle.png
>
> It is from US/CBC Survivor S42E13 around 9 minutes in.
>
> It says
>
>   eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte
>
> Easy LOL :) The first word should be "the"!

I'm not sure if it's just permutations.  "kudtce" could be "tucked", but
"erontuf"?

Anyway, I would personally permute only consonants - if the vowels are
out of order, the brain can often fill in the blanks pretty easily.
Also, it would be great to leverage ispell to exclude non-words from the
list of permutations - unfortunately, I don't know how to do it
(`ispell-word' looks pretty magical to me, at least after ~10 minutes of
looking - maybe if I had more time...)

But this made me think - one could write a simple game (a bit like M-x
decipher) to help decipher "permutation-based secret messages".  Looks
like a fun project.

Also, you don't have to list all the permutations to _count_ them -
Emacs can actually compute factorials:

(calc-eval "fact(5)") => "120"
(calc-eval "fact(10)") => "3628800"

Best,

-- 
Marcin Borkowski
http://mbork.pl

Re: puzzle with string permutations [photo]

[Emanuel Berg]

Marcin Borkowski wrote:

>>   eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte
>>
>> Easy LOL :) The first word should be "the"!
>
> I'm not sure if it's just permutations. "kudtce" could be
> "tucked", but "erontuf"?

Indeed it can't,

  (member "erontuf" (string-perms "kudtce")) ; nil

> Anyway, I would personally permute only consonants - if the
> vowels are out of order, the brain can often fill in the
> blanks pretty easily.

Good point, OTOH that's the beauty with programming, you have
to use your brain a lot so that you don't have to do that
anymore - at all! Luckily we haven't reached the point yet
where every problem can and is solved by a machine better than
a human being. So there are still stuff for us to do! Like for
example working on it ...

> Also, it would be great to leverage ispell to exclude
> non-words from the list of permutations - unfortunately,
> I don't know how to do it

Right, I asked some time ago why there isn't a lispy function
to spell a single word, I got the answer there's no use case
for that, I don't remember what the use case was back then but
now we know there are at least two. Anyway I did this, it uses
how ispell work when you use it interactively which,
admittedly, doesn't look good but in terms of the interface it
is usable with and from Lisp:

(defun spell-word (word)
  (with-temp-buffer
    (save-excursion
      (insert word) )
    (condition-case nil
        (not (ispell-word))
      (error nil) )))
;; (spell-word "length") ; t
;; (spell-word "lenght") ; nil

> (calc-eval "fact(5)") => "120"
> (calc-eval "fact(10)") => "3628800"

Indeed, however that isn't lispy either ...

Good that there is this list, suddenly I have stuff to do
again :)

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

>> (calc-eval "fact(5)") => "120"
>> (calc-eval "fact(10)") => "3628800"
>
> Indeed, however that isn't lispy either ...

(defun faculty (n)
  (if (> n 1)
      (* n (faculty (1- n)))
    1) )
;; (faculty  5) ;       120
;; (faculty 10) ; 3 628 800

(defun string-perms-num (str)
  (faculty (length str) ))
;; (string-perms-num "kudce") ; 120

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

>>> (calc-eval "fact(5)") => "120"
>>> (calc-eval "fact(10)") => "3628800"
>>
>> Indeed, however that isn't lispy either ...
>
> (defun faculty (n)
>   (if (> n 1)
>       (* n (faculty (1- n)))
>     1) )
> ;; (faculty  5) ;       120
> ;; (faculty 10) ; 3 628 800

Perhaps better, as no recursion.

(require 'cl-lib)

(defun cl-faculty (n)
  (cl-loop with prod = 1
    for i from 2 to n do
    (setq prod (* i prod))
    finally return prod) )
;; (cl-faculty  5) ;       120
;; (cl-faculty 10) ; 3 628 800

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

Emanuel Berg wrote:

>>>> (calc-eval "fact(5)") => "120"
>>>> (calc-eval "fact(10)") => "3628800"
>>>
>>> Indeed, however that isn't lispy either ...
>
> Perhaps better, as no recursion.
>
> (require 'cl-lib)
>
> (defun cl-faculty (n)
>   (cl-loop with prod = 1
>     for i from 2 to n do
>     (setq prod (* i prod))
>     finally return prod) )
> ;; (cl-faculty  5) ;       120
> ;; (cl-faculty 10) ; 3 628 800

Oh, that's right, we didn't think of duplicates. You can
remove them with `cl-remove-duplicates' like this

(cl-remove-duplicates
  (cl-remove-if-not (lambda (w) (spell-word w)) (string-perms str))
    :test #'string=)
                  ^^
( Indeed, Lisp is a fun language! =) )

but to do it without counting I think the formula is

  n!/(n - r)!

where n is the size of the set - here 26, as

  (length (alphabet t)) ; 26 [1]

and r is the number of items to be picked and arranged, or
here the length of the word.

This field of mathematics is called combinatorics BTW, maybe
because you combine a lot of stuff to solve it's problems
LOL :)

[1] https://dataswamp.org/~incal/emacs-init/abc.el

https://www.youtube.com/watch?v=6M3Kg1_5xFw

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

> to do it without counting I think the formula is
>
>   n!/(n - r)!
>
> where n is the size of the set - here 26, as
>
>   (length (alphabet t)) ; 26
>
> and r is the number of items to be picked and arranged, or
> here the length of the word.

It doesn't work exactly like that with strings, since for
example the scrambled word "ogod" is actually, here, treated
as

  o_1 g o_2 d

Yet the words

  g o_1 o_2 d 
  g o_2 o_1 d

are duplicates.

So the n, the set or alphabet is A = { d g o }

Yet it's stipulated that o, and only o, must be used twice!

Maybe there is a formula for that as well! Divide by 2 for all
chars that appear twice? But then how to generalize so it
scales for chars that appear thrice and so on?

The truth is out there ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Yuri Khan]

On Tue, 7 Jun 2022 at 21:18, Emanuel Berg <incal@dataswamp.org> wrote:

> It doesn't work exactly like that with strings, since for
> example the scrambled word "ogod" is actually, here, treated
> as
>
>   o_1 g o_2 d
>
> Yet the words
>
>   g o_1 o_2 d
>   g o_2 o_1 d
>
> are duplicates.

This extension of the concept of sets is called a multiset or a bag.
For each element, we also have a multiplicity. Let’s write it as {o:2,
g:1, d:1}.

Let’s solve the problem: Given a multiset of letters {X_1:n_1, …,
X_k:n_k}, how many distinct strings using up all of them are there?

First, we treat repeating letters as if they were distinct, e.g. by
numbering them as you did above: {o_1, o_2, g, d}. These are 4 letters
and there are 4! = 24 permutations.

However, every two permutations that only differ by the order of o_1
and o_2 are equivalent in our original unnumbered multiset. So we have
to divide by two: 4! / 2 = 24 / 2 = 12. dgoo, dogo, doog, gdoo, godo,
good, odgo, odog, ogdo, ogod, oodg, oogd.

What do we do if there are three or more instances of each letter?
Let’s consider a degenerate multiset {w:3}. If we number the
instances, it’s {w_1, w_2, w_3} and there are 3! = 6 permutations, but
clearly the only distinct string is www. So it looks like we need to
divide by 3! = 6: 3! / 3! = 6 / 6 = 1.

In general, with a multiset {X_1:n_1, …, X_k:n_k}, if we number each
letter, we get (n_1 + … + n_k)! permutations, and then we have to
adjust for duplicates for each individual letter by dividing by (n_1)!
… (n_k)!.

n_perm = (n_1 + … + n_k)! / (n_1)! … (n_k)!

For the above example of {o:2, g:1, d:1}:

n_perm = (2 + 1 + 1)! / 2! 1! 1! = 4! / 2 1 1 = 24 / 2 = 12.

(This problem was part of my exam in maths when I was applying at
Novosibirsk State University, Mechanics & Maths Department, in 1997.)

(You might also notice the formula is similar to that of a binomial
coefficient: C_{n,k} = n! / k! (n-k)!. That’s no coincidence.)

Re: puzzle with string permutations [photo]

[Emanuel Berg]

Yuri Khan wrote:

> This extension of the concept of sets is called a multiset
> or a bag. For each element, we also have a multiplicity.
> Let’s write it as {o:2, g:1, d:1}.

OK, cool!

> n_perm = (n_1 + ... + n_k)! / (n_1)! ... (n_k)!

Right, that's tedious to do programming of tho (but possible
of course) because of the expanding summation and
product ...

> This problem was part of my exam in maths when I was
> applying at Novosibirsk State University, Mechanics & Maths
> Department, in 1997.

:)

> You might also notice the formula is similar to that of
> a binomial coefficient: C_{n,k} = n! / k! (n-k)!. That's
> no coincidence.

That OTOH is easy to implement, but what is n and k exactly? Can you
use that here?

(defun binom (n k)
  (/ (cl-faculty n)
     (* (cl-faculty k)
        (cl-faculty (- n k)) )))

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

Yuri Khan wrote:

> In general, with a multiset {X_1:n_1, ..., X_k:n_k}, if we
> number each letter, we get (n_1 + ... + n_k)! permutations,
> and then we have to adjust for duplicates for each
> individual letter by dividing by (n_1)! ... (n_k)!.
>
> n_perm = (n_1 + ... + n_k)! / (n_1)! ... (n_k)!

You mean like this?

(require 'cl-lib)

(defun cl-faculty (n)
  (cl-loop with prod = 1
    for i from 2 to n do
    (setq prod (* i prod))
    finally return prod) )
;; (cl-faculty  5) ;       120
;; (cl-faculty 10) ; 3 628 800

(defun count (e l)
  (seq-count (lambda (elem) (= elem e)) l) )
;; (count ?o '(?d ?g ?o ?o)) ; 2

(defun product-string (str)
  (let*((str-list         (string-to-list str))
        (str-list-no-dups (cl-remove-duplicates str-list))
        (prod 1) )
    (dolist (e str-list-no-dups)
      (setq prod (* prod (cl-faculty (count e str-list)))) )
    prod ))
;; (product-string "ogod") ; 2

(defun perms-string-num (str)
  (let ((n (cl-faculty (length str)))
        (r (product-string str)) )
    (/ n r) ))
;; (perms-string-num "ogod")   ;  12
;; (perms-string-num "kudtce") ; 720

-- 
underground experts united
https://dataswamp.org/~incal

missing Lisp world (was: Re: puzzle with string permutations [photo])

[Emanuel Berg]

This code BTW illustrates the strategic weakness we have had
for a long time, since day one actually from my perspective
anyway, namely that we've had and have an Emacs world which
contains Lisp (Elisp), but what we should have is a Lisp world
and Emacs would be one of many components of that world!

> (require 'cl-lib)
>
> (defun cl-faculty (n)
>   (cl-loop with prod = 1
>     for i from 2 to n do
>     (setq prod (* i prod))
>     finally return prod) )
> ;; (cl-faculty  5) ;       120
> ;; (cl-faculty 10) ; 3 628 800
>
> (defun count (e l)
>   (seq-count (lambda (elem) (= elem e)) l) )
> ;; (count ?o '(?d ?g ?o ?o)) ; 2
>
> (defun product-string (str)
>   (let*((str-list         (string-to-list str))
>         (str-list-no-dups (cl-remove-duplicates str-list))
>         (prod 1) )
>     (dolist (e str-list-no-dups)
>       (setq prod (* prod (cl-faculty (count e str-list)))) )
>     prod ))
> ;; (product-string "ogod") ; 2
>
> (defun perms-string-num (str)
>   (let ((n (cl-faculty (length str)))
>         (r (product-string str)) )
>     (/ n r) ))
> ;; (perms-string-num "ogod")   ;  12
> ;; (perms-string-num "kudtce") ; 720

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

Marcin Borkowski wrote:

> Also, it would be great to leverage ispell to exclude
> non-words from the list of permutations

That was sure a good idea!

(defun string-perms-filter (str)
  (let ((strs (cl-remove-duplicates
               (cl-remove-if-not (lambda (w) (spell-word w)) (string-perms str))
               :test #'string=) ))
    (if (= 1 (length strs))
        (car strs)
      strs) ))

;; (string-perms-filter "eht")      ; the
;; (string-perms-filter "ogod")     ; good
;; (string-perms-filter "erontuf")
;; (string-perms-filter "si")       ; is
;; (string-perms-filter "kudtce")   ; tucked
;; (string-perms-filter "ni")       ; in
;; (string-perms-filter "hte")      ; the
;; (string-perms-filter "pigelsen")
;; (string-perms-filter "seot")     ; toes
;; (string-perms-filter "tagni")    ; giant

By now I think I can guess "erontuf" (fortune) and "pigelsen"
(sleeping), those are more expensive to compute because of the
longer words but I'm confident in this method by now ...

https://dataswamp.org/~incal/emacs-init/perm.el
https://dataswamp.org/~incal/emacs-init/spell.el

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Emanuel Berg]

> ;; (string-perms-filter "eht")      ; the
> ;; (string-perms-filter "ogod")     ; good
> ;; (string-perms-filter "erontuf")
> ;; (string-perms-filter "si")       ; is
> ;; (string-perms-filter "kudtce")   ; tucked
> ;; (string-perms-filter "ni")       ; in
> ;; (string-perms-filter "hte")      ; the
> ;; (string-perms-filter "pigelsen")
> ;; (string-perms-filter "seot")     ; toes
> ;; (string-perms-filter "tagni")    ; giant

OK, I completed the last two with the same method (functions),
it seems "pigelsen" is the only one that has two permutations
that are also words, see below.

Also it wasn't quite right above, the word order ... but
almost

;; (string-perms-filter "ogod")     ; good
;; (string-perms-filter "erontuf")  ; fortune
;; (string-perms-filter "si")       ; is
;; (string-perms-filter "kudtce")   ; tucked
;; (string-perms-filter "ni")       ; in
;; (string-perms-filter "eht")      ; the
;; (string-perms-filter "seot")     ; toes
;; (string-perms-filter "fo")       ; of
;; (string-perms-filter "hte")      ; the
;; (string-perms-filter "pigelsen") ; ("peelings" "sleeping")
;; (string-perms-filter "tagni")    ; giant

https://www.youtube.com/watch?v=VuDKPak3HQw

Ikr? I should have been on Survivor! I could have won with
this method! :D

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Marcin Borkowski]

http://mbork.pl/2022-08-01_Making_secrets_with_Emacs

On 2022-06-07, at 08:39, Emanuel Berg <incal@dataswamp.org> wrote:

> Try to solve this - not easy!
>
>   https://dataswamp.org/~incal/pimgs/survivor-puzzle.png
>
> It is from US/CBC Survivor S42E13 around 9 minutes in.
>
> It says
>
>   eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte
>
> Easy LOL :) The first word should be "the"!
>
> But even the second one, "kudce", that has
>
>   (length (string-perms "kudce")) ; 120
>
> permutations [source last]
>
> And (length (string-perms "pigelsen")) ; 40 320 !
>
> Even a word with just four letters, e.g. what should come out
> of "seot", has 24 perms already!
>
>   (length (string-perms "seot")) ; 24
>
> Because of the vowels, word order, and generally just how the
> brain works, which we don't know exactly even by far BTW, it
> doesn't translate lineary to more difficult because of more
> permutations ...
>
> But let's just say I was unable to solve it with a full
> stomach and rising from a cozy bed, actually that should be
> the other way around now that we are mentioning the brain
> and all.
>
> What should it be?
> "eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte" ?
>
> ;;; -*- lexical-binding: t -*-
> ;;
> ;; this file:
> ;;   https://dataswamp.org/~incal/emacs-init/perm.el
>
> (require 'cl-lib)
>
> ;; Christoph Conrad @ https://www.emacswiki.org/emacs/StringPermutations
> (defun perms (l)
>   (if l (cl-mapcan (lambda (a)
>                      (cl-mapcan (lambda (p)
>                                   (list (cons a p)))
>                                 (perms (cl-remove a l :count 1)) )) l)
>     '(()) ))
>
> (defun string-perms (s)
>   (let*((chars      (string-to-list s))
>         (char-perms (perms chars)) )
>     (mapcar (lambda (a)
>               (concat a) )
>             char-perms) ))
>
> ;; (string-perms "abc") ; abc acb bac bca cab cba
> ;; (string-perms "neo") ; neo noe eno eon one oen
>
> ;; eht kudtce pigelsen tagni ogod seot erontuf si ni fo hte
> ;; (length (string-perms "kudce"))    ; 120
> ;; (length (string-perms "seot"))     ; 24
> ;; (length (string-perms "pigelsen")) ; 40 320


-- 
Marcin Borkowski
http://mbork.pl

Re: puzzle with string permutations [photo]

[Emanuel Berg]

Marcin Borkowski wrote:

> http://mbork.pl/2022-08-01_Making_secrets_with_Emacs

Thanks!

I knew I'd make the Emacs News eventually but it sure happened
in an unexpected way ;)

The solution to the problem described initially is here

  https://dataswamp.org/~incal/emacs-init/perm.el

lines 33-45.

-- 
underground experts united
https://dataswamp.org/~incal

Re: puzzle with string permutations [photo]

[Jean Louis]

* Marcin Borkowski <mbork@mbork.pl> [2022-08-01 09:43]:
> http://mbork.pl/2022-08-01_Making_secrets_with_Emacs

That is great.

I have made package to use Emacs built-in encryption:

GNU Emacs Package: rcd-encryption.el: 
https://gnu.support/gnu-emacs/packages/GNU-Emacs-Package-rcd-encryption-el-70898.html

(rcd-encrypt-decrypt-base64 "Hello there" "mypassword") ⇒ "X4xvvMvQkoKwtN8t6sLvH2yA4+YoXCEbAlwymTzewF7ejjcYRA4g6OWhGeEBt0rby22xA+AP2xCZ
+cvK05rdrw=="

Or this encrypted region with password "something"

xEZW1e8Jj8b2mlJHpDjk0nFf4u2Jod3soRd12hYMT74bjPawxryZw4GBOD8ECC/XL37YXz2tDRUE6KsUi6Tb5w==

You may decrypt with {M-x rcd-decrypt-region-base64 RET} on the above text.

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/