0votos

Concatenación de números en Haskell

por josejuan hace 4 años

Bonito problema. Quizás exista una solución óptima analizando las palabras de entrada hasta aquella de máxima longitud (obteniendo O(n) o más probable O(n log n), ...). A lo bruto (pero eficiente) basta establecer el orden (que NO ES el habitual) y concatenar usando un heap de prioridad hasta encontrar uno.

Dada una lista de números devolver el valor numérico más alto resultado de reordenar la lista y concatenar los números

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import Data.Maybe 
import Data.List 
import qualified Data.Heap as H 
 
data N = N { unN :: String } deriving (Eq, Show) 
 
-- Un `N` es mayor que otro, no si realmente lo es, sino si puede llegar a serlo 
instance Ord N where 
    (N a) `compare` (N b) = 
        let (s, t) = (length a, length b) 
        in  case s `compare` t of 
                EQ -> a `compare` b 
                GT -> if b == take t a then LT else a `compare` b 
                LT -> if a == take s b then GT else a `compare` b 
 
 
fn :: (Read a, Show a) => [a] -> a 
fn xs = read $ search (H.singleton (N [], xs') :: H.MaxPrioHeap N [String]) 
    where xs' = map show xs 
          sz  = sum $ map length xs'    -- longitud objetivo (sólo nos piden una solución, 
                                        --                    no todas las posibles) 
          search h = let ((N k, ws), h') = fromJust $ H.view h 
                         inserting ls (w:rs) h = inserting (w:ls) rs $ H.insert (N (k++w), ls++rs) h 
                         inserting _  []     h = h 
                     in  if length k == sz then k else search $ inserting [] ws h' 
1 comentario
1votos

Escrito por drabor hace 4 años

Puedes utilizar newtype en vez de data cuando crees un tipo que envuelve a otro, es más rápido:
newtype N = N { unN :: String } deriving (Eq, Show)

newtype

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.