Удивительная система сортировки сумасшедшего библиотекаря

21

Это снова в школьный сезон! Так что на неполный рабочий день вы помогаете в школьной библиотеке. Проблема в том, что главный библиотекарь никогда даже не слышал слова «Десятичный Дьюи», не говоря уже о внедрении этой системы. Вместо этого используемая система сортировки выросла «органично», поскольку библиотека расширилась ...

Стремясь сохранить свое здравомыслие, вы решили написать программу, которая поможет вам сортировать книги по мере их поступления, потому что горе вам, если вы неправильно сортируете книги. (Главный библиотекарь ОЧЕНЬ строг.)

Ввод, вывод

  • Входными данными будет список (гипотетических) названий книг, по одному на строку, из STDIN / языкового эквивалента.
  • Вы можете принять не более 100 книг одновременно (вы можете носить с собой только столько книг одновременно).
  • В названиях книг может быть несколько слов, и эти слова могут быть разделены пробелами или другой пунктуацией (например, двоеточие :, тире -и т. Д.).
  • Для простоты расчета предположим, что все названия имеют UTF-8.

Выходные данные - это те же заголовки, отсортированные в соответствии с приведенными ниже правилами, снова по одному на строку, в STDOUT / эквивалент языка.

Правила сортировки

Книги отсортированы по номерам на основе их среднего значения символов (т. Е. Совокупного значения символов, разделенного на количество символов в названии книги), рассчитанного по следующим правилам:

  • Все символы учитываются для определения количества символов в заголовке.
  • Строчные буквы подсчитываются по их положению в алфавите. (А = 1, B = 2, ... г = 26)
  • Если заголовок содержит заглавные буквы, они считаются для 1,5 их строчными буквами (A = 1,5, B = 3, ... Z = 39). («Заглавные буквы важны!» - говорит библиотекарь.)
  • Каждый знак пунктуации / символ в этом списке !@#$%^&*()-=_+[]\{}|;':",./<>?~отсчитывает -1 от совокупного значения перед усреднением. («Грандиозных названий нет!»)
  • Если заголовок содержит число, написанное арабскими цифрами , это число перед сортировкой вычитается из среднего значения. Несколько последовательных цифр обрабатываются как одно число (например, 42вычтет 42, а не вычтет 4, а затем вычтет 2). Отдельные цифры не учитываются для совокупного значения (т. Е. Каждая цифра дает 0), но ДО учитываются для количества символов. Обратите внимание, что это может привести к отрицательному значению и должно рассматриваться соответствующим образом. (По слухам, библиотекарь уже несколько лет влюблен в преподавателя математики.)
  • Если заголовок содержит два отдельных слова, которые начинаются с «,» R, книга получает оценку «бесконечность» и сбрасывается в стопку в углу (т. Е. Случайно расположенную в конце списка). (Библиотекарь был когда-то брошен человеком с этими инициалами, или вы так слышали.)
  • Пробелы не учитывают совокупное значение символа (т. Е. Они дают 0), но ДО способствуют количеству символов в заголовке.
  • Символы, которые не соответствуют указанным выше правилам (например, a ÿ), не учитываются в совокупном значении символа (т. Е. Они дают 0), но ДОЛЖНЫ вносить вклад в количество символов в названии.
  • Например, гипотетическая книга ÿÿÿÿÿбудет иметь «оценку» (0+0+0+0+0) / 5 = 0, а гипотетическая книга ÿÿyÿÿбудет иметь «оценку» (0+0+25+0+0) / 5 = 5.
  • Две книги, которые "забивают" одно и то же, могут быть выведены на ваш выбор. (Во всяком случае, они на одной полке)

Пример ввода 1

War and Peace
Reading Rainbow: The Best Unicorn Ever
Maus
Home for a Bunny

Пример вывода 1 (в скобках указаны «оценки», чтобы показать обоснование - вам не нужно их печатать)

War and Peace (8.5)
Home for a Bunny (10.125)
Maus (15.125)
Reading Rainbow: The Best Unicorn Ever (infinity)

Пример ввода 2

Matthew
Mark
Luke
John
Revelations

Пример вывода 2 (с «счетами» в скобках, чтобы показать обоснование - вам не нужно их печатать)

Mark (12.375)
John (13)
Revelations (13.545454...)
Luke (13.75)
Matthew (~13.786)

Пример ввода 3

42
9 Kings
1:8
7th

Пример вывода 3 (в скобках указаны «показатели», чтобы показать обоснование - вам не нужно их печатать)

42 (-42)
1:8 (-9.3333...)
9 Kings (~0.36)
7th (2.3333...)

Другие ограничения

  • Это Code-Golf, потому что вы должны держать программу в секрете от постоянных глаз библиотекаря, и чем меньше программа, тем легче ее скрыть.
  • Стандартные ограничения лазейки применяются
  • Не позволяйте библиотекарю отвлечь вас, потратив все свое время на PPCG.
AdmBorkBork
источник
Что делать, если две книги забили одинаково. то есть у меня есть чтение Rainbow и Ruby Rails
Кишан Кумар
@KishanKumar В этом конкретном случае, «случайным образом расположенные в конце списка», так как они оба двойные R. Другими словами, сделайте свой выбор. В общем случае, если два слова имеют одинаковую оценку, они могут появляться в любом порядке относительно друг друга. Я добавлю пулю, чтобы уточнить это.
AdmBorkBork
7
Вам нужно слово A, чтобы ваша система имела название аббревиатуры. Я рекомендую Удивительную Систему Сортировки
Безумного
3
@ Geobits У вас есть класс?
AdmBorkBork
Числа просто десятичные числа? Что, если их несколько, все они вычитаются отдельно?
Паŭло Эберманн

Ответы:

5

APL (132)

{⎕ML←3⋄⍵[⍋{2='R'+.=↑¨⍵⊂⍨⍵≠' ':!99⋄↑(+/⍎¨'0',⍵⊂⍨⍵∊⎕D)-⍨((+/∊1.5 1×(⍳×∊⍨)∘⍵¨G)-+/⍵∊(⎕UCS 32+⍳94)~'`',⎕D,∊G←(⊂⎕A),⊂⎕UCS 96+⍳26)÷⍴⍵}¨⍵]}

Поскольку все остальные делают то же самое, это тоже функция, которая принимает массив заголовков и возвращает его отсортированным, например:

      titles
┌─────────────┬──────────────────────────────────────┬────┬────────────────┬───────┬────┬────┬────┬───────────┬──┬───────┬───┬───┐
│War and Peace│Reading Rainbow: The Best Unicorn Ever│Maus│Home for a Bunny│Matthew│Mark│Luke│John│Revelations│42│9 Kings│1:8│7th│
└─────────────┴──────────────────────────────────────┴────┴────────────────┴───────┴────┴────┴────┴───────────┴──┴───────┴───┴───┘

      {⎕ML←3⋄⍵[⍋{2='R'+.=↑¨⍵⊂⍨⍵≠' ':!99⋄↑(+/⍎¨'0',⍵⊂⍨⍵∊⎕D)-⍨((+/∊1.5 1×(⍳×∊⍨)∘⍵¨G)-+/⍵∊(⎕UCS 32+⍳94)~'`',⎕D,∊G←(⊂⎕A),⊂⎕UCS 96+⍳26)÷⍴⍵}¨⍵]}titles
┌──┬───┬───────┬───┬─────────────┬────────────────┬────┬────┬───────────┬────┬───────┬────┬──────────────────────────────────────┐
│42│1:8│9 Kings│7th│War and Peace│Home for a Bunny│Mark│John│Revelations│Luke│Matthew│Maus│Reading Rainbow: The Best Unicorn Ever│
└──┴───┴───────┴───┴─────────────┴────────────────┴────┴────┴───────────┴────┴───────┴────┴──────────────────────────────────────┘

Объяснение:

  • ⎕ML←3: установить ⎕MLв 3(для )
  • ⍵[⍋{... }¨⍵]: сортировка ввода по значениям, возвращаемым из внутренней функции
    • ↑¨⍵⊂⍨⍵≠' ': получить первый символ каждого слова
    • 2='R'+.=: посмотреть, если два из них 'R'.
    • :!99: если так, верни 99! (≈ 9,3 × 10 155 ). Это не совсем бесконечность, но это подойдет: заголовок никогда не может иметь оценку более чем в 38 раз превышающую его длину (ZZZZ ...), поэтому, если ни один заголовок не будет больше, чем примерно 2 × 10 130 йотбайт, Гарантируется, что это будет в конце.
    • : в противном случае:
    • (... )÷⍴⍵: разделите счет на длину после его вычисления:
      • G←(⊂⎕A),(⎕UCS 96+⍳26): хранить в Gверхнем и нижнем регистре букв
      • (⎕UCS 32+⍳94)~'`',⎕D,∊G: печатаемые символы ASCII, за исключением букв, цифр, пробелов и '`', которые являются символами, для которых вычитается точка. (Это короче, чем записать их все, потому что Gиспользуется позже.)
      • +/⍵∊: посчитать количество этих символов в
      • -вычесть это из:
      • +/∊1.5 1×(⍳×∊⍨)∘⍵¨G: сумма 1,5 × баллов за прописные буквы и 1 × баллов за строчные буквы.
    • -⍨: затем вычесть общее количество чисел в :
      • ⍵⊂⍨⍵∊⎕D: найти группы цифр в
      • '0',: добавить '0', чтобы предотвратить пустой список
      • ⍎¨: оценить каждую строку
      • +/: найти сумму
Мэринус
источник
Вместо того, чтобы !99вы могли использовать⌊/⍬
Адам
1
Я люблю смотреть на длинный код в APL. Это заставляет меня чувствовать, что мир намного больше меня. И мне нравятся символы.
Конор О'Брайен
2

Lua 5.3, 366 364 Bytes

r={}for i,s in ipairs(arg)do n=0 s:gsub("%l",function(a)n=n+(a:byte()-96)end):gsub("%u",function(a)n=n+(a:byte()-64)*1.5 end):gsub("%p",function(a)n=n-1 end):gsub("^R?.- R.- ?R?",function()n=math.huge end)m=n/utf8.len(s)s:gsub("%d+",function(a)m=m-a end)table.insert(r,{s=s,n=m})end table.sort(r,function(a,b)return a.n<b.n end)for i,v in ipairs(r)do print(v.s)end

Этот код работает только в Lua 5.3, потому что он должен работать с символами Unicode. Если вас не интересует Unicode, замените «utf8» на «string», и он будет хорошо работать с Lua 5.2 или 5.1.

Он берет свои входные данные из аргументов командной строки, поэтому либо запустите его из командной строки, либо поместите этот код над моим ответом:

arg = {"Title 1", "Title 2", "Title 3"}
Trebuchette
источник
Я не Lua 5.3 на моей машине, но я последовал за ваше предложение поменять местами utf8с stringна Ideone и не получил никакого вывода.
AdmBorkBork
@TimmyD см. Мое редактирование
Требушетт,
Хорошо. Соус. И (arg)сидит там, глядя мне в лицо. Этот вопрос, видимо, зажёг мне мозг. Есть +1.
AdmBorkBork
Для MoonScript это составляет 266 байт: pastebin.com/wr4qVs5h .
kirbyfan64sos
2

Mathematica, 253 216 байт (214 символов)

r=RegularExpression;c=ToCharacterCode;f=SortBy[Tr@Flatten@Reap[StringCases[#,
{r@"(\\bR.*)+"->∞,r@"\\d+":>0Sow@-FromDigits@"$0",r@"[a-z]":>c@"$0"-96,
r@"[A-Z]":>1.5c@"$0"-96,r@"[!-/:-@[-_{-~]"->-1}]/StringLength@#]&]

Вызовите функцию как f[{"42", "9 Kings", "1:8", "7th"}]; он вернет отсортированный список входных данных.

Просто едва сделал это! Сопоставление с образцом в Mathematica не так лаконично, когда задействованы строки, и меня просто убивают эти длинные имена. Два дополнительных байта предназначены для Infinityсимвола Юникод.

(Дайте мне знать, не попал ли я в какие-либо стандартные лазейки.)

Обновить

Посмотрев немного ближе к ответу edc65, похоже, что OP примет функцию, которая сортирует список строк. Имея это в виду, мы можем использовать каррированную форму SortBy(которую Mathematica называет «операторной формой»); с одним аргументом (функция, примененная к элементам списка для определения их порядка), она ведет себя как функция, которая принимает один аргумент, возвращая отсортированную форму ввода; то есть SortBy[list, f]эквивалентно (SortBy[f])[list].

Ungolfed

Function[{titles},
  SortBy[titles, Function[{str}, (* sort by function value *)
    Total[Flatten[Reap[ (* total up all the parts *)
      StringCases[str, {
        RegularExpression["(\\bR.*){2}"] -> Infinity
          (* matches R at the start of a word twice, adds infinity to the total *),
        RegularExpression["\\d+"] :> 0 * Sow[-FromDigits["$0"]]
          (* matches a number, Sows it for Reap to collect, then multiplies by zero
                                                          to not affect the average *),
        RegularExpression["[a-z]"] :> ToCharacterCode["$0"] - 96
          (* matches a lowercase letter and returns its value *),
        RegularExpression["[A-Z]"] :> 1.5 ToCharacterCode["$0"] - 96
          (* matches an uppercase letter and returns 1.5 its value *),
        RegularExpression["[!-/:-@[-_{-~]"] -> -1
          (* matches a 'grandiose' symbol and returns -1 *)
      }] / StringLength[#] (* averages character values *)
    ]]]
  ]]
]
2012rcampion
источник
1
Хороший ответ, и вы получаете интернет-куки для буквального использования "бесконечности" в ваших расчетах ;-).
AdmBorkBork
@TimmyD Красота символической математической обработки =)
2012rcampion
Вероятно, вы имеете в виду 214 символов, 216 байтов. Отлично, я пытался соревноваться, но никак не
мог
2

JavaScript (ES6), 210 218 251

Как функция с аргументом массива, возвращается отсортированный.

f=L=>(S=s=>([...s].map(c=>t-=(a=s.charCodeAt(l++))>32&a<48|a>57&a<65|a>90&a<96|a>122&a<127?1:a>64&a<123?96-(a<96?a*1.5:a):0,l=t=0),s.split(/\D/).map(n=>t-=n,t/=l),t/!s.split(/\bR/)[2]),L.sort((a,b)=>S(a)-S(b)))

//TEST

test1=['War and Peace','Reading Rainbow: The Best Unicorn Ever','Maus','Home for a Bunny']
test2=['Matthew','Mark','Luke','John','Revelations']
test3=['42','9 Kings','1:8','7th']

;O.innerHTML=f(test1)+'\n\n'+f(test2)+'\n\n'+f(test3);

// The comparing function used to sort, more readable

Sort=s=>(
  t = 0, // running total
  l = 0, // to calc the string length avoiding the '.length' property
  [...s].map(c=>{
    a=s.charCodeAt(l++);
    t-=a>32&a<48|a>57&a<65|a>90&a<96|a>122&a<127
      ? 1 // symbols (ASCII char except space, alphanumeric and backtick)
      : a>64&a<123 
        ? 96-(a<96?a*1.5:a) // alphabetic both upcase and lowcase, and backtick
        // lowcase: 96-a, upcase (64-a)*1.5=>96-a*1.5, backtick is 96 and 96-96 == 0
        : 0 // else space, non ASCII, and numeric : 0
  }),
  t = t/l, // average
  s.split(/\D/).map(n=>t-=n), // sub number values
  f = s.split(/\bR/)[2], // split at words starting with R, if less then 2 f is undefined
  t/!f // dividing by not f I can get the infinity I need
)
<pre id=O></pre>

edc65
источник
Красиво сделано. Для ссылки на кого - либо еще читает этот ответ, я должен был изменить , O.innerHTMLчтобы this.InnerHTMLв консоли браузера Firefox.
AdmBorkBork
1

C #, 352 349 байт

Из-за магии linq:

class A{static void Main(string[]a){foreach(var x in a.OrderBy(b=>{var s="0";int j=0;return Regex.Split(b,@"[^\w]+").Count(l=>l[0]=='R')==2?(1/0d):b.Aggregate(0d,(d,e)=>{if(e>47&e<58){s+=e;return d;}d+=(e>64&e<91)?(e-64)*1.5:(e>96&e<123)?e-96:e>32&e<127&e!=96?-1:0;j+=int.Parse(s);s="0";return d;})/b.Length-j-int.Parse(s);}))Console.WriteLine(x);}}

Могли бы сохранить еще 6 байтов, если бы обратный удар был бы включен в список знаков препинания!

class A
{
    static void Main(string[] a)
    {
        foreach (var x in a.OrderBy(b =>
            {
                var s = "0";
                int j = 0;
                return Regex.Split(b, @"[^\w]+").Count(l => l[0] == 'R') == 2
                    ? (1 / 0d)
                        : b.Aggregate(0d, (d, e) =>
                        {
                            if (e > 47 & e < 58) { s += e; return d; }
                            d += (e > 64 & e < 91) ? (e - 64) * 1.5 : (e > 96 & e < 123) ? e - 96 : e > 32 & e < 127 & e != 96 ? -1 : 0;
                            j += int.Parse(s);
                            s = "0";
                            return d;
                        }) / b.Length - j - int.Parse(s);
            }))
            Console.WriteLine(x);
    }

}
Yitz
источник
1

Go, 755 байт

package main
import("os"
"fmt"
"math"
"bufio"
"regexp"
"sort"
"strconv")
type F float64
type T []F
func(t T)Swap(i,j int){t[i],t[j],S[i],S[j]=t[j],t[i],S[j],S[i]}
func(t T)Len()int{return len(t)}
func(t T)Less(i,j int)bool{return t[i]<t[j]}
var S []string
func main(){var t T
for{b:=bufio.NewReader(os.Stdin)
w,_,_:=b.ReadLine()
if len(w)==0{break}
u:=string(w)
var v F
for _,c:=range u{if 96<c&&c<123{v+=F(c)-F(96)}else
if 64<c&&c<91{v+=(F(c)-64)*1.5}else
if (48>c&&c>32)||(c>57&&c<127){v-=1}}
a:=v/F(len(w))
r,_:=regexp.Compile("[0-9]+")
n:=r.FindAllString(string(w),-1)
for _,x:=range n{y,_:=strconv.Atoi(x);a-=F(y)}
if m,_:=regexp.Match("((^| )R.*){2}",w);m{a=F(math.Inf(1))}
S=append(S,u)
t=append(t,a)}
sort.Sort(t)
for _,o:=range S{fmt.Println(o)}}

Отформатированная версия:

package main

import (
    "bufio"
    "fmt"
    "math"
    "os"
    "regexp"
    "sort"
    "strconv"
)

type F float64
type T []F

func (t T) Swap(i, j int)      { t[i], t[j], S[i], S[j] = t[j], t[i], S[j], S[i] }
func (t T) Len() int           { return len(t) }
func (t T) Less(i, j int) bool { return t[i] < t[j] }

var S []string

func main() {
    var t T
    for {
        b := bufio.NewReader(os.Stdin)
        w, _, _ := b.ReadLine()
        if len(w) == 0 {
            break
        }
        u := string(w)
        var v F
        for _, c := range u {
            if 96 < c && c < 123 {
                v += F(c) - F(96)
            } else if 64 < c && c < 91 {
                v += (F(c) - 64) * 1.5
            } else if (48 > c && c > 32) || (c > 57 && c < 127) {
                v -= 1
            }
        }
        a := v / F(len(w))
        r, _ := regexp.Compile("[0-9]+")
        n := r.FindAllString(string(w), -1)
        for _, x := range n {
            y, _ := strconv.Atoi(x)
            a -= F(y)
        }
        if m, _ := regexp.Match("((^| )R.*){2}", w); m {
            a = F(math.Inf(1))
        }
        S = append(S, u)
        t = append(t, a)
    }
    sort.Sort(t)
    for _, o := range S {
        fmt.Println(o)
    }
}

Реализация пользовательского интерфейса сортировки сделала его длиннее, чем ожидалось. Программа читает из STDIN до конца ввода или вводится пустая строка.

Фабиан Шменглер
источник
1

PHP, 362 367 Б

<?for(;$w=fgets(STDIN);$S[]=$w){for($l=$i=mb_strlen($w);$i--;){$c=array_sum(unpack("C*",mb_substr($w,$i,1)));96<$c&&$c<123 and $v+=$c-96 or 64<$c&&$c<91 and $v+=1.5*$c-96 or 48<$c&&$c>32||$c>57&&$c<127 and $v-=1;}$v/=$l;preg_match_all("/\d+/",$w,$m);$v-=array_sum($m[0]);preg_match("/((^| )R.*){2}/",$w)&&$v=INF;$t[]=$v;}array_multisort($t,$S);echo join("
",$S);

Отформатированная версия:

<?php
for (; $w = fgets(STDIN); $S[] = $w) {
    for ($l = $i = mb_strlen($w); $i--;) {
        $c = array_sum(unpack("C*", mb_substr($w, $i, 1)));
        96 < $c && $c < 123 and $v += $c - 96
        or 64 < $c && $c < 91 and $v += 1.5 * $c - 96
        or 48 < $c && $c > 32 || $c > 57 && $c < 127 and $v -= 1;
    }
    $v /= $l;
    preg_match_all("/\d+/", $w, $m);
    $v -= array_sum($m[0]);
    preg_match("/((^| )R.*){2}/", $w) && $v = INF;
    $t[] = $v;
}
array_multisort($t, $S);
echo join("
", $S); 

Интересные строки:

$c = array_sum(unpack("C*", mb_substr($w, $i, 1)));

Преобразует один символ UTF-8 в его байтовые значения и суммирует их, чтобы мы получили реальное значение для символов ASCII и значение больше 127 для многобайтовых символов.

96 < $c && $c < 123 and $v += $c - 96
or 64 < $c && $c < 91 and $v += 1.5 * $c - 96
or 48 < $c && $c > 32 || $c > 57 && $c < 127 and $v -= 1;

Использует низкий приоритет оператора andи orдля назначения символьного значения в одном операторе без if.

Фабиан Шменглер
источник