Rust, 929 923 Zeichen
use std::io;use std::str::FromStr;static C:&'static [i32]=&[-2,-1,2,5,10,15];fn main(){let mut z=String::new();io::stdin().read_line(&mut z).unwrap();let n=(&z.trim()[..]).split(' ').map(|e|i32::from_str(e).unwrap()).collect::<Vec<i32>>();let l=*n.iter().min().unwrap();let x=n.iter().max().unwrap()-if l>1{1}else{l};let s=g(x as usize);println!("{}",p(1,n,&s));}fn g(x:usize)->Vec<i32>{let mut s=vec![std::i32::MAX-9;x];for c in C{if *c>0&&(*c as usize)<=x{s[(*c-1)as usize]=1;}}let mut i=1us;while i<x{let mut k=i+1;for c in C{if(i as i32)+*c<0{continue;}let j=((i as i32)+*c)as usize;if j<x&&s[j]>s[i]+1{s[j]=s[i]+1;if k>j{k=j;}}}i=k;}s}fn p(r:i32,n:Vec<i32>,s:&Vec<i32>)->i32{if n.len()==1{h(r,n[0],&s)}else{(0..n.len()).map(|i|{let mut m=n.clone();let q=m.remove(i);p(q,m,&s)+h(r,q,&s)}).min().unwrap()}}fn h(a:i32,b:i32,s:&Vec<i32>)->i32{if a==b{0}else if a>b{((a-b)as f32/2f32).ceil()as i32}else{s[(b-a-1)as usize]}}
Das hat Spaß gemacht!
Kommentar zur Implementierung
Mit der Größe bin ich also offensichtlich nicht sehr zufrieden. Aber Rust ist sowieso absolut schrecklich im Golfen. Die Leistung ist jedoch wunderbar.
Der Code löst jeden Testfall innerhalb kürzester Zeit korrekt, sodass die Leistung offensichtlich kein Problem darstellt. Zum Spaß ist hier ein viel schwierigerer Testfall:
1234567 123456 12345 1234 123 777777 77777 7777 777
wofür lautet die Antwort 82317, die mein Programm auf meinem (mittelschweren) Laptop in 1,66 Sekunden (!) auch mit dem rekursiven Brute-Force-Hamilton-Pfad-Algorithmus lösen konnte .
Beobachtungen
Zuerst sollten wir ein modifiziertes gewichtetes Diagramm erstellen, wobei die Knoten die einzelnen "Glückszahlen" und die Gewichte die Anzahl der Änderungen sind, die erforderlich sind, um von einer Reputationsstufe zur anderen zu gelangen. Jedes Knotenpaar muss durch zwei Kanten verbunden sein, da ein Anstieg nicht mit einem Absinken des Reputationswerts identisch ist (Sie können beispielsweise +10, aber nicht -10 erhalten).
Nun müssen wir herausfinden, wie die minimale Anzahl von Änderungen von einem Wiederholungswert zu einem anderen ermittelt werden kann.
Um von einem höheren Wert zu einem niedrigeren Wert zu gelangen, ist es einfach: Nimm einfach, ceil((a - b) / 2)wo ader höhere Wert und bder niedrigere Wert ist. Unsere einzige logische Option besteht darin, das -2 so oft wie möglich zu verwenden und dann das -1, falls erforderlich, einmal.
Ein niedriger bis hoher Wert ist etwas komplizierter, da die Verwendung des größtmöglichen Werts nicht immer optimal ist (z. B. für 0 bis 9 ist die optimale Lösung +10 -1). Dies ist jedoch ein dynamisches Programmierproblem im Lehrbuch, und zur Lösung dieses Problems reicht ein einfaches DP aus.
Sobald wir die minimalen Änderungen von jeder Zahl zu jeder anderen Zahl berechnet haben, bleibt uns im Wesentlichen eine leichte Variante von TSP (Problem des Handlungsreisenden). Glücklicherweise gibt es eine kleine Anzahl von Knoten (maximal 5 im härtesten Testfall), die für diesen Schritt ausreichen.
Ungolfed Code (stark kommentiert)
use std::io;
use std::str::FromStr;
// all possible rep changes
static CHANGES: &'static [i32] = &[-2, -1, 2, 5, 10, 15];
fn main() {
// read line of input, convert to i32 vec
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let nums = (&input.trim()[..]).split(' ').map(|x| i32::from_str(x).unwrap())
.collect::<Vec<i32>>();
// we only need to generate as many additive solutions as max(nums) - min(nums)
// but if one of our targets isn't 1, this will return a too-low value.
// fortunately, this is easy to fix as a little hack
let min = *nums.iter().min().unwrap();
let count = nums.iter().max().unwrap() - if min > 1 { 1 } else { min };
let solutions = generate_solutions(count as usize);
// bruteforce!
println!("{}", shortest_path(1, nums, &solutions));
}
fn generate_solutions(count: usize) -> Vec<i32> {
let mut solutions = vec![std::i32::MAX - 9; count];
// base cases
for c in CHANGES {
if *c > 0 && (*c as usize) <= count {
solutions[(*c-1) as usize] = 1;
}
}
// dynamic programming! \o/
// ok so here's how the algorithm works.
// we go through the array from start to finish, and update the array
// elements at i-2, i-1, i+2, i+5, ... if solutions[i]+1 is less than
// (the corresponding index to update)'s current value
// however, note that we might also have to update a value at a lower index
// than i (-2 and -1)
// in that case, we will have to go back that many spaces so we can be sure
// to update *everything*.
// so for simplicity, we just set the new index to be the lowest changed
// value (and increment it if there were none changed).
let mut i = 1us; // (the minimum positive value in CHANGES) - 1 (ugly hardcoding)
while i < count {
let mut i2 = i+1;
// update all rep-values reachable in 1 "change" from this rep-value,
// by setting them to (this value + 1), IF AND ONLY IF the current
// value is less optimal than the new value
for c in CHANGES {
if (i as i32) + *c < 0 { continue; } // negative index = bad
let idx = ((i as i32) + *c) as usize; // the index to update
if idx < count && solutions[idx] > solutions[i]+1 {
// it's a better solution! :D
solutions[idx] = solutions[i]+1;
// if the index from which we'll start updating next is too low,
// we need to make sure the thing we just updated is going to,
// in turn, update other things from itself (tl;dr: DP)
if i2 > idx { i2 = idx; }
}
}
i = i2; // update index (note that i2 is i+1 by default)
}
solutions
}
fn shortest_path(rep: i32, nums: Vec<i32>, solutions: &Vec<i32>) -> i32 {
// mercifully, all the test cases are small enough so as to not require
// a full-blown optimized traveling salesman implementation
// recursive brute force ftw! \o/
if nums.len() == 1 { count_changes(rep, nums[0], &solutions) } // base case
else {
// try going from 'rep' to each item in 'nums'
(0..nums.len()).map(|i| {
// grab the new rep value out of the vec...
let mut nums2 = nums.clone();
let new_rep = nums2.remove(i);
// and map it to the shortest path if we use that value as our next target
shortest_path(new_rep, nums2, &solutions) + count_changes(rep, new_rep, &solutions)
}).min().unwrap() // return the minimum-length path
}
}
fn count_changes(start: i32, finish: i32, solutions: &Vec<i32>) -> i32 {
// count the number of changes required to get from 'start' rep to 'finish' rep
// obvious:
if start == finish { 0 }
// fairly intuitive (2f32 is just 2.0):
else if start > finish { ((start - finish) as f32 / 2f32).ceil() as i32 }
// use the pregenerated lookup table for these:
else /* if finish > start */ { solutions[(finish - start - 1) as usize] }
}
<!-- language-all: lang-rust -->. ;)floor((a-b)/15)+{0,2,1,2,2,1,3,2,2,2,1,3,2,2,2}[(a-b)%15]. Ihre Lösung könnte wahrscheinlich davon profitieren.Pyth -
4342 BytesVerwendet bei allen Permutationen und Kombinationen den Brute-Force-Ansatz.
Ich möchte nicht mehr Golf spielen, da dies zu Pyth führt.Übersetzt.Dies ist sogar langsamer als die Python-Version, da ich Filter anstelle einer while-Schleife verwende. Erklärung in Kürze, schauen Sie sich jetzt den Python-Code an.
Probieren Sie es hier online .
Arbeiten an den Kleinen, ließen es bei den Großen nicht zu Ende laufen.
quelle
y5Whitespace ersetzen ?K=5C ++ - 863 Bytes, ungolfed
Dies läuft ziemlich schnell im selben Ballpark wie die in Rust geschriebene Lösung (ungefähr 6-mal so schnell beim Kompilieren mit aktivierter Optimierung). Ich werde heute Abend noch Golf spielen (also abends in Schweden).
quelle