From Newsgroup: comp.lang.c

This one I dreamt up when thinking about shuffling a sorted text file.

I haven't written any code yet, so it might be too easy or too hard or
too nonsense or too time-consuming (it took me a couple hours just
writing this up).

Let me know what you think.


-----------------------
Objective
-----------------------
An algorithm, implemented in C, that puts words from a unique sorted
list into a new order that maximizes the sum of the absolute shifts from
the original positions of the words.


---------------
Example N = 10 -------------------------------------------------------------------------
Initial Rand Abs Reverse Abs Rotate by 1
Words Address Algo Shift Sort Shift Pos Shift -------------------------------------------------------------------------
aaaaa 0 4 4 9 9 9 9
bbbbb 1 9 8 8 7 0 1
ccccc 2 3 1 7 5 1 1
ddddd 3 5 2 6 3 2 1
eeeee 4 7 3 5 1 3 1
fffff 5 0 5 4 1 4 1
ggggg 6 2 4 3 3 5 1
hhhhh 7 1 6 2 5 6 1
iiiii 8 6 2 1 7 7 1
jjjjj 9 8 1 0 9 8 1 -------------------------------------------------------------------------
Total 45 45 45 50 18 -------------------------------------------------------------------------

So:

1) a random shuffling gives total abs(shift) equal to the sum of 1..N-1.

2) Reversing the order gives a total abs(shift) of 50, which is
Sum(1..N-1) + (N/2)

3) "Rotate" means moving the positions up or down: last word become
the 1st word, 1st word becomes the 2nd word, 2nd word becomes the
3rd word, etc (or the other way).

Total
Rotate abs(shift)
1 18
2 32
3 42
4 48
5 50
6 48
7 42
8 32
9 18

So the formula for calculating the abs(shift) of a rotation value R is 2R(abs(N-R)) where R < N, and max abs(shift) occurs at N/2.


-----------------------
Max Score Available
-----------------------
Looks like Sum(1..N-1) + (N/2) is the max abs(shift) you can achieve if
all word positions are shifted by at least 1.


-----------------------
Challenge requirements
-----------------------
1) 0-based positioning
2) N = count of unique words
3) each 2 consecutive words from the original list must be separated by
at least N/50 places in the final shuffled list
4) each word must be moved at least N/10 places from its original
position
5) 1/2 the words must be moved up in position, and 1/2 must be moved
down in position (or rotated in either direction)
6) cannot use a random nbr generator or library in your code
7) 2 outputs, generated by your algorithm applied to the list below:
* the total abs(shift) of the shuffled word positions
* the Top 20 and Bottom 20 words after shuffling (and their original
positions)

Yes, requirements 3,4,5 are arbitrary, put in to make it more difficult
(I hope).

I debated putting this next statement in, since it will be obvious to
most, but assuming the input list is unique and sorted:

*** You don't need to sort any words. Ever. ***

You're free to do so, but it's not required to complete any part of the challenge.

If you read this far, can you think of any real-world usage for it?

Everyone's submission will be run against the same word list, which will
also be used to print your Top/Bottom 20. That 2600-word list (unique
and sorted) is:

https://filebin.net/t35q2wd67ovt97lj/2600words.txt


Enjoy!


--- Synchronet 3.21f-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Am 31.03.2026 um 23:33 schrieb DFS:

An algorithm, implemented in C, that puts words from a unique sorted
list into a new order that maximizes the sum of the absolute shifts from
the original positions of the words.

Just rotate the sorted list bei 50% ?
--- Synchronet 3.21f-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 4/1/2026 8:31 AM, Bonita Montero wrote:

Am 31.03.2026 um 23:33 schrieb DFS:

An algorithm, implemented in C, that puts words from a unique sorted
list into a new order that maximizes the sum of the absolute shifts
from the original positions of the words.

Just rotate the sorted list bei 50% ?

You didn't read the requirements.



--- Synchronet 3.21f-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 31/03/2026 22:33, DFS wrote:

I haven't written any code yet, so it might be too easy or too hard or
too nonsense or too time-consuming (it took me a couple hours just
writing this up).

Let me know what you think.

I think it's pretty hard, solutions could be slow like a bubble-sort for
an (relatively) easy solution or fast (if possible) for a difficult one.

-----------------------
Objective
-----------------------
An algorithm, implemented in C, that puts words from a unique sorted
list into a new order that maximizes the sum of the absolute shifts from
the original positions of the words.

I think this should have "subject to additional constraints as described
in the requirements list below" to set an excited mind steady enough to
take it all in before finding strategies.

---------------
Example N = 10

It looks like maybe that should be in the output, but maybe it's just
the title of the example output.

-------------------------------------------------------------------------          Initial    Rand  Abs        Reverse  Abs      Rotate by 1
 Words   Address    Algo  Shift       Sort   Shift      Pos Shift
-------------------------------------------------------------------------  aaaaa      0        4     4           9       9         9    9
 bbbbb      1        9     8           8       7         0    1

...

-----------------------
Challenge requirements
-----------------------
1) 0-based positioning
2) N = count of unique words

If that's /not/ in the output then it's confusing to be in a
requirements section:

- perhaps I have to define a nonconforming variable called 'N' instead
of 'n'! Not what I want to do if I know C, and
- perhaps, also, it has to have external linkage, otherwise it's not
really there at all; something doesn't add up.

If you read this far, can you think of any real-world usage for it?

Perhaps storage planning for fissile materials?

- to prevent problems in that area when working on the Manhatten
Project, nuclear physicist Richard Feynmann insisted the factory
designers be told what they were working so they would get it right. I
think that factory is where nuclear secrets leaked to the USSR so they
got the bomb. Mr. Feynmann talks about both events gleefully in his
hilarious "Los Alamos From Below" recording but doesn't seem to note the coincidence. Perhaps if he'd had an enthusiastic coder working with a
language just difficult enough to seem like an end in itself that could
have been prevented.

Rearranging queues of unruly children?
Thwarting businesses?
Thwarting romantic coupling?
--
Tristan Wibberley

The message body is Copyright (C) 2026 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

--- Synchronet 3.21f-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 4/3/2026 4:03 AM, Tristan Wibberley wrote:

On 31/03/2026 22:33, DFS wrote:

I haven't written any code yet, so it might be too easy or too hard or
too nonsense or too time-consuming (it took me a couple hours just
writing this up).

Let me know what you think.

I think it's pretty hard, solutions could be slow like a bubble-sort for
an (relatively) easy solution or fast (if possible) for a difficult one.

To be clear: the challenge doesn't require sorting of any kind, but
you're of course free to do so.

All you're trying to do is MOVE the words - subject to constraints 3,4,5
- to maximize the abs(differences) between the original positions and
the new positions.

-----------------------
Objective
-----------------------
An algorithm, implemented in C, that puts words from a unique sorted
list into a new order that maximizes the sum of the absolute shifts from
the original positions of the words.

I think this should have "subject to additional constraints as described
in the requirements list below" to set an excited mind steady enough to
take it all in before finding strategies.

---------------
Example N = 10

It looks like maybe that should be in the output, but maybe it's just
the title of the example output.

It's just the title.

-------------------------------------------------------------------------
         Initial    Rand  Abs        Reverse  Abs      Rotate by 1
 Words   Address    Algo  Shift       Sort   Shift      Pos Shift
-------------------------------------------------------------------------
 aaaaa      0        4     4           9       9         9    9
 bbbbb      1        9     8           8       7         0    1

...

-----------------------
Challenge requirements
-----------------------
1) 0-based positioning
2) N = count of unique words

If that's/not/ in the output then it's confusing to be in a
requirements section:

I put N here because the constraints 3,4,5 (which you snipped) used it.

- perhaps I have to define a nonconforming variable called 'N' instead
of 'n'! Not what I want to do if I know C, and
- perhaps, also, it has to have external linkage, otherwise it's not
really there at all; something doesn't add up.

Do you just like to talk your way around and out of making an attempt at
the challenge?

Fish or cut bait.

If you read this far, can you think of any real-world usage for it?

Perhaps storage planning for fissile materials?

- to prevent problems in that area when working on the Manhatten
Project, nuclear physicist Richard Feynmann insisted the factory
designers be told what they were working so they would get it right. I
think that factory is where nuclear secrets leaked to the USSR so they
got the bomb. Mr. Feynmann talks about both events gleefully in his
hilarious "Los Alamos From Below" recording but doesn't seem to note the coincidence. Perhaps if he'd had an enthusiastic coder working with a language just difficult enough to seem like an end in itself that could
have been prevented.

Thanks for the mention. I read that whole article last night. Very interesting. He's quite a humorous character for a physicist. I didn't
know he was so into bypassing locks and safe-cracking.

use it to promote my greatness and general superiority > my opinion

of my greatness and general superiority

wtf? Only losers brag about their self-proclaimed "greatness and
superiority"

--- Synchronet 3.21f-Linux NewsLink 1.2