21
\$\begingroup\$

A new code-golfer, Joe, just registered to the site. He has 1 reputation but determined to reach all his lucky numbers in reputation exactly. Joe believes in higher powers which will help him to achieve his goal with minimal amount of (his or others) actions. As a new user he also believes that negative reputation is possible.

You should write a program or function which helps Joe to compute how many action should he expect.

Details

  • The actions can change the reputation by the following amounts (all actions are available at every step regardless of stackexchange rules):

    answer accepted:     +15
    answer voted up:     +10
    question voted up:    +5
    accepts answer:       +2
    votes down an answer: −1
    question voted down:  −2
    
  • Other special reputation changes are disregarded.

  • Lucky numbers can be negative and can be reached in any order.
  • Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Input

  • Joe's lucky numbers as a list of integers in a common form of your language.

Output

  • The number of minimum actions needed as a single integer.
  • Output could be printed to stdout or returned as an integer.

Examples

Input => Output (Example reputation states)

1                     => 0  (1)
3 2 1                 => 2  (1 -> 3 -> 2)
2 10 50               => 7  (1 -> 3 -> 2 -> 12 -> 10 -> 25 -> 40 -> 50)
10 11 15              => 3  (1 -> 11 -> 10 -> 15)
42 -5                 => 7  (1 -> -1 -> -3 -> -5 -> 10 -> 25 -> 40 -> 42)
-10                   => 6  (1 -> -1 -> -3 -> -5 -> -7 -> -9 -> -10)
15 -65                => 39
7 2015 25 99          => 142
-99 576 42 1111 12345 => 885

This is code-golf so the shortest entry wins.

\$\endgroup\$
1
\$\begingroup\$

C# - 501 Bytes

Update 551 -> 501 Bytes

namespace System.Linq{class A {static void Main(){var i = c(new int[]{10,11,15});Console.WriteLine(i);Console.ReadLine();}private static int c(int[] a){var o=a.OrderBy(x => x).ToArray();int d=1,count=0;for(var i=0;i<a.Length;i++){if(o[i]==d)i++;int c=o[i],b=o.Length>=i+2?o[i+1]-o[i]:3;if(b<=2){i++;c=o[i];}while(d!=c){if(d>c){var e=d-c;if(e>1)d-=2;else d-=1;}else if(c>d){var e=c-d+2;if(e>14)d+=15;else if(e>9)d+=10;else if(e>4)d+=5;else if(e>2)d+=2;}count++;}if(b<=2){d-=b;count++;}}return count;}}}

Ungolfed code

namespace System.Linq {
    class Program {
        static void Main(){
            var i = CalculateNumbers(new int[]{10,11,15});
            Console.WriteLine(i);
            Console.ReadLine();
        }
        private static int CalculateNumbers(int[] numbers){
            var ordered = numbers.OrderBy(x => x).ToArray();
            int cur = 1, count = 0;
            for (var i = 0; i < numbers.Length; i++){
                if (ordered[i] == cur) i++;
                int val = ordered[i], next = ordered.Length >= i+2 ? ordered[i + 1] - ordered[i] : 3;
                if (next <= 2){
                    i++;
                    val = ordered[i];
                }
                while (cur != val){
                    if (cur > val){
                        var dif = cur - val;
                        if (dif > 1)
                            cur -= 2;
                        else
                            cur -= 1;
                    } else if (val > cur){
                        var dif = val - cur + 2;
                        if (dif > 14)
                            cur += 15;
                        else if (dif > 9)
                            cur += 10;
                        else if (dif > 4)
                            cur += 5;
                        else if (dif > 2)
                            cur += 2;
                    }
                    count++;
                }
                if (next <= 2){
                    cur -= next;
                    count++;
                }
            }
            return count;
        }
    }
}
\$\endgroup\$
16
\$\begingroup\$

Rust, 929 923 characters

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]}}

This was fun!


Commentary on the implementation

So I'm obviously not too happy with the size. But Rust is absolutely terrible at golfing anyway. The performance, however, is wonderful.

The code solves each of the test cases correctly in a near-instantaneous amount of time, so performance is obviously not an issue. For fun, here's a much more difficult test case:

1234567 123456 12345 1234 123 777777 77777 7777 777

for which the answer is 82317, which my program was able to solve on my (medium-performance) laptop in 1.66 seconds (!), even with the recursive brute-force Hamiltonian path algorithm.

Observations

  • First we should build a modified weighted graph, with the nodes being each "lucky" number and the weights being how many changes it takes to get from one reputation level to another. Each pair of nodes must be connected by two edges, since going up is not the same as going down in reputation value (you can get +10, for example, but not -10).

  • Now we need to figure out how to find the minimum amount of changes from one rep value to another.

    • For getting from a higher value to a lower value, it's simple: just take ceil((a - b) / 2) where a is the higher value and b is the lower value. Our only logical option is to use the -2 as much as possible, and then the -1 once if necessary.

    • A low to high value is a bit more complicated, since using the greatest possible value is not always optimal (ex. for 0 to 9, the optimal solution is +10 -1). However, this is a textbook dynamic programming problem, and simple DP is enough to solve it.

  • Once we have calculated the minimum changes from each number to every other number, we are essentially left with a slight variant of TSP (travelling salesman problem). Luckily, there are a small enough number of nodes (a maximum of 5 in the hardest test case) that brute force is sufficient for this step.

Ungolfed code (heavily commented)

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] }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Awesome answer! I'm interested in Rust and the explanation is actually very helpful for learning. And just as a heads up, you can get syntax highlighting with <!-- language-all: lang-rust -->. ;) \$\endgroup\$ – Alex A. Apr 15 '15 at 14:34
  • \$\begingroup\$ I'm working on a solution, and saw that the minimal amount of changes on the low to high weight can easily be calculated in O(1) by using a very small lookup-table, like in this C-like pseudo-code floor((a-b)/15)+{0,2,1,2,2,1,3,2,2,2,1,3,2,2,2}[(a-b)%15]. Your solution could probably benefit from this. \$\endgroup\$ – Fors Apr 24 '15 at 13:03
2
\$\begingroup\$

Pyth - 43 42 bytes

Uses completely brute force approach with all permutations and combinations. Not looking to golf more because will translate to Pyth. Translated.

K5tf.Em.Am}kmhs<dbUdQsm.pk.C[15yKK2_1_2)TZ

This is even slower than the python version because I use filter instead of a while loop. Explanation coming soon, now look at the Python code.

Try it here online.

from itertools import*
Q,Z=eval(input()),0
while True:
    if any(map(lambda d:all(map(lambda k:k in map(lambda b:sum(d[:b])+1,range(len(d))),Q)),chain.from_iterable(map(lambda k:permutations(k),combinations_with_replacement([15,10,5,2,-1,-2],Z))))):
        print(Z-1)
        break
    Z+=1

Works on the small ones, didn't let it run to completion on the big ones.

\$\endgroup\$
  • \$\begingroup\$ Haven't read code properly but can you replace 10 by, say, y5 to save on whitespace? \$\endgroup\$ – Sp3000 Apr 16 '15 at 14:28
  • \$\begingroup\$ @Sp3000 it would save whitespace but not any chars overall. But I think I can save a char by compressing the list by storing K=5 \$\endgroup\$ – Maltysen Apr 16 '15 at 15:04
  • \$\begingroup\$ Note that this answer doesn't follow the rules as "Your solution has to solve any example test case under a minute". (Quote is bolded in the Details section.) \$\endgroup\$ – randomra Apr 16 '15 at 23:39
0
\$\begingroup\$

C++ - 863 bytes, ungolfed

This runs fairly fast, in the same ballpark as the solution written in Rust (about 6 times as fast when compiling with optimisation turned on). I will golf this later this evening (evening in Sweden, that is).

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

const int lookup[] = {0, 2, 1, 2, 2, 1, 3, 2, 2, 2, 1, 3, 2, 2, 2};

int distance(int start, int end) {
    return start > end
        ? (start - end + 1) / 2
        : (end - start) / 15 + lookup[(end - start) % 15];
}

int walk(int current, std::vector<int> points) {
    int min = 0;

    if (points.size() == 0) return 0;

    for (int i = 0; i < points.size(); i++) {
        std::vector<int> new_points = points;
        new_points.erase(new_points.begin() + i);

        int d = distance(current, points[i]) + walk(points[i], new_points);

        min = min && min < d ? min : d;
    }

    return min;
}

int main() {
    std::vector<int> points;

    std::string line;
    std::getline(std::cin, line);

    std::stringstream ss(line);
    int i;

    while (ss >> i)
        points.push_back(i);

    std::cout << walk(1, points) << std::endl;

    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.