| Bytes | Lang | Time | Link |
|---|---|---|---|
| nan | 230618T092337Z | 138 Aspe | |
| 003 | Clean | 171206T113104Z | Οurous |
| 003 | Clingo | 171206T042436Z | Anders K |
| nan | C++ | 171206T032621Z | Colera S |
Rust
Port of @Colera Su's C++ answer in Rust.
use std::io::{self, BufRead};
use std::cmp::Ordering;
/// Equivalent to the C++ code's `VAL_MAX`.
const VAL_MAX: usize = 250;
/// Equivalent to the C++ code's `LOG_MAX = floor(log10(VAL_MAX - 1)) + 1`.
/// Since VAL_MAX = 250, log10(249) ≈ 2.39, floor(2.39) = 2, plus 1 = 3.
const LOG_MAX: usize = 3;
/// A simple "bitset" wrapper over a fixed-size array of booleans.
#[derive(Clone)]
struct Bools {
data: [bool; VAL_MAX],
}
impl Bools {
fn new() -> Self {
Bools {
data: [false; VAL_MAX],
}
}
fn get(&self, index: usize) -> bool {
self.data[index]
}
fn set(&mut self, index: usize, value: bool) {
self.data[index] = value;
}
}
#[derive(Clone, Debug)]
struct Ocr {
l: usize,
r: usize,
g: usize,
}
// We want to sort by `l` in descending order, i.e., bigger `l` comes first.
impl PartialEq for Ocr {
fn eq(&self, other: &Self) -> bool {
self.l == other.l && self.r == other.r && self.g == other.g
}
}
impl Eq for Ocr {}
impl PartialOrd for Ocr {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
// Sort descending by `l`.
Some(self.l.cmp(&other.l).reverse())
}
}
impl Ord for Ocr {
fn cmp(&self, other: &Self) -> Ordering {
// Sort descending by `l`.
self.l.cmp(&other.l).reverse()
}
}
/// Count how many times `target` appears in `text`, returning
/// (occurrence_count, last_found_position).
fn count_occurrences(text: &str, target: &str) -> (usize, Option<usize>) {
let mut ans = 0;
let mut offset = 0;
let mut last_pos = None;
while let Some(pos) = text[offset..].find(target) {
ans += 1;
let actual_pos = offset + pos;
last_pos = Some(actual_pos);
// Move offset by 1 to find possible further occurrences.
offset = actual_pos + 1;
}
(ans, last_pos)
}
/// Depth-first search logic replicated from the C++ code:
/// `dfs(size_t a, size_t b, const std::vector<std::string>& str, bools& cnt, int t)`.
fn dfs(a: usize, b: usize, strs: &Vec<String>, cnt: &mut Bools, t: usize) -> bool {
let mut a_idx = a;
let mut b_idx = b;
// If we've reached the end of the current string, move to the next.
if b_idx == strs[a_idx].len() {
a_idx += 1;
b_idx = 0;
}
// If we've iterated through all strings, success.
if a_idx == strs.len() {
return true;
}
let s = &strs[a_idx];
let mut p = 0_usize;
// Try building numbers from up to LOG_MAX digits.
for _ in 0..LOG_MAX {
if b_idx == s.len() {
break;
}
let digit = (s.as_bytes()[b_idx] ^ b'0') as usize;
b_idx += 1;
p = p * 10 + digit;
if p < VAL_MAX && !cnt.get(p) && p != t {
cnt.set(p, true);
if dfs(a_idx, b_idx, strs, cnt, t) {
return true;
}
cnt.set(p, false);
}
}
false
}
/// Recursive function equivalent to `int cal(std::vector<std::string> str, bools cnt, int t)`.
/// Returns true/false instead of int.
fn cal(mut strs: Vec<String>, mut cnt: Bools, t: usize) -> bool {
let _n = strs.len();
// We'll gather positions we might remove or shorten from each string.
let mut pos_vec = Vec::new();
// Try each i in [0..VAL_MAX)
for i in 0..VAL_MAX {
if cnt.get(i) {
continue;
}
let mut flag = 0;
let target = i.to_string();
let mut now = Ocr { l: 0, r: 0, g: 0 };
for (j, s) in strs.iter().enumerate() {
let (occ_cnt, last_pos) = count_occurrences(s, &target);
flag += occ_cnt;
if flag > 1 {
break;
}
if occ_cnt == 1 {
if let Some(lp) = last_pos {
now = Ocr {
l: lp,
r: lp + target.len(),
g: j,
};
}
}
}
// If the target doesn't appear at all (flag == 0) and matches t, success.
if flag == 0 && t == i {
return true;
}
// If exactly one occurrence (flag == 1) and i != t, queue up for removal.
if i != t && flag == 1 {
pos_vec.push(now.clone());
cnt.set(i, true);
}
}
// If no positions to remove/shorten, we do the fallback DFS approach.
if pos_vec.is_empty() {
// Sort the strings by ascending length (like in the C++ lambda).
strs.sort_by_key(|s| s.len());
return dfs(0, 0, &strs, &mut cnt, t);
}
// Sort positions in descending order of `l`.
pos_vec.sort();
// We'll build a list for leftover pieces after removals.
let mut leftover = Vec::new();
// Remove each found substring from its string.
for p in &pos_vec {
// If removal range extends beyond the string, no solution.
if p.r > strs[p.g].len() {
return false;
}
// Substring after the removal point.
let tmp = strs[p.g][p.r..].to_string();
if tmp.len() == 1 {
let digit = (tmp.as_bytes()[0] ^ b'0') as usize;
if cnt.get(digit) {
return false;
}
cnt.set(digit, true);
} else if !tmp.is_empty() {
leftover.push(tmp);
}
// Resize current string to keep only the left part [0..p.l].
strs[p.g].truncate(p.l);
}
// Now handle any strings that remain as single digits or leftover chunks.
for s in strs {
if s.len() == 1 {
let digit = (s.as_bytes()[0] ^ b'0') as usize;
if cnt.get(digit) {
return false;
}
cnt.set(digit, true);
} else if !s.is_empty() {
leftover.push(s);
}
}
// Recurse with updated leftover strings.
cal(leftover, cnt, t)
}
/// A helper for generating permutations in Rust without requiring `usize::MAX`.
///
/// Returns `false` if we've reached the last permutation, otherwise applies the
/// "next permutation" logic in place and returns `true`.
fn next_permutation(chars: &mut [char]) -> bool {
if chars.len() < 2 {
return false;
}
// 1) Find the largest k such that chars[k] < chars[k + 1].
// If no such k exists, we're at the last permutation.
let mut k = chars.len() - 2;
while k > 0 && chars[k] >= chars[k + 1] {
k -= 1;
}
if chars[k] >= chars[k + 1] {
// No more permutations
return false;
}
// 2) Find the largest l > k such that chars[k] < chars[l].
let mut l = chars.len() - 1;
while chars[l] <= chars[k] {
l -= 1;
}
// 3) Swap chars[k] and chars[l].
chars.swap(k, l);
// 4) Reverse chars[k+1..].
chars[k + 1..].reverse();
true
}
fn main() {
// Read the input string.
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let str_input = lines.next().unwrap().unwrap();
// We'll replicate the logic of p[10] in C++ to track digit usage.
let mut p_count = vec![0_i32; 10];
// For each i in [0..VAL_MAX), increment p_count for each digit of i.
for i in 0..VAL_MAX {
for &ch in i.to_string().as_bytes() {
let digit = (ch ^ b'0') as usize;
p_count[digit] += 1;
}
}
// Decrement p_count for each digit present in the input string.
for &ch in str_input.as_bytes() {
let digit = (ch ^ b'0') as usize;
p_count[digit] -= 1;
}
// Generate all permutations of leftover digits.
let mut leftover_digits = String::new();
for (digit, &count) in p_count.iter().enumerate() {
for _ in 0..count {
leftover_digits.push((digit as u8 ^ b'0') as char);
}
}
let mut prob = Vec::new();
if !leftover_digits.is_empty() {
let mut chars: Vec<char> = leftover_digits.chars().collect();
// Sort so we can generate permutations in lexicographical order.
chars.sort_unstable();
loop {
// Convert current permutation to an integer if it doesn't start with '0'.
if chars[0] != '0' {
let s: String = chars.iter().collect();
if let Ok(val) = s.parse::<usize>() {
if val < VAL_MAX {
prob.push(val);
}
}
}
if !next_permutation(&mut chars) {
break;
}
}
}
// If there's exactly one candidate, just print and return.
if prob.len() == 1 {
println!("{}", prob[0]);
return;
}
// Otherwise, check each candidate with cal(...)
prob.sort_unstable();
prob.dedup();
for &candidate in &prob {
let cnt = Bools::new();
if cal(vec![str_input.clone()], cnt, candidate) {
println!("{}", candidate);
}
}
}
Clean, ~0.3s
Fixed a huge bug in the algorithm, need to re-optimize it now.
module main
import StdEnv
import StdLib
import System.CommandLine
maxNum = 250
sample = "11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025"
case1 = "6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102"
case2 = "14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219"
case3 = "1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144"
case4 = "2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851"
failing = "0102030405060708090100101102103104105106107108109110120130140150160170180190200201202203204205206207208209210220230240249248247246245244243242241239238237236235234233232229228227226225224223222221219218217216215214213212211199198197196195194193192191189188187186185184183182181179178177176175174173172171169168167166165164163162161159158157156155154153152151149148147146145144143142141139138137136135134133132131129128127126125124123122121119118117116115114113112111999897969594939291898887868584838281797877767574737271696867666564636261595857565554535251494847464544434241393837363534333231292827262524232221191817161514131211987654321"
dupes = "19050151158951391658227781234527110196235731198137214733126868520474181772192213718517314542182652441211742304719519143231236593134207203121171237201705111617211824810013324511511436253946122155201534113626129692410611318356178791080921122151321949681166200188841675156120546124912883216212189712281541382202411041372421642917614416870223753814121124318415710310515010682172099012716167102179894920613516297239186222232225635312262134019719915382229399107111802082341491811011604815220291125247641482401691871755205639495788414314011714616366130175601931092467744819271230159131158714761192105218019822421812423322919341426216523821428232"
:: Position :== [Int]
:: Positions :== [Position]
:: Digit :== (Char, Int)
:: Digits :== [Digit]
:: Number :== ([Char], Positions)
:: Numbers :== [Number]
:: Complete :== (Numbers, [Digits])
numbers :: [[Char]]
numbers = [fromString (toString n) \\ n <- [0..(maxNum-1)]]
candidates :: [Char] -> [[Char]]
candidates chars
= moreCandidates chars []
where
moreCandidates :: [Char] [[Char]] -> [[Char]]
moreCandidates [] nums
= removeDup (filter (\num = isMember num numbers) nums)
moreCandidates chars []
= flatten [moreCandidates (removeAt i chars) [[c]] \\ c <- chars & i <- [0..]]
moreCandidates chars nums
= flatten [flatten [moreCandidates (removeAt i chars) [ [c : num] \\ num <- nums ]] \\ c <- chars & i <- [0..]]
singletonSieve :: Complete -> Complete
singletonSieve (list, sequence)
| (list_, sequence_) == (list, sequence)
= reverseSieve (list, sequence)
= (list_, sequence_)
where
singles :: Numbers
singles
= filter (\(_, i) = length i == 1) list
list_ :: Numbers
list_
= [(a, filter (\n = not (isAnyMember n (flatten [flatten b_ \\ (a_, b_) <- singles | a_ <> a]))) b) \\ (a, b) <- list]
sequence_ :: [Digits]
sequence_
= foldr splitSequence sequence (flatten (snd (unzip singles)))
reverseSieve :: Complete -> Complete
reverseSieve (list, sequence)
# sequence
= foldr splitSequence sequence (flatten (snd (unzip singles)))
# list
= [(a, filter (\n = not (isAnyMember n (flatten [flatten b_ \\ (a_, b_) <- singles | a_ <> a]))) b) \\ (a, b) <- list]
# list
= [(a, filter (\n = or [any (isPrefixOf n) (tails subSeq) \\ subSeq <- map (snd o unzip) sequence]) b) \\ (a, b) <- list]
= (list, sequence)
where
singles :: Numbers
singles
= [(a, i) \\ (a, b) <- list, i <- [[subSeq \\ subSeq <- map (snd o unzip) sequence | isMember subSeq b]] | length i == 1]
splitSequence :: Position [Digits] -> [Digits]
splitSequence split sequence
= flatten [if(isEmpty b) [a] [a, drop (length split) b] \\ (a, b) <- [span (\(_, i) = not (isMember i split)) subSeq \\ subSeq <- sequence] | [] < max a b]
indexSubSeq :: [Char] Digits -> Positions
indexSubSeq _ []
= []
indexSubSeq a b
# remainder
= indexSubSeq a (tl b)
| startsWith a b
= [[i \\ (_, i) <- take (length a) b] : remainder]
= remainder
where
startsWith :: [Char] Digits -> Bool
startsWith _ []
= False
startsWith [] _
= False
startsWith [a] [(b,_):_]
= a == b
startsWith [a:a_] [(b,_):b_]
| a == b
= startsWith a_ b_
= False
missingNumber :: String -> [[Char]]
missingNumber string
# string
= [(c, i) \\ c <-: string & i <- [0..]]
# locations
= [(number, indexSubSeq number string) \\ number <- numbers]
# digits
= [length (indexSubSeq [number] [(c, i) \\ c <- (flatten numbers) & i <- [0..]]) \\ number <-: "0123456789"]
# missing
= (flatten o flatten) [repeatn (y - length b) a \\ y <- digits & (a, b) <- locations]
# (answers, _)
= hd [e \\ e <- iterate singletonSieve (locations, [string]) | length (filter (\(a, b) = (length b == 0) && (isMember a (candidates missing))) (fst e)) > 0]
# answers
= filter (\(_, i) = length i == 0) answers
= filter ((flip isMember)(candidates missing)) ((fst o unzip) answers)
Start world
# (args, world)
= getCommandLine world
| length args < 2
= abort "too few arguments\n"
= flatlines [foldr (\num -> \str = if(isEmpty str) num (num ++ [',' : str]) ) [] (missingNumber arg) \\ arg <- tl args]
Compile with clm -h 1024M -s 16M -nci -dynamics -fusion -t -b -IL Dynamics -IL Platform main
This works by taking every number the string has to contain, and counting the number of places the required digit sequence is present in the string. It then repeatedly does these steps:
- If number has no possible positions, that's the answer
- Remove every number with one possible position (call these
singles) - Remove every position from all remaining numbers which overlaps with any positions from the previously removed numbers (the
singles)
Clingo, ≈ 0.03 seconds
This is too fast to be accurately measured—you’ll need to allow larger input cases rather than artificially stopping at 250.
% cat(I) means digits I and I+1 are part of the same number.
{cat(I)} :- digit(I, D), digit(I+1, E).
% prefix(I, X) means some digits ending at I are part of the same
% number prefix X.
prefix(I, D) :- digit(I, D), not cat(I-1), D < n.
prefix(I, 10*X+D) :- prefix(I-1, X), digit(I, D), cat(I-1), X > 0, 10*X+D < n.
% Every digit is part of some prefix.
:- digit(I, D), {prefix(I, X)} = 0.
% If also not cat(I), then this counts as an appearance of the number
% X.
appears(I, X) :- prefix(I, X), not cat(I).
% No number appears more than once.
:- X=0..n-1, {appears(I, X)} > 1.
% missing(X) means X does not appear.
missing(X) :- X=0..n-1, {appears(I, X)} = 0.
% Exactly one number is missing.
:- {missing(X)} != 1.
#show missing/1.
Example input
Input is a list of (k, kth digit) pairs. Here is problem 1:
#const n = 250.
digit(0,6;1,9;2,6;3,6;4,4;5,1;6,0;7,8;8,1;9,9;10,6;11,1;12,0;13,5;14,2;15,1;16,5;17,3;18,0;19,2;20,9;21,1;22,3;23,6;24,8;25,3;26,4;27,9;28,6;29,8;30,2;31,3;32,0;33,9;34,2;35,1;36,7;37,5;38,9;39,8;40,5;41,7;42,0;43,5;44,9;45,2;46,0;47,1;48,1;49,8;50,7;51,2;52,0;53,2;54,2;55,4;56,8;57,2;58,0;59,1;60,8;61,3;62,1;63,2;64,2;65,2;66,0;67,2;68,4;69,1;70,2;71,4;72,6;73,9;74,1;75,1;76,2;77,9;78,8;79,9;80,1;81,3;82,3;83,1;84,7;85,4;86,1;87,9;88,7;89,2;90,1;91,9;92,2;93,0;94,7;95,1;96,8;97,2;98,1;99,7;100,3;101,1;102,3;103,7;104,1;105,8;106,0;107,8;108,0;109,8;110,5;111,7;112,2;113,3;114,2;115,1;116,7;117,7;118,1;119,3;120,4;121,2;122,3;123,2;124,4;125,8;126,1;127,5;128,5;129,1;130,0;131,2;132,0;133,0;134,1;135,0;136,1;137,1;138,2;139,5;140,1;141,9;142,1;143,7;144,2;145,6;146,5;147,2;148,0;149,3;150,1;151,6;152,3;153,1;154,1;155,1;156,3;157,7;158,9;159,1;160,1;161,0;162,5;163,1;164,2;165,2;166,1;167,1;168,6;169,3;170,1;171,9;172,4;173,5;174,8;175,1;176,5;177,3;178,2;179,4;180,4;181,2;182,6;183,1;184,5;185,8;186,2;187,1;188,3;189,5;190,5;191,1;192,0;193,0;194,9;195,0;196,2;197,3;198,5;199,1;200,1;201,6;202,1;203,3;204,9;205,6;206,1;207,1;208,6;209,4;210,1;211,2;212,6;213,7;214,6;215,9;216,1;217,1;218,4;219,1;220,6;221,7;222,9;223,6;224,1;225,2;226,2;227,1;228,5;229,2;230,2;231,2;232,6;233,6;234,0;235,1;236,1;237,2;238,1;239,2;240,7;241,4;242,2;243,1;244,3;245,2;246,1;247,9;248,0;249,1;250,8;251,6;252,2;253,0;254,4;255,1;256,8;257,2;258,7;259,7;260,4;261,5;262,1;263,0;264,6;265,5;266,2;267,2;268,4;269,3;270,7;271,2;272,0;273,8;274,3;275,6;276,2;277,0;278,6;279,2;280,2;281,7;282,1;283,6;284,8;285,4;286,6;287,4;288,0;289,4;290,3;291,8;292,1;293,7;294,4;295,3;296,1;297,5;298,7;299,3;300,8;301,1;302,3;303,5;304,6;305,4;306,1;307,1;308,7;309,1;310,6;311,9;312,9;313,5;314,1;315,0;316,4;317,2;318,1;319,0;320,1;321,5;322,1;323,9;324,9;325,1;326,2;327,8;328,2;329,3;330,9;331,8;332,8;333,1;334,4;335,4;336,2;337,2;338,4;339,2;340,3;341,8;342,2;343,3;344,6;345,1;346,2;347,1;348,2;349,3;350,1;351,7;352,1;353,6;354,3;355,1;356,4;357,9;358,2;359,3;360,2;361,8;362,3;363,9;364,2;365,3;366,3;367,8;368,2;369,3;370,4;371,1;372,8;373,9;374,1;375,5;376,4;377,4;378,7;379,1;380,4;381,2;382,1;383,6;384,2;385,7;386,7;387,1;388,4;389,1;390,2;391,0;392,9;393,2;394,4;395,9;396,2;397,1;398,4;399,1;400,9;401,8;402,7;403,5;404,2;405,1;406,7;407,1;408,0;409,9;410,1;411,7;412,1;413,2;414,2;415,3;416,5;417,4;418,1;419,5;420,6;421,1;422,3;423,1;424,4;425,6;426,6;427,2;428,1;429,6;430,5;431,1;432,5;433,0;434,6;435,1;436,8;437,1;438,2;439,2;440,7;441,3;442,1;443,4;444,0;445,1;446,3;447,0;448,2;449,4;450,0;451,1;452,7;453,0;454,9;455,7;456,2;457,1;458,8;459,1;460,1;461,7;462,6;463,1;464,7;465,9;466,1;467,6;468,6;469,5;470,3;471,1;472,7;473,8;474,1;475,8;476,5;477,1;478,1;479,5;480,2;481,1;482,7;483,8;484,2;485,2;486,5;487,2;488,4;489,2;490,1;491,9;492,2;493,4;494,4;495,5;496,1;497,4;498,7;499,2;500,2;501,9;502,9;503,9;504,1;505,6;506,1;507,3;508,5;509,1;510,5;511,9;512,1;513,1;514,1;515,2;516,2;517,2;518,2;519,3;520,4;521,1;522,9;523,1;524,8;525,7;526,8;527,6;528,2;529,1;530,6;531,9;532,3;533,1;534,2;535,0;536,1;537,3;538,1;539,2;540,4;541,1;542,5;543,0;544,6;545,7;546,2;547,3;548,7;549,1;550,4;551,3;552,2;553,0;554,5;555,1;556,1;557,9;558,2;559,5;560,1;561,0;562,7;563,2;564,4;565,3;566,5;567,6;568,1;569,7;570,2;571,2;572,8;573,2;574,4;575,7;576,1;577,9;578,5;579,1;580,3;581,8;582,1;583,6;584,0;585,1;586,2;587,4;588,1;589,5;590,1;591,8;592,4;593,1;594,0;595,3;596,1;597,8;598,4;599,1;600,4;601,2;602,1;603,1;604,2;605,1;606,2;607,8;608,7;609,0;610,9;611,4;612,1;613,1;614,1;615,1;616,8;617,3;618,3;619,1;620,9;621,3;622,1;623,4;624,5;625,1;626,2;627,3;628,2;629,4;630,5;631,1;632,8;633,8;634,1;635,0;636,2).
Example output
$ clingo missing.lp problem1.lp
clingo version 5.2.2
Reading from missing.lp ...
Solving...
Answer: 1
missing(148)
SATISFIABLE
Models : 1+
Calls : 1
Time : 0.032s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.032s
C++, 5000 random test cases in 6.1 seconds
This is practically fast, but there may exist some testcases that make it slow. Complexity unknown.
If there are multiple solutions, it will print them all. Example.
Explanation:
Count the occurrences of digits.
List all possible answers.
Check if a candidate is a valid answer:
3-1. Try to split the string(s) by numbers which only occur once and mark it as identified, except the candidate.
For example,2112282526022911192312416102017731561427221884513has only one14, so it can be split into211228252602291119231241610201773156and27221884513.3-2. If any split string has length 1, mark it as identified.
If any contradiction is made (identified more than once), the candidate is not valid.
If we cannot find the candidate in the string, the candidate is valid.3-3. If any split is made, repeat step 3-1. Otherwise, do a brute force search to check if the candidate is valid.
#include <cmath>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
const int VAL_MAX = 250;
const int LOG_MAX = log10(VAL_MAX - 1) + 1;
using bools = std::bitset<VAL_MAX>;
std::pair<size_t, size_t> count(const std::string& str, const std::string& target)
{
size_t ans = 0, offset = 0, pos = std::string::npos;
for (; (offset = str.find(target, offset)) != std::string::npos; ans++, pos = offset++);
return std::make_pair(ans, pos);
}
bool dfs(size_t a, size_t b, const std::vector<std::string>& str, bools& cnt, int t)
{ // input: string id, string position, strings, identified, candidate
if (b == str[a].size()) a++, b = 0;
if (a == str.size()) return true; // if no contradiction on all strings, the candidate is valid
int p = 0;
for (int i = 0; i < LOG_MAX; i++) { // assume str[a][b...b+i] is a number
if (str[a].size() == b) break;
p = p * 10 + (str[a][b++] ^ '0');
if (p < VAL_MAX && !cnt[p] && p != t) { //if no contradiction
cnt[p] = true;
if (dfs(a, b, str, cnt, t)) return true; // recursively check
cnt[p] = false;
}
}
return false;
}
struct ocr {
int l, r, G;
bool operator<(const ocr& i) const { return l > i.l; }
};
int cal(std::vector<std::string> str, bools cnt, int t)
{ // input: a list of strings, whether a number have identified, candidate
// try to find numbers that only occur once in those strings
int N = str.size();
std::vector<ocr> pos;
for (int i = 0; i < VAL_MAX; i++) {
if (cnt[i]) continue; // try every number which haven't identified
int flag = 0;
std::string target = std::to_string(i);
ocr now;
for (int j = 0; j < N; j++) { // count occurences
auto c = count(str[j], target);
if ((flag += c.first) > 1) break;
if (c.first) now = {c.second, c.second + target.size(), j};
}
if (!flag && t == i) return true; // if cannot find the candidate, then it is valid
if (i != t && flag == 1) pos.push_back(now), cnt[i] = true;
// if only occur once, then its position is fixed, mark as identified
}
if (!pos.size()) { // if no number is identified, do a brute force search
std::sort(str.begin(), str.end(), [](const std::string& a, const std::string& b){return a.size() < b.size();});
return dfs(0, 0, str, cnt, t);
}
std::sort(pos.begin(), pos.end());
std::vector<std::string> lst;
for (auto& i : pos) { // split strings by identified numbers
if ((size_t)i.r > str[i.G].size()) return false;
std::string tmp = str[i.G].substr(i.r);
if (tmp.size() == 1) { // if split string has length 1, it is identified
if (cnt[tmp[0] ^ '0']) return false; // contradiction if it is identified before
cnt[tmp[0] ^ '0'] = true;
}
else if (tmp.size()) lst.push_back(std::move(tmp));
str[i.G].resize(i.l);
}
for (auto& i : str) { // push the remaining strings; same as above
if (i.size() == 1) {
if (cnt[i[0] ^ '0']) return false;
cnt[i[0] ^ '0'] = true;
}
else if (i.size()) lst.push_back(std::move(i));
}
return cal(lst, cnt, t); // continue the split step with new set of strings
}
int main()
{
std::string str;
std::vector<ocr> pos;
std::vector<int> prob;
std::cin >> str;
int p[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
for (int i = 0; i < VAL_MAX; i++)
for (char j : std::to_string(i)) p[j ^ '0']++;
for (char i : str) p[i ^ '0']--; // count digit occurrences
{
std::string tmp;
for (int i = 0; i < 10; i++)
while (p[i]--) tmp.push_back(i ^ '0');
do { // list all possible candidates (at most 4)
int c = std::stoi(tmp);
if (c < VAL_MAX && tmp[0] != '0') prob.push_back(c);
} while (std::next_permutation(tmp.begin(), tmp.end()));
}
if (prob.size() == 1) { std::cout << prob[0] << '\n'; return 0; }
// if only one candidate, output it
for (int i : prob) // ... or check if each candidate is valid
if (cal({str}, bools(), i)) std::cout << i << '\n';
}